7. Public Key Cryptography - RSA (2)

RSA Challenge Numbers

Prime Factorization 은 Hard problem 이다. 따라서 RSA 는 이를 사용한다.

RSA-576 : 174 digit number 사용

RSA-768 

RSA-2048 : 617 digit number 사용 

 

 

RSA Cryptosystem

RSA key 만들기

- p, q를 아주 큰 소수로 정한다.

- n = pq

- φ(n) = (p − 1)(q − 1)

• e는 1 < e < φ(n), gcd(e,φ(n)) = 1 를 만족하는 정수이다.
• d는 1 < d < φ(n), ed ≡ 1(mod φ(n)) 를 만족하는 정수이다.

(d는 extended euclidean algorithm 으로 계산한 modulo φ(n) 에 대한 e의 inverse이다.)

public key : (n,e) / private key : (n,d) 

n 은 public 하다. 왜냐면 n을 알더라도 p,q 를 아는 것이 어렵기 때문이다.

* 만약 gcd(e,φ(n)) 가 1이 아니라면, multiplicative inverse e 는 존재하지 않는다.

 

 

encryption(using e) / decryption(using d)

ed = 1 + k-times * φ(n) 와 같다.

(m^φ(n))^k mod n 은 Euler's theorem 과 동일하므로 1이 될 것이다.

따라서 m 이 성립하게 된다.

 

 

ex) 

 

e는 gcd(e,φ(n)) = 1을 만족하며 φ(n) 보다 작은 수 이므로, 다른 수도 가능할 것이다.

d는 5d = 1 (mod φ(n)) 을 만족하는 e의 multiplicative inverse 이다.

따라서 216 = 5 * 43 + 1

1 = 216 - 5 * 43 (mod 216)

1 = -5 * 43 (mod 216)

1 = 5 * 173 (mod 216)

이므로 d 는 173이 된다.

 

sender 는 receiver 에게 public key (e,n) 으로 encrypt 한 ciphertext 91 을 보낸다.

오직 receiver 만이 유일하게 (d,n) private key 을 가지고 있기 때문에 ciphertext 를 plaintext 로 decrypt 할 수 있다.

 

 

예시)

위와 같은 과정을 통해 Message Confidentiality 가 보장된다.

왜냐하면 attacker 가 전송되는 ciphertext 64를 가로채더라도, (d,n) key 가 없기 때문에 descrypt 할 수 없기 때문이다.

 

 

 

Security of RSA Cryptosystem

ciphertext 로 부터 m = c^d mod n 을 해독하기 위해서는 private key d가 필요하다.

d를 계산하기 위해서는 ed = 1(mod φ(n)) 를 통해 e의 역수인 d를 알아내야 한다.

이때, φ(n)는 (p-1)*(q-1) 의 값이므로, attacker 가 큰 factoring 값을 통해 p-1,q-1를 알아내기 매우 어렵다.

m -> d -> φ(n) -> (p-1),(q-1) -> p,q 순으로 알아내야 하므로 , 이는

harness of factoring large integer 에 따라 security 가 보장된다.

 

1024 bit-RSA (309 digits) 가 흔히 많이 사용된다.

더 강한 security 가 요구되는 군대같은 경우에는 4096 bit-RSA 가 선호된다.

key 길이가 두배 길어질 경우, encryption 은 4배가 느려지고 decryption 은 8배가 느려진다.

encryption < decription (더 어려움) 

-> 지수적 증가

 

 

 

|p-q| shoudl be large

만약 서로 다른 p,q 가 비슷하여 √n 에 가깝다면, 이는 안전하지 않다.

 p,q 가 아주 가깝다면 v는 아주 작은 값이고, u는 √n 보다 조금 큰 값일 것이다.

이 경우, 우리는 √n + 1 , √n + 2... 을 시도해보면서 u^2 - n = v^2 인 값을 추측할 수 있다.

따라서 빠르게 u 와 v를 결정할 수 있으며,

n = pq, p=u +v, q = u-v 이므로 p,q 까지 알 게 된다.

 

따라서 attacker 는 n을 통해 p,q 를 알게 되었으므로, φ(n) 을 계산할 수 있고, 이를 통해 e 를 계산하고, 마지막으로 d까지 알 수 있게 되므로 매우 위험하다.

 

 

예시)

위와 같은 경우에, √n 보다 조금 큰 값인 405를 u라고 추정하였다.

따라서 164009 = 405^2 - v^2 = 164025 - v^2 이므로, v = 4, u = 405 임을

쉽게 찾을 수 있다. 따라서 |p-q| 는 충분히 커야 함을 알 수 있다.

 

 

n = pq cannot be common

 

두개의 public-private key 쌍 (e1,d1) 과 (e2,d2) 가 n=pq 라는 공통된 값을 사용한다고 가정하자.

그리고 e1과 e2 는 서로소이다.

이때 c1 과 c2 는 공통된 mod n 을 통해 encrypt 되었다.

common modulo 를 사용한 경우, attacker 는 private key 를 모르더라도 ciphertext로 부터 message 를 알 수 있다.

gcd(e1,e2)=1 임을 알고 있으므로, extended euclidean algorithm 으로 r x e1 + s x e2 = 1을 만족하는 r,s 를 계산할 수 있을 것이다. 

따라서 c1^r x c2^s = m^(r x e1 + s x 32) = m mod n 이고, r x e1 + s x 32 = 1 이므로, m을 구할 수가 있게 된다.

 

따라서 (n1,e1), (n2,e1) .... 등 매번 다른 n을 사용하는 것이 매우 중요하다.

 

 

Common Modulus Attack 예시

 

 

Guard your φ(n)

φ(n) 과 n 를 안다고 가정해보자.

따라서 p를 구할 수 있게 된다. -> q도 구할 수 있다.

 

 

 

 

Hasihg is required in RSA

attacker 가 새로운 R을 만들고, C*R mod n으로 새로운 Ciphertext 를 만들어 receiver 에게 전송한다.

receiver 는 d를 이용해 해독하는데, m*r 이 나오게 된다. 이때 의미 없는 메시지라면, receiver 는 attacker 가 보낸 것임을 감지할 수 있다.

한편, m이 session key 와 같은 random string 이였다면, receiver 는 mr 이 맞는 것인지 아닌지를 구별할 수 없을 것이다.

 

 

따라서 message 와 hashed-message H(m) 을 묶어서 같이 encrypt 한 것을 ciphertext로 만든다.

attacker 는 아까와 같이 C*R mod n 으로 새로운 ciphertext C' 을 만들고 전송할 것이다.

receiver 는 d를 가지고 descrypt 하는데, 결과는 a | b 두부분(message, Hashed-message)이 될 것이다.

만약, correct 한  ciphertext라면, H(a) 를 한 결과는 b가 될 것이다.

Hash를 통해, receiver 는 ciphertext 가 수정된 것인지 아닌지 check할 수 있다.

ㅣ

 

 

Encrypt a long message

message 가 n보다 크다면, m은 각각의 조각은 n보다 작은 m1m2m3... 로 나눠져야한다.

 

Symmetric vs RSA  -> trade off!

 

- short message 보내기

 

- large size file 보내기

c2 : Message 를 secret key(symmetric key) 로 encrypt 하기

c1 : k 를 e로 encrypt 하기

 

 

RSA Digital Signature

alice 가 bob 게 메시지 + 서명을 보내려고 한다.

alice 는 Hashed-message H(m) 을 private key 로 encrpyt 한다. -> signiature 생성

서명을 alice 의 공개키(e) 로 복호화 한 것이 H(m) (해시 메세지) 과 같다면 sign 이 유효한 것이 확인된다.

 

 

hash function 을 사용하는 이유

1. reduce size : 긴 메시지 m > n 에 대해서, hash function 을 사용하면 H(m) < n 으로 길이를 줄일 수 있다. 

2. imporve security : 다음 상황은 hash function 없이 서명을 하는 경우이다.

위와 같은 경우에, attacker 은 서명 1,2 를 가지고 새로운 서명 3 을 만들었으며, 마찬가지로 새로운 메세지3을 만들었다.

attacker 는 m3 와 서명3 을 수신자에게 보내는데, 놀랍게도 이 서명은 공개키 e 에 의해서 verify 된다.

왜냐하면 σ3^e = (σ1*σ2)^e = (m1*m2)^ed mod n = (m1*m2) mod n (ed는 서로 역 이므로, 곱하면 1) = m3 mod n

으로, 성립하기 때문이다.

-> Hash 를 사용하지 않으면 서명을 guarantee 할 수 없다. 또한, Hash 를 사용하면 attacker 은 새로운 signature 을 직접 만들 수 없게 된다.

 

 

m1,m2 가 의미없는 메세지라면, m3 도 마찬가지 일테니깐 verifier 는 이를 탐지할 수 있다.

그러나 session key 처럼 random string 이라면 m3 도 random string 일테므로, 이때는 attacker 가 보낸 것임을 탐지 할 수 없다.

 

 

★★★ send a source authenticated message with large size over Internet

privacy - Encrypt/Decrypt

Data Authenticatoin - Hash

Non-Repudiation - Bob 은 자신이 서명한 사실을 부인할 수 X

User Authentication - Digital Signature

 

1. Bob 은 메세지를 Hash 함수에 넣어 H(M)을 만들고 그것을 자신의 private key 로 Encrypt 하여, 서명 σ1 을 생성한다. (mod n1 -> bob 의 n1 으로 modulo)

2. 짧은 key k 를 선택한다.

3. AES 로 M(message) 와 σ1,k(서명과 k) 를 Encrypt 한 C1 을 생성한다.

4. k(key) 와 H(K) (key 를 Hahed 한 것) 전체를 Alice 의 공개키 e2로 암호화 한 C2를 생성한다. 

(mod n2 -> alice 의 n2 로 modulo)

 

-> Bob 은 (C1, C2) 를 Alice 에게 전달한다.

 

5. Alice 는 C2를 자신의 개인키 d2로 복호화하고 mod n2 하여 나온 k | H(K) 에 대해서, K를 Hash 함수에 넣은 값이 H(K) 와 동일한지 비교하고, 같다면 올바른 key 임을 검증한다.

6. 구한 key 로 C1 을 복호화 하여 결과로 M 과 σ1 을 얻는다.

7. σ1을 e1(bob 의 public key) 로 복호화한 σ1^e1 이 H(M) mod n1 과 같은지 비교한다.

같다면 Bob 이 sign 한 message임이 verify 된다.