From: wayner@CS.Cornell.EDU (Peter Wayner)
Newsgroups: sci.crypt

Subject: Re: Braided streams (The Leichter Side)
Message-ID: <>
Date: 24 Jun 91 14:36:12 GMT
References: <1991Jun23.042445.9676@elevia.UUCP> <>
Sender: (USENET news user)
Organization: Cornell Univ. CS Dept, Ithaca NY 14853
Lines: 20

Hey, I just remembered something with regard to Braided streams
and known plaintext attacks. Let's say that you know that 
some string of bits, {b1,b2,} which has been braided into
the ciphertext {c1,c2,}. The goal is to retrieve the key, which
in this case is all the of the bits in the ci's that aren't derived
from the bi's. 

There is a UNIX command called "diff" which will display the
line-by-line differences between two text files. It will take two text
files, A and B, and figure out what lines have been inserted/deleted
in A to make B. The algorithm is pretty cool and, if I remember
correctly, runs in a reasonably polynomial time. I'll check on it. 


Peter Wayner   Department of Computer Science Cornell Univ. Ithaca, NY 14850    Office: 607-255-9202 or 255-1008
Home: 116 Oak Ave, Ithaca, NY 14850  Phone: 607-277-6678