RSA 알고리즘 요약

학부시절에 공부했던 자료들을 보다 보니 생각나서 요약해서 올려봅니다.

[RSA 개요]

1977년에 MIT에서 Ron Rivest, Adi Shamir, Leonard Adleman에 의해 개발된 암호화 알고리즘으로, RSA라는 말은 이들 이름의 앞 글자를 딴 것입니다. 기본 원리는, 큰 수를 확정적으로 소인수분해를 하기 어렵다는 사실을 이용한 방식입니다. 

현재는 RSA-2048~4096정도의 강도를 가진 RSA암호화가 주로 사용됩니다.

[사용 용도] 

1. 정보의 암호화(공개키로 암호화한뒤 개인키로 암호 해제) - SSL, PGP, 공공기관, 쇼핑몰 등

2. 공인인증서 등 공개서명(개인키로 암호화안 뒤 공개키로 암호 해제) - 이 방법은 상대방을 '인증'하기 위한 방식으로, 개인키로 암호화한 정보를 전달하면 해당 정보를 전달한 사람이 해당인인을 확실히 알 수 있습니다.

[RSA 암호화 과정]

1. 두 소수 p, q를 찾는 것 - 큰 임의의 홀수 2개를 찾은 뒤 2씩 더해가면서 소수를 찾는 방식을 사용하며, p, q는 가능하면 비슷한 크기로 한다.

2. n 구하기 - n = p * q

3. ϕ(n)구하기, p, q가 소인수라 ϕ(n) = (p-1)(q-1)

참고(오일러 파이 함수) : https://namu.wiki/w/%EC%98%A4%EC%9D%BC%EB%9F%AC%20%ED%8C%8C%EC%9D%B4%20%ED%95%A8%EC%88%98

4. e 구하기, e = 1 < e < ϕ(n)이며 ϕ(n)과 서로소인 수, e는 공개키에 사용되는 수입니다.

5. d 구하기, (e * d)modϕ(n) = 1인 숫자, d 는 개인키에 사용되는 수입니다.

6. 공개키(n, e), 개인키(n, d)설정

7. RSA 암호화 및 복호화 방법

원래 정보를 A, 암호화된 정보를 B라고 할 경우

RSA암호화 - B = A^e mod n

RSA복호화 - A = B^d mod n

[공격방법]

1. 소인수분해 방법 - 말 그대로 공개키 등 드러난 정보를 가지고 n에서 p, q를 계산하는 방식, 매우 오랜 시간이 소요됩니다.

2. 선택 암호문 공격 - 임의의 데이터 송신 시 암호문으로 간주하고 회신해주는 복호 오라클 서비스의 취약점을 이용한 방식

3. Side-Channel Attack(부채널 공격) - Timing Attack, Power Analysis등, 복호화 연산에 소모되는 시간, 전력량 등을 통해 암호화정도를 유추해서 해킹하는 방식