Cryptography-Digest Digest #326, Volume #10 Tue, 28 Sep 99 20:13:03 EDT
Contents:
Re: books on discrete logarithm problem (Jerry Coffin)
Re: RSA weak? yes! (Ben Lambregts)
Re: Hardest ever ECDL solved by INRIA researcher and 195 volunteers ("Douglas A.
Gwyn")
Re: Perfect Shuffle Algorithm? ("karl malbrain")
Re: Increasing password security dramatically without making it harder to remember
("Gary")
Re: ECC97 Challenge Solved (DJohn37050)
Re: Hardest ever ECDL solved by INRIA researcher and 195 volunteers (DJohn37050)
Re: Schrodinger's Cat and *really* good compression (Lamont Granquist)
Re: Schrodinger's Cat and *really* good compression (Lamont Granquist)
Re: RSA weak? yes! ("Steven Alexander")
Re: books on discrete logarithm problem ("Steven Alexander")
Re: arguement against randomness ("karl malbrain")
Re: Electronic envelopes (Mok-Kong Shen)
Re: Electronic envelopes (Mok-Kong Shen)
Re: books on discrete logarithm problem (JPeschel)
Re: Please review proposed rebuttal... (Bill Unruh)
Re: RSA weak? yes! (Jerry Coffin)
Re: review of peekboo please? (jerome)
Re: Electronic envelopes ("Richard Parker")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: books on discrete logarithm problem
Date: Tue, 28 Sep 1999 15:20:45 -0600
In article <7sr5ik$m26$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
> Are there any books (under 50 us dollars) still in print (preferably recent)
> that cover the discrete logarithm problem? I want something that includes
[information on discrete logarithms in cryptography and cryptanalysis]
Have you read through chapter three of "Handbook of Applied
Cryptography" ? That would be an obvious place to start, especially
since it's available online for free.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: Ben Lambregts <[EMAIL PROTECTED]>
Subject: Re: RSA weak? yes!
Date: Tue, 28 Sep 1999 23:35:12 +0200
RSA weak?
It seems so.
See:
http://www.andovernews.com/cgi-bin/news_story.pl?48052/topstories
---------
http://www.benlambregts.com
The truth is out there. Anyone knows the URL?
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Hardest ever ECDL solved by INRIA researcher and 195 volunteers
Date: Tue, 28 Sep 1999 17:41:29 GMT
The strange thing is that the press release claims that this
shows that cracking a 97-bit EC system is harder than cracking
a 512-bit RSA system. Unless there is some breakthrough
theorem I haven't yet heard of (please enlighten me if so),
what was shown is that the *particular methods of attack*
being compared obey that relationship, not that the EC
problem intrinsically *requires* a higher work factor.
------------------------------
Reply-To: "karl malbrain" <[EMAIL PROTECTED]>
From: "karl malbrain" <[EMAIL PROTECTED]>
Crossposted-To: sci.stat.math,sci.math
Subject: Re: Perfect Shuffle Algorithm?
Date: Tue, 28 Sep 1999 14:54:37 -0700
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Dr D F Holt wrote:
> > The easiest approach, which would certainly solve the problem fast, is
> > to program the case of finding the order of an arbitrary permutation of
the
> > set {1,2,3,...,n} (in your case n=1001). Just write the permutation in
> > cycles, and then the order is the least common multiple of the cycle
> > lengths.
>
> Yes, that is workable; nice answer! So the program sought would
> simulate the shuffle only once, to build the permutation (not
> hard), then would decompose the perm. into cycles (not hard),
> then find the LCM of the cycle lengths (not hard). Perhaps the
> interviewer's purpose was to probe the applicant's experience in
> working with things very like this. In which case, turning to
> the net means he has not met the criteria.
If you look back to the history of PUBLISHING circa 1500, you'll find
TRAVELLING JOURNEYMEN offering to reproduce all sorts of things from the
back of their wagons -- in other words, taking inspiration from the NET is
no barrier to PARTICIPATION.
The criteria is set by REMOVING THE RANDOMNESS FROM THE PROOF COPY. Come on
guys, this isn't all that hard, is it??? Karl M
------------------------------
From: "Gary" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,comp.security.pgp
Subject: Re: Increasing password security dramatically without making it harder to
remember
Date: Tue, 28 Sep 1999 22:58:43 +0100
Johnny Bravo wrote in message <[EMAIL PROTECTED]>...
>On Tue, 28 Sep 1999 14:08:51 +0100, "Gary" <[EMAIL PROTECTED]> wrote:
> That's assuming that the attacker is only using one computer as slow as
yours.
Yes you're right. This method is open to parallel attack.
However in <http://www.counterpane.com/low-entropy.html> kindly linked by
David Wagner in this thread, a solution is outlined.
For everyday passwords this does deter your average resourced/funded
attacker.
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: ECC97 Challenge Solved
Date: 28 Sep 1999 21:55:52 GMT
Lots on info on ECC, RSA, and DL crypto at IEEE P1363 web site.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Hardest ever ECDL solved by INRIA researcher and 195 volunteers
Date: 28 Sep 1999 21:53:38 GMT
The known best method to attack a 512-bit RSA key took less total work than the
known best method to attack a 97-bit ECC key. And the ECC attack was lucky.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (Lamont Granquist)
Subject: Re: Schrodinger's Cat and *really* good compression
Date: 28 Sep 1999 22:04:52 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> writes:
>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.
The twin paradox is very easy to understand if you can understand
non-Euclidean geometry. It isn't a paradox. However, I doubt anybody out
there really understands the Schroedinger's cat problem, although
some people claim to.
--
Lamont Granquist ([EMAIL PROTECTED])
ICBM: 47 39'23"N 122 18'19"W
------------------------------
From: [EMAIL PROTECTED] (Lamont Granquist)
Subject: Re: Schrodinger's Cat and *really* good compression
Date: 28 Sep 1999 22:00:42 GMT
"Douglas A. Gwyn" <[EMAIL PROTECTED]> writes:
>John Savard wrote:
>> Actually, however, the box has to be *very* well-insulated in order
>> for the cat not to be inadvertently observed.
>
>Well, actually that just spreads the superposition to a wider system
>(according to the theory of measurement that is being questioned).
>
>> In fact, since a cat is big enough to have a detectable gravitational
>> pull, and no insulator for gravity is known - after all, it bends the
>> fabric of space itself - and so there may be a *fundamental*
>> impssibility involved; at least this is what Roger Penrose has
>> suggested.
>
>Gravity works even at the microlevel, but its effects are usually
>dwarfed by the e-m and strong forces. So it doesn't seem to have
>anything to do with the actual issue; it's another case of "I don't
>know whether it is relevant or not, so it might explain something".
Yet another case of "I didn't bother to (or couldn't) understand his point,
so I'll just dismiss it."
>Remeber, Penrose was taken in by Searle's "Chinese box" argument.
No he wasn't. Penrose didn't use that argument at all.
>He's undoubtedly a very smart person in his own field, but like
>many, he doesn't seem nearly as smart when dabbling in another field.
Much in the same way that you're dabbling in quantum gravity and
consciousness theories?
--
Lamont Granquist ([EMAIL PROTECTED])
ICBM: 47 39'23"N 122 18'19"W
------------------------------
From: "Steven Alexander" <[EMAIL PROTECTED]>
Subject: Re: RSA weak? yes!
Date: Tue, 28 Sep 1999 15:10:33 -0700
Try to understand something before you begin speculating, eh? 512-bits is
the weakest key size that I've seen implemented. As of 1995, the size that
I heard recommended was 768-bits. Factoring(breaking) a 4096-bit RSA key is
still way(way, way, way) beyond computational ability using any known
factoring algorithm(I can't speculate on government agencies).
-steven
Ben Lambregts <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> RSA weak?
> It seems so.
>
> See:
> http://www.andovernews.com/cgi-bin/news_story.pl?48052/topstories
>
> ---------
>
>
> http://www.benlambregts.com
> The truth is out there. Anyone knows the URL?
------------------------------
From: "Steven Alexander" <[EMAIL PROTECTED]>
Subject: Re: books on discrete logarithm problem
Date: Tue, 28 Sep 1999 15:13:12 -0700
> Have you read through chapter three of "Handbook of Applied
> Cryptography" ? That would be an obvious place to start, especially
> since it's available online for free.
Now that it is completely free, I have to wonder what I payed $70+ US for.
-steven
------------------------------
Reply-To: "karl malbrain" <[EMAIL PROTECTED]>
From: "karl malbrain" <[EMAIL PROTECTED]>
Subject: Re: arguement against randomness
Date: Tue, 28 Sep 1999 15:39:23 -0700
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tim Tyler wrote:
> > elarson <[EMAIL PROTECTED]> wrote:
> > : It doesn't take a pompous genuis to see the randomness of Nature.
> > If the universe is deterministic, all this is dead wrong.
>
> No, randomness and determinism are not exact opposites.
PRECISELY: Randomness is an OBJECTIVE measure of ENTROPY (after the fact),
while Determinism a SUBJECTIVE measure of capability (before the fact).
Both measure PROOF COPY. Karl M
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Electronic envelopes
Date: Tue, 28 Sep 1999 22:16:15 +0200
Richard Parker wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > Would you please say whether this means it can be ensured that the
> > message can be decrypted exactly at time point T and not before T and
> > this is entirely independent of computing resources available?
>
> Hmmm. Well, the Crescenzo/Ostrovsky/Rajagopalan time-release protocol
> allows time to be specified with whatever granularity is required.
> The message can be decrypted by the receiver if and only if the time
> is not earlier than the release-time T. Note that technically the
> method I proposed also allows time to be specified with arbitrary
> granularity, but the COR time-release protocol is much more practical
> if you want to specify the release-time with a fine granularity.
I understand this to mean that it is indeed possible to decrypt
the message exactly at time point T, say to the accuracy of
one second, and nobody can do that before T. Am I right?
>
> As to being "entirely independent of computing resources available"
> the answer is no. However, the requirements are modest. The paper
> provides the following estimates for the interaction between the time
> server and the message receiver:
>
> n - size of public key
> k - number of bits to encode time
> t - soundness parameter for the non-interactive zero-knowledge proof
>
> computational complexity: 8nk modular products
> communication complexity: 12nk + n log t
> storage complexity: 6n + n log t
>
> Also, I should note that the security of the protocol relies on
> public-key encryption and the hardness of deciding quadratic
> residuosity modulo Blum integers.
Granted that the assumptions of public-key encrption and quadratic
residues are correct, does it matter if someone employs 1000 times
the computing resources that he is normally assumed to possess?
In other words, can the amount of resources employed somehow be
audited (proved)? Could the vulnerability of the (presumably
continued) connection between the time server and the client be
an issue? I should be very grateful if you would like to give the
answers, for the solution of my problem would pretty much depend
on them.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Electronic envelopes
Date: Tue, 28 Sep 1999 22:16:26 +0200
Johnny Bravo wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> >> >In other words, one deposits an envelope containing
> >> >secrets at a notary who opens it at a certain time point and
> >> >announces the contents. The envelope is to be opened exactly at
> >> >that time point and not before. No trust on the notary is assumed.
> >>
> >> Then you can't even be sure your envelope will even be opened.
The depositor can, for example, publically annouce that an envelope
has been deposited at the notary to be opened at such and such a date.
The notary is thus sort of forced to do that job properly.
> >In the case of normal envelopes I suppose that there are ways of
> >sealing that are traditionally considered to be adequate against
> >frauds and there are specialists who can examine that. I don't know
> >what the actual probability of frauds is, but it seems that people
> >accept (believe) that degree of security (compare signatures on
> >cheques).
>
> I was just responding to your comment about not trusting the notary.
> Given this, you can't even trust they will open the envelope or even
> bother reading the message. :)
See above.
> >The signals that synchronize, for example, your alarm clock.
>
> The only signal that synchronizes my alarm clock is the current flowing
> through my brain. I have to set my own alarm clocks manually, and set them
> again
> every time the power goes out. :)
Sorry, I was assuming that you are using a radio-synchronized
alarm clock which can be bought nowadays very cheaply at department
stores and which eliminates any need of adjustment. (I am also in
possession of a nice and well functioning Baby-Ben of the fifties
but I am not using it currently.)
> But now you aren't talking about an electronic envelope but a physical one.
> This violates the first requirement you listed at the beginning of your request.
Do you mean 'the conventional envelope' I mentioned above? I was
contrasting the case of a conventional (physical) envelope with
an electronic envelope in respect of possiblities of detecting
frauds. Did this argumentation disturb you?
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: books on discrete logarithm problem
Date: 28 Sep 1999 22:41:29 GMT
"Steven Alexander" <[EMAIL PROTECTED]> writes:
>Now that it is completely free, I have to wonder what I payed $70+ US for.
A good paper edition that is easier to read.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Please review proposed rebuttal...
Date: 28 Sep 1999 22:41:47 GMT
In <7sqv7v$h05$[EMAIL PROTECTED]> Bob Silverman <[EMAIL PROTECTED]> writes:
>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)
Probably, but I also wonder how well it would work on a "supercluser"
Ie, Cray class machines are now, for certain problems at least much much
cheaper than 5-10M. ( ie a few hundred thousand will buy you a pretty
powerful Beowulf cluster.)
>(b) consider it a 'modest' resource?
Rental of time on such a system is a modest resource, since the amount
of time needed is much less that the depreciation time of such a
machine.
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: RSA weak? yes!
Date: Tue, 28 Sep 1999 16:45:06 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
> RSA weak?
> It seems so.
>
> See:
> http://www.andovernews.com/cgi-bin/news_story.pl?48052/topstories
Yes and no. Given that another 512-bit number was recently factored,
this isn't showing a lot that's really particularly new or exciting.
To some extent it might show that the other 512-bit factoring job
wasn't more or less an accident -- it's clearly a repeatable operation
for just about anybody who has the requisite computing power
available.
OTOH, at least in this press release, there's no mention of a large
machine to solve the final matrix, as is normally needed when using a
GNFS. Chances are this is simply an oversight in the article, but if
they've found a way of factoring numbers of this size without such a
resource, it really DOES mean something. OTOH, does little more than
provide a (mostly unnecessary) confirmation of something we already
knew -- that a 512-bit key is no longer adequate with RSA.
In particular, this really doesn't mean a thing about the security of
RSA in general, only about the key size needed to make RSA secure. If
there's a reasonable method of factoring (say) a 1024 bit RSA key, I'm
reasonably certain it's not publicly known.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: [EMAIL PROTECTED] (jerome)
Subject: Re: review of peekboo please?
Reply-To: [EMAIL PROTECTED]
Date: Tue, 28 Sep 1999 23:03:12 GMT
On Tue, 28 Sep 1999 15:21:28 -0700, Steven Alexander wrote:
>I noticed that PGP-Net takes a long time to generate key pairs as well(4096
>bits). However, my I originally used PGP 2.6.2 I could generate keys very
>quickly(2048-bits)(100mhz Pentium). How does the difficulty of generating a
>key pair scale with size? Should it take twice as long to generate a
>4096-bit key as a 2048-bit key or should it be based off some other
>approximation for time.
if i remember correctly, it is in O(n^4).
so if im not wrong, it should be 16 times larger.
im not remember where i saw that... maybe in pgp doc
------------------------------
From: "Richard Parker" <[EMAIL PROTECTED]>
Subject: Re: Electronic envelopes
Date: Tue, 28 Sep 1999 23:12:31 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> I understand this to mean that it is indeed possible to decrypt
> the message exactly at time point T, say to the accuracy of
> one second, and nobody can do that before T. Am I right?
Yes, it is entirely possible to construct a practical implementation
of the Crescenzo/Ostrovsky/Rajagopalan protocol with a time
granularity of one second.
> Granted that the assumptions of public-key encrption and quadratic
> residues are correct, does it matter if someone employs 1000 times
> the computing resources that he is normally assumed to possess?
No, given those assumptions. If you know the computing resources of
your adversary and the duration that the message must remain secret,
you can choose a public key size and a ZNP soundness parameter large
enough that the protocol will remain secure against that adversary
with any desired probability.
In actual practice the selection of these parameters would involve
making the same sorts of educated guesses and assumptions that are
involved in selecting a key size for a block cipher.
> In other words, can the amount of resources employed somehow be
> audited (proved)?
I'm afraid I don't really understand this question.
> Could the vulnerability of the (presumably continued) connection
> between the time server and the client be an issue?
The protocol does not require a persistent connection between the time
server and the message receiver. The receiver need only communicate
with the time server on or after the release-time.
-Richard
------------------------------
** 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
******************************
