[현대 암호학] 06-4. RSA

4. RSA

RSA(Rivest-Shamir-Adleman)

• https://ko.wikipedia.org/wiki/RSA_암호
• RSA는 공개 키 암호 알고리즘의 하나
• 개발자 3명의 이름(Ron Rivest, Adi Shamir, Leonard Adleman)* 로널드 라이베스트, 아디 샤므르, 레너드 애들먼

 

 

RSA 응용

• 공개 키 암호
• 디지털 서명(공개 키 서명)
• 키 교환(공개 키 전송/교환 방식)

 

 

RSA에 의한 암호화

 

• RSA에서 평문도 키도 암호문도 숫자로 변환한 뒤 실행
• RSA의 암호화는 다음 식으로 표현

 

암호문 = (평문)^E mod N

평문을 E 제곱해서 N으로 나눈 나머지

 

 

(E, N) : 공개 키

• E와 N이라는 한쌍의 수를 알면 누구라도 암호화를 행할 수 있다.
• E와 N이 RSA 암호화에 사용되는 키
• E와 N은 면밀한 계산을 통해 생성

 

 

RSA에 의한 복호화

 

• 복호화도 단순하다.
• RSA 복호화는 다음 식으로 표현

 

평문 = (암호문)^D mod N

암호문을 D 제곱해서 N으로 나눈 나머지

 

 

(D, N): 개인 키

• D와 N이라는 한쌍의 수를 알면 누구라도 복호화를 행할 수 있다.
• D와 N이 RSA 복호화에 사용되는 키
• D와 N도 면밀한 계산을 통해 생성
• E와 D는 밀접한 연관관계

 

 

RSA 암호화 복호화

 

RSA 의 암호화 / 복호화

 

 

 

 

키 쌍의 생성

 

-----------------------------------------------------------------------

암호문 = (평문)^E mod N          평문 = (암호문)^D mod N

-----------------------------------------------------------------------

 

RSA 키 쌍

 

public key(E, N), private key(D, N) => 숫자 : E, D, N

 

① N을 구한다.

• 큰 소수를 2개 준비(p & q)
• N = p × q (p, q : 소수)

 

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

• L은 RSA의 암호화나 복호화에 사용안함
• 키 쌍을 만들 때 임시로 사용
• L=LCM(p-1, q-1) : L은 p-1과 q-1의 최소공배수(Least Common Multiple)

 

③ E을 구한다.

• 다음 두 식을 만족하는 수 E를 하나 찾아낸다.
• (조건1) 1 < E < L
• (조건2) GCD(E, L) = 1 : E와 L은 서로소

 

④ D를 구한다

• 다음 두 식을 만족하는 수 E를 하나 찾아낸다.
• (조건1) 1 < D < L
• (조건2) E×D mod L = 1 : E×D와 L은 서로소

 

 

 

구체적 계산 - 키 쌍(공개 키, 개인 키)의 생성

 

• https://ko.wikipedia.org/wiki/RSA_암호
• 구체적인 수를 써서 RSA의 키 쌍 생성, 암호화/복호화를 실제로 구현
• 너무 큰 수(p와 q)를 사용하면 계산이 힘들기 때문에 작은 수를 이용하여 계산

 

 

 

RSA 공개키/개인키 구하기 예 (구할려고 하는 값 => N, E, D)

 

① p와 q 선택하기(2개의 큰 소수 p, q 선택)

• 2개의 소수 p=17, q=19 선택

 

② N 구하기(2개의 큰 소수 곱하기)

• N = p × q = 17 × 19 = 323

 

③ L 구하기

• L = LCM(p-1, q-1) = LCM(16, 18) = 144 (16과 18의 최소공배수)

 

④ E 구하기(선택하기) * (조건1) 1 < E < 144 조건을 만족하는 E 값을 하나 선택한다.

• (조건2) GCD(E, L) = 1 되는 수 E를 선택하자
• E가 될수 있는 수는 다음과 같은 수이다.  => 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, ...
• E=5 선택(다른 수를 선택해도 무방)

 

⑤ D 구하기

• (조건1) 1 < D < 144 조건을 만족하는 D 값을 하나 선택한다.
• (조건2) E × D mod L => 5 × D mod 144 = 1 => 145 mod 144 = 1 이므로 D=29

 

⑥ 따라서, 공개키, 개인키

• 공개키: (E, N) = (5, 323)
• 개인키: (D, N) = (29, 323)

 

 

 

RSA 암호화/복호화 예

 

평문은 N=323 보다 작은 수

예를 평문(P)=123이라 하고 암호화를 해 보자.

 

암호문 = (평문)^E mod N (P=123 --> C=225)

         = 1235 mod 323

         = 225

 

평문 = (암호문)^D mod N (C=225 --> P=123)

      = 22529 mod 323

      = 123