코드일기장

현대암호 RSA암호에 대해(2) 본문

이산수학과 암호론

현대암호 RSA암호에 대해(2)

won_hyeok2 2021. 12. 26. 16:03

현대 암호 RSA암호에 대해(1)에서는 백그라운드 지식을 넓혔다. 이번에는 RSA알고리즘으로 암호화를 하는 방법을 알려주겠다. 암호화를 하는 방법을 배우기 전 알아야 할 수학적 지식이 3가지가 있다.

1. 유클리드 호제법

최대공약수를 구하는 공식이다. 5와 10의 최대 공약수를 구해보아라. 독자들은 쉽게 2라는 것을 알 수 있다. 

다시 문제를 내보겠다. 만약 62와 510의 최대 공약수를 구해본다고 생각해 보자. 빠른 시간에 답을 알기에는  힘들 것이다. 이런 큰 두 정수의 최소 공약수를 빠르고 쉽게 구하는 공식이 유클리드 호제법이다. 

 

 

위와 같이 유클리드 호제법을 사용하면 큰 정수 a,b가 있어도 쉽게 최대공약수를 구할 수 있다.

 

💎 유클리드 호제법 참고 사이트

 

2.  오일러 피 함수

1부터 n까지 n과 서로소인 것의 개수 

(서로소란, 공약수 1뿐)

 

오일러 피 함수 기호는 Ø(파이)

 

ex) Φ(6)= 1~6까지  서로소는 1,5 따라서 Φ(6)=2

     Φ(11)=1~11  서로소 1,2,3,4,5,6,7,8,9,10 따라서 Φ(11)=10

 

 

💎 오일러 피 함수 참고 사이트

3. 페르마 소정리

p가 소수이고 a와 p가 서로소이면 ap-1≡1(mod p)이다.
즉, ap-1을 p로 나누면 나머지가 1이다.

 

 

💎 페르마의 소정리 참고 사이트

4. RSA알고리즘 

국제 표준화 기구에서 정한 암호의 표준

140자리 이상의 큰 두 개의 소수를 선택한 수 곱하고 추가 연산 통해 공개키와 개인키로 구성 (합성수의 소인수분해의 어려움을 이용함.)

 

 

과정

  1.   n=p*q (p와 q는 무조건 소수이어야 한다.)  원래 이 알고리즘은 140자리 이상 소수 두 개를 사용하지만 우리는 알고리즘 이해를 위해 낮은 수를 사용하겠다.
  2.   오일러 Φ(파이) 피 함수로 Φ(n)=(p-1)(q-1) 값과 서로소인 자연수 e를 정한다. (1은 제외) 여기서 자연수 e= 공개키로 이용한다.
  3.   e*d=1 (mod (p-1)(q-1))인 자연수 d 정하기 자연수 d=개인키로 이용한다.

 

암호화:  이때 임의 자연수 m에 대하여 m^e≡C (mod n)이 된다. C의 값은 암호문이다.

복호화:  C^d≡M(mod n)을 만족하면 M 평서문

 

 

예제를 통해 RSA알고리즘에 대해 더 자세히 이해해보자.

 

 

  • 소수 p=3, q=11 RSA암호 공개키 구성

1.  n=3*11, Φ(33)=(3-1)(11-1)=20

2. (e,20)=1인 e=3     (공개키 e=3)   

3. 3*d=1 (Mod 20)  d=7    (개인키 d=7)

 

공개키 (3,33) 개인키(7,33)

 

  • 평문 M=5를 암호화하라 

C=5^3(Mod 33)=26  C=26 (암호문)

 

5의 3승은 3은 공개키 e

 

  • 반대로 C=26 복호화

M=26^7 (Mod 33)=5  페르마의 소정리 사용

 

26의 7승은 7은 개인키 d

 

 

우리는 쉽게 배우기 위해 한자리 수 혹은 두 자릿수 소수를 사용했지만 RSA암호의 실사용에서는 140자리 수의 소수 두 개를 사용한다는 것을 잊지 말자.

 

 

 

https://www.flaticon.com/kr/free-icon/password_1902798

'이산수학과 암호론' 카테고리의 다른 글

현대암호 RSA암호에 대해(1)  (0) 2021.10.30
'이산수학과 암호론' Related Articles more
Comments