콘텐츠로 이동

RSA

Prerequisites

Basic concepts of Number theory

GCD(greatest common divisor)

GCD

\[ \begin{matrix} \text{Let} \ d \ \text{be} \gcd(a, b). \\ d = \min\{ax + by : x,y \in \mathbb{Z}\} \end{matrix} \]

가장 유명한 성질 중 하나인데, GCD는 \(ax + by\) 로 만들 수 있는 가장 작은 수이다

Mathematical Induction으로 증명할 수 있음

Linear Congruence

Linear Congruence

\[ \begin{matrix} ax \equiv b \pmod{n} \ \text{has a solution} \Leftrightarrow d \mid b \ (\text{where} \ d = \gcd(a, n)) \\ \text{If then, it has} \ d \ \text{incongruent solutions.} \end{matrix} \]

사실은 위의 GCD 성질에서부터 바로 유도된다

\(ax \equiv b \pmod{n}\) 의 해가 존재한다는 것은, \(ax + ny = b\) 인 \(y\) 가 존재한다는 뜻이고, 어떤 \(t\) 에 대해서 \(ax + ny = dt = b\) 이다.

이후는 설명할 필요도 없다. 반대도 비슷하다.

(실제 해를 구하는 방법도 간단하니 궁금하면 찾아보세요)

Fermat's little Theorem

Fermat's little Theorem

\[ \begin{matrix} \text{Let} \ p \ \text{be a prime and} \ p \nmid a. \\ a^{p-1} \equiv 1 \pmod{p}. \end{matrix} \]

이건 설명하기에는 너무 유명하다

여담이지만 little만 소문자로 쓰는 이유는 FLT(Fermat's Last Theorem)가 있기 때문임..

Preliminaries

Euler's phi function

Euler's phi(\(\phi\)) function

\[\phi(n) = \# \ \text{of} \ k < n \ s.t. \ \gcd(k, n) = 1\]

정수론에서 매우 중요한 역할을 하는 \(\phi\) 함수이다.

\(n\) 보다 작은 서로소의 개수를 나타낸다.

Properties

Properties

\[ \begin{aligned} \textbf{(a)} \ &\text{If} \ p \ \text{is a prime, then} \ \phi(p) = p-1 \\ \textbf{(b)} \ &\phi \ \text{is multiplicative.} \\ &\text{i.e.} \ \text{if} \ \gcd(m, n) = 1, \ \text{then} \ \phi(mn) = \phi(m)\phi(n) \end{aligned} \]

multiplicative 개념은 정수론 전반에 등장하므로, 알아두면 좋다.

Euler's Theorem

Euler's Theorem

\[ \begin{matrix} \text{If} \ \gcd(a, n) = 1, \ \text{then} \ a^{\phi(n)} \equiv 1 \pmod{n} \end{matrix} \]

위에서 서술한 페르마 소정리의 일반화 버전이다.

\(n\) 이 소수라면 \(a^{\phi(n)} \equiv a^{n-1} \equiv 1 \pmod{n}\) 이 된다.

RSA

How does it work?

RSA Algorithm

  1. 두 소수(일반적으로 아주 큰) \(p, q\) 를 선택한다.
  2. 두 소수의 곱 \(n = pq\) 을 계산한다.

  3. \(\phi(n)\) 을 아주 쉽게 계산한다.

    • (위에서 언급한 성질을 이용하여 \(\phi(n) = \phi(pq) = \phi(p)\phi(q) = (p-1)(q-1)\) 임을 알 수 있다.)

  4. \(1 < k < \phi(n)\), \(\gcd(k, \phi(n)) = 1\) 인 \(k\) 를 아무거나 선택한다.

    • 이러한 \(k\) 는 자명히 존재한다.
    • 이 \((n, k)\) 쌍은 public key가 된다(!!)

  5. 이제 암호화 하고자 하는 문장(수로 표현된)을 \(M\)이라 하자.

    • 중요한 점은, 우리는 \(\pmod{n}\) 상에서 사용할 것이기 때문에 \(M\) 은 \(n\) 보다 작아야 한다는 것이다. \(M\) 을 \(n\) 보다 작아질때까지 자르는 방식 등을 사용할 수 있다. (ex. 123456789 -> 123/456/ 789)

  6. \(M^k \equiv r \pmod{n}\) 이라 할때, 암호화된 문장은 \(r\) 이 된다.

  7. \(1 < j < \phi(n)\) 인 \(j\) 중에서, \(kj \equiv 1 \pmod{\phi(n)}\) 인 \(j\) 를 고른다.

    • 여기에서 서술했듯이, 이러한 \(j\) 는 딱 하나, 반드시 존재한다.
    • (애초에 \(\gcd(k, \phi(n)) = 1\) 인 \(k\) 를 골랐기 때문)

  8. \(r^j \equiv (M^k)^j \equiv M^{kj} \pmod{n}\) 이다. 이렇게 되면 어떤 \(t\) 에 대해 \(M^{kj} \equiv M^{1 + t\phi(n)} \equiv M \cdot M^{\phi(n)} \pmod{n}\) 이다. 오일러 정리에 의해서 \(M \cdot M^{\phi(n)} \equiv M \cdot 1 \equiv M \pmod{n}\) 이다. 즉, 암호화한 문장을 알아냈다.

    • \(\gcd(M, n) \neq 1\) 이라면? 이라는 아주 날카로운 질문을 할 수도 있다. 결론은 상관없이 제대로 작동한다지만, 궁금하면 아래를 참고
CRT (Chinese Remainder Theorem)

나중에써야지

이 알고리즘만 봐서는 이 방식이 어떤식으로 작동하는지 이해가 어려울 수 있다.

왜냐하면 이 암호화는 old-fashioned 암호화와 아주 큰 차이점 하나가 있기 때문인데, 그건 바로 이 암호화는 공개키 암호방식(Public-key cryptography)이라는 것이다.

그래서 암호화(encoding)하는 사람과 복호화(decoding)하는 사람이 알고있는 정보가 다르고, 이 정보들을 계산하는 과정이 번갈아 가며 나오기 때문이다.

RSA의 동작방식을 잠시 제쳐두고 공개키 암호화에 대해서 잠깐 알아보자

Public-key cryptography

Symmetric-key cryptography

우선 아주 이전부터 사용하던 직관적인 암호화인 대칭키 암호화 (Symmetric-key cryptography)에 대해서 알아보자.

sequenceDiagram
    participant A as 수신자 (A)
    participant B as 송신자 (B)

    Note over A, B: 0. 키 공유

    Note over B: 1. 메시지를 키를 이용해 암호화

    B->>A: 2. 암호문 전송

    Note over A: 3. 암호문을 키를 이용해 복호화

그림만 보고도 알 수 있을 정도로 직관적이고 간단하다.

대표적인 예시로 카이사르 암호화 등이 있다.

다만 이 방식에는 큰 허점이 있는데, 두 사람이 키를 공유하는 과정이 필수적이라는 것이다.

이는 온라인 상황등에서는 아주 치명적이다.

키를 공유하는 과정이 공개적으로 이루어지기 때문에 탈취가 매우 쉽기 때문이다.

Public-key cryptography

그렇다면 공개키 암호화는 어떨까? 어떻게 이 문제를 해결할까?

공캐기 암호화는 비대칭키 암호화라는 방식으로 이 문제를 해결한다.

이 방식에서는 암호화에 사용되는 키와 복호화에 사용되는 키가 다르다.

따라서 암호화에 사용되는 키만 알고 있다면 암호화된 문장을 복호화 할 수가 없다.

즉, 복호화 키는 나 혼자만 가지고 있는 상태로 암호화 키를 모두에게 공개하고, 송신자는 이 암호화 키를 이용해 메시지를 암호화 한 다음 이 암호문 또한 모두에게 공개한다. 그럼 수신자는 이 암호문을 받아, 나만 가지고 있는 복호화 키로 암호문을 해독한다.

이렇게 키를 탈취(?)당할 걱정 없이 메시지를 몰래 주고받을 수 있다.

그럼 이제 다시한번 이거를 이해해보자.

sequenceDiagram
    participant A as 수신자 (A)
    participant B as 송신자 (B)

    Note over A: 1,2,3,4. (n, phi(n), k) 를 계산한다.
    A ->> B: (n, k) 를 전달한다.<br>(탈취되어도 상관없음!)

    Note over B: 5,6. 암호문 r을 얻는다.

    B ->> A: 암호문 r을 전달한다.

    Note over A: 7. j를 계산한다.

    Note over A: 8. 복호화로 원래 문장을 얻는다.

Is it safe?

이 방식이 과연 안전할까?

암호화 키 만으로 복호화를 할 수는 없을까?

물론 가능하다.

모든 공개키 암호화는 이론적으로, 그리고 직관적으로 당연하게도 풀 수 있다.

RSA를 암호화키만으로 푸는 방법은 간단하다.

\((n, k)\) 가 주어졌을 때, \(\phi(n)\) 을 구하기만 하면 된다. 그리고 이는 간단히 구할 수 있다. \(n\) 보다 작은 수들을 하나씩 서로소인지 판단해 보면 된다.

눈치챘겠지만, 그래서 우리는 1번 과정에서 아주 큰 두 소수를 구할 필요가 있었다. 수신자는 \(\phi\) 의 성질을 이용해 아주 쉽게 \(\phi(n)\) 을 계산할 수 있었지만, 어떤 두 소수가 곱해졌는지 모르는 송신자에게는 불가능하다.

즉, 이 방식의 안전성은 소인수분해의 어려움(Time Complexity가 큼, 정확히는 그러할 것으로 추정)에 기대고 있다.

다만 이 문제가 현재 P-문제에 속하지 않을 것으로 강하게 추측되고 있고, 실용적인 레벨에서 현재 \(\phi(n)\) 을 직접 계산하는데에는 우주의 나이보다도 긴 시간이 필요하다고 알려져 있으므로 걱정할 필요는 없을 것이다.

댓글