[QUIZ] Cryptogram II (#206)

[Forum]

This is a strange way to spell
MARY HADA LITT LELA MBDA

R.

···

On Fri, May 22, 2009 at 7:12 PM, Daniel Moore <yahivin@gmail.com> wrote:

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

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

--
-Daniel
http://rubyquiz.strd6.com

--
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]

[lim]

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.

[Martin_DeMello]

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

crypto.rb (2.62 KB)

[Martin_Boese]

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:

  Substitution Cypher Cracker's Workbench

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 Sat, 2009-05-23 at 02:12 +0900, Daniel Moore wrote:

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

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

[Daniel_Moore]

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

206.tar.gz (4.19 KB)

[Martin_DeMello]

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

martin

···

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.

[Martin_Boese]

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, 2009-05-26 at 00:21 +0900, lith 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.

Cheers.

[Martin_DeMello]

Bravo Very nicely done indeed.

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:

[Joshua_Ball1 (Joshua Ball)]

Check out this link to understand what a cryptogram is:

Cryptogram

···

-----Original Message-----
From: Martin DeMello [mailto:martindemello@gmail.com]
Sent: Monday, May 25, 2009 8:30 AM
To: ruby-talk ML
Subject: Re: Cryptogram II (#206)

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

[Ken_Bloom]

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)}" }

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, 26 May 2009 13:45:45 +0900, Martin Boese wrote:

--
Chanoch (Ken) Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/

[lim]

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?

···

On May 26, 1:34 am, Joshua Ball <Joshua.B...@microsoft.com> wrote:

Check out this link to understand what a cryptogram is:Cryptogram - Wikipedia

[Luke_Cowell]

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

···

--
Posted via http://www.ruby-forum.com/\.

[Harry3 (Harry)]

"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 Tue, May 26, 2009 at 12:59 PM, lith <minilith@gmail.com> wrote:

On May 26, 1:34 am, Joshua Ball <Joshua.B...@microsoft.com> wrote:

Check out this link to understand what a cryptogram is:Cryptogram - Wikipedia

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?

--
A Look into Japanese Ruby List in English

Kakueki.com is for sale | HugeDomains

[Rob_Biedenharn1 (Rob Biedenharn)]

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 May 26, 2009, at 8:38 AM, Harry Kakueki wrote:

On Tue, May 26, 2009 at 12:59 PM, lith <minilith@gmail.com> wrote:

On May 26, 1:34 am, Joshua Ball <Joshua.B...@microsoft.com> wrote:

Check out this link to understand what a cryptogram is:Cryptogram - Wikipedia

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?

"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

--
A Look into Japanese Ruby List in English
http://www.kakueki.com/ruby/list.html

[Harry3 (Harry)]

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, May 26, 2009 at 10:05 PM, Rob Biedenharn <Rob@agileconsultingllc.com> wrote:

On May 26, 2009, at 8:38 AM, Harry Kakueki wrote:

On Tue, May 26, 2009 at 12:59 PM, lith <minilith@gmail.com> wrote:

On May 26, 1:34 am, Joshua Ball <Joshua.B...@microsoft.com> wrote:

Check out this link to understand what a cryptogram
is:Cryptogram - Wikipedia

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?

"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

--
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

--
A Look into Japanese Ruby List in English

Kakueki.com is for sale | HugeDomains

[Todd_Benson]

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

···

On Tue, May 26, 2009 at 8:45 AM, Harry Kakueki <list.push@gmail.com> wrote:

On Tue, May 26, 2009 at 10:05 PM, Rob Biedenharn > <Rob@agileconsultingllc.com> wrote:

On May 26, 2009, at 8:38 AM, Harry Kakueki wrote:

On Tue, May 26, 2009 at 12:59 PM, lith <minilith@gmail.com> wrote:

On May 26, 1:34 am, Joshua Ball <Joshua.B...@microsoft.com> wrote:

Check out this link to understand what a cryptogram
is:Cryptogram - Wikipedia

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?

"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

--
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

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.