RSA의 문서과 이해

정리가 잘되어 있는 문서가 있다.
http://www.parkjonghyuk.net/lecture/modernCrypto/lecturenote/chap05.pdf

정리를 하면 다음과 같다.

<E,N> 쌍 : 공개키
<D,N> 쌍 : 개인키
암호문 = 평문^E mod N
평문 = 암호문^D mod N

주) ^ 연산은 pow() 함수를 의미한다.

N,D,E 생성 순서

(1) N을 구한다

(2) L을 구한다 (L은 키 쌍을 생성할 때만 등장하는 수이다)

(3) E를 구한다

(4) D를 구한다

구하기

(1)N = p*q (p,q는 소수) : p, q 랜덤

(2)L = lcm(p-1, q-1) : lcm 최소 공배수 ex)lcm(12, 18)=36=> lcm(2*2*3,2*2*3*3)

(3)1 < E < L 조건을 만족하는 E 선택 gcd(E, L) = 1 : gcd 최대 공약수

(4)1 < D < L 조건을 만족하는 D 선택 E*D mod L = 1

예)

(1) N을 구한다

2개의 소수 p=17, q=19 를 고른다.

N = p × q = 17×19 = 323

(2) L을 구한다

L = lcm(p-1, q-1) 

= lcm(16,18) (p-1은 16, q-1은 18) 

= 144 (16과 18의 최소공배수) 

(3) E를 구한다

gcd(E, L) = gcd(E, 144) = 1 이 되는 E를 구한다

이과 같은 E는 많이 있다. 예를 들면, 다음과 같은 수이다. 

5, 7, 11, 13, 17, 19, 23, 25, 29, 31, …

여기서는 E로서 5를 골라 보겠다.
여기까지 해서 공개키는 (E,N)=(5, 323)이 되었다. 

(4) D를 구한다

D는 식 E*D mod L = 1 을 충족시켜야만 된다. 

E에 뭔가를 곱해서 mod L을 취하면 1이 되는 수를 찾아보자. 

D = 29는, 이 관계식을 충족시킨다. 왜냐 하면, 

E*D mod L = 5*29 mod 144

= 145 mod 144

= 1

„ 여기까지 해서 개인키는 (D,N)=(29, 323)이 되었다. 

(5) 암호화

‡평문은 N 미만의 수, 즉 323 미만의 수여야 한다.

평문으로서 123을 암호화해 보자.

평문^E mod N = 123^5 mod 323

= 225

‡ 따라서 암호문은 225가 된다. 

(6) 복호화

암호문 225를 복호화 하겠다. 

복호화에서는 개인 키 D = 29, N = 323을 사용 한다.

암호문^D mod N = 225^29 mod 323

= 123

• RSA에 대한 공격

‡(1) 수 D를 알면 암호문을 복호화 할 수 있다. 

그렇기 때문에 RSA에 대한 공격 방법으로서, D의 후보가 되는 수를 순서대로 시도해서 복호화한다는 전사공격을 생각할 수 있다. 

전사공격은 D의 비트 수가 크면 클수록 시도해보아야 할 수도 많아지고 계산도 복잡해지므로 점점 더 시간이 걸리며 어려워진다. 

따라서 비트 수가 충분히 크면 전사공격으로 수 D를 찾아내는 것은 현실적으로는 불가능해진다. 

‡(2) p와 q는 소수이기 때문에 N으로부터 p와 q를 구하는 것은 자연수 N을 소인수분해하는 것과 같다.

큰 수의 소인수분해를 고속으로 할 수 있는 방법이 발견되면 RSA는 해독할 수 있다

• Java Key로 저장되는 값

이전 소스를 변형하여 쌍으로 생성된 키를 출력해 보았다.

     generator.initialize(128);
     KeyPair pair = generator.generateKeyPair();
     Key pubKey = pair.getPublic();  // Kb(pub) 공개키
     Key privKey = pair.getPrivate();// Kb(pri) 개인키
     System.out.println("pub key: "+ new String(pubKey.toString()));
     System.out.println("pri key: "+ new String(privKey.toString()));

결과는 아래와 같다.

pub key: RSA Public Key
            modulus: dff077aaf0d951a074bc40121e3d5b33
    public exponent: 10001

pri key: RSA Private CRT Key
            modulus: dff077aaf0d951a074bc40121e3d5b33
    public exponent: 10001
   private exponent: 89bee85d057927735ccc19f3ac010a81
             primeP: efc54140ccaef98b
             primeQ: ef18e3b09d2c49f9
     primeExponentP: 31b480ac80421db5
     primeExponentQ: d48320cd37c5c7b1
     crtCoefficient: e04b791dd2e5a6fc

각각의 의미하는 바를 살펴보기로 하자.
modulus는 N을 의미한다. primeP,primeQ는 각각 P,Q값을 의미하고 P*Q = N이 된다.
이것을 Java로 계산해서 확인해 보았다.

  BigInteger bi1= new BigInteger("efc54140ccaef98b",16);
  BigInteger bi2= new BigInteger("ef18e3b09d2c49f9",16);
  BigInteger bi3 = bi1.multiply(bi2);
  System.out.println(bi3.toString(16));

결과가 dff077aaf0d951a074bc40121e3d5b33 딱 맞게 나왔다.
public exponent가 E를 의미하며 따라서 공개키<E,N>은 <public exponent,modulus> 가 된다. 개인키 <D,N> 는 <private exponent,modulus>가 된다.