RSA (Rivest, Shamir, and Adleman) 알고리즘

RSA(Rivest, Shamir, and Adleman) 알고리즘에 대해 알아봅시다.

이름에서 풍겨져 오다 시피, Rivest, Shamir, and Adleman 3명이서 뚝딱뚝딱 만들었다. (1978)

공개키 암호 알고리즘 중 하나로, 역시나 암호, 디지털 서명 모두 사용가능하다.

 

RSA에서는 평문, 암호, 키 모두 숫자이다. 가장 쉽게 설명하자면 이렇다.

 

평문을 나타내는 숫자에 E를 제곱하여 N 모듈러 연산한다.

그렇다면 여기서 키 쌍은 E와 N은 무슨 역할을 할까요.

 

E와 N이 뭔지만 알면 암호문이 짠하고 나타난다. 그럼 (N,E)은 당연히 공개키겠지?

그르타 공개키가 맞다. 

 

그리고 반대로 D와 N만 알면 복호화가 가능하다. 그럼 개인키는 (N,D)가 될 것이다.

 

N은 엄청나게 큰 숫자중 소수(Prime number) 즉, 약수가 자기와 1밖에 없는 애들..(모르는 사람 없겠지)

그 중에서 p, q 두가지를 고른다. 

N은 p와 q의 곱으로 정한다. ( N =pq)

 

그리고 여기서 Z라는 값을 하나 더 구한다.

 Z = (p-1)(q-1)

이건 E를 구할때 쓴다.

 

E는 N보다 작고 Z와 상대적 소수관계를 가져야 한다. 

무슨말인가.. 공약수가 1밖에 없는거다. 서로소라고 했던가 아마.

 

그리고 마지막에 D라는 놈을 찾는다. D는 E와 D를 곱한 값이 Z로 나누었을 때 나머지가 1이어야 한다.

ED = 1 (mod z) 가 된다.

 

정리를 한번 하자면,

N = P*Q

Z = (P-1)*(Q-1)

E < N , E와 Z는 서로소

E*D = 1 (mod Z)

 

뭐 증명도 있던데 생략하겠음.

RSA의 공개키 = (N,E)

RSA의 개인키 = (N,D)

요게 핵심이다.