Cryptoanalysis Exercise: Decypher a poem

Part 1: Understand basic cryptoanalysis and apply natural language statistics to decrypt a ciphertext. Document the process you use to analyze the encryption. Justify your answer by describing the various tests you perform to verify the results you obtained.

• Here is the ciphertext:

  HQCBCFDGDLJABEADLSFXARRCQQCCD
  FSDGCBBXLNCIRDSCHHBFJARUCHT
  FSDUACSAHBFJARABRCSELGHCCD
  FSDRCCOADDCQSCSAFGMFBFGLNCIRD
  HCQTABALHUASHLSHTAISDABEBCQHT
  
  
  HTASHCCOHTACHTAB,FGWIGHFGMFLB
  FSDTFJLSEYABTFYGHTAUAHHABNRFLK
  UANFIGALHQFGEBFGGXFSDQFSHADQAFB
  HTCIETFGMCBHTFHHTAYFGGLSEHTABA
  TFDQCBSHTAKBAFRRXFUCIHHTAGFKA
  
  
  FSDUCHTHTFHKCBSLSEAPIFRRXRFX
  LSRAFJAGSCGHAYTFDHBCDDASURFNO
  CTLOAYHHTAMLBGHMCBFSCHTABDFX
  XAHOSCQLSETCQQFXRAFDGCSHCQFX
  LDCIUHADLMLGTCIRDAJABNCKAUFNO
  
  
  LGTFRRUAHARRLSEHTLGQLHTFGLET
  GCKAQTABAFEAGFSDFEAGTASNA
  HQCBCFDGDLJABEADLSFQCCDFSDL
  LHCCOHTACSARAGGHBFJARADUX
  FSDHTFHTFGKFDAFRRHTADLMMABASNA
  

  Solution:
  

  Decipher the following poem which is encrypted using Monoalpha substitution.

  HQCBCFDGDLJABEADLSFXARRCQQCCD
  FSDGCBBXLNCIRDSCHHBFJARUCHT
  FSDUACSAHBFJARABRCSELGHCCD
  FSDRCCOADDCQSCSAFGMFBFGLNCIRD
  HCQTABALHUASHLSHTAISDABEBCQHT

  HTASHCCOHTACHTAB,FGWIGHFGMFLB
  FSDTFJLSEYABTFYGHTAUAHHABNRFLK
  UANFIGALHQFGEBFGGXFSDQFSHADQAFB
  HTCIETFGMCBHTFHHTAYFGGLSEHTABA
  TFDQCBSHTAKBAFRRXFUCIHHTAGFKA

  FSDUCHTHTFHKCBSLSEAPIFRRXRFX
  LSRAFJAGSCGHAYTFDHBCDDASURFNO
  CTLOAYHHTAMLBGHMCBFSCHTABDFX
  XAHOSCQLSETCQQFXRAFDGCSHCQFX
  LDCIUHADLMLGTCIRDAJABNCKAUFNO

  LGTFRRUAHARRLSEHTLGQLHTFGLET
  GCKAQTABAFEAGFSDFEAGTASNA
  HQCBCFDGDLJABEADLSFQCCDFSDL
  LHCCOHTACSARAGGHBFJARADUX
  FSDHTFHTFGKFDAFRRHTADLMMABASNA

  First we run Ankur Patwa's character frequency tool to obtain the frequencies of uni-gram, di-gram, tri-gram in the ciphertext.

  We get the following trigram statistics:

  HTA	13
  FSD	9
  HTF	6
  LSE	5
  TAB	5
  ADL	4
  FRR	4
  CHT	4
  FJA	4
  ABA	4
  BFJ	3
  IRD	3
  CDF	3

   

  From English language character frequency statistics http://www.cs.chalmers.se/Cs/Grundutb/Kurser/krypto/en_stat.html or viewgraph 10 of http://cs.uccs.edu/~cs591/crypto/basicCrypto.ppt we know that the, and, ing, ion have high frequency appearances.
  I choose the following mapping
  HTA-->the
  FSD-->and
  
  Note that the high frequency of HTF-->tha (HTFH-->that) also support this mapping.
  
  Next we map
  LSE-->LnE-->ing
  since we know S-->n
  
  TAB->heB  a good choice will be
  B-->r
  
  ABA-->ere (here) seems to validate this.

  FRR-->aRR  with a repeat letter RR,A common word is all.
  we choose
  R-->l

  CHT-->Cth; a good mapping will be oth
  We guess
  C-->o

  FJA-->aJe  could be are or ave but if we decide B-->r then J cannot be r, let us choose
  J-->v

  BFJ-->rav

  Now let us use monosub.pl on Bilbo.uccs.edu to test the mapping:
  [chow@bilbo ~]$ cp -r /home/cs591/public_html/crypto/src/monosub .
  [chow@bilbo ~]$ cd monosub
  [chow@bilbo monosub]$ ls
  mapfilenew.txt  monosub.pl  poem2.txt  poem.txt
  mapfile.txt     poem1.txt   poem3.txt
  [chow@bilbo monosub]$ perl monosub.pl poem.txt mapfile.txt
  oldline: HQCBCFDGDLJABEADLSFXARRCQQCCD
  newline: tQoroadGdivergedinaXelloQQood
  oldline: FSDGCBBXLNCIRDSCHHBFJARUCHT
  newline: andGorrXiNoIldnottravelUoth
  oldline: FSDUACSAHBFJARABRCSELGHCCD
  newline: andUeonetravelerlongiGtood
  oldline: FSDRCCOADDCQSCSAFGMFBFGLNCIRD
  newline: andlooOeddoQnoneaGMaraGiNoIld
  oldline: HCQTABALHUASHLSHTAISDABEBCQHT
  newline: toQhereitUentintheIndergroQth
  oldline:
  newline:
  oldline: HTASHCCOHTACHTABFGWIGHFGMFLB
  newline: thentooOtheotheraGWIGtaGMair
  oldline: FSDTFJLSEYABTFYGHTAUAHHABNRFLK
  newline: andhavingYerhaYGtheUetterNlaiK
  oldline: UANFIGALHQFGEBFGGXFSDQFSHADQAFB
  newline: UeNaIGeitQaGgraGGXandQantedQear
  oldline: HTCIETFGMCBHTFHHTAYFGGLSEHTABA
  newline: thoIghaGMorthattheYaGGingthere
  oldline: TFDQCBSHTAKBAFRRXFUCIHHTAGFKA
  newline: hadQorntheKreallXaUoIttheGaKe
  oldline:
  newline:
  oldline: FSDUCHTHTFHKCBSLSEAPIFRRXRFX
  newline: andUoththatKorningePIallXlaX
  oldline: LSRAFJAGSCGHAYTFDHBCDDASURFNO
  newline: inleaveGnoGteYhadtroddenUlaNO
  oldline: CTLOAYHHTAMLBGHMCBFSCHTABDFX
  newline: ohiOeYttheMirGtMoranotherdaX
  oldline: XAHOSCQLSETCQQFXRAFDGCSHCQFX
  newline: XetOnoQinghoQQaXleadGontoQaX
  oldline: LDCIUHADLMLGTCIRDAJABNCKAUFNO
  newline: idoIUtediMiGhoIldeverNoKeUaNO
  oldline:
  newline:
  oldline: LGTFRRUAHARRLSEHTLGQLHTFGLET
  newline: iGhallUetellingthiGQithaGigh
  oldline: GCKAQTABAFEAGFSDFEAGTASNA
  newline: GoKeQhereageGandageGhenNe
  oldline: HQCBCFDGDLJABEADLSFQCCDFSDL
  newline: tQoroadGdivergedinaQoodandi
  oldline: LHCCOHTACSARAGGHBFJARADUX
  newline: itooOtheoneleGGtraveledUX
  oldline: FSDHTFHTFGKFDAFRRHTADLMMABASNA
  newline: andthathaGKadeallthediMMerenNe

  From the first stanza, by identifying the potential word, such as
  tQo-->two; roadG-->roads; XelloQ-->yellow; Qood-->wood.
  And from the 2nd stanza, too0-->took;  thoIgh -->though
  We got the following mappings
  Q-->w
  G-->s
  X-->y
  O-->k
  I-->u

  Modify the mapping file with the new info. Let us run the program again:
  [chow@bilbo monosub]$ perl monosub.pl poem.txt mapfile1.txt

  oldline: HQCBCFDGDLJABEADLSFXARRCQQCCD
  newline: tworoadsdivergedinayellowwood
  oldline: FSDGCBBXLNCIRDSCHHBFJARUCHT
  newline: andsorryiNouldnottravelUoth
  oldline: FSDUACSAHBFJARABRCSELGHCCD
  newline: andUeonetravelerlongistood
  oldline: FSDRCCOADDCQSCSAFGMFBFGLNCIRD
  newline: andlookeddownoneasMarasiNould
  oldline: HCQTABALHUASHLSHTAISDABEBCQHT
  newline: towhereitUentintheundergrowth
  oldline:
  newline:
  oldline: HTASHCCOHTACHTABFGWIGHFGMFLB
  newline: thentooktheotherasWustasMair
  oldline: FSDTFJLSEYABTFYGHTAUAHHABNRFLK
  newline: andhavingYerhaYstheUetterNlaiK
  oldline: UANFIGALHQFGEBFGGXFSDQFSHADQAFB
  newline: UeNauseitwasgrassyandwantedwear
  oldline: HTCIETFGMCBHTFHHTAYFGGLSEHTABA
  newline: thoughasMorthattheYassingthere
  oldline: TFDQCBSHTAKBAFRRXFUCIHHTAGFKA
  newline: hadworntheKreallyaUoutthesaKe

  Nould can be would (but Q-->w already) or could.
  NlaiK-->claim  validate N-->c is a good choice.
  saKe-->same valide K-->m a good choice.
  Also Uoth->both
  Wust-->just;  Mair-->fair.
  Therefore
  N-->c
  K-->m
  U-->b
  W-->j
  M-->f

  Let us run monosub.pl again:

  oldline: HQCBCFDGDLJABEADLSFXARRCQQCCD
  newline: tworoadsdivergedinayellowwood
  oldline: FSDGCBBXLNCIRDSCHHBFJARUCHT
  newline: andsorryicouldnottravelboth
  oldline: FSDUACSAHBFJARABRCSELGHCCD
  newline: andbeonetravelerlongistood
  oldline: FSDRCCOADDCQSCSAFGMFBFGLNCIRD
  newline: andlookeddownoneasfarasicould
  oldline: HCQTABALHUASHLSHTAISDABEBCQHT
  newline: towhereitbentintheundergrowth
  oldline:
  newline:
  oldline: HTASHCCOHTACHTABFGWIGHFGMFLB
  newline: thentooktheotherasjustasfair
  oldline: FSDTFJLSEYABTFYGHTAUAHHABNRFLK
  newline: andhavingYerhaYsthebetterclaim
  oldline: UANFIGALHQFGEBFGGXFSDQFSHADQAFB
  newline: becauseitwasgrassyandwantedwear
  oldline: HTCIETFGMCBHTFHHTAYFGGLSEHTABA
  newline: thoughasforthattheYassingthere
  oldline: TFDQCBSHTAKBAFRRXFUCIHHTAGFKA
  newline: hadwornthemreallyaboutthesame
  oldline:
  newline:
  oldline: FSDUCHTHTFHKCBSLSEAPIFRRXRFX
  newline: andboththatmorningePuallylay
  oldline: LSRAFJAGSCGHAYTFDHBCDDASURFNO
  newline: inleavesnosteYhadtroddenblack
  oldline: CTLOAYHHTAMLBGHMCBFSCHTABDFX
  newline: ohikeYtthefirstforanotherday
  oldline: XAHOSCQLSETCQQFXRAFDGCSHCQFX
  newline: yetknowinghowwayleadsontoway
  oldline: LDCIUHADLMLGTCIRDAJABNCKAUFNO
  newline: idoubtedifishouldevercomeback
  oldline:
  newline:
  oldline: LGTFRRUAHARRLSEHTLGQLHTFGLET
  newline: ishallbetellingthiswithasigh
  oldline: GCKAQTABAFEAGFSDFEAGTASNA
  newline: somewhereagesandageshence
  oldline: HQCBCFDGDLJABEADLSFQCCDFSDL
  newline: tworoadsdivergedinawoodandi
  oldline: LHCCOHTACSARAGGHBFJARADUX
  newline: itooktheonelesstraveledby
  oldline: FSDHTFHTFGKFDAFRRHTADLMMABASNA
  newline: andthathasmadeallthedifference

  YerhaYs-->perhaps
  ePually-->equally

  Therefore
  Y-->p
  P-->q
  Now we got all the mapping:
  [chow@bilbo monosub]$perl monosub.pl poem.txt mapfile3.txt

  oldline: HQC BCFDG DLJABEAD LS F XARRCQ QCCD
  newline: two roads diverged in a yellow wood
  oldline: FSD GCBBX L NCIRD SCH HBFJAR UCHT
  newline: and sorry I could not travel both
  oldline: FSD UA CSA HBFJARAB RCSE L GHCCD
  newline: and be one traveler long I stood
  oldline: FSD RCCOAD DCQS CSA FG MFB FG L NCIRD
  newline: and looked down one as far as I could

  oldline: HC QTABA LH UASH LS HTA ISDABEBCQHT
  newline: to where it bent in the undergrowth
  oldline:
  newline:
  oldline: HTAS HCCO HTA CHTAB FG WIGH FG MFLB
  newline: then took the other as just as fair
  oldline: FSD TFJLSE YABTFYG HTA UAHHAB NRFLK
  newline: and having perhaps the better claim
  oldline: UANFIGA LH QFG EBFGGX FSD QFSHAD QAFB
  newline: because it was grassy and wanted wear
  oldline: HTCIET FG MCB HTFH HTAY FGGLSE HTABA
  newline: though as for that the passing there
  oldline: TFD QCBS HTAK BAFRRX FUCIH HTA GFKA
  newline: had worn them really about the same
  oldline:
  newline:
  oldline: FSD UCHT HTFH KCBSLSE APIFRRX RFX
  newline: and both that morning equally lay
  oldline: LS RAFJAG SC GHAY TFD HBCDDAS URFNO
  newline: in leaves no step had trodden black
  oldline: CT L OAYH HTA MLBGH MCB FSCHTAB DFX
  newline: oh I kept the first for another day
  oldline: XAH OSCQLSE TCQ QFX RAFDG CS HC QFX
  newline: yet knowing how way leads on to way
  oldline: L DCIUHAD LM L GTCIRD AJAB NCKA UFNO
  newline: I doubted if I should ever come back
  oldline:
  newline:
  oldline: L GTFRR UA HARRLSE HTLG QLHT F GLET
  newline: I shall be telling this with a sigh
  oldline: GCKA QTABA FEAG FSD FEAG TASNA
  newline: some where ages and ages hence
  oldline: HQC BCFDG DLJABEAD LS F QCCD FSD L
  newline: two roads diverged in a wood and i
  oldline: L HCCO HTA CSA RAGG HBFJARAD UX
  newline: I took the one less traveled by
  oldline: FSD HTFH TFG KFDA FRR HTA DLMMABASNA
  newline: and that has made all the difference

  This is the poem written by Robert Foster, "The Road Not Taken" 1915.
  http://www.wsu.edu:8080/~wldciv/world_civ_reader/world_civ_reader_2/frost_road.html

Encryption usign openssl with AES.

• An important hint of Part 1 is encrypted using OpenSSL with AES encryption and base 64 encoding. It is saved in http://cs.uccs.edu/~cs591/crypto/hw4Part1Hint.enc
• Decrypt the file with symmetric key (or called password/passphrase) cs591 and find out what it the hint. Give your best effort to solve the Part 1 before you try this hint.
  Results:

  [cs591@bilbo hw4]$ wget http://cs.uccs.edu/~cs591/crypto/hw4Part1Hint.enc
  --2008-10-15 16:37:32--  http://cs.uccs.edu/~cs591/crypto/hw4Part1Hint.enc
  Resolving cs.uccs.edu... 128.198.162.68
  Connecting to cs.uccs.edu|128.198.162.68|:80... connected.
  HTTP request sent, awaiting response... 200 OK
  Length: 65 [text/plain]
  Saving to: `hw4Part1Hint.enc'
  
  100%[======================================>] 65          --.-K/s   in 0s      
  
  2008-10-15 16:37:32 (4.71 MB/s) - `hw4Part1Hint.enc' saved [65/65]
  
  [cs591@bilbo hw4]$ openssl enc -d -aes-256-cbc -a -in hw4Part1Hint.enc
  enter aes-256-cbc decryption password:
  peom from Robert Frost

• For the corresponding command see the above link. We are using 256 bit cbc (cipher block chaining) chaining mode.