지침
중동에서 만들어진 고대 암호 체계인 아핀 암호를 구현해 봐요.
아핀 암호는 단일 문자 치환 암호의 한 종류예요.
각 문자는 그에 대응하는 숫자로 바뀌고, 수학 함수로 암호화된 다음, 새로운 숫자 값에 해당하는 문자로 변환돼요.
모든 단일 문자 치환 암호가 약하기는 하지만, 아핀 암호는 훨씬 많은 키를 가지기 때문에 아트바시 암호보다 훨씬 강력해요.
암호화
암호화 함수는 다음과 같아요:
E(x) = (ai + b) mod m
여기서:
-
i는 알파벳 길이에서 1을 뺀 값까지의 범위에서 0부터 시작하는 문자의 인덱스예요.
-
m은 알파벳의 길이예요.
로마자 알파벳에서 m은 26이에요.
-
a와 b는 암호화 키를 이루는 정수예요.
자동 복호화가 성공하려면 a와 m이 서로소(또는 서로소 관계)여야 해요. 즉, 두 수의 공약수가 1뿐이어야 하죠(자세한 내용은 서로소 정수에 관한 위키백과 문서에서 볼 수 있어요).
a가 m과 서로소가 아니면, 프로그램은 이것이 오류임을 알려야 해요.
그렇지 않으면 주어진 키로 암호화하거나 복호화해야 해요.
이 연습 문제에서는 숫자도 유효한 입력이지만 암호화되지는 않아요.
공백과 문장 부호 문자는 제외해요.
암호문은 고정된 길이의 묶음으로 나누어 쓰고, 각 묶음은 공백으로 구분해요. 전통적인 묶음 크기는 문자 5개예요.
이렇게 하면 단어 경계를 기준으로 암호문을 추측하기가 더 어려워져요.
복호화
복호화 함수는 다음과 같아요:
D(y) = (a^-1)(y - b) mod m
여기서:
-
y는 암호화된 문자의 숫자 값, 즉 y = E(x)예요
-
a^-1은 a mod m의 모듈러 곱셈 역원(MMI)이라는 점이 중요해요
- 모듈러 곱셈 역원은
a와 m이 서로소일 때만 존재해요.
a의 MMI는 ax를 m으로 나눈 나머지가 1이 되는 x예요:
ax mod m = 1
모듈러 곱셈 역원을 구하는 방법과 그 의미에 대한 더 많은 정보는 관련 위키백과 문서에서 찾을 수 있어요.
일반적인 예시
- 키
a = 5, b = 7로 "test"를 암호화하면 "ybty"가 나와요
- 키
a = 5, b = 7로 "ybty"를 복호화하면 "test"가 나와요
- 잘못된 키
a = 11, b = 7로 "ybty"를 복호화하면 "lqul"이 나와요
- 키
a = 19, b = 13로 "kqlfd jzvgy tpaet icdhm rtwly kqlon ubstx"를 복호화하면 "thequickbrownfoxjumpsoverthelazydog"가 나와요
- 키
a = 18, b = 13으로 "test"를 암호화하면 18과 26이 서로소가 아니기 때문에 오류예요
모듈러 곱셈 역원(MMI)을 구하는 예시
a = 15의 MMI 구하기:
(15 * x) mod 26 = 1-
(15 * 7) mod 26 = 1, 즉 105 mod 26 = 1
-
7은 15 mod 26의 MMI예요
