[Cryptography] Public Key Cryptography - RSA
[Cryptography] Public Key Cryptography - RSA
Public key cryptography
- 두개의 key 사용(public key, private key)
- 비대칭키(asymmetric system)
- 키 배포가 필요없어 대칭키 시스템의 문제 해결
- Digital Signatures에 사용
Key
1. Public key
- message를 암호화하는데 사용
- 전자서명에서는 signature를 검증하기 위해 사용
2. Private Key
- message를 복호화하는데 사용
- 전자서명에서는 signature를 생성하기 위해 사용
Encryption/Decryption
1. Encryption
- 수신자의 공개키를 이용하여 암호화하고 Ciphertext를 전송
2. Decryption
- Ciphertext를 받은 수신자는 본인의 개인키를 이용하여 복호화하여 plaintext 추출
Requirements
1. Decryption key를 찾는 것을 불가능하게 해야한다.
- Encryption key와 algorithm은 공개
2. trapdoor one-way function
- k와 X를 알고 있을 때, Y = fk(X) 는 쉬워야 한다.
- k와 Y를 알고 있을 때, X = fk^-1(Y)는 쉬워야 한다.
- Y만 알고 있을 때, X = fk^-1(Y)는 불가능해야 한다.
Security
- 키 길이를 크게 하여 exhaustive search(키 소진 공격)에 더 안전하게 해야함
-> 대신, 키 길이가 크면 속도가 더 느림
RSA
- public key scheme 중 가장 많이 알려지고 사용된 system
- IFP(Integer Factorization Problem, 소인수분해 문제)에 기반을 두고 설계
- 1024bit의 키 사용
Key Setup
1. 큰 소수 p,q 선택
2. n, tot(n) 계산
- n = p*q
- tot(n) = (p-1)*(q-1) (euler's function)
3. e 선택
- gcd(e, tot(n)) = 1, 1 < e < tot(n) 중에 선택
4. d 계산
- e*d mod tot(n) = 1 인 d 계산(0 <= d <= n)
5. Public key, Private key
- PU = {e,n}
- PR = {d,n}
Ex) p =17, q = 11
1. n, tot(n) 계산
- n = 17*11 = 187
- tot(n) = 16*10 = 160
2. e 선택
- gcd(e, 160) = 1, e = 3
3. d 계산
- e*d mod 160 = 1 -> d = 107
4. Public key, Private key
- PU = {3, 187}
- PR = {107, 187}
Encryption/Decryption
1. Encryption
- public key : PU = {e, n}
- C = M^e mod n (0 <= M < n)
-> M이 n보다 작아야 함(block)
2. Decryption
- private key : PR = {d, n}
- M = C^d mod n