RSA Encryption

비대칭 암호 #

송신자와 수신자 모두 자신의 공개키와 개인키 한 쌍으로 가지고 있어야 한다.

공개키는 그냥 공개되어 있음.

암호화 과정 #

Alice는 Bob의 공개키 (B+)로 암호화

• 개인키 (B-)가 없는 사람들은 복호화하지 못하도록 Bob은 자신의 개인키로 복호화

전자서명 과정 #

1. Alice는 자신의 개인키(A-)로 암호화 (sign, 서명)
2. 수신자는 Alice의 공개키로 Alice의 서명임을 증명/확인.

RSA #

아주 큰 소수 p, q를 설정해 N = p*q로 아주 쉽지만 N에서 p, q를 구하는 것은 매우 어렵다.

용어 정리 #

• Public Key: K+ = (N, e)

• Private key: K- = d

• 암호화: C = Ek+(x) = M^e mod N

• 복호화: M = Dk-(y) = C^d mod N

키 생성 #

1. 서로 다른 큰 소수 p와 q를 선택한다.
2. p와 q를 곱해 N을 계산한다.
3. phi(N) = (p - 1)(q - 1)
4. e ∈ {1, 2, 3 … phi(N)} 중 gcd(e, phi(N)) = 1을 만족시키는 e를 구한다.
5. d * e mod phi(N) = 1을 만조시키는 d를 구한다.

예시 #

1. p = 11, q = 3
2. N = pq = 33
3. phi(N) = (p-1)(q-1) = 20
4. phi(N)과 서로소인 수 찾기
5. d * 3 mod 20 = 1 성립하는 d 찾기 d * 3 = 21, d = 7

특징 정리 #

• DES, AES보다 긴 시간 소요

• 복호화 시간 > 암호화 시간