2장(2)

알고리즘 : 어떠한 문제를 해결하기 위한 여러 동작들의 모임. 유한성(언젠가는 끝나야함)

• 명확성
• 유한성(종결성)
• 효율성 : 모든 과정은 명백하게 실행 가능

분석 기준 - 정확성, 최적성, 작업량(running time), 사용량(memory)

딥러닝 알고리즘과 암호 알고리즘은 서로 유사함.

---

[모듈로 연산(Modular Arithmetic)]

Start Idea : 컴퓨터에서 무한한 정수를 다 사용할 수 없기 때문에 모듈로 연산을 이용해 유한한 정수 집합을 사용.

n : modulus(모듈러), r : residus

입력값 n : modulus(모듈러)

결과값 r : residue(나머지) = [0,n-1]

 

결과값인 나머지들로 이루어진 정수 체계를 사용하는 것.

이 정수 집합을 Zn (최소 잉여 집합) 이라고 한다.

 

r이 음수일 경우, r = r + modulus

ex) -18 mod 14 = 10 ( -4 + 14 = 10 )

- 합동(Congruence)

ex) -8 ≡ 2 ≡ 12 ≡ 22 (mod10)

- 잉여류(Residue Classes)

[a] : 모듈로 n에 합동인 정수들의 집합 (a : [0,n-1], 모듈러로 나온 나머지 값)

#include <stdio.h>
#include <string.h>
#include <malloc.h>

int mod(int n1, int n2){
	int r = n1%n2;
    if(n1<0) r = r+n2;
    return r;
}

void Resuide_Classes(int n){
	int **p = (int **)malloc(sizeof(int*)*n);
    for(int i=0;i<n;i++){
    	p[i] = (int *)malloc(sizeof(int)*10);
    }
    for(int i=0;i<n;i++){
    	printf("[%d] : ", i);
        for(int j=0;j<10;j++){
        	p[i][j] = i + n*j;
            printf("%d ", p[i][j]);
        }
        printf("\n");
    }
    for(int i=0;i<n;i++){
    	free(p[i]);
    }
    free(p);
}

 

- 모듈로 연산자의 성질

(a+b) mod n = [(a mod n) + (b mod n)] mod n

(a-b) mod n = [(a mod n) - (b mod n)] mod n

(a*b) mod n = [(a mod n) * (b mod n)] mod n

---

[덧셈 암호(Additive Cipher), 이동 암호(Shift Cipher)]

Encryption : C = (P + k) mod 26

Decryption : P = (C - k) mod 26

#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>
#include <string.h>

int mod(int n1) {
	int r = n1 % 26;
	if (n1<0) r = r + 26;
	return r;
}

void Encryption(char p[], int k) {
	int str = strlen(p);
	for (int i = 0; i < str; i++) {
		int a; int r;
		if ('A' <= p[i] && p[i] <= 'Z') a = (int)p[i] - 65;
		else if ('a' <= p[i] && p[i] <= 'z') a = (int)p[i] - 97;
		else continue;
		r = mod(a + k);
		if ('A' <= p[i] && p[i] <= 'Z') p[i] = (char)(r+65);
		else p[i] = (char)(r + 97);
	}
	printf("%s\n", p);
}

void Decryption(char p[], int k) {
	int str = strlen(p);
	for (int i = 0; i < str; i++) {
		int a; int r;
		if ('A' <= p[i] && p[i] <= 'Z') a = (int)p[i] - 65;
		else if ('a' <= p[i] && p[i] <= 'z') a = (int)p[i] - 97;
		else continue;
		r = mod(a - k);
		if ('A' <= p[i] && p[i] <= 'Z') p[i] = (char)(r + 65);
		else p[i] = (char)(r + 97);
	}
	printf("%s\n", p);
}

int main()
{
	char p[20];
	int key;
	int choice;
	printf("1. 암호화 2. 복호화\n");
	scanf("%d", &choice);
	switch (choice) {
	case 1:
		printf("암호화할 평문을 입력하세요 : ");
		scanf("%s", p);
		printf("key를 입력하세요 : ");
		scanf("%d", &key);
		Encryption(p, key);
		break;
	case 2:
		printf("복호화할 암호문을 입력하세요 : ");
		scanf("%s", p);
		printf("key를 입력하세요 : ");
		scanf("%d", &key);
		Decryption(p, key);
		break;
	default :
		break;
	}
}

---

+ 정수론에서의 모듈러 연산

 

 

 

 

 

 

---

* 덧셈에 대한 역원(Additive Inverse)

a + b ≡ 0 (mod n)

=> 모듈러 연산에서 모든 정수는 덧셈에 대한 역원을 갖는다.

 

* 곱셈에 대한 역원(Multiplicative Inverse)

a * b ≡ 1 (mod n)

=> 모듈러 연산에서, 곱셈에 대한 역원이 있을 수도 있고 없을 수도 있다.

<sol> 확장 유클리드 알고리즘 적용, t만 이용

gcd(n,b) = 1일 때, Zn에서 b의 곱셈에 대한 역원을 찾을 수 있다.

#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>

int t1 = 0; int t2 = 1;
int d; int n;

void gcd(int n1, int n2) {
	int r = n1 % n2;
	if (r == 0) {
		d = n2;
		return;
	}
	else {
		n1 = n2;
		n2 = r;
		gcd(n1, n2);
	}
}

void ext_gcd(int n1, int n2) {
	int r = n1 % n2;
	int q = n1 / n2;
	int tmp;
	if (r == 0) {
		while (t2<0 || t2 >= n) {
			if (t2 < 0) t2 = t2 + n;
			else t2 = t2 - n;
		}
		return;
	}
	else {
		n1 = n2;
		n2 = r;
		tmp = t1 - q * t2;
		t1 = t2;
		t2 = tmp;
		ext_gcd(n1, n2);
	}
}

int main() {
	int b;
	scanf("%d %d", &n, &b);
	gcd(n, b);
	if (d != 1) printf("Z%d에서 %d에 대한 역원이 존재하지 않습니다.", n, b);
	else {
		ext_gcd(n, b);
		printf("Z%d에서 %d에 대한 역원은 %d이다.\n", n, b, t2);
	}
}

---

[곱셈 암호(Multiplicative Cipher)]

평문과 암호문은 Z26의 원소, 키는 Z26*의 원소(복호화를 위해 역원이 존재해야하므로)

-> 역원이 없는 짝수, 13은 키로 사용 불가능

Encryption : C = (P * k) mod 26

Decryption : P = (C * k^-1) mod 26

#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>
#include <string.h>

int t1 = 0; int t2 = 1;

void init() {
	t1 = 0; t2 = 1;
}

int mod(int n1) {
	int r = n1 % 26;
	if (n1<0) r = r + 26;
	return r;
}

void ext_gcd(int n1, int n2) {
	int r = n1 % n2;
	int q = n1 / n2;
	int tmp;
	if (r == 0) {
		while (t2<0 || t2 >= 26) {
			if (t2 < 0) t2 = t2 + 26;
			else t2 = t2 - 26;
		}
		return;
	}
	else {
		n1 = n2;
		n2 = r;
		tmp = t1 - q * t2;
		t1 = t2;
		t2 = tmp;
		ext_gcd(n1, n2);
	}
}

void Encryption(char p[], int k) {
	int str = strlen(p);
	for (int i = 0; i < str; i++) {
		int a; int r;
		if ('A' <= p[i] && p[i] <= 'Z') a = (int)p[i] - 65;
		else if ('a' <= p[i] && p[i] <= 'z') a = (int)p[i] - 97;
		else continue;
		r = mod(a * k);
		if ('A' <= p[i] && p[i] <= 'Z') p[i] = (char)(r + 65);
		else p[i] = (char)(r + 97);
	}
	printf("%s\n", p);
}

void Decryption(char p[], int k) {
	int str = strlen(p);
	for (int i = 0; i < str; i++) {
		init();
		int a; int r;
		if ('A' <= p[i] && p[i] <= 'Z') a = (int)p[i] - 65;
		else if ('a' <= p[i] && p[i] <= 'z') a = (int)p[i] - 97;
		else continue;
		ext_gcd(26, k);
		r = mod(a * t2);
		if ('A' <= p[i] && p[i] <= 'Z') p[i] = (char)(r + 65);
		else p[i] = (char)(r + 97);
	}
	printf("%s\n", p);
}

int main() {
	char p[20];
	int key;
	int choice;
	printf("1. 암호화 2. 복호화\n");
	scanf("%d", &choice);
	switch (choice) {
	case 1:
		printf("암호화할 평문을 입력하세요 : ");
		scanf("%s", p);
		printf("key를 입력하세요 : ");
		scanf("%d", &key);
		Encryption(p, key);
		break;
	case 2:
		printf("복호화할 암호문을 입력하세요 : ");
		scanf("%s", p);
		printf("key를 입력하세요 : ");
		scanf("%d", &key);
		Decryption(p, key);
		break;
	default:
		break;
	}
}