Cryptography-Digest Digest #2, Volume #10 Fri, 6 Aug 99 20:13:02 EDT
Contents:
Re: frequency of prime numbers? (Jim Felling)
Re: AES finalists to be announced (Terje Mathisen)
Constants in hash functions ([EMAIL PROTECTED])
Re: Yarrow RNG (Paul Koning)
Re: AES finalists to be announced (Paul Rubin)
Re: AES finalists to be announced ([EMAIL PROTECTED])
Re: Factoring-Protected Exponentiation (John Savard)
Re: key lengths ([EMAIL PROTECTED])
Re: AES finalists to be announced (DJohn37050)
Re: AES finalists to be announced ([EMAIL PROTECTED])
Re: rsa prime collision (DJohn37050)
Re: AES finalists to be announced (John Savard)
Re: AES finalists to be announced ([EMAIL PROTECTED])
Re: : I AM CAVING IN TO JA... ("Douglas A. Gwyn")
Re: Americans abroad/Encryption rules? ("Douglas A. Gwyn")
Re: Americans abroad/Encryption rules? ("Douglas A. Gwyn")
Re: What is "the best" file cryptography program out there? ([EMAIL PROTECTED])
Re: Need letter frequencies (Jim Gillogly)
----------------------------------------------------------------------------
From: Jim Felling <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: frequency of prime numbers?
Date: Fri, 06 Aug 1999 16:43:48 -0500
Bob Silverman wrote:
> In article <[EMAIL PROTECTED]>,
> Jim Gillogly <[EMAIL PROTECTED]> wrote:
> > Sniggerfardimungus wrote:
> > >
> > > I ask this question here not because it necessarily relates to cryptography,
> > > but to an interest of cryptographers, prime numbers; is there any reason to
> > > believe that there are either a finite or an infinite number of primes? Even
> > > better, is there any proof either way?
> >
> > There's an infinite number of them, and an easy proof. Suppose the
> > number were finite. Then we can take the product of all the primes
> > and add one to it. This number is not evenly divisible by any of the
> > primes, since the remainder modulo each prime is 1. Therefore this
> > number is also prime
>
> NO! NO! NO!
>
> Why must we hear the same tired mistakes over and over?
>
> I have lost count of the number of times I have heard this
> assertion on the Internet.
>
> The resulting number is NOT necessarily prime.
>
> What is true is that EITHER it is prime OR it is divisible by a prime
> not on our original list.
>
> --
> 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/
> Share what you know. Learn what you don't
How about this modified proof.
Def. A prime is a number such that its only factors are 1 and itself.
Assume the primes are a finite set.P={p1,.....,pn}
then take set q=p1*p2*....*pn+1
Then q is prime ->CONTRADICTION
OR
q is not prime, in which case since q mod pi=1 for all pi, there must be a number n0
which is contained in P that is a factor of q,
if n0 has no factors other than 1 and n0 then n0 is prime, and the list is incomplete
-> CONTRADICTION
if n0 is not prime, then a number n1<n0 which is not contained in P, if n1 is
prime-> CONTRADICTION
....
if ni is not prime, then a number nj<ni exists not contained in P, if nj is prime
->CONTRADICTION
(j=i+1 is included for notational clarity)
since the sequence ni is monotone decreasing, eventually it will terminate, and that
last number nomega must have no factors other than 1 and itself, and not be contained
in P ->CONTRADICTION
Since all cases lead to contradiction our axiom is false, thus the prime numbers are
NOT finite.
------------------------------
From: Terje Mathisen <[EMAIL PROTECTED]>
Subject: Re: AES finalists to be announced
Date: Fri, 06 Aug 1999 23:50:07 +0200
Paul Crowley wrote:
> These ciphers have some disadvantage that makes it unlikely they'll
> get further: SAFER+ (too slow), Hasty Pudding (too weird), CRYPTON
> (too similar to Rijndael and some cryptanalytic results), DFC (too
> slow on 32-bit processors).
That's not true: DFC used to be one of the 3-4 slowest ciphers, but
after Robert Harley challenged myself and a couple of others to optimize
it, it became one of the 3-4 fastest ciphers instead. :-)
Using Roberts Alpha code, it is of course _the_ fastest on a 64-bit cpu.
Terje
--
- <[EMAIL PROTECTED]>
Using self-discipline, see http://www.eiffel.com/discipline
"almost all programming can be viewed as an exercise in caching"
------------------------------
From: [EMAIL PROTECTED]
Subject: Constants in hash functions
Date: Fri, 06 Aug 1999 22:02:54 GMT
I've noticed in some hash functions that some constants are declared.
My question is why? Why can't these be values generated from the
plaintext being hashed? Are they necessary?
Casey
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Yarrow RNG
Date: Fri, 06 Aug 1999 17:28:30 -0400
vincent wrote:
> ...
> What do you think about it, and is it possible that they've put a
> trapdoor inside to be (the only one to be) able to break it ?
Possible but unlikely.
> Does the fact that they provide the source code actually prove their
> sincerity ?
It's a pretty strong argument, isn't it? If you let everyone see
the code, it would be rather difficult to hide anything nasty in it.
There's also the fact that Scheier et al. have a reputation to
protect; pulling any weird stunts would destroy them forever.
paul
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: AES finalists to be announced
Date: 06 Aug 1999 15:05:12 -0700
Paul Crowley <[EMAIL PROTECTED]> writes:
> RC6: incredible simplicity, blinding performance, impressive mixing
I don't agree with this. RC6 is only fast on processors with
parallel multipliers. Where I come from (8-bit embedded controllers)
processors that can run RC6 are not too far from water-cooled mainframes ;-).
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: AES finalists to be announced
Date: Fri, 06 Aug 1999 22:21:15 GMT
In article <7oflm3$sr5$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Nonsense. If Little Tommy boy is as smarts as he thinks he is he
would
> crack it by hand in a few hours. But he is not. He is arrogant
> condescending and mostly wrong. Did you not notice hes response to the
> first post. Look at his other post too.
Did you read my post? I said posting random binaries is stupid but
gimme the c code and I will take a look. I openly admited I wanted to
challenge you.
You just don't get it do you? Posting random binary files does not
constitute a challenge. How do I know you actually followed the
algorithm?
BTW, it's funny to note you write just like Dave Scott....
Tom
--
PGP 6.0.2i Key
http://mypage.goplay.com/tomstdenis/key.pgp
PGP 2.6.2 Key
http://mypage.goplay.com/tomstdenis/key_rsa.pgp
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Factoring-Protected Exponentiation
Date: Fri, 06 Aug 1999 22:35:14 GMT
[EMAIL PROTECTED] () wrote, in part:
>...my entry in the "Biprime Cryptography" sweepstakes, if someone else
>hasn't already thought of it.
Having gone back to the discussion about finding a new name for RSA, I find that
I came up with a bunch of names - none very good:
in the original thread,
Exponential Non-Secret Encryption
Clifford Cocks Algorithm
Secret Inverse Exponent Method
Concealed Factorization Modulus Method
Composite Modular Exponentiation Method
then in the next thread
Factoring Concealed Inverse Exponent (similar to the one I've suggested now)
and I even suggested a new name for Diffie-Hellman
Mutual Exponent Product Generation
and one for public-key cryptography itself
Open-Setup Encryption
(which spawned considerable discussion; I quite admit I don't really expect that
the name should be changed at this late date)
Someone else suggested
Cocks' Two-Prime Algorithm
and there was a non-serious suggestion (note the acronym) of
Public-Use Keyed Encryption
I know my suggestions haven't been that catchy, but I was hoping they'd give
other people ideas; Biprime Cryptography is good, but perhaps someone will be
inspired to come up with something even more appropriate.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: key lengths
Date: Fri, 06 Aug 1999 22:30:29 GMT
In article <7ofi2r$pu5$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> In article <7ofeqk$ngg$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> > People like quoting big key lengths. Here are some numbers to look
at
> >
> > A 64-bit key at 2^20 keys a second, can be searched in 2^44 seconds.
> > That is 557,844 years (278,922 years average). Throw 2^20 machines
at
> > it and you are down to 194 days (97 days average).
> >
> > A 80-bit key at 2^20 keys a second, can be searched in 2^60 seconds.
> > That is 36,558,901,084 (18,279,450,542 average). Throw 2^20
machines
> > at it and you get 34,865 years (17,432 years avg.).
> >
> > A 128-bit key at 2^20 keys a second can be searched in 2^108
seconds.
> > That is 10,290,415,831,380,857,647,867,707 years ... enough?
> >
> > Basically 64-bit keys provide personal level privacy where simple
> > letters are intended as private but not life threatening. 80-bit
keys
> > are long enough to thwart any real dedicated attack (like
> > distributed.net). Maybe with 2^30 machines you can find 80 bit keys
> > but that's not likely (still would take 2^50 seconds). 128-bit keys
> > are not really searchable in this universe. It would take to long
> even
> > with every single cpu on earth working on it. With 2^40 (1
trillion)
> > computers running at 2^30 keys a second (billion) searching a 128-
bit
> > key still takes 2^58 seconds or 9,139,725,271 years (4,569,862,635
> > years avg).
> >
> > Now that this has been said. Can we stop assuming the strength is
in
> > the key length? Please?
> >
> Just you assumed that. Let us see you crack that message.
What are you talking about? (btw proofread your posts your english is
bad).
Tom
--
PGP 6.0.2i Key
http://mypage.goplay.com/tomstdenis/key.pgp
PGP 2.6.2 Key
http://mypage.goplay.com/tomstdenis/key_rsa.pgp
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: AES finalists to be announced
Date: 06 Aug 1999 22:30:01 GMT
My guesses are Rijndael, Twofish, MARS, RC6, E2 and Serpent.
Don Johnson
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: AES finalists to be announced
Date: Fri, 06 Aug 1999 22:40:39 GMT
In article <[EMAIL PROTECTED]>,
Paul Crowley <[EMAIL PROTECTED]> wrote:
> These ciphers have some disadvantage that makes it unlikely they'll
> get further: SAFER+ (too slow), Hasty Pudding (too weird), CRYPTON
> (too similar to Rijndael and some cryptanalytic results), DFC (too
> slow on 32-bit processors).
SAFER also has cryptanalysis against 192 and 256 bit keys. It is well
suited for 8-bit targets though.
> These two ciphers are just certs for the shortlist, since they're
> great all-rounders: Rijndael, Twofish. They aren't the front runners
> by every measurement, but they're never far behind the front runner.
I agree. Although both are complex (compared to RC6) but have fast
implementations.
> That leaves five candidates for three places:
> E2, RC6, MARS, Serpent, CAST-256.
>
> My guess is that MARS won't make it because it has no big wins over
> RC6, and it's more complex and not based on a fielded design, and E2
> won't make it because it doesn't have any big wins over any of them.
> That leaves these three:
E2 is wierd as well. MARS is just complex. I don't think it's gonna
win either.
> RC6: incredible simplicity, blinding performance, impressive mixing
Good history (ala RC5). Note: that it's conservative as well, keeping
with the RC5 model RC6 would only require 12 rounds for 'basic' usage
but they chose to use 20 rounds (I think it's a good idea as well).
It's also very efficient and compact.
> CAST-256: based on well-understood and widely respected design
Not terribly efficient though. I don't think CAST-256 will be on the
top of the winnings. It's not compact either.
> Serpent: conservative design and very attractive security analysis.
Nice algorithm. I think this should be in the top three (it's fast,
well analyzed...) It's also compact and reasonably fast.
> There's my guess: Twofish, Rijndael, RC6, CAST-256, Serpent. Any
> other guesses?
My Guess:
RC6, Twofish, Serpent, Rijndael, CAST-256
Tom
--
PGP 6.0.2i Key
http://mypage.goplay.com/tomstdenis/key.pgp
PGP 2.6.2 Key
http://mypage.goplay.com/tomstdenis/key_rsa.pgp
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: rsa prime collision
Date: 06 Aug 1999 22:18:54 GMT
There is a possible concern if the RNG is "chilled" in some way. By "chilled"
I mean the variability is reduced from over 2**80 to about 2**15 or so. Such
an RNG may pass the FIPS 140-1 RNG stat tests, but if a bad guy knows about the
chilling, he can do GCD on the potentially weak RSA keys. This was mentioned
in my PKS '99 talk, paper available at www.certicom.com
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: AES finalists to be announced
Date: Fri, 06 Aug 1999 22:02:25 GMT
Paul Crowley <[EMAIL PROTECTED]> wrote, in part:
>Candidates: CAST-256, CRYPTON, DEAL, DFC, E2, FROG, Hasty Pudding,
>LOKI97, MARS, MAGENTA, RC6, Rijndael, SAFER+, SERPENT, Twofish.
>These ciphers have real cryptanalytic results against them and can't
>be considered: Frog, MAGENTA, Loki97, DEAL.
>These ciphers have some disadvantage that makes it unlikely they'll
>get further: SAFER+ (too slow), Hasty Pudding (too weird), CRYPTON
>(too similar to Rijndael and some cryptanalytic results), DFC (too
>slow on 32-bit processors).
>These two ciphers are just certs for the shortlist, since they're
>great all-rounders: Rijndael, Twofish. They aren't the front runners
>by every measurement, but they're never far behind the front runner.
>That leaves five candidates for three places:
>E2, RC6, MARS, Serpent, CAST-256.
>My guess is that MARS won't make it because it has no big wins over
>RC6, and it's more complex and not based on a fielded design, and E2
>won't make it because it doesn't have any big wins over any of them.
>That leaves these three:
>RC6: incredible simplicity, blinding performance, impressive mixing
>CAST-256: based on well-understood and widely respected design
>Serpent: conservative design and very attractive security analysis.
>There's my guess: Twofish, Rijndael, RC6, CAST-256, Serpent. Any
>other guesses?
I'll have to admit I'm inclined to think that MARS will make it in, although I'm
not sure which of your guesses it will displace. But I think your analysis is
very thoughtful.
I'm surprised, though, to hear that SAFER+ is too slow, although I think it
should have had a better key schedule.
I definitely do agree that Twofish belongs on the shortlist, although I've heard
other people exclude it from their list of guesses.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: AES finalists to be announced
Date: Fri, 06 Aug 1999 21:56:24 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
> [EMAIL PROTECTED] wrote, in part:
> >In article <[EMAIL PROTECTED]>,
> > [EMAIL PROTECTED] (John Savard) wrote:
> >> [EMAIL PROTECTED] wrote, in part:
>
> >> > You dont know much that file is not currupted it is simple to
crack
> >but
> >> >beyond you. Its now in seperate thread just for you oh little one.
>
> >> Who cares? Read the FAQ on why that sort of thing is a waste of
> >> time...
>
> > I cares. Read the charter on why.
>
> The sci.crypt charter is as follows:
>
> >sci.crypt Different methods of data en/decryption.
>
> >It is not. It is reserved for discussion of the _science_ of
cryptology,
> >including cryptography, cryptanalysis, and related topics
> I don't see what in there is supportive of your challenge.
>
You does not? Its cryptanalysis.
> As it is quite easy - even without using an encryption method that is
genuinely
> secure - to encrypt a message in such a way that decrypting it would
take an
> inordinate amount of work, the fact that I could cook up a message
that you
> couldn't break wouldn't prove that I was smarter than you.
>
> That sort of tactic is, quite appropriately, undeserving of a response
and of
> whatever time and effort might be required to solve the challenge
message
> involved.
>
Nonsense. If Little Tommy boy is as smarts as he thinks he is he would
crack it by hand in a few hours. But he is not. He is arrogant
condescending and mostly wrong. Did you not notice hes response to the
first post. Look at his other post too.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: : I AM CAVING IN TO JA...
Date: Fri, 6 Aug 1999 22:14:02 GMT
"Thomas J. Boschloo" wrote:
>Support the Anybrowser Campaign! <http://www.anybrowser.org/campaign/>
I second the motion.
Unless the purpose of your Web page is significantly furthered
by using multimedia, programmable applets, etc. the best thing
is to keep it clean and simple. There are even some Lynx users
out there, for example blind persons, or just people who can't
stand how long it takes to download all the graphics, audio,
etc. one finds on many Web pages.
If you want television, you know where to find it.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Americans abroad/Encryption rules?
Date: Fri, 6 Aug 1999 22:23:07 GMT
Serge Paccalin wrote:
> - You DO need to learn a secret to decode ROT-N (namely, the value of
> N), so ROT-N is encryption. The algorithm is weak (frequencies...) and
> the key is laughably short (< 5 bits), but that's another matter...
For messages of very modest length, you don't need to learn
a secret to decode the ROT-N message.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Americans abroad/Encryption rules?
Date: Fri, 6 Aug 1999 22:20:32 GMT
John Myre wrote:
> BTW, does anyone know who first discovered this representation
> [355/113] of pi?
It's presumably in Petr Beckmann's "History of Pi".
As I recall, it goes back to "Biblical" times
(although not within the Bible itself, which uses
a much cruder estimate).
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: What is "the best" file cryptography program out there?
Date: Fri, 06 Aug 1999 22:25:33 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
> [EMAIL PROTECTED] wrote, in part:
>
> >That form of implicit trust scares me. What makes a 1024 bit key
less
> >secure then a 4096 bit key? (And if you say ease of solving you have
> >no clue about the crypto world).
>
> Well, a 1024 bit RSA modulus or D-H public key may not be crackable
today. But
> compare a Pentium III with a 6502. Computers are getting faster! And
factoring
> and other such attack algorithms are improving too.
The problem is not speed. It's memory. The matrix step in
512/768/1024 bit keys is quite large. The resources required is quite
large. I would read the RSA stuff on TWINKLE to find out more.
>
> (However, baldly claiming that 2048 is insecure, and changing to 4096
is
> _necessary_, *does* remind me of David A. Scott. One might suggest
doing so to
> be on the safe side, but a simple assertion that 2048 is insecure
_is_ kind of
> far-out.)
Claiming that 512-bit keys are insecure is not right. Although it will
be soon possible to factor them. I made 768 bit keys because they are
somewhat secure and they are fast (on my 486).
Tom
--
PGP 6.0.2i Key
http://mypage.goplay.com/tomstdenis/key.pgp
PGP 2.6.2 Key
http://mypage.goplay.com/tomstdenis/key_rsa.pgp
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Need letter frequencies
Date: Fri, 06 Aug 1999 16:42:23 -0700
"Douglas A. Gwyn" wrote:
> The question that should be asked is, "To what use are these frequencies
> to be put?" I find that many novice cryptanalysts place too much
> reliance on such frequency tables. A particular piece of plaintext
> (unless it is *really* huge, such as your complete Sherlock Holmes)
> is unlikely to match the frequencies better than very roughly,
> especially the n-gram (for n>1) frequencies.
I use a common framework program to solve about 7 dozen kinds of
classical ciphers, and for undoctored English I find a tegragraph
table drawn from a very large sample of English lit (mostly Gutenberg,
but with a lot of other stuff thrown in) does an excellent job as the
basis for an evaluation function. It's pretty well populated: about
1/4 of the possible tetragraphs have a frequency entry, however small.
For foreign languages I use trigraphs, since I haven't gone to as
much trouble to accumulate data and the tetragraph tables would be
correspondingly sparser and thus less discriminating. However, in
a pinch I'll use a table from a related language to solve a cipher,
and it's typically good enough.
I find that a good general frequency table gives better results than
a sloppy small one.
--
Jim Gillogly
14 Wedmath S.R. 1999, 23:35
12.19.6.7.12, 4 Eb 20 Xul, Eighth Lord of Night
------------------------------
** 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
******************************
