공개키 암호 알고리즘

공개키 암호

- 암/복호화에 서로 다른 키를 사용

- 송신자는 수신자의 공개키를 이용하여 암호화, 수신자는 자신의 개인키로 복호화 가능

- 수학적 난제를 기반으로 설계

- 대칭키 암호에 비해 속도가 느림

 

Diffie-Hellman

- 이산대수 문제를 기반한 방식

- 중간자 공격(MITM : Man In the Middle Attack)에 취약

Alice와 Bob이 상대방에 대한 인증을 보장하지 못한다. 공격자는 중간에서 통신을 가로채 Alice와 공격자, 공격자와 Bob 사이에 각각 두 개의 디피 헬먼 키 교환을 생성하고, Alice와 Bob이 각각 서로와 통신하는 것처럼 위장할 수 있다.

 

키 교환 절차

1) Alice는 소수p, 그리고 1부터 p-1까지의 정수 g를 선택하여 사전에 Bob과 공유한다.

2) Alice는 0보다 크거나 같고 p-1보다 작은 정수 a를 선택한다. a는 공유하지 않는다.

3) Alice는 A=g^a mod p를 계산한다.(g^a를 p로 나눈 나머지)

4) Alice는 A를 Bob에게 전송한다.

5) Bob은 0보다 크거나 같고 p-1보다 작은 정수 b를 선택한다.

6) Bob은 B=g^b mod p를 계산한다.(g^b를 p로 나눈 나머지)

7) Bob은 B를 Alice에게 전송한다.

8) Alice는 B^a mod p를, Bob은 A^b mod p를 계산한다.

B^a mod p = (g^b)^a mod p = g^ab mod p

A^b mod p = (g^a)^b mod p = g^ab mod p

따라서 g^ab mod p라는 공통의 비밀키(K)를 공유한다.

 

 

ECC(Elliptic Curve Cryptography)

- 타원곡선 이론에 기반한 공개키 암호방식

- 이산대수 문제에 착안해 만들어진 암호방식으로, 256비트의 ECC키는 3072비트의 RSA키와 비슷한 암호화 레벨이며 킷값이 커질수록 RSA보다 암호화 레벨이 급격하게 높아진다.

- RSA보다 훨씬 효율적

- 디지털 서명, 키 교환을 위한 공개키 암호에 사용

 

Elgamal

- 이산대수 문제의 어려움에 기반한 방식

- p가 소수이고 g가 원시근일 때 g, x, p를 이용하여 y=g^x mod p를 구하긴 쉽지만, g, y, p 값을 이용하여 지수승의 x를 구하기는 어렵다.

- x가 개인키, y가 공개키로 사용된다.

- 디지털 서명, 암호화, 키 교환에 사용

- 속도가 느림

 

 

RSA(Rivest Shamir Adleman)

 

A와 B가 서로 비밀 메시지를 주고 받아야 할 경우, B가 A에게 메시지를 전달하기 위해서는 A의 공개키가 필요하다. A는 아래와 같은 방법을 통해 공개키와 개인키를 생성한다.

 

p 와 q 라고 하는 두 개의 서로 다른 소수(p q)를 고른다.

1) p 와 q 두 수를 곱하여 N = pq을 찾는다.

2) ∅(N) = (p-1)(q-1)를 구한다.

3) ∅(N) 보단 작고, ∅(N)와 서로소인 정수 e를 찾는다.

4) 확장된 유클리드 호제법을 이용하여 d × e를 ∅(N)로 나누었을 때 나머지가 1인 정수 d를 구한다. (de ≡ 1 (mod ∅(N)) )

 

위에서 구한 e와 N은 공개키이고, d와 N은 개인키이다.

A는 공개키(N,e)를 B에게 공개하고 B는 공개키를 이용하여 메시지를 암호화해서 A에게 전달한다. A는 B로부터 전달받은 암호문을 자신의 개인키로 복호화하여 메시지를 확인할 수 있다.

(A의 공개키로 암호화했기 때문에 A의 개인키로만 복호화 가능함)

 

암호화

C = m^e mod N

 

복호화

D = C^d mod N

 

 

Rabin

- RSA와 같은 원리이나 더 간단한 구조이다.

- RSA 암호에서 e와 d를 2로 고정한다. 중국인의 나머지 정리를 이용해서 복호화한다. 복호화한 결과는 4가지로 나오지만, 1개로 추론하여 결정할 수 있다.

---

 

* 모듈러 연산

11^7 mod 13을 구한다고 가정하면

 

11^2 = 121 mod 13 = 4

-> 4 (mod 13)

 

11^4 = (11^2)^2 = 4^2 = 16 mod 13 = 3

-> 3 (mod 13)

 

11^7 = 11^4 * 11^2 * 11 = 3 * 4 * 11 = 132 mod 13 = 2

-> 2 (mod 13)

 

최종적으로 2가 남음

 

 

* 유클리드 호제법

2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다.

a,b에 대하여 a를 b로 나눈 나머지를 r이라 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

 

1071과 1029의 최대공약수를 구하면,

1071은 1029로 나누어떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다.

=> 42

1029는 42로 나누어떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다.

= 21

42는 21로 나누어 떨어진다.

따라서, 최대공약수는 21이다.

q(몫)	r1	r2	r(나머지)
1	1071	1029	42
24	1029	42	21
2	42	21	0
	21(최대공약수)	0