기초 암호 정리

jaewon·2024년 11월 5일

공개키 프로토콜은 어려운 수학 문제에 기반한다

Note
어려운 문제란 ? : 알려진 계산 방법들의 계산량 함수의 하한이 준지수 함수 또는 지수함수 밖에 없는 경우 -> 즉 때려 맞추면 준지수 혹은 지수가 된다

소인수 분해 기반

소인수 분해란?

84를 2와 42로 나눕니다.
2는 소수이므로 더 이상 나누지 않습니다.
42를 다시 2와 21로 나눕니다.
21을 3과 7로 나눕니다.

그래서 어떻게 소인수 분해가 어떻게 쓰이지?

RSA는 두 개의 큰 소수의 곱으로 이루어진 수를 공개키로 사용하는데, 이 수를 소인수 분해하는 것이 현실적으로 불가능할 정도로 어렵다는 점을 이용하여 보안성을 확보합니다

1. 키 생성 (Key Generation)

두 개의 큰 소수 p와 q를 선택합니다.
$n=p×q$
오일러 피 함수 ϕ(n)=(p−1)×(q−1)\을 계산합니다.
e를 선택합니다. e는 $1<e<ϕ(n)$ 이며, $gcd⁡(e,ϕ(n))=1$ 을 만족하는 값입니다. (일반적으로 e는 65537로 선택됨)
d를 계산합니다. $d×e≡1mod ϕ(n)$ 즉, eee의 모듈러 역원으로 d를 구합니다.

공개 키: (e,n)
개인 키: (d,n)

암호화 (Encryption)

평문 M (메시지)을 암호화하려면 다음과 같이 계산합니다: $C=M^e mod n$ 여기서 C는 암호문입니다.

3. 복호화 (Decryption)

암호문 C를 복호화하려면 다음과 같이 계산합니다: $M=C^d mod n$ 여기서 M은 복호화된 평문입니다.

RSA

그래서 여기서 어떻게 소인수분해의 어려움이 쓰이는거지?

n의 소인수분해 어려움:
- n = p * q입니다. 여기서 p와 q는 매우 큰 소수입니다.
- n이 공개되어도, n을 소인수분해하여 p와 q를 찾는 것은 계산적으로 매우 어렵습니다.
- 현재 알려진 가장 빠른 고전적 알고리즘으로도, n의 비트 수가 증가함에 따라 소요 시간이 지수적으로 증가합니다.

φ(n) 계산의 어려움:
- φ(n) = (p-1) * (q-1)입니다.
- p와 q를 모르면 φ(n)을 계산할 수 없습니다.
d 계산의 어려움:
- d는 e의 모듈러 곱셈에 대한 역원입니다. 즉, d * e ≡ 1 (mod φ(n))입니다.
- φ(n)을 모르면 d를 효율적으로 계산할 수 없습니다.

키 교환 프로토콜

핵심은 두개의 소수 (prime number)를 곱하여 얻은 매우 큰 수에서부터, 원래의 소수를 다시 찾는 것이 매우 어렵다는 수학정 성질에 기반한다
또한 Asymmetric Encryption으로서 Symmetric encryption에서 발생할 수 있는 키 노출 문제를 방지할 수 있다.

Bob이 공개키와 개인키를 생성하고 공개키를 Alice에게 보냅니다.
Alice는 랜덤 세션 키를 생성하고 Bob의 공개키로 암호화합니다.
Alice는 암호화된 세션 키를 Bob에게 보냅니다.
Bob은 자신의 개인키로 세션 키를 복호화합니다.
이후 Alice와 Bob은 이 세션 키를 사용하여 안전하게 통신합니다.

디지털 서명

단순 암호화뿐만 아니라, 메세지의 진위 여부와 위변조 방지를 위한 디지털 서명 기능도 제공한다. 이에따라 특정 사용자가 비밀 키로 메세지에 서명하고, 다른 사람들은 공개키로 이를 확인할 수 있어 신뢰성 측면에서도 중요한 역할을 한다.

이산 로그 문제 기반

What is the Discrete Logarithm Problem (DLP)?

→ 이산 로그 문제; g^x = h mod p 라는 식에서 g, h, p가 주어졌을 때 x를 찾는 것은 매우 어려움.

(ex. 3^29 mod 17 = 12 → Easy | 3^x mod 17 = 12 → Hard)

→ 이에 따라, one-way function은 대입하기는 쉬우나 <> 반대로 x를 유추하는 것이 매우 어렵다.
How does the Diffie-Hellman protocol work?

→ DLP에 기반한 Assymetric key exchage 프로토콜. 두 사람이 인터넷을 통해 비밀키를 안전하게 공유하는 것을 가능하게 해준다. 키 교환 자체를 암호화하기에 공격자가 실제 비밀키를 알아낼 수 없다.

Step 1. 공개 값 공유

두 사람이 p (prime number) 와 g (generator)를 공개적으로 공유한다.

ex) p = 23, g = 5

Step 2. 개인 값 생성

두 사람은 각각 자신만이 아는 비밀 값 a 와 b를 선택한다.

ex) a = 6, b = 15

Step 3. 키 교환

첫번째 사람은 A (= g^a mod p)를 계산하고, 두번째 사람은 B (=g^b mod p)를 계산해서 전송한다.

ex) A = 5^6 mod 23 = 8, B = 5^15 mod 23 = 19. (A=8 ↔ B=19)

Step 4. 비밀키 생성

첫번째 사람은 Ka (= B^a mod p)를 계산하고 두번째 사람은 Kb (= A^b mod p)를 계산하여 동일한 secret key를 가진다.

ex) for A: Ka = 19^6 mod 23 = 2, Kb = 8^15 mod 23 = 2 (Ka = Kb)
What is the main idea behind ElGamal encryption?

→ DLP에 기반한 public key encryption 시스템. 비밀 키 교환 & 메세지 암호화에 사용된다.

Step 1. 공개키 생성:

prime number (p), generator (g) 그리고 비밀값 (x)를 선택한다. e = g^x mod p, Pk = (p, g, e)

ex) p = 17, g = 6, x = 5 (1<x<p-1) → e = g^x mod p = 6^5 mod 17 =7

Pk = (p, g, e) = (17, 6, 7)

Step. 2 암호화:

발신자는 메세지 (M)를 암호화 할 때, 랜덤값 (y)를 선택하고 C1 = g^y mod p 와 함께 암호화된 메세지 C2 = M • e^y mod p 를 계산하여 전송한다.

Ciphertext = (C1, C2)

ex) Let: M = 13, y = 10 (1 < y < p-1)

C1 = 6^10 mod 17 = 15 | C2 = 13 * 7^10 mod 17 = 9| Ciphertext (15, 9)

Step 3. 복호화:

수신자는 비밀값 x를 사용해 암호문을 풀고 원래 메시지를 복원할 수 있다.

z = (C1)^x mod p, M = C2 * z^(p-2) mod p

ex) z = (15)^5 mod 17 = 2. _M = 9 2^(17-2) mod 17 = 13_*

Can you name a drawback of using DLP-based systems?

→ 위의 예시들과는 다르게, 높은 보안성을 위해서는 매우 큰 소수 및 generator가 필요하다. 이는 complexity를 크게 증가시키기에 많은 자원가 computing power를 필요로한다. 또한, 양자 컴퓨팅이 발전함에 따라 DLP 기반 암호 시스템이 쉽게 풀릴 위험이 있다.