From: jkreznar@ininx.com (John E. Kreznar)
Date: Mon, 7 Feb 94 03:06:15 PST
To: cypherpunks@toad.com
Subject: Re: Magic Money attack
In-Reply-To: <199402070541.VAA25288@jobe.shell.portal.com>
Message-ID: <9402071101.AA08570@ininx>
MIME-Version: 1.0
Content-Type: text/plain


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

> >The idea would be for him to try to factor a legal Y using just the
> >primes he has.  If he can find a factorization using only small primes
> >of a number which holds the magic 18-byte sequence in the right place,
> >he can multiply together the signed forms of the primes to produce a
> >signed version of that number.  This would be a successfully forged coin.

> 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?

> >So, the question is whether it would be feasible to collect enough
> >signed small primes to be able to generate more valid coins than you
> >have primes.  (It costs you a coin each time you get the bank to sign
> >something, so for this to be a money-making venture you want to get
> >more out of it than you put into it!)  I think there are a reasonable
> >fraction of numbers factorable by only small primes.  Since there are
> >2^128 possible money values (based on the 16 random bytes) there
> >should be quite a lot which are factorable by only small primes.

> Any math whizzes out there care to run these numbers?

A useful and delightful reference on this subject (and many others) is
_Number Theory in Science and Communication_ by M.R.~Schroeder,
Springer-Verlag, 1984.

Let me quote the first few paragraphs of Chapter 11, ``The Prime Divisor
Functions''.  I use LaTeX coding.

	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!

	{\large\bf 11.1 The Number of Different Prime Divisors}

	In connection with encrypting messages by means of Euler's
	theorem, the number of distinct {\em prime\/} divisors of a given
	integer $n$, $\omega(n)$, is of prime importance.  Its
	definition is similar to that of the divisor function $d(n)$,
	except that the sum is extended --- as the name implies --- only
	over the prime divisors of $n$:

	$$ \omega(n) := \sum_{p_i \mid n} 1 . $$

	It is easily seen that $\omega(n)$ is additive, i.e., for $(n,m)
	= 1$,

	$$ \omega(nm) = \sum_{p_i \mid nm} 1
		      = \sum_{p_i \mid n} 1 + \sum_{p_i \mid m} 1
		      = \omega(n) + \omega(m) . $$

	Of particular interest to our encrypting desires will be the
	behavior of $\omega(n)$ for large $n$, i.e., its asymptotic
	behavior.  We shall try to get an idea of this behavior by means
	of our usual ``dirty tricks.''

...and so on.  It seems unlikely that this development would be useless in
answering the question at hand.  I don't have time now to study further.

	John E. Kreznar		| Relations among people to be by
	jkreznar@ininx.com	| mutual consent, or not at all.

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

iQCVAgUBLVYddsDhz44ugybJAQHpZAP/azfOzvVEkymO3rh/4HbTc537zuEajoW+
Kz+03iRenJh/Xe7906t9EmxqK9Bx2Zu28AbGonUfBSg39agrGfSyCqMltvapIbhw
m2MCf25UIn5q69WB6pbIA0/V77xNFx1YEm7CtTeuBO9vqrtYW7DirJKk29brAd4d
6FlX6+nbyd8=
=JuTg
-----END PGP SIGNATURE-----