Shotgun Hillclimbing
edt...@yahoo.com
Pubkeybreaker
Douglas A. Gwyn
> What makes people post off-the-subject queries?
You tell us. The original inquiry was on subject.
edt...@yahoo.com
Jim Gillogly
> What makes Shotgun Hillclimbing different from Simulated Annealing?
I'm not an expert on simulated annealing, but it's my impression
that you need to determine an analogue to the target temperature,
and that may not be obvious in the crypto application. It's also
not obvious to me how it avoids getting trapped in local maxima.
Shotgun hillclimbing avoids the first issue by not being locked
into trying to adapt a foreign paradigm to the cipher, and the
second by restarting the search in a straightforward manner.
There are lots of variations possible in shotgun hillclimbing
to put in a little memory, or some reluctance to leave a potentially
rich area, or to remember useful pieces, and so far as I know there
hasn't been a lot of systematic work done to explore these
variations. I assume an expert in simulated annealing would
be able to make appropriate modifications to the algorithm to
get good results, and perhaps end up with a perfectly workable
set of ad-hockery such as one might get with a carefully tuned
shotgun hillclimbing (or genetic programming, for that matter)
approach.
--
Jim Gillogly
jsa...@ecn.ab.ca
> I'm not an expert on simulated annealing, but it's my impression
> that you need to determine an analogue to the target temperature,
> and that may not be obvious in the crypto application. It's also
> not obvious to me how it avoids getting trapped in local maxima.
I think *that* part of it follows from what you said. If it seems like
it's trapped in a local maximum, raise the temperature.
Not that I'm expert enough about this to say more than vague
generalities like that about it - but real-life annealing works by
alternately raising and lowering the temperature, until the crystal
domains are settled the right way.
John Savard
Francois Grieu
"edt...@yahoo.com" <edt...@yahoo.com> wrote:
> Nobody seems interested in explaining the differences, then?
For a start, could we get a (pointer to a) definition of
"Shotgun Hillclimbing" ?
TIA,
Francois Grieu
Frode....@cern.ch
In the scientific literature it goes under the name "iterated
hillclimbing" or "random-restart iterated hillclimbing". If you do a
search on these terms you will find many papers explaining this search
algorithm and the uses to which it has been put.
If you are curious about its cryptanalytical uses perhaps you want
to have a look at what we are presently doing with Shotgun
Hillclimbing:
http://www.cryptocellar.org/Flossenbuerg/flo.html
Frode
John Hadstate
What's the difference between "Shotgun Hillclimbing" and "Directed
Random Search"?
Stefan Krah
> Nobody seems interested in explaining the differences, then?
Please choose an appropriate subject and/or quote the text
you are referring to.
I gather from the other responses that you want to hear about
differences between Shotgun Hillclimbing and Simulated Annealing.
Furthermore I assume that you are trying to apply one or both of
the algorithms to a classical cipher, which would make it on-topic
here.
Shotgun Hillclimbing is also called Random Restart Hillclimbing.
Lets leave the ``Random Restart'' part out for a moment and
compare Hillclimbing and Simulated Annealing.
Similarities:
1. You need mutation functions working on the object you are
trying to improve (e.g playfair grid, enigma steckerbrett).
2. You need a scoring function to examine if a mutation is
an improvement or otherwise.
Differences:
1. In Hillcimbing, conventionally a higher score is better, in
Simulated Annealing a lower score is better (this is purely
a technical difference.
2. Hillclimbing is a greedy algorithm, picking up every improvement
in a score or even searching for the steepest ascent path,
whereas the SA Algorithm does the following:
- It accepts better scores.
- It also accepts worse scores, but with decreasing probability
as the algorithm progresses.
Point 2 is the major difference which has these implications:
Hillclimbing is very likely to get stuck in a local maximum. To counteract
this, one wraps a random restart loop around the algorithm. This just means
that the algorithm starts over and over again with a new random object
(playfair grid, steckerbrett combination ...), until (hopefully) the _global_
maximum is reached.
SA on the other hand has the ability to move away from local minima, so
the chance of hitting the global minimum in the first pass is much higher
than with Hillclimbing. You can use the _same_ random restart loop to
make sure you reach the global minimum virtually every time.
Some practical points:
I have used Random Restart Hillclimbing for the Playfair cipher, ADFGVX cipher
and the Enigma.
For comparison reasons I wrote an SA (Random Restart) program for the Playfair
cipher. To solve the Playfair stage of Simon Singh's Cipher Challenge, the
Hillclimbing program takes an average of 6.4 seconds, the SA program 1.83
seconds (both on a Celeron 1.2 GHz). This comparison is grossly inaccurate,
since I used different mutations.
Some links:
http://en.wikipedia.org/wiki/Main_Page
http://members.aol.com/jpeschel/historical.htm
sky.fit.qut.edu.au/~clarka/papers/prague1996.pdf
Stefan Krah
--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
Francois Grieu
Frode....@cern.ch wrote:
> In the scientific literature (Shotgun Hillclimbing) goes under
> the name "iterated hillclimbing" or "random-restart iterated
> hillclimbing" is been put.
Thanks for the definition.
> If you are curious about its cryptanalytical uses perhaps you want
> to have a look at what we are presently doing with Shotgun
> Hillclimbing:
http://www.cryptocellar.org/Flossenbuerg/flo.html
MUCH interesting from the standpoint of history of cryptography,
and (independently) history of Germany during WW2. We can only
guess that the full article will be interesting from the standpoint
of plaintext-only cryptanalysis, and search heuristics.
François Grieu
Frode....@cern.ch
Stefan Krah wrote:
> * edt...@yahoo.com <edt...@yahoo.com> wrote:
> > Nobody seems interested in explaining the differences, then?
>
>
> Lets leave the ``Random Restart'' part out for a moment and
> compare Hillclimbing and Simulated Annealing.
>
>
> Similarities:
Stefan, many thanks for a nice overview. I fully agree with your
analysis. I should nevertheless like to add a few points which
perhaps is not quite obvious.
What makes Shotgun Hillclimbing or Random-restart Hillclimbing so
powerful is it simplicity. Many of the other algorithms including
most GA and Simulated Annealing are more like an art than a science
and they need extensive tweaking to get them to work in an optimal
way. Even with properly optimised parameters Simulated Annealing
can be rather slow to converge. Slow convergence is a major
obstacle when your key search space is large and speed is a serious
issue.
Another problem with applying evolutionary computation to
cryptanalytical problems is that the problem is never well defined.
Very often you only have a very vague idea about the underlaying
plaintext, sometimes you don't even know for sure what language it
is in. In such cases Hillclimbing is more like Jungle Hillclimbing
where you never seem to find hills at all. The vegetation or the
statistical noise is so large and dense that you hardly get a
perception of the plaintext.
The statistics used to score in your hillclimbing or for that
matter any search or evolutionary algorithm is of utmost
importance. This was the first lesson we learned in trying to break
the German SS messages from 1941 and 1945. Along the way we also
developed other tricks to get the hillclimbing started or to stay
on track in difficult cases. When your ciphertext is around 100
letters long or less you have very little statistical
evidence to play with. Analysing some of these hillclimbs we often
would discover that the Stecker connections it correctly deducted
very early in a climb would be undone higher up in the climb and
the end result would be a failure.
We will describe all this in some detail in our forthcoming
Cryptologia article. Having used Shotgun Hillclimbing with quite
some success on the Enigma and other cryptanalytical problems I am
convinced about its suitability. This is not to say that other
algorithms cannot do as well or perhaps even better. I would
therefore encourage all those of you who are interested to try to
apply evolutionary computation on cryptanalytical problems.
Frode
edt...@yahoo.com
solve different types of cryptograms, Genetic Algorithms (GA),
Simulated Annealing (SA), and Shotgun Hillclimbing. I realized that GA
would require many different subroutines for the breeding of solutions,
and the setup for defining the evaluation of the results would be
complex. I looked at the literature for SA and hillclimbing and saw
much less complication in the algorithms, but I wasn't sure where they
differed. Thank you all.
Stefan Krah
> Stefan Krah wrote:
>> Shotgun Hillclimbing is also called Random Restart Hillclimbing.
>> Lets leave the ``Random Restart'' part out for a moment and
>> compare Hillclimbing and Simulated Annealing.
>>
> analysis. I should nevertheless like to add a few points which
> perhaps is not quite obvious.
I am glad you did.
> What makes Shotgun Hillclimbing or Random-restart Hillclimbing so
> powerful is it simplicity. Many of the other algorithms including
> most GA and Simulated Annealing are more like an art than a science
> and they need extensive tweaking to get them to work in an optimal
> way. Even with properly optimised parameters Simulated Annealing
> can be rather slow to converge. Slow convergence is a major
> obstacle when your key search space is large and speed is a serious
> issue.
My initial reaction was to ask for an example. Instead, I sat down
and tried to apply SA to the Enigma Stecker connections. It is possible
to find a (near) solution using only random mutations, but for this
problem steepest ascent hillclimbing is indeed much faster. So I
guess I found my example.
> The statistics used to score in your hillclimbing or for that
> matter any search or evolutionary algorithm is of utmost
> importance. This was the first lesson we learned in trying to break
> the German SS messages from 1941 and 1945. Along the way we also
> developed other tricks to get the hillclimbing started or to stay
> on track in difficult cases. When your ciphertext is around 100
> letters long or less you have very little statistical
> evidence to play with. Analysing some of these hillclimbs we often
> would discover that the Stecker connections it correctly deducted
> very early in a climb would be undone higher up in the climb and
> the end result would be a failure.
>
> We will describe all this in some detail in our forthcoming
> Cryptologia article.
This is going to be interesting. Is 100 letters a common threshold?
My own experience is limited to the Singh (Cipher Challenge) message,
where I used trigram statistics compiled without much thought from
Thomas Mann's Tristan and Schiller's poems.
Using these statistics the hillclimber fails when the message is
truncated below 108 letters.
Thanks for your comments,
Stefan Krah
sp...@hut-six.co.uk
Stefan Krah wrote:
> This is going to be interesting. Is 100 letters a common threshold?
> My own experience is limited to the Singh (Cipher Challenge) message,
> where I used trigram statistics compiled without much thought from
> Thomas Mann's Tristan and Schiller's poems.
> Using these statistics the hillclimber fails when the message is
> truncated below 108 letters.
Singh's message was not a very good example of a typical Enigma
message. It only used six Stecker connections, rather than the more
usual ten and it was assumed that all Ringstellung were set at A. This
should make it *much* easier to break. It also had a higher than usual
frequency of X.
I believe the final IC was well above 0.07
Your trigram sample was probably not a good match to the frequencies in
the Singh message.
Cheers,
Geoff Sullivan
Joe Peschel
news:1115643866....@o13g2000cwo.googlegroups.com:
> It also had a higher than usual
> frequency of X.
> I believe the final IC was well above 0.07
>
Yes, it was above 0.08, high even for German. One X was used for a space,
two Xs for a new line.
J
--
__________________________________________
When will Bush be tried for war crimes?
"Our enemies are innovative and resourceful, and so are we. They
never stop thinking about new ways to harm our country and our
people, and neither do we." --G. W. B.
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
Stefan Krah
> Stefan Krah wrote:
>> Using these statistics the hillclimber fails when the message is
>> truncated below 108 letters.
>
> Singh's message was not a very good example of a typical Enigma
> message. It only used six Stecker connections, rather than the more
> usual ten and it was assumed that all Ringstellung were set at A. This
> should make it *much* easier to break. It also had a higher than usual
> frequency of X.
> I believe the final IC was well above 0.07
>
> Your trigram sample was probably not a good match to the frequencies in
> the Singh message.
As it turns out, my trigram dictionary was simply too long. Just by
reducing its size drastically, the program finds a (near) solution
with the message truncated to 63 letters. Now I should try different
text samples.
Stefan Krah
sp...@hut-six.co.uk
> As it turns out, my trigram dictionary was simply too long. Just by
> reducing its size drastically, the program finds a (near) solution
> with the message truncated to 63 letters. Now I should try different
> text samples.
I've noticed that when using entire novels. 10-20k works better.
63 letters is not bad for this message, but how does (near) stand out
from the other 1,054,559 wheel arrangements?
Try 10 plugs also.
Geoff
Douglas A. Gwyn
> As it turns out, my trigram dictionary was simply too long. Just by
> reducing its size drastically, the program finds a (near) solution
> with the message truncated to 63 letters. Now I should try different
> text samples.
Perhaps you're already aware of this issue, but for those
to whom it is new: There is a very real problem with the
use of tabulated n-gram statistics as a statistical model
for a source: Suppose the corpus that was scanned to
build the table contained 0 occurrences of the trigram
SYZ; the table frequency will be 0. If taken literally
as the model that means that any attempt at deciphering
that produces a plaintext trigram SYZ will be rejected as
*literally impossible*. (So if the plaintext contained
"SYZYGY" it would not be deciphered.) In MilCryp as I
recall they used the artificial assignment of "1/2 of an
occurrence" in place of "0 occurrence" for all unseen n-
grams. There actually is a rigorous theory of how to
handle this, first published in 1953 by I. J. Good as "The
Population Frequencies of Species and the Estimation of
Population Parameters" in Biometrika, 40(16), pp. 237-264.
The original insight and method were developed by Alan
Turing somewhere around 1940 and involved "distributions
of distributions". (I don't think the original Turing
work was ever declassified.) The topic has generally come
to be known as "Good-Turing smoothing".
Mike Amling
>
> Perhaps you're already aware of this issue, but for those
> to whom it is new: There is a very real problem with the
> use of tabulated n-gram statistics as a statistical model
> for a source: Suppose the corpus that was scanned to
> build the table contained 0 occurrences of the trigram
> SYZ; the table frequency will be 0. If taken literally
> as the model that means that any attempt at deciphering
> that produces a plaintext trigram SYZ will be rejected as
> *literally impossible*. (So if the plaintext contained
> "SYZYGY" it would not be deciphered.) In MilCryp as I
> recall they used the artificial assignment of "1/2 of an
> occurrence" in place of "0 occurrence" for all unseen n-
> grams.
Does 1 observed occurrence also get renormalized, to 1.5?
> There actually is a rigorous theory of how to
> handle this, first published in 1953 by I. J. Good as "The
> Population Frequencies of Species and the Estimation of
> Population Parameters" in Biometrika, 40(16), pp. 237-264.
> The original insight and method were developed by Alan
> Turing somewhere around 1940 and involved "distributions
> of distributions". (I don't think the original Turing
> work was ever declassified.) The topic has generally come
> to be known as "Good-Turing smoothing".
--Mike Amling
Douglas A. Gwyn
> Does 1 observed occurrence also get renormalized, to 1.5?
MilCrypt didn't do that; they weren't applying the exact
theory but just an approximate fix for the 0 tallies in
order to avoid complete calamity. In principle, all
counts should be adjusted (but not by 0.5).
Stefan Krah
In this instance "near" meant: (legible && score close to perfect).
So the score stood out pretty well from the other arrangements' score.
Having tried other messages, I've encountered (legible && useless score)
as well, though.
For the people who are new to this thread, I'm talking about trigram
scores, not IC scores. The question I have been asking myself is what
to do when all you have is a short ciphertext (without cribs) and IC
scores fail to weed out bad wheel/ring settings.
> Try 10 plugs also.
This is an attempt at creating a military sounding message:
================
stefan:> ./enigma -M H -r GHL -w 231 -s ATEOMDQYWGLXPZNFUJIH -m WSK
xhptmxseydlitzfliegerstaffelxdreixmeldetxaufklaerungsflugxerfolgreichx
likjqjrwbzhaxsvwfbcgywsmwvcwuhfihzybwmdsnuaiemxxvodaiavfjmnbplgkwnhfpd
================
With the correct wheel/ring settings the hillclimbing part takes an
average of 2.8 seconds (Celeron 1.2 GHz) to find the perfect solution,
the minimum being around 0.1s, the maximum around 12s.
100000 random restarts seem to ensure that the perfect score is reached
in 97% of all cases, the other 3% have useless[1] scores but are somewhat
legible.
200000 random restarts _seem_ to result in a 100% (let's say close to
100%) success rate, extending the average time to 3.8 seconds.
With 200000 random restarts a random (nonsense) ciphertext of this
length keeps the program busy for an average 21s.
At this point I'd like to ask if those values look reasonable or if
the performance could be easily improved. - I've tried a variety of
mutations, but searching for the steepest ascent single (swap/undo)
move always gave the best performance. The benefit of looking two moves
ahead _seemed_ to be outdone by more random restarts. I gather that
the article you and Frode submitted will address some of these issues.
Anyway, the prospect of iterating through 60*26^3*26^2 arrangements
doing an expensive hillclimb on each of those isn't really enticing.
I imagine one could get rid of many arrangements /relatively/ cheap
by doing a single pass hillclimb and do a full hillclimb only on the
arrangements with scores in the top 20%. (The assumption that the
correct arrangement will yield a score in the top 20% is just based
on a few examples that I checked.)
60*26^3*26^2 * 0.2 * 21s is still a lot.
Are there any known shortcuts for messages of this length?
Stefan Krah
[1] a little above the typical score that a random ciphertext
would create.
sp...@hut-six.co.uk
We are getting one or two orders of magnitude improvement on your
timing, but we are doing far fewer loops - remarkably few. You could
also throw away that Celeron :-) And check that your compiler is well
optimised. some are better than others.
Too many random restarts are not good, watch out for that shotgun, use
a smaller propellant charge (damp gunpowder works OK for me).
It looks like the article will be published real soon, but there is
still time to order your subscription! There are some 'graded' examples
of real message in the paper that you could try. Hopefully you will not
have to wait long for the publication date.
>
> Anyway, the prospect of iterating through 60*26^3*26^2 arrangements
> doing an expensive hillclimb on each of those isn't really enticing.
It is enticing if you *must* read the messages, that is the situation
we were in. Nothing for it but to try every wheel arrangement. There is
some incentive to optimise the hill climb if you need to read several
hundred messages.
> I imagine one could get rid of many arrangements /relatively/ cheap
> by doing a single pass hillclimb and do a full hillclimb only on the
> arrangements with scores in the top 20%. (The assumption that the
> correct arrangement will yield a score in the top 20% is just based
> on a few examples that I checked.)
This did not work for us. The hill climb starts very slowly, due to the
double pass of the plugboard. If you get one cable correct, your plain
text increases on average from about 1 in 19 to about 1 in 10 correct
letters. If you have messed up one of the self-Steckers you may be back
to square one - or worse. So a short run hardly puts the key into the
top 20%, or even perhaps the top 99%.
> 60*26^3*26^2 * 0.2 * 21s is still a lot.
> Are there any known shortcuts for messages of this length?
Yes.
Cheers,
Geoff Sullivan
Stefan Krah
>> 100%) success rate, extending the average time to 3.8 seconds.
>>
>> With 200000 random restarts a random (nonsense) ciphertext of this
>> length keeps the program busy for an average 21s.
>>
>> At this point I'd like to ask if those values look reasonable or if
>> the performance could be easily improved. - I've tried a variety of
>> mutations, but searching for the steepest ascent single (swap/undo)
>> move always gave the best performance. The benefit of looking two moves
>> ahead _seemed_ to be outdone by more random restarts. I gather that
>> the article you and Frode submitted will address some of these issues.
>
> We are getting one or two orders of magnitude improvement on your
> timing, but we are doing far fewer loops - remarkably few. You could
> also throw away that Celeron :-) And check that your compiler is well
> optimised. some are better than others.
I finally threw away the Mann/Schiller based trigram statistics instead.
With the new statistics (10k trigrams) based on 71k WW1 army reports I
get these timings:
Allowing for a maximum of 100000 "perturbed restarts" (see below)
results in a 100% success rate.
Average decipherment time is now 1.7 seconds.
A nonsense ciphertext keeps the program busy for 10.5 seconds.
Leaving the statistics factor or details of the hillclimbing algorithm
aside, currently I get a rate of about 1200000 plugboard combinations
tested per second. Does that sound decent?
I definitely would like a L1 cache that holds the trigram dictionary.
As for the compiler, I use gcc, will try the Intel compiler later.
> Too many random restarts are not good, watch out for that shotgun, use
> a smaller propellant charge (damp gunpowder works OK for me).
Same here, actually. I consistently wrote "random restarts" when I meant
"perturbed restarts". In fact my (currently) fastest algorithm doesn't use
random restarts at all, but only does 2-4 random moves when restarting.
Wrapping a true random restart loop around a perturbed restart loop
with less iterations hasn't led to improvements yet.
> It looks like the article will be published real soon, but there is
> still time to order your subscription! There are some 'graded' examples
> of real message in the paper that you could try. Hopefully you will not
> have to wait long for the publication date.
<rant> The subscription process is a hillclimb in itself, googling was
needed to overcome "For payment send check drawn on US bank". </rant>
>> 60*26^3*26^2 * 0.2 * 21s is still a lot.
>> Are there any known shortcuts for messages of this length?
>
> Yes.
"Yes" as in "to be continued in Cryptologia" or as in "don't ask questions
with yes/no answers"? ;)
If the latter is the case, please give a pointer to literature.
Thanks,
Stefan Krah
Stefan Krah
>> 100%) success rate, extending the average time to 3.8 seconds.
>>
>> With 200000 random restarts a random (nonsense) ciphertext of this
>> length keeps the program busy for an average 21s.
>>
>> At this point I'd like to ask if those values look reasonable or if
>> the performance could be easily improved. - I've tried a variety of
>> mutations, but searching for the steepest ascent single (swap/undo)
>> move always gave the best performance. The benefit of looking two moves
>> ahead _seemed_ to be outdone by more random restarts. I gather that
>> the article you and Frode submitted will address some of these issues.
>
> We are getting one or two orders of magnitude improvement on your
> timing, but we are doing far fewer loops - remarkably few. You could
> also throw away that Celeron :-) And check that your compiler is well
> optimised. some are better than others.
I finally threw away the Mann/Schiller based trigram statistics instead.
With the new statistics (10k trigrams) based on 71k WW1 army reports I
get these timings:
Allowing for a maximum of 100000 "perturbed restarts" (see below)
results in a 100% success rate.
Average decipherment time is now 1.7 seconds.
A nonsense ciphertext keeps the program busy for 10.5 seconds.
Leaving the statistics factor or details of the hillclimbing algorithm
aside, currently I get a rate of about 1200000 plugboard combinations
tested per second. Does that sound decent?
I definitely would like a L1 cache that holds the trigram dictionary.
As for the compiler, I use gcc, will try the Intel compiler later.
> Too many random restarts are not good, watch out for that shotgun, use
> a smaller propellant charge (damp gunpowder works OK for me).
Same here, actually. I consistently wrote "random restarts" when I meant
"perturbed restarts". In fact my (currently) fastest algorithm doesn't use
random restarts at all, but only does 2-4 random moves when restarting.
Wrapping a true random restart loop around a perturbed restart loop
with less iterations hasn't led to improvements yet.
> It looks like the article will be published real soon, but there is
> still time to order your subscription! There are some 'graded' examples
> of real message in the paper that you could try. Hopefully you will not
> have to wait long for the publication date.
Will do.
>> 60*26^3*26^2 * 0.2 * 21s is still a lot.
>> Are there any known shortcuts for messages of this length?
>
> Yes.
"Yes" as in "to be continued in Cryptologia" or as in "don't ask questions
John Savard
wrote, in part:
>> Yes.
In this field, a third possiblity exists:
"Yes, but not in the open literature."
Of course, it's usually another poster here who mutters things like
that...
John Savard
http://www.quadibloc.com/index.html
_________________________________________
Usenet Zone Free Binaries Usenet Server
More than 120,000 groups
Unlimited download
http://www.usenetzone.com to open account
sp...@hut-six.co.uk
Stefan Krah wrote:
> Leaving the statistics factor or details of the hillclimbing
algorithm
> aside, currently I get a rate of about 1200000 plugboard combinations
> tested per second. Does that sound decent?
That is quite fast, faster than our method - but we are doing far less
plugboard tests so searching all the wheel settings is possible without
waiting forever.
>
> <rant> The subscription process is a hillclimb in itself, googling
was
> needed to overcome "For payment send check drawn on US bank". </rant>
>
<rant> I agree entirely. perhaps encryption may allow them to accept
credit cards one day :-) </rant>
>
> >> 60*26^3*26^2 * 0.2 * 21s is still a lot.
> >> Are there any known shortcuts for messages of this length?
> >
> > Yes.
>
> "Yes" as in "to be continued in Cryptologia" or as in "don't ask
questions
> with yes/no answers"? ;)
Some which are obvious, some which were found while doing the job and
some I will never know about. The first two are in the paper, the third
I can only answer yes.
Geoff
sp...@hut-six.co.uk
John Savard wrote:
> Of course, it's usually another poster here who mutters things like
> that...
Of course, I have no idea who you mean!
Geoff
Stefan Krah
> Stefan Krah wrote:
>> Leaving the statistics factor or details of the hillclimbing algorithm
>> aside, currently I get a rate of about 1200000 plugboard combinations
>> tested per second. Does that sound decent?
>
> That is quite fast, faster than our method - but we are doing far less
> plugboard tests so searching all the wheel settings is possible without
> waiting forever.
Good, I will focus my efforts on the algorithm and the statistics.
>>>> Are there any known shortcuts for messages of this length?
>>> Yes.
>> "Yes" as in "to be continued in Cryptologia" or as in "don't ask
>> questions with yes/no answers"? ;)
>
> Some which are obvious, some which were found while doing the job and
> some I will never know about. The first two are in the paper, the third
> I can only answer yes.
In that case, I'll keep thinking && waiting. Thanks for all the information!
Cheers,
Stefan Krah