Affine cipher(아핀 암호)
아핀암호는 고전적인 대치 암호 중 하나로, 각 문자를 수학적으로 변환하여 암호화하는 방식입니다. 이 암호는 단순하면서도 수학적인 원리를 기반으로 한다.
1. 개요
Affine Cipher는 알파벳의 각 문자를 수학적인 함수를 이용해 치환한다. 기본적으로 다음과 같은 함수를 사용한다.
암호화 공식
x : 평문 문자를 0부터 m-1까지 숫자로 변환한 값
a : 키 값 중 하나 (곱셈키)
b : 키 값 중 하나 (덧셈키)
m : 문자의 수 ( 영어의 경우 26 )
E(x) : 암호문 문자에 해당하는 숫자
복호화 공식
y : 암호문 문자 숫자
a^-1 : a의 mod m에 대한 곱셈 역원
2. 예시
Step 1.
만약 a = 5, b = 8, m= 26일 경우
예시 : HELLO -> H = 7, E = 4, L = 11, O = 14
Step 2.
공식에 따라
H(7) = ( 5 7 + 8 ) mod 26 = 43 mod 26 = 17 -> R
E(4) = ( 5 4 + 8 ) mod 26 = 28 mod 26 = 2 -> C
L(11) = ( 5 11 + 8 ) mod 26 = 63 mod 26 = 11 -> L
L(11) = ( 5 11 + 8 ) mod 26 = 63 mod 26 = 11 -> L
O(14) = ( 5 * 14 + 8 ) mod 26 = 78 mod 26 = 0 -> A
암호문 : "RCLLA"
3. 키 조건
a(key1)는 m과 서로소여야 한다.
그래야 a의 역원이 존재하기 때문에 복호화가 가능해진다.
예를 들어 m이 26이라면
가능한 a는 1, 3, 5, 7, .... 25 가 있다.
4. 곱셈(모듈러) 역원
복호화 공식에서 a^-1은 mod m에 대한 곱셈 역원이다.
즉 a*a^-1 ≡ 1 mod m 을 만족하는 a^-1이 존재한다면 그걸 a의 역원이라고 한다.
즉 5 * inv ≡ 1 mod 26 을 만족하는 inv를 찾아야 한다.
하나씩 대입해보면 inv = 21 일 때 1 mod 26을 만족한다.
복호화에는 a^-1 이 필요하다.
5 * 21 = 105 ≡ 1 mod 26
a^-1 = 21
5. 복호화
암호문 : "RCLLA"
복호화
D(17) = 21(17 - 8) mod 26 = 7 -> H
D(2) = 21(2 - 8) mod 26 = -126 mod 26 = 4 -> E
- -126 = (-5) * 26 + r -> -130 + r -> r = 4
D(11) = 21(11 - 8) mod 26 = 63 mod 26 = 11 -> L
D(11) = L
D(0) = 21(0 - 8) mod 26 = -168 mod 26 = 14 -> O
- -168 = (-7) * 26 + r = -182 + r -> r = 14
평문 : "HELLO"
6. 보안성과 한계
간단한 구조로 인해 빈도 분석 공격에 취약하다.
총 가능한 키의 수는 ϕ(m) × m 개 이다.
보안이 매우 낮기 때문에 현대에서는 학습용이나 퍼즐 등에만 사용된다.
ETC.
-
ϕ(m) × m은 무엇일까?
ϕ(m)은 오일러의 토션트 함수이다.ϕ(m)은 1부터 m-1까지의 정수 중에 m과 서로소인 수의 개수를 의미한다.
따라서 m은 b의 개수를 의미하며
ϕ(m)은 a의 개수를 의미한다. ( m과 서로소 인 수의 개수 )알파벳 기준으로 최대 312개가 가능하다.
워게임 문제 및 풀이 ( Affe!n )
오늘 풀 문제는 Affe!n이다.
Affein으로 암호화된 암호문이 주어진다. 그리고 암호화 및 복호화 코드가 주어진다.
정리해보면 우리가 가진 정보는
- 복호화 코드
- 암호화 코드
- 암호문
이다.
알아내야할 정보는 바로 Key1 과 Key2이다.
암호화 당시 사용한 키 값을 알지 못한다.
m은 251이다.
즉 우리가 고려해야할 조건은 다음과 같다.
- Key1은 251과 서로소이다.
- 평문에는 cryptography라는 단어가 포함되어 있다.
- Key2는 1~250까지의 값이 가능하다.
문제에서 주어진 암호화와 복호화 코드는 그대로 사용하고, 가장먼저 키를 찾는 과정을 추가로 작성하였다. 키는 브루트포싱을 이용하였고, 서로소임을 검증하는 것은 math라이브러리의 gcd 함수를 이용하였다.
그리고 key1값이 정해지면 key2값을 반복문을 통해 돌며, 복호화를 진행하였다. 복호화된 바이트 데이터에 cryptography라는 값을 포함하고 있다면 데이터를 출력한다.
또한 우리에게 주어진 암호문은 hex데이터 이므로 바이트로 포맷을 변경한 후에 복호화를 진행하였다.
Found keys! key1=79, key2=87
Decrypted message:
b"The affine cipher is a type of monoalphabetic substitution cipher used in cryptography. It is a simple and ancient method of encrypting a message. In this cipher, each letter of the plaintext is first mapped to its numerical equivalent using the position in the alphabet (e.g., A=0, B=1, ..., Z=25). Then, the letter's numerical value is multiplied by a constant 'a' and then added to
another constant 'b.' The result is taken modulo 26 to obtain the corresponding ciphertext letter. The constants 'a' and 'b' are
the keys of the cipher and are carefully chosen to ensure the encryption and decryption processes can be correctly reversed. The
affine cipher provides a limited level of security and can be easily broken using frequency analysis if the key is not well chosen. However, with appropriate key selection, it can serve as a basic method of encryption in educational or recreational settings.
Now, here comes the flag- DH{3fcd60d46ff03b6fcd3a6d4c71805b131f8f48af5ffdf4fb4b9ab7cf5a09a4ef}"
복호화 결과는 위와 같다.
Key1 = 79, Key2 = 87 이다.
FLAG : DH{3fcd60d46ff03b6fcd3a6d4c71805b131f8f48af5ffdf4fb4b9ab7cf5a09a4ef}
