PARI / GP 를 사용한 빅데이터 연산 : RSA 암호화 및 복호화

0. 개요

RSA는 다음과 같은 순서로 암호화 및 복호화 한다.

1. 시작하기 전에

1) 단방향 연산에 대해

One-way function (단방향 연산)은 쉽다

즉 E(x) = y 일때 x가 주어졌을 때 y를 구하는것은 쉽다.

하지만 y에서 x를 구하는 것은 어렵다. 

이때 어떠한 힌트을 주어서 빨리 풀 수 있으면 되는데 이 때 어떠한 힌트를 비밀키라 한다.

2) 공개키, 개인키

우리의 공개키 파일을 열어보면 n, e의 쌍을 볼 수 있다.

이 때 N의 길이는 2048이고 e의 길이는 1024이다.

3) 알아야할 수학 지식

- 페르마의 소정리

이라 할 때 페르마의 소정리는 다음과 같다. 

엄청 풀기 어려운 문제를 각종 공식을 이용해 증명했다고 하는데 난 잘 모르겠다. 

- 인수분해 문제의 난이도와 오일러

Eulerphi(3)은 3보다 작은 수 중에 서로소인 수의 개수를 의미한다

오일러 공식은 다음과 같은데 

이 공식을 보면 결국 오일러를 구하는 것과 인수분해를 하는 것은 같은 난이도라는 것을 알 수 있다.

(여기서 pq는 n이니까 구하기 쉬어도 이를 구할려면 결국 p와 q를 알아야 한다.)

2. 오일러와 인수분해 문제 실습

1) 인수분해

p = nextprime(큰 수) 

q = nextprime(큰 수)

을 이용해 소수를 구한다.

n = p*q 

그리고 두 소수를 곱한 n 을 구한다. 

factor(n)을 하면 n의 인수를 구할 수 있다. 수가 커지면 커질 수록 굉장히 오랜시간이 걸린다.

2) 오일러 값 구하기

오일러 공식을 사용해 Zn* 의 개수를 구한다.

phi(n) = (p-1) * (q-1) 과 같다.

3. RSA 암호화

RSA를 사용하여 암호화 하는 방법은 다음과 같다.

이것의 난이도는 n을 인수분해하는 것과 같다.

이 때 e의 역원은 d 라 한다면 d는 비밀키가 된다.

phi(n) 만 알면 d를 구할 수 있는데 phi(n)은 다음을 만족하기 때문에 p 와 q를 알면 이는 구하기 쉽다.

실제 암호화 하는 방법은 다음과 같다.

1) 소수를 구한다.

p=nextprime(random(10^50))  q=nextprime(random(10^50))

2) 두 소수를 곱한 값을 구한다.

n=p*q

3) n보다 작은 램덤한 e를 구한다.

e=random(n)

4) phi(n)을 구한다. (n 보다작은 소수의 개수)

phin=(p-1)*(q-1)

5) 이 때 phi(n)와 최대공약수가 1인 e를 구한다.

while(gcd(e,phin)!=1,e=e+1)

6) e의 역수 d를 구한다 (비밀키)

d = lift(Mod(e,phin)^(-1))

7) 제대로 값이 구해졌는지 확인한다. (1이 출력되면 정상적으로 된 것이다.)

Mod(e*d,phin)

8) 메시지 m 을 작성한다.

암호화 방식은 다음과 같다. 문자 { x ,y, z, ... } 에 대한 아스키 번호를 { a, b, c, ...} 라 하고

띄어쓰기와 기본 알파벳을 포함한 총 글자수가 27자라하면 (스페이스 = 0, A =1, B= 2, ...Z = 26)

(a * 27 ^ 0)  + (b * 27 * 1) + (c * 27 ^ 2) + ....

이 방식은 사용자에 따라 얼마든지 변할 수 있다.

내가 암호화 할려는 글자는 KOREA UNIV 이다.

m=11+27*15+27^2*18+27^3*5+27^4*1+27^5*0+27^6*21+27^7*14+27^8*9

9) 암호화 함수를 작성한다.

E(x)=lift(Mod(x,n)^e)

10) 복호화 함수를 작성한다.

D(x)=lift(Mod(x,n)^d)

11) 암호화된 값은 다음과 같다.

secret_message = E(m)

12) 복호화된 메시지는 다음과 같다.

D(secret_message)

4. 파일을 사용한 RSA 암호화

위의 처럼 하면 너무 계산이 오래 걸리므로 메모장 파일에 위의 연산을 모두 작성하여 한번에 처리 한다.

/*알파벳 집합 */ {alphabet=[" ","A","B","C","D","E","F","G","H","I","J","K","L","M", "N","O","P","Q","R","S","T","U","V","W","X","Y","Z"]; } /*문자를 숫자로 */ {letter_to_number(l, n)= for(n=1,27,if(alphabet[n]==l,return(n-1))); error("invalid input."); } /*숫자를 문자로*/ {number_to_message(n, s="")= while(n>0, s = concat(s,alphabet[n%27+1]); n = n \ 27); return(s); } /*메시지를 숫자로*/ {message_to_number(w, i,n=0)= for(i=1,length(w), n = n + 27^(i-1)*letter_to_number(w[i])); return(n); } /* rsa 키 생성*/ {make_rsa_key(len, p,q,n,e,d)= p = nextprime(random(10^(len/2))); q = nextprime(random(10^(len/2+3))); n = p*q; phin = (p-1)*(q-1); e = random(phin); while(gcd(e,phin)!=1,e=e+1); d = lift(Mod(e,phin)^(-1)); return([n,e,d]); } encrypt(message, n, e) = lift(Mod(message_to_number(message),n)^e); decrypt(secret, n, d) = number_to_message(lift(Mod(secret,n)^d));

1) 다음 파일을 다운 받아 C:\Program Files (x86)\Pari-2-7-3 에 넣는다.

rsa.txt

2) read 함수를 사용해 파일을 불러온다.

read("rsa.txt")

3) 큰 값에 대한 rsa 키를 생성한다.

rsa=make_rsa_key(300)

4) n e, d 의 값을 설정한다.

n = rsa[1]; e = rsa[2]; d = rsa[3];

5) n, e 를 사용하여 공개키를 만든다.

public_key = [n,e]

6) 메시지를 입력한다. 

msg = ["K", "O", "R", "E", "A", " ", "U", "N", "I"];

7) 공개키를 사용해 메시지를 암호화한다. 

secret = encrypt(msg,n,e)

8) 개인키를 사용해 암호문을 복호화 한다. 

decrypt(secret, n, d)