Subject: Re: [stella] A7800 From: Paul Hart <hart@xxxxxxxxxxx> Date: Tue, 8 Dec 1998 16:11:49 0700 (MST) 
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 wellknown _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 publickey 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 512bit 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 (p1)*(q1), 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 (p1)(q1) or d = e^(1) mod ((p1)(q1)) 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. Threedigit 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/
Current Thread 


< Previous  Index  Next > 

Re: [stella] A7800, jvmatthe  Thread  [stella] A7800, Keith W Gerdes 
[stella] A7800, Keith W Gerdes  Date  [stella] Atari 7800 checksum algori, Paul Hart 
Month 