More from Risks... Amos Shapir's point below is well taken -- if indeed computer capacity is growing exponentially, which from all accounts it seems to be, then any code can be broken in linear time! ------------------------------ RISKS-LIST: RISKS-FORUM Digest Weds 11 May 1994 Volume 16 : Issue 05 ------------------------------ Date: Tue, 10 May 1994 15:37:05 -0400 From: pcw@access.digex.net (Peter Wayner) Subject: Re: Elevators, Car bumpers and Cryptography... I once talked to a major elevator company about doing just what the Schindler Elevator Corp. is accused of doing by the Toronto government. (RISKS-16.04). The company told me that they were in the habit of selling the elevators at a loss so they could make up the money in service contracts. Then they found themselves battling independent service companies who undercut their prices. They hoped to use cryptography to lock out any other service provider without the right key. Of course, this loss-lead approach is common in many businesses. Car companies often sell their cars at a low price and hope to make it up selling spare parts later. That is why I discovered that a spare bumper for my car cost over $500. The difference is that other companies are now making duplicate parts. The major automakers can try and discourage them, but they can't lock them out of the business. Cryptographic locks, though, are a different story. They probably can't be broken in a reasonable amount of time. (See also 16-04) I'm not sure of the case law on this, but I would suspect that it might fall under questionable or illegal trade practices. At least in the US. ------------------------------ Date: Tue, 10 May 94 19:33:36 PDT From: Fredrick B. Cohen <fc@Jupiter.SAIC.Com> Subject: Re: Bellcore cracks 129-digit RSA encryption code (RISKS-16.04) I think a lot of people are missing the real point about the RSA. On my pocket PC, I can create a code that requires 5,000 MIP years to break in a matter of seconds. If I am willing to use several more seconds, I can make a code that takes 10^25 MIPS years to break. Compare this to any other encryption scheme, and you will find that the workload amplification of the RSA is quite good. And Shannon told us in 1949 that any non-perfect information transform can be broken with enough cyphertext - and developed the concept of workload for evaluating cryptosystems. If we want perfect cryptosystems we know how to get them, but it requires secure distribution. On the other hand, the RSA provides any degree of complexity we wish to generate (finite) and a fantastic complexity amplification factor, and the advantages of a dual public key system that can be used for both encryption and authentication. The point is that the RSA has not been broken, rather it has shown just how much of a David is required to defeat a given Goliath. After all, in terms of that story, David would have been a MIP second and Goliath 5,000 MIP years in relative sizes for a break-even fight. I'll take that David any day. FC ------------------------------ Date: 11 May 1994 15:19:01 GMT From: amos@CS.HUJI.AC.IL (Amos Shapir) Subject: Re: Bellcore cracks 129-digit RSA encryption code (RISKS-16.04)
So where does the 40 quadrillion figure come from?
It comes from this very table. 10^9 is a billion, not a trillion, in the US system, and 40 quadrillion is 4 x 10^16, which is even less than what I get by interpolating to 425 bits (can anyone who has access to the original RSA article verify this?). There seems to be an interesting risk here: most encryption methods rely on "hard" problems, i.e. problems whose "brute force" solutions require computation resources which are an exponential function of the key length. But in a world in which computing power grows exponentially, such problems can be solved in polynomial (or even linear) time! Amos Shapir, The Hebrew Univ. of Jerusalem, Dept. of Comp. Science. Givat-Ram, Jerusalem 91904, Israel +972 2 585706,586950 amos@cs.huji.ac.il ------------------------------