Simple cipher solver, finding all possible key combinations

I am trying to find every possible combination of the letters of the alphabet to create a file by a program to solve simple replacement ciphers. There shouldn't be any repeats of letters in the combination (i.e. a can only occur once in a given combination).

I had thought of using the code below to get every possible combination and, even though it contains duplicate letters in the combinations it generates, I was going to prune those out. The problem is that it would take a very considerable number of years before the program finishes. Anyone know of an algorithm that I could use to generate the possibilities in a more timely manner?

class Value
  def initialize val='a'
    @value = val
  end
  
  def == rhs
    if rhs.class != self.class
      return false
      
    end
    rhs.value == self.value
  end
  
  def next
    if @value == 'z'
      self.reset
    else
      @value = @value.next
    end
  end
  
  def reset
    @value = 'a'
  end
  
  def value
    @value
  end
  
end

class Set
  def initialize
    @buffer = []
    26.times {@buffer << Value.new}
   end
  
  def value
    @buffer
    
    temp = []
    
    @buffer.each{|a| temp << a.value}
    
    temp
  end
  
  def exausted?
    @buffer.each do |a|
      if a.value != 'z'
        return false
      end
    end
    return true
  end
  
  def next
    cursor = 1
    
    while true
      if @buffer.last(cursor)[0].value == 'z'
      
        @buffer.last(cursor)[0].next()
        cursor += 1
        @buffer.last(cursor)[0].next()
      
      else
        @buffer.last(cursor)[0].next()
        break
      end
    end
    self.value
    
  end
  
end

···

#################################################################
#################################################################

s = Set.new
f = open "sets.out",'w'

f << s.value

while s.exausted? == false
  f << s.next << "\n"
end

---------------------------------
Be a better Globetrotter. Get better travel answers from someone who knows.
Yahoo! Answers - Check it out.

This is actually a timely question; I was about to start working on the same
problem!

I'm a Ruby nuby, and as practice I decided that my first project would be a
suite of old school cryptography encryption/decryption software. (Later to
be web-ified with Rails so anyone can use it on the web)

So this isn't exactly an answer to your question, but it is a way to
optimize your decryption:

Substitution cyphers are easiest to solve with a frequency analysis. (The
most common letters in the English language are 'E' 'T' and 'A' in that
order) Of course, the utility of this method increases with the length of
the cyphertext, so it may not be useful for very short (one word) messages
but is very useful for longer blocks of text (two or three sentences or
more).

Rather than computing all possible cyphers every time, you could make each
calculation dependent on a frequency analysis. So you count the number of
times each letter appears in the cyphertext, then try substituting the
letter that corresponds to the frequency. It is possible you may have to
run through several dozen combinations before you hit on the right one, but
it should be much faster than just calculating every single possible
combination. Rather than a random assignment of letter combinations, you
make the choice of combinations dependent on the frequency analysis. It
will require user input each time (puts 'Does this make sense? (y/n)') in
order to determine if the decryption actually worked (unless you're going to
include a syntax library to check it against, and if you do that, please
tell me how you do it!). I hope eventually to allow the user to adjust the
frequency analysis themselves, because the human brain can spot patterns
that pure statistics can't. . .but that's a little more complicated.

I wish I had some code for you, but like I said, I was just about to start
working on this myself. On the other hand, if you want some Ruby code for
substitution ENcryption, I'm putting the finishing touches on that right
now. Sorry I'm not faster, but I'm learning Ruby in between raising a
toddler, gestating a new kid, and trying to get into law school :wink:

Hit me up on AIM if you want to talk about old school cryptography. I'm not
much of a Ruby coder yet, but I know a lot about old school cryptography :slight_smile:

Jamie Lynn
AKA greymaiden
over.

···

On 8/10/07, Aric Campbell <ajcampbell0128@yahoo.com> wrote:

I am trying to find every possible combination of the letters of the
alphabet to create a file by a program to solve simple replacement ciphers.
There shouldn't be any repeat of letters in the combination (i.e. a can
only occur once in a given combination).

I had thought of using the code below to get every possible combination
and, even though it contains duplicate letters in the combinations it
generates, I was going to prune those out. The problem is that it would take
a very considerable number of years before the program finishes. Anyone know
of an algorithm that I could use to generate the possibilities in a more
timely manner?

class Value
  def initialize val='a'
    @value = val
  end

  def == rhs
    if rhs.class != self.class
      return false

    end
    rhs.value == self.value
  end

  def next
    if @value == 'z'
      self.reset
    else
      @value = @value.next
    end
  end

  def reset
    @value = 'a'
  end

  def value
    @value
  end

end

class Set
  def initialize
    @buffer =
    26.times {@buffer << Value.new}
   end

  def value
    @buffer

    temp =

    @buffer.each{|a| temp << a.value}

    temp
  end

  def exausted?
    @buffer.each do |a|
      if a.value != 'z'
        return false
      end
    end
    return true
  end

  def next
    cursor = 1

    while true
      if @buffer.last(cursor)[0].value == 'z'

        @buffer.last(cursor)[0].next()
        cursor += 1
        @buffer.last(cursor)[0].next()

      else
        @buffer.last(cursor)[0].next()
        break
      end
    end
    self.value

  end

end

#################################################################
#################################################################

s = Set.new
f = open "sets.out",'w'

f << s.value

while s.exausted? == false
  f << s.next << "\n"
end

---------------------------------
Be a better Globetrotter. Get better travel answers from someone who
knows.
Yahoo! Answers - Check it out.

Aric Campbell wrote:

I had thought of using the code below to get every possible combination
and, even though it contains duplicate letters in the combinations it
generates, I was going to prune those out. The problem is that it would
take a very considerable number of years before the program finishes.
Anyone know of an algorithm that I could use to generate the
possibilities in a more timely manner?

Well, you could try more than just the most common letters strategy.
What you really want to do is reduce the number of possibilities. There
are a limited number of legitimate one and two character words. You
could start with them and see if things add up elsewhere with those
letters assigned.

Check the recent Ruby puzzle for finding crosswords.
Ruby Quiz - Crossword Solver (#132) Interestingly enough, there were a
good many groovy approaches but the one listed in this link reference a
widget made by google which is made for finding words like this. It
seems highly optimized and could help you out.

···

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

Right, probably should have told you my AIM name if I asked you to talk to
me there. I'm LastGreyMaiden on AIM. greymaiden on GoogleChat.

Braaaaaiiiiinsss. . . .sigh.

···

On 8/10/07, Jamie Lynn O'Marr <greymaiden@gmail.com> wrote:

This is actually a timely question; I was about to start working on the
same problem!

I'm a Ruby nuby, and as practice I decided that my first project would be
a suite of old school cryptography encryption/decryption software. (Later
to be web-ified with Rails so anyone can use it on the web)

So this isn't exactly an answer to your question, but it is a way to
optimize your decryption:

Substitution cyphers are easiest to solve with a frequency analysis. (The
most common letters in the English language are 'E' 'T' and 'A' in that
order) Of course, the utility of this method increases with the length of
the cyphertext, so it may not be useful for very short (one word) messages
but is very useful for longer blocks of text (two or three sentences or
more).

Rather than computing all possible cyphers every time, you could make each
calculation dependent on a frequency analysis. So you count the number of
times each letter appears in the cyphertext, then try substituting the
letter that corresponds to the frequency. It is possible you may have to
run through several dozen combinations before you hit on the right one, but
it should be much faster than just calculating every single possible
combination. Rather than a random assignment of letter combinations, you
make the choice of combinations dependent on the frequency analysis. It
will require user input each time (puts 'Does this make sense? (y/n)') in
order to determine if the decryption actually worked (unless you're going to
include a syntax library to check it against, and if you do that, please
tell me how you do it!). I hope eventually to allow the user to adjust the
frequency analysis themselves, because the human brain can spot patterns
that pure statistics can't. . .but that's a little more complicated.

I wish I had some code for you, but like I said, I was just about to start
working on this myself. On the other hand, if you want some Ruby code for
substitution ENcryption, I'm putting the finishing touches on that right
now. Sorry I'm not faster, but I'm learning Ruby in between raising a
toddler, gestating a new kid, and trying to get into law school :wink:

Hit me up on AIM if you want to talk about old school cryptography. I'm
not much of a Ruby coder yet, but I know a lot about old school cryptography
:slight_smile:

Jamie Lynn
AKA greymaiden
over.

On 8/10/07, Aric Campbell <ajcampbell0128@yahoo.com> wrote:
>
> I am trying to find every possible combination of the letters of the
> alphabet to create a file by a program to solve simple replacement ciphers.
> There shouldn't be any repeat of letters in the combination (i.e. a can
> only occur once in a given combination).
>
> I had thought of using the code below to get every possible combination
> and, even though it contains duplicate letters in the combinations it
> generates, I was going to prune those out. The problem is that it would take
> a very considerable number of years before the program finishes. Anyone know
> of an algorithm that I could use to generate the possibilities in a more
> timely manner?
>
>
>
> class Value
> def initialize val='a'
> @value = val
> end
>
> def == rhs
> if rhs.class != self.class
> return false
>
> end
> rhs.value == self.value
> end
>
> def next
> if @value == 'z'
> self.reset
> else
> @value = @value.next
> end
> end
>
> def reset
> @value = 'a'
> end
>
> def value
> @value
> end
>
> end
>
>
>
>
> class Set
> def initialize
> @buffer =
> 26.times {@buffer << Value.new}
> end
>
> def value
> @buffer
>
> temp =
>
> @buffer.each{|a| temp << a.value}
>
> temp
> end
>
> def exausted?
> @buffer.each do |a|
> if a.value != 'z'
> return false
> end
> end
> return true
> end
>
> def next
> cursor = 1
>
>
> while true
> if @buffer.last(cursor)[0].value == 'z'
>
> @buffer.last(cursor)[0].next()
> cursor += 1
> @buffer.last(cursor)[0].next()
>
> else
> @buffer.last(cursor)[0].next()
> break
> end
> end
> self.value
>
> end
>
> end
>
>
> #################################################################
> #################################################################
>
>
> s = Set.new
> f = open "sets.out",'w'
>
> f << s.value
>
>
> while s.exausted? == false
> f << s.next << "\n"
> end
>
>
>
>
> ---------------------------------
> Be a better Globetrotter. Get better travel answers from someone who
> knows.
> Yahoo! Answers - Check it out.
>

We had an older quiz that was even closer to this problem:

http://www.rubyquiz.com/quiz13.html

James Edward Gray II

···

On Aug 10, 2007, at 1:04 PM, Lloyd Linklater wrote:

Aric Campbell wrote:

I had thought of using the code below to get every possible combination
and, even though it contains duplicate letters in the combinations it
generates, I was going to prune those out. The problem is that it would
take a very considerable number of years before the program finishes.
Anyone know of an algorithm that I could use to generate the
possibilities in a more timely manner?

Well, you could try more than just the most common letters strategy.
What you really want to do is reduce the number of possibilities. There
are a limited number of legitimate one and two character words. You
could start with them and see if things add up elsewhere with those
letters assigned.

Check the recent Ruby puzzle for finding crosswords.
Ruby Quiz - Crossword Solver (#132)

I don't have AIM but I do have GoogleChat.

I will have to look into the frequency analysis angle. It wouldn't be too hard to analyze a few works of fiction form project Gutenberg and then use the results to make suggestions for substitutions. I'm guessing that if spaces are included in the cipher text you could also suggest 'i' and 'a' for single characters and other optimizations like that.

I'm still curious whether there is a way to find all possible combinations. It's more of a "I feel like I'm missing something obvious and want to know what it is" kind of curiosity. I suppose I could ask on a math forum as well. My method simply isn't practical. There would be 6,156,119,580,207,157,310,796,674,288,400,203,776 iterations in my program before I even got to pruning the results.

Jamie Lynn O'Marr <greymaiden@gmail.com> wrote: Right, probably should have told you my AIM name if I asked you to talk to
me there. I'm LastGreyMaiden on AIM. greymaiden on GoogleChat.

Braaaaaiiiiinsss. . . .sigh.

···

On 8/10/07, Jamie Lynn O'Marr wrote:

This is actually a timely question; I was about to start working on the
same problem!

I'm a Ruby nuby, and as practice I decided that my first project would be
a suite of old school cryptography encryption/decryption software. (Later
to be web-ified with Rails so anyone can use it on the web)

So this isn't exactly an answer to your question, but it is a way to
optimize your decryption:

Substitution cyphers are easiest to solve with a frequency analysis. (The
most common letters in the English language are 'E' 'T' and 'A' in that
order) Of course, the utility of this method increases with the length of
the cyphertext, so it may not be useful for very short (one word) messages
but is very useful for longer blocks of text (two or three sentences or
more).

Rather than computing all possible cyphers every time, you could make each
calculation dependent on a frequency analysis. So you count the number of
times each letter appears in the cyphertext, then try substituting the
letter that corresponds to the frequency. It is possible you may have to
run through several dozen combinations before you hit on the right one, but
it should be much faster than just calculating every single possible
combination. Rather than a random assignment of letter combinations, you
make the choice of combinations dependent on the frequency analysis. It
will require user input each time (puts 'Does this make sense? (y/n)') in
order to determine if the decryption actually worked (unless you're going to
include a syntax library to check it against, and if you do that, please
tell me how you do it!). I hope eventually to allow the user to adjust the
frequency analysis themselves, because the human brain can spot patterns
that pure statistics can't. . .but that's a little more complicated.

I wish I had some code for you, but like I said, I was just about to start
working on this myself. On the other hand, if you want some Ruby code for
substitution ENcryption, I'm putting the finishing touches on that right
now. Sorry I'm not faster, but I'm learning Ruby in between raising a
toddler, gestating a new kid, and trying to get into law school :wink:

Hit me up on AIM if you want to talk about old school cryptography. I'm
not much of a Ruby coder yet, but I know a lot about old school cryptography
:slight_smile:

Jamie Lynn
AKA greymaiden
over.

On 8/10/07, Aric Campbell wrote:
>
> I am trying to find every possible combination of the letters of the
> alphabet to create a file by a program to solve simple replacement ciphers.
> There shouldn't be any repeat of letters in the combination (i.e. a can
> only occur once in a given combination).
>
> I had thought of using the code below to get every possible combination
> and, even though it contains duplicate letters in the combinations it
> generates, I was going to prune those out. The problem is that it would take
> a very considerable number of years before the program finishes. Anyone know
> of an algorithm that I could use to generate the possibilities in a more
> timely manner?
>
>
>
> class Value
> def initialize val='a'
> @value = val
> end
>
> def == rhs
> if rhs.class != self.class
> return false
>
> end
> rhs.value == self.value
> end
>
> def next
> if @value == 'z'
> self.reset
> else
> @value = @value.next
> end
> end
>
> def reset
> @value = 'a'
> end
>
> def value
> @value
> end
>
> end
>
>
>
>
> class Set
> def initialize
> @buffer =
> 26.times {@buffer << Value.new}
> end
>
> def value
> @buffer
>
> temp =
>
> @buffer.each{|a| temp << a.value}
>
> temp
> end
>
> def exausted?
> @buffer.each do |a|
> if a.value != 'z'
> return false
> end
> end
> return true
> end
>
> def next
> cursor = 1
>
>
> while true
> if @buffer.last(cursor)[0].value == 'z'
>
> @buffer.last(cursor)[0].next()
> cursor += 1
> @buffer.last(cursor)[0].next()
>
> else
> @buffer.last(cursor)[0].next()
> break
> end
> end
> self.value
>
> end
>
> end
>
>
> #################################################################
> #################################################################
>
>
> s = Set.new
> f = open "sets.out",'w'
>
> f << s.value
>
>
> while s.exausted? == false
> f << s.next << "\n"
> end
>
>
>
>
> ---------------------------------
> Be a better Globetrotter. Get better travel answers from someone who
> knows.
> Yahoo! Answers - Check it out.
>

---------------------------------
Fussy? Opinionated? Impossible to please? Perfect. Join Yahoo!'s user panel and lay it on us.

It sounds to me like you are wanting to break Vigenere's Cypher.

There are several ways to do it although it sounds like you are going for
the most painful. Here is a description of Vigenere:

http://www.trincoll.edu/depts/cpsc/cryptography/vigenere.html

You really do want to perform a frequency alanysis to break something like
that:

I don't have my crypto book in front of me but their table looks pretty
good.

···

On 8/10/07, Aric Campbell <ajcampbell0128@yahoo.com> wrote:

I don't have AIM but I do have GoogleChat.

I will have to look into the frequency analysis angle. It wouldn't be too
hard to analyze a few works of fiction form project Gutenberg and then use
the results to make suggestions for substitutions. I'm guessing that if
spaces are included in the cipher text you could also suggest 'i' and 'a'
for single characters and other optimizations like that.

I'm still curious whether there is a way to find all possible
combinations. It's more of a "I feel like I'm missing something obvious and
want to know what it is" kind of curiosity. I suppose I could ask on a math
forum as well. My method simply isn't practical. There would be
6,156,119,580,207,157,310,796,674,288,400,203,776 iterations in my program
before I even got to pruning the results.

Jamie Lynn O'Marr <greymaiden@gmail.com> wrote: Right, probably should
have told you my AIM name if I asked you to talk to
me there. I'm LastGreyMaiden on AIM. greymaiden on GoogleChat.

Braaaaaiiiiinsss. . . .sigh.

On 8/10/07, Jamie Lynn O'Marr wrote:
>
> This is actually a timely question; I was about to start working on the
> same problem!
>
> I'm a Ruby nuby, and as practice I decided that my first project would
be
> a suite of old school cryptography encryption/decryption
software. (Later
> to be web-ified with Rails so anyone can use it on the web)
>
> So this isn't exactly an answer to your question, but it is a way to
> optimize your decryption:
>
> Substitution cyphers are easiest to solve with a frequency
analysis. (The
> most common letters in the English language are 'E' 'T' and 'A' in that
> order) Of course, the utility of this method increases with the length
of
> the cyphertext, so it may not be useful for very short (one word)
messages
> but is very useful for longer blocks of text (two or three sentences or
> more).
>
> Rather than computing all possible cyphers every time, you could make
each
> calculation dependent on a frequency analysis. So you count the number
of
> times each letter appears in the cyphertext, then try substituting the
> letter that corresponds to the frequency. It is possible you may have
to
> run through several dozen combinations before you hit on the right one,
but
> it should be much faster than just calculating every single possible
> combination. Rather than a random assignment of letter combinations,
you
> make the choice of combinations dependent on the frequency analysis. It
> will require user input each time (puts 'Does this make sense? (y/n)')
in
> order to determine if the decryption actually worked (unless you're
going to
> include a syntax library to check it against, and if you do that, please
> tell me how you do it!). I hope eventually to allow the user to adjust
the
> frequency analysis themselves, because the human brain can spot patterns
> that pure statistics can't. . .but that's a little more complicated.
>
> I wish I had some code for you, but like I said, I was just about to
start
> working on this myself. On the other hand, if you want some Ruby code
for
> substitution ENcryption, I'm putting the finishing touches on that right
> now. Sorry I'm not faster, but I'm learning Ruby in between raising a
> toddler, gestating a new kid, and trying to get into law school :wink:
>
> Hit me up on AIM if you want to talk about old school cryptography. I'm
> not much of a Ruby coder yet, but I know a lot about old school
cryptography
> :slight_smile:
>
> Jamie Lynn
> AKA greymaiden
> over.
>
>
>
> On 8/10/07, Aric Campbell wrote:
> >
> > I am trying to find every possible combination of the letters of the
> > alphabet to create a file by a program to solve simple replacement
ciphers.
> > There shouldn't be any repeat of letters in the combination (i.e. a
can
> > only occur once in a given combination).
> >
> > I had thought of using the code below to get every possible
combination
> > and, even though it contains duplicate letters in the combinations it
> > generates, I was going to prune those out. The problem is that it
would take
> > a very considerable number of years before the program finishes.
Anyone know
> > of an algorithm that I could use to generate the possibilities in a
more
> > timely manner?
> >
> >
> >
> > class Value
> > def initialize val='a'
> > @value = val
> > end
> >
> > def == rhs
> > if rhs.class != self.class
> > return false
> >
> > end
> > rhs.value == self.value
> > end
> >
> > def next
> > if @value == 'z'
> > self.reset
> > else
> > @value = @value.next
> > end
> > end
> >
> > def reset
> > @value = 'a'
> > end
> >
> > def value
> > @value
> > end
> >
> > end
> >
> >
> >
> >
> > class Set
> > def initialize
> > @buffer =
> > 26.times {@buffer << Value.new}
> > end
> >
> > def value
> > @buffer
> >
> > temp =
> >
> > @buffer.each{|a| temp << a.value}
> >
> > temp
> > end
> >
> > def exausted?
> > @buffer.each do |a|
> > if a.value != 'z'
> > return false
> > end
> > end
> > return true
> > end
> >
> > def next
> > cursor = 1
> >
> >
> > while true
> > if @buffer.last(cursor)[0].value == 'z'
> >
> > @buffer.last(cursor)[0].next()
> > cursor += 1
> > @buffer.last(cursor)[0].next()
> >
> > else
> > @buffer.last(cursor)[0].next()
> > break
> > end
> > end
> > self.value
> >
> > end
> >
> > end
> >
> >
> > #################################################################
> > #################################################################
> >
> >
> > s = Set.new
> > f = open "sets.out",'w'
> >
> > f << s.value
> >
> >
> > while s.exausted? == false
> > f << s.next << "\n"
> > end
> >
> >
> >
> >
> > ---------------------------------
> > Be a better Globetrotter. Get better travel answers from someone who
> > knows.
> > Yahoo! Answers - Check it out.
> >
>
>

---------------------------------
Fussy? Opinionated? Impossible to please? Perfect. Join Yahoo!'s user
panel and lay it on us.

--
"Hey brother Christian with your high and mighty errand, Your actions speak
so loud, I can't hear a word you're saying."

-Greg Graffin (Bad Religion)