RSA 암호화 프로그래밍

<C언어>

1) 서로 다른 큰 소수 p와 q를 선택한다.

2) n= p*q를 계산한다.

3) φ(n)=(p-1)(q-1)를 계산한다.

4) φ(n)보다 작고 φ(n)과 서로소인 임의의 자연수 e를 선택한다.

(gcd(e, φ(n))=1, 1 < e < φ(n)에 만족하는 e 선택)

5) *확장 유클리드 호제법을 이용하여 e mod φ(n)에 대한 곱의 역원, 즉 ed mod φ(n)=1인 d를 구한다.

(ed≡ 1 mod φ(n), 1 < d < φ(n)에 만족하는 d 값)

공개키={e, n}, 개인키={d, n}

 

암호화

M < n
C≡ M^e mod n

복호화

M≡ C^d mod n

[아래 코드에서 M=number]

---

* 확장 유클리드 호제법

1. 두 수 a, b(a >= b)를 준비한다.

2. r = a mod b를 준비한다.

3. r' = b mod r를 계산한다.

4. 이 과정을 계속하여 나눈 나머지가 0이 되면 나누는 수는 최대공약수이다.

​

ex) 60과 24 :

60 mod 24 = 12

24 mod 12 = 0

따라서 60과 24의 최대공약수는 12

-a mod b 모듈러 연산으로, a를 b로 나누었을 때 나머지 값 

---

두 소수  p=17, q=11를 선택

n= p*q=187

*φ(N)=(p-1)(q-1)=160

160보다 작으면서 φ(N)과 서로소인 자연수e=7

d<160이면서 demodφ(N)=1인 수 d=23

(d*7mod160=1이므로 23이 d가 된다.)

아래 코드에서는 공개키={7,187}, 개인키={23,187}이 된다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

long pow(long i, long j, long k) {
	double l, temp, p = 1;
	for (temp = 0; temp < j; temp++) {
		p = (p * ((double)i));
		l = (long)(p / k); //소수점 삭제
		p = p - (l * k);
	}
	return (long)p;
}

int gcd(a, b) {
	while (b) {
		a, b = b, a% b;
	}
	return a;
}
find_e(phi) { //e찾기
	int e, i=0;
	for (i = 2; i < phi; i++) {
		if (gcd(phi, i) == 1){
			e = i;
			break;
		}
	}
	return e;
}
find_d(phi, e) { //d찾기
	int d, i = 0;
	for (i = phi / e; i < phi; i++) {
		if (e * i % phi == 1) {
			d = i;
			break;
		}
	}
	return d;
}

//암호화
int Encryption(int number, int e, int n) {
	int i = pow(number, e, n);
	printf("RSA encryption: %d\n", i);
	return i;
}
//복호화
int Decryption(int number, int d, int n) {
	int i = pow(number, d, n);
	printf("RSA decryption: %d\n", i);
	return i;
}

int main(void) {
	int number,d,e;
	scanf("%d", &number);

	int p = 17, q = 11;
	int phi=(p-1)*(q-1), N = p * q;
	e = find_e(phi);
	d = find_d(phi, e);

	number = Encryption(number, e, N);
	Decryption(number, d, N);
	return 0;
}