COS 126: Spring 1997
Due: Wed. 2/26, 11:59pm

For this assignment, you'll write a program, scramble.c, that encrypts or decrypts its input. Using a key, scramble writes a scrambled rendition of the standard input to the standard output. For example,

% lcc scramble.c
% echo Hello world | a.out | od -c
0000000   c   Z   > 007 222 212   V   @   p 266   %   a

scrambles the input "Hello world\n". The vertical bars mean "pipe the output of the previous command to the input of the next one." Thus, the output of "echo Hello world" (that is, the text "Hello world") is made to be the input of a.out. The output of a.out (that is, the scrambled text) is displayed with od, because it's gobblygook; it almost certainly contains nonprintable characters. As illustrated in the output above, od ("octal dump") displays such characters by printing their codes in octal. The 0000000 and 0000014 are the byte offsets for the first characters in the output lines; these values are not part of scramble's output. Do a "man od" for more information about od.

If the input is already encrypted, running through scramble decrypts, or unscrambles, it:

% echo Hello world | a.out | a.out
Hello world

Writing scamble.c involves using arrays, character input/output, modular arithmetic, and bitwise operators. Also, as detailed below, you'll write three functions that manipulate arrays.

First, here's how scramble scrambles its input. It uses a 256-element array, S, that holds a permutation of the integers 0 to 255. It reads the input a character at a time and uses an element of S to scramble each character. It also rearranges S as it reads the input. Here's pseudocode for this algorithm. (Pseudocode is explained in Deitel and Deitel, Sec. 3.1).

i <- 0, j <- 0
for each character c in the input:
i <- (i + 1) mod 256
j <- (j + Si) mod 256
exchange Si and Sj
k <- (Si + Sj) mod 256
output c xor Sk

The expressions involving "mod" denote modular arithmetic, e.g., (i+1) mod 256 denotes the remainder of i+1 divided by 256, which is an integer in the range 0 to 255 inclusive. The expression c xor Sk denotes the "exclusive OR" operation; see Deitel and Deitel, Sec. 10.9. You must write a function that implements this algorithm; it should take S as an argument, read characters from the standard input, and write the scrambled characters to the standard output. Reading and writing characters one at a time is easy: Use getchar and putchar (see Deitel and Deitel, Sec. 8.5). Hint: When getchar returns EOF, the input has been exhausted. Note that getchar returns an int, not a char, because EOF is not a character.

You must also write a function that takes S and two indices as arguments and exchanges those elements in S.

The following algorithm initializes the array S, given an array K, called the key.

for i <- 0 to 255 do Si <- i
j <- 0
for i <- 0 to 255:
j <- (j + Si + Ki) mod 256
exchange Si and Sj

S has 256 elements, but K may have fewer, so the elements of K are doled out repeatedly from the beginning as often as is necessary to initialize S. You must write a function that takes S and K as arguments and initializes S. This function should call the exchange function described above to rearrange S. Initialize the elements of K in your main function to 0x7A, 0x85, 0x0E, 0x9F, and 0x16.

Test your program on small inputs, like "Hello world\n", as shown above, and on the file /u/cs126/data/secret. That is, run the command

% a.out </u/cs126/data/secret

It will be obvious from the output whether or not your program is working properly!

Turn in your program and your documentation with the command

/u/cs126/bin/submit 3 readme scramble.c

Reminder: Your scramble.c must define and use three functions in addition to main:

  1. A function that takes S and K as arguments and initializes S.
  2. A function that takes S and two indices and exchanges those elements in S.
  3. A function that takes S and writes the scrambled version of the standard input on the standard output.

Extra Credit

Peek ahead to Lecture 6 and learn about command-line arguments (argv and argc). Then make your scramble.c take an optional, variable-length hexadecimal key from the command line. Thus

% a.out 7A 85 0E 9F 16 </u/cs126/data/secret

uses the default key to reveal the message in /u/cs126/data/secret. If there are no arguments, use the default key.

B. Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C, 2nd ed., Wiley, 1996, Chap. 17.

Copyright © 1996 David R. Hanson /
$Revision: 1.6 $ $Date: 1996/09/26 11:04:47 $