On Tue, Dec 08, 1998 at 12:07:59AM -0600, Russ Perry Jr wrote:
> It strikes me that these primes should be known quantities, as once discovered,
> you wouldn't necessarily want to waste time to find them again, so there MUST
> be a list of all known primes somewhere -- I mean, the Guinness Book of World
> Records has a record for highest known prime number, correct?
I'm afraid that as "armchair cryptographers" we all might have some naive
notions about the problem at hand. I'll take some quotes from Bruce
Schneier's well-known _Applied Cryptography_ (second edition, page 258)
which, among other things, discusses public key cryptography and its need
for prime numbers. He writes:
"1. If everyone needs a different prime number, won't we run out?
No. In fact, there are approximately 10^151 primes 512 bits in length or
less. For numbers near n [with n being a large integer], the probability
that a random number is prime is approximately one in ln n. So the total
number of primes less than n is n/ln(n). There are only 10^77 atoms in
the universe. If every atom in the universe needed a billion new primes
every microsecond from the beginning of time until now, you would only
need 10^109 primes; there would still be approximately 10^151 primes left.
2. What if two people accidentally pick the same prime number?
It won't happen. With over 10^151 prime numbers to choose from, the odds
of that happening are significantly less than the odds of your computer
spontaneously combusting at the exact moment you win the lottery.
3. If someone creates a database of all primes, won't he be able to use
that database to break public-key algorithms?
Yes, but he can't do it. If you could store one gigabyte of information
on a drive weighing one gram, then a list of just the 512-bit primes would
weigh so much that it would exceed the Chandrasekhar limit and collapse
into a black hole ... so you couldn't retreive the data anyway."
Considering that our own magic number is 960 bits long, our prospects
for cryptanalysis don't look so good.
I went back an reread Bruce Tomlin's description of the algorithm in the
7800 ROM and compared it to the RSA algorithm, and the two do seem very
similar. Bruce wrote that:
Y = X^2 MOD Z
where X must be the encrypted hash (checksum) of the cartridge, Z must be
the public key, and Y must be the unencrypted hash (checksum). Z is known
and embedded in the ROM and Y can be calculated, so we're only missing X.
This *really* looks like RSA when used a digital signature algorithm
(encrypting the hash of the cartridge instead of the entire cartridge),
but RSA uses a different exponent for X instead of 2 in the decryption
stage. RSA uses an exponent that is related to the two factors of Z
(which is the public key). Could this be the break we are looking for?
Perhaps it really isn't necessary to factor Z to find X, since this seems
to be a restricted version of RSA with that exponent clamped to a specific
value (in this case, 2).
To show just how RSA works, I'll include a short example from Schneier's
book (more or less directly quoted). I'm still struggling to fully
understand it as a novice, but perhaps it might make sense to some of the
list members. To start, choose two prime numbers p and q at random.
Let's choose p = 47 and q = 71. Calculate the product n where:
n = p*q
which gives us n = 3337. Now, we need to find the encryption key e, which
must not have any common factors with (p-1)*(q-1), namely 46*70, or 3220.
Let's choose e to be 79, at random. We now need the decryption key d such
that:
e*d = 1 mod (p-1)(q-1)
or
d = e^(-1) mod ((p-1)(q-1))
That gives us:
d = 79^(-1) mod 3220 = 1019
which can be calculated from the extended Euclidean algorithm. Publish e
and n (the public key), and keep d (the private key) secret. Discard p
and q, but never reveal them.
To encrypt the message m = 6882326879666683 first break it into small
blocks. Three-digit blocks would work nicely in this case. The message
is split into six blocks, m1 through m6, in which:
m1 = 688
m2 = 232
m3 = 687
m4 = 966
m5 = 668
m6 = 003
Encrypting a message block is defined as:
c = m^e mod n
where m is the plain text, c is the cipher text, and e and n are as
defined above. Decrypting the message block is similar, with:
m = c^d mod n
with d as defined above.
The first block is encrypted as:
688^79 mod 3337 = 1570 = c1
Performing the same operation on the subsequent blocks generates an
encrypted message:
c1 = 1570
c2 = 2756
c3 = 2091
c4 = 2276
c5 = 2423
c6 = 158
Decrypting the message requires performing the same exponentiation using
the decryption key of 1019, so:
1570^1019 mod 3337 = 688 = m1
The rest of the message can be recovered in this manner.
Now, how does this apply to our Atari 7800 problem? Well, in RSA the
exponent used for encryption and decryption is either e or d, which depend
indirectly on p and q, the factors of n. Thus factoring n must be the way
to determine the private key if you know the public key (which you
should). Since knowing the public key gives you n and e, if you can
determine p and q (the factors of n) then you can determine the private
key!
Since the 7800 appears to use a fixed exponent (2), does this mean that
its signature algorithm can be cracked without factoring anything? That
is the question, gentlemen!
Paul Hart
--
Paul Robert Hart ><8> ><8> ><8> Verio Web Hosting, Inc.
hart@xxxxxxxxxxx ><8> ><8> ><8> http://www.iserver.com/
--
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/
