시험 직전 요약장

n을 인수분해해 p·q를 알면 φ(n)과 d를 계산할 수 있다. 그래서 RSA는 소인수분해 기반 공개키 방식으로 분류한다. 하지만 모든 RSA 공격이 반드시 소인수분해부터 해야 한다는 뜻은 아니다. 부적절한 키 생성, 패딩·오류 응답, 키 유출로도 보호가 깨질 수 있다.

원문 정수에 위 식만 적용하는 textbook RSA는 동일 입력에 동일 결과가 나오는 등 안전한 암호화 스킴의 요건을 갖추지 못한다. 실제 RSA 암호화에는 OAEP 같은 검증된 인코딩·패딩 방식이 필요하다. 단순히 빈 공간에 0을 채우는 것이 아니다.

RSA 서명은 별도의 서명 스킴이다. OAEP는 암호화, PSS는 서명에 쓰이는 이름으로 구별하고 상세 인코딩 내부는 필기 핵심 밖으로 확장하지 않는다.

평문을 0 ≤ m < n인 정수로 표현하는 RSA 원시 연산은 다음과 같다.

암호화: c = m^e mod n
복호화: m = c^d mod n

위 키에서 m=42를 암호화한다. 큰 거듭제곱을 한 번에 계산하지 않고 제곱할 때마다 나머지를 구한다.

42^2 mod 221 = 217
42^4 mod 221 = 217^2 mod 221 = 16
42^5 mod 221 = 16 × 42 mod 221 = 9

복호화 지수 77 = 64 + 8 + 4 + 1을 이용한다.

9^77 mod 221
= (35 × 120 × 152 × 9) mod 221
= 42

암호문 9에서 원래 값 42가 복원된다. 이 작은 수는 원리 확인용이며 실제 데이터 보호에 사용할 수 없다.