more from RISKS

[dat@ebt.com (David Taffs)]

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

------------------------------