Re: What ever happened to... Cray Comp/NSA co-development

At 10:32 PM 12/17/95, Anonymous wrote:

>What caught my attention was the architecture.
>
>A "hybrid design linking two supercomputer processors with an
>array of HALF A MILLION inexpensive processors" that were
>designed by the U.S. government laboratory affiliated with the
>NSA. The same chip house that brought us Clipper.

First, half a million chips is not that big a deal...the Connection Machine
had up to 64,000. Very few cryptographic problems of interest to us will be
affected by a mere factor of a million or so.

Second, there was work on a "processor-in-memory" architecture, in
conjunction with a Bowie, Maryland spook-connected company. Perhaps this is
what you are thinking of?

Third, all avenues of continued funding having fallen through, Cray
Computer (not Cray Research, of course) was shut down and assets
liquidated. I haven't heard what's become of Seymour, though. (He is
undoubtedly an asset, buy I doubt the Agency would have him liquidated.)

>I've not kept up with the "ultimate" demise that eventually
>befell Cray Computer Company, but the October 16 FBI filing
>on capacity for Digital Telephony got me thinking back to this
>article. 1% seems like a rather huge need for horsepower. And
>what if GAK doesn't fly? And the widespread use of hard crypto
>just keeps increasing?

The tightly-coupled supercomputers are hardly needed for these sorts of
problems.

>This kind of machine could, in theory:
>
>1) Implement ALL Clipper(II) based Key Escrow functionality in
>   silicon (the easy part) AND allow for simultaneous decrypt and
>   surveil of 'who knows how many' Clipper based data streams.

Huh? First, what evidence do you have for this claim? Second, who cares?
Implementing Clipper in a Cray Computer machine--why bother?

As to the claim that a million-processor machine could do this, you need to
work out the math. (If a backdoor exists, or the LEAF has been gotten, a
supercomputer is not needed....)

>2) Implement general RSA based Prime Factoring functionality in
>   silicon (the not so easy part) AND allow massively parallel
>   decrypt and surveil of 'who knows how many' RSA/etc. based
>   data streams.

Prime Factoring? Primes are easy to factor, of course. (Hint: Every prime
has two factors.)

If you mean using supercomputers to brute force the general factoring of an
RSA modulus, this is nonsense. While there may be math shortcuts we don't
yet publically know about which make factoring easier than we currently
think it is, a mere million or even a billion processors will not make a
dent in the factoring of, say, a 700-digit modulus. See the tables in
Schneier and elsewhere for some estimates of factoring efforts needed.

>3) Implement it all, AND 'on-line' transaction based surveillance
>   via the FBI's 1% capacity infrastructure.

Let's see some numbers. (On second thought, let's not.)


>Chilling... Who needs key escrow (or RSA private keys) when
>you've got a massively parallel prime factoring machine. What if
>GAK was to become a 'non-issue'? How fast do you think a machine
>such as this could factor RSA 129?

Well, do the math. The MIPS-years for the RSA-129 crack were publicized, so
the computation for a million SPARC-equivalent (or even
UltraSPARC-equivalent) can be done.

When you've done this, and concluded that RSA-129 could be done in, say, X
minutes, then move on to RSA-384 (the BlackNet key cracked by the MIT
group), and on to the 1024- and 2048-bit keys. Tell us how many years or
centuries it will take. (Hint: Rivest and Schneier have done these
calculations....)


--Tim May, who fears that he's just been trolled by Derek Atkins


Views here are not the views of my Internet Service Provider or Government.
---------:---------:---------:---------:---------:---------:---------:----
Timothy C. May              | Crypto Anarchy: encryption, digital money,
tcmay@got.net  408-728-0152 | anonymous networks, digital pseudonyms, zero
Corralitos, CA              | knowledge, reputations, information markets,
Higher Power: 2^756839      | black markets, collapse of governments.
"National borders are just speed bumps on the information superhighway."

Correction of one detail:

> tcmay@got.net (Timothy C. May) writes:
> When you've done this, and concluded that RSA-129 could be done in, say, X
> minutes, then move on to RSA-384 (the BlackNet key cracked by the MIT
> group), and on to the 1024- and 2048-bit keys. Tell us how many years or
> centuries it will take. (Hint: Rivest and Schneier have done these

The BlackNet key break didn't have any MIT involvement: it was done by
Paul Leyland of Oxford, Arjen Lenstra of Bellcore, Alec Muffet of Sun UK,
and Jim Gillogly of Cypherpunks, RAND, and Gillogly Software in no
particular order.

	Jim Gillogly
	Trewesday, 28 Foreyule S.R. 1995, 05:49

Correction of another detail:

> > tcmay@got.net (Timothy C. May) writes:
> > When you've done this, and concluded that RSA-129 could be done in, say, X
> > minutes, then move on to RSA-384 (the BlackNet key cracked by the MIT
> > group), and on to the 1024- and 2048-bit keys. Tell us how many years or
> > centuries it will take. (Hint: Rivest and Schneier have done these

RSA-129 is 129 decimal digits, not 129 bits.  This computes to about
425 bits, which is actually more difficult than the 384-bit Blacknet
key.

-derek

-----BEGIN PGP SIGNED MESSAGE-----

Hello,

tcmay wrote:
...
> Prime Factoring? Primes are easy to factor, of course. (Hint: Every prime
> has two factors.)
...

Can someone enlighten me as to what the two factors are?

With sensible definitions I've heard you either get one (just itself)
or four (itself [p], both units [1,-1] and the co-whatsitsname [-p]).

(Sorry to pick on tcmay, but usually when you factorise a number you
*never* put it a "1*", for example:
  6 = 2*3
  9 = 3*3*3
and
  7 = 7
not
  7 = 1*7
, so I suspect the usual statement would be "Every prime has one factor.".)


Or am I totally clueless?

Jiri
- --
If you want an answer, please mail to <jirib@cs.monash.edu.au>.
On sweeney, I may delete without reading!
PGP 463A14D5 (but it's at home so it'll take a day or two)
PGP EF0607F9 (but it's at uni so don't rely on it too much)

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2i

iQCVAwUBMNdXQyxV6mvvBgf5AQEaNwP/RB9ABUWWX20hChSFC5embOLwv7dhI4qU
rJkz/VmOM8y746be87nAIKCih3hJCz7G4OqsqiVdtvhx2FqldqSuw6Jmp3Mx41ut
l+OdwwHYH0K7OH1SIRr9nfpZ4IuZ3dsXVTTPl1H8Z3ktv5B4hFziLiIt3WPZTqVu
k4nXVsirfuo=
=X1zb
-----END PGP SIGNATURE-----

On Wed, 20 Dec 1995, Jiri Baum wrote:

...
> Can someone enlighten me as to what the two factors are?
...
In this country, children are taught that prime numbers indeed have two 
factors: 1 and themselves.  I suspect its a cultural difference.

Ben.
____
Ben Samman..............................................samman@cs.yale.edu
"If what Proust says is true, that happiness is the absence of fever, then
I will never know happiness. For I am possessed by a fever for knowledge,
experience, and creation."                                      -Anais Nin
PGP Encrypted Mail Welcomed      Finger samman@powered.cs.yale.edu for key
Want to give a soon-to-be college grad a job?         Mail me for a resume

On Wed, 20 Dec 1995, Jiri Baum wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> 
> Hello,
> 
> tcmay wrote:
> ...
> > Prime Factoring? Primes are easy to factor, of course. (Hint: Every prime
> > has two factors.)

> ...
> 
> Can someone enlighten me as to what the two factors are?
> 

The two factors of a prime number are itself and one.  However, prime 
factoring usually refers to (?) factoring a number out into it's 
component prime numbers.

Tobin Fricke