Cryptography-Digest Digest #856, Volume #10 Thu, 6 Jan 00 16:13:01 EST
Contents:
Re: stupid question (No Spam)
OLD RLE TO NEW BIJECTIVE RLE (SCOTT19U.ZIP_GUY)
Re: meet-in-the-middle attack for triple DES (Mok-Kong Shen)
Re: How about this for a "randomly" generated bitstream? (Terje Elde)
Re: Blowfish weirdness (was: Re: Blowfish) (Erann Gat)
Re: Please Comment: Modified Enigma (Jim)
Re: How to pronounce "Vigenere"? (Michael Groh)
Re: How to pronounce "Vigenere"? (Michael Groh)
Re: Truly random bistream (CLSV)
Re: Miller Rabin alg--which is the right one? (Bob Silverman)
frequency analysis with homophones ("r.e.s.")
Re: Truly random bistream (Bob Silverman)
Re: Square? (Paul Crowley)
Re: Please Comment: Modified Enigma (Paul Crowley)
Re: RSA encrypt (Paul Crowley)
Re: frequency analysis with homophones (David Wagner)
----------------------------------------------------------------------------
From: No Spam <[EMAIL PROTECTED]>
Subject: Re: stupid question
Date: Thu, 06 Jan 2000 13:27:32 -0500
Reply-To: [EMAIL PROTECTED]
Albert Yang wrote:
>
> I think there are several other problems as well. First, I wrote a
> little bigram program before. So I would probably run a bigram program
> against Shakespeare's works, and calculate a commonality of letter
> pairs. For example, if you are basing your keys off of "Jack and Jill"
> JA and JI are fairly common pairs as is LL and CK. So it's easy to
> guess. Things like "JZ" which don't exist in the common english are a
> bit harder.
>
> Also, rapid seed expansion does not make it any more secure. Let me
> give you an example. Let's say I have a hash or PRNG program, that
> takes 16bits and converts it to 168 bits. So what? If I know this,
> then I won't be trying to crack 168bit key, I will be trying to crack a
> 16 bit key, which can be easily bruteforced.
>
> Albert
Albert
The point is that there are 19 such two pairs needed decode.. guessing
2,4, or 8 of the pairs would do no good.. all must be known. If you had
guessed 18 of the pairs correctly you there would be no indication of
that. All 19 pairs are required for decrypting.
Green in New Hampshire
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: OLD RLE TO NEW BIJECTIVE RLE
Date: Thu, 06 Jan 2000 19:49:18 GMT
I think I have found the RLE that the old bzip uses. Any way instead
of ragging on how bad it is. I used it as a basises to model a new RLE
that follows the one used there as close as possible but removing the
information that it needlessly adds to the compressed file. Both the
original and modifed RLE's and there DOS executables are at my site
for those who are interested. It should help those interested in doing
better compression. ALso if one used an Unadulterated arithemtic compression
such as what Matt Timmermans used you could improve that part of
bkzip also.
So you don't have to look go to http://members.xoom.com/ecil/compres7.htm
Take Care
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website NOT FOR WIMPS
http://members.xoom.com/ecil/index.htm
Scott rejected paper for the ACM
http://members.xoom.com/ecil/dspaper.htm
Scott famous Compression Page WIMPS allowed
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
"The road to tyranny, we must never forget, begins with the destruction of the
truth."
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: meet-in-the-middle attack for triple DES
Date: Thu, 06 Jan 2000 20:18:56 +0100
[EMAIL PROTECTED] wrote:
>
> The RC6 key schedule is highly recursive, that is each new key depends on
> multiple previous keys. The property makes is difficult to go backwards or
> forwards in the keystream with only partial information. Gaining full
> information on the state of the key schedule is more diffucult than just
> guessing the orginal key.
>
> With this mode, if an attacker guesses the key for one block then it does not
> help with other blocks. Guessing the key for multiple blocks should be
> harder than guessing the orginal key.
I think it is much more clean (and hence easier to get right) to
seperate the key generation issue 'entirely' from the block algorithm
that utilizes the keys.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Terje Elde)
Subject: Re: How about this for a "randomly" generated bitstream?
Date: Thu, 6 Jan 2000 19:59:07 +0100
In article <[EMAIL PROTECTED]>, John McDonald, Jr. wrote:
>Does anyone have thoughts on this? Problems with implementation?
First of all I'd choose something other than music, sound is a excelnt
source tho, because of the high rate, thus we can afford to shorten it
down a bit:
Take the LSB of every sample, line them all up, then run a simple check on
two and two bits at a time:
00 == throw away
11 == throw away
10 == keep 1
01 == keep 0
This ensures that if you get long runs of 0's or 1's or some other such
thing then it'll be discarded. Then again, if you get long runs of
0101010... you're in trouble again :)
Anyways, I've always enjoyed playing with combining random sources,
keeping in mind that if you xor two random streams you can gain a lot, but
rarely loose much, so you might want to combine with other inputs like
perhaps the keyboard. If you have something which will feed you at a too
slow rate to use, like a keyboard input, you can always seed a tream
cipher with it and use the output of that mixed with the output of the
audio data.
Playing with block ciphers and hashes are also a fun thing.
If you don't mind a small ammount of work then I strongly recommend yarrow
tho. It's got so many advantages I won't even start listing them =)
Terje
--
Those who duck, duck
Those who do not duck, get hit...?
------------------------------
From: [EMAIL PROTECTED] (Erann Gat)
Subject: Re: Blowfish weirdness (was: Re: Blowfish)
Date: Tue, 28 Dec 1999 15:36:27 -0800
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Erann Gat) wrote:
> In article <[EMAIL PROTECTED]>, stanislav shalunov
> <[EMAIL PROTECTED]> wrote:
>
> > General info:
> >
> > http://www.counterpane.com/blowfish.html
>
> Here's the description of Blowfish given in Schneier's paper:
>
> Divide x into two 32-bit halves: xL, xR
> For i = 1 to 16:
> xL = xL XOR Pi
> xR = F(xL) XOR xR
> Swap xL and xR
> Swap xL and xR (Undo the last swap.)
> xR = xR XOR P17
> xL = xL XOR P18
> Recombine xL and xR
>
> Can anyone tell me why he bothered to put in steps 5 and 6 (the swap
> of xL and xR that is immediately undone)? Or is this a mistake?
Turns out its a typo. Some indentation got lost in the conversion
to html. The algorithm should read:
Divide x into two 32-bit halves: xL, xR
For i = 1 to 16:
xL = xL XOR Pi
xR = F(xL) XOR xR
Swap xL and xR
Swap xL and xR (Undo the last swap.)
xR = xR XOR P17
xL = xL XOR P18
Recombine xL and xR
But I have another question: why is the key limited to 448 bits (= 14x32)
instead of 512 (= 32x16, the number of rounds) or 576 (= 32x18, the size
of the P array)?
Thanks,
Erann Gat
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Jim)
Subject: Re: Please Comment: Modified Enigma
Date: Thu, 06 Jan 2000 19:38:26 GMT
Reply-To: Jim
On Thu, 06 Jan 2000 01:53:11 GMT, Albert Yang <[EMAIL PROTECTED]> wrote:
>[EMAIL PROTECTED] wrote:
>>
>> Hello,
>> I wonder if someone can comment on the strength of the following simple
>> cipher: Extend the enigma algorithm by variable rotor permutations. Each
>> rotor permutation would be part of the key.
>>
><snip>
>
>The thing you have to remember though is, things are different. If you
>are out in the field and don't have a computer, that doesn't mean
>whoever intercepts your message doesn't have a computer either!!! So
>such things are very weak. Enigma is a joke to crack for my desktop.
>
So if I send you a piece of Enigma ciphertext, you'll be able to
crack it?
(3 out of 5 rotors).
--
Jim Dunnett.
nordland at lineone.net
amadeus at netcomuk.co.uk
------------------------------
From: [EMAIL PROTECTED] (Michael Groh)
Subject: Re: How to pronounce "Vigenere"?
Date: Thu, 6 Jan 2000 14:37:27 -0500
Well, you might think so, but because I can't even begin to fake a French
accent, I'd rather pronounce it "English-like". I feel I'd have less
chance of offending someone if I express the name with an American accent
than pretending I speak French!
- Mike
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
> Michael Groh wrote:
> > Would somebody provide me with the phonetic pronunciation of
> > "Vigenere" (as an English-speaking person might pronounce it).
>
> Wouldn't it be better to pronounce it like a French-speaking person?
>
------------------------------
From: [EMAIL PROTECTED] (Michael Groh)
Subject: Re: How to pronounce "Vigenere"?
Date: Thu, 6 Jan 2000 14:38:47 -0500
Hey Tony! Finally a pronounciation I can do without sounding (too) silly!
Thank you.
- Mike
In article <[EMAIL PROTECTED]>, u091889@cic-
mail.lanl.gov says...
> vision air
>
>
------------------------------
From: CLSV <[EMAIL PROTECTED]>
Subject: Re: Truly random bistream
Date: Thu, 06 Jan 2000 19:42:40 +0000
Mike Rosing wrote:
[Topic: the hardware PRNG described at
http://www.terracom.net/~eresrch]
> From the perspective of engineering,
> it's a reasonable proof: it can be built and tested and
> it works for many applications.
It is an interesting piece of hardware, I think
it gives great value for little money. When I have
some spare time in this life I think I'm going to
try and build one.
Regards,
Coen Visser
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Miller Rabin alg--which is the right one?
Date: Thu, 06 Jan 2000 19:54:46 GMT
In article <852i4a$33n$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> In article <852at1$t09$[EMAIL PROTECTED]>,
>
> While we are on the subject... What is the probability that a prime
'n'
> cheat a Fermat Little Theorem test when using 's' prime witnesses.
0.
If instead you mean: What is the probability that a COMPOSITE 'n'
can cheat s times, I suggest you read the Kim & Pomerance paper.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: frequency analysis with homophones
Date: Thu, 6 Jan 2000 12:14:05 -0800
I posted this problem in a couple of *.math groups about a week ago,
but so far there has been no "solution".
The context is cryptanalysis of a substitution cipher which we
suppose to be "monoalphabetic" and "homophonic". Specifically,
for any given letter of plaintext -- suppose there are I different
such letters -- any one of J different ciphertext symbols is
substituted at random. We envision this as a table-lookup in which
row(i) of the table contains the J possible substitutes for letter(i)
of the plaintext alphabet, and we suppose the I plaintext letters
(rows) occur with probabilities p(i), i=1..I.
Now if we have only ciphertext, we might try creating a frequency
table of all the observed ciphertext symbols. Supposing that we
know the size of the substitution table (IxJ), we might then make
a sorted list of the frequencies and subtotal them in successive
groups of size J, hoping that the ordering and magnitudes of the
resulting I frequency subtotals might give clues about which rows
correspond to which plaintext letters.
That's the motivation for a somewhat-abstracted statistics problem,
concisely stated as follows:
>From an IxJ table, a row is selected at random according
to probabilities p(i), i=1..I, then from that row a cell
is selected uniformly at random. This procedure is done
independently K times, resulting in cell frequencies f(i,j),
with 0<=f(i,j)<=K, sum(f(i,j))=K.
The frequencies f(i,j) are then sorted in increasing order,
and subtotalled in successive groups of size J, yielding I
"ranked frequency subtotals", say g(i), i=1..I.
**Question** What is the distribution of the g(i), i=1..I?
E(g(i))? V(g(i))?
This much seems clear: As K->oo, f(i,j)/K -> p(i)/J (w.p. 1)
and therefore, g(i) ~ K*q(i), where the q(i) are the ranked p(i).
So asymptotically as K -> oo, E(g(i))~ K*q(i); but short of
knowing the actual distribution, it's V(g(i)) that would be
most interesting.
---
(As a contrived example just for illustration, we might have
the following row probabilities & observed cell frequencies
for K=10:
0.2 [0 1 0]
0.3 [2 0 1]
0.5 [3 1 2]
Then the sorted frequencies are 0,0,0,1,1,1,2,2,3
and the "ranked frequency subtotals", g(i), are 0,3,7.)
---
r.e.s.
[EMAIL PROTECTED]
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Truly random bistream
Date: Thu, 06 Jan 2000 20:08:15 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> TohuVohu <[EMAIL PROTECTED]> wrote:
> It /may/ not be impossible. It's just that nobody knows whether it's
> possible or not.
>
> : Isn't radioactive decay "random" enough for this.
>
> Perhaps, perhaps not. It depends on your "this" - since the original
> poster did not specify an application and instead asked after a
"truly"
> random bitstream
Yep! There is also the question of how to define "random enough".
- an entity whose existence some regard in much the same
> light as they would a perpetual motion machine.
Yep!
> Even if radioactive decay /were/ perfectly random,
Some physicists (John Wheeler for example) have presented arguments
which suggest that time itself is quantized (the minimum unit of time
is the time for light to cross the Planck length). Under this
circumstance it is impossible to get a 'truly' random *continuous*
distribution. One can only get an approximation.
> there is no known way
> of amplifying it to a macroscopic scale while demonstrably avoiding >
>every possibility of non-random influence from the
Indeed. Seeing common sense prevail is so refreshing!
The time between decay events is NOT a uniform random variable. It
follows an Erlang distribution (Exponential waiting time). Now if
you want to use this as a source for a UNIFORM (Bernoulli bit stream)
one must introduce a transformation. There are then two sources of
possible error: [maybe more?]
(1) We can not measure the time between events sufficiently accurately.
(2) We can not compute the non-linear transform with "true" [i.e.
infinite) precision.
Both introduce bias that forces a deviation from "true" uniform
randomness.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: Square?
Date: 6 Jan 2000 19:02:52 -0000
[EMAIL PROTECTED] (David Wagner) writes:
> Instead of Square, I'd suggest considering Rijndael, a successor of
> Square that has received a good deal of analysis thanks the fact that
> it is currently one of the five AES candidates.
>
> But frankly, I wouldn't suggest using a cipher as new as either Square
> or Rijndael for production purposes unless it were absolutely necessary.
> What's wrong with Triple-DES or Blowfish?
For some applications the smaller block size could be a disadvantage.
Square has a 128-bit blocksize. Rijndael supports blocksizes of 128,
192, and 256 bits.
--
__
\/ o\ [EMAIL PROTECTED] Got a Linux strategy? \ /
/\__/ Paul Crowley http://www.hedonism.demon.co.uk/paul/ /~\
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: Please Comment: Modified Enigma
Date: 6 Jan 2000 19:26:00 -0000
[EMAIL PROTECTED] writes:
> Do you know of other 'homemade' non-electronic crypto which is strong in
> today's terms ?
There's Bruce Schneier's Solitaire:
http://www.counterpane.com/solitaire.html
but that has statistical problems:
http://www.hedonism.demon.co.uk/paul/solitaire/
I'm working on an alternative, currently called "Mirdek". I've thrown
up a quick description on my Web pages, but this is a "work in
progress" and I already have some possible changes in mind. This
description makes most sense if you've already read the description of
Schneier's Solitaire. I'd be fascinated to know what people think so
far though if you're interested.
http://www.hedonism.demon.co.uk/paul/crypto/mirdek/
--
__
\/ o\ [EMAIL PROTECTED] Got a Linux strategy? \ /
/\__/ Paul Crowley http://www.hedonism.demon.co.uk/paul/ /~\
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: RSA encrypt
Date: 6 Jan 2000 19:55:49 -0000
"Brice" <[EMAIL PROTECTED]> writes:
> If I was to calculate M^d (M: message, d: secret key) and give it away for
> the modular step to be done by someone else (say), how easy would it be for
> that person to find what my secret key is since my public key is available
> to anyone ?
This method is quite secure; it would be vastly more difficult for
them to calculate your secret key given M^d than it would be using
factoring. However, the main expense would be reading in the
combinatorically[1] huge amount of data you'd sent them...
--
__
\/ o\ [EMAIL PROTECTED] Got a Linux strategy? \ /
/\__/ Paul Crowley http://www.hedonism.demon.co.uk/paul/ /~\
[1] "Combinatorial numbers" - like "astronomical numbers" but much,
much bigger.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: frequency analysis with homophones
Date: 6 Jan 2000 12:51:43 -0800
In article <852t43$9pu$[EMAIL PROTECTED]>,
r.e.s. <[EMAIL PROTECTED]> wrote:
> The context is cryptanalysis of a substitution cipher which we
> suppose to be "monoalphabetic" and "homophonic".
You might look at digraph statistics.
(I don't have any experience breaking this type of cipher, but this is
one of the approaches I'd try if I needed to.)
If s,t are two possible substitutes for the same plaintext letter, then
the digraphs su and tu should occur with roughly the same frequency, for
all u. Conversely, if s and t don't represent the same plaintext letter,
I'd guess these statistics probably will differ considerably.
This suggests defining a `Measure of Similarity' between s and t by
computing (say) a chi-squared test of similarity for the distributions
D(u) = Prob[su] and D'(u) = Prob[tu], and then trying to group the
ciphertext symbols into equivalence classes that maximize the total
measure of similarity.
An alternative approach, which may be useful here, is to use Hidden Markov
Models. Let the (hidden) internal states be the set of plaintext symbols,
with transition probabilities given by the digraph statistics of the
plaintext source, and then the probability of outputting the ciphertext
symbol c at state labelled by plaintext letter p is 0 if c can't represent
p, or 1/n if c is one of the n representatives of p. (The latter probabilities
are of course unknown to the cryptanalyst.) The problem is now to
approximately compute the sequence of internal states corresponding to a
given ciphertext, and I believe standard Hidden Markov Model algorithms can
solve this problem for you.
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
