RSA, 제대로 이해하기 (1)

안녕하세요. 오늘은 요즘에 딥하게 빠져버린 암호학 중 필수 개념인 RSA (textbook-RSA)에 대해 알아보고자 합니다.

 

****************  INDEX  *****************

RSA?

✔️ Key Generation

✔️ Key Distribution

✔️ Encryption

✔️ Decryption

< 2부 >

Effective En/Decryption

- square-and-multiply

- CRT

Attack

- CCA

- Broadcast attack

******************************************** 

 

📚 RSA? 

RSA는 전 세계에서 가장 많이 사용되는 공개키 암호 알고리즘입니다.

오랜시간 지속해서 사용하고 있는 아주 중요한 알고리즘이라 꼭 포스팅해서 기록하고 싶어지더라구요~.~

TMI ) RSA라는 이름은  Ron Rivest, Adi Shamir and Leonard Adleman의 이름을 앞 글자를 따서 지었다고 합니다.

 

RSA 알고리즘은 소인수분해 문제가 어렵다는 사실에 기반한 알고리즘인데요.

이 부분은 알고리즘 과정 중 키 생성 알고리즘(Key Generation)을 알아볼 때 한 번 더 언급하겠습니다.

 

참고로, 이 포스팅에서 다루는 RSA는 Textbook-RSA입니다.

 

 

Alice send information to Bob using RSA

 

 

오랜만에 일러를 켰습니다,,,, 또 오랜 시간이 드는 포스팅이 되겠군요 🤣

RSA 알고리즘은 Key Generation, Key Distribution, Encryption, Decryption 4개의 단계를 가집니다.

 

공개키 암호화의 특징을 다시 한 번 정리해볼까요?

암호화된 메세지를 보내려면 수신자의 public key를 가지고 있어야하고,

암호화된 메세지는 반드시 같이 생성된 private key로만 복호화할 수 있습니다.

 

이제 RSA를 한 단계씩 알아보도록 할텐데요. 자주 나올 문자에 대해 정의하고 가겠습니다.

 

- $M$ : 평문, 보내고자하는 메세지를 의미합니다. (Message)

- $C$ : 암호문, 평문을 암호화한 결과 암호문을 의미합니다. (Ciphertext)

- $lcm(a, b)$ : $a$와 $b$에 대한 최소공배수를 의미합니다. (Least Common Multiple)

- $gcd(a, b)$ : $a$와 $b$에 대한 최대공약수를 의미합니다. (Greatest Common Divisor)

 

 

✔️ Key Generation

 

가장 먼저 공개키 public key와 개인키 private key를 생성합니다. 

이 부분은 공개키 암호화의 구조를 알고있어야 이해할 수 있습니다.

Generate Bob's Private Key & Public Key

 

키 생성 알고리즘은 5단계를 거친 후, 공개키인 public key와 개인키인 private key를 생성합니다.

다양한 기호가 등장하기 때문에 여러번 반복해서 봐야겠더라구요.

 

그리고 과정을 보기 전에 public key는 (e, N)로 구성되어 있고,

private key는 (d, N)으로 구성되어 있다는 점을 기억해주세요!

각 e, d, N 값은 아래 과정에서 생성되는 수입니다.

 

 

 

1. Choose $p$ and $q$.

 

먼저, 최소한 1024 bits 이상의 서로 다른 Prime number p, q를 선택합니다.

그 이유는 보안상 현재 컴퓨팅파워로 풀 수 있는 소인수 분해 문제에 대한 제한 때문입니다.

1024 bits이하인 소수를 사용하면 해커들이 시간 내에 두 소수를 예측해낼 수 있기 때문이죠.

 

고른 p와 q는 절대 공개되어서는 안됩니다.

 

 

2. Compute $\small N = p \times q$.

고른 p와 q를 이용해서 $N$을 구합니다.

$N$은 공개키와 개인키의 일부로, modulo연산의 제수(divisor)로 사용됩니다. 

 

공개키의 일부이기 때문에 $N$값은 공개된 값이 되는데,

여기서 짚고 넘어가야할 점이 $N$ 값을 소인수분해하게 되면 두 비밀값 p와 q을 얻을 수 있다는 점입니다.

그래서 1024bit 이상의 소수라는 기준처럼 p와 q를 충분히 크게 해야되고,

위에서 언급했던 소인수분해 문제가 어렵다는 사실에 기반한다는 것도 바로 이 부분에 해당하는 말입니다.

 

참고로 RSA의 키 사이즈를 말할 때 주로 N의 사이즈를 의미합니다.

 

 

3. Compute $l $.

$l = lcm({\small p-1, q-1})$

 

$p-1$와 $q-1$값의 최소공배수 $l$를 구합니다.

$l$ 값은 비밀 값으로, 공개되어서는 안됩니다.

 

 

 

 

4. Choose an integer $e$.

$gcd(e, l) = 1$ ($1 < e < l$)

 

$l$보다 작으면서 $l$과 서로소인 값인$e$을 고릅니다.이 때 고른 값은 공개키의 일부로 사용됩니다.

e는 보통 3, 17, 65537 값 중 하나를 사용하는데요.그 이유는 암/복호화를 더욱 효과적으로 하는 방법에서 자세한 이유를 적겠습니다.

 

 

 

5. Determine $d$.

$e \times d\,\bmod\,l =1$ ($1 < d < l$)

 

$l$보다 작으면서 $\bmod l$ 상에서 $e$의 곱셈의 역원인 $d$를 고릅니다.이 때 고른 값은 개인키의 일부로 사용됩니다.

$d$는 비밀키이며, 외부로 알려져서는 안됩니다.

 

 

 

여기까지 키 생성 알고리즘이었습니다.

많이 헷갈려도 다음 과정들은 생각보다 아주아주 간단합니다.

 

 

 

✔️ Key Distribution

Bob transmits his Public Key to Alice

생성된 키를 분배합니다.

만약 A가 B에게 어떤 정보 M을 보내고 싶다면, A는 M을 B의 공개키로 암호화해서 A에게 전달해야합니다.

위 목표를 달성하기 위해서는 사전에 B의 공개키와 개인키가 생성되어야 하고,

A가 B의 공개키를 갖고 있어야 전달받은 암호화된 메세지를 복호화할 수 있겠죠?

 

메세지의 암호화를 위해 public key 를 reliable한 채널을 통해 전달합니다.

참고할 사항은 A에게 공개키를 전달할 때는 반드시 Secure한 채널을 통하지 않아도 됩니다.

신뢰하지 않은? 안전하지 않은..? 경로로 전달해도 된다는 의미입니다.

해커가 공개키를 얻어도 메세지를 복호화할 수 있는 건 A의 private key 뿐이기 때문입니다.

 

 

 

✔️ Encryption

 

private key를 얻었다면 이제 암호화를 통해 메세지를 전달할 수 있습니다.

암호화는 굉장히 간단해요.

 

$C = M^e \bmod\,N$

 

먼저, 메세지 M을 N보다 작은 정수 m으로 변환(padding scheme 변환법)합니다. 

이 변환방식은 전달받은 사람과 공유되어야 합니다. (복호화 이후 복구해야하기 때문)

그리고 $m$의 $e$승한 값에 $N$값으로 모듈러 연산을 취한 값으로 암호문 $C$를 얻습니다. 

 

암호문을 생성했으면, 생성한 암호문을 수신자(공개키의 주인)에게 전달합니다.

 

 

 

✔️ Decryption

암호문 $C$가 수신자에게 전달되고, 복호화를 통해 평문으로 변환하면 안전하게 평문을 전달하는 것이 마무리 됩니다.

 

수신자가 암호화된 $C$를 받으면 복호화를 통해 $m$을 얻을 수 있습니다.

복호화도 암호화만큼이나 간단해요.

 

$M = C^d \bmod\,N$

 

$C$를 private key의 일부인 d의 값으로 제곱해서 $N$의 값으로 모드를 취해주면 됩니다.

신기하죠. M이 된다는 걸 증명해보면 더 재밌습니다.

 

복호화가 되는 과정을 증명하기 위해서는 오일러의 정리를 알아야합니다.

오일러의 정의는 아래와 같습니다.

 

$a^{\varphi(n)} \equiv 1 \bmod\,n \quad {\scriptsize (a, n은 서로소) \cdot \cdot \cdot (1)}$

 

이 때,  $\varphi(n)$는 오일러 파이 함수로, 1부터 n까지 n과 서로소인 집합의 크기를 뜻합니다.

예를 들면 n이 6일때, 1부터 6까지 6과 서로소인 수는 1, 5의 두 개 뿐이므로 $\varphi(6)=2$가 되죠.

 

자세히는 알아보지 않고, 복호화 설명에 집중하겠습니다.

 

$M = C^d \bmod\, = (M^e)^d \bmod\,N$.

 

여기서 $e \times d = k \cdot l +1$으로 표현할 수 있습니다. 

 

키 생성 마지막 단계에서 $e \times d\,\bmod\,l \equiv 1$의 조건으로 $d$를 생성했습니다.

$e \times d$가 $l$로 모듈러 연산을 취한 값이 1이라는 것은,

$e \times d$를 $l$로 나누었을 때 그 나머지가 1이라는 의미입니다.

몫을 임의의 상수 값 $k$라고 두고 $k \cdot l +1$로 표현할 수 있겠죠.

 

$(M^e)^d \bmod\,N = M^{l \cdot k + 1} \bmod\,N$

 

이 때, 오일러 정리(1)를 이용하면

 

$(M^l)^k \cdot M^1 \bmod\,N = M^1 \bmod\,N$

$\therefore M \bmod\, N$

 

 

여기서 중요한 조건이 하나 있었는데요.

오일러 정리를 적용하려면 위의 식 중 $M$과 $N$이 서로소이어야 한다는 점이죠.

$M$이 p와 q만 아니라면 $N$과 서로소일 수 밖에 없습니다.

$N$은 두 소수 p x q 값이니까요.

 

 

이렇게 복호화 과정을 증명할 수 있습니다.

 

그럼 마지막으로, 실제 값을 대입해서 확실하게 이해해볼게요.

 

 

 

👾 Example

Key Generation

 

1. Choose two distinct prime numbers p and q.

👉🏻 $p = 11, q=3 $

예시이기 때문에 간편하게 작은 값을 취하겠습니다.

 

2. Compute $N = p \times q$.

👉🏻 $N = p \times q = 33$

 

3. Compute the $l = lcm(p-1, q-1)$.

👉🏻 $l = lcm(10, 2) = 10$

 

4. Choose an integer $e$ : $gcd(e, l) = 1$ ($1 < e < l$).

👉🏻 $e = 3$

 

5. Determine $d$ : $e \times d\,\bmod\,l \equiv 1$ ($1 < d < l$).

$e \times d \bmod\, l = 3 \times d \bmod\, 10 = 1$

👉🏻 $d = 7$

 

 

실제 데이터를 가지고 계산하니까 훨씬 이해하기 쉽죠?

위의 예시를 통해 🔑public key <e, N>과 🔑private key <d, N>을 얻었습니다.

 

Key Distribution 과정을 거치고 난 후로, 암호화를 계속해서 해볼게요.

 

 

Encryption

전달하고자 하는 메세지 M을 8($< N$)이라고 가정합니다.

$C = M^e \bmod\,N$

$8^3 \bmod\,33 = 512 \bmod\,33 = 17$

 

암호화한 암호문 $C=17$를 수신자에게 전달합니다.

 

 

Decryption

받은 C의 값을 본인의 private key로 복호화합니다.

$M = C^d \bmod\,N = 17^7 \bmod 33 = 410,338,673 \bmod 33 = 8$

 

 

 

지금까지 RSA 알고리즘을 자세히 확인해보았습니다. 

암호화 알고리즘이 재밋지 않나요 ㅎㅎㅋㅎㅋㅎㅋ(재미강요 😉)

틈틈히 더 알아볼 예정이라 꾸준히 업데이트 하겠습니다,,

피드백은 언제나 환영입니다!! 잘못된 부분이나 오타, 첨언 내용이 있다면 댓글에 남겨주세요 🙌🏻