From: remailer@merde.dis.org (remailer bogus account)
Date: Mon, 7 Feb 94 01:30:32 PST
To: cypherpunks@toad.com
Subject: More on Magic Money attack
Message-ID: <9402070928.AA10499@merde.dis.org>
MIME-Version: 1.0
Content-Type: text/plain


-----BEGIN PGP SIGNED MESSAGE-----

(I sent that last message before receiving Hal's response)

hfinney@shell.portal.com wrote:

>I think it's great that you are able to fix these things so quickly.
>It's natural that there will be a lot of shaking out in any initial
>release.

But what does MPJ think of getting a 400K mailbomb? If you object, MPJ,
feel free to flame me and I'll stop sending them.

>>How many small primes would it take? How would he know what numbers to
>>multiply to get the coins? Just create random coins and look for one which
>>is made of all small factors? I should try this and see if I can find one.
>>Not being an expert in the math, would most coins have a large factor, or
>>would there be a fair number with only small factors?

>Knuth has some discussion of this in Seminumerical Algorithms.  The term
>for numbers which have only small factors is that they are "smooth".  He
>has some formulas for what fraction of numbers are smooth based on the
>size of the largest allowed prime and the size of the numbers.
>Unfortunately I won't have access to my copy until Tuesday.  Perhaps 
>someone else can look it up.

Someone please do. I can make the changes as needed tomorrow, if someone
posts the math results. I am anxious to play with a real live digicash
system, and transferring money between two directories on my hard drive
does not count.

>>The small-factor sieve is fast, and with the proper #defines, it checks 
>>all primes below 8192 decimal. The slowtest() PGP uses is slow even for
>>the 512-bit primes used to make 1024 bit PGP keys. It would be useless 
>>for a full 1024-bit number. Would eliminating coins with factors below 
>>8192 be enough? Or how could one more quickly check the coin for 
>>primality?

>The 8192 cutoff might work.  We would have to check it out, but it
>could be that finding 1024-bit numbers in a relatively narrow range of
>+/- 2^64 which are composed solely of factors in the range, say, 8192
>to 16384 would be infeasible.  I don't recall whether Knuth considers the
>problem in this form.  This would be a great save if it works.

Whoever has the Knuth book, please check this out. Maybe we should patent
this solution, if it works, and make Chaum pay us, since he patented his
blind signature protocol. :-)

                                                Pr0duct Cypher

-----BEGIN PGP SIGNATURE-----
Version: 2.3a

iQCVAgUBLVX0s8GoFIWXVYodAQG2TwP/Qa2Ql5JGu3aaYTvyfMLXeICCSQTWH2al
Mx4XxAEMgsh31JH18McVwltla6I33hndYfLyFwRKetPaNW5EKO/ypzZFPHIN6m5k
J9iiYDUk/FsKxScR//yjUTEsOu/3UQwczk3qRadJkNOBZQBo+qDpXewASJlVEewH
0oCWeXmqoZU=
=beCP
-----END PGP SIGNATURE-----