[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

Efficiency

1. Encryption

- e의 크기가 작을 경우, 더 빠르게 암호화를 수행할 수 있음

- e의 크기가 너무 작을 경우, 암호해독이 가능할 수 있음

2. Decryption

- d의 크기가 커야 더 안전함

- d의 크기가 크기 때문에 느려질 수 있지만, CRT(Chinise Remainder Theorem)을 사용하여 좀 더 빠르게 계산할 수 있음

Security

1.brute force key search

- 키 길이가 크기 때문에 불가능

2. mathematical attacks

- n을 factorization하기 어렵기때문에 불가능

3. Timing Attack

- 계산 속도 차이를 이용하여 암호 해독을 수행하는 방법

-> 일정한 계산 속도를 유지하게 함

-> random delay 추가