RSA암호 원리

■ RSA암호 원리

 

금융, 개인정보, 카드등의 인터넷 상의 안전성을 유지하기 위하여 사용되는 RSA암호의 원리를 알아보자

 

1. 공개 열쇠와 비밀 열쇠 만들기

 

n, e를 공개 열쇠, p, q, d를 비밀 열쇠라고 하자.

p, q를 소수로 하고, n=pq로 나타낸다.

어떤 수 e, d를

ed mod LCM(p-1,q-1) =1이 되도록 고른다.

e는 최소공배수와 서로소이다.

 

LCM(p-1, q-1) : p-1, q-1의 최소 공배수 (예 LCM(2,5)=10 )

mod : 나눗셈의 나머지를 구한다.(예 5 mod 2 = 1 )

 

2. 먼저 비밀 열쇠가 되는 두 소수 p, q를 정한다.

예) 두 소수 p=3, q=7로 하자. n=3×7=21

 

3. 다음에 또 하나의 공개 열쇠 e를 구한다.

e는 최소공배수와 서로소인 수로 정한다.

예) e=5

 

4. 또 하나의 비밀 열쇠 d를 구한다.

d는 e를 곱해서 p-1과 q-1의 최소공배수로 나누면 나머지가 1이 되는 수로 한다.

예) LCM(3-1, 7-1)=LCM(2,6)=6

ed ÷ 6에서 나머지가 1이 되는 d값을 구한다.

즉 5×d ÷ 6에서 나머지가 1이 되는 d값

1부터 차례로 대입해서 생각해 나가면

d=5

 

5. 암호화(앞에서 만든 공개 열쇠를 써서 평문을 암호화)

평문을 M, 암호문을 C로 했을 때,

암호화 ( M → C)의 식으로 나타낼 때, C=M^e mod n

예) M=12라면

암호문(C)은 M을 e제곱하고 n으로 나눈 나머지로 구해진다.

암호화는 공개 열쇠(n과 e)만으로 할 수 있다.

암호문은 12의 5제곱을 21로 나눈 나머지가 되며, 12^5 = 248832를 21로 나누면 나머지는 3, 암호문 C=3이 된다.

 

6. 복호(비밀 열쇠를 써서 암호문이 평문으로 되돌아 오는가를 확인)

복호 ( C → M)의 식으로 나타낼 때, M=C^d mod n

복호는 암호화(평문 M을 e제곱하고 n으로 나눈 나머지)와 역방향(대칭적)의 계산을 의미한다.

평문(M)은 암호문 C를 d제곱하고 n으로 나눈 나머지로 구해진다.

복호에는 비밀 열쇠(d)의 정보가 필요해진다.

비밀 열쇠(d)의 값을 공개 열쇠(n)로부터 구할 수는 없다.

(단 n이 p와 q의 소인수 분해가 된 경우를 제외)

평문(M)은 3을 5제곱하고 21로 나눈 나머지가 된다.

3^5=243이므로 221로 나누면 나머지는 12

암호화하기 전의 평문 M=12로 알수 있다.

 

12는 특별한 의미가 없는 숫자이다. 그러나 문자에 숫자를 할당하는 등, 문자열을 수열로 변환하면 문장도 암호화 할 수 있다. 공개 열쇠(n)의 자릿수가 곧 구해진다. 시험적으로 공개 열쇠의 자릿수를 올려 보면 계산량이 급격히 늘어난다. 공개 열쇠의 자릿수를 더 높이면 암호의 안전성이 높아진다는 것을 알 수 있습니다.

 

예제)

RSA 암호문 C=141를 평문으로 바꿔라.

<힌트> 공개열쇠 n=437, e=119

 

풀이)

n=437를 소인수 분해해야 한다.

n=437=19×23

비밀 열쇠 p와 q는 p=19, q=23

비밀 열쇠 d는

119×d mod LCM(18,22)=1

LCM(18,22)=198

e	d	ed	LCM	나머지	비고
119	1	119	198	119
119	2	238	198	40
119	3	357	198	159
119	4	476	198	80
119	5	595	198	1

엑셀을 이용하여

119를 곱한 다음에 198로 나누면 나머지가 1이 되는 수 d=5

 

평문(M)은 암호문 C를 d제곱하고 n으로 나눈 나머지로 구해지므로

M= 141^5 ÷ 437인 나머지

141^5 = 55730836701 이므로

437로 나눈 나머지는 335

따라서 평문(M)=335