Re: Mathematics > NSA + GCHQ

Tim May wrote:

>Thus, as bright as Brian Snow or Don Coppersmith or John Conway may be, the
>"edge" the NSA may have once had is largely gone. Which is not to say that
>they are not still a formidable technical organization, with substantial
>computer resources.
>
>But modern crypto systems are, as we all know, based on fundamental
>mathematical results ...

Along this line:

A few days ago we received an 8-page excerpt from "Shift Register
Sequences," by Solomon W. Golomb (at USC), Holden-Day, Inc., 
no date, with a handwritten note:

   NSA has tried to suppress knowledge of this stuff. Nearly all NSA 'good'
   algorithms are based on this technology.

IANAM, so would any of the mathematicians here give any credibility to 
this claim? We'll scan and put the excerpt on our Web site if worthwhile.
It's composed of the book's 3 page preface and 5 pages of text and
diagrams of Chapter 2 on The Shift Register as a Finite State Machine,
with principal focus on de Bruijn diagrams for shift registers.

John Young writes:

> Along this line:

> A few days ago we received an 8-page excerpt from "Shift Register
> Sequences," by Solomon W. Golomb (at USC), Holden-Day, Inc., 
> no date, with a handwritten note:

>    NSA has tried to suppress knowledge of this stuff. Nearly all NSA 'good'
>    algorithms are based on this technology.

> IANAM, so would any of the mathematicians here give any credibility to 
> this claim?

"The Magic Singing and Dancing Shift Register Algorithm" has been making
the rounds for a number of years now, and surfaces in various forms at
periodic intervals on the Net. 

It is based on a mathematical technique once used to do transcendental
function approximation on now slow and obsolete calculator chips, and as
far as I can tell, offers no magic insights into efficient ways of
computing cryptographically interesting functions, such as factoring,
descrete log, or symmetric block cipher key recovery.

I would put it in my comedy file along with the "RSA is Easy To Break"
paper, and similarly innumerate rants. 

> We'll scan and put the excerpt on our Web site if worthwhile.
> It's composed of the book's 3 page preface and 5 pages of text and
> diagrams of Chapter 2 on The Shift Register as a Finite State Machine,
> with principal focus on de Bruijn diagrams for shift registers.

The book is probably a serious text on the mathematical techniques in
question.  But unless you are looking for a way to compute Trig functions
with lots of iterations and little hardware, it probably isn't worth more
than a cursory glance.  It's not going to break codes for you.

--
     Mike Duvos         $    PGP 2.6 Public Key available     $
     enoch@zipcon.com   $    via Finger                       $
         {Free Cypherpunk Political Prisoner Jim Bell}

John Young <jya@pipeline.com> writes:

> Along this line:
>
> A few days ago we received an 8-page excerpt from "Shift Register
> Sequences," by Solomon W. Golomb (at USC), Holden-Day, Inc.,
> no date, with a handwritten note:
>
>    NSA has tried to suppress knowledge of this stuff. Nearly all NSA 'good'
>    algorithms are based on this technology.
>
> IANAM, so would any of the mathematicians here give any credibility to
> this claim? We'll scan and put the excerpt on our Web site if worthwhile.
> It's composed of the book's 3 page preface and 5 pages of text and
> diagrams of Chapter 2 on The Shift Register as a Finite State Machine,
> with principal focus on de Bruijn diagrams for shift registers.

The NSA certainly did try to suppress much shift-register-related stuff.

The recent Sandia lawsuit is over shift register stuff.

There are increasingly persistent rumor of a fast factoring algorithm
based on shift registers.

Therefore anything mentioning them is of interest.

But: Was there any info in the package other than the passages from the book?

I don't think it's a good idea to put up chunks of the book - the publisher
might cry copyright infringement, and everybody probably has it anyway.

[I'm about to turn off this box, so I won't see any responses in a while.]

---

Dr.Dimitri Vulis KOTM
Brighton Beach Boardwalk BBS, Forest Hills, N.Y.: +1-718-261-2013, 14.4Kbps