Python :: Substitution Cipher Auto decrypt :: 단일 치환 암호 자동 해독 프로그램

substitution cipher이란 치환 암호를 뜻하며, 카이사르 암호(시저 암호)처럼 단일 치환 암호이지만 대칭되는 알파벳이 무작위이기 때문에 가능한 경우의 수가 기하급수적으로 증가하여 비교적 복잡한 암호이다. 다음은 암호수학 수업시간에 교수님께서 내주신 과제의 내용이다.

 

APS ZU BMS THAAMT KB SOP CHAAPJ MQ LPUWHKX. K UHJ SM JMZ SMLHJ VJ QXKPBLU -- UM PCPB SOMZDO TP

QHEP SOP LKQQKEZASKPU MQ SMLHJ HBL SMVMXXMT, K USKAA OHCP H LXPHV. KS KU H LXPHV LPPWAJ XMMSPL

KB SOP HVPXKEHB LXPHV. K OHCP H LXPHV SOHS MBP LHJ SOKU BHSKMB TKAA XKUP ZW HBL AKCP MZS SOP SXZP

VPHBKBD MQ KSU EXPPL: "TP OMAL SOPUP SXZSOU SM IP UPAQ-PCKLPBS, SOHS HAA VPB HXP EXPHSPL PGZHA."

K OHCP H LXPHV SOHS MBP LHJ MB SOP XPL OKAAU MQ DPMXDKH SOP UMBU MQ QMXVPX UAHCPU HBL SOP UMBU

MQ QMXVPX UAHCP MTBPXU TKAA IP HIAP SM UKS LMTB SMDPSOPX HS SOP SHIAP MQ IXMSOPXOMML. K OHCP H

LXPHV SOHS MBP LHJ PCPB SOP USHSP MQ VKUUKUUKWWK, H USHSP UTPASPXKBD TKSO SOP OPHS MQ KBFZUSKEP,

UTPASPXKBD TKSO SOP OPHS MQ MWWXPUUKMB, TKAA IP SXHBUQMXVPL KBSM HB MHUKU MQ QXPPLMV HBL

FZUSKEP. K OHCP H LXPHV SOHS VJ QMZX AKSSAP EOKALXPB TKAA MBP LHJ AKCP KB H BHSKMB TOPXP SOPJ TKAA

BMS IP FZLDPL IJ SOP EMAMX MQ SOPKX URKB IZS IJ SOP EMBSPBS MQ SOPKX EOHXHESPX. K OHCP H LXPHV

SMLHJ. K OHCP H LXPHV SOHS MBP LHJ LMTB KB HAHIHVH, TKSO KSU CKEKMZU XHEKUSU, TKSO KSU DMCPXBMX

OHCKBD OKU AKWU LXKWWKBD TKSO SOP TMXLU MQ KBSPXWMUKSKMB HBL BZAAKQKEHSKMB -- MBP LHJ XKDOS

SOPXP KB HAHIHVH AKSSAP IAHER IMJU HBL IAHER DKXAU TKAA IP HIAP SM FMKB OHBLU TKSO AKSSAP TOKSP

IMJU HBL TOKSP DKXAU HU UKUSPXU HBL IXMSOPXU. K OHCP H LXPHV SMLHJ. K OHCP H LXPHV SOHS MBP LHJ

PCPXJ CHAAPJ UOHAA IP PNHASPL, HBL PCPXJ OKAA HBL VMZBSHKB UOHAA IP VHLP AMT, SOP XMZDO WAHEPU

TKAA IP VHLP WAHKB, HBL SOP EXMMRPL WAHEPU TKAA IP VHLP USXHKDOS, HBL SOP DAMXJ MQ SOP AMXL

UOHAA IP XPCPHAPL HBL HAA QAPUO UOHAA UPP KS SMDPSOPX.

 

위의 암호문을 풀어오는 과제이며 ‘substitution cipher’ 키워드가 힌트로 주어졌다. 이 문제를 자동으로 풀어서 plaintext를 출력해내는 프로그램을 만들고 싶어 pyhton으로 개발하게 되었다.

간략한 복호화 알고리즘은 아래와 같다

1. 입력 값 이어받기(개행 무시)

2. 입력 값 특수문자 제거 및 공백단위로 단어 리스트 만들기

3. 알파벳 빈도 분석 후 최다 빈도 알파벳과 ‘e’ 치환

4. 단어 빈도 분석 후 조건에 맞는 최다 빈도 단어를 ‘the’ ‘that 순으로 치환

5. 치환된 알파벳이 많은 순으로 단어를 정렬

6. 정렬된 리스트 순서대로 사전검색

7. 사전검색 결과가 1개인 경우 치환

8. 5-7을 반복

9. 치환된 글에 대문자가 없으면 루프탈출 및 출력

소스코드는 아래와 같다

import string
import operator
import requests
 
key={}
 
 
def Input():
   text=""
   #암호문 개행 입력 제거
   while True:
      tmp = input()
      if tmp == "":
         break
      else:
         text+=tmp+" "
   #암호문 특수문자 제거
   for i in ["\"", ".", ",", "'", "-"]:
      text = text.replace(i,"")
   return text
 
 
 
def BasicProcess(text):
   #알파벳 빈도수 정렬
   table=[]
   for alphabet in string.ascii_uppercase:
      table.append([alphabet,text.count(alphabet)])
   table.sort(key=lambda x:x[1], reverse=True)
   print("\n############### Frequency Count Table ###############")
   for i in range(len(table)):
      print("["+table[i][0]+" : "+str(table[i][1])+"]",end=" ")
      if (i+1)%4 == 0:
         print("")
   #최다빈도 알파벳을 'e'로 치환
   text = text.replace(table[0][0],'e')
   key[table[0][0]] = 'e'
   
   #최다빈도 단어를 the, that순으로 치환
   for word in ["the","that"]:
      wordList = text.split(' ')
      words={}
      for i in wordList:
         if len(i)==len(word) and i[-1]==word[-1]:
            if word=="that" and i[:2]!="th":
               continue
            if i not in words:
               words[i] = 1
            else:
               words[i] +=1
      if words=={}:
         continue
      words = sorted(words.items(), key=operator.itemgetter(1), reverse=True)
      text = Substitution(text, words[0][0], word)
 
 
   return text
 
 
def AutoProcess(text):
   wordList=text.split(" ")
   words={}
 
   #소문자로 이루어진 완결된 단어 필터링
   for i in wordList:
      if i in words:
         continue
      else:
         words[i] = 0
      for j in i:
         if j in string.ascii_lowercase:
               words[i] +=1
      if words[i]==len(i):
         del words[i]
   words = sorted(words.items(), key=operator.itemgetter(1), reverse=True)
   
   #정렬된 단어순으로 사전검색
   possible=[]
   for i in words:
      possible = SearchWord(i[0])
      if len(possible) ==1:
         text = Substitution(text, i[0], possible[0])
         print("Found > "+possible[0])
         break
   return text
 
 
 
def Substitution(text, oldWord, newWord):
   #치환되지 않은 알파벳만 치환
   for i in range(len(newWord)):
      if oldWord[i] in string.ascii_uppercase:
         text = text.replace(oldWord[i], newWord[i])
         key[oldWord[i]] = newWord[i]
   return text
 
 
 
 
def SearchWord(word):
   URL= "https://www.onelook.com"
   words=[]
   result=""
   #검색명령 폼에 맞춤
   for i in range(len(word)):
      if word[i] in string.ascii_uppercase:
         word=word[:i]+'*'+word[i+1:]
 
   #사전 페이지에 요청 및 응답
   params = {'w':word, "scwo":1, "sswo":1, "ssbp":1}
   res = requests.get(URL,params=params)
   if "Sorry, there are no words matching" not in res.text:
      for num in range(res.text.count(". <a href")):
         start=res.text.index(str(num+1)+". ")+15+len(str(num+1))
         end=res.text[start:].index("\"")
         result=res.text[start:start+end]
         if len(result) == len(word):
            words.append(result)
         
   #단어 싱크로율 체크
   for i in words:
      for j in range(len(word)):
         if word[j] !='*' and word[j]!=i[j]:
            words.remove(i)
            break
         
   return words
 
 
print("Input Ciphertext")
print("----------------")
ciphertext = BasicProcess(Input())
plaintext=ciphertext
 
#본문 내에 대문자가 없을시 프로그램 종료
print("\n############### decrypt ###############")
while(True):
   complete=0
   plaintext = AutoProcess(plaintext)
   for i in string.ascii_uppercase:
      if i in plaintext:
         complete=-1
   if complete==0:
      break
 
print("\n############### Plaintext ###############")
print(plaintext)
print("\n############### Key Table ###############")
key = sorted(key.items(), key=operator.itemgetter(0))
for k,v in key:
   print("["+k+" : "+v+"]", end=" ")

실행결과는 다음과 같다

========= RESTART: C:\Users\samsung\Desktop\암호수학 과제\[이재승]decrypt.py =========
Input Ciphertext
----------------
APS ZU BMS THAAMT KB SOP CHAAPJ MQ LPUWHKX. K UHJ SM JMZ SMLHJ VJ QXKPBLU -- UM PCPB SOMZDO TP
QHEP SOP LKQQKEZASKPU MQ SMLHJ HBL SMVMXXMT, K USKAA OHCP H LXPHV. KS KU H LXPHV LPPWAJ XMMSPL
KB SOP HVPXKEHB LXPHV. K OHCP H LXPHV SOHS MBP LHJ SOKU BHSKMB TKAA XKUP ZW HBL AKCP MZS SOP SXZP
VPHBKBD MQ KSU EXPPL: "TP OMAL SOPUP SXZSOU SM IP UPAQ-PCKLPBS, SOHS HAA VPB HXP EXPHSPL PGZHA."
K OHCP H LXPHV SOHS MBP LHJ MB SOP XPL OKAAU MQ DPMXDKH SOP UMBU MQ QMXVPX UAHCPU HBL SOP UMBU
MQ QMXVPX UAHCP MTBPXU TKAA IP HIAP SM UKS LMTB SMDPSOPX HS SOP SHIAP MQ IXMSOPXOMML. K OHCP H
LXPHV SOHS MBP LHJ PCPB SOP USHSP MQ VKUUKUUKWWK, H USHSP UTPASPXKBD TKSO SOP OPHS MQ KBFZUSKEP,
UTPASPXKBD TKSO SOP OPHS MQ MWWXPUUKMB, TKAA IP SXHBUQMXVPL KBSM HB MHUKU MQ QXPPLMV HBL
FZUSKEP. K OHCP H LXPHV SOHS VJ QMZX AKSSAP EOKALXPB TKAA MBP LHJ AKCP KB H BHSKMB TOPXP SOPJ TKAA
BMS IP FZLDPL IJ SOP EMAMX MQ SOPKX URKB IZS IJ SOP EMBSPBS MQ SOPKX EOHXHESPX. K OHCP H LXPHV
SMLHJ. K OHCP H LXPHV SOHS MBP LHJ LMTB KB HAHIHVH, TKSO KSU CKEKMZU XHEKUSU, TKSO KSU DMCPXBMX
OHCKBD OKU AKWU LXKWWKBD TKSO SOP TMXLU MQ KBSPXWMUKSKMB HBL BZAAKQKEHSKMB -- MBP LHJ XKDOS
SOPXP KB HAHIHVH AKSSAP IAHER IMJU HBL IAHER DKXAU TKAA IP HIAP SM FMKB OHBLU TKSO AKSSAP TOKSP
IMJU HBL TOKSP DKXAU HU UKUSPXU HBL IXMSOPXU. K OHCP H LXPHV SMLHJ. K OHCP H LXPHV SOHS MBP LHJ
PCPXJ CHAAPJ UOHAA IP PNHASPL, HBL PCPXJ OKAA HBL VMZBSHKB UOHAA IP VHLP AMT, SOP XMZDO WAHEPU
TKAA IP VHLP WAHKB, HBL SOP EXMMRPL WAHEPU TKAA IP VHLP USXHKDOS, HBL SOP DAMXJ MQ SOP AMXL
UOHAA IP XPCPHAPL HBL HAA QAPUO UOHAA UPP KS SMDPSOPX.
 
 
############### Frequency Count Table ###############
[P : 156] [H : 124] [S : 116] [K : 97] 
[M : 87] [A : 81] [O : 75] [X : 69] 
[B : 68] [U : 68] [L : 63] [T : 29] 
[V : 28] [Q : 27] [J : 26] [C : 24] 
[I : 24] [E : 20] [D : 18] [Z : 18] 
[W : 14] [F : 4] [R : 4] [G : 1] 
[N : 1] [Y : 0] 
############### decrypt ###############
Found > together
Found > brotherhood
Found > brothers
Found > character
Found > interposition
Found > mississippi
Found > transformed
Found > difficulties
Found > injustice
Found > tomorrow
Found > governor
Found > exalted
Found > valley
Found > black
Found > equal
 
############### Plaintext ###############
let us not wallow in the valley of despair i say to you today my friends  so even though we face the difficulties of today and tomorrow i still have a dream it is a dream deeply rooted in the american dream i have a dream that one day this nation will rise up and live out the true meaning of its creed: we hold these truths to be selfevident that all men are created equal i have a dream that one day on the red hills of georgia the sons of former slaves and the sons of former slave owners will be able to sit down together at the table of brotherhood i have a dream that one day even the state of mississippi a state sweltering with the heat of injustice sweltering with the heat of oppression will be transformed into an oasis of freedom and justice i have a dream that my four little children will one day live in a nation where they will not be judged by the color of their skin but by the content of their character i have a dream today i have a dream that one day down in alabama with its vicious racists with its governor having his lips dripping with the words of interposition and nullification  one day right there in alabama little black boys and black girls will be able to join hands with little white boys and white girls as sisters and brothers i have a dream today i have a dream that one day every valley shall be exalted and every hill and mountain shall be made low the rough places will be made plain and the crooked places will be made straight and the glory of the lord shall be revealed and all flesh shall see it together 
 
############### Key Table ###############
[A : l] [B : n] [C : v] [D : g] [E : c] [F : j] [G : q] [H : a] [I : b] [J : y] [K : i] [L : d] [M : o] [N : x] [O : h] [P : e] [Q : f] [R : k] [S : t] [T : w] [U : s] [V : m] [W : p] [X : r] [Z : u]