The key to the third part of Kryptos has been recovered!
July 25th - August 14th, 2003
The first three parts of KRYPTOS have been broken over four years ago. However the actual encryption process
and the key to the third part have not been [publicly] recovered until now. It is the first major discovery
since Jim Gillogly breaking the first three parts of the sculpture.
The key is 0362514 (KRYPTOS).
And the encryption process is Route Transposition followed by a Keyed Columnar Transposition.
Jim Gillogly who first broke the first three parts of the KRYPTOS writes later:
> Yes -- I used my standard army double transposition program on it, and
> it discovered a lot of the text, which I rearranged by hand to get the
> actual solution: the third (irregular) transposition and complete
> crack. It wasn't until later (after I'd described the break) that I
> saw the clean and easy way... which I'm quite sure is the way Scheidt
> had intended. That said, a triple columnar transposition has indeed
> been used historically... but this ain't it!
Other cryptanalysts came up with different solutions, but they all lacked consistency and Sanborn kept saying
that they were not correct solutions. I didn't like them either. When I first saw Elonka's page describing
the way to decrypt the third part, I immediately told her that in my opinion it wasn't the right way and
I dedicated some time to prove it. I put together a proper encryption-decryption process for a keyed columnar
transposition using either 4152630 or 0362514 as the key and e-mailed the keys to the greatest inspiration for
anyone interested in breaking KRYPTOS - the Yahoo KRYPTOS Group - recommending them to run a dictionary over
those keys to find a proper keyword. I wasn't surprised when the next morning David Wilson found a good match.
Impressively enough it was the word KRYPTOS itself. As Elonka insisted, I'm publishing my findings here.
______________________________________________________________________________________________________________
The actual encryption process as I see it:
Step 1, Route Transposition:
First we pad the message fitting it into a 86xN box.
Why padding it? To make the text in all the columns line up leaving columns of only two different lengths for
the person decrypting to deal with, who is expected to know exactly how many of them there are and which ones
they are. We are just being considerate of the guy with the key on the other end.
How many letters to add? The message length is 336 and we are fitting it into a box of width 86. 86 mod 7 = 2.
It means that every line except for the last one will have 2 extra columns. 336 mod 86 = 78.
The last line will be 78 letters long and 78 mod 7 = 1.
And since the number of the last line's "extra" columns has to be the same as the first lines
to make the columns line up, we only need one extra Q to make it 2 for all the lines. Clear enough?
Now to the transposition itself:
In by Rows backwards into 86x4, Out by Columns in groups of 7 which is the length of the key:
SLOWLYDESPARATLYSLOWLYTHEREMAINSOFPASSAGEDEBRISTHATENCUM
BEREDTHELOWERPARTOFTHEDOORWAYWASREMOVEDWITHTREMBLINGHAND
SIMADEATINYBREACHINTHEUPPERLEFTHANDCORNERANDTHENWIDENING
THEHOLEALITTLEIINSERTEDTHECANDLEANDPEEREDINTHEHOTAIRESCA
PINGFROMTHECHAMBERCAUSEDTHEFLAMETOFLICKERBUTPRESENTLYDET
AILSOFTHEROOMWITHINEMERGEDFROMTHEMISTXCANYOUSEEANYTHINGQ?
->
?QGNIHTYNAEESUOYNACXTSIMEHTMORFDEGREMENIHTIWMOOREHTFOSLIATEDYLTNESERPTUBREKCILFOTEMALF
EHTDESUACREBMAHCEHTMORFGNIPACSERIATOHEHTNIDEREEPDNAELDNACEHTDETRESNIIELTTILAELOHEHTGNI
NEDIWNEHTDNARENROCDNAHTFELREPPUEHTNIHCAERBYNITAEDAMISDNAHGNILBMERTHTIWDEVOMERSAWYAWROO
DEHTFOTRAPREWOLEHTDEREBMUCNETAHTSIRBEDEGASSAPFOSNIAMEREHTYLWOLSYLTARAPSEDYLWOLS
What makes me think it was written backwards? Because the extra space is not at the end of the message but
before the first letter. Who would bother calculating the position of the first letter and start writing
the message beginning with the 7th column just to make it fill up the rectangle perfectly at the end?
I think it is easier to simply fill out the rectangle backwards if you are doing it with pen and paper.
Either way, it is 86x4 with 7 spaces in front of the first letter.
?QGNIHT YNAEESU OYNACXT SIMEHTM ORFDEGR EMENIHT IWMOORE HTFOSLI ATEDYLT NESERPT UBREKCI LFOTEMA LF
EHTDESU ACREBMA HCEHTMO RFGNIPA CSERIAT OHEHTNI DEREEPD NAELDNA CEHTDET RESNIIE LTTILAE LOHEHTG NI
NEDIWNE HTDNARE NROCDNA HTFELRE PPUEHTN IHCAERB YNITAED AMISDNA HGNILBM ERTHTIW DEVOMER SAWYAWR OO
DEHTFOT RAPREWO LEHTDER EBMUCNE TAHTSIR BEDEGAS SAPFOSN IAMEREH TYLWOLS YLTARAP SEDYLWO LS
Whichever way the text was written initially, after we restack it into 7 columns, it will result in:
?QGNIHT
EHTDESU
NEDIWNE
DEHTFOT
YNAEESU
ACREBMA
HTDNARE
RAPREWO
OYNACXT
HCEHTMO
NROCDNA
LEHTDER
SIMEHTM
RFGNIPA
HTFELRE
EBMUCNE
ORFDEGR
CSERIAT
PPUEHTN
TAHTSIR
EMENIHT
OHEHTNI
IHCAERB
BEDEGAS
IWMOORE
DEREEPD
YNITAED
SAPFOSN
HTFOSLI
NAELDNA
AMISDNA
IAMEREH
ATEDYLT
CEHTDET
HGNILBM
TYLWOLS
NESERPT
RESNIIE
ERTHTIW
YLTARAP
UBREKCI
LTTILAE
DEVOMER
SEDYLWO
LFOTEMA
LOHEHTG
SAWYAWR
LS
LF
NI
OO
Now write the key on top and proceed with...
Step 2, The Keyed Columnar Transposition:
KRYPTOS KOPRSTY
0362514 -> 0123456
?QGNIHT ?HNQTIG
EHTDESU ESDHUET
NEDIWNE NNIEEWD
DEHTFOT DOTETFH
YNAEESU YSENUEA
ACREBMA AMECABR
HTDNARE HRNTEAD
RAPREWO RWRAOEP
OYNACXT OXAYTCN
HCEHTMO HMHCOTE
NROCDNA NNCRADO
LEHTDER LETERDH
SIMEHTM STEIMHM
RFGNIPA RPNFAIG
HTFELRE HRETELF
EBMUCNE ENUBECM
ORFDEGR OGDRREF
CSERIAT CARSTIE
PPUEHTN PTEPNHU
TAHTSIR TITARSH
EMENIHT EHNMTIE
OHEHTNI ONHHITE
IHCAERB IRAHBEC
BEDEGAS BAEESGD
IWMOORE IROWEOM
DEREEPD DPEEDER
YNITAED YETNDAI
SAPFOSN SSFANOP
HTFOSLI HLOTISF
NAELDNA NNLAADE
AMISDNA ANSMADI
IAMEREH IEEAHRM
ATEDYLT ALDTTYE
CEHTDET CETETDH
HGNILBM HBIGMLN
TYLWOLS TLWYSOL
NESERPT NPEETRS
RESNIIE RINEEIS
ERTHTIW EIHRWTT
YLTARAP YAALPRT
UBREKCI UCEBIKR
LTTILAE LAITELT
DEVOMER DEOERMV
SEDYLWO SWYEOLD
LFOTEMA LMTFAEO
LOHEHTG LTEOGHH
SAWYAWR SWYARAW
LS L S
LF L F
NI N I
OO O O
Now to the last...
Step 3, Out by columns downwards, left to right resulting in:
?ENDYAHROHNLSRHEOCPTEOIBIDYSHNAIACHTNREYULDSLLSLLNO
HSNOSMRWXMNETPRNGATIHNRARPESLNNELEBLPIIACAEWMTW
NDITEENRAHCTENEUDRETNHAEOETFOLSEDTIWENHAEIOYTEY
QHEENCTAYCREIFTBRSPAMHHEWENATAMATEGYEERLBTEEFOASFIO
TUETUAEOTOARMAEERTNRTIBSEDDNIAAHTTMSTEWPIEROAGR
IEWFEBAECTDDHILCEIHSITEGOEAOSDDRYDLORITRKLMLEHA
GTDHARDPNEOHMGFMFEUHEECDMRIPFEIMEHNLSSTTRTVDOHW
Reminds you of anything? ;)
The decryption process requires knowing the key and the rectangle size for the route transposition:
KRYPTOS and 86.
First we determine the line lengths to split the message:
86 mod 7 = 2. It means that two of the columns are going to be longer.
Which two and by how much?
The first two in our system (they are 0 and 3 for the person decrypting the message), with lengths 51 and 47.
The difference between those lengths will be the same (4) for 86 mod 7 regardless of the message length.
You may want to find out why as an excercise.
So we...
Step 1, Split the input as follows:
0 ?ENDYAHROHNLSRHEOCPTEOIBIDYSHNAIACHTNREYULDSLLSLLNO
1 HSNOSMRWXMNETPRNGATIHNRARPESLNNELEBLPIIACAEWMTW
2 NDITEENRAHCTENEUDRETNHAEOETFOLSEDTIWENHAEIOYTEY
3 QHEENCTAYCREIFTBRSPAMHHEWENATAMATEGYEERLBTEEFOASFIO
4 TUETUAEOTOARMAEERTNRTIBSEDDNIAAHTTMSTEWPIEROAGR
5 IEWFEBAECTDDHILCEIHSITEGOEAOSDDRYDLORITRKLMLEHA
6 GTDHARDPNEOHMGFMFEUHEECDMRIPFEIMEHNLSSTTRTVDOHW
Step 2, Write it in columns... (i omitted it to make Step 3 clearer, hence the following text is on its side)
Step 3, Reorder the columns according to the key:
0 ?ENDYAHROHNLSRHEOCPTEOIBIDYSHNAIACHTNREYULDSLLSLLNO
3 QHEENCTAYCREIFTBRSPAMHHEWENATAMATEGYEERLBTEEFOASFIO
6 GTDHARDPNEOHMGFMFEUHEECDMRIPFEIMEHNLSSTTRTVDOHW
2 NDITEENRAHCTENEUDRETNHAEOETFOLSEDTIWENHAEIOYTEY
5 IEWFEBAECTDDHILCEIHSITEGOEAOSDDRYDLORITRKLMLEHA
1 HSNOSMRWXMNETPRNGATIHNRARPESLNNELEBLPIIACAEWMTW
4 TUETUAEOTOARMAEERTNRTIBSEDDNIAAHTTMSTEWPIEROAGR
Step 4, Chop them into 86-letter long lines
(in groups of 4 of course, since 337/86 is > 3 but is <= 4)
0 ?END YAHR OHNL SRHE OCPT EOIB IDYS HNAI ACHT NREY ULDS LLSL LNO
3 QHEE NCTA YCRE IFTB RSPA MHHE WENA TAMA TEGY EERL BTEE FOAS FIO
6 GTDH ARDP NEOH MGFM FEUH EECD MRIP FEIM EHNL SSTT RTVD OHW
2 NDIT EENR AHCT ENEU DRET NHAE OETF OLSE DTIW ENHA EIOY TEY
5 IEWF EBAE CTDD HILC EIHS ITEG OEAO SDDR YDLO RITR KLML EHA
1 HSNO SMRW XMNE TPRN GATI HNRA RPES LNNE LEBL PIIA CAEW MTW
4 TUET UAEO TOAR MAEE RTNR TIBS EDDN IAAH TTMS TEWP IERO AGR
Step 5, Read the resulting 4 lines of the message backwards (reverse of the Step 1 of encryption). Done.
______________________________________________________________________________________________________________
If the same key KRYPTOS=0362514 was used to encrypt the 4th part, the decryption process would be as follows:
Let's say the number of columns for the route transposition was 49 or 21...
Step 1:
?OBKRUOXOGHULBSOLIFBBWFLRVQQPRNGKSSOTWTQSJQSSEKZZWATJKLUDIAWINFBNYPVTTMZFPKWGDKZXTJCDIGKUHUAUEKCAR
->
?OBKRUOXOGHULB
SOLIFBBWFLRVQQ
PRNGKSSOTWTQSJ
QSSEKZZWATJKLU
DIAWINFBNYPVTT
MZFPKWGDKZXTJC
DIGKUHUAUEKCAR
Step 2:
?SPQDMD
OORSIZI
BLNSAFG
KIGEWPK
RFKKIKU
UBSZNWH
OBSZFGU
XWOWBDA
OFTANKU
GLWTYZE
HRTJPXK
UVQKVTC
LQSLTJA
BQJUTCR
Step 3:
KOPRSTY KRYPTOS
0123456 -> 0362514
?SPQDMD ?QDPMSD
OORSIZI OSIRZOI
BLNSAFG BSGNFLA
KIGEWPK KEKGPIW
RFKKIKU RKUKKFI
UBSZNWH UZHSWBN
OBSZFGU OZUSGBF
XWOWBDA XWAODWB
OFTANKU OAUTKFN
GLWTYZE GTEWZLY
HRTJPXK HJKTXRP
UVQKVTC UKCQTVV
LQSLTJA LLASJQT
BQJUTCR BURJCQT
Step 4:
For 49 columns:
?QDPMSD BSGNFLA RKUKKFI OZUSGBF OAUTKFN HJKTXRP LLASJQT
OSIRZOI KEKGPIW UZHSWBN XWAODWB GTEWZLY UKCQTVV BURJCQT
For 21 columns:
?QDPMSD UZHSWBN HJKTXRP
OSIRZOI OZUSGBF UKCQTVV
BSGNFLA XWAODWB LLASJQT
KEKGPIW OAUTKFN BURJCQT
RKUKKFI GTEWZLY
Step 5:
For 49: TQCJRUBVVTQCKUYLZWETGBWDOAWXNBWSHZUWIPGKEKIOZRISOTQJSALLPRXTKJHNFKTUAOFBGSUZOIFKKUKRALFNGSBDSMPDQ?
For 21: YLZWETGIFKKUKRTQCJRUBNFKTUAOWIPGKEKTQJSALLBWDOAWXALFNGSBVVTQCKUFBGSUZOIOZRISOPRXTKJHNBWSHZUDSMPDQ?
Step 6: Breaking the cipher (most probably the same double-key Vigenere) and reading the message.
The key to the transposition is most probably different and a different route transposition may have been used.
In any case, it is all done by the book: Chapter 11 of the Army Field Manual on Basic Cryptanalysis.
Breaking keyed columnar transpositions is described in Chapter 12.
I would not be surprised if the 4th part gets broken in less than a month after this long four-year pause.
Moral of the story: Always Recover the Key.
Special thanks to: Elonka Dunin, Jim Gillogly, David Wilson.
Sean O'Neil <soneil@iss.net>
Reverse Engineering Guru,
X-Force Research Group,
Internet Security Systems Inc.
https://xforce.iss.net
PS: Yes, we all have our day jobs and we will all die eventually... BG 5.20