Since we are getting more advanced in the C language, I have been working on
a tutorial that covers a more advanced C program: Blowfish.
For those of you who don't know, Blowfish is a symmetric block cipher (an
encryption algorithm with one key) made by Bruce Schneier, a well-respected
cryptographer. It has a 64-bit block size, and a variable key length (up to
448 bits).
I'll go over how Blowfish works so you can get a better understanding of the
code. This is straight from Schneier's book:
" Blowfish is a 64-bit block cipher with a variable-length key. The algorithm
consists of two parts: key expansion and data encryption. Key expansion
converts a key of up to 448 bits into several subkey arrays totaling 4168
bytes.
Data encryption consts of a simple function iterated 16 times. Each round
consists of a key-dependent permutation, and a key- and data-dependent
substitution. All operations are additions and XORs on 32-bit words. The only
additional operations are four indexed array data lookups per round." (What
he means is data is taken from an array)
" Blowfish uses a large number of subkeys. These keys must be precomputed
before any data encryption or decryption."
(Begin my comments)
The array P consists of 18 32-bit subkeys.
Four arrays S consist of 256 entries. (it's a two-dimensional array).
To encrypt, we do the following, assuming that x is a 64-bit plaintext block:
First divide x into two 32-bit blocks, Xl and Xr. (Or X-left and X-right :)
for i = 0 to 15 (16 times):
Xl = Xl XOR P[i];
Xr = Function F(Xl) XOR Xr;
Swap Xl and Xr
After the loop is done, swap Xl and Xr again.
Xr = Xr XOR P[17];
Xl = Xl XOR P[18];
Concatenate Xl and Xr back together (Remember our left and right? :)
This is function F, which is a BIT confusing, because of inconsistancies in
Schneier's explanation and Schneier's code:
Divide Xl into 4 8-bit quarters: a, b, c, and d.
((S1[a] + S2[b] mod 2(exp)32) XOR S3[c]) + S4[d] mod 2(exp)32;
A bit confusing, no? However, unless mod does not mean modulus, here's what
Schneier's code says instead:
((S1[a] + S2[b]) XOR S3[c]) + S4[d]
No modulus at all in there. Maybe the book has an errata list I can check
somewhere, I'll look at it later.
Here is the challenge for you all right now: write a function or macro for
function F. Assume the 4 S arrays are global variables. It will be
interesting to see how you split the 32-bit block into four 8-bit blocks.
Lastly, this is how subkey generation works (from the book again). Things in
parenthesis are notes from me:
"
(1) Initialize first the P-array and then the four S-boxes (the 4 S arrays),
in order, with a fixed string. This string consts of the hexadecimal digits
of pi.
(2) XOR P1 with the first 32 bits of the key, XOR p2 with the second 32 bits
of the key, and so on for all bits of the key (up to P18). Repeatedly cycle
through the key bits until the entire P-array has been XORed with key bits
(This is how it takes a variable-length key)
(3) Encrypt the all-zero string (bad English! Guess he didn't have a
proofreader) with the Blowfish algorithm, using the subkeys described in
steps (1) and (2). (Right now, the S-arrays are some of the hexadecimal
digits of pi, so remember, function F will still work, even though they
haven't really been "initialized" yet)
(4) Replace P1 and P2 with the output of step (3).
(5) Encrypt the output of step (3) using the blowfish algorithm with the
modified subkeys
(6) Replace P3 and P4 with the output of step (5).
(7) Continue the process, replacing all elements of the P-array, and then all
four S-boxes in order, with the output of the continuously changing Blowfish
algorithm.
"
I will follow up this post with the tutorial soon, right now I am just
cleaning up Schneier's code (which has given me a new respect to writing
stuff cleanly). In the mean time, let me see the answers to that challenge :)
Morgon
--
grab my updated (12/21/02) public key from http://www.surgo.net/pubkey.asc
a tutorial that covers a more advanced C program: Blowfish.
For those of you who don't know, Blowfish is a symmetric block cipher (an
encryption algorithm with one key) made by Bruce Schneier, a well-respected
cryptographer. It has a 64-bit block size, and a variable key length (up to
448 bits).
I'll go over how Blowfish works so you can get a better understanding of the
code. This is straight from Schneier's book:
" Blowfish is a 64-bit block cipher with a variable-length key. The algorithm
consists of two parts: key expansion and data encryption. Key expansion
converts a key of up to 448 bits into several subkey arrays totaling 4168
bytes.
Data encryption consts of a simple function iterated 16 times. Each round
consists of a key-dependent permutation, and a key- and data-dependent
substitution. All operations are additions and XORs on 32-bit words. The only
additional operations are four indexed array data lookups per round." (What
he means is data is taken from an array)
" Blowfish uses a large number of subkeys. These keys must be precomputed
before any data encryption or decryption."
(Begin my comments)
The array P consists of 18 32-bit subkeys.
Four arrays S consist of 256 entries. (it's a two-dimensional array).
To encrypt, we do the following, assuming that x is a 64-bit plaintext block:
First divide x into two 32-bit blocks, Xl and Xr. (Or X-left and X-right :)
for i = 0 to 15 (16 times):
Xl = Xl XOR P[i];
Xr = Function F(Xl) XOR Xr;
Swap Xl and Xr
After the loop is done, swap Xl and Xr again.
Xr = Xr XOR P[17];
Xl = Xl XOR P[18];
Concatenate Xl and Xr back together (Remember our left and right? :)
This is function F, which is a BIT confusing, because of inconsistancies in
Schneier's explanation and Schneier's code:
Divide Xl into 4 8-bit quarters: a, b, c, and d.
((S1[a] + S2[b] mod 2(exp)32) XOR S3[c]) + S4[d] mod 2(exp)32;
A bit confusing, no? However, unless mod does not mean modulus, here's what
Schneier's code says instead:
((S1[a] + S2[b]) XOR S3[c]) + S4[d]
No modulus at all in there. Maybe the book has an errata list I can check
somewhere, I'll look at it later.
Here is the challenge for you all right now: write a function or macro for
function F. Assume the 4 S arrays are global variables. It will be
interesting to see how you split the 32-bit block into four 8-bit blocks.
Lastly, this is how subkey generation works (from the book again). Things in
parenthesis are notes from me:
"
(1) Initialize first the P-array and then the four S-boxes (the 4 S arrays),
in order, with a fixed string. This string consts of the hexadecimal digits
of pi.
(2) XOR P1 with the first 32 bits of the key, XOR p2 with the second 32 bits
of the key, and so on for all bits of the key (up to P18). Repeatedly cycle
through the key bits until the entire P-array has been XORed with key bits
(This is how it takes a variable-length key)
(3) Encrypt the all-zero string (bad English! Guess he didn't have a
proofreader) with the Blowfish algorithm, using the subkeys described in
steps (1) and (2). (Right now, the S-arrays are some of the hexadecimal
digits of pi, so remember, function F will still work, even though they
haven't really been "initialized" yet)
(4) Replace P1 and P2 with the output of step (3).
(5) Encrypt the output of step (3) using the blowfish algorithm with the
modified subkeys
(6) Replace P3 and P4 with the output of step (5).
(7) Continue the process, replacing all elements of the P-array, and then all
four S-boxes in order, with the output of the continuously changing Blowfish
algorithm.
"
I will follow up this post with the tutorial soon, right now I am just
cleaning up Schneier's code (which has given me a new respect to writing
stuff cleanly). In the mean time, let me see the answers to that challenge :)
Morgon
--
grab my updated (12/21/02) public key from http://www.surgo.net/pubkey.asc