## Attempting to Deduce the Chaocipher Stepping Mechanism

Moderator: mosher

# Attempting to Deduce the Chaocipher Stepping Mechanism

 Posts 137
Super member
mosher
Super member
Joined: May 26th, 2009, 10:24 am
Background

In April 2009 Jeff Hill presented his important document "Chaocipher: Analysis and Models". Jeff's current theory is that the Chaocipher consists of several cipher disks or slides which advance, or step, 1, 2, or 4 positions each encipherment. Jeff has described several models, and research is currently being done to determine which of the models is the correct one.

It would be extremely helpful if the precise stepping sequence (i.e., the stream of 1s, 2s, and 4s) was known. Such knowledge would greatly simplify the task of determining the Chaocipher's internal cipher disk alphabets.

Chaocipher as some form of autokey

Chaocipher shows no periodicity and no isomorphs. This seems to indicate that it is keyed with some aperiodic keying system. We know Chaocipher cannot be too complex (see Henry Langen's description of Chaocipher: "With only two disks used, I am a bit confused as to how this can result in such utter chaotification of the plaintext message.") We also know that the three "in-depth" messages in Exhibit #5 display a random number of "hits" between themselves when aligned. All this points in the direction of a plain and/or cipher autokey system. This means that the number of steps to take after an encipherment is determined by any or all of the following factors:
• certain plaintext letters
• certain ciphertext letters
• some other factor (e.g., line number, column number)
Examining pt/ct identities

There are many pt/ct sequences in Chaocipher Exhibit #1 that display "pt/ct identities". A pt/ct identity is a sequence of plain and the corresponding cipher letters such that two identical pt/ct pairs are located near each other. For example, on line 77 of Exhibit #1 we find the following:

Code: Select all

``````Line[space]77:[space](p):[space][UMP][space]OVERLAZYDO[space][GTO]
[space][space][space][space][space][space][space][space][space](c):[space][QFK][space]EHGUTNFVTE[space][UOQ]
[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]^[space][space][space][space][space][space][space][space]^[space][space][space][space][space][space]
``````
The text we're interested in is the non-bracketed text in the middle; the bracketed texts to the left and right are the three letters that preceded and followed the main text, respectively. We see that pt "O" was enciphered into ct "E", followed nine steps later by the same "O/E" pair.

If Jeff's model is correct, the Chaocipher enciphered O into E, then advanced nine steps consisting of any combination of 1, 2, and 4, at which point the cipher disks were aligned to again encipher O into E. If the cipher disks are realigned after moving exactly 26 positions, this means the sum of the nine steps equals exactly 26.

So we can make a cautious assertion: assuming these nine pt/ct pairs contribute to the autokeying process, we may be able to deduce information about these precise pt/ct pairs.

pt/ct stepping permutations

Coming back to the nine-step pt/ct identity above, I wrote a program to determine all permutations of the numbers 1, 2, and 4 taken nine at a time that equal 26. For groups of nine numbers the answer is:

Code: Select all

``````[space][space][space][space]Determine[space]probabilities[space]for[space]26[space]teeth,[space]9[space]steps

[space][space][space][space]26[space]/[space]0.000015258789062500[space](permutations:[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]756):[space]1[space]1[space]2[space]2[space]4[space]4[space]4[space]4[space]4[space]
[space][space][space][space]26[space]/[space]0.000003814697265625[space](permutations:[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]126):[space]2[space]2[space]2[space]2[space]2[space]4[space]4[space]4[space]4[space]
``````
This should be understood as follows:

(*) There are two generic ways to have nine steps of 1/2/4 that equals 26:

1 1 2 2 4 4 4 4 4 (756 permutations)
2 2 2 2 2 4 4 4 4 (126 permutations)

(*) The first generic form can be permuted in 756 different ways, while the second form has 126 permutations.
(*) The probabilities at the beginning of each line denote the probability of such a permutation occurring. Since Jeff Hill posits that steps of (1, 2, 4) occur with a probability of (0.5, 0.25, 0.25) respectively, the first form will occur with a probability of ((0.5)^2) x ((0.25)^7) = 0.000015258789062500.

(*) As the number of steps increases, the sum of the steps can equal a multiple of 26 (e.g., 52). For example, for 13 steps we get the following:

Code: Select all

``````-------------------------------------------------------------------

Determine[space]probabilities[space]for[space]26[space]teeth,[space]13[space]steps

26[space]/[space]0.000003814697265625[space](permutations:[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]6435):[space]1[space]1[space]1[space]1[space]1[space]1[space]1[space]1[space]2[space]4[space]4[space]4[space]4[space]
26[space]/[space]0.000000953674316406[space](permutations:[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]60060):[space]1[space]1[space]1[space]1[space]1[space]1[space]2[space]2[space]2[space]2[space]4[space]4[space]4[space]
26[space]/[space]0.000000238418579102[space](permutations:[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]25740):[space]1[space]1[space]1[space]1[space]2[space]2[space]2[space]2[space]2[space]2[space]2[space]4[space]4[space]
26[space]/[space]0.000000059604644775[space](permutations:[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]858):[space]1[space]1[space]2[space]2[space]2[space]2[space]2[space]2[space]2[space]2[space]2[space]2[space]4[space]
26[space]/[space]0.000000014901161194[space](permutations:[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]1):[space]2[space]2[space]2[space]2[space]2[space]2[space]2[space]2[space]2[space]2[space]2[space]2[space]2[space]

Total[space]#[space]permutations:[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]93094
-------------------------------------------------------------------

Determine[space]probabilities[space]for[space]52[space]teeth,[space]13[space]steps

52[space]/[space]0.000000014901161194[space](permutations:[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]1):[space]4[space]4[space]4[space]4[space]4[space]4[space]4[space]4[space]4[space]4[space]4[space]4[space]4[space]

Total[space]#[space]permutations:[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]1
-------------------------------------------------------------------``````
Here there are many ways to equal 26 in 13 steps. There is, however, only one way to equal 52 in 13 steps, i.e., all 4s.

For the information, here is all the permutation information from 9 to 12:

Code: Select all

``````-------------------------------------------------------------------
Determine[space]probabilities[space]for[space]26[space]teeth,[space]9[space]steps

26[space]/[space]0.000015258789062500[space](permutations:[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]756):[space]1[space]1[space]2[space]2[space]4[space]4[space]4[space]4[space]4[space]
26[space]/[space]0.000003814697265625[space](permutations:[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]126):[space]2[space]2[space]2[space]2[space]2[space]4[space]4[space]4[space]4[space]
-------------------------------------------------------------------
Determine[space]probabilities[space]for[space]26[space]teeth,[space]10[space]steps

26[space]/[space]0.000015258789062500[space](permutations:[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]1260):[space]1[space]1[space]1[space]1[space]2[space]4[space]4[space]4[space]4[space]4[space]
26[space]/[space]0.000003814697265625[space](permutations:[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]3150):[space]1[space]1[space]2[space]2[space]2[space]2[space]4[space]4[space]4[space]4[space]
26[space]/[space]0.000000953674316406[space](permutations:[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]120):[space]2[space]2[space]2[space]2[space]2[space]2[space]2[space]4[space]4[space]4[space]
-------------------------------------------------------------------
Determine[space]probabilities[space]for[space]26[space]teeth,[space]11[space]steps

26[space]/[space]0.000015258789062500[space](permutations:[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]462):[space]1[space]1[space]1[space]1[space]1[space]1[space]4[space]4[space]4[space]4[space]4[space]
26[space]/[space]0.000003814697265625[space](permutations:[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]11550):[space]1[space]1[space]1[space]1[space]2[space]2[space]2[space]4[space]4[space]4[space]4[space]
26[space]/[space]0.000000953674316406[space](permutations:[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]4620):[space]1[space]1[space]2[space]2[space]2[space]2[space]2[space]2[space]4[space]4[space]4[space]
26[space]/[space]0.000000238418579102[space](permutations:[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]55):[space]2[space]2[space]2[space]2[space]2[space]2[space]2[space]2[space]2[space]4[space]4[space]
-------------------------------------------------------------------
Determine[space]probabilities[space]for[space]26[space]teeth,[space]12[space]steps

26[space]/[space]0.000003814697265625[space](permutations:[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]13860):[space]1[space]1[space]1[space]1[space]1[space]1[space]2[space]2[space]4[space]4[space]4[space]4[space]
26[space]/[space]0.000000953674316406[space](permutations:[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]27720):[space]1[space]1[space]1[space]1[space]2[space]2[space]2[space]2[space]2[space]4[space]4[space]4[space]
26[space]/[space]0.000000238418579102[space](permutations:[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]2970):[space]1[space]1[space]2[space]2[space]2[space]2[space]2[space]2[space]2[space]2[space]4[space]4[space]
26[space]/[space]0.000000059604644775[space](permutations:[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]12):[space]2[space]2[space]2[space]2[space]2[space]2[space]2[space]2[space]2[space]2[space]2[space]4[space]
-------------------------------------------------------------------
``````
All pt/ct identities from 9 to 12 in Chaocipher Exhibit #1

There are 87 pt/ct identities of distance 9 to 12. Here they are:

Code: Select all

``````Distance[space]=[space]9

*[space][space][space]4207(p):[space][UMP][space]OVERLAZYDO[space][GTO]
*[space][space][space]4207(c):[space][QFK][space]EHGUTNFVTE[space][UOQ]

*[space][space][space]7800(p):[space][EWO][space]ULDRELINQU[space][ISH]
*[space][space][space]7800(c):[space][BVD][space]BFBWYZLOYB[space][SST]

*[space][space][space]7864(p):[space][NES][space]TIMABLETOT[space][HEM]
*[space][space][space]7864(c):[space][IGY][space]ARLTYSNDFA[space][LTT]

*[space][space][space]9838(p):[space][THE][space]SECOLONIES[space][VFO]
*[space][space][space]9838(c):[space][VZN][space]XYPJKPVESX[space][NUD]

-------------------------------------------------------------

Distance[space]=[space]10

*[space][space][space]5821(p):[space][PLE][space]TODISSOLVET[space][HEP]
*[space][space][space]5821(c):[space][EHC][space]KCESWHKLDAK[space][DFL]

*[space][space][space]6001(p):[space][NTR][space]ESPECTTOTHE[space][OPI]
*[space][space][space]6001(c):[space][MXF][space]FWNUCTFXKVF[space][BSP]

*[space][space][space]6148(p):[space][REA][space]TEDEQUALQQT[space][HAT]
*[space][space][space]6148(c):[space][RVV][space]PKIHKTRABMP[space][GLO]

*[space][space]11806(p):[space][EOF][space]OURINTENTIO[space][NSQ]
*[space][space]11806(c):[space][LHH][space]CYWFPYMERDC[space][QZO]

*[space][space]11902(p):[space][LAR][space]EVTHATTHESE[space][UNI]
*[space][space]11902(c):[space][NZJ][space]WONFFHGCQCW[space][BBD]

*[space][space]13570(p):[space][OPL][space]ESHALLNOTPE[space][RIS]
*[space][space]13570(c):[space][SEN][space]MNPJDRPFSRM[space][FXQ]

-------------------------------------------------------------

Distance[space]=[space]11

*[space][space][space][space]389(p):[space][LLG][space]OODQQUICKBRO[space][WNF]
*[space][space][space][space]389(c):[space][UZL][space]AGDBCUAMFQLA[space][CRW]

*[space][space][space][space]994(p):[space][LLG][space]OODQQUICKBRO[space][WNF]
*[space][space][space][space]994(c):[space][SYE][space]WVJZTQXDEWKW[space][SWI]

*[space][space][space]3689(p):[space][LLG][space]OODQQUICKBRO[space][WNF]
*[space][space][space]3689(c):[space][AZJ][space]WDLNAAPMJHGW[space][MXB]

*[space][space][space]3854(p):[space][LLG][space]OODQQUICKBRO[space][WNF]
*[space][space][space]3854(c):[space][TZR][space]NJTINYWRAWAN[space][CJQ]

*[space][space][space]4624(p):[space][LLG][space]OODQQUICKBRO[space][WNF]
*[space][space][space]4624(c):[space][PSA][space]MRVBQGXNIZBM[space][VGV]

*[space][space][space]5868(p):[space][DTH][space]EMWITHANOTHE[space][RQA]
*[space][space][space]5868(c):[space][SIK][space]VSZTAOEPOMRV[space][LBA]

*[space][space][space]5958(p):[space][WSO][space]FNATUREANDOF[space][NAT]
*[space][space][space]5958(c):[space][CGT][space]ATTDSEXFVKJA[space][YYV]

*[space][space][space]6253(p):[space][THE][space]PURSUITOFHAP[space][PIN]
*[space][space][space]6253(c):[space][YVT][space]JXMLSQTVZBYJ[space][OJM]

*[space][space][space]6672(p):[space][ATG][space]OVERNMENTSLO[space][NGE]
*[space][space][space]6672(c):[space][GPD][space]NMZNNFPQDVBN[space][GTX]

*[space][space][space]7383(p):[space][UTE][space]TYRANNYOVERT[space][HES]

*[space][space][space]8281(p):[space][IVE][space]POWERSQINCAP[space][ABL]
*[space][space][space]8281(c):[space][SFW][space]XQQREXSUZOXX[space][UAK]

*[space][space][space]8893(p):[space][TUD][space]EOFNEWOFFICE[space][SQA]
*[space][space][space]8893(c):[space][GRI][space]IXJBCHVMZCTI[space][QBX]

*[space][space][space]9015(p):[space][AND][space]INGARMIESQWI[space][THO]
*[space][space][space]9015(c):[space][DCO][space]TPYABDHZVMUT[space][CCC]

*[space][space][space]9646(p):[space][ESY][space]STEMOFENGLIS[space][HLA]
*[space][space][space]9646(c):[space][GPX][space]OUQFOYUTEVVO[space][DSP]

*[space][space]10142(p):[space][SZH][space]EHASPLUNDERE[space][DOU]
*[space][space]10142(c):[space][JSD][space]TPKRASVLUXXT[space][VAQ]

*[space][space]10242(p):[space][ETR][space]ANSPORTINGLA[space][RGE]
*[space][space]10242(c):[space][BGN][space]YCVRUBAOWZVY[space][SYW]

*[space][space]11732(p):[space][NER][space]ALCONGRESSQA[space][SSE]
*[space][space]11732(c):[space][YND][space]ENIYAHCEPOXE[space][DQV]

*[space][space]12317(p):[space][TOF][space]THISDECLARAT[space][ION]
*[space][space]12317(c):[space][KIY][space]BVFRYHRBATZB[space][ETF]

*[space][space]13243(p):[space][ITI][space]SRATHERFORUS[space][TOB]
*[space][space]13243(c):[space][DOS][space]VCHDPKPUPIUV[space][XFQ]

*[space][space]13501(p):[space][EAN][space]EWBIRTHOFFRE[space][EDO]
*[space][space]13501(c):[space][JQA][space]ZRNDEMKVQAKZ[space][GKA]

-------------------------------------------------------------

Distance[space]=[space]12

*[space][space][space][space]895(p):[space][KBR][space]OWNFOXESJUMPO[space][VER]
*[space][space][space][space]895(c):[space][KYD][space]WRXCJUFPXCPBW[space][YQP]

*[space][space][space]1445(p):[space][KBR][space]OWNFOXESJUMPO[space][VER]
*[space][space][space]1445(c):[space][GWB][space]EAVTJAAPUMPYE[space][MGD]

*[space][space][space]1500(p):[space][KBR][space]OWNFOXESJUMPO[space][VER]
*[space][space][space]1500(c):[space][JCW][space]NLIEPENPVKIMN[space][SSQ]

*[space][space][space]1940(p):[space][KBR][space]OWNFOXESJUMPO[space][VER]
*[space][space][space]1940(c):[space][QZW][space]PBIJOCZIPAFAP[space][FPG]

*[space][space][space]3205(p):[space][KBR][space]OWNFOXESJUMPO[space][VER]
*[space][space][space]3205(c):[space][UFI][space]PPIUWJMSYKWUP[space][MYD]

*[space][space][space]3480(p):[space][KBR][space]OWNFOXESJUMPO[space][VER]
*[space][space][space]3480(c):[space][ORG][space]OFSPJHBHWDMIO[space][CWO]

*[space][space][space]5350(p):[space][KBR][space]OWNFOXESJUMPO[space][VER]
*[space][space][space]5350(c):[space][OZF][space]DWSLYUTGXPLMD[space][UFE]

*[space][space][space]5405(p):[space][KBR][space]OWNFOXESJUMPO[space][VER]
*[space][space][space]5405(c):[space][WOB][space]IVZFKNEUBSAAI[space][ZYX]

*[space][space][space]1072(p):[space][UMP][space]OVERLAZYDOGTO[space][SAV]
*[space][space][space]1072(c):[space][RYX][space]SAVEPRWPKQJMS[space][VGY]

*[space][space][space]1347(p):[space][UMP][space]OVERLAZYDOGTO[space][SAV]
*[space][space][space]1347(c):[space][LUZ][space]BEQAGYIPZPHAB[space][QQR]

*[space][space][space]2007(p):[space][UMP][space]OVERLAZYDOGTO[space][SAV]
*[space][space][space]2007(c):[space][DIN][space]AOMYBGLPBRXZA[space][NBC]

*[space][space][space]4097(p):[space][UMP][space]OVERLAZYDOGTO[space][SAV]
*[space][space][space]4097(c):[space][ITQ][space]EJVXXNBEICFPE[space][WJC]

*[space][space][space]4757(p):[space][UMP][space]OVERLAZYDOGTO[space][SAV]
*[space][space][space]4757(c):[space][UCQ][space]HEYRAAVHXAYDH[space][NNN]

*[space][space][space]5913(p):[space][HEE][space]ARTHTHESEPARA[space][TEA]
*[space][space][space]5913(c):[space][NDX][space]DMMZEPIFUMKGD[space][GFF]

*[space][space][space]5970(p):[space][DOF][space]NATUREXSGODEN[space][TIT]
*[space][space][space]5970(c):[space][KJA][space]YYVNUQWYZXXDY[space][LGV]

*[space][space][space]6128(p):[space][IDE][space]NTQTHATALLMEN[space][ARE]
*[space][space][space]6128(c):[space][OKW][space]ETWJWRZIDQYDE[space][JWY]

*[space][space][space]6404(p):[space][GOV][space]ERNMENTBECOME[space][SDE]
*[space][space][space]6404(c):[space][LBM][space]KYFUOMFRWFLRK[space][BMP]

*[space][space][space]6416(p):[space][COM][space]ESDESTRUCTIVE[space][OFT]
*[space][space][space]6416(c):[space][FLR][space]KBMPTKLUROLYK[space][ZYX]

*[space][space][space]6452(p):[space][IGH][space]TOFTHEPEOPLET[space][OAL]
*[space][space][space]6452(c):[space][MUQ][space]OAGFVSALRFLYO[space][VMB]

*[space][space][space]6477(p):[space][OAB][space]OLISHITQANDTO[space][INS]
*[space][space][space]6477(c):[space][YUQ][space]XGGHWUTZYBORX[space][SPD]

*[space][space][space]6793(p):[space][REM][space]OREDISPOSEDTO[space][SUF]
*[space][space][space]6793(c):[space][ODM][space]EHNUPWVNDWTTE[space][ZUD]

*[space][space][space]6940(p):[space][TIO][space]NSQPURSUINGIN[space][VAR]
*[space][space][space]6940(c):[space][NNJ][space]WSDUDHUAWGVNW[space][IKM]

*[space][space][space]6979(c):[space][MZJ][space]FXRCNWJKKBXOF[space][RET]

*[space][space][space]7042(p):[space][TIS][space]THEIRDUTYQTOT[space][HRO]
*[space][space][space]7042(c):[space][GEH][space]ZRLXNCAERWAZZ[space][GCQ]

*[space][space][space]7250(p):[space][TWT][space]HEHISTORYOFTH[space][EPR]
*[space][space][space]7250(c):[space][BQF][space]MBYIVDIAKZFHM[space][BXL]

*[space][space][space]7251(p):[space][WTH][space]EHISTORYOFTHE[space][PRE]
*[space][space][space]7251(c):[space][QFM][space]BYIVDIAKZFHMB[space][XLQ]

*[space][space][space]7348(p):[space][REC][space]TOBJECTTHEEST[space][ABL]
*[space][space][space]7348(c):[space][YDK][space]IMOKSWLOPTODI[space][LTS]

*[space][space][space]7453(p):[space][DWZ][space]HEHASREFUSEDH[space][ISA]
*[space][space][space]7453(c):[space][OZN][space]GYMEYAKKIKMQG[space][FJI]

*[space][space][space]7859(p):[space][IGH][space]TINESTIMABLET[space][OTH]
*[space][space][space]7859(c):[space][WLW][space]DXIGYARLTYSND[space][FAL]

*[space][space][space]8011(p):[space][ICR][space]ECORDSQFORTHE[space][SOL]
*[space][space][space]8011(c):[space][THI][space]WVVKWVLNJCDUW[space][NYR]

*[space][space][space]8095(p):[space][EDR][space]EPRESENTATIVE[space][HOU]
*[space][space][space]8095(c):[space][ZHV][space]QYSLTEHMFCGBQ[space][FFO]

*[space][space][space]8186(p):[space][OPL][space]EZHEHASREFUSE[space][DFO]
*[space][space][space]8186(c):[space][UYD][space]URWHZNOSVMNWU[space][LST]

*[space][space][space]8528(p):[space][CTI][space]NGTHELAWSFORN[space][ATU]
*[space][space][space]8528(c):[space][KSQ][space]DSGDZXORWJJVD[space][TOY]

*[space][space][space]8625(p):[space][DRA][space]ISINGTHECONDI[space][TIO]
*[space][space][space]8625(c):[space][UYZ][space]KBLWHIRYCZNBK[space][NCM]

*[space][space][space]9238(p):[space][ING][space]HISASSENTTOTH[space][EIR]
*[space][space][space]9238(c):[space][ZLV][space]SBNAWGTPXTIKS[space][CZA]

*[space][space][space]9401(p):[space][OMM][space]ITONTHEINHABI[space][TAN]
*[space][space][space]9401(c):[space][FRV][space]GLBSBVXVDQSCG[space][DUA]

*[space][space][space]9410(p):[space][EIN][space]HABITANTSOFTH[space][ESE]
*[space][space][space]9410(c):[space][XVD][space]QSCGDUAOHTWTQ[space][KEB]

*[space][space][space]9632(p):[space][OLI][space]SHINGTHEFREES[space][YST]
*[space][space][space]9632(c):[space][TWW][space]PQKFYOXFDXZGP[space][XOU]

*[space][space][space]9818(p):[space][SAM][space]EABSOLUTERULE[space][INT]
*[space][space][space]9818(c):[space][WVV][space]SRXDTYVCGNMKS[space][REO]

*[space][space][space]9850(p):[space][SVF][space]ORTAKINGAWAYO[space][URC]
*[space][space][space]9850(c):[space][XNU][space]DEPQLTFAPOBYD[space][FOH]

*[space][space]10009(p):[space][INV][space]ESTEDWITHPOWE[space][RTO]
*[space][space]10009(c):[space][BMH][space]STTQSHIPCSGMS[space][COD]

*[space][space]10212(p):[space][LIV][space]ESOFOURPEOPLE[space][ZHE]
*[space][space]10212(c):[space][NWT][space]NMMWICCNHVMFN[space][PJM]

*[space][space]10638(p):[space][SEX][space]CITEDDOMESTIC[space][INS]
*[space][space]10638(c):[space][AIM][space]BOQBGSFYKQIAB[space][JEP]

*[space][space]10848(p):[space][TAG][space]EOFTHESEOPPRE[space][SSI]
*[space][space]10848(c):[space][YZD][space]YMIPYBMPHPGYY[space][HIU]

*[space][space]11060(p):[space][FAF][space]REEPEOPLEWNOR[space][HAV]
*[space][space]11060(c):[space][ZXN][space]KROKUNOETOSXK[space][WRJ]

*[space][space]11149(p):[space][ETO][space]TIMEOFATTEMPT[space][SBY]
*[space][space]11149(c):[space][HHR][space]WLAFHBBNXUNIW[space][ZGS]

*[space][space]11314(p):[space][IRN][space]ATIVEJUSTICEA[space][NDM]
*[space][space]11314(c):[space][FRL][space]AOZROARZLRIGA[space][VVX]

*[space][space]11323(p):[space][UST][space]ICEANDMAGNANI[space][MIT]
*[space][space]11323(c):[space][RZL][space]RIGAVVXIGYKFR[space][HTL]

*[space][space]11771(p):[space][UPR][space]EMEJUDGEOFTHE[space][WOR]
*[space][space]11771(c):[space][TML][space]EMRPHWZQDCOVE[space][GZV]

*[space][space]11922(p):[space][COL][space]ONIESAREQANDO[space][FRI]
*[space][space]11922(c):[space][OPV][space]SLISHHMWCUGYS[space][JBJ]

*[space][space]12006(p):[space][LEG][space]IANCETOTHEBRI[space][TIS]
*[space][space]12006(c):[space][FMI][space]POOSJUGYCVVNP[space][SNA]

*[space][space]12228(p):[space][SHC][space]OMMERCEQANDTO[space][DOA]
*[space][space]12228(c):[space][AYV][space]SYVRKNQCRSLPS[space][SXY]

*[space][space]12305(p):[space][FOR][space]THESUPPORTOFT[space][HIS]
*[space][space]12305(c):[space][OPO][space]BTBMNSKSFKIYB[space][VFR]

*[space][space]12413(p):[space][ROU][space]RLIVESQOURFOR[space][TUN]

*[space][space]12708(p):[space][EME][space]TONAGREATBATT[space][LEF]
*[space][space]12708(c):[space][XQH][space]POOHAWYKJYOHP[space][BHW]

*[space][space]13222(c):[space][JRP][space]ACIPLKXEFSYIA[space][UQA]

*[space][space]13424(p):[space][LYR][space]ESOLVETHATTHE[space][SED]
*[space][space]13424(c):[space][ZAY][space]TPIVWNQCVJRIT[space][RKE]
``````
My Approach: Hill-Climbing

I wanted to see if values of 1, 2, or 4 could be assigned to all 676 pt/ct pairs such that the 87 pt/ct identity strings would all equal 26. These 87 identity sequences account for exactly 1,000 pt/ct pairs.

I did not use pt/ct identities of distance 13 because of the extremely remote possibility that a 13-step identity might equal 52, rather than 26. I used only 9-12 steps to guarantee that the data is "untainted" by higher multiples of 26.

Spurred on by osric's fruitful use and advocacy of hill-climbing/simulated annealing/Churn, I wrote a simple hill-climbing algorithm to determine the stepping values for each pt/ct pair. The hill-climbing algorithm works as follows:

(1) Allocate a 26x26 table holding stepping values for all 676 pt/ct pairs
(2) Initialize each cell to 1
(3) For each of the 87 pt/ct identity sequences, compute the sum of the pt/ct pairs (do not include the rightmost pair in the calculations; the previous N-1 steps are used to reach this pt/ct identity).
(4) Our global goodness-of-fit metric is the sum of (26 - sequence value) ** 2, for all 87 sequences (we square the value to handle both positive and negative differences). This measures how far we are from a perfect match, the ideal being a value of 0.
(5) Select a random stepping table cell
(6) Change the cell's stepping value to one of the two other values (out of the set of 1, 2, and 4)
(7) Iterating over all 87 sequences with the new cell value, compute the goodness-of-fit metric.
(8) If the new metric is better, keep it, otherwise restore the previous cell value.
(9) Endlessly loop to (5), exiting when 3000 iterations fail to improve the global metric.

Results

After about a thousand runs, the best stepping table the program could achieve is the following:

Code: Select all

``````Best[space]metric:[space]13
spin-limit=3000[space]initialValue=1

[space][space]A[space]B[space]C[space]D[space]E[space]F[space]G[space]H[space]I[space]J[space]K[space]L[space]M[space]N[space]O[space]P[space]Q[space]R[space]S[space]T[space]U[space]V[space]W[space]X[space]Y[space]Z
A[space]1[space]1[space][space][space]1[space]1[space]1[space]2[space]2[space]1[space]1[space]4[space][space][space][space][space]4[space]2[space]4[space]1[space]4[space]1[space]1[space]4[space]1[space][space][space]1[space]4[space]1
B[space][space][space][space][space]2[space][space][space][space][space][space][space][space][space]2[space][space][space][space][space][space][space][space][space][space][space]1[space]1[space][space][space]1[space]4[space][space][space][space][space][space][space]2[space]2[space]2[space]2[space]2
C[space][space][space]2[space]2[space]1[space][space][space]4[space][space][space][space][space]4[space][space][space][space][space][space][space]2[space]4[space]1[space]4[space][space][space]2[space]1[space]4[space][space][space]4[space]4[space][space][space][space][space][space]
D[space][space][space]4[space]1[space]1[space]4[space][space][space]1[space][space][space]4[space]1[space]1[space]1[space]2[space][space][space]1[space][space][space]4[space][space][space]2[space]1[space]1[space]4[space]1[space]1[space]1[space]1
E[space]1[space]1[space]1[space]1[space]1[space]2[space]1[space]1[space]2[space]1[space]1[space]2[space]2[space]4[space]1[space]4[space]4[space]1[space]2[space]4[space]4[space]2[space]2[space]1[space]2[space]4
F[space]4[space]1[space]1[space]2[space]1[space]1[space]1[space][space][space]4[space]2[space]4[space]2[space]1[space]1[space][space][space]1[space]1[space][space][space][space][space]2[space]1[space][space][space]1[space][space][space]1[space]2
G[space]2[space][space][space][space][space][space][space]1[space]1[space]1[space]2[space][space][space]1[space]1[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]1[space][space][space][space][space]1[space][space][space]1[space]4[space]2
H[space][space][space]4[space]1[space]1[space][space][space]4[space]1[space][space][space]1[space][space][space]4[space][space][space]1[space][space][space]2[space]2[space]4[space]2[space]1[space]2[space]2[space]4[space]2[space]1[space]1[space]1
I[space]1[space]1[space]2[space]2[space]4[space]4[space]1[space]2[space]2[space]4[space]1[space]2[space][space][space]2[space]4[space]4[space]4[space]1[space]1[space]2[space]2[space]1[space]4[space]1[space][space][space]4
J[space]1[space]1[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]1[space][space][space][space][space][space][space][space][space]4[space][space][space][space][space][space][space][space][space]2[space]1[space]2[space]1[space]1[space][space]
K[space]2[space][space][space][space][space][space][space]4[space]4[space][space][space][space][space]4[space]1[space][space][space]1[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]
L[space]4[space]4[space][space][space]4[space]1[space]1[space]2[space][space][space][space][space][space][space]4[space]4[space][space][space]2[space][space][space]4[space]4[space]4[space]4[space]4[space][space][space]1[space][space][space]1[space]2[space]4
M[space]4[space][space][space][space][space]4[space][space][space]1[space][space][space][space][space]1[space][space][space][space][space]1[space]2[space]4[space][space][space]2[space][space][space]2[space]4[space][space][space]1[space]1[space]1[space]1[space]2[space][space]
N[space]4[space]4[space]2[space]4[space]2[space]4[space]1[space]2[space]2[space][space][space]1[space]4[space]2[space]1[space]2[space]4[space]1[space][space][space]1[space]4[space][space][space]2[space]1[space]2[space]2[space]1
O[space]2[space]1[space]2[space]4[space]4[space]4[space]4[space]1[space]4[space]4[space]4[space]1[space]1[space]4[space]2[space]2[space]4[space]1[space]1[space]1[space]4[space]2[space]4[space]2[space]1[space]4
P[space]1[space]2[space][space][space][space][space][space][space]4[space]4[space][space][space]2[space]1[space]4[space][space][space]4[space]4[space]1[space]4[space][space][space]1[space]2[space][space][space]4[space]1[space][space][space]4[space]4[space][space]
Q[space]2[space]2[space]4[space]1[space][space][space][space][space][space][space][space][space]1[space][space][space]4[space]1[space]1[space]1[space][space][space][space][space]1[space][space][space]4[space]4[space][space][space][space][space]2[space]4[space]2[space]1
R[space]4[space]2[space]2[space]2[space]4[space]4[space]4[space]1[space]2[space][space][space]2[space]1[space]1[space]2[space]1[space]4[space][space][space]4[space]2[space]4[space]4[space]2[space]4[space]1[space]2[space][space]
S[space]2[space]1[space]4[space]1[space][space][space]1[space]1[space]2[space]2[space][space][space]1[space]2[space]1[space]4[space]4[space]1[space]2[space]2[space]4[space]2[space]2[space]1[space]2[space]2[space]1[space]2
T[space]4[space]2[space]4[space]4[space]1[space]2[space]2[space]2[space]4[space]1[space]2[space]4[space]1[space]2[space]1[space]1[space]2[space]4[space]1[space]1[space]4[space]2[space]1[space]2[space]1[space]2
U[space]1[space]4[space]2[space]4[space][space][space][space][space]4[space]1[space]4[space][space][space]1[space][space][space]2[space]2[space]2[space]1[space]4[space]2[space]1[space]4[space]4[space]1[space][space][space]4[space]1[space][space]
V[space]1[space]2[space][space][space]4[space]1[space][space][space][space][space]2[space]4[space]1[space][space][space][space][space]1[space][space][space]4[space][space][space][space][space]4[space][space][space][space][space][space][space][space][space]2[space][space][space]4[space][space]
W[space]1[space]1[space][space][space][space][space][space][space]1[space][space][space]4[space][space][space][space][space][space][space]4[space]1[space][space][space]1[space]4[space]2[space]1[space][space][space][space][space]1[space]4[space]2[space][space][space][space][space]2
X[space]1[space][space][space]4[space][space][space]1[space][space][space][space][space]4[space][space][space]1[space][space][space][space][space][space][space]2[space][space][space][space][space][space][space][space][space][space][space][space][space]4[space][space][space]1[space][space][space][space][space][space]
Y[space][space][space][space][space][space][space][space][space]4[space]2[space][space][space]1[space][space][space][space][space]1[space][space][space][space][space][space][space][space][space]1[space][space][space]4[space][space][space][space][space][space][space]4[space][space][space][space][space]1[space]2
Z[space][space][space]1[space][space][space][space][space][space][space]2[space][space][space][space][space]1[space][space][space][space][space]1[space][space][space][space][space][space][space][space][space][space][space]1[space][space][space][space][space][space][space]1[space]2[space][space][space][space][space][space]

Step[space]of[space]1[space]occurs[space]181[space]times
Step[space]of[space]2[space]occurs[space]124[space]times
Step[space]of[space]4[space]occurs[space]137[space]times``````
The explanation is:

(*) This is the best table with a metric of 13.
(*) The search terminates after 3000 fruitless iterations.
(*) The table is initialized to 1 before running the iterations.
(*) When this table is used, 74 of the 87 strings equal exactly 26
(*) 13 strings do not equal 26.
(*) All 13 "bad fits" are off by only one (i.e., they equal either 25 or 27). For example, the identity sequence:

Code: Select all

``````Line[space]143:[space](p):[space][NES][space]TIMABLETOT[space][HEM]
[space][space][space][space][space][space][space][space][space][space](c):[space][IGY][space]ARLTYSNDFA[space][LTT]``````
sums up to 4+1+1+1+2+4+4+4+4 = 25, which is one short of the coveted 26.

(*) Steps 1, 2, and 4 occur in the table 157, 139, 146 times, respectively.

My interpretation

Although a metric of 13 is quite good, with all 13 mismatches being only one unit away from 26, hundreds of runs could not do any better than this. If the stepping mechanism were indeed directly related to the pt/ct pair I would have expected to reach a metric of 0 (there may have been several tables that would give 0, but the hill-climbing program should have found at least one. Having run through over a thousand runs, each run running until no improvement is detected for 3,000 iterations, I assume it is not possible to better these results.

My conclusion is that the stepping mechanism is not solely dependent on the pt/ct pair enciphered. It may have another factor which must be identified and tested.

Truth be told, I did not expect to reach a successful conclusion. If the stepping were solely dependent on the pt/ct pair enciphered, there would have had to be repetitions within the first 100 lines of Exhibit #1. This work was more of an exercise in hill-climbing, and a hopeful wish that something of interest might pop up.

Moving Forward
Can anyone envision a hypothetical cipher system, possibly using autokey principles, consisting of two cipher disks (i.e., four cipher wheels, two wheels per cipher disk) that can produce an aperiodic keying stream? Remember, John F. Byrne enciphered a 55-letter sentence ("ALLGOODQQUICK...") one hundred times in succession without creating repetitions. Any such hypothesis can be tested (e.g., using hill climbing). Discovering the keying method would be a tremendous leap forward in solving the Chaocipher.

I still believe that examining the pt/ct identity sequences for distances between 9-12, and maybe even larger distances, is a correct way to break into the system. Such identity sequences would mirror steppings that are a multiple of 26.

Does anyone have any ideas?
Last edited by mosher on December 5th, 2009, 5:11 pm, edited 11 times in total.

 Posts 23
Just registered
cmdline
Just registered
Joined: July 17th, 2008, 4:42 am
Hi Moshe,

I'm trying to understand your example. The steps that you gave (2+2+2+4+2+1+4+4+4) don't seem to match up with the stepping table. Does row/column correspond to plaintext/ciphertext, or is it column/row?
If I go row=T and col=A, I get step=1, and if I do it the other way around, I get 4, not 2. Am I missing something?

 Posts 137
Super member
mosher
Super member
Joined: May 26th, 2009, 10:24 am
Hi cmdline,

Kudos for catching my error -- mea culpa. My original post demonstrated a low metric of 14. While authoring the post my hill-climbing program, which was running in the background, popped up with a metric of 13. I copied-and-pasted the new 26x26 table and modified relevant passages. But I forgot to update the text you found -- thank you! I have since made the necessary corrections to the original post.

FYI, I have left the hill-climbing program running for the past few days. The best it has been able to do to date is a metric of 11. This is good but not good enough, and indicates that the keying mechanism is more complicated.

I hope you enjoy the post!

Moshe

 Posts 23
Just registered
cmdline
Just registered
Joined: July 17th, 2008, 4:42 am
Thanks, Moshe. It makes a lot more sense now! For step #5, where you randomly pick a cell, do you only choose from cells that are occupied? I assume the blank cells are ones that don't occur in any of the 87 sequences.

You should try other optimization algorithms, like annealing, before concluding that you can't get a better score. Hill climbing is apt to get caught in local minima.

You guys have done some great work on Chaocipher! I've been following your work closely. I spent my holidays last summer researching the cipher, but I've been too busy this year. You've done some things that I was planning on doing, such as contacting NSA for info. It's too bad they didn't have much to offer. Has anyone tried to check Friedman's archives in Virginia?

 Posts 137
Super member
mosher
Super member
Joined: May 26th, 2009, 10:24 am
Hi cmdline,

Indeed, I ignore a randomly picked cell that is empty, because this means that the particular pt/ct pair does not occur in the 87 sequences. For the randomly chosen cell, the algorithm randomly chooses one of the other two numbers (e.g., if the cell contains a '4', the algorithm will choose 1 or 2 randomly).

osric has written extensively about SA, both in The Cryptogram and in Cryptologia. He has developed Churn, which is a simpler form of SA. I look forward to learning from you all about Hill-climbing, SA, and Churn, and using it more often in my work.

Regarding local minima, a single run continues until it reaches an apparent minima, characterized by no improvement for 3,000 iterations. At that point I start an entirely new run from scratch, randomly choosing other cells, etc. So far I've run about 7,000 such runs. My thinking here is that each run probes a different area of the N-dimensional space. Can this be improved?

Many thanks for your kind words re our work on Chaocipher. Since establishing The Chaocipher Clearing House I have found several persons, particularly Jeff Hill and Mike Cowan (aka osric ) who have also done, and continue to do, extensive work on Chaocipher. Now you say that you did work on your own on it, too. Would you be willing to share any thoughts you may have on the cipher? What got you started on Chaocipher?

Regarding NSA, I'm considering resubmitting a FOIA request, this time wording it differently. My first request was more general, and did not clearly request cryptanalytic results, etc. I'd like to give it a second try. I find it hard to believe that they didn't do an intensive, in-house effort to solve Chaocipher. Since Chaocipher is not of national security import, I see no reason why they shouldn't provide the information.

For Chaocipher-related tidbits from Friedman's archives in Virgina, see Jeff Hill's Chaocipher: Analysis and Models for references (4, 8, 9, 10) from the Friedman papers.

Welcome aboard!

Moshe
Last edited by mosher on July 27th, 2009, 2:07 pm, edited 1 time in total.

 Posts 118
Super member
osric
Super member
Joined: March 15th, 2009, 11:05 am
wrote: Moshe poses this question: "Can anyone envision a hypothetical cipher system, possibly using autokey principles, consisting of two cipher disks (i.e., four cipher wheels, two wheels per cipher disk) that can produce an aperiodic keying stream? "
Here's a system that fits your specification:

(1) choose a 5-integer primer, say 4,7,2,5,9 ;

(2) create a stream of pseudo-random numbers between 1 and 26 from the primer, using the Gromark principle, as illustrated in the Java program below. This is how it works:

primer = 4 7 2 5 9
next number is 1st + 2nd =11
next 2nd + 3rd = 9
next 3rd + 4th = 7
next 4th + 5th = 14
next 5th + 6th = 20 and so on.

If a number >25 then take modulo 26.
To get away from zero, add 1 to each number formed above.

Here's the program that does the job:

package gromarkstream;

public class Main {

public Main() {
}

public static void main(String[] args)
{
int len,tot,j,x,y,z,m;
int [] primer = {4,7,2,5,9};
int [] key; key= new int[1000];

tot=1000;

for(j=0;j<tot;j++)
{
x=primer[0]; y=primer[1];
z=1+(x+y)%26;
key[j]=z;
System.out.print(z + " ");
for(m=0;m<4;m++)
primer[m]=primer[m+1];
primer[4]=z;
}
}
}

(3) move wheel 1 by an amount dictated by the stream; move wheel 2 every 26 times that wheel 1 moves.

(4) after each move, use the configuration of the two wheels to encipher a plain letter.

The two-wheel system can create 676 different enciphering alphabets. The stream will select at random a different alphabet to encipher each letter. This will give a ciphertext as difficult to solve as Byrne's BUT, like any random stream, it also gives plain-cipher repeats at intervals less than 9 that are not found in Byrne's texts. At least, that's what I have found. So I'm not sure this in itself is good enough.

Last edited by osric on July 28th, 2009, 7:20 am, edited 3 times in total.

 Posts 23
Just registered
cmdline
Just registered
Joined: July 17th, 2008, 4:42 am
wrote:Now you say that you did work on your own on it, too. Would you be willing to share any thoughts you may have on the cipher? What got you started on Chaocipher?
I don't recall exactly how I came upon the Chaocipher. I may have read about it on Elonka Dunin's page of unsolved historical ciphers. I normally work on Kryptos and Beale, and more recently on the Zodiac ciphers. But I became intrigued by Byrne's cipher because there was so much ciphertext and plaintext to work with, compared to these other ciphers.

I agree with some of the earlier discussion here, that Kruh and Devours' three cipher examples may be the way to go. We know that those examples were encrypted by computer, so they should be "clean" encryptions, without errors. Similar to your efforts, I have had trouble finding the matching plaintext sentences in Easton's book. Someone here mentioned that they might be quotations, which makes a lot of sense. I was searching for whole sentences that matched the same length as the examples, but I wasn't finding anything that really matched up well. Often, the sentences I found weren't 'stand alone' sentences. Of course, Kruh and Devours might have chosen totally random sentences, but quotations are more likely.

 Posts 137
Super member
mosher
Super member
Joined: May 26th, 2009, 10:24 am
I wanted to comment on osric's Gromark-like approach ("Gromark" is an acronym for "Gronsfeld with Mixed Alphabet and Running Key").

This type of approach certainly gets us over the problem of no repetitions/isomorphisms in the 100 "ALLGOOD" encipherments in Exhibit 1 of "Silent Years". I wrote a quick-and-dirty Perl script to examine different-sized Gromark seeds (I subsequently found the whole discussion in the ACA "Cryptogram" issue from January/February 1975).

A five-digit seed can have periods of 781, 2343, 5467, or 16401 digits, depending on the type of seed (i.e., permutations of odd and even digits). I tested some six-digit Gromark seeds (100000-100100, 987654-988000) which all have a period of 196,812. So a judiciously selected Gromark seed would not have repeated for the entire Exhibit 1.

I realize we haven't even proven that a Gromark-like scheme was used in Chaocipher, but I have several questions about its possible use:
• Byrne, Langen, and Kruh/Deavours do not allude or hint to a running key feature.
• Exhibit 5 indicates that the keying sequence is different for all three messages, although they all begin "in depth". With a Gromark key, identical columns should show a kappa-sub-plain probability of coincidences/hits, no matter how many alphabets there are.
• Byrne writes "The ancient Egyptians and Babylonians could have been completely familiar with the principle, a fact which is readily deducible from a treatise on mathematics written by Heron of Alexandria in the second century B.C.". As far as I can see, the Fibonacci-like method of adding successive digits to form a new one was not particularly known to the Egyptians and Babylonians. (As an aside, I leafed through Hero's "Stereometrica" and "Mensurae" in the original Greek and German translation yesterday, but did not see anything that could have been enlisted to the aid of Chaocipher.)
In summary, any proposed system must consider the following issues:
• No repetitions or isomorphisms in the 100 "ALLGOOD" lines in Exhibit 1
• No pt/ct identities in less than nine (9) steps
• The three "in depth" message in Exhibit 5 do not show expected coincidences/hits
These three issues will rule out systems that fulfill one or two out of the three criteria.

 Posts 707
NSA worthy
jdege
NSA worthy
Joined: December 7th, 2006, 8:43 pm
osric wrote:](2) create a stream of pseudo-random numbers between 1 and 26 from the primer, using the Gromark principle, as illustrated in the Java program below. This is how it works:

primer = 4 7 2 5 9
next number is 1st + 2nd =11
next 2nd + 3rd = 9
next 3rd + 4th = 7
next 4th + 5th = 14
next 5th + 6th = 20 and so on.

If a number >25 then take modulo 26.
To get away from zero, add 1 to each number formed above.
For those who might be looking for more information on this alogorithm, it's called the Lagged Fibonacci random number generator.
When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl.

 Posts 557
NSA worthy
kryptosfan
NSA worthy
Joined: September 4th, 2011, 6:09 am
mosher wrote:Regarding NSA, I'm considering resubmitting a FOIA request, this time wording it differently. My first request was more general, and did not clearly request cryptanalytic results, etc. I'd like to give it a second try. I find it hard to believe that they didn't do an intensive, in-house effort to solve Chaocipher. Since Chaocipher is not of national security import, I see no reason why they shouldn't provide the information.
I've been recently considering something similar with Kryptos. Seems like he didn't get enough the first time...

Anyone else ever submit a FOIA request for something ciper-related?
OBKR
UOXOGHULBSOLIFBBWFLRVQQPRNGKSSO
TWTQSJQSSEKZZWATJKLUDIAWINFBNYP
VTTMZFPKWGDKZXTJCDIGKUHUAUEKCAR