RSA 암호(RSA Encryption)
상위 문서: {{ item.title }} -
Cryptosystem
RSA 암호시스템에서 각 개인은 공개 키와 개인 키를 갖는다.
- 공개 키:
- 개인 키:
키를 얻는 방법은 다음과 같다.
- 200자리 이상의 큰 소수 둘을 찾아 선택하고 라 한다.
- 단, .
- 라 한다.
- 이 은 암/복호화할 때 modulus로 쓸 것이다.
- 을 계산해서, 이것을 이라 한다.
- 과 서로소인 정수 를 찾아 선택한다.
- 단, .
- 이 성립하는 를 구한다.
- 즉 모듈로 의 역을 구하고, 그것을 라고 한다.
이 때 공개키는 이고, 개인 키는 가 된다.
Encryption
평문 을 암호화한다고 하자.
- 평문 의 각 알파벳을 두 자리 숫자로 변환한다.
- A는 00, B는 01, C는 02, …
- 이 숫자들을 붙여 커다란 하나의 숫자열로 만든다.
- 숫자열을 같은 크기의 블록들로 나눈다.
- 단, 각 블록의 길이는 n을 초과하지 않는 짝수여야 한다.
- 마지막 블록의 길이가 다른 블록보다 짧다면 평문에 더미 문자열을 덧붙여서 길이를 맞춘다.
- 이제 숫자로 바뀐 평문들의 블록을 를 얻었다.
- 을 사용하여 각 블록 를 암호화된 블록 로 변환한다.
- 암호화된 를 암호문의 수신자에게 보낸다.
암호화 예제
Encrypt the message STOP using the RSA cryptosystem with key . Note that , and are primes, and .
다음 조건들을 사용해 공개 키 으로 평문 “STOP“을 암호화하시오.
일단 STOP 을 숫자로 변환하자. A 를 00, B를 01 이라 하면…
S | T | O | P |
18 | 19 | 14 | 15 |
블록의 길이를 4로 정했다고 하자. 그러면 이 숫자는 두 개의 블록으로 쪼개지게 된다.
이제 각 블록을 에 넣으면 된다!
공개 키가 이므로, 이고 이다.
직접 계산한다면 숫자가 꽤 크므로 나머지를 구하는 연산은 이진법을 사용해 거듭제곱 수의 나머지를 구하는 알고리즘을 사용하자.
암호화된 메시지는 다음과 같다.
Decryption
해독키 는 모듈로 의 역이므로, 이다.
(와 이 서로소이기 때문에 역 는 반드시 존재한다.)
따라서 인 정수 k 가 반드시 존재한다.
이므로, 원문 을 얻어내기 위해 다음과 같이 생각할 수 있다.
한편 가 소수이므로 다음과 같이 [[Fermat-s-little-theorem]]{페르마의 소정리}를 사용할 수 있다.
그러므로 은 에서 합동이다.
같은 방법으로, 은 에서도 합동이다.
따라서 다음과 같이 정리할 수 있다.
복호화 예제
We receive the encrypted message 0981 0461. What is the decrypted message if it was encrypted using the RSA cipher from Example 8?
- 암호화된 메시지 가 위의 암호화 예제와 같은 조건으로 암호화되었다고 하자.
- 원문은 무엇인가?
위의 예제에서는 공개 키 을 제공했다. 그러나 개인 키 는 제공하지 않아서 가 무엇인지 모른다.
부터 구하자.
는 13 모듈로 2436 의 역이다.
역을 구하는 방법을 사용해서 역을 구해보자.
먼저 유클리드 호제법을 사용해 을 찾도록 하자.
이다.
베주의 항등식을 만들면 사칙연산만으로 쉽게 역을 구할 수 있다.
따라서 를 으로 나누었을 때 나머지 1 이 나오게 하는 수 는 이다.
이제 블록 를 해독하기 위해 다음 식에 입력만 하면 된다.
을 넣어보자.
가 나왔다.
A 가 00 이고, B 가 01 이었으므로, 다음과 같이 원문을 알아낼 수 있다.
07 | 04 | 11 | 15 |
H | E | L | P |
참고문헌
- Rosen의 이산수학 / Kenneth H. Rosen 저 / 공은배 등저 / 한국맥그로힐(McGraw-Hill KOREA) / 2017년 01월 06일