Solved

Crypto challenge 33 revisited

Posted on 2007-03-22
23
404 Views
Last Modified: 2007-03-23
In view of the debacle in posting the wrong ciphertext for http://www.experts-exchange.com/Other/Puzzles_Riddles/Q_22424196.html I have awarded points for the efforts to date and closed the question. I am offering a fresh set of points for breaking the code here.

The message is: (Underscores represent spaces)

n_ealas_bvo___ko_twrmaanasratos__rrWtera_eittlivfacewco_susr_nnofdeeecrdtB_p_rniriad_dc_tn__ae.aoborenuhied__naee_rhsyneluo.tmlrothd_tate_giOt_rfurad__nngeoe?dn_kyrhrs__Wr_la_i_eeomnhonhwgowbamsya_ahlethiT_nt__eir_sf_uo_tfeeeo_a_ndroe_w_i_ma_estcln_ha

The message should be 251 characters long. Just to review the clues so far; this is a double transposition cipher, its keys are 6 and 9 characters long and the message contains the text "has been keeping us entertained".
0
Comment
Question by:KelvinY
  • 8
  • 7
  • 5
  • +2
23 Comments
 
LVL 53

Expert Comment

by:Infinity08
ID: 18778154
There's still something I seem to be misinterpreting.

Can you confirm that this is the way to encrypt a string ([]'s are used to show the string boundaries) :

The original text :

    [I am here, am I ?]

key of length 6, so ordered in 6 columns :

    [I am h]
    [ere, a]
    [m I ?#]

(note that the # is a placeholder that means : no character, empty)

After transposition of the columns (3, 6, 2, 1, 5, 4), we might get :

    [ah I m]
    [eare ,]
    [I# m? ]

So, in one line, we have :

    [aeIha r Iem  ?m, ]

Now, we use a key of length 9, so we organise the string in 9 columns :

    [aeIha r I]
    [em  ?m, #]

And after transposition of the columns (7, 8, 2, 3, 9, 1, 4, 6, 5), we might get :

    [r eIIah a]
    [, m #e m?]

So, finally, we have :

    [r,  emI Iaeh  ma?]


Is that correct ??? Because following this procedure backwards does not seem to get me any good results for your text.
0
 
LVL 16

Assisted Solution

by:Peter Kwan
Peter Kwan earned 25 total points
ID: 18778226
Hi KelvinY,

I have tried my best to get the logic and still cannot find the plaintext you gave.... Here is my logic:

1) 251/9 = 8.xxx, which means there are 8 long columns of 28 characters and 1 short column of 27 characters.
2) Two consecutive characters in columns in the plaintext will yield in two consecutive characters in row in the second matrix.
3) Since "p" is one of characters that only occurs once in the plaintext/ciphertext, and is given in your plaintext, I use this to fix the position and find the second key of the column "hepsrd" and "_kgni", by moding the position of each two characters by 28.
4) Then I use the second key and loop 6! times (since without any idea, so just use brute-force search) to find the first key to best match.

However, I cannot find anything sensible.
0
 
LVL 8

Author Comment

by:KelvinY
ID: 18778896
Infinity08

Your method is correct. Bear in mind that since placeholders are discarded some of the transposed columns are different lengths, which does complicate the process of reversing the procedure somewhat. The keyspace for this cipher is huge, which also makes your task much harder.

pkwan

It sounds like you're on the right track. In applying this cipher the 6 character key was used for the first transposition, which would break the 31 characters of plaintext that you were given into 5 blocks of 5 and 1 of 6. The second transposition really mixes things up, so that in the end you only find 2 or 3 characters from the given plaintext next to each other in the final ciphertext.

The problem with this cipher is that there are so many permutations for the keys, 6! * 9!, that there are over 261 million (261 273 600 to be exact)  possible keys, even though the key lengths are known. As a bonus clue I will post a diagram showing where the given plaintext characters have ended up in the final ciphertext, otherwise this is just going to be too difficult.

The characters "" are distributed in the final ciphertext as

n....a........k....r........t........e....i........e.........n....e........p.................e............._........s....u........h....t...i.............g....d........_.............n........b....a....e........_....s............._....e........e.*...n...

where . represents a placeholder for a character, _ represents a space and the # indicates an empty position, which should give position of the short column in the key.
0
 
LVL 2

Assisted Solution

by:TeamSrv
TeamSrv earned 25 total points
ID: 18780133
Hi KelvinY,
I just want to make sure I am looking at this right.  The * character represents a place holder and when it is written out into 9 columns, (without transposing) the * character will be in the last column, 7 positions from the bottom.  Is that right?
0
 
LVL 8

Author Comment

by:KelvinY
ID: 18780255
TeamSrv

> 7 positions from the bottom
The * will appear in the bottom row. It is just a placeholder and there is no character in that position. Where the columns are rearranged according to the key it will appear in the last column on the bottom row.  Just to remove all confusion here is the final ciphertext, showing known text distribution from the clue, in 9 columns.

n....a...
.....k...
.r.......
.t.......
.e....i..
......e..
.......n.
...e.....
...p.....
.........
...e.....
........_
........s
....u....
....h....
t...i....
.........
g....d...
....._...
.........
.n.......
.b....a..
..e......
.._....s.
.........
..._....e
........e
.*...n...

So, the second column, which ends with the * was the last column before the second key was applied.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 18780307
KelvinY - now you've got me really confused ... you're reading the string row by row, and not column by column, as a normal transposition cipher would do (see my earlier example).

Which is the way you did it ? Because if it's per row, I've been doing it wrong all along lol.

Oh, and is it the same way for the first key ? ie. also row by row ?
0
 
LVL 4

Expert Comment

by:dagesi
ID: 18780432
Boy, we're embarassing, aren't we...
Ok, one more Q just for clarity...
Though your crypted string is 251 characters in length, this string:
n....a........k....r........t........e....i........e.........n....e........p.................e............._........s....u........h....t...i.............g....d........_.............n........b....a....e........_....s............._....e........e.*...n...
is actually 252 (to fill the matrix), correct?
0
 
LVL 8

Author Comment

by:KelvinY
ID: 18780565
This day just keeps getting better. Yes, I've screwed up again. Here's the ciphertext, with the placeholder in position, arranged correctly, I hope.

n....a........k....r........
t........e....i........e...*
......n....e........p.......
..........e............._...
.....s....u........h....t...
i.............g....d........
_.............n........b....
a....e........_....s........
....._....e........e....n...

dagesi - yes, the text is 252 characters long with the placeholder padding it out.
0
 
LVL 8

Author Comment

by:KelvinY
ID: 18780603
or as it should have appeared in columns

nt...i_a.
.........
.........
.........
.........
a...s..e_
..n......
.........
.........
.e.......
...eu...e
..e......
.........
.........
ki...gn_.
.........
.........
.........
.........
r...hd.se
..p......
.........
.........
.e....b..
..._t...n
.........
.........
.*.......
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 18780704
Well, I've brute-forced the hell out of this, and I don't get any readable results.

I've made my own 251 character string, and encoded it just like my earlier example (manually), and my brute-force tool has no problem with that. But with yours ... it seems I'm still misunderstanding the correct procedure you used to encrypt the string.
0
 
LVL 4

Assisted Solution

by:dagesi
dagesi earned 25 total points
ID: 18780901
Not that this helps anyone else yet, but by my counting there are no more than 336 possible choices...
based on the placement of the letters that Kelvin provided us...
0
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 
LVL 8

Author Comment

by:KelvinY
ID: 18781337
And so it continues...the puzzle from hell. Keeping up my 100% record of screw ups the wrong text has again been posted. It should have been

n....a........k....r........t........e....i........e.........n....e........p.................e............._...*....s....u........h....t...i.............g....d........_.............n........b....a....e........_....s............._....e........e....n....

So that when you arrange it in rows you get

n....a........k....r........
t........e....i........e....
.....n....e........p........
.........e............._...*
....s....u........h....t...i
.............g....d........_
.............n........b....a
....e........_....s.........
...._....e........e....n....
0
 
LVL 4

Expert Comment

by:dagesi
ID: 18781508
lol... you don't make me feel quite as bad for the mistakes I made/make in the cryptopuzzles... =]
0
 
LVL 8

Author Comment

by:KelvinY
ID: 18781593
Right. I've checked and double checked it now. I have also tried it with a placeholder inserted to pad out to 252 characters, making it evenly divisible by 6 and 9. Just so we're fully clear here is the full ciphertext and below it the clue based on the known phrase "has been keeping us entertained".

n_ealas_bvo___ko_twrmaanasratos__rrWtera_eittlivfacewco_susr_nnofdeeecrdtB_p_rniriad_dc_tn__ae.aoborenuhied__na#ee_rhsyneluo.tmlrothd_tate_giOt_rfurad__nngeoe?dn_kyrhrs__Wr_la_i_eeomnhonhwgowbamsya_ahlethiT_nt__eir_sf_uo_tfeeeo_a_ndroe_w_i_ma_estcln_ha

n....a........k....r........t........e....i........e.........n....e........p.................e............._...#.....s....u........h....t...i.............g....d........_.............n........b....a....e........_....s............._....e........e....n...

All of the characters in the lower text should appear in the same positions in the full ciphertext. That can be confrmed by pasting into a text processor with a fixed pitch font like Courier.
0
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 425 total points
ID: 18782097
Aaaah, that's better heh :)

"The movie industry has been keeping us entertained for well over a hundred years now. One of the most enduring art forms is the animated cartoon. Who was the creator of a Warner Brothers cartoon featuring a black and white cat and a small yellow bird?"
0
 
LVL 53

Accepted Solution

by:
Infinity08 earned 425 total points
ID: 18782112
And the answer if I'm not mistaken is : Isadore "Friz" Freleng
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 18782140
The keys :

3 4 1 5 2 6  :  tweety

5 8 3 9 1 6 7 4 2 : sylvester
0
 
LVL 4

Expert Comment

by:dagesi
ID: 18782200
>Infinity08...
congrats... I'm still leagues away from figuring it out myself... barring incredible luck... =]
0
 
LVL 2

Expert Comment

by:TeamSrv
ID: 18782977
Hey KelvinY
I really liked this puzzle.  I haven't had to think this hard in a long time.  I'm looking forward to the next one.  Keep the puzzles coming :)

0
 
LVL 8

Author Comment

by:KelvinY
ID: 18783509
Well done, Infinity08. It didn't actually take that long once the correct ciphertext was posted. Sorry about the confusion everyone. I hadn't originally intended to post a challenge and ended up throwing it together in too much of a hurry. Please post a brief description of how you cracked this code if you have the time, Infinity08.

TeamSrv, I'm going to be taking some time of from EE to go travelling for about a month, but I will certainly look at resuming the series when I return.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 18783558
>> Please post a brief description of how you cracked this code if you have the time, Infinity08.

The plaintext you gave : "has been keeping us entertained" was a big help. In 6 columns, that gave :

......
has_be
en_kee
ping_u
s_ente
rtaine
d.....
......

The relevant column parts are : "hepsrd", "ani_t", "s_nea", "_kgni", "be_tn" and "eeuee".

These six short strings can be used to find the second key, using this :

n....a........k....r........
t........e....i........e....
.....n....e........p........
.........e............._...#
.....s....u........h....t...
i.............g....d........
_.............n........b....
a....e........_....s........
....._....e........e....n...

to get this :

.....s....u........h....t...
....._....e........e....n...
.....n....e........p........
a....e........_....s........
n....a........k....r........
i.............g....d........
_.............n........b....
t........e....i........e....
.........e............._...#

Notice that you can read the six short strings I determined earlier vertically, and that the place holder # is at the end.

So, the second key is :

5 8 3 9 1 6 7 4 2

We can now use that second key to do the first transposition on the ciphertext :

n_ealas_bvo___ko_twrmaanasra
tos__rrWtera_eittlivfacewco_
susr_nnofdeeecrdtB_p_rniriad
_dc_tn__ae.aoborenuhied__na#
ee_rhsyneluo.tmlrothd_tate_g
iOt_rfurad__nngeoe?dn_kyrhrs
__Wr_la_i_eeomnhonhwgowbamsy
a_ahlethiT_nt__eir_sf_uo_tfe
eeo_a_ndroe_w_i_ma_estcln_ha

becomes :

ee_rhsyneluo.tmlrothd_tate_g
eeo_a_ndroe_w_i_ma_estcln_ha
susr_nnofdeeecrdtB_p_rniriad
a_ahlethiT_nt__eir_sf_uo_tfe
n_ealas_bvo___ko_twrmaanasra
iOt_rfurad__nngeoe?dn_kyrhrs
__Wr_la_i_eeomnhonhwgowbamsy
tos__rrWtera_eittlivfacewco_
_dc_tn__ae.aoborenuhied__na#

The latter is read column by column to get :

eesani_t_eeu__O_od_osaetWscr_rha_r__ha_llr__ts_neaflrnynntsuar_ndoh_r_W_erfibaitalodTvd_eeuee_o_er.o_en__eaa.wet_no_ot_c__nmebmir_kgniol_deoehtrrmti_ooteoaBrtenlnt___w?hiuhepsrdwvhds_fmngfi_tr_a_oaetcnuakwcdalionybe_tnr_araw_e_itshmcn_hafrrsoagadeasy_

or written out in 6 columns :

eesani_t_eeu__O_od_osaetWscr_rha_r__ha_llr
__ts_neaflrnynntsuar_ndoh_r_W_erfibaitalod
Tvd_eeuee_o_er.o_en__eaa.wet_no_ot_c__nmeb
mir_kgniol_deoehtrrmti_ooteoaBrtenlnt___w?
hiuhepsrdwvhds_fmngfi_tr_a_oaetcnuakwcdali
onybe_tnr_araw_e_itshmcn_hafrrsoagadeasy_

Here it's easy to spot the first key : just two columns need to be moved - the one starting with 'T' and the one starting with 'h' are moved to the front to get :

Tvd_eeuee_o_er.o_en__eaa.wet_no_ot_c__nmeb
hiuhepsrdwvhds_fmngfi_tr_a_oaetcnuakwcdali
eesani_t_eeu__O_od_osaetWscr_rha_r__ha_llr
__ts_neaflrnynntsuar_ndoh_r_W_erfibaitalod
mir_kgniol_deoehtrrmti_ooteoaBrtenlnt___w?
onybe_tnr_araw_e_itshmcn_hafrrsoagadeasy_

The first key is thus :

3 4 1 5 2 6

And reading the decrypted text column by column gives :

The_movie_industry_has_been_keeping_us_entertained_for_well_over_a_hundred_years_now._One_of_the_most_enduring_art_forms_is_the_animated_cartoon._Who_was_the_creator_of_a_Warner_Brothers_cartoon_featuring_a_black_and_white_cat_and_a_small_yellow_bird?
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 18783577
Ironically, after your last post with the correct placeholder position, it took me only 5 minutes to find the solution manually. While I had spent several days manually trying to decode the other strings, also using brute-force tools specifically written for this encryption, etc.

Well, it was fun :) Thanks, KelvinY
0
 
LVL 4

Expert Comment

by:dagesi
ID: 18784327
Hmmm... I must have had spaces or something in there wrong... for some reason I couldn't get my 'p' and 'r' on the same line as the other letters...
Ah well... can't be good at everything... =]
0

Featured Post

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Suggested Solutions

Short answer to this question: there is no effective WiFi manager in iOS devices as seen in Windows WiFi or Macbook OSx WiFi management, but this article will try and provide some amicable solutions to better suite your needs.
In this article, I will show you HOW TO: Perform a Physical to Virtual (P2V) Conversion the easy way from a computer backup (image).
Excel styles will make formatting consistent and let you apply and change formatting faster. In this tutorial, you'll learn how to use Excel's built-in styles, how to modify styles, and how to create your own. You'll also learn how to use your custo…
When you create an app prototype with Adobe XD, you can insert system screens -- sharing or Control Center, for example -- with just a few clicks. This video shows you how. You can take the full course on Experts Exchange at http://bit.ly/XDcourse.

706 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

17 Experts available now in Live!

Get 1:1 Help Now