[Cryptography] Diffie-Hellman, ECC

[Cryptography] Diffie-Hellman, ECC

Diffie-Hellman Key Exchange

- 비밀 키를 공유하는 방법

- 유한 필드의 exponentation에 기반하고 있음

- 안전성은 이산 대수 문제(DLP, Discrete logarithms problem)의 어려움에 기반

Key Exchange

1. 큰 소수인 p를 선택

2. mod p의 primitive root인 g 설정

3. 수신자, 송신자는 a와 b를 선택하여 A = g^a mod p, B = g^b mod p를 계산

4. 계산된 A,B를 서로에게 전송하고 K = B^a mod p = A^b mod p를 계산

5. 계산에 의해 생긴 k를 비밀 키로 사용

Security

1. 이산 대수 문제의 어려움에 기반하여 안전성이 유지

2. Man-in-the Middle 공격에 취약

- 수신자, 송신자 사이에서 오고 가는 패킷을 탈취하여 키를 획득

- p, g, A, B를 전송과정에 도청하여 이를 이용하여 키 계산

ElGamal Cryptography

- Diffie-Hellman과 관련있는 공개키 암호 시스템

- 안전성은 이산 대수 문제(DLP)의 어려움에 기반

Setup

1. 비밀키 선택

- 1 < Xa < q - 1

2. 공개키 계산

- Ya= a^Xa mod q

Message Exchange

1. Message 표현

- 0 <= M <= q-1 로 표현

- q보다 클 경우, block으로 나눔

2. Random number k 선택

- 1 <= k <= q-1

3. One-time key 계산

- K = Ya^k mod q

4. Message M을 (C1,C2)로 암호화

- C1 = a^k mod q

- C2 = KM mod q

5. 복호화

- K = C1^Xa mod q

- M = C2 * (K^-1 mod q)

Elliptic Curve Cryptography

- RSA, Diffie-Hellman 매우 큰 키와 message를 가공해야하기 때문에 큰 부하가 일어남

- 이 점을 해결하기 위해 등장

- 작은 키로 같은 안전성을 제공

- 특정 점에 대한 타원 곡선의 이산 로그를 찾는 것의 어려운 점에 기반

- 덧셈 : modulo multiply

- 연속 덧셈 : modulo exponentiation

Real Elliptic Curve

- 타원 곡선은 두개의 변수 x,y의 방정식과 계수로 이루어져있음

- Real Elliptic Curve에서는 모두 실수로 된 방정식 이용

Finite Ellipic Curve

1. Zp에 정의된 소수 curve인 Ep(a, b)

- 소수로 modulo된 integer 사용

- software에 적합

2. GF(2^n)에 정의된 binary curve인 E2m(a,b)

- binary coefficients를 사용한 polynomials 사용

- hardware에 적합

Security

1. elliptic curve logarithm problem에 기반하여 안전성 보장

2. RSA와 키 길이가 같을 경우 비슷한 속도지만, RSA보다 훨씬 작은 키 길이를 사용하여 빠르고 안전