비대칭키 알고리즘, RSA

개발 과정에서 RSA 암호화 방식이 자주 등장하는데, 원리에 대한 이해를 하고 사용하고자 공부한 내용을 적습니다.

비대칭키

암호화에 사용하는 키와 복호화에 사용하는 키가 다른 암호화 방식

대칭키 암호화 방식은 암호화에 사용하는 키와 복호화에 사용하는 키가 동일합니다.

공개키 암호화(public key cryptography)

비대칭키 기반의 암호화 방식으로, 암호화키와 복호화키가 분리된다.

원칙

1. 암호화키, 복호화키는 같은 사람의 키쌍이어야 한다.
2. 키는 암호화 복호화 중 한 번만 사용해야 한다.
3. 암호화 복호화에 다른 사람의 개인키는 사용할 수 없다.

송신자 암호화수신자 복호화사용

송신자의 개인키	송신자의 공개키	인증, 부인방지(전자 서명)
송신자의 개인키	송신자의 개인키	X - 3원칙 위배
수신자의 개인키	수신자의 공개키	X - 3원칙 위배
수신자의 공개키	수신자의 개인키	기밀성(email)

구조

수신자의 키쌍으로 암/복호화

암호화에 public key(공개키)를 복호화에 private key(개인키)를 사용

누구나 공개키를 통해 암호화를 할 수 있지만, 개인키를 가진 수신자만이 문서를 볼 수 있다.

1. bob측에서 public/private key(키쌍) 생성
2. public key는 키 분배 채널을 통해 분배
3. alice측에서 public key로 평문을 암호문으로 암호화
4. 암호문을 bob측에 전송
5. bob측에서 private key로 암호문을 평문으로 복호화

RSA

공개키 암호화 알고리즘의 한 종류

공개키 암호화는 하나의 추상화된 개념이며, RSA는 추상화된 개념을 구현한 알고리즘

키 생성 알고리즘

1. 서로 다른 두 소수 p, g를 선택한다.
2. N=p*q
3. K=(p-1)*(q-1)
4. K와 최대공약수가 1인 수(서로소인 수) e(1 < e < K)를 찾는다.
5. e*d를 K로 나눈 나머지가 1이 되는 d를 찾는다.
6. N과 e를 공개한다(공개키)
7. d는 키 생성자가 보관한다(개인키)

예시

1. p = 7, q = 13
2. N = 7 * 13 = 91
3. K = (7-1) * (13-1) = 72
4. K와 서로소인 수 e = 5, 7, 11... 11 선택
5. 11*d % 72 = 1인 d = 57, 131... 57 선택
6. 공개키: [ N, e ] = [ 91, 11 ]
7. 개인키: [ N, d] = [ 91, 57 ]

암/복호화

• 평문: P
• 암호문: C
• 공개키: [ N, e ]
• 개인키: [ N, d ]

암호문 생성: C = P^e mod N

평문 생성: P = C^d mod N

안전성

RSA 암호화는 일정한 수의 소인수분해 수를 알기 어렵다는 것에 기반한다.

공개키 [ N, d ]로 부터 비밀키 d를 알아내면 RSA는 뚫린다. 다만 여기서 N으로 부터 K를 구하면 d를 쉽게 알 수 있다. 따라서, RSA 암호화의 안전성은 p, q를 선택하는 것에 있다.

안전을 위해 소수 p, q의 크기는 512비트의 수로 권장한다.