A.2 Cryptographic Routines

This section shows implementations of some simple cryptographic algorithms mentioned in Chapter 3. Two implementations of the Extended Euclidean Algorithm, which is used to find inverses in Z_p, are also shown.

Be aware that these implementations are intended to illustrate the principles involved and are definitely not meant to be used in real cryptographic software. As we've seen throughout the text, writing robust security software is difficult and requires special diligence to avoid potential exploits. Unfortunately, writing robust security software involves details that obscure the underlying principles the examples are intended to illustrate, so the examples were chosen to favor simplicity over robustness.

A Trivial Cipher

This subsection shows a python implementation (Figure A.1) of the trivial cipher that we saw in Chapter 3. As mentioned there, this cipher is useful only as an example of what not to do.

Figure A.1. An Implementation of the Trivial Cipher

[View full size image]

23
The tohex function uses the python join/map idiom to return a string of bytes as colon-delimited hex digits.
45
These lines retrieve the key and message from the command line.
6
We empty ct, the string that will hold the ciphertext.
912
We initialize the key stream generator by capturing the length of the key and setting the index into the key to -1.
1318
The next function returns the next byte of the keythat is, of the key streamby incrementing the index and resetting it to 0 if it exceeds the key length.
19
This line constructs an instance, ks, of the key stream generator.
2021
These lines take each byte of the message, exclusive-OR it with the next key stream byte, and append the result to the ciphertext string.
22
This line prints the encrypted message.

An RC4 Implementation

Figure A.2 shows a python implementation of RC4 written to act as a filter. Notice that it is only barely more complicated than the trivial cipher.

Figure A.2. An Implementation of RC4

[View full size image]

5
We obtain the key from the command line. Because this application functions as a filter, it will read the plaintext from STDIN and write the ciphertext to STDOUT.
817
These lines initialize the RC4 state exactly as described in Chapter 3.
1821
The swap function merely swaps S_i and S_j.
2227
The next function returns the next byte of the key stream. It follows the pseudocode from Chapter 3 very closely.
28
We instantiate an instance, ks, of the key stream generator.
2930
These lines continuously read bytes from STDIN, exclusive-OR them with the next byte from the key stream generator, and write the result to STDOUT.

Finding Inverses in Z_p

Recall from Chapter 3 that the RSA algorithm requires us to find an inverse for x Z_p. That is, given x {0, 1, . . . , p - 1}, where p is prime, find y such that xy mod p = 1. Because x and p are obviously relatively prime for prime p, their greatest common denominator is 1. That is, 1 is the largest integer that divides them both. We can use the Extended Euclidean Algorithm to find m and n such that mx + np = gcd(x, p) = 1. Note that this implies that mx mod p = 1.

We present two implementations of this algorithm: one using the UNIX bc utility and the other using python. Both implementations are based on Algorithm X from Section 4.5.2 of [Knuth 1998].

Our first implementation (Figure A.3) uses bc. Normally, bc is used interactively, but it can also accept input from a script. See Knuth for an explanation of this algorithm and a proof that it is correct.

Figure A.3. A `bc`-Based Implementation of the Extended Euclidean Algorithm

[View full size image]

Figure A.4 gives a slightly more readable python-based implementation.

Figure A.4. A `python`-Based Implementation of the Extended Euclidean Algorithm

[View full size image]