1977년에 리베스트, 샤미르, 애들먼이 고안한 공개 키 암호. 큰 두 소수 p, q의 곱 n과 공개 지수 e를 공개 키로 하고, e × d ≡ 1 (mod (p − 1)(q − 1))을 만족하는 d를 개인 키로 한다. 암호화는 c = m^e mod n, 복호화는 m = c^d mod n으로 수행한다. n의 소인수분해가 어렵다는 것이 안전성의 근거이며, 암호화와 서명 양쪽에 사용할 수 있다. 실제로는 OAEP나 PSS 같은 난수를 포함하는 패딩과 조합하여 사용한다.
일본어 명칭: RSA暗号
RSA 암호(RSA Cryptosystem)은(는) 암호 기술의 기초와 응용, 양자 컴퓨터의 하드웨어 등 2개 분야의 연습 문제 10개에 나와요.
분야: 암호 기술의 기초와 응용
p = 5, q = 11이면 n = 55, (p − 1)(q − 1) = 40입니다. e = 3으로 하면 3 × 27 = 81 ≡ 1 (mod 40)이므로 d = 27입니다. 평문 m = 7은 7³ = 343 ≡ 13 (mod 55)으로 암호화되고, 13^27 mod 55를 계산하면 7로 돌아갑니다.
NIST SP 800-57의 표에서는 2048비트의 n이 112비트 상당, 3072비트가 128비트 상당의 안전성 기준으로 되어 있습니다. 같은 안전성으로 비교하면 타원 곡선 암호보다 훨씬 긴 키와 서명이 필요하며, 키 생성이나 서명 계산도 무거워집니다. 공개 지수로는 계산이 빨리 끝나는 65537(2^16 + 1)이 자주 쓰입니다.
예전의 TLS에서는 클라이언트가 만든 키 재료를 서버의 RSA 공개 키로 암호화하여 보내는 키 교환이 널리 쓰였지만, 전방향 안전성이 없기 때문에 TLS 1.3에서는 폐지되었습니다. 현재의 RSA 암호는 주로 인증서나 소프트웨어의 서명에 사용되고 있습니다. 대규모 양자 컴퓨터가 실현되면 쇼어 알고리즘으로 깨지므로, 양자 내성 암호로의 이행이 진행되고 있습니다.
정답: B. 27
n = 5 × 11 = 55, φ(n) = 4 × 10 = 40입니다. 3 × d를 40으로 나눈 나머지가 1이 되는 d를 찾으면 3 × 27 = 81 = 2 × 40 + 1이므로 d = 27입니다. 공개 키는 (n, e) = (55, 3), 개인 키는 d = 27이며, p와 q를 모르면 φ(n)을 알 수 없어 d를 구할 수 없다는 것이 안전성의 근거가 됩니다. 실제 RSA 암호에서는 p와 q가 각각 1000비트를 넘는 큰 소수이며, e로는 65537이 자주 쓰입니다.
정답: A. 13
7³ = 343이고, 343 = 6 × 55 + 13이므로 c = 13입니다. 이 공개 키에 대응하는 비밀 지수는 d = 27(p = 5, q = 11, φ(n) = 40이며 3 × 27 ≡ 1)이고, 13^27 mod 55를 계산하면 원래 평문인 7로 돌아갑니다. 암호화는 공개 키만으로 할 수 있지만, 복호화에는 d가 필요합니다.
p와 q를 알면 (p − 1)(q − 1)을 계산할 수 있고, 공개되어 있는 e로부터 d를 구할 수 있기 때문입니다. n은 공개되어 있으므로, 안전성은 n을 소인수분해하는 어려움에 의존하고 있습니다.
RSA 암호로 한 번에 암호화할 수 있는 것은 n보다 작은 수뿐이며, 계산도 대칭 키 암호보다 훨씬 무겁기 때문입니다. 실제로는 파일을 AES 등의 대칭 키 암호로 암호화하고, 그 대칭 키만 공개 키로 보호하는 하이브리드 암호 방식을 사용합니다.
실제 RSA 암호에서는 p와 q가 각각 1000비트를 넘는 큰 소수이며, e로는 65537이 자주 쓰입니다.
RSA 암호의 구조를 작은 수로 확인한다. 소수 p = 5, q = 11로부터 n = pq를 만들고, 공개…교과서 그대로의 RSA 암호는 난수를 사용하지 않는 결정론적 방식이므로, '예', '아니요'처럼 후보가 적은 평문은 공격자가 후보를 모두 공개 키로 암호화하여 암호문과 비교하기만 하면 알아내 버립니다.
교과서 그대로의 RSA 암호(평문 m을 그대로 c = m^e mod n으로 하는 방식)를 패딩을 붙이지 않…NIST SP 800-57 Part 1의 표에서는 128비트 상당의 안전성 기준으로 RSA 암호는 3072비트, 타원 곡선 암호는 256~383비트로 되어 있습니다.
NIST SP 800-57의 표에서 128비트 대칭 키 암호(AES-128)와 같은 정도의 안전성 기준으로…RSA 암호의 안전성은 큰 수의 소인수분해의 어려움에, 타원 곡선 암호는 이산 로그 문제의 어려움에 기반하고 있습니다.
대규모 오류 내성 양자 컴퓨터가 실현되었을 때, 쇼어 알고리즘에 의해 안전성이 크게 손상될 것으로 생각되는…키나 서명의 크기가 RSA 암호나 타원 곡선 암호보다 커지는 것이 많으므로, 통신 프로토콜이나 임베디드 기기, 하드웨어 구현에 대한 영향을 고려하면서 이행을 진행합니다.
양자 내성 암호(포스트 양자 암호, PQC)의 설명으로 올바른 것은?TLS 나머지 연산(Modulo Operation) 타원 곡선 암호(Elliptic Curve Cryptography) 디피-헬먼 키 교환(Diffie-Hellman Key Exchange) 대칭 키 암호(Symmetric-key Cryptography) 쇼어 알고리즘(Shor's Algorithm) AES 양자 내성 암호(Post-Quantum Cryptography) 해시 함수(Hash Function) 전방향 안전성(Forward Secrecy)