At 09:20 AM 3/27/98 -0800, you wrote: >Marco DI LEO quotes the "Free On-Line Dictionary Of Computing" at >http://wombat.doc.ic.ac.uk/foldoc/index.html: >> security of RSA is predicated on the assumption that factoring is >> difficult; an easy method for factoring large prime numbers would >> break RSA. > >Actually, factoring primes is very easy. It's factoring composites >that can be tricky. Factoring primes is a snap since there are no factors, except possibly itself and 1, which doesn't count since then there would be no prime numbers. Factoring a pseudo prime (as used in RSA) into its two primes is tough. I already said this. I miss your point. >Richard Nowak writes: >> I would like to get more data on this one. Every so often someone claims to >> have cracked RSA but in every case I've heard of the claim was false. >> >> The problem is to show mathematically how to factor a *very* large pseudo >> prime number into its two prime factors. This is the part I want to see. >> >> A billion computers working in parallel to do it once is not a crack. If in >> fact it was accomplished it was either because the primes were >> insufficiently large or the guy was very lucky. > >I think there may be differing definitions of "cracked" at work >here. Richard seems to mean that a cracked code is one for which >an easy reversal algorithm exists. Obviously an encryption scheme >becomes completely useless when "cracked"; I'm not aware of any of >the popular encryption schemes being "cracked" by this definition. In RSA we know the "reversal" algorithm. If we didn't the poor bastard we sent the message to could spend the next trillion years trying to figure it out. RSA's success is based on the fact that there is no simple way to factor a pseudo prime number. There is no concern whether the methodology gets into the "wrong" hands or not. The scheme is already known. That's why it's so cool. The encryption scheme does not necessarily become useless if somebody discovers a key. I will grant you, however, that the secrecy of the message is lost. >However, some people have worked on decoding single messages with >brute-force attacks. RSA offers rewards for this, in fact, in >order to show that lesser encryption systems are inadequate. There are many strategies to consider when launching a brute force attack on an encrypted message. RSA, as part of their testing, has enticed many into a game of trying to "crack" a series of encrypted messages - even offering money to the machine that discovers the key. In doing this they would hope that somebody would stumble onto some anomaly if one existed in the process. Someone may even discover a fast method of factoring pseudo primes quickly which would defeat RSA's encryption strength. I've signed on the RC5-64 project and my machine acts in concert with possibly thousands of others on the internet in a mass brute force attack on one encrypted message. The process runs in the background and has no noticeable impact on the performance of my PC. My machine process keys at the rate of 280,000 keys/sec and runs 18 hours/day. There are teams out there processing keys at the rate of 750 Million keys/sec. The key size is 64 bits - 2^64 possible keys. It has been estimated that to develop an engine to do the job in the time frame required by government (on the order of 10-20 seconds to discover the key) would cost about 500 million dollars and about six months to build. This internet attack is expected to take a couple of years before the message is "cracked". In an earlier posting I mentioned 3000 char [width] but I believe in one of the original papers I read on RSA the key width discussed was on the order of two to three hundred characters, and was the basis of the "age of the earth" time frame to crack a message encrypted using the RSA public/private key scheme. Rich ========================================= = Abolish the Income Tax! Fire the IRS! = = http://www.nrst.org/ = ========================================= ========================================= = Here's a site that wants your views = = http://www.not4irs.org/ = =========================================