|COS 126: Spring 1997 |
|Due: Wed. 2/26, 11:59pm|
For this assignment, you'll write a program,
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 0000014
scrambles the input "
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 "
for more information about
If the input is already encrypted, running through scramble decrypts, or unscrambles, it:
% echo Hello world | a.out | a.out Hello world
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
Deitel and Deitel, Sec. 8.5).
the input has been exhausted. Note that getchar returns an int, not a
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
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 "
as shown above, and on the file
/u/cs126/data/secret. That is, run
% 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
scramble.c must define and
use three functions in addition to
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
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.