pearson cipher?
By anders pearson 01 Mar 2002
pretty much everyone who studies cryptography a little eventually thinks they’re clever and comes up with their own encryption scheme. of course, since they’re just amateurs, most of these schemes are easily broken by any expert who has time to crack it. but experts’ time is precious so the end result is thousands and thousands of (weak) amateur encryption routines floating around. still, coming up with your own encryption scheme is fun and good practice so here’s my attempt. i at least know enough to do a little analysis and maybe point out some of the interesting parts. it’s a pretty straightforward cipher so i’d be surprised if no one else has independently discovered it, but i couldn’t find anything similar in the small collection of crypto books in my apartment.
<p>first, i need to explain a little about pseudo-random number generators (<span class="caps">PRNG</span>s). since it’s really impossible to generate true randomness with a deterministic machine like a computer (as Von Neumann said: “Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.”). so when computers need “random” numbers, they resort to <span class="caps">PRNG</span>s, often using a “seed” from the outside world. a <span class="caps">PRNG</span> is essentially a mathematical function that given a particular number as input will give you another number as an output in a way that doesn’t really have any predictableness or pattern to it. you generate a series of random numbers by feeding the output of each cycle back in as input. you can generally prove that for any starting “seed”, a given <span class="caps">PRNG</span> will eventually loop back to the beginning and give that seed as output after a certain number of cycles. the better the <span class="caps">PRNG</span>, the more cycles you have to go through before you get this repetition. the algorithms most cryptographic applications use will only loop after somewhere on the order of 2^256 cycles. since that’s more than the number of atoms in the universe, even though it’s not “true” randomness it’s usually good enough for practical applications.</p>
<p>the other key thing to understand with <span class="caps">PRNG</span>s is that they should be repeatable. meaning that if you give it the same seed twice, you will get the same sequence of random numbers both times. this is useful because it lets you check the results of some simulation that you may have used the numbers for. it also means that if you really want random numbers, you have to be careful to pick a seed that can’t be guessed. so usually some kind of outside source of randomness will be used as the seed, eg, a number based on the time between keystrokes as the user types.</p>
<p>also a note about one-time pads. one-time pads are the only <em>provably</em> secure cipher. as long as the key used is longer than the message being encrypted, is random, and the same key is <strong>never</strong> used more than once, a one-time pad provides perfect encryption. the problem is that the restriction of keys never being used more than once makes them somewhat impractical.</p>
<p>my cipher essentially makes use of a <span class="caps">PRNG</span> to generate keys for one-time pads. here’s how it works:</p>
<p>Alice and Bob have a shared number K<small><sub>A-B</sub></small> that they generated randomly (using a “true” random number generator) that’s about 128 bits long (or longer if they’re really paranoid). they’re the only ones that know the number and have gone to great pains to keep it secret. there is also a <span class="caps">PRNG</span> P which is public, has a really long period (ie, it’s a good <span class="caps">PRNG</span>) and is repeatable.</p>
<p>when Alice wants to send a message to Bob, she generates another random number S (also about 128 bits long). then she takes the bitwise <span class="caps">XOR</span> of S and K<small><sub>A-B</sub></small> (<span class="caps">XOR</span> is the exclusive-or logical operation: 1 <span class="caps">XOR</span> 1 = 0, 1 <span class="caps">XOR</span> 0 = 1, 0 <span class="caps">XOR</span> 1 = 1, 0 <span class="caps">XOR</span> 0 = 0). she uses the result of this <span class="caps">XOR</span> as a seed for P. the string of random numbers that P produces, she uses as a one-time pad key for encrypting her message M. she takes the resulting ciphertext C and sends (C,S) to Bob. </p>
<p>to decrypt, Bob takes S, <span class="caps">XOR</span>s it with K<small><sub>A-B</sub></small> and feeds it to P to produce the one-time pad key. with that he decrypts C to retrieve M.</p>
<p>that’s all there is to it. what i think makes this algorithm interesting is that it offloads all the security to K<small><sub>A-B</sub></small> being secret and large enough that guessing it would be pretty much impossible and to the <span class="caps">PRNG</span> not being predictable. if fact it should be fairly simple to prove that cracking this scheme is <em>entirely</em> dependent on discovering a pattern in the <span class="caps">PRNG</span>. while i’m not an expert, i believe that there are some pretty good <span class="caps">PRNG</span> algorithms out there. however, i would guess that, similar to how we suspect but haven’t ever proven that factoring large numbers is extremely difficult, the best we could do for a <span class="caps">PRNG</span> is suspect but not prove its lack of predictability.</p>
<p>the drawback may be that since you have to generate a new random S for every message, the generation of S could be slow if you require that S also be truely random. i’m not sure if that’s really a requirement though; it’s probably good enough if S was generated from a <span class="caps">PRNG</span> that was given a truely random seed. in that case, we could also prove that the speed of encrypting and decrypting is pretty much dependent on the speed of the <span class="caps">PRNG</span>.</p>
<p>the advantages are that if you have a <span class="caps">PRNG</span> which you know to be efficient and secure, you can do encryption that is just about as efficient and just as secure.</p>
<p>from a theoretical point of view, the cipher may be interesting because it is provably as secure as the <span class="caps">PRNG</span>. eg, Rabin public key encryption, though not used very much, was considered a big theoretical advancement because it was provably as secure as factoring large numbers. ie, you could crack Rabin encryption if and only if you could factor large numbers. <span class="caps">RSA</span> on the other hand, <em>may</em> someday be shown to have other weaknesses.</p> Tags: cryptography