[정보보호] RSA

RSA란 가장 많이 쓰이는 public-key scheme 중 하나로, finite Galois field 에서의 exponentiation을 기반으로 한다.

큰 소수를 곱하는 것은 쉽지만, 결과로 나온 큰 수를 다시 소인수분해 하는 것은 매우 어렵다.

RSA는 이 아이디어를 이용하여 큰 정수(1024, 2048 bits 등)들을 사용해 정수를 factoring 하는데에 드는 cost를 높여 보안을 제공한다. 

 

<RSA 알고리즘>

** 내가 여기서 생겼던 의문은 (e,n)이 public key로써 이미 알려져 있다면, d는 mod n에 대한 e의 multiplicative inverse이므로 충분히 유추될 수 있지 않냐? 라는 것이었다. 하지만 RSA에서 사용되는 수 n은 굉장히 큰 소수 p,q의 곱으로 이루어져 있고, 이 p와 q는 공개되지 않는다. (앞에서 이야기했듯 큰 소수를 곱하는 것은 쉽지만, 결과로 나온 큰 수를 다시 소인수분해 하는 것은 매우 어렵다.) 뒤에서 다시 설명하겠지만 RSA의 decryption 시 mod n에 대해 direct 하게 decryption을 진행하는 것이 아니라, 이를 CRT를 이용하여 p와 q로 나누어 decrypt 하는 방식이 더 빠르므로 이 방식을 채택한다. 즉 multiplicative inverse를 구하기 위해서는 n만 안다고 해서 쉽게 구할 수 있는 것이 아니며, p와 q 또한 알아야 하기 때문에 RSA의 보안이 유지될 수 있다. 

 

<RSA 알고리즘 예제>

 

 

 

** power modulo 계산 시  계수를 이진법으로 바꾸는 이유는 square and multiply로 인한 exponentiation을 이용하기 위함

 

---

 

Efficient Encryption

encryption 시 exponentiation을 사용한다. (power of e)

따라서 e를 많이들 작게 선택하는데, 그게 encryption을 더 빠르게 만들어주기 때문이다. 

자주 쓰이는 e에는 3, 17, 65537(2^16+1)이 있다.

하지만 e가 3처럼 너무 작으면 공격받을 가능성이 있다. 

 

잘 모르겠음

---

Efficient Decryption

 

RSA Decryption 시 exponentiation to power d (M = C^d mod n)을 쓴다. 

이 때 d가 충분히 크지 않으면 brute-force attack이나 다른 cryptanalysis로부터 insecure 하다.

만약 d가 너무 크면, computational cost가 높다.

 

 

computation  속도를 높이기 위해 CRT를 사용하여, mod n을 mod p와 mod q로 나눈다. 

이 방식은 mod n을 direct 하게 사용하는 것보다 약 4배가 더 빠르고, 

이는 p와 q값을 각각 알고 있는 private key owner만 시행할 수 있다. 

 

---

RSA Key Generation

 

1. RSA 사용자는 쉽게 유추될 수 없을만큼 충분히 큰 prime인 p,q를 설정해야 한다. 이 때 arbitrarily large prime을 생성할 수 있는 효과적인 기술이 없기 때문에, 주로 guess 한 후 probabilistic test를 거친다. 

 

2. e,d 중 하나를 고른 후 다른 하나는 inverse algorithm으로 compute 한다. 

 

---

 

RSA Security

 

RSA를 attack 하는 방법에는 다음과 같은 것들이 있다.

1. Brute force key search: 키의 숫자가 크면 infeasible 하다.

2. Mathematical attacks: n을 소인수 분해하여 ø(n)을 계산하기 어렵다는 점을 이용

3. Timing attacks: Decryption이 진행되는 동안의 시간을 측정하여 공격하는 방법

4. Chosen Cipher text attack: RSA 시스템에 특정한 plaintext를 제공하고 그에 대응하는 ciphertext를 관찰한 후에 이를 이용하여 시스템의 private key를 추측하고 암호문을 해독하려는 시도

 

 

Factoring problem: 큰 정수를 두 소수의 곱으로 분해하는 문제

 

<세 가지 Mathematical 접근 방식>

 

 

 

 

 

 

 

 

1. n을 소수 p와 q의 곱으로 분해하고, 그 후에 ø(n)을 계산하여 d = e-1 mod ø(n)을 구함
2. p와 q를 먼저 결정하지 않고 ø(n)을 직접 결정하고, 이후에 d = e-1 mod ø(n)을 계산함
3. ø(n)을 먼저 결정하지 않고 바로 d를 찾음

 

ø(n)을 결정하는 것은 n을 factoring 하는 것과 동일한 문제이다. 큰 n을 factoring 하는 것은 매우 어렵지만 이는 연도별로 알고리즘이 개선되며 느린 발전을 보이고 있다. 알고리즘의 발전은 "Quadratic Sieve (QS)" → "Generalized Number Field Sieve (GNFS)" → "Lattice Sieve (LS)"로 이루어졌고, 현재까지 최고의 기술은 "Lattice Sieve" (LS)를 사용하여 200자리(663비트)의 소수로 이뤄진 키를 분해하는 것이다,
현재로서는 1024- 2048bit key RSA가 secure 하다. 단, p와 q는 크기가 비슷해야 하며, 다른 constraint를 만족해야 한다. 

 

Timing attacks

 

- 1990년대 중반 Paul Kocher에 의해 개발

 

-  1)연산에서 발생하는 시간의 차이 2) 연산에 소요되는 시간을 기반으로 피연산자의 크기를 추론한다. 

e.g.1) 작은 수와 큰 수를 곱하는데 걸리는 시간 등 연산에서 발생하는 시간의 차이를 이용

e.g.2) RSA exponentiation 연산에 걸린 시간을 이용하여 키 추정, 암호문 해독

 

- ciphertext only attack 방법

 

- 대응책(Counterattack)

1) 일정한 exponentiation time 사용: 알고리즘을 설계할 때 exponentiation에 걸리는 시간을 일정하게 유지하여 시간변동성 줄임
2) random delays 추가: 알고리즘에 random delays을 추가하여 시간 기반 공격을 어렵게 만든다.
3) 계산에 사용되는 값을 블라인드 처리: 연산에 사용되는 중요한 값들을 블라인드 처리하여 timing attack을 방어

 

 

Chosen Ciphertext Attacks

 

Chosen Ciphertext Attacks에서 공격자는 특정한 암호문을 선택하고 그에 대응하는 평문을 얻을 수 있는 능력을 가지고 있다.

 

- 이는 다음 속성을 이용한다. 

 

 

- 해킹 과정은 다음과 같다. 

 

- 대응책(Countermeasure) 

1) Random pad 추가
: plaintext에 랜덤한 패딩을 추가하여 chosen cipher text attack에 대비한다. 하지만 더 정교한 CCAs가 가능하기 때문에, 이는 불충분하다. 

2) OEAP(Optimal Asymmetric Encryption Padding)
: RSA Security Inc.에서 개발된, 더 정교한 CCAs에 대비하기 위한 방법이다. 
OAEP는 Feistel 네트워크의 형태를 가진 것으로, Asymmetric encryption (예: RSA) 전에 plaintext processing을 하는 방식으로 사용된다. 이는 PKCS#1 v2에서 Standardized 되었다.

 

 

 

Breaking RSA

 

1) Coppersmith's attack
RSA에서 사용되는 moduli n을 소인수로 factorization하는 기법

 

2) Bleichenbacher's attack:
PKCS#1 v1.5에 대한 Adaptive CCA로, 이는 SSL/TLS 서버를 대상으로 하는 practical attack으로 활용될 수 있다. 

 

3) Manger's attack
PKCS#1 v2.0 RSA-OAEP 암호화에 대한 Adaptive CCA이다. 이는 특정한 조건이 충족될 때 RSA-OAEP 암호문을 해독할 수 있게 해준다.