Path: cactus.org!milano!cs.utexas.edu!usc!elroy.jpl.nasa.gov!swrinde!zaphod. + mps.ohio-state.edu!rpi!batcomputer!cornell!wayner From: wayner@CS.Cornell.EDU (Peter Wayner) Newsgroups: sci.crypt Subject: Re: Braided streams (The Leichter Side) Message-ID: <1991Jun24.143612.6277@cs.cornell.edu> Date: 24 Jun 91 14:36:12 GMT References: <1991Jun23.042445.9676@elevia.UUCP> <25633@well.sf.ca.us> Sender: news@cs.cornell.edu (USENET news user) Organization: Cornell Univ. CS Dept, Ithaca NY 14853 Lines: 20 Nntp-Posting-Host: kama.cs.cornell.edu 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,b3...bn} which has been braided into the ciphertext {c1,c2,...cm}. 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 -- Peter Wayner Department of Computer Science Cornell Univ. Ithaca, NY 14850 EMail:wayner@cs.cornell.edu Office: 607-255-9202 or 255-1008 Home: 116 Oak Ave, Ithaca, NY 14850 Phone: 607-277-6678