[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Re: [QUIZ] Cryptograms (#13

Michael C. Libby

1/3/2005 12:42:00 PM

DISCUSSION CONTAINS SPOILERS

On Sat, 2005-01-01 at 03:27 +0900, Ruby Quiz wrote:
> 2. Support Ruby Quiz by submitting ideas as often as you can:
>
> http://www.grayproductions.net/...

According to the site: "The only goal we try to follow with the quizzes
is to keep them pretty short (30 minutes to an hour to solve for the
average coder). This is obviously vague, so use you're best judgment.
We're interested in fun little diversions, not a massive time sink."

> Coding a brute force solution is relatively trivial,

Speak for yourself! :)

Having never written a brute force decryption algorithm I thought I'd
better make sure it was as trivial as everyone says (including myself,
knowing that essentially all it needs to do is iterate over the entirety
of the possible keyspace).

This actually took me a few hours because while in theory I knew what
was required, getting from the vague notion of "test all 25! keys in the
key space" to actual working code was another matter. But I'm glad I
took the time because I am now a lot more familiar with Ruby and the
problem space.

> but there are many opportunities for the clever optimizer.

Yes, there are. Thank the gods, because the brute force solution is
miserably slow on a standard home PC. I got bored watching and never did
make certain that my brute force algorithm actually works on the
cryptograms in the Quiz (I did make sure it could solve shorter grams
with much smaller dict files).

> -----
> crypto3.txt
> -----

This particular cipher text kept two very capable humans busy for over
30 minutes with not even a hint of a solution in sight. My optimized
parser (which actually took about an hour or two to write) worked on it
for three or four hours itself and only spat out gibberish.

-----

I want to thank you for this Quiz, though. Not only have I been reading
Neal Stephenson's excellent book "Cryptonomicon", I'd just been
explaining to my daughter last weekend how encryption was different from
encoding, how encryption worked, and possible techniques to foil
mechanical solvers such as this Quiz will generate.

Now , thanks to crypto3.txt, I will add to the list of ways to foil
solvers: write messages that are nearly unsolvable in the first
place. :)

I will post my solution(s) to this Quiz later today or tomorrow. My
optimized method involves using patterns from the cipher text and the
dictionary to create sets of maps for each token and then using Set#& to
join them together when possible to make a set of maps covering the
entire character set of the cipher text. The chief speed differences
seem to be related to the order in which to compare the tokens against
each other.

And I have yet to try something like:

eval "set[0] & set[1] & set[2] ... & set[n]"

Which would combine them all at once. Hmmmm. Back to emacs...

So... is anyone else giving this a go? What strategies are you using?

- Michael C. Libby, www.andsoforth.com
7 Answers

Glenn Parker

1/3/2005 4:37:00 PM

0

Michael C. Libby wrote:
>
> According to the site: "The only goal we try to follow with the quizzes
> is to keep them pretty short (30 minutes to an hour to solve for the
> average coder). This is obviously vague, so use you're best judgment.
> We're interested in fun little diversions, not a massive time sink."

My apologies, I was not aware of the suggested time constraint. I
responded to the e-mailed request for quiz ideas with a problem that a
group of my friends had previously attacked in C, Perl, and Python. We
all solved it in our own way and had a fine time discussing our various
optimizations. Nobody spent more than a week's worth of spare time on
it, so it seemed to be within bounds for a weekly quiz. I also think
the recent tic-tac-toe problem was of comparable difficulty.

The cryptogram problem is definitely more than an hour's work, if only
because test runs can be time consuming. For me, a Ruby neophyte, the
Ruby version consumed over 10 hours of keyboard time, and that was after
I had developed a Python solution previously.

For those who only want a quickie 10 minute "golf" challenge, try
writing a cryptogram generator.

>>Coding a brute force solution is relatively trivial,
>
> Speak for yourself! :)

I said "relatively", as in relatively trivial compared to a fast and
efficient solution. :)

>>but there are many opportunities for the clever optimizer.
>
> Yes, there are. Thank the gods, because the brute force solution is
> miserably slow on a standard home PC. I got bored watching and never did
> make certain that my brute force algorithm actually works on the
> cryptograms in the Quiz (I did make sure it could solve shorter grams
> with much smaller dict files).

Another optional challenge is to come up with a way to measure your
progress as you chew through the very large solution space. If you get
clever about pruning, the math can get tricky.

> Now , thanks to crypto3.txt, I will add to the list of ways to foil
> solvers: write messages that are nearly unsolvable in the first
> place. :)

Again, my apologies if that puzzle proved too difficult for some. I
assure that there is at least one solution. I created these puzzles
myself to avoid copyright issues, and it's hard to evaluate their
difficulty. I do know that lots of medium-length words in which no
letters are re-used makes it harder, and crypto3.txt is a fine example
of that.

Sometimes, looking at the problem from a more practical standpoint, a
complete computer-generated solution is overkill. If you scan through
your algorithm's partial results, you may get enough insight to finish
the solution on your own. This is especially true when your algorithm
is stumbling on a proper noun, e.g. an author's name, that is not in
your dictionary.

--
Glenn Parker | glenn.parker-AT-comcast.net | <http://www.tetrafoi...

Florian Gross

1/3/2005 11:05:00 PM

0

Glenn Parker wrote:

> For those who only want a quickie 10 minute "golf" challenge, try
> writing a cryptogram generator.

Would this do the job? (42 characters)

l="a".."z";$><<[*l]<<$/<<l.sort_by{rand}<<$/

Glenn Parker

1/4/2005 1:46:00 AM

0

Florian Gross wrote:
> Glenn Parker wrote:
>
>> For those who only want a quickie 10 minute "golf" challenge, try
>> writing a cryptogram generator.
>
>
> Would this do the job? (42 characters)
>
> l="a".."z";$><<[*l]<<$/<<l.sort_by{rand}<<$/

That produces a cryptogram mapping, but a cryptogram consists of
ciphertext that has been created using such a mapping, so I think you
have to also read a plaintext and display the resulting ciphertext.

--
Glenn Parker | glenn.parker-AT-comcast.net | <http://www.tetrafoi...

Florian Gross

1/4/2005 11:04:00 AM

0

Glenn Parker wrote:

>> Would this do the job? (42 characters)
>>
>> l="a".."z";$><<[*l]<<$/<<l.sort_by{rand}<<$/
>
> That produces a cryptogram mapping, but a cryptogram consists of
> ciphertext that has been created using such a mapping, so I think you
> have to also read a plaintext and display the resulting ciphertext.

Like this? (75 chars)

> l=*"a".."z";m=l.to_s;n=l.sort_by{rand}.to_s;$><<$<.read.tr(m,n);warn m+$/+n

Glenn Parker

1/4/2005 2:02:00 PM

0

Florian Gross wrote:
> Like this? (75 chars)
>
>> l=*"a".."z";m=l.to_s;n=l.sort_by{rand}.to_s;$><<$<.read.tr(m,n);warn
>> m+$/+n

Getting warmer, but look carefully at the map display. This is the
"forwards" map that produced the cryptogram, but what you really want to
show is the "reverse" map that solves the cryptogram.

m=*"a".."z";n=m.sort{rand};$><<$<.read.tr(m.to_s,n.to_s);warn
m.to_s+$/+m.sort_by{|i|n[i[0]-?a]}.to_s

--
Glenn Parker | glenn.parker-AT-comcast.net | <http://www.tetrafoi...

Florian Gross

1/4/2005 2:33:00 PM

0

Glenn Parker wrote:

> Getting warmer, but look carefully at the map display. This is the
> "forwards" map that produced the cryptogram, but what you really want to
> show is the "reverse" map that solves the cryptogram.

Would not be fixed by changing m+$/+n to n+$/+m?

Glenn Parker

1/4/2005 4:22:00 PM

0

Florian Gross wrote:
> Glenn Parker wrote:
>
>> Getting warmer, but look carefully at the map display. This is the
>> "forwards" map that produced the cryptogram, but what you really want
>> to show is the "reverse" map that solves the cryptogram.
>
> Would not be fixed by changing m+$/+n to n+$/+m?

In a way, yes, but it's much harder to actually use it if the top line
is not sorted.

--
Glenn Parker | glenn.parker-AT-comcast.net | <http://www.tetrafoi...