Cryptosystem

RSA 암호시스템에서 각 개인은 공개 키와 개인 키를 갖는다.

  • 공개 키:
  • 개인 키:

키를 얻는 방법은 다음과 같다.

  • 200자리 이상의 큰 소수 둘을 찾아 선택하고 라 한다.
    • 단, .
  • 라 한다.
    • 은 암/복호화할 때 modulus로 쓸 것이다.
  • 을 계산해서, 이것을 이라 한다.
  • 과 서로소인 정수 를 찾아 선택한다.
    • 단, .
  • 이 성립하는 를 구한다.
    • 모듈로 의 역을 구하고, 그것을 라고 한다.

이 때 공개키는 이고, 개인 키는 가 된다.

Encryption

평문 을 암호화한다고 하자.

  1. 평문 의 각 알파벳을 두 자리 숫자로 변환한다.
    • A는 00, B는 01, C는 02, …
  2. 이 숫자들을 붙여 커다란 하나의 숫자열로 만든다.
  3. 숫자열을 같은 크기의 블록들로 나눈다.
    • 단, 각 블록의 길이는 n을 초과하지 않는 짝수여야 한다.
    • 마지막 블록의 길이가 다른 블록보다 짧다면 평문에 더미 문자열을 덧붙여서 길이를 맞춘다.
  4. 이제 숫자로 바뀐 평문들의 블록을 를 얻었다.
  5. 을 사용하여 각 블록 를 암호화된 블록 로 변환한다.
  6. 암호화된 를 암호문의 수신자에게 보낸다.

암호화 예제

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일