[암호공학] 10장. Assymetric-Key Cryptography

대칭키와 비대칭키 암호화 방식을 둘다 필요하며 서로 상호보완적이다. 한 방식의 advantage가 다른 방식의 disadvantage를 보상한다.

비대칭키 암호 방식은 두 seperate key를 이용한다. 하나는 private, 하나는 public key이다. 암호화는 public key로 수행하고, 복호화는 private key로 수행하는 식이다.

대칭키 방식 암호화의 main idea는 trapdoor-one-way-function이다

 

** One-Way Function(OWF)

: f는 compute하기 쉬우나, f^-1은 compute하기 어려운 function.

** Trapdoor One-Way Function(TOWF)

: y와 trapdoor가 주어지면 x를 쉽게 compute할 수 있는 function.

 

ex)

OWF : n이 매우 클 때, n = p*q는 one-way function이다. p,q가 주어졌을 때 n을 계산하기는 쉬우나 n이 주어졌을 때 p와 q를 찾아내기는 매우 힘들다. 이를 factorization problem이라 한다.

TOWF : n이 매우 클 때, y = x^k mod n은 trapdoor one-way function이다. x,k,n이 주어졌을 때 y를 계산하기는 쉬우나 y,k,n이 주어졌을 때 n을 찾기는 매우 힘들다. 이는 discrete logarithm problem이라 한다. 그러나, 우리가 trapdoor인 k`(k prime)을 안다면, (이 때 k prime은 k의 inverse이다.) 우리는 x = y^k` mod n 으로 x를 찾아낼 수 있다.

 

1) Knapsack Cryptography

a = [a1, a2, a3, ..., ak], x = [x1,x2,x3,...,xk]일 때

a와 x가 주어졌을 때 s를 계산하기는 쉬우나, s와 a가 주어졌을 때는 x를 찾기 힘들다.

** Superincreasing Tuple

위 관계를 만족하는 tuple을 superincreasing tuple이라 한다.

knapsackSum과 inv_knapsackSum을 할 때 만약 a가 superincreasing하다면, 다음과 같은 방식으로 KnapsackSum과 Inv_knapsackSum을 계산할 수 있다.

이제는 Alice와 Bob이 어떻게 knapsack cryptosystem을 이용해서 secret message를 보내는지 확인해보자.

1 ) 먼저 superincreasing k-tuple인 b = [b1,b2,b3...,bk]를 만든다.

2 ) modulus n을 골라야하는데 n은 n>b1+b2+b3+...+bk 을 만족해야 한다.

3 ) random integer r을 선택하는데, n과 서로소이며 n-1보다는 작거나 같고 1보다는 크거나 같아야한다.

4 ) temporary k-tuple t=[t1,t2,t3,...,tk]를 생성한다. 이때 ti = r*bi mod n이다.

5 ) k object의 permutation을 선택하고 a = permute(t)로 새로운 a 튜플을 생성한다.

6 ) 이제 공개키는 k-tuple a이며, private key는 n,r과 k-tuple b이다.

 

예제 ) 

1) Bob이 super increasing k-tuple인 b를 생성한다.

b = [7,11,19,39.,79,157,313]

2,3)Bob은 n=900을 선택하고, r=37을 선택한다. permutation table은 [4 2 5 3 1 7 6]을 선택한다.

4)Bob은 tuple t를 계산한다.

t1 = 37*7 mod 900 = 259 , t2 = 37*11 mod 900 = 407, t3 = 37*19 mod 900 = 703....

 t = [259.,407,703,543,223,409,781]

5) a = permute(t)로, a = [543, 407, 223, 703, 259, 781, 409]가 된다.

6) 이제 공개키는 a이며, n,r,b는 private key이다.

 

이제 Alice가 Bob에게 single character "g"를 보내기로 하자.

"g"는 7-bit ASCII로 (1100111)이므로, 튜플 x = [1,1,0,0,1,1,1]이다. 이는 평문이다.

Alice는 s = KnapsackSum(a,x)를 계산한다. 위에서, a = [543, 407, 223, 703, 259, 781, 409]였으므로,

543+407+259+781+409 = 2399이다. s = 2399. 이는 Bob에게 보내지는 암호문이다.

 

Bob이 암호문 s = 2399를 받았다.

Bob은 s` = s*r^(-1) mod n을 계산한다. s = 2399, r = 37, n = 900이었다.

s` = 2399*37^(-1)mod900 = 527

이제 x` = Inv_knapsackSum(s`,b)를 계산한다.

b = [7,11,19,39.,79,157,313]였다. s` = 313 + 157 + 39 + 11 + 7이므로

이는 [1,1,0,1,0,1,1]이 된다.

이제 Permutation을 다시 해주면 (1100111)이 되고, 이는 char "g"이다.

 

2) RSA Cryptosystem

: 가장 일반적인 public-key 알고리즘이다. RSA는 두 가지 exponents인 e,d를 사용한다. 이 때 e는 public, d는 private이다. P가 평문이고, C가 암호문일 때 Alice는 C = P^e mod n 으로 암호문 C를 만들어내고, Bob은 P = C^d mod n으로 평문을 만들어내는 방식이다. 이 때 n은 매우 큰 수이며 key generation process에서 생성된다. 

 

위 그림에서 보듯이, 만약 RSA를 attack하기 위해서는 Eve는 e(sqrt(c)) mod n 만큼의 연산을 해야한다.

 

암호화 과정은 위 그림과 같다.

RSA는 두가지 대수적 구조, ring과 group을 이용한다.

Encryption과 Decryption에 commuitative ring R = <Zn,+,*>를 이용하고 이는 public하다.

Key-generation에 multiplicative group인 G = <Z*, *>를 이용한다. 이는 private하다.

 

Proof of RSA

위는 Euler's theorem이고, 아래가 증명과정이다. 

EX ) 

p = 11, q = 3이다.

n = p*q = 33이다.

f(n) = f(33) = (p-1)(q-1) = 10 * 2 = 20

encryption key로 e = 3을 선택한다(이는 f(n)과 서로소)

d*e = 1 mod f(n)이어야 한다. d*e = 1 mod 20, THEREFORE d = 7

 

message M = 5를 보낸다고 생각해보자.

암호화 : C = 5^e mod n = 5^3 mod 33 = 125 mod 33 = 26

복호화 : M = 26^6 mod 33 = 5

 

message M = 14을 보낸다고 생각해보자.

암호화 : C = 14^3 mod 33 = 5

복호화 : M = 5^7 mod 33 = 14

 

EX 2) Bob이 p = 7, q = 11을 선택했다.

n = 77, f(n) = 60

e = 13, d = 37 을 선택했다. (13 * 37 mod 60 = 1, 서로는 inverse 관계)

Alice가 평문 5를 Bob에게 보내고 싶다. 

암호화 : C = 5^e mod n = 5^13 mod 77 = 26

복호화 : M = 26^37 mod 77 = 5 mod 77 = 5

 

EX 3) John이 Bob에게 63을 보내고 싶다.

암호화 : C = 63^13 mod 77 = 28

복호화 : M = 28^37 mod 77 = 63

 

EX 4) Jeniffer은 p = 397, q = 401을 선택했고, n=159197 임을 계산했다.

f(n) = 158400이고, e = 343, d = 12007를 선택했다.

Ted가 message "NO"를 jeniffer에게 전송하고 싶다. 

NO를 plaintext 1314로 변환하고, Ted는 e와 n을 이용해서 메시지를 암호화한다.

암호화 : C = 1314^343 mod 159197 = 33677

복호화 : M = 33677^12007 mod 159197 = 1314

1314를 다시 char형으로 코딩하면 "NO"가 된다.

 

Attacks on  RSA

RSA에는 다음과 같은 potential attacks이 존재한다.

1) Factorization Attack

: RSA의 보안성은 modulus n 이 매우 크다는 아이디어가 근본이다. 만약 eve가 n을 factor해서 p와 q를 알아낼 수 있다면, Eve는 f(n) = (p-1)(q-1)을 알아낼 수 있고, 그러면 d = e^-1 mod f(n)을 찾아낼 수 있다. e가 public하기 때문이다. 따라서 Eve가 n을 쉽게 factorization할 수 없도록 RSA에서는 n은 300 decimal digits 이상, 1024bits이상의 크기로 쓸 필요가 있다. 이정도 크기의 수를 factorization하는데에는 infeasibly long period가 걸리기 때문에 factorization을 매우 효율적으로 할 수 있는 알고리즘이 나오지 않는 이상 RSA는 secure 하다는 것을 의미한다.

 

이하는 생략.

Recommendation on RSA **

이론적 및 실험적인 결과로 아래의 사항들이 추천된다.

1. n은 최소한 1024비트 이상.n은 2^1024값 or 309 decimal digits.

2. 두 소수 p와 q는 최소한 512bits이다. 

3. p와 q는 너무 가까운 값이지 않도록 설정.

4. p-1과 q-1은 최소한 하나의 큰 소수 factor를 가짐.

5. p/q의 비율은 분자나 분모가 작은 유리수와 가깝지 않은게 좋다.

6. moduls n은 공유되지 않는게 좋다.

7. e값은 2^16 + 1 혹은 이와 가까운 integer이어야 한다. 

8. private key d가 유출되면, Bob은 그 즉시 n과 e,d를 바꾸는게 좋다. n과 (e,d)pair를 알면 다른 pair도 찾을 수 있다는것이 증명되었다.

9. message는 OAEP를 통해 패딩되는게 좋다. 아래에 설명할 것.

 

short message의 RSA는 ciphertext가 short mesasge attack에 약하게 만든다. 따라서 padding, 즉 bogus data를 message에 adding해서 Eve의 attack을 힘들도록 만들 수 있다. 그중 한 방법이 OAEP이다. 

1. Alice는 메시지를 패딩해서 m-bit 메시지로 만든다. 이를 M이라고 함.

2. Alice는 random number r을 생성한다. 이 r은 k bits이고, r은 한번만 이용하고 파괴된다.

3. Alice는 public one-way function G를 이용한다. r을 받아 m bits integer로 바꾼다. m은 M의 사이즈이며, r<m이다. 이는 마스크라 한다.

4. Alice는 마스크 G(r)을 첫번째 plaintext 부분 P1에 이용한다. P1 = M + G(r)(+는 exclusive OR).이제 P1은 masked message이다.

5. Alice는 Plaintext의 두번째 부분을 만든다. P2 = H(P1)+r, 함수 H는 다른 public function으로 m-bits 입력을 kbits로 변환한다. 이 function은 cryptographic hash function일 수 있다. P2는 Bob이 이 mask를 복호화 후 볼 수 있도록 하기 위한 용도이다.

6. Alice는 C = P^e = (P1||P2)^e 를 만들고 C를 Bob에게 보낸다.

 

복호화

1. Bob은 P = C^d = (P1||P2)를 만들어낸다.

2. Bob은 value r을 재생성하는데, H(P1)+P2 = H(P1)+H(P1)+r = r으로 만들어낸다.

3. Bob은 이제 G(r) + P를 이용해서 G(r) + G(r) + M = M으로 padded message를 만든다.

4. 이제 패딩을 제거하면 original message를 받는다.

 

예제를 살펴보자.

우리는 512-bit p,q를 선택하고 n과 f(n)을 계산했다. e를 선택하고 d를 계산한다.

Bob이 e=35535를 선택했다. (ideal은 65537이지만) 그리고 f(n)과 e가 서로소이도록 하는 d를 계산한다.

이제 Alice는 "THIS IS A TEST"라는 메시지를 보내고 싶다. 이는 00-26 encoding scheme으로 변환된다.

 

4. Elgamal Cryptosystem

: RSA와 Rabin 말고, 다른 공개키 암호화 방식은 ElGamal 방식이다. 이는 discrete logarithm problem에 기초해있다.

예제와 함께 살펴보자.

Bob은 p= 11, e1 = 2, d = 3, e2 = e1^d mod 11 = 8으로 고른다.

따라서 public key는 (2,8,11)이 되고 private key d는 3이 된다.

alice는 r=4를 선택해서 C1과 C2를 계산하고자 한다.(평문은 7)

 

C1 = e1^r mod p = 2^4 mod 11 = 5

C2 = P * e2^r mod 11 = 7 * 4096 mod 11 = 6

따라서 암호문은 (5,6)이 된다.

이제 Bob이 메시지를 받아 복호화한다.

C2 * (C1^d)^-1 mod 11 = 6 * (5^3)^-1 mod 11 = 6*3 mod 11 = 7

성공적으로 복호화 되었다.