[ 암호학 ] 공개 키 암호_3 (RSA)

< RSA의 키 쌍의 생성 >

  1) N을 구한다

     (작으면X) 큰 소수 2개(p,q)를 준비, N = p*q (ex.2,3,5,7,11,13, ...)

     의사난수 생성기로 p와 q를 구한다

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

     L은 RSA의 암/복호화에 사용X, 키 쌍을 만들 때 임시로 사용

     L = lcm(p-1, q-1) (L은 p-1과 q-1의 최소공배수)

  3) E를 구한다

     1<E<L과 gcd(E,L)=1(E와L은 서로 소) 두 식을 만족하는 수 E를 찾음

  4) D를 구한다

     1<D<L과 E*D mod L = 1 두 식을 만족하는 수 E를 찾음

---

  ex)) RSA의 예시, 원래 p와 q는 큰 소수여야 하지만 예시에서는 작은 소수를 선택함.

  1) p와 q 선택 => p=17, q=19

  2) N 구하기 => N = p * q = 17 * 19 = 323

  3) L 구하기 => L = lcm(p-1, q1) = lcm(16,18) = 144

  4) E 구하기 => gcd(E,L) = 1이 되는 수 E를 선택. 예시로 5 선택

  5) D 구하기 => E*D mod L = 5 * 29 mod 144 = 145 mod 144=1

  D=29

     ==>> 공개 키 : (E, N) = (55, 323) / 개인 키 : (D, N) = (29, 323)

---

암호화

평문은 N=323보다 작은 수 (나머지이기 때문에 작아야 한다.

예로 평문을 123이라고 가정하고 암호화를 해보자

(평문)Emod N = 1235 mod 323 = 225(암호문)

 

중요 : 평문의 크기는 N보다 작아야 함!

문제점 : 평문이 0이면 암호문도 0이다!

평문이 1이면 암호문도 1이다!(평문의 E제곱이기 때문)

큰 수(긴 평문)는 암/복호화 하기 힘들다.

---

< 중간자 공격 > : RSA 알고리즘에서 그나마 유효한 공격

[ 멜로리에 의한 중간자 공격 ]

  1. 엘리스가 밥한테 메시지를 보낸다 (밥의 공개키가 필요)

  2. 만약 이 중간에 멜로리가 있으면 밥의 공개키를 훔치고 멜로리의 키로 바꿔치기한다.

  3. 엘리스는 멜로리의 공개키로 암호화를 한다. 그 암호문을 멜로리가 가로챈다.

  4. 멜로리의 공개키로 암호화를 했으니 멜로리의 개인 키로 복호화도 가능하다.

  5. 위조문을 만들어서 아까 탈취했던 밥의 공개키로 암호화 후 전달.

  6. 사실 밥의 공개키가 확실한 것은 아니다.

---

기타 공개키 암호

> ELGamal 방식

> Rabin 방식

> 타원곡선 암호

> etc...