http://qs1969.pair.com?node_id=550450

This is a compliment to my recent obfuscated post, Vigenére cipher. In honor of Charles Babbage (pictured here so you don't have to squint too hard), who is credited with breaking Vigenére's cipher ca. 1854, but his method was not published until several years later, and as a result credit for the development was instead given to Friedrich Kasiski, who made the same discovery some years after Babbage.

What is now commonly referred to as the Kasiski examination allows a cryptanalyst to deduce the length of the keyword used in the polyalphabetic substitution cipher. Once the length of the keyword is discovered, the cryptanalyst lines up the ciphertext in N columns, where N is the length of the keyword. Then, each column can be treated as the ciphertext of a monoalphabetic substitution cipher. As such, each column can be attacked with frequency analysis

This homage to Charles Babbage uses this approach.

$_='`$t` `.=lc for<>;u($_` )for` 3..``6;%t=qw ` `(a 82 b 15 c 28 d 43 e ` `127 f 22 ` g 20 h 61 i 70 ` `j 2 k 8 ```````l 40 m 24 n 67 ` o 75` ` p 19 q 1` ` r ` 60 s 63 t ` 91 ` u 28 v 1 `0 w ` 24 x 2 y ` `20 ` ` z 1);$k= k() ` ``;$d+=$t{$` `_}f o``r keys%t;$l =$d` /in` ``t(`length($t)/ $k)/100 ` ;map{%n=f(t($_));@g=b(1,\` `%n);$y.= i(\@g)}0..$k-1;@_=(a..z); map{@$_= @_;if($;++){for$"(2..$;){ pu ` sh` `` @$_,shift@$_} `` `` `}` }@_;map{$p=i` n` d`ex `((join\'\',` ` ` `@`{(sp `lit//,$y)[$c ` ]}),$_);` `$o```.=$p>=0?$`a` `` [ $p]: $_;$c+=$c<$k-1?1 ````: `-$` ``k+1}split//,$t;s ``ub \'b{my($e,$s `,@g)=@_;p ` ``ush@ `g`,[$_,(s pli` `` ``t//,\'#\' ``x in` `` `t($$s{`$_}*$e )`)]for ` `+sort+keys%$s;retur ```n@g}s` ub\'c{my$x=shift;$x=g($x,shift ```)while@_; return$x}sub\'f{my%d;$d{$_}++f` or grep/[a-z]/ ,split//,shift;$d{$_}||=0for a..z;return%d}su b\'g{my($x,$y)=@_;($x,$y)=($y,$x%$y)while$y;r eturn$x}sub\'i{my($g,@c)=@_;map{push@c,o(v($g),` `` ` $$g[0][0]);w($g)}0..25;return(map{$_->[1]}sort{$` b-`` >[0]<=>$a->[0]}@c)[0]} sub\'k{my@g;for(sort{$s{` `$b}`` <=>$s{$a}}keys%s){last ``if$s{$_}<3;next unless y `/a-``` z//>2;my@f ;push@f,(pos `($t)-3)while$t=~/$_/g;m` ````````y$g=c(n(@f) );`$g```` >2&&push@g,$g}return c(@` g)}sub\'n{my$o= shift;return map{$_-$o}@_ }sub\'o{my($g,$w) =@_;my$c=0;map{map{/\+/&&` $c++;/\-/&&$c--}@ $_}@$g;return[$c,$w]}sub\' `t{my($o)=@_;my$c= 0;my$r;map{$r.=$_ unless( `$k-$o+$c)%$k;$c++} split//,$t;$r=~s/[^a-z]/ /g;return$r}sub\'u{ my$l=$_[0];$s{substr($t` ,$_,$l)}++for 0..(le ngth($t)-$l)}sub\'v{my($ `m)=@_;my@g=b($l,\%t );$s=\@g;$z=0;map{$x=0;ma `p{$$s[$z][$x]=$$m` [$z][$x]eq\'#\'&&$$s[$z][ `$x]eq\'#\'?\'+` \':\'-\';$x++}@$_;$z++}@$m `;return$s}sub \'w{$R=shift;push@$R,shif` `t@$R}print" Key: $y\nPlaintext:\n$o\`` `n";';s-\s \s+--gmx;s&`&&gm;eval#;` #etur#`` `#my($x($v());$y=$z#`#` ##```` ``# charles #`` #`````` ````# babbage #` #`````````` # # # # #` # ` ` ` `# ##`

This reads in ciphertext via STDIN. If saved as babbage.pl, and Vigenére cipher is saved as vigenere.pl, you can see it in action via:

perl vigenere.pl | perl babbage.pl

I have a more fully featured (unobfuscated, commented, and POD'd) version which even produces HTML output detailing the results of the Kasiski examination, and optionally the letter frequency analysis charts, which I will post to the code contributions section shortly. But not too quickly, as it's basically a giant spoiler for this :-)

I'd like to give a special thanks to liverpole, as without his Latent Image Obfuscation Generator, I wouldn't have been so easily able to generate an ascii 'portrait' of Charles Babbage that I could then turn into code.



--chargrill
$,=42;for(34,0,-3,9,-11,11,-17,7,-5){$*.=pack'c'=>$,+=$_}for(reverse s +plit//=>$* ){$%++?$ %%2?push@C,$_,$":push@c,$_,$":(push@C,$_,$")&&push@c,$"}$C[$# +C]=$/;($#C >$#c)?($ c=\@C)&&($ C=\@c):($ c=\@c)&&($C=\@C);$%=$|;for(@$c){print$_^ +$$C[$%++]}

Replies are listed 'Best First'.
Re: Breaking the indecipherable cipher, courtesy Charles Babbage.
by turo (Friar) on May 19, 2006 at 18:34 UTC

    I do not remember very well the theory, but one of the hardest part of the kasiski analysis was to discover which was the key length; and the fact is that you can only discover it, if the length of the cipher text is longer enough and the key shorter enough (we'll need practice to know this). isn't it?

    Anyway, in those years, neither computer (i do not include the mechanic machine for calculations made by Babage) nor high level programming languages exists. Now, we can break that code by brute force (the only important thing, is to know if the ciphertext is a polialphabetic cipher or not) for discovering the key length with the frequency analysis help ... a'm i wrong?

    I think i must read those old books of cryptography to analyse with great appetite your code ... but i'm curious and i cannot wait, did you use brute force, or another intersting algorithm for breaking the vigenere cipher? I mean, on your last post, you said that you've been written a extrange method to break the vigenere cipher.


    Saludos :-)


    turo

    PS: umm, i've made a code breaker script for the scitale cipher ... but it have some problems with thick scitales ^_^> ... i hope to submit it later, when i have some spare time. cheers

    PS2: i forgot to say, great work! (i didn't know Babage break the Vigenere cipher before than Kasiski did)

    perl -Te 'print map { chr((ord)-((10,20,2,7)[$i++])) } split //,"turo"'

      You're absolutely correct - the cipher text must be long enough and in a recognizable langauge, because my code looks for repeated substrings at some interval, and compares the letter fequency distribution of every Nth letter to the standard letter frequency distribution for a given langauge (English in my case ;). In fact it looks for multiple repeating substrings to better try to zero in on the likely key length. Once repeated substrings are found, it computes the greatest common factor of the intervals for a given repeat, and then computes the greatest common factor for those greatest comman factors, and uses that as the key length.

      That doesn't always work :)

      I've had mixed results - if I rename vigenere.pl to just "chargrill" and encode the same text, the above code can't find any common factors, and then fails. It would actually take a fair amount of refactoring to account for this.

      Honestly, I think my algorithm for figuring out what key letter would make an encrypted cipher string of every Nth character matches the standard letter frequency distribution is the most ... interesting. I couldn't think of a better way to do it than with the human eye, and I think my algorithm gets as close to a visual inspection of peaks and valleys of letter frequency charts as I could think of...



      --chargrill
      $,=42;for(34,0,-3,9,-11,11,-17,7,-5){$*.=pack'c'=>$,+=$_}for(reverse s +plit//=>$* ){$%++?$ %%2?push@C,$_,$":push@c,$_,$":(push@C,$_,$")&&push@c,$"}$C[$# +C]=$/;($#C >$#c)?($ c=\@C)&&($ C=\@c):($ c=\@c)&&($C=\@C);$%=$|;for(@$c){print$_^ +$$C[$%++]}

        your algorithm works well your only fail is to feed your vigener cipher machine with simbols others than alphabetics ones.

        Problems of keeping spaces on your ciphertext are that there are some words that are very common on your language (examples: the, and, of, I, you ...), and the same goes for other simbols like the ``''' and the ``?''. So in old cipher methods is important to remove this simbols (except on transposition ciphers like the scitale ^_^>)

        i think your algorithm failed because of those spureous simbols

        prove with this text instead:

        TheVigenerecipherknownbysomeaslechiffreindechiffrableFrenchfor theindecipherablecipherisamethodofencryptionthatusesaseriesof differentCaesarciphersbasedonthelettersofakeywordthoughthereis someargumentamongcryptographiccirclesastowhichincarnationofthis particularpolyalphabeticsubstitutioncanaccuratelybeattributedtoBlaise deVigenereThisimplementationisasimpleformofapolyalphabetic substitutionToencipheratableofalphabetscanbeusedtermedatabula rectaorVigeneretableItconsistsofthealphabetwrittenout26times indifferentrowseachalphabetshiftedcycliclytotheleftcomparedtothe previousalphabetIncidentallytheresagoodchancethatthisplaintext islongenoughtodisplaythecryptographicalweaknessofthisparticular algorithmCanyouspotit

        perl -Te 'print map { chr((ord)-((10,20,2,7)[$i++])) } split //,"turo"'