 # cryptoanarchy.wiki

Arise, you have nothing to lose but your barbed wire fences!

# 1994-02-07 - Re: Magic Money attack

From: jkreznar@ininx.com (John E. Kreznar)
Message Hash: f3f70e355758f0deb6484d5024784fb59aa81aa35f62274c9eb41ba9d564c848
Message ID: <9402071101.AA08570@ininx>
UTC Datetime: 1994-02-07 11:06:15 UTC
Raw Date: Mon, 7 Feb 94 03:06:15 PST

## Raw message

From: jkreznar@ininx.com (John E. Kreznar)
Date: Mon, 7 Feb 94 03:06:15 PST
Subject: Re: Magic Money attack
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