Cryptography-Digest Digest #637, Volume #13 Tue, 6 Feb 01 00:13:00 EST
Contents:
efficient coin flipping ([EMAIL PROTECTED])
Re: ith bit of an LFSR sequence? (David Wagner)
Re: Phillipine math guy claims to have fast RSA Factoring... (Bill Unruh)
Re: ith bit of an LFSR sequence? ("bubba")
Re: Phillipine math guy claims to have fast RSA Factoring... (Tom St Denis)
Re: RSA, discrete log Both not secure... (Tom St Denis)
Re: Phillipine math guy claims to have fast RSA Factoring... (Tom St Denis)
Re: RSA, discrete log Both not secure... (Bill Unruh)
Re: RSA, discrete log Both not secure... ("Marcin")
Re: MIKE - alternative to SPEKE and PAK (Thomas Wu)
Re: Pseudo Random Number Generator (Charles Lyttle)
Re: DH question ("Scott Fluhrer")
Re: ith bit of an LFSR sequence? ("Matt Timmermans")
Re: ith bit of an LFSR sequence? (Paul Rubin)
Microsoft's (Failed) Product Activation (Splaat23)
on the RSA "crack" (Dido Sevilla)
Re: [RSA] Hype, hoax, or ? (Dido Sevilla)
Re: efficient coin flipping ("Joseph Ashwood")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: efficient coin flipping
Date: Tue, 06 Feb 2001 01:59:47 GMT
The population at large agrees that flipping a coin is a good way to
make a random binary decision. But it's slow.
A faster method is to drop lots of coins, line them up horizontally, and
read them left to right. The only reason to do such a thing is if you
need to say "I made 2000 coin flips and ...".
- Bob Jenkins
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: ith bit of an LFSR sequence?
Date: 6 Feb 2001 02:25:58 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Rob Warnock wrote:
>David Wagner <[EMAIL PROTECTED]> wrote:
>| [...] the i-th successor of a state s is x^i * s mod p(x), [...]
>
>But you can, of course, use the usual square-and-multiply techniques
>on the powers of the matrix M, too.
Of course. But multiplying two nxn matrices requires O(n^3) bits
operations, whereas multiplying two elements of GF(2^n) requires
O(n^2) bit ops. That's why I predicted that the polynomial method
may be faster than the matrix method. Did I overlook something?
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Phillipine math guy claims to have fast RSA Factoring...
Date: 6 Feb 2001 02:59:09 GMT
In <[EMAIL PROTECTED]> [EMAIL PROTECTED] (Padgett 0sirius)
writes:
>Guess I have two questions now that have had a chance to think about it a
>bit more:
>a) doesn't 1 mod <any positive integer greater than 1> = 1 ?
Yes.
> this makes x=0 the only value for 2^x= 1 mod N
No.
Mod is a many to one function. Ie there are many solutions ( infinitley
many) to the equation a mod N=1
------------------------------
From: "bubba" <[EMAIL PROTECTED]>
Subject: Re: ith bit of an LFSR sequence?
Date: Tue, 06 Feb 2001 02:59:55 GMT
Hi David,
I bet you are the same David Wagner mentioned on the front page
of today's Wall Street Journal. The artical was addressing security
concerns of wireless networks.
Here is some C code that advances an LFSR as part of a primitive
polynomial search. It is plain square and multiple, but is ugly because
of optimization. I have a portable version I hope to one day cleanup
and post.
http://sduplichan.home.att.net/primitive/primitivePolynomials.htm
"David Wagner" <[EMAIL PROTECTED]> wrote in message
news:95ljkt$2fg$[EMAIL PROTECTED]...
> >Given i in 0..2^^n-2, what's the most efficient way to generate the LFSR
> >sequence starting at the ith bit? (The best I can come up with offhand
> >is the standard way of producing large exponents, that is, multiplying n
> >nxn bit matrices together. Is there a better way?)
>
> Here's one that's probably more efficient. Let p(x) be the feedback
> polynomial. Note that states can be identified with elements of
> GF(2)[x]/(p(x)), and that state update is multiplication by x. Thus,
> the i-th successor of a state s is x^i * s mod p(x), and x^i mod p(x)
> can be computed efficiently using square-and-multiply techniques in a
> possibly more efficient way than computing M^i for some matrix M.
>
> >Given x in 1..2^^n-1, what's the most efficient way to find i such that
> >x is the ith to i+n-1th bits of an LFSR's sequence?
>
> This is precisely as hard as the discrete log problem in F^*, where
> F = GF(2)[x]/(p(x)); it is no harder, and no easier. The best algorithm
> I know of for computing discrete logs over finite fields of characteristic
> 2 is due to Don Coppersmith. It is somewhat faster than corresponding
> algorithms for computing discrete logs over (Z/pZ)^*, but still
> super-polynomial.
>
> For n=32 or 64, Coppersmith's algorithm should be very efficient, but
> it is probably also overkill. A square-root algorithm (e.g., lambda
> method, kangeroo-catching, etc.) that ignores the structure of the
> field will be much simpler, and probably will suffice as long as you
> don't need to do this too frequently.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Phillipine math guy claims to have fast RSA Factoring...
Date: Tue, 06 Feb 2001 02:49:03 GMT
In article <tvCf6.56506$[EMAIL PROTECTED]>,
"arcmight" <[EMAIL PROTECTED]> wrote:
> "To do this, one approach that I claim as also mine is to multiple N with a
> number Y. Such that N * Y will give a binary product with all bit one," De
> Velez said.
>
> Example: N = 55, its binary representation is 110111 If we multiply N by Y =
> 19065, the product will be equal to 11111111111111111111 (20 digits).
>
> To find Y = 19065, we just add 110111 to itself many times but shifting the
> binary number to the left so that we always add 1 to the zero to make it 1.
But we don't know 110111 (19065) since it's an unknown factor.
Uh oh your idea doesn't work.
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: RSA, discrete log Both not secure...
Date: Tue, 06 Feb 2001 02:49:33 GMT
In article <95nemd$qrj$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Are there any public-key cryptosystem left?
>
> What's gonna happen to ecommerce? Game over?
>
> I see how discrete log is completely insecure. Will elliptic curve
> suffer in similar ways?
>
> PS. The philippino's alg works. I tried it myself. I guess he's probably
> not the first one breaking RSA. The previous ones just aren't exposed.
> Look how his algorithm is not reported worldwide :)
PS the scheme doesn't work since it assumes you already know a factor.
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Phillipine math guy claims to have fast RSA Factoring...
Date: Tue, 06 Feb 2001 02:51:51 GMT
In article <95nomt$3g8$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> In article <tvCf6.56506$[EMAIL PROTECTED]>,
> "arcmight" <[EMAIL PROTECTED]> wrote:
> > "To do this, one approach that I claim as also mine is to multiple N with a
> > number Y. Such that N * Y will give a binary product with all bit one," De
> > Velez said.
> >
> > Example: N = 55, its binary representation is 110111 If we multiply N by Y =
> > 19065, the product will be equal to 11111111111111111111 (20 digits).
> >
> > To find Y = 19065, we just add 110111 to itself many times but shifting the
> > binary number to the left so that we always add 1 to the zero to make it 1.
>
> But we don't know 110111 (19065) since it's an unknown factor.
>
> Uh oh your idea doesn't work.
Oops I messed up. Disregard my post.
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: RSA, discrete log Both not secure...
Date: 6 Feb 2001 03:10:45 GMT
In <95nkdj$iag$[EMAIL PROTECTED]> "Carpe Diem" <[EMAIL PROTECTED]> writes:
>Well, you can factor an integer in polynomial time and I do not think this
>made RSA less secure.
Maybe he can.Noone else can. The best algorithms are far from polynomial
time.
------------------------------
From: "Marcin" <[EMAIL PROTECTED]>
Subject: Re: RSA, discrete log Both not secure...
Date: Tue, 06 Feb 2001 03:38:22 GMT
Please stop this madness! If anyone wants a practical example just how
inefficient this NEW algorithm is with the 2^X=1 (mod N) calculation to find
X or Y, you can check out a sample java code at:
http://www.optymalni.com/~marcin/
"Joseph Ashwood" <[EMAIL PROTECTED]> wrote in message
news:OT5A3D#jAHA.280@cpmsnbbsa07...
> <[EMAIL PROTECTED]> wrote in message
news:95njd1$v0a$[EMAIL PROTECTED]...
> > What I really want to know is whether elliptic curve will be affected.
> >
> > And how badly ecommerce will be affected.
> Please see comments by Paul Crowley and Bob Silverman in this NG, you will
> see that it not only does not affect ECC, it does not effect RSA or DH
> except to add another miserably failed attempt at breaking any of the
> aforementioned.
> Joe
>
>
------------------------------
From: Thomas Wu <[EMAIL PROTECTED]>
Subject: Re: MIKE - alternative to SPEKE and PAK
Date: 05 Feb 2001 19:37:38 -0800
"Michael Scott" <[EMAIL PROTECTED]> writes:
>
> Quite right. That was dumb of me. Which leaves me with either.....
>
> 3. Carol: A=3^a mod p, w=4^c mod p, a and c random. Sends {A,w} to Steve
> 4. Steve: B=3^b.v^r mod p. u=4^r mod p, b and r random. F=H(w^r). Sends
> {B,u,F} to Carol
> 5. Carol: Check F=?=H(u^c). If not abort, else S=(B/u^x)^a. Steve calculates
> S=A^b
>
> The idea is the same, to force Steve to make u=4^something by engaging in a
> base-4 Diffie-Hellman. Only if it he does will Carol continue.
>
> ..... or the somewhat faster alternative, as previously posted but tidied up
> a little, which includes the result of the base-4 DH in the key.
>
> 3. Carol: A=3^a mod p, w=4^c mod p, a and c random. Sends {A,w} to Steve
> 4. Steve: B=3^b.v^r mod p. u=4^r mod p, b and r random. Send {B,u} to Carol.
> 5. Carol: S=B^a.u^(c-ax) mod p. Steve calulates S=A^b.w^r
An impostor Chris has stolen Carol's v from Steve (v=4^x) and now wishes
to impersonate Carol.
3'. Chris: A'=3, w'=4.v mod p. Sends {A',w'} to Steve.
4'. Steve: B=3^b.v^r mod p, u=4^r mod p, b and r random. Sends {B,u} to Carol.
5'. Chris calculates S = B.u = 3^b.v^r.4^r
Steve calculates S = A'^b.w'^r = 3^b.(4.v)^r = 3^b.4^r.v^r
This protocol can be broken by an adversary who steals v, and does not
require a dictionary attack, since the client can log in without knowing
the real password x. This attack generalizes easily, so it cannot be
prevented by checking A and w for these specific values. Oddly enough,
Chris's attack is actually more efficient than a normal protocol run(!)
Frankly, I'm not sure grafting on extensions this way is the best way
to design a secure verifier-based protocol, because it's just too easy
to break something in the process of patching something elsewhere,
given what's happened with these last few proposals.
> Mike Scott
Tom
--
Tom Wu * finger -l [EMAIL PROTECTED] for PGP key *
E-mail: [EMAIL PROTECTED] "Those who would give up their freedoms in
Phone: (650) 723-1565 exchange for security deserve neither."
http://www-cs-students.stanford.edu/~tjw/ http://srp.stanford.edu/srp/
------------------------------
From: Charles Lyttle <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: Pseudo Random Number Generator
Date: Tue, 06 Feb 2001 04:00:05 GMT
Damian Kneale wrote:
>
> Once Charles Lyttle <[EMAIL PROTECTED]> inscribed in stone:
>
> >Great. Recall why I posted this DVD idea in the first place : To get it
> >into the public domain so someone can't patent it and include it in some
> >snakeoil product. And it does seems as much fun as the "lava lamp" PRN
> >generator posted a while back:)
>
> One problem with that plan, for at least some countries. A patent on
> the idea would allow you to control the implementation, but copyright
> only applies for an original work, not just an idea. You have to have
> a product or some original work towards your encryption engine to
> allow this to have much validity.
>
> To get around copyright currently, you have to prove someone copied
> your (non-existant) encryption engine. I can happily claim a
> different implementation of the same idea and be safe under law. Of
> course, being in Australia some US court decisions appear "odd" to us,
> so perhaps you might have a chance after all!
>
> I quite like steganography myself, which combined with encryption of
> the message to be hidden could be fun, if bandwidth intensive.
>
> Damian.
Not much we can do about copyright. But a patent is stronger, although
for a limited time. Copyright doesn't carry the same advertising weight
as a patent. Steganography is a good means of transmitting messages,
until the bad guys know you are sending hidden messages.
--
Russ Lyttle
[EMAIL PROTECTED]
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: DH question
Date: Mon, 5 Feb 2001 20:00:24 -0800
DJohn37050 <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> needs to be an abelian group to do DH as normally concieved.
Errr, why? The subgroup generated by a single generator is always abelian,
as:
g**x * g**y = g**(x+y) = g**y * g**x
--
poncho
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: ith bit of an LFSR sequence?
Date: Tue, 06 Feb 2001 04:09:38 GMT
Do you need to do it fast? This is a discrete log, but your problem sizes
are small enough to be tractable. Using Pollard's rho method on a fast PC,
you can do it for n=32 in the blink of an eye, and n=64 in a few hours.
<[EMAIL PROTECTED]> wrote in message
news:95lha2$3vd$[EMAIL PROTECTED]...
> Given x in 1..2^^n-1, what's the most efficient way to find i such that
> x is the ith to i+n-1th bits of an LFSR's sequence? (This seems an
> example of the discrete log problem, which is roughly as hard as
> factoring. But maybe there are special tricks for LFSRs.)
>
> I'm specifically interested in n=32 and n=64, that is, hardware words.
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: ith bit of an LFSR sequence?
Date: 05 Feb 2001 20:20:50 -0800
[EMAIL PROTECTED] writes:
> Given i in 0..2^^n-2, what's the most efficient way to generate the LFSR
> sequence starting at the ith bit? (The best I can come up with offhand
> is the standard way of producing large exponents, that is, multiplying n
> nxn bit matrices together. Is there a better way?)
>
> Given x in 1..2^^n-1, what's the most efficient way to find i such that
> x is the ith to i+n-1th bits of an LFSR's sequence? (This seems an
> example of the discrete log problem, which is roughly as hard as
> factoring. But maybe there are special tricks for LFSRs.)
The answers to these questions are well known in the literature. Look
in the index to Applied Cryptography for LFSR's, then check the
references in the bibliography, for example. And to answer your
question, solving an LFSR is *not* as hard as factoring. That's why
LFSR keystreams are not secure. This stuff goes back for decades.
------------------------------
From: Splaat23 <[EMAIL PROTECTED]>
Subject: Microsoft's (Failed) Product Activation
Date: Tue, 06 Feb 2001 04:26:03 GMT
This is more along the lines of an FYI than a topic of discussion, but
since its relevant to recent discussions I thought I would relay it to
you all. It seems that a recent beta of Microsoft's Windows XP (new
name, yuck!) was released, followed the next day by two different
cracks that completely remove the product activation/hardware generated
key antipiracy software.
In my opinion, this just proves that trying to hide or restrict access
to information from the user of that computer is futile, and thus any
antipiracy schemes that rely on this will fail miserably, especially
when the software that utilizes it is widespread (benefits of cracking
the system are greater).
In any case, any input on this involvement. Maybe the real topic here
is what can we do to stop this foolishness and wasted time and money by
companies like Microsoft? Some famous cryptographers could publicly
refute the value of these schemes, but I'm not sure that's enough to
derail a company like Microsoft. In the end, if they are not stopped,
it will just lead to hassle after hassle for customers that, for
reasons outside of their control, need/want Microsoft software.
- Andrew
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Dido Sevilla <[EMAIL PROTECTED]>
Subject: on the RSA "crack"
Date: Tue, 06 Feb 2001 12:32:30 +0800
http://www.seedmuse.com/rsa_edit.htm
Apparently my esteemed countryman Mr. de Velez was able to find a way to
crack small RSA numbers, and had spoken to the press and told them to
hold on to the story until after he had finished his correspondence with
Ron Rivest. Well, somebody got keyboard happy and wrote up the story
without waiting as he was asked to do...
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
ICSM-F Development Team, UP Diliman +63 (917) 4458925
OpenPGP Key ID: 0x0E8CE481
------------------------------
From: Dido Sevilla <[EMAIL PROTECTED]>
Subject: Re: [RSA] Hype, hoax, or ?
Date: Tue, 06 Feb 2001 12:34:44 +0800
Paul Crowley wrote:
>
> Mistake; it turns out, unsurprisingly, that the technique isn't
> practical. He mailed his technique directly to Ron Rivest, who was
> kind enough to give a detailed and clear explanation of the maths
> behind RSA and the reasons why the technique won't work.
>
> The explanation appeared on the "cryptography" mailing list; I can't
> find a URL for archives just now.
http://www.seedmuse.com/rsa_edit.htm
Transcript of the correspondence between de Velez and Rivest.
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
ICSM-F Development Team, UP Diliman +63 (917) 4458925
OpenPGP Key ID: 0x0E8CE481
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: efficient coin flipping
Date: Mon, 5 Feb 2001 20:31:58 -0800
<[EMAIL PROTECTED]> wrote in message
news:95nlqf$11u$[EMAIL PROTECTED]...
[drop a bag of coins]
I'm not sure that'd have the desired result. There wouldn't be an influx of
energy, just a release of energy already stored. Now if you were to take
that same bag (I assume you'd have them in a bag), and launch the mass of
change using a catapult-type device against a wall, or preferably in the
open, that could create the influx of energy necessary, but I'd still test
it a lot first. While we're making changes why not instead make coins where
one side was white, the other black, make the floor green, and use digital
video technology to detect the white and black spots for the ones and zeros.
You could use a conveyor belt to then drag them all to one side of the room
to feed them back in to be launched again. Of course this would be a massive
undertaking, but it would be faster than flipping a coin manually, and a lot
more convenient. However I think my neighbors would complain about the
noise.
Joe
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
