🚀 go-pugleaf

A Silicon Valley Company has a (very fast) chip implementation of
exponentiation (mod m) currently available.  It supports the standard
public key crypto-algorithms which involve exponentiation including RSA.

The company is

	Cylink 
	920 West Fremont Avenue
	Sunnyvale, CA 94087

dgc

David G. Cantor
Internet:  dgc@cs.ucla.edu
UUCP:      ...!{ihnp4, randvax, sdcrdcf, ucbvax}!ucla-cs!dgc

       Is the patent out in any country yet?  I'm interested in seeing how
it works.  A patent number for any country would be appreciated.  In
any case, these things can't be considered secure until they've stood
considerable scrutiny.  Always remember Friedman's remark, "No new cypher
is worth looking at unless it comes from someone who has already broken a very
difficult one."
       The big problem with public key systems is that one needs some
suitable function whose inverse is enormously harder to compute than the
function itself.  The two functions most discussed to date are the knapsack
problem and the factorization of large numbers, and advances in mathematics
have made both problems much more tractible in the last few years.  If
someone has a new function, it may be a significant step forward.  Or
it may not.  One would like a problem with a provable lower bound, but the
theory of lower bounds is very weak as yet.
       With the advent of good, fast, modem technogies, and good voice
digitization and compression schemes, the use of digital encryption for
voice over voice-grade lines without serious loss of quality is already
possible.  If this new scheme works, one could produce secure telephones
for consumer use which would automatically exchange public keys at startup
and then go to encrypted digital mode when talking to another of their
own kind.  This sounds expensive and complicated, but it will eventually 
come down to one chip with a small number of pins.  
       This has definite product potential.  Let's hear more details about
the technology.

					John Nagle

					John Nagle

-		It is virtually impossible for an outsider to break the 
-	decrypting key, which consists of a binary string of more than 1,000 
-	characters, Mr. Vanstone said.
-		"It would take more than a billion years, working with the 
-	fastest computers available, to break just one key," he said.

I hope it is obvious to most readers of this newsgroup that
the above claim is bullshit.  A similar argument would lead
to the claim that Rubik's cube would take forever to solve.

I personally have broken cryptosystems with longer keys.
There is more to cryptosystem strength than key length.

> / sci.crypt / gwyn@brl-smoke.ARPA (Doug Gwyn ) /  8:56 am  Jan  7, 1987 /

> -		It is virtually impossible for an outsider to break the 
> -	decrypting key, which consists of a binary string of more than 1,000 
> -	characters, Mr. Vanstone said.
> -		"It would take more than a billion years, working with the 
> -	fastest computers available, to break just one key," he said.
> 
> I hope it is obvious to most readers of this newsgroup that
> the above claim is bullshit.

    Pretty strong statement, Doug.  Let's look a little closer...

    If they use RSA, and the product number (public key) is 1000 bits long,
    we can ask how log it would take to factor the public key, or
    alternatively, how much it would cost.  It presently costs about US$100000
    to factor a 100 digit number.  The cost increases by a factor of ten for
    each ten digits.  1000 bits is 300 digits, so the cost of factoring the
    public key would be US$10000000000000000000000000.  I think that's enough
    to deter even the NSA.  For a Cray 2, assuming a cost of operation of
    US$10Meg per year, this works out to 10^18 years.  This is > 1 billion.

    Of course there are some hazy points.  Do they use RSA, are there fast
    methods of breaking RSA (or factoring), is "1000 characters" actually
    1000 bits, is my cost estimate and scaling formula correct, etc?  The
    point is that Mr. Vanstone's statement, while unclear as quoted, is not
    unreasonable.

In article <5490@brl-smoke.ARPA>, gwyn@brl-smoke.ARPA (Doug Gwyn ) writes:
> -		It is virtually impossible for an outsider to break the 
> -	decrypting key, which consists of a binary string of more than 1,000 
> -	characters, Mr. Vanstone said.
> -		"It would take more than a billion years, working with the 
> -	fastest computers available, to break just one key," he said.
> 
> I hope it is obvious to most readers of this newsgroup that
> the above claim is bullshit.  A similar argument would lead
> to the claim that Rubik's cube would take forever to solve.
> 
> I personally have broken cryptosystems with longer keys.
> There is more to cryptosystem strength than key length.

I think everybody realizes that, and actually it is your notice that is
bullshit.  The original posting (which you even quoted) draws no comparison
between key length and time to break the key.  They are two different
statements in different paragraphs.  The way I read this is similar to the
way I would read a statement on, say, the RSA protocol.

Namely, breaking the RSA protocol has the same complexity as factoring
a very large number.  The fastest computer available today would take
several billion years to factor such a large number, giving the security
of the system.

Clearly, nobody would consider an attempt at trying *all* keys (which would
take considerably longer than a billion years for such a large key) as you
seem to imply (with the statement about Rubik's Cube).

-- 
Steve Tate			UUCP: ..!{ihnp4,decvax}!duke!srt
				CSNET: srt@duke
				ARPA:  srt%duke@csnet-relay

> It is virtually impossible for an outsider to break the 
> encrypting key, which consists of a binary string of more than 1,000 
> characters, Mr. Vanstone said.
> "It would take more than a billion years, working with the 
> fastest computers available, to break just one key," he said.

  Ok if I believe the assertion that it is impossible for an outsider
to break the key (absolute security? right...), why, then I'll just
bribe an insider!  Startling new idea isn't it :-)

Bob Devine

In article <117@vianet.UUCP> devine@vianet.UUCP (Bob Devine) writes:
>[If it is impossible for an outsider to break the key], why, then I'll just
>bribe an insider!  Startling new idea isn't it :-)

I've heard that was the problem with the Great Wall of China.  Incredible
accomplishment (visible from the Moon?), but the enemy bribed a gatekeeper.

>> [it is "virtually impossible" to break a certain system]

> Ok if I believe the assertion that it is impossible for an outsider
> to break the key (absolute security? right...), why, then I'll just
> bribe an insider!  Startling new idea isn't it :-)

Right.  People are often the weakest link in a security system.

Assuming, that is that there *is* an insider who knows the key.  If
they were smart, there is no such person.  (They killed him as soon as
he typed in the numbers....:-)  A box could have, let us say, a
cosmic-ray detector which it uses to generate large numbers, then maybe
it counds by twos until it finds primes.  (No flames on details please,
I just want to show the idea is feasible.)

					der Mouse

USA: {ihnp4,decvax,akgua,utzoo,etc}!utcsri!mcgill-vision!mouse
     think!mosart!mcgill-vision!mouse
Europe: mcvax!decvax!utcsri!mcgill-vision!mouse
ARPAnet: think!mosart!mcgill-vision!mouse@harvard.harvard.edu

In article <602@mcgill-vision.UUCP> mouse@mcgill-vision.UUCP (der Mouse) writes:
>>...bribe an insider!  Startling new idea isn't it :-)
>Right.  People are often the weakest link in a security system.
>
>Assuming, that is that there *is* an insider who knows the key.  If
>they were smart, there is no such person.  (They killed him as soon as
>he typed in the numbers....:-)  A box could have, let us say, a
>cosmic-ray detector which it uses to generate large numbers, then maybe
>it counds by twos until it finds primes.  (No flames on details please,
>I just want to show the idea is feasible.)

OK.  Bribe an insider to learn the technology and the time when keys are
generated.  At that time, a nuclear accelerator in a truck on the street
outside will create a modulated signal for the key generator's detector.
Noise might interfere with the signal, but the technique might skew the keys
in a known way.  [OK, let's not get into a counteratomic spoofing discussion]

Any method which uses an external signal depends upon secrecy of the
algorithm.  If an outsider can't spoof the signal, he might be able
to listen to it and duplicate the key generation.

With a radio receiver as the detector, the above could be called "electronic
warfare".  But in the atomic field, "nuclear warfare" has another
meaning, although that also messes up detectors :-)

-- 
Scot E. Wilcoxon   Minn Ed Comp Corp  {quest,dayton,meccts}!mecc!sewilco
(612)481-3507           sewilco@MECC.COM       ihnp4!meccts!mecc!sewilco
   
  "Who's that lurking over there?  Is that Merv Griffin?"

> >> [it is "virtually impossible" to break a certain system]

> > Ok if I believe the assertion that it is impossible for an outsider
> > to break the key (absolute security? right...), why, then I'll just
> > bribe an insider!  Startling new idea isn't it :-)

> [What if] there is no such person.  (They killed him as soon as
> he typed in the numbers....:-)

  It then might be possible to use the third part of system security --
denial of service (theft of information and creation of false information
are the other two).  In a statement to the owners of a system, we would
say "Alright! Give us all your encrypted information or da computer gets it!".
Such statements carry more weight if you have arranged to aim a rather
nasty weapon in the general direction of the computer beforehand...

  This approach may not bring the expected result if you try it against
people who have even nastier weapons aimed at you.

Bob Devine