Suppose Alice would like to send Bob a message without allowing a malevolent associate Mallory read the message. There is only one way to absolutely ensure 100% security: the use of a one-time pad. We will first start by describing and looking at computer implementations of one-time pads, and we will follow this by looking at stream ciphers, an attempt to simulate the characteristics of one-time pads.

One-time pads

Suppose that Alice has a message stored as a string of $n$ characters. We will call that the plain-text. If Alice creates a second string of $n$ random characters and has previously shared that random string with Bob, then Alice can apply xor to each of the characters. This will encrypt the plain-text producing the cipher-text that can be sent to Bob. We must assume that Mallory is able to intercept the cipher-text while it is in transmission. The following code performs the action of both encrypting and then decrypting the cipher-text to recover the original plain-text:

#include <iostream>
#include <string>
#include <stdexcept>

int main();
void encrypt_decrypt( std::string &text, std::string const &one_time_pad );

void encrypt_decrypt( std::string &text, std::string const &one_time_pad ) {
	if ( text.length() > one_time_pad.length() ) {
		throw std::length_error( "The message is shorter than the one-time pad." );
	}

	for ( size_t k{0}; k < text.length(); ++k ) {
		text[k] ^= one_time_pad[k];
	}
}

int main() {
	std::string msg{"Meet me tonight."};

	// 20 randomly chosen characters based on atmospheric noise
	//   - see https://www.random.org/integers/
	//   - this is a null-character terminated string
	char random_numbers[21]{
		  -5,  32, -36, -120,   -8,  -94,   48,   78,  -99,  -92,
		  25,  79,  29,   59,  -41, -108, -127,  -84,   55,   10,
		   0
	};

	std::string one_time_pad{random_numbers};

	std::cout << msg << std::endl;
	encrypt_decrypt( msg, one_time_pad );
	std::cout << msg << std::endl;
	encrypt_decrypt( msg, one_time_pad );
	std::cout << msg << std::endl;

	return 0;
}

Note that a char is actually a number between -128 and 127, and while printable letters, numbers and symbols constitute only subset of these 256 possible values, the noise must be able to take on all possible values in the range.

When this is executed, the plain-text is converted to the cipher-text and then printed out. The algorithm for extracting the plain-text from the cipher-text is actually the same operation. Recall that while in C++, the caret symbol ^ is used for xor, in mathematical notation, the exclusive or of $x$ and $c$ is represented as $x \veebar c$:

Plain-text $x$	One-time pad $c$	Encrypted cipher-text $x \veebar c$	Decrypted text $(x \veebar c) \veebar c$
0	0	0	0
0	1	1	0
1	1	0	1
1	0	1	1

Note that regardless of the value of the bit from the one-time pad, the second exclusive or correctly recovers the original bit from the plain text.

To demonstrate that the same algorithm that encrypts the message also decrypts it, the decrypted message is generated and printed out.

Meet me tonight.
¶E¹üØÏUnéËw&zS£°
Meet me tonight.

With a different sequence of random values of type char, some of the letters may be non-printable characters such as values from 0 to 31. Instead of printing the cipher-text, it could be written to a file and sent to Bob.

The cipher-text may be transmitted to Bob and even if Mallory obtains this cipher-text, it is impossible for Mallory to decrypt it so long as one-time pad is

• a sequence of characters is truly randomly generated, and
• never used again, ever.

The problem with one-time pads is that Alice must distribute the one-time pads string to Bob prior to Bob receiving the message. Then, Alice and Bob should destroy the one-time pad string once it is used. If Bob looses his string, it is impossible for him to decrypt the message.

During the Great Patriotic War, Soviet agents used one-time pads; however, due to the high demand, duplicate pads were produced allowing Allied forces to decrypt some Soviet communications through the Venona project.

Why are one-time pads cryptographically secure?

Each bit of the message is encrpyted by, and affected by, exactly one bit in the one-time pad. Thus, we really only have to ask one question: if you choose 0 or 1, and I flip a coin and if the coin ends up heads, you tell everyone the number you choose; and if the coin ends up tails, you tell everyone the other number.

Now that everyone knows what you publicly announced, can anyone guess with a greater than 50% chance of correctly deducing which number you actually picked, as opposed to which number you announced? Certainly not, because there is no other information available to help.

In the same way, the random number is adding a coin toss to the value of every single bit, so anyone examining the cipher-text will have no idea what any of the values of the bits are.

Now, while coin tosses are essentially random, they can only produce bits at a rate of $0.25\ {\rm Hz}$, which isn't very fast. Faster techniques are available, including the use of radioactive decay and phenomenon as atmospheric noise.

Stream ciphers

A stream cipher simulates a one-time pad by having pseudo-random number generator simulate the output of a one-time pad. We describe such a generator as pseudo-random because we will see that it only has the appearance, at first glance, to creating a sequence of random numbers. The state of the generator is initialized with a shared unsigned integer or key.

This first example uses the pseudo-random number generator rand() from the C standard library. This function produces a deterministic sequence of pseudo-random numbers where the next number in the sequence depends on the previous. If you were to write a program that printed the output of rand() ten times, you will see that every time you run this, you get exactly the same random numbers. This ensures that the pseudo-random numbers are repeatable. If you want a different sequence of random numbers, you must provide a different seed. This is a positive integer that can be passed to the srand( unsigned int seed ) function.

For this example, we will use srand(...) where the key to our encryption becomes the seed passed to that function:

#include <iostream>
#include <string>

void stream_cipher( std::string &text, unsigned int key );
int main();

void stream_cipher( std::string &text, unsigned int key ) {
	// Use the 'key' to seed the random number generator
	srand( key );

	// XOR each character in the string with the next random number
	for ( size_t k{0}; k < text.length(); ++k ) {
		text[k] ^= (char)rand();
	}
}

int main() {
	std::string msg{"Meet me tonight."};

	std::cout << msg << std::endl;
	stream_cipher( msg, 5235395 );
	std::cout << msg << std::endl;
	stream_cipher( msg, 5235395 );
	std::cout << msg << std::endl;

	return 0;
}

The output of this stream cipher is:

Meet me tonight.
È*TÓ]z|'6o®+l`áô
Meet me tonight.

Now, if Alice and Bob have previously shared the key value of $5235395$, they can send as long a string as they wish; however, they should not use the same key twice; alternatively, if they were somehow to continue off from when rand() was last called, it would be possible to continue using this stream cipher. A cipher that allows you to continue where you left off is said to be reentrant. Unfortunately, rand() is not reentrant: if given a seed s, you called rand() $23$ times, then if you wanted to carry on, you would have to reuse the same key, call rand() $23$ times, and then continue using it from that point on.

Cryptographically secure stream ciphers

Unfortunately, a more important issue is that rand() is not a cryptographically secure random number generator. What this means is that there are subtle non-random patterns that appear, and expert cryptographers can exploit this non-randomness. Thus, it is more correct to say that rand(..) produces a pseudo-random sequence of numbers.

If you want to implement your own stream cipher, consider reading about linear-feedback shift registers. This is a class of pseudo-random number generators which is reasonably secure for shorter messages, although they are only ever pseudo-random, and thus always subject to attack.

More on one-time pads

We are using bits to represent both the characters and the random information that is xored with the characters. This is, of course, not how it was previously done during the Cold War. Instead, spies and embassies were given books of random letters together with a translation key:

The message itself would be reduced to just capital letters without spaces or punctuation, so our message above would be MEETMETONIGHT. Next, we would start with the first random letter K. This would specify the translation between the plain-text and the cipher-text, so for K, A would be coded as P, B as O, C as N, and so on. In this case, M would be encrypted as D:

To encrypt the next letter, we go to the next random letter O, and here we see that E is to be encrypted as H:

We can repeat this process with the next eleven random letters and thus the entire message would be encrypted as follows:

and thus the cipher-text is DHRVZVYWIMMZK. Alice would send this to Bob, and Bob using the same one-time pad to decrypt the cipher-text. By the way, there is one error in this encryption; can you find it?