Ruby Forum Ruby > Cryptogram II (#206)

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The three rules of Ruby Quiz:

1.  Please do not post any solutions or spoiler discussion for this
quiz until 48 hours have elapsed from the time this message was
sent.

2.  Support Ruby Quiz by submitting ideas and responses
as often as you can!
Visit: http://rubyquiz.strd6.com/suggestions

3.  Enjoy!

Suggestion:  A [QUIZ] in the subject of emails about the problem
helps everyone on Ruby Talk follow the discussion.  Please reply to
the original quiz message, if you can.

RSS Feed: http://rubyquiz.strd6.com/quizzes.rss

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

## Cryptogram II (#206)

YRFFJ OSLXA PQPQY APVRR DPNSA ZAPIK
OXMQJ BOIMY XMSZZ FRIHE AUXJS IOROR
IEAHB QYAPQ YRHXJ STRIF ORIEX KOIKD
REAQK JHBOI QSFIQ AJHPA QPKIF FREKO
XMQJB OIGAA LRKIS PRNSA Z13VI PIKOX
MQJBO IGNSA ZIPVR FFYJM RXJSY IEUSH

On Fri, May 22, 2009 at 7:12 PM, Daniel Moore <yahivin@gmail.com> wrote:
> Visit: http://rubyquiz.strd6.com/suggestions
>
> --
> -Daniel
> http://rubyquiz.strd6.com
>
This is a strange way to spell
MARY HADA LITT LELA MBDA

R.



--
Toutes les grandes personnes ont d’abord été des enfants, mais peu
d’entre elles s’en souviennent.

All adults have been children first, but not many remember.

[Antoine de Saint-Exupéry]

> 1.  Please do not post any solutions or spoiler discussion for this
> quiz until 48 hours have elapsed from the time this message was
> sent.

> YRFFJ OSLXA PQPQY APVRR DPNSA ZAPIK

Since 48 hours have passed, maybe somebody could at least explain what
this quiz was about. Or maybe simply post a solution.

Cheers.

On Mon, May 25, 2009 at 8:51 PM, lith <minilith@gmail.com> wrote:
>> 1.  Please do not post any solutions or spoiler discussion for this
>> quiz until 48 hours have elapsed from the time this message was
>> sent.
>
>> YRFFJ OSLXA PQPQY APVRR DPNSA ZAPIK
>
> Since 48 hours have passed, maybe somebody could at least explain what
> this quiz was about. Or maybe simply post a solution.

About: Write a ruby program to convert that into English text.

martin

Check out this link to understand what a cryptogram is:
http://en.wikipedia.org/wiki/Cryptogram

On May 26, 1:34 am, Joshua Ball <Joshua.B...@microsoft.com> wrote:
> Check out this link to understand what a cryptogram is:http://en.wikipedia.org/wiki/Cryptogram

I was wondering if the blanks represent actual word breaks or not. If
this were the case and if we were dealing with a normal cryptogram,
the word "FFYJM" would begin with two times the same letter. English
isn't my mother tongue but this seems rather unlikely to me which is
why I have concluded that is isn't a normal cryptogram, which is about
the point where I stopped.

Also, there already was a rubyquiz about solving cryptograms, which
made me suspect that we are dealing with something else here. Was I
wrong?

lith wrote:
> I was wondering if the blanks represent actual word breaks or not. If
> this were the case and if we were dealing with a normal cryptogram,
> the word "FFYJM" would begin with two times the same letter. English
> isn't my mother tongue but this seems rather unlikely to me which is
> why I have concluded that is isn't a normal cryptogram, which is about
> the point where I stopped.

I was thinking that each tuple represents a single letter. It seems 
unlikely that we have 36 words that all have exactly 5 letters in them.

Luke

I was starting something like this. But it doesn't seem to work out:

 crypt = <<-ENDC
  YRFFJ OSLXA PQPQY APVRR DPNSA ZAPIK
  OXMQJ BOIMY XMSZZ FRIHE AUXJS IOROR
  IEAHB QYAPQ YRHXJ STRIF ORIEX KOIKD
  REAQK JHBOI QSFIQ AJHPA QPKIF FREKO
  XMQJB OIGAA LRKIS PRNSA Z13VI PIKOX
  MQJBO IGNSA ZIPVR FFYJM RXJSY IEUSH
 ENDC

 ('A'[0]..'Z'[0]).each { |c| puts "#{c.chr} -> #{crypt.count(c.chr)}" }
 A -> 14
 B -> 5
 C -> 0
 D -> 2
 E -> 6
 F -> 9
 G -> 2
 H -> 6
 I -> 18
 J -> 10
 K -> 8
 L -> 2
 M -> 6
 N -> 3
 O -> 12
 P -> 11
 Q -> 11
 R -> 15
 S -> 11
 T -> 1
 U -> 2
 V -> 3
 W -> 0
 X -> 9
 Y -> 7
 Z -> 5


 english = File.read('/usr/share/dict/words').upcase

('A'[0]..'Z'[0]).each { |c| puts "#{c.chr} ->#{english.count(c.chr)}" }
 A -> 64123
 B -> 15524
 C -> 31569
 D -> 28877
 E -> 88441
 F -> 10551
 G -> 23073
 H -> 19313
 I -> 66892
 J -> 1915
 K -> 8456
 L -> 40826
 M -> 22433
 N -> 57227
 O -> 48779
 P -> 21891
 Q -> 1510
 R -> 57035
 S -> 88135
 T -> 52446
 U -> 25927
 V -> 7903
 W -> 7431
 X -> 2124
 Y -> 12507
 Z -> 3238

On Tue, May 26, 2009 at 12:59 PM, lith <minilith@gmail.com> wrote:
> Also, there already was a rubyquiz about solving cryptograms, which
> made me suspect that we are dealing with something else here. Was I
> wrong?
>
>

"FFYJM" could be ["oomph", "oozed", "oozes"] but "PQPQY" could be
["cacao", "cocoa", "dodos", "lulus", "mamas", "mimic", "tutus",
"vivid"].

Looking at these, there is no common letter for "Y".
So, I don't think these are just a bunch of five letter words.

Harry

On May 26, 2009, at 8:38 AM, Harry Kakueki wrote:
>> the point where I stopped.
> So, I don't think these are just a bunch of five letter words.
>
> Harry
>
> -- 
> A Look into Japanese Ruby List in English
> http://www.kakueki.com/ruby/list.html


Come on people! This is a standard technique to prevent things like
lone letters or letter pairs providing too much help. The whole
cryptogram is likely a simple substitution (one letter stands for
another) with possible "filler" letters at the end (to make a multiple
of 5). You need to find word breaks after you apply a substitution.

Martin is probably on the right track with comparing frequency counts
between English and the cryptogram, but that's only a start. Once you
have a candidate substitution, you have to see if you can pull letters
off the cryptogram to form words.  If you get a series of words that
leaves fewer than 5 letters at the end, then you very likely have a
solution.

-Rob

Rob Biedenharn    http://agileconsultingllc.com
Rob@AgileConsultingLLC.com

On Tue, May 26, 2009 at 10:05 PM, Rob Biedenharn
<Rob@agileconsultingllc.com> wrote:
>>> this were the case and if we were dealing with a normal cryptogram,
>> ["cacao", "cocoa", "dodos", "lulus", "mamas", "mimic", "tutus",
>
> cryptogram to form words.  If you get a series of words that leaves fewer
> than 5 letters at the end, then you very likely have a solution.
>
> -Rob
>
> Rob Biedenharn          http://agileconsultingllc.com
> Rob@AgileConsultingLLC.com
>
>
>
>

I think most people are aware of everything you said.
And it will probably be easy to understand after seeing the result.
But there are many tricks that could be used here and I suspect that
most people only have a few hours to work on this, not days.
Also, it is easy to criticize others without actually having a
solution of your own. :)

Harry

On Tue, 26 May 2009 13:45:45 +0900, Martin Boese wrote:

> 
>  ('A'[0]..'Z'[0]).each { |c| puts "#{c.chr} -> #{crypt.count(c.chr)}" }

cipherside=('A'[0]..'Z'[0]).map { |c| crypt.count(c.chr) }

>  english = File.read('/usr/share/dict/words').upcase
> 
> ('A'[0]..'Z'[0]).each { |c| puts "#{c.chr} ->#{english.count(c.chr)}" }

englishside = ('A'[0]..'Z'[0]).map { |c| english.count(c.chr) }

class Array
  def rotate num
    self[num..-1]+self[0...num]
  end
end

(0...26).each do |rot|
  dotprod=cipherside.zip(englishside.rotate(rot)).inject(0) do |a,(b,c)|
    a+b*c
  end
  printf "%d -> %d\n", rot, dotprod
end

0 -> 6418143
1 -> 5568695
2 -> 5549352
3 -> 6915018
4 -> 6262198
5 -> 5279474
6 -> 4898071
7 -> 4508113
8 -> 5015397
9 -> 5761530
10 -> 6017183
11 -> 5443382
12 -> 5440166
13 -> 5944635
14 -> 5750203
15 -> 4540453
16 -> 5307004
17 -> 5184543
18 -> 5899138
19 -> 5232100
20 -> 5903220
21 -> 5759249
22 -> 6291068
23 -> 4976438
24 -> 4537099
25 -> 5448116

def decrypt msg, num
  msg.each_byte do |x|
    next if x>?Z or x<?A
    x+=num
    x-=26 if x>?Z
    x+=26 if x<?A
    print x.chr
  end
  puts
end

(0...26).each do |rot|
  decrypt crypt, rot
  puts
end

I'll let you run this to see the output, but clearly this isn't a
rotation cipher.

On Tue, May 26, 2009 at 8:45 AM, Harry Kakueki <list.push@gmail.com> 
wrote:
>>>>
>>>
>>> A Look into Japanese Ruby List in English
>> between English and the cryptogram, but that's only a start. Once you have a
>>
>>
>
> I think most people are aware of everything you said.
> And it will probably be easy to understand after seeing the result.
> But there are many tricks that could be used here and I suspect that
> most people only have a few hours to work on this, not days.
> Also, it is easy to criticize others without actually having a
> solution of your own. :)

I love this quiz!  I'll throw it at my friend, though.  In real life,
these cryptograms can be tough, because you don't know if it's
english, and if it is, you don't know the order because of the 5 by 6
representation.  That's the way I'd change it up, anyway.

I'll assume it's left-top to right-bottom, and see if he can come up
with something that works using frequency analysis.

Todd

Well, here's my abortive attempt at solving it :) Attaching the code
anyway in case anyone wants to use it. It's more along the lines of
using ruby as a tool to explore the cipher.

martin

Got it ;-)

Below the result.


How? Instead of counting characters look for repeating sequences. Then
think carefully about the long word that it finds. I used this (ugly)
code:



crypted = <<HERE
YRFFJ OSLXA PQPQY APVRR DPNSA ZAPIK
OXMQJ BOIMY XMSZZ FRIHE AUXJS IOROR
IEAHB QYAPQ YRHXJ STRIF ORIEX KOIKD
REAQK JHBOI QSFIQ AJHPA QPKIF FREKO
XMQJB OIGAA LRKIS PRNSA Z13VI PIKOX
MQJBO IGNSA ZIPVR FFYJM RXJSY IEUSH
HERE
crypted = crypted.gsub(/[^A-Z]/, '')


class String
 def count(ss)
    r = 0
    self.split(//).each_index do |idx|
      r+=1 if self[idx..-1][0..(ss.length-1)] == ss
    end
    r
 end
end

cfound = {}
(1..11).each do |len|
  found = {}
  crypted.split(//).each_index do |idx|
     next if crypted[idx+len].nil?
     search = crypted[idx..(idx+len)]
     nfound = crypted.count(search)
     found[search] = nfound if nfound > 1
  end
  cfound[len] = found.sort { |a,b| a[1]<=>b[1] }
end

(1..11).each do |idx|
   k = idx
   v = cfound[idx]
   n = cfound[k+1] || []
   v.each do |f|
          puts "#{f[0]} => #{f[1]}" unless n.find { |e|
e[0].include?(f[0]) }
   end
end


This website then helps:


  http://tomacorp.com/codes/workbench.html



























Result:






sub = [['A', 'I'],
       ['B', 'G'],
       ['C', '.'] ,
       ['D', 'K'],
       ['E', 'D'],
       ['F', 'L'],
       ['G', '.'],
       ['H', 'N'],
       ['I', 'A'],
       ['J', 'O'],
       ['K', 'C'],
       ['L', 'B'],
       ['M', 'P'],
       ['N', 'Q'],
       ['O', 'R'],
       ['P', 'S'],
       ['Q', 'T'],
       ['R', 'E'],
       ['S', 'U'],
       ['T', 'F'],
       ['U', '.'],
       ['V', 'W'],
       ['W', '.'],
       ['X', 'Y'],
       ['Y', 'H'],
       ['Z', 'Z']
       ]



Now back to work...

Martin

On Wed, May 27, 2009 at 12:58 PM, Martin Boese <boesemar@gmx.de> wrote:
> Got it ;-)
>
> Below the result.
>
>
> How? Instead of counting characters look for repeating sequences. Then
> think carefully about the long word that it finds. I used this (ugly)
> code:

Bravo :) Very nicely done indeed.

martin

There was some discussion on the mailing list about the objective of
the quiz, due to its enigmatic nature. After the no-spoiler period
expired, several people began contributing programs to explore the
cryptogram.

Ken Bloom provided a solution to decrypt a rotation cipher. A rotation
cipher is a simple substitution cipher where each letter is
substituted with the letter a fixed number of positions ahead in the
alphabet. An example of this is the Caeser Cipher[1] or ROT13[2]. This
quiz did not happen to be a rotation cipher, but the algorithm used to
encrypt the text was something along those lines.

Martin DeMello submitted an exploratory solution. His solution is well
commented and documents the process of trying out different
substitutions to crack the cipher.

There were attempts to use frequency analysis, which is frequently a
good strategy to employ in working towards a solution. However, the
original text contained the word 'quiz' three times, 'cryptogram'
twice and 'cryptography' once. It also contained the words 'rubyists'
and 'puzzle'. These particular inclusions in the small amount of text
skewed the distribution enough to make frequency analysis problematic.

Martin Boese was successfully able to crack the cryptogram. He counted
repeated sequences to gain insight into possible words in the cipher
text. In particular, the string `KOXMQJBOIG` appeared more than once.

The text was encoded using a substitution cipher[3] with the key
phrase 'ILKERUBY' to create a mixed alphabet. The cipher text alphabet
was created by removing the key phrase and prepending it to mix up the
letters: `@cipher_text_alphabet = keyword_array + (@alphabet -
keyword_array)`. Then each letter in the plain text message is
replaced by the corresponding letter in the cipher text alphabet.

Have you guessed what the long word that was repeated in the cipher
text was? It was `cryptogram`. The encrypted text was actually the
description of the quiz itself, though it wouldn't help much until it
is cracked.

Here's the original plain text message:

    Hello Rubyists,

    This week's quiz is a cryptography puzzle and if you are reading
    this then you've already cracked it. Congratulations! It's called
    Cryptogram II because quiz #13 was a cryptogram quiz as well.

    Hope you had fun!

[1]: http://en.wikipedia.org/wiki/Caesar_cipher
[2]: http://en.wikipedia.org/wiki/ROT13
[3]: http://en.wikipedia.org/wiki/Substitution_cipher