RSA
공개키 암호 시스템
만든 사람
로널드 라이베스트, 아디 샤미르, 레너드 애들먼
그래서 RSA임(라이베스트, 샤미르, 애들먼)
이거 만들어서 2002년 튜링상 수상함.
원리
큰 숫자를 소인수 분해하는 것이 어렵다.
근데 1993년 피터 쇼어의 쇼어 알고리즘은 양자 컴퓨터를 이용하여 임의의 정수를 다항 시간 안에 소인수 분해하는 법을 발표함.
즉, 양자 컴퓨터로 RSA 알고리즘 무용지물 됨.
다항 시간?
입력 크기 n에 대해 최악의 경우 n^k
반대로 비디항 시간(지수 시간)은 2^k 형태
방식
두 개의 키를 사용함.
여기서 키는 상수임.
공개키로 암호화를 하고, 개인키로 복호화를 한다.
즉, 암호화는 누구나 할 수 있지만 복호화는 해당 공개키와 연결된 개인키를 가지고 있는 사람만 가능하다.
표준 방식
- 메시지 서명
- 메시지의 해시 값을 A의 개인키로 암호화해서 디지털 서명 생성
- 이 서명은 메시지가 A에 의해서 작성되었고 변조가 없음을 보증
- 메시지 암호화
- A는 B의 공개키로 디지털 서명을 포함하여 전제 메시지를 암호화
- 이 암호화된 메시지를 B에게 전송
- 메시지 복호화
- B는 자신의 개인키로 메시지 복호화(메시지 기밀성 보장)
- B는 복호화된 메시지 내에서 A의 공개키로 디지털 서명 검증(무결성, 인증)
예시
1. 키 생성
공개키는 n, e
개인키는 n, d
2. n 구하기
두 소수 p, q를 곱한 값을 n이라고 함.
3. e 구하기(공개키 생성)
ϕ(n) = (p-1) x (q-1)
(n이 두 수소 p, q의 곱일 때, 1부터 n 사이에서 n과 서로소인 정수의 개수)
1 < e < ϕ(n)
ϕ(n)과 서로소인 e를 정한다.
4. d 구하기(개인키 생성)
(e x d) mod ϕ(n) = 1
-> e×d+φ(n)×k=1
5. 암호화
C: 암호화 메시지
M: 원본 메시지
C = M^e mod n
6. 복호화
M = C^d mod n
(페르마의 소정리)
