시저 암호 · Shift Cipher
고전 암호
각 알파벳을 오른쪽으로 k 칸씩 밀면 시저 암호가 된다. 간단한 덧셈 연산이지만 알파벳이 26개뿐이므로 모든 k를 시도(brute force)하면 금방 풀린다.
edit평문
lock암호문
암호화 E(x) = (x + k) mod 26
복호화 D(y) = (y − k) mod 26
key키워드
edit평문
lock암호문
암호화 Ci = (Pi + Ki mod m) mod 26 · m = 키워드 길이
복호화 Pi = (Ci − Ki mod m) mod 26
소수 p
소수 q
공개 지수 e
n = p · q
3233
φ(n) = (p−1)(q−1)
3120
비밀 지수 d
2753
1키 생성
n = p · q, φ = (p−1)(q−1)
두 소수 p, q를 고르고 n과 φ(n)을 계산. e는 gcd(e, φ)=1 인 수.
2비밀키 d
d ≡ e−1 (mod φ)
확장 유클리드 알고리즘으로 e의 역원을 구한다. e·d ≡ 1 (mod φ).
3암호화·복호화
C = Me mod n, M = Cd mod n
평문 M을 e제곱 하고 n으로 나눈 나머지가 암호문 C. 다시 d제곱 하면 원래 M이 돌아온다.
edit평문
| 문자 | M | Me mod n | Cd mod n | 복호 |
|---|
오일러 정리: gcd(M, n)=1 이면 Mφ(n) ≡ 1 (mod n). 따라서 Me·d = Mkφ+1 ≡ M (mod n).