공개키암호 - RSA

RSA는 교수님께서 공개키 중에서 가장 중요한 암호라고 언급하셨다. 엇 그럼 시험출제각?

​

얘는 배낭 암호보다 이해하기 어려운데, 공식만 외운다면 푸는 방법은 배낭 암호보다 훨씬 간단하다.

​

RSA는 배낭 암호와 동일하게 공개키로 암호화를 하고 개인키로 복호화를 한다.

​

RSA를 이용해 공개키와 개인키를 만들어내기 위해서는 제법 큰 수인 서로소 관계인 p와 q가 필요하다.

​

얘들로 계수인 N, 암호화 지수인 e, 복호화 지수인 d를 만든다.

​

N = p*q

e = (p-1)(q-1)과 서로소 관계인 정수

ed = 1 mod(p-1)(q-1)

​

공개키는 (N,e)가 되고 개인키는 d가 된다.

​

암호화, 복호화하는 공식은 아래와 같다.

가장 아래의 식은 오일러 정리를 통해 성립이 된다.

​

예시를 들어보겠다.

​

'제법 큰 수'인 서로소 관계인 p와 q를 각각 11, 3으로 지정한다.

​

N = p*q 이므로 N = 33이 된다.

​

e는 (p-1)(q-1)과 서로소 관계인 수 이므로 e는 20과 서로소인 3으로 지정한다.

​

ed = 1 mod (p-1)(q-1)이므로 대입하면 3d = 1mod20 이 되고, d는 7이라는 값을 얻게 된다.

​

따라서 공개키는 (33,3)이 되고 개인키는 7이 된다.

​

평문 M = 15를 암호화하려면 C = M^e mod N 을 사용하면 된다. 대입하면 C = 15^3 mod 33 = 9

​

암호문 C를 복호화하려면 M = C^d mod N 을 사용하면 된다. 대입하면 M = 9^7 mod 33 = 15

​

복호화할 때 지수가 크면 계산속도가 굉장히 느려지는데, 꼼수(?)를 쓰면 훨씬 낮은 수로 값을 구할 수 있다.

​

9^7mod33 = (9^2)^3 * 9 mod 33 = (81)^3 * 9 mod 33 = 15^3 * 9 mod 33 = 225 * 15 * 9 mod 33 = 27 * 15 * 9 mod 33 = 27 * 3 mod 33 = 15

 

엄청 조잡하게 했는데 훨씬 더 간단하게 가능하다.