Previous lecture

Table of contents

Next lecture

I congratulated students because almost all of the RSA assignment was done: the red balls have been turned to blue. I also was cutting up my twinned bits to put them in the randomizer -- an effort to construct a one-time pad. I then asked Ms. Wu to discuss how she had "broken" RSA. She won a prize.

I remarked that we had done binary conversion and arithmetic last time. Today we would do a provably totally secure method of encryption. I wrote the addition and multiplication tables mod 2, mentioning this was binary arithmetic without carries. I identified 0 and 1 as off and on, and also indicated that 0 and 1 were true and false. I even mentioned Leibniz and attempting to arithmetize philosophy via symbolic logic. The tables for addition and multiplication I identified as "exclusive or" and "and". I tried to indicate their logical meanings.

Then I discussed "random". I asked people to define the word. My target was to get some idea of what a random bitstream might mean. For example, one suggestion was made to just flip a coin. I replied that many U.S. coins were top heavy, with a bias towards heads. Constructing a random stream of bits was rather difficult in practice. My operational definition of "random" was that neither I nor anyone could predict a bit.

I then discussed the one-time pad, obtained by xoring a message stream with a random stream of bits by the sender, and then decrypting by xoring by the receiver by the same random stream of bits. After a while people were convinced that the description was clear and could be done. They also got convinced that the message would be received (A xor B xor B will always be A). I asked about the security, and we had some discussion, in which I tried to convince people that if they could "guess" a plaintext bit while looking at a cryptotext bit, then they would essentially be able to predict a bit of the random bitstream, contradicting the nature of "random".

Then I tried to send a message using the papers I had prepared, but it was done poorly. I had tried to blindly construct (without anyone knowing whether there would be a 0 or a 1) a stream of bits. I had done this by typing two 0's on pieces of paper, and two 1's, putting these papers in a bag, drawing them out at random, and then pasting the two halves in order on different lists. Then I would have had one team xor a a "message" bitstream, announce it publicly, and have another team decode it by xoring again. See [PDF|PS|TeX] and [PDF|PS|TeX]. But it didn't work out too well physically.

I mentioned that for highly secure applications, "natural processes" were used to create random bitstreams, and that then CD's were used to exchange them. I remarked that sending bitstreams like this was very cumbersome but that it is usual to employ older (more dependable?) technology.

I described Venona, a case of Russians spying in the U.S. during the 1940's and 50's (information available at the NSA museum web site). The spies used one-time pads and about 2200 messages were sent. Some (2 or 3%) were deciphered (how is this possible for an "unbreakable" encryption scheme?) and arrests followed. So next week we'll discuss how the one-time pad can be broken in practice.

Previous lecture

Table of contents

Next lecture