Public key (Asymmetric key)

Previous Learning) The Advantages of symmetric keys: 

The ciphertext size is small, and the process of encryption and decryption is very fast.

Then, how can transfer the secret key to the public channel?

 

Asymmetric(Public)-Key Cryptography?  Encryption key is public, decryption key is secret.

 

▪︎ 단계 1) Public-key Encryption (공개 키 암호)

- 암호화/복호화 키 상이 + 암호화 키 공개 가능(비밀 키 공유 필요X) - 인터넷 프로토콜의 초석

- 암호화 키를 이용해, 복호화 키를 알아내는 것의 어려움

- 사전에 키에 대한 정책을 교환하지 않아도, 암호화 전송 가능

Ex)  RSA, ElGamal Encryption, 격자기반 공개키 암호

 

▪︎ 단계 2) Key exchange protocol (키 교환 프로토콜)

- Key Agreement(키 합의/공유)

- 두 통신 당사자가 공개적인 정보 교환의 결과로 비밀키를 얻는 프로토콜

- 키 교환을 통해 얻은 비밀키로 대칭키 암호화 통신 수행 가능

* Secure Channel(비밀키 공유) 생성 → 암호화 통신(대칭키 사용 가능)

Ex) Merkle's puzzle / Diffie-Hellman 키 교환 기법 - Transport Layer Security (TLS)

 

# 머클의 퍼즐 - 공개키 암호 초기 아이디어

1) Bob -> (서로 다른 ~ 비밀 키/식별 키) 쌍 * 1000개의 퍼즐 형태 (무차별 공격 가능한 대칭키 암호) -> Alice (전달)

2) Alice, 1000개 조각 중 랜덤하게 한개 선택 -> 복호화된 ID/Secret_Key 획득 -> Secret_Key 저장 후, Bob에게 ID 전달

3) Bob, ID에 해당하는 Secret_Key를 공유키로 저장

 

-- 공격자에게 주어진 정보: ID, 1000개의 퍼즐

=> 공개된 채널을 통해 비밀키 공유 가능, But 단점:

1. 1000개 퍼즐 제작 시간 소요 및 큰 저장 공간 필요

2. 1000개 퍼즐 전송시, 전송량 및 전송 시간 상당 소요

3. Alice의 퍼즐 푸는 시간(무차별 대입 공격) 소요

 

# Diffie-Hellman 키 교환 프로토콜 - 인터넷 상 암호화 통신 기술 대중화

ㄴ 중간자 공격(상대방 인증X)에는 취약(도청 가능성) → 추가 안전장치 필요(p, g 선택의 중요성) 

 

[예제, 참조] *실제로는 안전을 위해 10진수 수백~수천자리 크기의 큰 소수를 사용함

공개된 정보 = 파란색, 비밀 정보 = 붉은색 // *모듈러 연산 ~ 덧셈/곱셉에 대하여 결합, 교환, 분배법칙 성립

* 이산로그 문제 (Discrete Logarithm Problem, DLP)

ㄴ y = gx mod p 에서,  g x p ~> y 도출 가능, But g y p ~> 도출 어려움

* DL ⇒ Computational_(CDH, 계산 문제) Decisional_(DDH, 결정 문제)

1. 앨리스와 밥은 p(소수 선택)=23, g(1~p-1까지의 정수 중)=5를 사용하기로 합의한다.
2. 앨리스가 비밀 정보를 전송하기 위해 임의의 정수 a=6을 고른 후, 밥에게 A = ga(승) mod p 을 전송한다.
   • A = 56 mod 23 = 15,625 mod 23 = 8 (나머지)
3. 밥은 임의의 정수 b=15를 고르고, 앨리스에게 B = gb mod p를 전송한다.
   • B = 515 mod 23 = 30,517,578,125 mod 23 = 19
4. 앨리스는 밥에게서 받은 B를 바탕으로 s = B a mod p를 계산한다.
   • s = 196 mod 23 = 47,045,881 mod 23 = 2
5. 밥은 앨리스에게서 받은 A를 바탕으로 s = A b mod p를 계산한다.
   • s = 815 mod 23 = 35,184,372,088,832 mod 23 = 2
6. 앨리스와 밥은 이제 비밀 키 s = 2를 공유하게 되었다.

--> 이후 비밀키 s를 가지고, 대칭키 암호를 이용하여 통신 암호화 가능

 

* 여기서 𝑝가 충분히 클 경우, 외부에서 비밀 키를 알아내기 위해 도청을 하는 도청자 이브는 𝑔𝑎나 𝑔𝑏를 통해 𝑠를 알아낼 수 없는 것으로 알려져 있다.

* 그러나 𝑝 나 𝑎, 𝑏가 너무 작을 경우, 도청자는 가능한 모든 조합을 다 계산해보는 방식으로 𝑠를 계산해낼 수 있다.

따라서 실제 비밀 통신에는 충분히 큰 소수를 사용해야 한다.

만약 𝑝 가 최소 300자리의 소수이고, 𝑎와 𝑏가 각각 100자리 이상의 정수일 경우, 현재 인류가 보유한 모든 컴퓨터를 동원해도 공개된 정보로부터 비밀 키를 알아낼 수 없는 것으로 알려져 있다.

---

 

 

Computational Complexity = 기본 연산 수행 횟수 (input size에 대한 함수로 표현)

Ex) n 개의 Merkle's puzzle을 푸는 계산복잡도 n에 비례, n 비트 곱셈의 계산복잡도 - n2에 비례

*Big-O Complexity Chart 참조

 

+𝑁 (= 𝑝 ⋅ 𝑞) 인수분해의 계산 복잡도는 입력 비트 수에 대해, 지수함수적으로 증가

ㄴ Polynomial time algorithm: n 비트 입력과 어떤 다항식 F(x)에 대해 계산 복잡도 O(f(n))를 가진 알고리즘

⟷ Superpolynomial time algorithm: O(g(n))만에 수행, g(n)은 모든 다항식보다 빠르게 증가하는 어떤 함수 (지수 복잡도)

 

* 문제를 풀기 위해, 다항시간 알고리즘이 존재하는 문제를 P문제 라고 지칭

* 인수분해 문제처럼, 채점하는 다항시간 알고리즘이 존재하는 문제를 NP문제라고 지칭 (풀이는 어려우나, 답을 확인하는 것은 단순)

단, P문제 = NP문제가 될 수 없도록, NP문제를 구성해야 함

 

Ex) NP 문제 - 인수분해 (RSA 암호) / 이산로그 (Diffie-Hellman 키 교환) → 양자 컴퓨터로 다항시간 안에 풀 수 있음

ELGAMAL 공개키 암호 - 이산로그 (Diffie-Hellman 기반, 공개키 암호화 알고리즘)

 

# 타원 곡선 암호: 평면에 있는, 좌표성분들이 x,y로 구성된 곡선의 일종 - 특별한 성질로, 대수기하학과 수론의 주요 연구 대상

방정식 )  𝑦2 = 𝑥3 + 𝑎𝑥 + 𝑏 (단, 𝑎, 𝑏는 − 16 (4𝑎3 + 27𝑏2) ≠ 0을 만족하는 상수)

+ 타원 곡선 위에서의 덧셈이란? 곡선위 두 점 P, Q에 대해, 두 점의 덧셈을 어떻게 계산할지에 대한 규칙 < 교환법칙, 결합법칙 충족 >

ㄴ P, Q를 지나가는 직선을 그리고, 직선이 지나는 타원 곡선위의 제 3점(R)을 찾는다. (R축과 대칭인 점 = P + Q)

* 타원 곡선 덧셈 예외 처리 - 자기 자신에 대한 덧셈, Y축과 평행한 직선상에 놓인 P, Q의 경우

* MOD P에 대한 타원 곡선 - 소수 p를 하나 정하고, x,y 좌표 각각이 mod p에 대해 합동이면 두 점을 같은 것으로 취급

+ ) 타원 곡선 이산로그 문제

 

 

---

 

 

---

https://ko.wikipedia.org/wiki/%EB%94%94%ED%94%BC-%ED%97%AC%EB%A8%BC_%ED%82%A4_%EA%B5%90%ED%99%98

To be continued..