암호문 두 줄이 각각 그럴듯해도 같은 표로 만들 수 있을까요? CIMT의 치환 암호 활동에서, 같은 글자는 같은 암호 글자로 바꾼다는 조건을 가져와 기록 수선 문제를 만들어 봐요.
대문자 A부터 Z까지를 같은 26글자에 일대일 대응시키는 표 하나를 두 기록에 함께 써요. 서로 다른 원문 글자는 서로 다른 암호 글자로 가요. A를 바꾼 글자를 f(A)라 적어요. 표는 알파벳을 일정하게 미는 방식일 필요가 없고, 어떤 글자는 자기 자신으로 가도 돼요.
확정된 첫 기록은 ABBA→MNNM, 둘째 기록은 ACCA→MNNM입니다. 원문 두 줄과 첫 암호문은 고정해요. 둘째 암호문의 네 위치에서 글자를 바꾸는 것만 허용해요. 삽입·삭제는 없어요. 같은 표를 쓸 수 있도록 최소 몇 위치를 고쳐야 할까요?
첫 기록은 f(A)=M, f(B)=N을 정해요. 둘째 기록을 그대로 두면
공통수학2의 일대일 대응 조건을 어겨요. 두 줄을 따로 검사하면 놓치는 충돌이에요.
한 위치만 고쳐도 둘째 줄의 가운데 두 N 중 하나는 남아요. 따라서 f(C)=N이 여전히 필요해, 첫 기록의 f(B)=N과 충돌해요. 양끝을 고치는 것으로도 이 문제를 없앨 수 없어요.
가운데 두 위치를 모두 P로 바꾸면 ACCA→MPPM이 돼요. A,B,C가 각각 M,N,P로 가므로 충돌이 사라져요. 나머지 23개 원문 글자도 남은 23개 암호 글자에 하나씩 배정하면 전체 표를 완성할 수 있어요. 한 위치로는 불가능하고 두 위치로는 가능하므로 정답은 2입니다.
수선한 네 글자 아래에 바뀐 위치를 표시해 볼까요? “N이라는 글자 한 종류를 P로 바꿨다”와 “두 위치를 고쳤다”는 다른 셈이에요. 실제 통신의 보안성을 판정하는 활동은 아니에요.
착안: CIMT, Codes and Ciphers — Unit1 Substitution Ciphers. 동일 치환표의 알려진 조건만 참고했어요. 두 기록·수선 허용 범위·최소 위치 논증은 자체 작성했으며 원문 표나 암호 메시지를 옮기지 않았어요.