Forum

[solved] Challenge "Double Column Transposition"

[solved] Challenge "Double Column Transposition"  

  By: admin on May 7, 2010, 2:34 p.m.

The double columnar transposition is considered one of the best manual encryption systems. Many secret organizations have made use of it or still use it today. As there are only a few publications on this method, it is not clear if and how a well-constructed double transposition cipher can be broken.
Read more...

 Last edited by: admin on Oct. 31, 2021, 2:54 a.m., edited 2 times in total.

Re: Challenge "Double Columnar Transpostion"  

  By: Veselovský on Oct. 14, 2011, 3:35 p.m.

Hi,
Have you looked at a link in the description file?

"More information is available(in German) at: http://www.heise.de/tp/r4/artikel/26/26876/1.html"
There is an example of a columnar transposition.

Plaintext is:
ERWARTE MORGEN NEUE LIEFERUNG
Keyword is:
TELEPOLIS

According to them the corresponding ciphertext is:
RGEAN EMEGW EFEUN TEURN ROLERI

But I think it should be:
RGEAN EMEGW EFEUN TEURN ROLIE R

Should I expect similar mistakes also in the challenge itself???
Are the authors of the web page same as authors of the challenge?
Or they performed the transposition in a different way than is standard?
I do not understand German, so I can not figure this out.

Re: Challenge "Double Columnar Transpostion"  

  By: Veselovský on Oct. 14, 2011, 3:46 p.m.

In fact, the resulting ciphertext is correct, but they made a mistake in the middle step.
They have:
EEILLOPST
———
RAMWETROE
GNEEUENLR
EEGFNURI

…and it should be:
EEILLOPST
———
RAMWETROR
GNEEUENLI
EEGFNURE

I assumed that the middle step was correct and I only checked the final ciphertext produced from that step.

Re: Challenge "Double Columnar Transpostion"  

  By: Veselovský on Oct. 16, 2011, 2:15 a.m.

Hints from PDF file:

Here are a few hints:
The cleartext is written in English.
Both key words are English as well.
The key words have more than 20 letters each.
The length of the two key words is different.

Does "Both key words are English as well." mean that the keywords are single English words or they can be made of more words?

Is it this type of keyword:
"electroencephalograph" (which is single word of length 21)

or this type of keyword:
"todayisalovelydayeventhoughitrains" (it is made of 9 English words and its total length is 34)

If keywords can be made of more than one word, then the hint is of no help, because I can imagine infinitely many such keywords, the more that the lower bound of the length is given, not upper.
(usually an upper bound is given as a hint, here I can choose from interval (21,infinity))

So logically I assume, that the hint to be a real hint, means that the keyword is single English word.
Can someone confirm this?

Re: Challenge "Double Columnar Transpostion"  

  By: fretty on Oct. 16, 2011, 10:34 a.m.

They aren't going to make it that easy that you just search for words with 21 letters or more…that would narrow down the possible keys greatly.

The whole point of this challenge is to inspire people to make new methods of breaking this type of cipher, not to do a routine decryption using the hint. This is not a "simplified" version of a cipher like in level 1 and 2 challenges, where you are given many hints that together contribute to a solution.

The hints here are not really to act as hints, but to confirm the difficulty of the cipher itself. The fact that the keywords are longer than 20 letters is mostly irrelevant, but serves as a reminder that this is not an easily breakable cipher (so that in your analysis you may ignore "small" keywords that you would usually have to check).

This challenge uses parameters that are considered fully secure even by todays standards. It will take fresh ideas to break.

Re: Challenge "Double Columnar Transpostion"  

  By: Veselovský on Oct. 16, 2011, 11:37 a.m.

There are still lots of words in English of length bigger than 20.
Some are crazy and you probably would never use them, but they satisfy English grammar so we must count them as words.
For example: Antidisestablishmentarianism.
By extension of existing words by the addition of prefixes and suffixes we can create unimaginable many words of length bigger than 20.
So it would not be a big hint too, but compared to the given hint at least small decrease of possibilities.

Re: Challenge "Double Columnar Transpostion"  

  By: Veselovský on Oct. 16, 2011, 11:51 a.m.

Wouldn't it be almost same, to inspire people to make new methods, by saying that lengths are 37 and 43 for example?
I think there is no good method even if you know the lengths (of course not for small lengths when brute force is effective).
And then, if someone finds a method to solve cases when lengths are known, to publish a new challenge with unknown lengths.

Re: Challenge "Double Columnar Transpostion"  

  By: realkus on Oct. 16, 2011, 10:35 p.m.

Should I expect similar mistakes also in the challenge itself???
Sorry for the mistake in the heise online article. Nevertheless, the version in the challenge in MTC3 is correct. I built the challenge cipher text with CrypTool v1. There should be no mistake in it.

Does "Both key words are English as well." mean that the
keywords are single English words or they can be made of more
words?
They can be made of more than one word. My goal was to make the challenge as realistic as possible, and in reality a password can easily be a whole phrase.

Re: Challenge "Double Columnar Transpostion"  

  By: fretty on Oct. 16, 2011, 11:28 p.m.

But you are treating this as "we must find the two keywords by trying all possible words of length 21 or more". That method of breaking a cipher is already known and is called "brute force". It is infeasible in this instance…and the challenge has been purposefully made in this way.

The creators of the challenge are not going to make it that easy…the hint for this challenge is irrelevant as an "aid", it is not there to make the challenge easier but to clarify certain details that make the analysis of the cipher feasible enough once an intended analysis is taken. This is different to ciphers in levels 1 and 2 since these ones are intended to be solved with relative ease and with direct use of the hints.

Re: Challenge  

  By: Scryer on Dec. 4, 2013, 8:27 p.m.

There aren't lots of individual words longer than 20 letters. In my standard word list (based on an unabridged dictionary) of 308,081 words, I see:

99 of length 21
49 of length 22
19 of length 23
6 of length 24
1 of length 25
0 of length 26-28
1 of length 29

If that's all there was to this challenge, it would be easily brute-forceable.

Re: Challenge  

  By: Veselovský on Dec. 19, 2013, 11:50 p.m.

This is my solution, how much will I get for it? ;-)

This is first key for decryption:
{376,389,336,477,230,147,5,9,317,14,587,591,167,493,70,352,486,503,145,415,469,2,36,553,435,487,337,188,568,501,179,555,74,305,334,340,593,202,445,377,16,385,62,1,92,407,332,524,299,418,388,515,521,528,433,545,162,584,463,163,509,427,575,370,279,371,497,447,206,454,183,471,101,146,409,438,109,455,365,113,87,187,347,542,373,81,300,132,85,217,538,30,150,460,316,285,51,582,121,112,399,571,125,517,229,135,168,494,546,261,151,478,152,32,52,78,479,410,559,126,119,91,298,453,465,296,141,441,61,294,129,50,278,485,420,386,93,343,406,49,211,45,547,209,37,495,392,17,124,140,335,565,47,431,508,502,289,339,105,182,19,35,28,430,269,439,421,118,400,11,178,90,138,174,207,161,381,103,548,437,180,44,398,240,348,111,353,165,144,461,563,384,577,267,246,273,250,466,413,350,567,42,539,451,231,257,3,351,131,492,393,22,186,7,59,561,94,175,374,424,512,543,39,198,297,46,507,516,275,290,12,247,262,184,4,429,357,172,550,64,171,344,464,520,484,195,483,123,560,318,480,578,271,127,408,166,444,537,489,482,55,242,153,88,18,233,8,474,440,277,449,73,265,108,448,315,40,65,102,510,253,33,173,530,338,154,142,390,403,263,215,157,266,312,221,181,158,72,254,270,252,544,220,506,10,56,227,432,286,525,15,382,226,592,368,333,225,134,255,100,359,536,80,475,155,293,590,401,459,326,476,576,425,387,228,311,411,329,423,462,139,572,306,434,67,21,77,164,122,450,304,519,349,274,71,481,133,498,283,116,500,204,75,402,41,416,356,200,417,586,452,276,328,58,358,412,436,541,251,136,355,23,532,115,130,143,307,523,443,446,527,210,345,473,504,239,396,308,24,96,160,245,199,194,588,341,488,98,458,137,364,295,314,259,363,292,34,20,531,303,557,117,581,354,320,232,540,205,291,589,249,551,496,558,213,149,583,66,457,192,256,189,170,43,214,323,99,470,554,128,310,569,169,313,177,69,499,106,534,319,331,442,325,6,360,372,107,68,26,53,243,309,31,241,467,268,301,258,82,203,288,218,511,287,176,580,549,379,552,366,234,223,513,369,272,505,60,191,397,573,414,224,419,190,490,216,468,375,428,222,29,219,27,378,529,564,185,526,518,57,562,86,89,281,514,362,342,367,383,302,13,535,426,156,585,394,566,54,472,522,260,322,491,63,76,556,405,95,395,391,97,104,84,533,327,244,79,574,248,114,282,193,264,83,238,120,208,570,48,148,196,284,237,212,456,330,380,25,197,159,422,38,280,361,201,579,321,324,404,346,110,236,235}

This is second key for decryption:
{301,443,212,370,178,58,312,216,347,118,486,495,352,40,239,132,166,128,339,456,383,155,581,181,362,344,462,521,217,359,585,47,234,207,430,246,431,398,364,349,557,2,321,112,123,533,439,273,120,282,230,91,232,516,363,235,519,185,288,44,337,524,399,561,392,148,93,36,279,152,257,510,80,274,535,556,208,196,75,332,411,43,172,194,403,51,579,190,541,83,503,575,412,421,520,284,250,219,165,189,341,167,496,271,55,434,507,195,105,560,563,182,578,156,38,69,221,237,146,111,404,475,4,197,318,63,572,384,537,249,453,78,54,228,299,141,504,382,413,258,23,272,451,375,252,314,525,586,77,66,264,365,428,231,34,350,358,573,424,440,554,416,13,21,538,351,160,484,407,576,564,41,506,322,193,405,547,540,571,256,268,102,122,188,310,26,388,270,418,479,22,515,426,39,29,142,110,354,81,555,336,204,562,297,269,300,425,289,508,169,82,391,99,308,517,553,491,45,552,500,265,145,408,435,457,326,505,68,32,470,492,226,17,35,410,460,465,163,295,262,309,433,432,290,386,161,401,353,175,198,24,467,8,327,446,248,330,115,369,549,546,582,532,117,489,493,89,452,241,385,9,191,157,261,236,542,131,200,544,499,86,437,140,287,377,291,469,319,101,57,459,50,15,25,497,449,124,390,143,487,205,244,371,569,488,543,526,170,92,393,259,548,454,409,278,56,76,498,580,52,307,27,450,199,104,530,59,96,129,536,90,529,334,61,180,305,293,192,30,72,567,345,210,313,402,422,346,436,100,227,565,306,71,149,283,245,512,559,260,253,494,511,474,539,570,12,298,513,286,528,320,333,5,224,415,455,366,480,240,329,368,70,445,374,420,276,551,466,116,135,461,518,88,98,343,114,139,444,478,19,379,292,577,275,400,203,263,206,558,342,138,254,1,458,387,127,468,164,7,238,37,42,186,463,348,361,218,380,267,464,427,501,46,243,550,209,126,406,471,335,225,373,85,448,376,64,473,171,16,179,531,315,121,215,108,266,211,73,162,144,325,311,183,62,158,130,255,65,33,242,476,277,522,481,159,106,74,11,316,395,360,153,20,151,545,136,31,357,566,340,328,229,79,28,324,10,317,176,147,53,84,534,133,429,125,281,294,107,223,372,119,514,509,247,48,381,3,202,485,584,187,177,482,201,447,220,302,587,285,438,60,6,304,483,95,338,367,574,490,502,168,222,233,441,583,214,67,355,423,568,356,184,331,378,14,414,280,323,527,103,296,419,94,213,523,397,173,87,396,113,472,97,174,49,417,109,394,18,251,477,154,137,442,303,389,134,150}

Re: Challenge  

  By: Veselovský on July 6, 2014, 6:23 p.m.

I think it would be fair to inform users that they should not except to receive any points for this challenge anymore, since the solution is publicly known.

I wonder why nobody from MTC3 team has informed us about this, or they take it as a matter of course that we should know it?

I myself was still running my program from time to time (when my PC had no other task to do) to see if I will have some luck to find the plaintext, but today I found that the solution was publicly disclosed (at least) a week ago.

Re: Challenge  

  By: aurelie on July 8, 2014, 12:36 p.m.

I wonder why nobody from MTC3 team has informed us about this, or they take it as a matter of course that we should know it?

Thank you for hinting at this issue, Viktor! No, we didn't take it for granted that you know about it.

I set the status of this challenge to "solved" which means that you can still send in your solution but won't be rewarded with points. Take it as an exercise!

If you're interested in how the challenge has been solved, please refer to the corresponding Cryptologia article published on June 13.
Plus there's a small article in our own news section summarizing the events and the available challenges on MTC3.

I hope that you enjoy our three "new" DCT challenges (search for "Double column transposition reloaded")!

Re: [solved] Challenge  

  By: bgr on Aug. 25, 2014, 9:30 p.m.

Hallo,
ich habe vor einiger Zeit die Lösung per Mail eingesendet, bis jetzt aber noch keine Rückantwort bekommen. Ist die Verzögerung urlaubsbedingt oder ging die Mail unter?
Bernhard

Re: [solved] Challenge  

  By: bgr on Feb. 26, 2015, 4:18 p.m.

Ich konnte mit Toolunterstützung den richtigen Klartext ermitteln, ebenso den Schlüssel für die 1. und 2. Spaltentransposition. Auch das Schlüsselwort für die 2. Spaltentranspositon konnte ermittelt werden. Wie mir "be" mitgeteilt hat, gilt die Challenge allerdings erst als gelöst, wenn auch das richtige Schlüsselwort für die 1. Spaltentransposition mitgeteilt werden kann.

Das Schlüsselwort manuell zu ermitteln schlug bei mir bisher fehl, auch wenn ich meine eine "kleine" Gemeinsamkeit in beiden Schlüsseln erkennen zu können. Allerdings kann ich den Rest des Schlüsselworts nicht ermitteln.

Gibt es hierfür ein Tool, um bei bekanntem Schlüssel mögliche Schlüsselwörter (in englisch) ableiten zu können?

Bernhard


Currently 29 guests and 0 members are online.
Powered by the CrypTool project
© 2009-2021 MysteryTwister team