From: qwerty-remailer@netcom.com
Date: Wed, 9 Feb 94 07:27:22 PST
To: cypherpunks@toad.com
Subject: Another PGP Tools / Magic Money update
Message-ID: <199402091526.HAA12975@mail.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


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

There should be a new version of PGP Tools and Magic Money on csn.org soon.
The PGP Tools will be called pgptl10b.zip and the Magic Money will be
mgmny10b.zip. The new naming was warlord's idea: the "b" will be "c" etc
in future releases, until some serious updating justifies a new version.
The new Magic Money does not contain the PGP Tools files, so be sure to
download PGP Tools as well. Will I run out of bugs or letters first? :-)

The prime-multiplication problem appears to have gone away. The new Magic
Money checks the whole coin, but the attack is probably impossible anyway.

jkreznar@ininx.com quotes:

   Here we consider only {\em prime\/} divisors of $n$ and ask, for
   given order of magnitude of $n$. ``how many prime divisors are
   there typically?'' and ``how many {\em different\/} ones are
   there?''  Some of the answers will be rather counterintuitive.
   Thus, a 50-digit number ($10^{21}$ times the age of our universe
   measured in picoseconds) has only about 5 different prime
   factors on average and --- even more surprisingly --- 50-digit
   numbers have typically fewer than 6 prime factors in all, even
   counting repeated occurrences of the same prime factor as
   separate factors.

   We will also learn something about the distribution of the
   number of prime factors and its implications for the important
   factoring problem.  Thus, we discover that even for numbers as
   large as $10^{50}$, the two smallest primes, 2 and 3, account
   for about 25\% of all prime factors!

A number of several hundred digits, such as a Magic Money coin, if it were
to be made of all small primes, would need 50 or 100 factors. These would
probably be very rare, considering this average.

hfinney@shell.portal.com wrote:

>I was thinking over the attack I described on Magic Money and Chaum
>cash, and I now think it will not actually work, especially in the case
>of the Chaum cash.  Specifically, it will take as much work to forge
>cash as to factor the modulus.

[ describes how finding smooth numbers is equivalent to factoring ]

>So, unless there is in fact some trick that can be used to quickly find
>smooth numbers given that the low order 128 bits are free, I don't
>think there is any need to worry about my attack on Magic Money.  And
>it looks like Chaum's online cash is completely invulnerable to this
>approach.

Unless something else comes up, it looks like we don't need to worry about
this one. If it does become a problem, it would be easy to go to full Chaum 
cash - take the MD5 of a random number and use it, including the random 
number in the coin. But there is no reason to code this unless we find out 
we need it.

As for the big-endian problem, andrewl@wtg20.wiltel.com wrote:

>I retrieved the latest version of Magic Money from the mpj archive
>and compiled it on a big-endian machine (a 68k NeXT).  It seems
>to work now...  I was able to setup the server and client and
>move a little cash around whereas before the server would never
>sucessfully find a q....

This was the last version, which set all precision to max. The last version
also had a bug in pgp_extract_rsa, again involving set_precision. The new 
one has defines which try to use lower precision and adjust pointers, for 
those functions which can be sped up this way. If that fails, another define 
will go back to setting everything max. Please test this on a big-endian 
machine and find out if it works without everything set to max. If it 
doesn't, please try to debug it and post what needs to be done.

The code seems to be getting close to working. Does anyone want to set up
a Magic Money server? You could run it through a remailer, if you want to.
The server filters PGP messages from stdin to stdout, so you would not
need root access to run one. It would probably be no harder than running 
a remailer. I compiled in the 8086.asm under DOS, and it is fast enough.
Use the assembly for whatever system you are running on, because the server
has to perform a lot of secret key operations: decrypt, sign message, and
sign each coin.

                                             Pr0duct Cypher

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

iQCVAgUBLVdKTsGoFIWXVYodAQFGAgQAgNs7PiGe3KItFiouUs/iXoH5bfVsgdGs
pVbf4sTZcF3c531KARJGxVkXsrTXH+VOU2QPi2zj3M/w06elCnov/KZYl/aSRerg
viLquHK8sUymEq9KB7swIO+Kthk5G8fke/h/3xq1i4S0n6klajtU8HuOR5FdmcAU
kfA05Czngzw=
=gleH
-----END PGP SIGNATURE-----