본문바로가기
[오일러 프로젝트] 암호 풀고 대탈출: XOR 방식으로 암호화된 메시지를 해독하라!
수학동아 2021.06.25 17:10 조회 322

 

코.알.못 홍 기자의 코딩 도전기

코딩(프로그래밍)의 ‘코’자도 모르는 코.알.못. 홍 기자가 수학 문제를 코딩으로 푸는 오일러 프로젝트 문제를 하나하나 해결해 나갑니다. 오일러 프로젝트는 수학과 코딩 실력을 모두 키울 수 있도록 2001년에 만든 수학 문제 웹사이트입니다. 홍 기자와 함께한다면 수학과 코딩 언어의 하나인 파이썬 모두 정복할 수 있지 않을까요?

 

 

‘한 번 갇히면 빠져나올 수 없다! 극한의 탈출 버라이어티!’ 대탈출 시즌 4가 7월 11일 첫 방송됩니다.

대탈출 멤버들과 함께 암호문을 풀거나 각종 트릭을 찾아 해결하다 보면

방구석에서도 방탈출 게임을 하는 기분을 느낄 수 있죠.

두뇌 회전을 위해 대탈출에 나올 법한 오일러 프로젝트 문제 하나를 풀어볼까요?

컴퓨터 앞에 앉아 30분 타이머를 켜고, 암호문 해독에 도전해보세요. 지금부터 시작!

 

 

<오일러 프로젝트 59번>

우리가 사용하는 문자는 컴퓨터에서 보통 '미국정보교환표준부호코드(ASCII·아스키)'를 사용해 숫자코드로 나타냅니다. 따라서 문장을 암호화하려면 먼저 각 글자를 ASCII로 바꾸고, 각 글자에 비밀키를 적용해 암호화하는 'XOR 방식'을 적용합니다. 비밀키는 영어 소문자 3글자, 숨겨진 평문은 평범한 영어 문장일 때, 암호문을 해독하세요.

 

 

59번 문제의 XOR 연산은 컴퓨터 연산의 일종으로 두 값을 비교해 값이 같으면 0, 다르면 1을 출력합니다. 이를 이용해 암호화하는 방식을 'XOR 방식'이라 하죠. 평문을 비밀키의 글자로 암호화하는 과정은 아래와 같습니다. 

 

① 암호화할 평문의 글자 하나하나를 컴퓨터가 받아들일 수 있게 ASCII로 바꾸고,

② ASCII로 나타낸 평문 글자 하나를 비밀키 글자 하나와 XOR 연산해 값을 얻는다.

   이때 비밀키보다 평문이 더 길면, 비밀키를 반복해서 사용합니다.

 

평문을 비밀키로 암호화한 것처럼, XOR 연산의 성질에 의해 암호문의 글자와 비밀키의 글자를 연산하면 평문의 글자를 얻을 수 있습니다. 파이썬으로 세 개의 영문 알파벳 소문자로 만들 수 있는 비밀키를 모두 찾고, 이를 이용해 암호문을 해독해보겠습니다.

 

 

파이썬 완전정복! '암호 푸는 코드 짜기'

59번 문제를 해결하는 데 필요한 파이썬 명령어입니다.

꿀팁 중의 꿀팁, 밑줄 쫙! 핵심만 소개하니 꼭 익혀두세요!

 

1. 가능한 비밀키의 경우의 수 찾기

59번 문제에 나와있는 조건은 암호화에 쓰인 비밀키가 영문 알파벳 소문자 세 개라는 것입니다. 알파벳 소문자는 총 26개로 각 자리에 26가지 글자가 들어갈 수 있습니다. 따라서 가능한 경우의 수는 26×26×26=1만 7576가지입니다. 1만 7576가지 경우를 일일이 손으로 쓰면 오래 걸리지만, 코딩을 이용하면 빠르게 만들어낼 수 있습니다.

먼저 파이썬에는 한 문자를 ASCII로 변환하는 ord 함수가 있습니다. ord 함수를 이용해 a부터 z까지의 알파벳을 97부터 122까지의 숫자로 바꾸고 리스트에 저장합니다.

 

 

그리고 리스트 az에서 값을 하나씩 뽑아 나열하는 product 함수를 이용해 영문 알파벳 소문자 세 개로 만들어진 비밀키를 만듭니다.

 

 

2. 암호문 해독하기

변수 k에 저장된 비밀키를 이용해 ‘cipher’라는 리스트에 저장한 암호문을 해독합니다. 암호문과 비밀키를 담고 있는 두 숫자 사이의 XOR 연산은 ^ 연산자를 써서 나타낼 수 있습니다. 또 비밀키는 세 자리 글자라고 했으므로, 암호문의 i번째 글자와 연산할 비밀키의 글자는 i를 3으로 나눈 나머지를 이용해 찾습니다.

 

 

 

도전! 오일러 프로젝트 59번 문제 뽀개기

* 코딩 언어는 Python으로 두고 실행하세요!

* 암호문이 너무 길어 아직 실행이 안돼요! 잠깐 다른 숫자를 cipher 리스트에 입력해서 실행해보고,

원래 문제의 암호문은 잠시만 기다려주세요~!

 

 

#3 암호문을 해독해 얻은 평문에 ^, / 같은 특수 문자가 있는지 판별해 일반적인 영어 문장인지 확인하는 함수 is_ok(c)를 만듭니다.

#4 평문을 이루는 숫자들이 모두 알파벳 대소문자거나 공백, (, ) 등의 특수문자에 대응하는 32~90, 97~122 범위 안에 있다면 해당 평문을 되돌려줍니다.

#5, 6, 7, 8 문제의 조건을 만족하는 비밀키 조합을 만들고, 이를 이용해 암호문을 해독한 결과를 얻습니다.

#9, 10 어떤 비밀키로 해독한 평문이 특수 문자가 없는 일반적인 영어 문장이라면 이때의 비밀키와 평문을 출력합니다.

#11 위의 조건을 만족하는 값이 없다면 None, None을 출력합니다.

#12, 13 arr라는 리스트의 ASCII값을 문자열로 바꾸는 함수 code2str(arr)를 정의합니다. 이때 chr() 함수는 코드값에 해당하는 문자를 문자들의 리스트로 바꾸는 함수로, join() 함수를 이용해 리스트를 문자열로 바꿉니다.

#14, 15 e059() 함수를 이용해 일반적인 영어 문장을 만드는 비밀키와 이때의 평문을 얻고, 문자열로 바꿔 출력합니다.

 

 

BONUS 오일러 퀴즈

오일러 프로젝트 59번 문제를 풀어보고, 다음 예제 문제에도 도전해보세요!

 

① 59번 문제를 푸는 전체 코드를 응용해 원하는 메시지를 암호화하는 코드를 만들어보세요.

 

② XOR 연산 외에 암호화에 쓰이는 다른 방식을 찾고, 코드로 암호화 방식을 나타내보세요.

 

 

이번 대탈출 시즌4는 ‘탈 지구급 어드벤처’를 예고했습니다.

몰입감 넘치는 세트, 디테일한 스토리와 함께 DTCU,

일명 D(대) T(탈) C(출) U(유니버스)로 세계관을 넓힐 예정이라고 해요.

대탈출을 다시 만나기 전 암호문을 만들어 게임을 해보는 건 어떨까요?

재밌는 암호문을 만들었다면, 이곳에 올려 공유해주세요!

 

첫 댓글의 주인공이 되어 보세요!
  • 폴리매스 문제는 과학기술진흥기금 및 복권기금의 재원으로 운영되고, 과학기술정보통신부와 한국과학창의재단의 지원을 받아 수행된 성과물로 우리나라의 과학기술 발전과 사회적 가치 증진에 기여하고 있습니다.

  • ☎문의 02-6749-3911