RSA

안녕하세요. 옆집 컴공생입니다.

정말 유명한 RSA에 대해 이야기 해봅시다.

RSA는 1978년, MIT의 Rivest, Shamir, Adleman 세명의 연구로 발명되었습니다. 공개키 암호시스템의 하나로 암호화뿐만 아니라 전자서명이 가능한 최초의 알고리즘입니다. 공개키 스키마로 가장 유명한데요. 보통 1024비트 이상의 큰 정수를 사용합니다.    

 

---

 

바로 어떻게 작동하는지 확인해보겠습니다.

그렇게 엄청 어려워보이진 않습니다! (희망적)

물론 이걸 이해하기 위해 앞에서 많은 시간들 할애해 다양한 것들을 배워야합니다. 갈로아필드라든지 페르마 정리 라든지 등등.

 

평문은 집어넣는거 부터 생각을 해보겠습니다. 평문 P가 C로 암호화가 됩니다. 이때 수신자의 공개키와 n을 이용해 암호화를 합니다. 암호문 Cipher text 를 보냅니다. 그럼 수신자는 자신의 비밀키를 통해서 암호문을 복호화시킵니다. 

여기서 n은 p x q 입니다. n이 알려진다고 해도 ∅(n),오일러 파이 펀션을 알기가 힘들기 때문에 공개키와 비밀키를 알 수가 없습니다(어렵습니다). 공개키와 비밀키의 관계는 ( e * d = 1 mod ∅(n), 오일러파이펀션 ) 입니다. 그니깐 오일러 파이펀션을 알 수 없으니 공개키와 비밀키도 모르게 되겠죠?

 

gcd(∅(n), e ) = 1입니다. 생각해보면 당연한게 서로소가 아니라면 ed mod ∅(n)=0 이 되버릴 겁니다.

 

 

정리를 하자면...

 

1. p,q 는 prime number (서로소 두개 선택합니다.)

2. n = pq  (공개됩니다.)

3. e 는 gcd(∅(n), e) = 1 되는 수 중 하나 선택(공개됩니다.)

4. d = e^ -1 ( mod ∅(n)) (비밀키입니다.)

 

Private = { d, p, q} , Public  = { e, n }

 

 

 

RSA key 를 한 번 만들어 보겠습니다.

1. 프라임 두개 선택 :  p = 17 & q = 11

2. n 계산 : n = p x q = 17 x 11 = 187

3. e 계산 위해 ∅(n) 계산 : ∅(n)=(p - 1)(q - 1) =16 x 10 = 160

4. e 선택 : gdc(e, 160) = 1, 7 선택, e = 1 

5. d 결정 : de = 1 mod 160 그리고 d < 160

d 는 23 , 23 x 7 = 161 = 10 x 160 +1

6. Public key 는 (e , n) = (7, 187)

7. Private key 는 d = 23

 

---

RSA 증명 

---

Exponentiation on RSA 

RSA 에서 지수승을 효율적으로 계산하는 방법에 대해 알아보겠습니다. 위에서 말했듯이 RSA 의 비밀성을 높이기 위해선 숫자들이 적어도 1024비트 굉장히 큽니다. 그리니 이를 빨리 계산하는 방식이 필요합니다. 

우리에겐 Square and Multiply Algorithm  이 있습니다!

즉 제곱과 곱셈 알고리즘입니다. 

지수승에 있어 빠르고 효과적인 알고리즘이고 기본적 컨셉은 반복되는 제곱에 기초합니다. 

이해하기 어려울 수 있습니다만 예를 보면 바로 이해 될 겁니다!

 

ex)

 

7^5 = 7^4 x 7 = 3 x 7 = 10 mod 11

어떻게 7^4 가 3이 되냐면요.

1. 7 ^ 4 = (7^2)^2 이고

2. 7 x 7 = 5 mod 11 입니다. 

3. 5 x 5 = 3 이니깐 

4. 7 ^ 4 = 3입니다.

 

제곱을 계속 쪼개는 겁니다. 

 

똑같은 방식으로 

3^129 = 3^128 x 3 = 5 x 3 = 4 mod 11

입니다. 엄청 크고 번잡한 지수승 계산을 빠르게 할 수 있습니다. ( O(log2 N) 의 복잡도를 가집니다) 

 

그러면 이진수를 사용하여 계산하는 법을 알아보겠습니다. 

 

a^b mod n 을 계산해보겠습니다. 여기서 b 가 이진수로 표현 됩니다.

a^b mod n
b 이진수로 표현 -> bk bk-1 ... b0

c <- 0; f <- 1;
for i <- k down to 0
 //무조건 실행되는 부분
 do c <- 2 x c
  f <- (f x f) mod n
  //여기까지
  	if bi = 1 then, c <- c+1, f <- (fxa) mod n
  return f

 

식만 보면 어려우니깐 예를 들어보겠습니다.

그럼 반복문을 따라가보겠습니다. b를 이진수로 표현했을때 10자리 수니깐(9 ~0) k 는 9입니다.

그러면 반복문을 10번 돌리겠죠.

 

-b9은 1입니다.

c <-2 x c ,여기서 c는 0입니다.

f 가 제곱됩니다.

근데 f는 1이기 때문에 1 x 1 =1 입니다.

if 문을 보니 조건에 만족하니 c = c+1 = 2 고 f <- f x a mod n = 1 x 7 = 7 입니다. 

 

-b8는  0입니다. 

c<-2 x c  = 2 x 1, c는 2입니다.

f 가 제곱됩니다.

f는 7이기 때문에 7 x 7 =49 mod 561 입니다.

if 문을 보니 조건에 만족하지 않습니다. 

 

-b7는  0입니다.

c<-2 x c  = 2 x 2, c는 4입니다.

f 가 제곱됩니다.

f는 49이기 때문에 49 x 49 =157 mod 561 입니다.

if 문을 보니 조건에 만족하지 않습니다.

 

-b6는  0입니다.

c<-2 x c  = 2 x 4, c는 8입니다.

f 가 제곱됩니다.

f는 157이기 때문에 157 x 157 = 526 mod 561 입니다.

if 문을 보니 조건에 만족하지 않습니다.

 

-b5는  1입니다.

c<-2 x c  = 2 x 8, c는 16입니다.

f 가 제곱됩니다.

f는 526이기 때문에 526 x 526 = 103 mod 561 입니다.

if 문을 보니 조건에 만족합니다. c <- c+1 = 16 + 1 = 17 입니다. 

f <- f x a = 103 x 7 = 160 mod 561 입니다.

 

이렇게 반복문을 따라가면 됩니다.

---

효율적인 암호화

암호화에는 e의 지수승을 사용합니다. 

그러므로 e가 작으면 계산이 빨라집니다. 

종종 e = 65537(2^16 +1) 를 선택합니다. 

2^16 + 1의 이진수는 1 이 몇개 일까요? 1000 0000 0000 0001 이렇게 2개입니다. 

1이면 계산이 더 많아지기 때문에 1이 적어야 계산이 빠르기 때문에 e = 65537 로 선택한 것입니다. 

그렇다고 2^1 +1 = 3 이나 2 ^ 4 = 16 +1 = 17 등을 선택하면 안됩니다. 숫자가 작아서 금방 어택을 당할 수 있기 때문입니다. 또 gcd( e,  ∅(n)) = 1 이어야 합니다. 

 

 

효율적인 복호화

복호화에는 d의 지수승을 사용합니다. 

이 경우 중국인의 나머지 정리 (CRT)를 사용해서 p&q mod 를 빠르게 분할해서 계산할 수 있습니다. 오직 이용자만이 p와 q의 값을 알기 때문에 효율적으로 이 계산을 할 수 있습니다.  CRT를 계산하는게 그냥 계산했을때보다 3,4배 빠르다고 합니다. 

 

즉 속도가 빨라지기 위해선

- 작은 공개 e 

- CRT 

가 있겠습니다. 

 

---

Attacks on RSA 

 

-Factorization : n = p x q 알아내기

-chosen-ciphertext : 공격자가 암호문과 복호화된 평문을 없는거 

    Optimal Asymmetric Encryption Padding(OAEP) 로 방지 

-Encryption exponent

-Decryption exponent

-Plaintext

-Modulus

-Implementation : 하드웨어 구현에서 타이밍과 소비전력의 차이를 이용해 1, 0 을 구분해서 알아냄

 

 

-OAEP 로 난수 r를 통해 평문을 변환시키고 이 변환시킨 평문을 암호화 -> CCA 방지 할 수 있음