Cryptography-Digest Digest #324, Volume #10 Tue, 28 Sep 99 15:13:04 EDT
Contents:
Re: Compress before Encryption (Tom St Denis)
Re: Need advice for encrypting information (James Felling)
Re: Hardest ever ECDL solved by INRIA researcher and 195 volunteers (Robert Harley)
Re: Comments on ECC (Patrick Juola)
Re: frequency of prime numbers? ("karl malbrain")
Re: Hardest ever ECDL solved by INRIA researcher and 195 volunteers (DJohn37050)
Re: Schrodinger's Cat and *really* good compression (Mok-Kong Shen)
Re: msg for Dave Scott (Tom St Denis)
Re: NEMA, Swiss cipher machine (Frode Weierud)
Re: factoring with quadratic sieve (Bob Silverman)
public/private/session keys (Tom St Denis)
Re: Electronic envelopes (Anton Stiglic)
More Comments on ECC (Medical Electronics Lab)
Bit commitment via hash and coin flipping ([EMAIL PROTECTED])
Re: review of peekboo please? (Medical Electronics Lab)
Re: ECC97 Challenge Solved (Medical Electronics Lab)
Re: Electronic envelopes ("Richard Parker")
Re: Please review proposed rebuttal... (Bob Silverman)
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Compress before Encryption
Date: Tue, 28 Sep 1999 13:50:05 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Hasn't this holy war gone on long enough? When do you ever quit?
>
What I don't get is almost EVERYONE agrees that compression before
encryption is a good idea. So why is he carrying this on?
What I don't agree with is saying that compression is the pancea of
security, or that you have to use a bad method like huffman coding to
get secure documents. I would use compression to make the messages
smaller. True they might be a tad harder to brute force (the difficulty
goes up linearly not exponentially with message size, which is why I say
why not use larger keys if you are paranoid. I.e instead of doing 256
passes to get an 2^8 improvement (assuming the cipher is not a group)
why not just add 8 bits to the key?). But some unknown person will
acknowledge this.
Oh well, maybe he will let it drop (i.e if you can't be open to an idea,
might as well remain closed to all).
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: James Felling <[EMAIL PROTECTED]>
Subject: Re: Need advice for encrypting information
Date: Tue, 28 Sep 1999 09:26:35 -0500
Tom St Denis wrote:
> In article <[EMAIL PROTECTED]>,
> yoni <[EMAIL PROTECTED]> wrote:
> > I thought of encrypting each record on its own - if I always use the
> > same key (lets say in RC4 128 bits) hashed with the position index of
> > the record - is it more secured ?
> > Can't someone try to gather information about my key if all objects
> > starts the same (or very simillar) ?
> > Thanks for the advice, I will look in the book.
>
> Well in peekboo for example I did this
>
> Session_Key = HASH(PASSWORD + SALT)
>
> This way you can use the same password for quite sometime but no messages
> will be encrypted with the same session key (unless you pass n/2 messages
> ,where n is the 2^sizeofsalt ... etc...). This way if you find one session
> key you have to reverse the HASH to find the password ...
>
A technical quibble. It is possible that you get lucky and have two messages
in a row have the same salt( you are picking randomly aren't you?). I think
what you neant is that the probability of two messages having the same salt+
password combo is 1- (( 1 - (2^(-n)) )^m). where m = number of nessages
sent. Your n/2 figure sounds like you are expecting a birthday type
coincidence -- actually in theory you could send n messages and never have a
duplicate key used -- mind you it is so unlikely as to be ludicrious for any
reasonable sized n)
>
> Tom
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: Robert Harley <[EMAIL PROTECTED]>
Subject: Re: Hardest ever ECDL solved by INRIA researcher and 195 volunteers
Date: 28 Sep 1999 16:19:50 +0200
Don Johnson writes:
> Also check out www.certicom.com.
Why do that?
To read a press release with less info, mistakes, and that goes out of
its way to avoid giving credit where it is due?
Like I said, much better to get the info from the horse's mouth at:
http://pauillac.inria.fr/~harley/ecdl/
Rob.
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Comments on ECC
Date: 28 Sep 1999 10:31:54 -0400
In article <[EMAIL PROTECTED]>, Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>Patrick Juola wrote:
>> In article <[EMAIL PROTECTED]>, Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>> >Unless somebody also invents an algorithm for converting
>> >any NP-complete problem into a P problem, knowing that
>> >P=NP wouldn't be of any practical use.
>> Cook invented most of such an algorithm in 1971 -- a problem
>> that is known to be NP-complete can be used to solve ANY problem
>> in NP by suitable formulation of the inputs, and the process
>> of proof of NP-completeness gives such an algorithm. All
>> we lack is the ability to reduce one such program to P.
>
>In other words, we don't have a glimmer of an algorithm.
We also don't have any evidence to support the claim that P=NP.
If you assume that we know, for whatever reason, that P=NP, then
that knowledge will *give* us the algorithm we need.
-kitten
------------------------------
Reply-To: "karl malbrain" <[EMAIL PROTECTED]>
From: "karl malbrain" <[EMAIL PROTECTED]>
Subject: Re: frequency of prime numbers?
Date: Tue, 28 Sep 1999 08:23:47 -0700
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> karl malbrain wrote:
> > It's time to ANTE up guys. No, you cannot DIFFERENTIATE anything from
> > ZEROES, you just get more zeroes. Have the COMPILER emit a warning
message
> > for( !! ) if you must, else dismiss as a SINGULARITY at run-time. Karl
M
>
> Are you a buzzword-generation program, or a person?
I'm not aware that any LISP implementations own sufficient PROPERTIES to be
classified alongside a person.
In any event, we're talking about the notion of !!<<logical expression>> in
the compiler syntax rules. Not since IBM GENEVA came up with complete PL-1
semantics AND syntax in 1968 have I seen anything close to what YOU seem to
suggest here as a question. As for luck, Thanks, but, no-thanks. Karl M
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Hardest ever ECDL solved by INRIA researcher and 195 volunteers
Date: 28 Sep 1999 15:44:36 GMT
I am not sure I understand.
I see your name mentioned in the Certicom press release and a hot link pointer
to your press release. Your release rightly gives the details on the credit of
those involved. I would think people would want to read all "takes" on this
significant work of yours.
Don Johnson
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Schrodinger's Cat and *really* good compression
Date: Tue, 28 Sep 1999 15:45:50 +0200
John Myre wrote:
>
> a concept that you don't say directly. The experiment is the
> real story. You could really do the experiment, although you
> wouldn't learn anything, since the interesting part is before
> you open the box to find out what happened!
I read that the practical functioning of quantum computing depends
on a certain quantity termed 'decoherence time' having a not too small
value. When the experimenter in the Schroedinger experiment opens
the box and looks into it, his brain circuits need some finite time
to do the appropriate switching in order to be able to see the
objects inside the box. I guess this neuro-chemical/electrical
time of the 'thought' or 'non-thougt' (actual) cat experiment is
then what corresponds to (or perhaps actually IS) the decoherence
time. It is my layman's humble (maybe entirely nonsensical) view
that Schroedinger's cat is of the same genre as the twin paradox,
both are very famous, genious and both are totally confusing man's
mind in unnecessary ways. Fortunately we don't have such stuffs in
cryptology, excepting perhaps (I am not quite sure either way)
in some remote sense the ideal OTP.
M. K. Shen
=============================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: msg for Dave Scott
Date: Tue, 28 Sep 1999 16:28:27 GMT
In article <[EMAIL PROTECTED]>,
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
> Tom St Denis wrote:
> > So generally a 'blind' keysearch is the only way.
>
> Not even close.
Ok name one popular symmetric algorithm that can be solved without using
brute force?
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Frode Weierud)
Subject: Re: NEMA, Swiss cipher machine
Date: 28 Sep 1999 16:20:44 GMT
Reply-To: [EMAIL PROTECTED]
[EMAIL PROTECTED] (John Savard) writes:
>I'll probably add a brief description of it to my web page, on the
>same page as I describe the FIALKA and other cipher machines similar
>to the Enigma. (That is, if you have no objection.) However, with the
>notation I use in my schematic diagrams, the drive rotors will become
>pinwheels - and they will be in one row, with the contact rotors in
>another row. (The text will note the discrepancy.)
I have nothing against you putting up something about the NEMA on
your Web page, but I would advice you to wait until you have read
the article as not everything is as straight forward as it looks.
>As I understand it, the red rotor and two of the drive rotors move
>with every letter enciphered, while the other two drive rotors are
>controlled by the red rotor (and whenever a drive rotor is thus
>prevented from moving, its accompanying contact rotor also does not
>move). While the machine has a large number of initial settings, that
>means its period is only 676, but I suppose that was considered
>adequate, and regulations limited the length of the segment of a
>message that could be enciphered at a single setting.
The period of the machine is 17576. The reason for this will be
apparent when you have looked at the stepping configuration in
detail.
Frode
--
Frode Weierud Phone : +41 22 7674794
CERN, SL, CH-1211 Geneva 23, Fax : +41 22 7679185
Switzerland E-mail : [EMAIL PROTECTED]
WWW : home.cern.ch/~frode
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: factoring with quadratic sieve
Date: Tue, 28 Sep 1999 16:43:55 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> hi
>
> i would like to know how to choose the number of elements in the
factor base.
> possibly automatically.
For what size number?
For up to 90 digits you can find complete info in:
The Multiple Polynomial Quadratic Sieve
Math. Comp. V. 48 pp. 329-340 Jan 1987
For over 90 digits you will need to extrapolate.
Note also that the answer depends on a number of other factors:
How long you chose for a sieve interval per polynomial
The size of the upper bound on large primes
How much memory your machine has for dealing with the matrix.
etc.
--
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: Tom St Denis <[EMAIL PROTECTED]>
Subject: public/private/session keys
Date: Tue, 28 Sep 1999 16:51:34 GMT
Apparently alot of people are getting confused about how the keys are used in
peekboo. Maybe my site is not clear enough, at any rate here is an
explanation.
The public/private keys are based on the discrete logarithm problem. I.e
it's easy to calc
X = g^x mod p
but hard to find x from X. This one-way function also has algebraic
structure that Diffie and Hellman exploited in their key exchange
Y = g^y mod p
k = Y^x mod p
k' = X^y mod p
k = k'
Well the public/private keys in Peekboo work exactly the same way. Now here
is the tricky part, instead of encrypting session keys with these numbers we
have a shared secret (k). Now for each message there is a session key:
Si = SHA(k + SALTi)
Where i is the current index into the salt. Think of it this way. The salt
is 64-bits this means you can have 2^64 variations (or session keys) as long
as there are no collisions in SHA.
In Peekboo the SALT is found by xoring some of the hash + time to get
SALT1 = h1 xor h2 xor h3 xor time_in_seconds
SALT2 = h4 xor h5 xor time_in_milliseconds
SALT = SALT1 + SALT2 (concatenation)
I hope this clears it up, and if anybody has any questions or comments plase
ask me here or in private. BTW I know about the bday paradox and I figured
nobody is going to send the avg 2^32 messages to make it a problem anyways..
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Electronic envelopes
Date: Tue, 28 Sep 1999 13:35:54 -0400
==============2BD276097B14FDC2EA4F5647
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
>
The sole fact that you use time is enough to say that
it can't work. Time is relative, you would need a trusted
central unit that would give you the exact time. If you have
a trusted central unit (authority) U, Alice and Bob could just
agree with U about the time U is to reveal the ciphertext to Bob.
It isn't more complicated than that!
Anton
==============2BD276097B14FDC2EA4F5647
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
<blockquote TYPE=CITE><a
href="http://home.t-online.de/home/mok-kong.shen"></a> </blockquote>
The sole fact that you use time is enough to say that
<br>it can't work. Time is relative, you would need a trusted
<br>central unit that would give you the exact time. If you have
<br>a trusted central unit (authority) U, Alice and Bob could just
<br>agree with U about the time U is to reveal the ciphertext to Bob.
<p>It isn't more complicated than that!
<p>Anton
<br> </html>
==============2BD276097B14FDC2EA4F5647==
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: More Comments on ECC
Date: Tue, 28 Sep 1999 12:32:43 -0500
This is from the INRIA press release:
:Arjen K. Lenstra, Vice President at Citibanks's Corporate Technology
:Office in New York and one of the main contributors to the recent
:successful attack on the RSA-155 challenge, compared the two
:computational efforts and noted that the present result makes 160-bit
:ECC keys look even better compared to 1024-bit RSA keys, from a
:security point of view. "Ideally we would like new theoretical advances
:to further reinforce these practical results, although such advances
:appear out of reach for the moment."
Congratulations to the ECC2-97 team, good luck on knocking off 102.
I also concur with Harley's sentiment (from the 4k-associates PR):
>"We are now close to the 112-bit limitation that many Western
>governments impose on exportable ECC software via the Wassenaar
>Agreement." said Mr. Harley. "Our repeated successes are
>demonstrating that such short keys offer a wholly inadequate level of
>security. These export restrictions, while claimed to be in the public
>interest, in fact facilitate industrial espionage, hinder global
>competition and limit people's right to privacy."
'nuff said.
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED]
Subject: Bit commitment via hash and coin flipping
Date: 28 Sep 1999 17:43:48 GMT
I am referring here to pages 87 and 88 of AC (2nd edition).
Basically, why wouldn't this work instead:
(1) Alice generates on random-bit string R.
(2) Alice creates a message of (R,b)
(3) Alice computes and sends/publishes H(R,b).
To confirm:
(4) Alice sends/publishes (R,b).
(5) Bob computes H(R,b) and compares it to the original message.
Also, I'm going to be using a version of this for an application I'm
writing to roll dice fairly. The stakes here are low (no money
involved), and user-friendliness is important. I'm going to be using
MD5 as the H() above (because it's readily available to me). How many
bits of the hash would be sufficient to prevent Alice from cheating?
At the moment, for my purposes, I'm thinking 32 bits, since that's 8
hex characters, and relatively easy to type. How much work is involved
to find a (R',b') such that H(R',b')[32 bits]==H(R,b)[32 bits] in
terms of time on a PC?
--
Sent via USENET
Learn what you know. Share what you don't. -- [EMAIL PROTECTED]
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: review of peekboo please?
Date: Tue, 28 Sep 1999 12:48:30 -0500
Tom St Denis wrote:
> 1) Ease of use (can a newbie use it?)
Yeah, after a little help. A stoned hippy couldn't come close
to making it work.
> 2) Flexibility (does it do what it's
> suppose todo?)
Seems to. Once I got used to it, seems pretty simple.
>3) Source code readability and neatness (is it put together in
> a responsible fashion?
Haven't got that far :-)
>4) Efficiency (Does it run in a resonable amount of
> time? Is it too big?)
Encrypt/decrypt is a blink on my ancient 66MHz Pentium original.
Takes forever (about 2.5 minutes) to create the DH key tho.
Patience, persistence, truth,
Dr. mike
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: ECC97 Challenge Solved
Date: Tue, 28 Sep 1999 12:42:21 -0500
Sam Simpson wrote:
>
> http://www.certicom.com/press/99/sept2899.htm
>
> It is interesting to note that this challenge took ~16,000 MIPS-years
> whilst an 512-bit RSA key took ~8,000 MIPS-years.
>
> Any comments on the press release?
I liked INRIA's press release a touch better. There were more quotes
to steal :-) They really all say the same thing. I liked the section
in INRIA's PR where they point out that the search process got very
lucky and found 2 points within an hour of each other (less than 1
in a 100 chance of that they say). That points out that luck is
still a factor in cracking anything. But even with luck, the ECC
problem is harder.
Which has always been "obvious", but at least now there's some
empirical evidence to back that up.
Patience, persistence, truth,
Dr. mike
------------------------------
From: "Richard Parker" <[EMAIL PROTECTED]>
Subject: Re: Electronic envelopes
Date: Tue, 28 Sep 1999 17:57:58 GMT
> Why not skip all the crypto and just have the "trusted clock" release the
> message on time? All your system does is add another person to the loop.
Consider a system that has many senders and many receivers. A trusted
party who holds all of the messages until the release time would scale
poorly and introduces many additional risks.
-Richard
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Please review proposed rebuttal...
Date: Tue, 28 Sep 1999 17:52:05 GMT
In article <7spki3$hdo$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Bill Unruh) wrote:
> In <[EMAIL PROTECTED]> "me" <[EMAIL PROTECTED]> writes:
<snip>
> Sorry. Too many problems.
>
> What has been shown is that 512 bit key (any organisation's
> 512 bit key) is breakable with modest resources (modest for a
reasonable sized organisation).
One needs a very large Cray-class machine to deal with the matrix.
(fairly big bucks, i.e. $5-10 Million)
Might I ask if you either:
(a) forgot about this requirement. (no flame intended)
(b) consider it a 'modest' resource?
I have all the resources (and code!) to break a 512-bit key EXCEPT
for dealing with the matrix in reasonable time. And I would consider
RSA Security as a 'reasonable sized' organization.
--
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.
------------------------------
** 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
******************************
