카이사르 암호

개념

카이사르 암호는 전쟁중에 메세지를 고국에 보내야 할 때 문자를 다른 문자로 대체하여 적군이 메세지를 가로채도 이해하지 못하게 안전하게 메세지를 보낼 수 있는 암호입니다.

문자를 다른 문자로 대체한다는 말은 아래 사진과 같이 문자열을 앞으로 밀거나 뒤로 당겨서 암호를 만드는 방식입니다.

옛날 사람들은 암호학이라는 것이 발달하지 않아서 이것만 해도 적군이 알아차리지 못했다고 합니다. 역사를 살펴보니까 치환 암호 부류에서는 최초의 치환 암호이며, 2번째로 만들어진 암호라고 하네요.

우리가 이 카이사르 암호 문제를 풀 때는 문자가 어느 방향으로 몇 번 이동했는지 이해한 후 풀어야 하거나, 입력 값을 통하여 몇 번 이동해야 하는지 주어지는 편입니다.

여기서 아스키 코드가 쓰이는데 알파벳은 26개이므로 우리는 아스키 코드와 사칙연산, 그리고 나머지 연산자를 이용하여 암호문을 평문으로 해독할 수 있습니다.

이 유형은 문제를 보면서 이해하는 것이 좋으므로 바로 문제를 풀어보겠습니다.

연습문제

BOJ 5598

https://www.acmicpc.net/problem/5598www.acmicpc.net

문자를 A -> D, B -> E, C -> F, ... 로 3칸씩 건너뛰어 문자들을 암호화했다고 합니다.

이 암호화를 한 방법은 알고리즘 문제를 풀 때로 생각하자면 아래와 같습니다.

아스키 코드로 변환한다.
A의 아스키 코드는 65이므로 모든 값에 65를 빼준다.
3을 더해준다.
26으로 나눈 나머지로 변경한다.
다시 65를 더해준다.
문자열로 변환해준다.

이것을 그림으로 그려보면 이렇게 나옵니다.

우리는 암호문을 평문으로 해독해야 하는 문제니까 반대로 하는 방법은 아래와 같습니다.

아스키 코드로 변환
65를 빼줌
26을 더함
3을 빼줌
26으로 나눈 나머지로 값을 변경
65를 더해줌
문자로 변환

평문을 암호문으로 만드는 방법보다 한 단계가 추가되었습니다.

이것도 그림을 그려보면 아래와 같습니다.

우리가 알고리즘을 풀 때는 이 계산 과정을 한 줄로 압축할 수 있습니다.

어떤 문자를 x라고 하면

ord(x)
ord(x) - 65
ord(x) - 65 + 26
ord(x) - 65 + 26 - 3
(ord(x) - 65 + 26 - 3) % 26
((ord(x) - 65 + 26 - 3) % 26) + 65
chr(((ord(x) - 65 + 26 - 3) % 26) + 65)

이렇게 표현할 수 있고, -65 + 26 - 3을 정리하면

chr(((ord(x) - 42) % 26) + 65)

이런 식으로 문제를 쉽게 풀고 넘어갈 수 있게 됩니다. 바로 문제를 풀어보겠습니다.

일단 문자를 하나하나 쪼개서 원래 글자로 해독해야 하니까 list()로 입력값을 받아야 합니다.

arr = list(input())

그리고 for문을 이용하여 위에 나온 수식을 사용하면 됩니다.

arr = list(input())
for i in range(len(arr)):
    arr[i] = chr(((ord(arr[i]) - 42) % 26) + 65)
print(''.join(arr))

참고로 이 문제는 딕셔너리로 문제를 풀 수 있습니다. 딕셔너리로 푸는 방법은 문자끼리 1 대 1 매칭을 해주기만 하면 되기 때문에 여기서 설명하지는 않겠습니다.

BOJ 15874

https://www.acmicpc.net/problem/15874www.acmicpc.net

알파벳을 몇 칸 미는지 주어진다고 합니다.

k의 범위가 10,000,000인데 어차피 알파벳을 26칸 밀어버리면 다시 원상태로 돌아오니까 k = k % 26을 해주면 되겠네요.

이제 입력값을 받는 코드를 짜봅시다. 여기서 주의할 점은 우리는 문자를 다른 문자로 바꿔야하므로 리스트로 문자를 받아주면 됩니다.

k, n = map(int,input().split())
k %= 26

s = list(input())

이제 평문에서 암호문으로 바꿔야 하는데, 알파벳이 소문자, 대문자가 들어온다고 합니다.

이것도 별로 다르지 않습니다. 다만 대문자일 때는 A의 아스키 코드인 65를 뺐다가 더해줘야 하고, 소문자인 경우에는 a의 아스키 코드인 97을 뺐다가 더해줘야 합니다.

아스키 코드로 변환
아스키 코드가 알파벳 범위인지 확인
대문자면 65를 빼주고, 소문자면 97을 빼줌
k를 더해줌
26으로 나눈 나머지의 값으로 변경함
대문자면 다시 65를 더해주고, 소문자면 97을 더해줌
문자로 변환해서 s[i]에 넣음

이것을 단계별로 구현해봅시다.

아스키 코드로 변환

k, n = map(int,input().split())
k %= 26

s = list(input())
for i in range(n):
    x = ord(s[i])

아스키 코드가 알파벳 범위인지 확인

A의 아스키 코드는 65니까 65 + 25 = 90으로 Z의 아스키 코드는 90이 되겠습니다.

a의 아스키 코드는 97이니까 97 + 25 = 122로 z의 아스키 코드는 122입니다.

k, n = map(int,input().split())
k %= 26

s = list(input())
for i in range(n):
    x = ord(s[i])
    if 65 <= x <= 90 or 97 <= x <= 122:
        blah blah

대문자면 65를 빼주고, 소문자면 97을 빼줌

여기서 대소문자 확인하는 방법은 두 가지가 있었습니다.

하나는 s[i] == s[i].upper() 혹은 s[i] == s[i].lower()이고, 하나는 그 외 메소드에서 설명한 s[i].isupper(), s[i].islower()입니다.

upper()메소드와 lower()메소드만 알고 있어도 대소문자로 변경하고 확인할 수도 있어서 isupper()와 islower()가 잘 쓰이지 않기는 한데, 갑자기 생각나서 한 번 사용해보겠습니다.

k, n = map(int,input().split())
k %= 26

s = list(input())
for i in range(n):
    x = ord(s[i])
    if 65 <= x <= 90 or 97 <= x <= 122:
        if s[i].isupper(): x -= 65
        else: x -= 97

k를 더함

k, n = map(int,input().split())
k %= 26

s = list(input())
for i in range(n):
    x = ord(s[i])
    if 65 <= x <= 90 or 97 <= x <= 122:
        if s[i].isupper(): x -= 65
        else: x -= 97
        x += k

26으로 나눈 나머지로 변경함

k, n = map(int,input().split())
k %= 26

s = list(input())
for i in range(n):
    x = ord(s[i])
    if 65 <= x <= 90 or 97 <= x <= 122:
        if s[i].isupper(): x -= 65
        else: x -= 97
        x += k
        x %= 26

대문자면 다시 65를 더해주고, 소문자면 97을 더해줌

k, n = map(int,input().split())
k %= 26

s = list(input())
for i in range(n):
    x = ord(s[i])
    if 65 <= x <= 90 or 97 <= x <= 122:
        if s[i].isupper(): x -= 65
        else: x -= 97
        x += k
        x %= 26
        if s[i].islower(): x += 97
        else: x += 65

문자열로 변경해서 s[i]에 넣음

k, n = map(int,input().split())
k %= 26

s = list(input())
for i in range(n):
    x = ord(s[i])
    if 65 <= x <= 90 or 97 <= x <= 122:
        if s[i].isupper(): x -= 65
        else: x -= 97
        x += k
        x %= 26
        if s[i].islower(): x += 97
        else: x += 65
        s[i] = chr(x)

그리고 이제 출력을 해주면 됩니다.

k, n = map(int,input().split())
k %= 26

s = list(input())
for i in range(n):
    x = ord(s[i])
    if 65 <= x <= 90 or 97 <= x <= 122:
        if s[i].isupper(): x -= 65
        else: x -= 97
        x += k
        x %= 26
        if s[i].islower(): x += 97
        else: x += 65
        s[i] = chr(x)

print(''.join(s))

풀어볼 문제

이번에 풀어볼 문제는 여러 암호 문제를 각각 1문제씩 풀어보겠습니다. 두 암호 문제 역시 아스키 코드를 이용하여 문제를 푸는 방식입니다.

Previous추가 문제 Next순열과 조합

Last updated 3 years ago