WRONG: Attack on Magic Money and Chaum cash

[Hal <hfinney@shell.portal.com>]

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.

My idea was to collect signed forms of small primes, then try to find a
"smooth" number of the proper form, one which can be factored over this
set of primes.  By multiplying together the proper primes, one could
generate a signed number which would look like cash.

What I was remembering as I was driving tonight is that this is very
similar to a family of algorithms for factoring large numbers.  The one
I know best is the continued fraction algorithm, but I think the number
field sieve uses broadly similar principles.  In the cfrac algorithm,
the goal is to find two squares which are equal mod n.  This lets you
factor n immediatly by taking its gcd with the sum or difference of the
two numbers.

This is done by taking a bunch of squares and trying to factor them
over a set of small primes.  If you generate enough factorizations,
approximately as many as there are primes, you can multiply selected
ones together and generate two equal squares.

The point is, finding as many smooth numbers as there are small primes
will let you factor n.  But that is the same criterion I had to meet in
my proposed attack in order to make a profit.  So it seems that in
general my attack will not work; it will be as hard as factoring the
modulus.

There may still be a problem with Magic Money because its cash values
leave the low order 128 bits free, but I'm not so sure about it.  I was
wrong, I think, to suggest that a simple sieve could quickly identify
smooth numbers.  Although a sieve will easily tell you that a number
has _no_ factors less than some cutoff, it will not easily tell you
that a number has _only_ factors in that range.  It may be that the
only way to identify smooth numbers is by trial division, which would
be the same situation as for Chaum cash.

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.

Sorry to have raised a red flag unnecessarily.

Hal