161012_사진

RSA 암호화 알고리즘의 이해

HansolNexG 제품/시장

RSA 암호화 알고리즘의 이해

한솔넥스지 QA센터

 최만수 과장

  들어가기 전 여기에서 공개키 암호에 대한 개념은 설명은 하지 않습니다. 그러므로 공개키 암호에 대한 개념이 없으면 먼저 공개키 암호의 개념을 확인 하신 후 이 글을 읽는 것을 권장합니다.   RSA란? RSA는 대표적인 공개키 암호로서 Diffie와Hellman의 공개키 암호 개념을 기반으로MIT공대 연구팀 소속의 세 학자Rivest, Shamir, Adleman에 의해 탄생되었고, RSA이름은 세 학자 이름의 머리글자를 따서 만든 명칭입니다. RSA는 큰 수의 소인수분해가 매우 어렵다는 것을 기반으로 만들어 졌습니다. 즉 n=p*q일 때, p와 q로 n을 구하기는 쉬우나 n으로 p와 q를 찾기 힘들다는 소인수분해의 어려움을 이용하였습니다.   RSA 알고리즘 RSA 알고리즘을 확인하기 전에 RSA 알고리즘에서 사용하는 표기법에 대해 알아보겠습니다. RSA 알고리즘에서 사용하는 표기법은 다음과 같습니다.
  • 표기법
p, q 매우 큰 서로 다른 소수
n p*q의 합성수
gcd(a, b) a와b의 최대 공약수
φ(n) 오일러 Totient함수로, φ(n)은 n보다 작은 자연수 중에서 n과 서로 소인 자연수의 개수
a mod n 모듈러 연산으로, a를 n로 나누었을 때 나머지 값
a≡ r mod n a와 r은 n으로 나누었을 때 그 나머지가 같음 (a와 r은 합동)
e n과 함께 공개되는 공개키로 암호화 지수에 사용
d 공개되지 않는 개인키로 복호화 지수에 사용
M 평문으로 공개키를 이용하여 암호화
C 암호문으로 개인키를 이용하여 복호화
KU 공개키로 KU= {e, n}으로 표기
KR 개인키로 KR= {d, n}으로 표기
  이제 RSA알고리즘에 대해서 알아보도록 하겠습니다. 먼저 암/복호화에 사용될 키 생성 알고리즘을 확인하고 그 키를 이용하여 암/복호화하는 과정을 살펴보겠습니다.
  • 키 생성
1)    서로 다른 큰 소수 p와 q를 선택한다. 2)    n= p*q를 계산한다. 3)    φ(n)=(p-1)(q-1)를 계산한다. 4)    φ(n)보다 작고 φ(n)과 서로소인 임의의 자연수 e를 선택한다. (gcd(e, φ(n))=1, 1 < e < φ(n)에 만족하는 e 선택) 5)    확장 유클리드 호제법을 이용하여 e mod φ(n)에 대한 곱의 역원, 즉 ed mod φ(n)=1인 d를 구한다. (ed≡ 1 mod φ(n), 1 < d < φ(n)에 만족하는 d 값) 6)    공개키: KU= {e, n} 7)    개인키: KR= {d, n}
 
  • 암호화
M < n C≡ Me mod n
 
  • 복호화
M≡ Cd mod n
  예제 아래 그림은 RSA 알고리즘을 요약한 것입니다. 아래 그림의 내용을 가지고 키 생성 및 암/복호화를 진행해 보겠습니다. 예제에서는 작은 수의 소수를 선택하겠습니다. 161012_사진
  • 키 생성
    • 1) 서로 다른 큰 소수 p와 q를 선택한다. -> p=5, q=11 선택
    • 2) n= p*q를 계산한다. -> n= 5*11= 55
    • 3) φ(n)=(p-1)(q-1)를 계산한다. -> φ(n)= (5-1)(11-1)= 40
    • 4) φ(n)보다 작고 φ(n)과 서로소인 임의의 자연수 e를 선택한다. -> e= 7 선택
    • 5) 확장 유클리드 호제법을 이용하여 e mod φ(n)에 대한 곱의 역원, 즉 ed mod φ(n)=1인 d를 구한다.

-> 확장 유클리드 호제법을 이용하여 d값 구하기

φ(n)=40, e= 7 ed mod φ(n)= 7d mod 40=1   ① φ(n)을 e로 나누고 몫을 ⓑ에 곱합니다. L                     R ————————————- 40                  40          —— ⓐ [φ(n) 값] 7                  1             —— ⓑ [e와 나머지 값] 40/7= 5 5*7= 35              5*1= 5         —— ⓒ   ② ⓐ에서 ⓒ의 값을 빼줍니다. 40-35= 5            40-5= 35        ——- ⓓ   ③ ⓑ의 L열의 값을 ⓓ의 L열의 값으로 나누고 몫을 ⓕ에 곱합니다. 7                 1                —– ⓔ [ⓑ 값] 5                 35               —– ⓕ [ⓓ 값] 7/5= 1 1*5= 5            1*35= 35        —— ⓖ   ④ ⓔ에서 ⓖ의 값을 빼줍니다. 1-35= -34 7-5= 2           -34 mod 40= 6 mod 40= 6     —— ⓗ ※ R열의 값이 음수가 나오면 mod φ(n) 연산을 하는데 양수를 만들기 위해 피제수에 φ(n)값을 더해 줍니다. -34 mod 40= 6 mod 40   ⑤ L열의 값이 1이 될 때까지 ③~④ 과정을 반복합니다. 그럼 계속해서 d값을 찾아보도록 하겠습니다. ⑥ ⓕ의 L열의 값을 ⓗ의 L열의 값으로 나누고 몫을 ⓙ에 곱합니다. 5                 35                —– ⓘ[ⓕ 값] 2                  6                —– ⓙ[ⓗ 값] 5/2= 2 2*2= 4           2*6= 12           —– ⓚ   ⑦ ⓘ에서 ⓚ의 값을 빼줍니다 5-4= 1            35-12= 23        —– ⓛ   ⓛ에서 L열의 값이 1이 나왔으므로 d의 값은 23입니다. d= 23   d값 확인: 7*23 mod 40 = 161 mod 40= 1
키 생성 알고리즘을 이용하여 KU= {7, 55}, KR= {23, 55}의 키 쌍을 생성한 후 p와 q는 삭제합니다. (p, q를 알면 d를 알 수 있으므로) 공개키인 KU는 공개하고 개인키인 KR은 공개하지 않습니다. 그럼 생성된 키를 이용하여 암/복호화를 해보겠습니다. 여기서 M= 13으로 하겠습니다.  
  • 암호화
    • 암호화는 C≡ Me mod n 이므로 C≡ 137 mod 55 입니다. 모듈러 연산규칙을 이용하여 아래와 같이 계산할 수 있습니다.
    • 131 mod 55= 13
    • 132 mod 55= 169 mod 55= 4
    • 134 mod 55= 28561 mod 55= 16
    • 137 mod 55= (13*4*16) mod 55= 832 mod 55= 7
    • C= 7로 암호화가 되었습니다.
  • 복호화
    • 복호화는 M≡ Cd mod n이므로 M≡ 723 mod 55 입니다.
    • 71 mod 55= 7
    • 72 mod 55= 49
    • 74 mod 55= 2401 mod 55= 36
    • 78 mod 55= 5764801 mod 55= 31
    • 78 mod 55= 5764801 mod 55= 31
    • 723 mod 55= (7*49*36*31*31) mod 55= 11866428 mod 55= 13
    • M= 13으로 복호화가 되었습니다.
    RSA로 할 수 있는 것 암호/복호: 송신자는 수신자의 공개키로 메시지를 암호화하고 수신자는 수신자의 개인키로 복호화 한다. 디지털 서명: 송신자는 송신자의 개인키로 메시지에 “서명”하고 수신자는 송신자의 공개키로 “검증” 한다. 키 교환: 송신자의 수신자의 공개키로 세션키를 암호화하여 전달하고 수신자는 수신자의 개인키로 복호화하여 세션키를 서로 공유한다.   문제 p=7, q=11, e=11, C=57일 때 d와 M은 무엇일까요?   참고문헌 William Stallings, 『컴퓨터 통신보안 3rd』, 최용락 외 3인 공역, 도서출판 그린, 2006 Mark Stamp, 『정보보안 이론과 실제』, 안태남, 손용락, 이광석 공역, 한빛미디어, 2008 위키백과, “RSA 암호”, https://ko.wikipedia.org/wiki/RSA_%EC%95%94%ED%98%B8, 2016.10.8