지침
고대 중동에서 만들어진 암호 체계인 아핀 암호를 구현해 보세요.
아핀 암호는 단일 문자 치환 암호의 한 종류예요.
각 문자는 해당하는 숫자로 대응되고, 수학 함수로 암호화된 다음, 새로운 숫자 값에 해당하는 문자로 변환돼요.
모든 단일 문자 치환 암호는 취약하지만, 아핀 암호는 키가 훨씬 많기 때문에 아트바시 암호보다 훨씬 강력해요.
암호화
암호화 함수는 다음과 같아요:
E(x) = (ai + b) mod m
여기서:
-
i는 0부터 알파벳 길이에서 1을 뺀 값까지의 문자 인덱스예요.
-
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예요.
