Cryptography-Digest Digest #364, Volume #10 Mon, 4 Oct 99 23:13:04 EDT
Contents:
Re: Is 128 bits safe in the (far) future? (Bruno Wolff III)
Re: Factoring public keys attack? (Kurt Wismer)
Re: EAR Relaxed? Really? ("karl malbrain")
Re: Factoring public keys attack? (James Felling)
Re: Perfect Shuffle Algorithm? (Douglas Zare)
Re: Announcement of results ([EMAIL PROTECTED])
Re: Compress before Encryption ("Richard Parker")
Re: ECC97 Challenge Solved (Christopher Biow)
Newbie Question -- Matrix multiplies in Twofish ("Les Lawrence")
Re: Factoring public keys attack? (Bob Silverman)
Pocket (Quantum) Calculators? FW : Europe's banking codes have been cracked in the
blink of an eye (Ron Cecchini)
Re: Factoring public keys attack? ([EMAIL PROTECTED])
Re: True Random numbers (Johnny Bravo)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Bruno Wolff III)
Crossposted-To: comp.security.pgp.discuss,alt.security.pgp
Subject: Re: Is 128 bits safe in the (far) future?
Date: 4 Oct 1999 21:21:31 GMT
Reply-To: [EMAIL PROTECTED]
>From article <[EMAIL PROTECTED]>, by "Thomas J. Boschloo"
><[EMAIL PROTECTED]>:
>
> What I am basically interested in is a encryption product that hasn't
> got a timebomb in it. Like the Y2K bug. 128 bits may be secure for now,
> and may remain so for the next hundred years, but after that you need to
> change all software. And maybe we won't be alive by then (very likely),
> but that's no reason not to put these things in software now! It's not
> like we are using 96 bit encryption now, just because it is safe. Why
> not use a bitlength that is safe forever?
Twofish can use 256 bit keys. The OPEN PGP RFC (2440) has defined a code of
10 for 256 bit Twofish. So it is probably supported by GNUPG. If not, it
shouldn't be hard to change GNUPG to use it.
If you don't trust 1024 bit public keys (DH or RSA), than distribute keys
to your correspondants securely and use conventional encryption.
------------------------------
From: [EMAIL PROTECTED] (Kurt Wismer)
Subject: Re: Factoring public keys attack?
Date: Mon, 4 Oct 1999 21:54:08 GMT
DJohn37050 ([EMAIL PROTECTED]) wrote:
: Gosh, are there lots of primes?
: Don Johnson
? there's a countably infinite number of them...
--
Making sure everyone gets Internet access whether they can afford it or not.
The Toronto Free-Net needs your support to help pay for continued operation.
Donors (personal or corporate) of $25+ can receive charitable tax receipts.
Please see http://www.torfree.net for office contact details.
------------------------------
Reply-To: "karl malbrain" <[EMAIL PROTECTED]>
From: "karl malbrain" <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: EAR Relaxed? Really?
Date: Mon, 4 Oct 1999 15:18:41 -0700
SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote in message
news:7tb81i$pmi$[EMAIL PROTECTED]...
> In article <rz8K3.94$[EMAIL PROTECTED]>, "karl malbrain"
<[EMAIL PROTECTED]> wrote:
(...)
> >They can say that any encrypted file on your computer `decrypts' to
anything
> >they say it does, and you have no defense against it. Whenever the FBI
has
> >investigated itself in the past, they find criminal behaviour without
> >criminals. How can you defend yourself against an agency like that????
Karl
> >M
>
> I guess the only hope we have is if people start electing honest
politicans
> like Jessie Ventura. Since none of the current main stream politicians
even
> give a rats ass about honesty or the constitution. With an honest justice
> department it might even be possible to get there killers that specialize
> in shooting unarmed women holding babies in jail as well as the bosses
that
> ordered the killings.
What is Jesse Ventura, or anyother candidate from any of the EXISTENTIAL
parties going to do about millions of civil servants constituted as the
SECRET POLICE of the 21st Century??? This is an ORGANIZATIONAL problem, not
a single POLITICAL one. Karl M
------------------------------
From: James Felling <[EMAIL PROTECTED]>
Subject: Re: Factoring public keys attack?
Date: Mon, 04 Oct 1999 16:57:40 -0500
UBCHI2 wrote:
> Instead of trying to factor a prime based public key after somebody has used
> it, why not have a lookup table of all the keys. It is quicker to create the
> keys than to factor a key. So just do the following:
>
> 1) 10-20 Years ago, you started your massively parallel computers creating all
> possible prime based keys for 128, 512, 1024 and 2048 bit keys. You made the
> keys so you also know the primes. Don't do any factoring at all.
And now you are about 10^-1500'th of the way through this project(I am being fairly
optimistic there. You have secertly hidden the values of all these primes by
encoding them at a rate of 2 bits/hydogen atom, and are just finishing up with the
Milky Way storage project and moven on to your Andromeda Galaxy storage for more
space.
>
>
> 2) Now just use a lookup table of the all keys you created to determine the
> two primes that an encryptor is using. This is sort of like the "Find" file
> command in windows. This eliminates the need for factoring. It also takes
> advantage of the fact that creating keys is quick and can be done in advance.
>
> Why do people think that factoring cryptanalysis will only start once a key is
> used? The government could have just been making keys for the past 20 years to
> put on its lookup table. Then if you use one of the keys of the standard
> lengths, they already know the primes. Wouldn't this work against the public
> key system?
Not in 10^20 years.
------------------------------
From: Douglas Zare <[EMAIL PROTECTED]>
Crossposted-To: sci.stat.math,sci.math
Subject: Re: Perfect Shuffle Algorithm?
Date: Mon, 04 Oct 1999 18:52:58 -0400
Dan Day wrote:
> [...]
> I've seen magicians who can quickly perform perfect shuffles
> at will (and also split a deck into two even stacks of 26).
> As a parlor trick, they shuffle a new deck N times (I forget
> the proper "N", but I'm sure you guys can easily figure it out),
> returning it to its original order, freaking out audience members
> who aren't aware of the cycles involved.
Splitting a deck into two even stacks seems quite reasonable; numerous tricks
require that one discreetly place a card into the nth position, though usually n
is smaller. But perfect shuffles are relatively hard. I expect that this would
be a high-risk trick for most magicians even after much practice. It would be
much easier to _say_ that you are performing 8 perfect shuffles, or look like
you are, but either perform false shuffles (you can push the interleaved halves
into opposite hands instead of squaring and cutting) or just switch decks.
I'd like to see someone who can cut the deck with a binomial distribution. I
would guess that it is very difficult to train yourself to have a particular
non-uniform distribution.
Douglas Zare
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: comp.theory
Subject: Re: Announcement of results
Date: Mon, 04 Oct 1999 22:14:52 GMT
In article <[EMAIL PROTECTED]>,
E C D L Account <[EMAIL PROTECTED]> wrote:
>
> Could I take this opportunity to invite comments on the following
paper:
>
> http://www.angelfire.com/nv/papers
>
> The main point of this paper (that I am hosting for the author) is a
> construction which claims to use coherent optics and the wavefront
> reconstruction property to solve various computationally hard problems
> (that is NP-complete problems, and trapdoor functions such as prime
> factorisation).
>
> This is an extraordinary claim, and although the paper has now been
> distributed for several months to a number of researchers in the
field of
> optics and computational complexity, the author (perhaps
understandably)
> wishes to remain anonymous at this stage.
>
> Please direct all e-mail correspondence to either the appropriate
> newsgroup, or the e-mail address given at the site mentioned. (i.e.
not to
> this e-mail address)
>
I have a few of comments to make on "Squ. t. P"'s paper, "The logic
Camera Obsura".
The labels used in the text don't seem to match up with those in the
illustrations. And for whatever reasons, I couldn't print figures 7 -
9. Oh well.
If the construction worked you wouldn't need to bother with diffraction
gratings, coherent sources of light, or other such hardware. You could
hack it up on your PC. Order all the relevent pinholes in the
construction according to their distance from the source. Then you can
easily compute the illumination and phase of each pinhole from its
predecessors, since you know their distances. This would work just as
well in the reverse direction.
But this won't work. After discussing the construction of a XOR gate,
the author glibly states:
Of course, suitable choices of other conditions for placement
of the points p and ~p, with regard to constructive
and destructive interference, can be used to express any
binary logic gate.
This set off the warning buzzer. After all, XOR is information
preserving, so it's no surprise you can do it with a linear process
like light superposition. But AND and OR are a different matter.
Here's the proof that you can't build an AND gate this way:
Let's try to build such an AND gate.
Let a, b, ~a, and ~b be points on the X "input" plane, and p be a point
on the Y "output" plane. We want to arrange a, b, ~a, and ~b and
choose p so that:
(1) Illuminating a and b (but not ~a or ~b) produces constructive
interence at p.
(2) Illuminating only a and ~b, or only ~a and ~b, or only ~a and b,
produces destructive interference at p.
Let A denote the distance from point a to point p. Likewise ~A denotes
the distance from point ~a to point p, etc.
The "destructive conditions" (2) give:
A - ~B = pi(2n + 1)
~B - ~A = pi(2m + 1)
~A - B = pi(2q + 1)
where n, m and q are integers. Adding the above three equations, we
get:
A - B = pi(2(n + m + q) + 3)
= pi(2r + 1) where r = n + m + q + 1.
So when only points a and b are illuminated they interfere
destructively at p, contradicting condition (1). Of course the same
argument can be used to show that OR gates or not possible.
There are good reasons why physicists designing real optical gates have
to go through the trouble of using nonlinear processes.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Richard Parker" <[EMAIL PROTECTED]>
Subject: Re: Compress before Encryption
Date: Mon, 04 Oct 1999 22:53:13 GMT
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
> Using "C" and "C'" for the forward and reverse mapping,
> for all m in V*: C(m) and C'(m) are well defined and in V*.
> for all m in V*: C'C(m) == m and CC'(m) == m.
I agree.
> Since V* is open-ended (and denumerably infinite), there are some
> interesting questions about algorithm termination, etc.
Yes, since V* is countably infinite the properties which we are
discussing are not sufficient to guarantee that a compression
algorithm will terminate. Conventional adaptive Huffman compression,
and David Scott's scheme in particular, do not share this concern
since for these algorithms the amount of expansion that can occur when
an input is compressed can be proved to have a finite bound.
It is, however, an interesting point.
> I don't think the name "symmetric" properly captures the essence.
> "Universal", "complete", or "covering" is closer..
I don't think "complete" is a good choice, but I think there is an
argument that makes use of both "symmetric" and "universal". If David
Scott's compression function C is used to define a binary relation
R = {<x,y> in V* x V* : y = C(x)}
then, unlike conventional compression, the symmetric closure is
s(R) = V* x V* = U.
So the distinguishing property of David Scott's scheme is that the
symmetric closure of the compression relation is the universal
relation on V*.
I'm afraid that this doesn't really get me much closer to finding a
convenient name for his scheme. The phrase "symmetric-closure-
universal compression" doesn't exactly roll off the tongue.
-Richard
------------------------------
From: Christopher Biow <[EMAIL PROTECTED]>
Subject: Re: ECC97 Challenge Solved
Date: Mon, 04 Oct 1999 18:20:37 -0400
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
>One of my favorite stories concerns Dirac. Reportedly, after he
>gave a presentation at a seminar, he stated that he would now be
>happy to answer questions from the audience. One member said:
>"Professor Dirac, I don't see how you derived that [specific]
>equation.", to which Dirac replied "That is not a question. Next?"
Dirac and Trebec are actually the same name, if spelled sideways in
Slovenain.
------------------------------
From: "Les Lawrence" <[EMAIL PROTECTED]>
Subject: Newbie Question -- Matrix multiplies in Twofish
Date: Mon, 4 Oct 1999 19:34:30 -0400
Twofish makes extensive use of matrix multiplies (RS,MDS). I understand
matrix multiplies in an algebraic sense but my feeble attempts to duplicate
the test results (even the simple task of generating the S-Box keys) on my
hand calculator fails. Would someone please describe the nit gritty of how a
matrix multiply is performed in crypto math, i.e. the element by element
multiplication and summation?
Thanks.
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Factoring public keys attack?
Date: Tue, 05 Oct 1999 00:00:49 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (UBCHI2) wrote:
> The point I'm making is also that you don't need to make a lookup table of all
> keys less than 512 bits. You only need to make a lookup table of keys that are
> exactly 512 bits. This is because everyone sets there key length to exactly
> 128, 512, 1024 or 2048. This creates a vulnerability.
I suggest that you count how many keys there are of length 512.
I suggest that you count how many there are of length less than 512.
Hint: How many 10 digit numbers are there? How many numbers
less than 10 digits are there?
Do the arithmetic. Then get back to us.
>
--
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: [EMAIL PROTECTED] (Ron Cecchini)
Subject: Pocket (Quantum) Calculators? FW : Europe's banking codes have been cracked
in the blink of an eye
Date: Tue, 05 Oct 1999 00:40:10 GMT
Reply-To: [EMAIL PROTECTED]
So, what are the Israelis talking about?
i thought we were still a *looong* way off from actually
building something like the hypothesized "quantum computer".
Are the Israelis "blowing smoke" or what?
..................
http://www.sunday-times.co.uk/news/pages/tim/99/09/29/timintint02001.html?1341861
Europe's banking codes have been cracked in the blink of an eye
�
End of the Enigma: Quantum Computing will spell the end of conventional
encryption, such as the codes broken at Bletchley Park
No safety in numbers
BEN HAMMERSLEY
[EMAIL PROTECTED]
After an Israeli research institute said it could break
Europe's banking codes in less than a second, a initiative
has been launched that could result in unbreakable codes.
The European Institute of Quantum Computing Network
was launched on Monday, to bring companies and
research labs throughout Europe together in the hope that
the new technology - Quantum Computing - can be taken
from the theory to the high street.
The institute was founded a few weeks after news leaked
from the Israel's Weizmann Institute that it was using a
mixture of quantum computing and special optical
technology to break the RSA-512 code, the system used
by the European banking system. It claims it has
developed a hand-held device that can break the code in
12 microseconds.
Quantum computing works by taking advantage of the
peculiar characteristics of subatomic particles. Whereas a
normal computer relies on a signal - or bit - being either
on or off, a quantum bit can be both on and off at the
same time. This unusual ability means a great deal more
information can be stored. While a regular computer
works through each sum one at a time, a quantum
computer can do every operation at the same time.
This, the EIQC says, offers, "not just incremental
improvements, but a fundamental breakthrough" in
computing power - enough for code-breaking,
voice-recognition and translating computers to be simple
to build.
The second aspect of Quantum computing, however, will
help to make information more secure. Using a feature
called "quantum entanglement", information could be sent
between two computers that could not be eavesdropped
upon without the two computers' knowledge. Because
quantum physics dictates that monitoring a subatomic
particle changes its state; not only would an eavesdropper
announce his presence, but the message would be
garbled.
"A hacker wouldn't know where to start," says Jonathan
Curtis of Quantum Electronic Devices.
As one member of EIQC, who wished to remain
anonymous, predicts: "While quantum computers may be
some time off, when they are available no communication
will be secure unless it is quantum."
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Factoring public keys attack?
Date: 4 Oct 1999 21:25:36 -0400
UBCHI2 <[EMAIL PROTECTED]> wrote:
> The point I'm making is also that you don't need to make a lookup table of all
> keys less than 512 bits. You only need to make a lookup table of keys that are
> exactly 512 bits. This is because everyone sets there key length to exactly
> 128, 512, 1024 or 2048. This creates a vulnerability.
If you have every atom being a large mass media storage system and have
many multi-verses for all the atoms in the universe could not hold them.
There are a LOT of primes <grin>! And even a LOT of primes of length 1024
bits!
(consider number of 512 bits ... ALL the numbers of fewer bits ... how
many of them are there? the same as the number of exactly 512 bits!
Asymptotically how many primes are there of exactly n bits?
Let a and b be close to 1 (make n large) and the number of primes of at
most n bits is a*2^(n+1)/((n+1)*ln2) and subtract out the number of at
most n-1 bits (b*2^n/(n*ln2)) to get asymptotically 2^n/ln(2^n) (instead
of 2^(n+1)/(ln(2^(n+1)). About half of all the primes of length no more
than 512 bits have exactly length 512 bits. So ... one only needs have the
gigantic number of universes to hold the data for those primes instead of
all the primes of under 512 bits (of course if someone decides to use 513
bits ... <grin>)...
There are a LOT of primes!
------------------------------
From: [EMAIL PROTECTED] (Johnny Bravo)
Crossposted-To: comp.lang.java.advocacy,comp.lang.java.security
Subject: Re: True Random numbers
Date: Mon, 04 Oct 1999 20:24:57 GMT
On Mon, 04 Oct 1999 14:47:39 -0700, Roedy Green <[EMAIL PROTECTED]> wrote:
>>How will you know if your DVD has been copied or not? How
>>will you know if the Feds break into your house and copy
>>it, or if they've bribed the courier, or...
>
>no different that a any other private key, just a bit more bulky.
It is different. You can exchange private keys without having a secure
channel available. With a OTP you need a secure channel beforehand. And is
unworkable for large groups. If you have 1000 people you need 1 million
different sets of data, and each user would have to keep 1000 one time pads
secure.
>With otps you don't put all your eggs in one basket.
You put just as much in the basket as you do with public key cryptography.
>If one DVD is compromised not all your data is exposed.
Just as much data as would fit on that DVD. For most users, this would be
more data than they will send to that one recipient in their lifetime.
> If you use a single private key, if it is compromised, all your communications are.
Only until you change your key. There is nothing preventing you from using a
separate public key for each message if you really feel the need for it.
Without the problem of sending that key to the recipient beforehand. One time
pads seem far inferior in this respect.
Johnny Bravo
------------------------------
** 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
******************************
