RSA

01무엇이고, 어떤 일을 하나

• 공개키와 개인키의 계산 관계를 이용한다.
• 암호화와 전자서명에서 서로 다른 스킴을 사용한다.
• 대칭키 기술과 결합해 큰 데이터 처리와 신원 증명을 분담한다.

02어떤 순서로 동작하나

1. 모듈러스

   서로 다른 소수 p·q로 n=pq를 만들며 공개키는 n·e를 포함한다. p·q를 알면 비밀 지수 계산에 필요한 구조가 드러난다.

2. 역원 조건

   교과서 예에서 gcd(e,φ(n))=1인 e를 고르고 ed≡1 mod φ(n)을 만족하는 d를 사용한다.

3. 입력 범위

   기본 RSA 연산은 0≤m<n인 정수 대표값을 처리한다. 임의 길이 파일을 그대로 한 정수 연산에 넣는 구조가 아니다.

4. 스킴의 역할

   OAEP는 메시지·난수·해시·길이 조건을 인코딩하고, PSS는 서명용 인코딩을 정한다. 두 스킴을 교환해 쓸 수 없다.

5. 키 길이의 한계

   작은 정수는 계산 원리만 설명한다. 실제 안전성은 충분한 강도와 검증된 구현·난수·오류 처리까지 요구한다.

03먼저 알아둘 용어와 구성요소

Modulus n

두 소수의 곱으로 만드는 RSA 연산의 법.

공개 지수 e

공개키에 포함되는 지수.

개인 지수 d

적절한 모듈러 역원 관계를 만족하는 비밀 지수.

OAEP·PSS

각각 RSA 암호화와 서명을 위한 인코딩·검증 스킴.

RSA-OAEP

RSA 암호화에 메시지 길이·난수·해시를 포함한 인코딩을 결합하는 스킴.

RSA-PSS

RSA 서명에 확률적 인코딩을 결합하는 스킴.

φ(n)

서로 다른 소수 p·q의 곱에 대해 (p−1)(q−1)이 되는 오일러 함수 값.

04예제로 따라가기

• 작은 소수: 교육용 p=61, q=53이면 n=3233이고 φ(n)=60×52=3120이다.
• 지수 선택: e=17, d=2753을 쓰면 17×2753=46801=3120×15+1이므로 역원 관계가 성립한다.
• 메시지 변환: m=65를 교과서 식에 넣으면 c=65^17 mod 3233=2790이다.
• 복원 확인: 2790^2753 mod 3233=65로 원래 대표값을 얻는다. 이는 수학식의 확인이지 안전한 파일 암호화 예제가 아니다.
• OAEP와 차이: 실제 OAEP에서는 동일 평문도 인코딩의 난수 때문에 다른 대표값이 될 수 있다. 위 예에는 그 보호가 없다.

05혼동하기 쉬운 점과 확인 기준

• 키 해석: PEM·DER 컨테이너와 실제 알고리즘·키 길이를 확인한다. 확장자만으로 RSA 키인지 인증서인지 판단하지 않는다.
• 스킴 불일치: OAEP 해시·MGF 설정·label이나 PSS 매개변수가 양쪽에서 다르면 같은 키 쌍이어도 검증·복호화가 실패할 수 있다.
• 길이 초과: RSA 암호화의 최대 평문은 모듈러스 바이트 수에서 스킴 오버헤드를 뺀 값이다. 긴 자료는 혼합 암호화 구조로 처리한다.

06상세 노트 · 실습 자료

헤더 구조, 설정 예시, 수치 계산과 수업 캡처는 아래 노트에서 이어집니다.