백준16611🐨Kleptography.py (Autokey Cipher)
https://blog.naver.com/sepaper/221801268480
Autokey Cipher, Vernam Cipher, One-Time Pad
기존 암호의 취약점 단일문자 암호는 평문의 한 문자는 치환될 때 항상 같은 한 문자로만 치환되어서 평문...
blog.naver.com
https://www.acmicpc.net/problem/16611
--- ---
AutoKey 암호는 고전 암호화 방식 중 하나로, 평문(원래의 메시지)을 암호화하기 위해 키(key)를 사용하는 암호 기법이다. 일반적인 비즈네르(Vigenère) 암호와 유사하지만, AutoKey 암호에서는 평문의 일부가 키로 사용된다는 점에서 차이가 있다.
AutoKey 암호의 작동 방식
- 키 생성:
- 초기 키는 일반적으로 짧은 단어 또는 구문으로 시작된다.
- 평문의 첫 부분은 이 초기 키로 암호화되지만, 그 이후에는 평문의 일부가 키로 사용된다. 예를 들어, 초기 키가 "KEY"이고 평문이 "HELLO"라면, 첫 번째 키는 "KEY"이고 그 다음에는 암호화된 평문의 "H"가 키의 일부로 사용된다.
- 암호화 과정:
- 각 문자는 Vigenère 암호화 방식처럼 평문의 각 문자와 키의 해당 문자를 결합하여 암호화된다. 이 과정에서 평문 문자와 키 문자를 알파벳 순서로 더하여 암호문을 생성한다.
- 예를 들어, 평문이 "HELLO"이고 키가 "KEYHE"라면, 각 문자가 다음과 같이 암호화된다.
- H + K → R
- E + E → I
- L + Y → J
- L + H → S
- O + E → S
- 따라서 암호문은 "RIJSS"가 된다.
- 복호화 과정:
- 복호화는 암호화 과정의 역순이다. 암호문과 초기 키를 사용해 평문을 하나씩 복원하고, 복원된 평문 문자는 다음 복호화를 위한 키로 사용된다.
- 예를 들어, 암호문 "RIJSS"와 초기 키 "KEY"를 사용하여 복호화를 진행하면 다음과 같다:
- R - K → H
- I - E → E
- J - Y → L
- S - H → L
- S - E → O
- 따라서 평문은 "HELLO"가 된다.
특징 및 장점
- 평문 자체가 키로 사용되기 때문에 키의 길이가 평문과 동일하게 늘어나게 된다. 이는 같은 키를 반복적으로 사용하는 비즈네르 암호보다 더 안전하다고 할 수 있다.
- 하지만 키의 일부가 평문과 연관되어 있기 때문에, 만약 공격자가 키의 일부분이나 평문을 알고 있다면, 복호화가 더 쉬워질 수 있는 단점도 존재한다.
AutoKey 암호는 고전 암호로서 현대 암호화 기술에 비해 보안성이 떨어지지만, 고전 암호화 방법을 이해하고 학습하는 데 유용하다.
만약 마지막 글자의 평문을 안다면?
AutoKey 암호에서 마지막 글자의 평문을 알고 있다면, 이를 이용해 이전 평문을 역으로 추측할 수 있다. 이 과정은 복호화와 유사하게 작동하며, 특정 조건에서는 전체 평문을 추론할 수 있다. 이를 설명하기 위해 예시를 들어보겠다.
예시:
암호문이 "RIJSS"이고, 마지막 평문이 "O"라는 것을 알고 있다고 가정해보자. 초기 키는 "KEY"이다.
단계 1: 마지막 평문을 이용한 복호화
- 마지막 암호문 문자 "S"와 마지막 평문 문자 "O"를 사용하여 키의 마지막 문자를 찾을 수 있다.
- S - O = E (알파벳에서 'S’의 위치에서 'O’의 위치를 빼면 'E’가 나온다.)
단계 2: 이전 평문 복원
- 마지막 평문이 "O"였다는 정보를 이용하여, 이제 앞서 나온 문자들을 복호화할 수 있다.
- 두 번째 마지막 암호문 "S"에서 "E"를 빼면 평문 문자 "L"이 복원된다.
- 이렇게 복원된 평문 문자 "L"은 이제 이전 암호문을 복호화하기 위한 키로 사용된다.
단계 3: 이어지는 복호화
이 과정을 반복하면서, 전체 평문을 역으로 복원할 수 있다.
- “J” - “L” = “L”
- “I” - “E” = “E”
- “R” - “K” = “H”
결과:
복호화 과정을 통해 복원된 평문은 "HELLO"이다.
요약:
마지막 평문 문자와 암호문을 알고 있는 경우, AutoKey 암호의 구조상 역으로 키를 복원하고 이전 평문을 추측할 수 있다. 이는 AutoKey 암호의 잠재적 취약점 중 하나로, 특히 초기 키를 알고 있거나 일부 평문이 유추 가능한 상황에서는 전체 평문이 쉽게 노출될 수 있다.
따라서, AutoKey 암호는 현대의 보안 요구를 만족하기에는 충분하지 않으며, 특히 알려진 평문 공격에 취약하다. 이러한 이유로 현대 암호화 알고리즘에서는 더 강력한 키 관리 및 암호화 방법을 사용하고 있다.
키가 n 글자이고 마지막 n글자를 안다면?
AutoKey 암호에서 키의 길이가 ( n ) 글자이고 마지막 ( n ) 글자의 평문을 알고 있다면, 이 정보를 이용해 전체 평문을 복원할 수 있다. 이 경우, 암호화 과정에서 사용된 키와 평문 간의 관계를 역으로 추적할 수 있기 때문이다.
예시로 설명:
- 초기 정보:
- 암호문: “RIJSS”
- 키: ( n = 3 )글자 (“KEY”)
- 마지막 ( n ) 글자의 평문: “LLO” (즉, 마지막 평문이 "HELLO"에서 "LLO"라고 가정)
- 마지막 ( n ) 글자 복호화:
마지막 ( n ) 글자의 평문을 알고 있으므로, 마지막 ( n ) 글자를 복호화하여 각 위치에서 사용된 키를 복원할 수 있다.- 마지막 문자 "S"에서 "O"를 빼면 마지막 키 문자는 "E"이다.
- 네 번째 문자 "S"에서 "L"을 빼면 그 다음 키 문자는 "H"이다.
- 세 번째 문자 "J"에서 "L"을 빼면 그 다음 키 문자는 "Y"이다.
- 초기 키와 복원된 키 비교:
복원된 키의 일부는 초기 키와 일치해야 한다. 이 예시에서는 초기 키가 "KEY"이므로, 복원된 "KEY"와 일치하는 부분을 찾을 수 있다. - 평문 전체 복원:
마지막 ( n ) 글자의 평문을 알고 있으므로, 이 정보를 이용해 전체 평문을 복원할 수 있다.- 첫 번째 문자 "R"에서 "K"를 빼면 "H"이다.
- 두 번째 문자 "I"에서 "E"를 빼면 "E"이다.
- 세 번째 문자 "J"에서 "Y"를 빼면 "L"이다.
- 네 번째 문자 "S"에서 "H"를 빼면 "L"이다.
- 다섯 번째 문자 "S"에서 "E"를 빼면 "O"이다.
결론:
AutoKey 암호에서 마지막 ( n ) 글자의 평문을 알고 있으면, 이 정보를 이용해 전체 평문을 복원할 수 있다. 이는 AutoKey 암호의 큰 취약점 중 하나로, 키 길이와 동일한 길이의 평문이 노출되는 경우 복호화가 가능해진다.
이러한 이유로 현대 암호화에서는 키가 평문과 연관되지 않도록 더 복잡한 암호화 방법을 사용하며, 평문과 키 간의 관계를 최소화하려는 노력이 이루어진다.
def decrypt_autokey(n, m, last_n_plaintext, ciphertext):
# 문자 -> 숫자 변환
to_num = lambda c: ord(c) - ord('a')
# 숫자 -> 문자 변환
to_char = lambda n: chr(n + ord('a'))
# 전체 평문을 담을 리스트
plaintext = [''] * m
# 마지막 n개의 평문 복사
for i in range(n):
plaintext[m - n + i] = last_n_plaintext[i]
# 역순으로 평문 복원
for i in range(m - n - 1, -1, -1):
# b_i = ciphertext[i], k_i+n = plaintext[i+n] 사용하여 a_i 계산
k_i = to_num(plaintext[i + n])
b_i = to_num(ciphertext[i + n])
a_i = (b_i - k_i + 26) % 26
plaintext[i] = to_char(a_i)
# 결과를 문자열로 반환
return ''.join(plaintext)
# 입력 처리
n, m = map(int, input().split())
last_n_plaintext = input().strip()
ciphertext = input().strip()
# 평문 복원
result = decrypt_autokey(n, m, last_n_plaintext, ciphertext)
print(result)