Public Key Cryptography, RSA

암호기술 큰틀

• 대칭키 암호(Symmetric key cryptography)
  • Block Cipher
  • Stream Cipher
• 비대칭 암호
  • Public-key Cryptography(공개 키 암호학)
  • Digital Signature

 

공개키 암호학

- 2개의 key가 존재 public key private key

A에게 전송할 때는 공개된 A의 public key를 사용하여 암호화, 전송

A는 수신한 내용을 A 자신의 private key를 사용하여 복호화

   -> 반대의 경우는 '서명' signature 을 위한 경우

 

 

- trap door one way function: 개구멍 있는 일방통행

개구멍(private key)을 아는 사람만 볼 수 있도록 하는 방법

 

RSA(Rivest, Shamir, Adelman)

사용된 난제: Large prime number factorization

 

준비

1. 큰 소수 p, q를 준비, N = pq                                                      ex) p = 11, q = 3
2. 암호화를 위한 ϕ(pq) = (p-1)(q-1) 와 서로소인 작은수 e 선택   ex) p-1 * q-1 = 20, e = 3(20 과 서로소인 수)
3. ed = 1 mod (p-1)(q-1)을 만족하는 d를 선택                             ex) 3*7 = 1 mod 20, d = 7
4. public key = (N,e), private key = d                                            ex) (N,e) = (33,3), d = 7

 

C = M^e mod N => 암호화

M = C^d mod N => 복호화

 

증명:

오일러 공식: x가 prime 이면 x^ϕ(n) = 1 mod n