Mini-Blowfish
---- --------
The Blowfish algorithm has become a popular encryption
algorithm for data streams and large files, as it can
be efficiently implemented in software. In this problem
you are asked to code and test a miniature version of
this algorithm, which we call Mini-Blowfish, or MB for
short.
Description of MB:
----------- -- --
MB uses an 18+256 byte vector of `subkeys'. The first
18 of these are referred to as P[1] through P[18]. The
next 256 are referred to as S[0] through S[255]. The
18+256 subkeys are collectively referred to as K[1]
through K[18+256], so K[1] == P[1], K[18] == P[18],
K[19] == S[0], K[18+256] == S[255].
The S values define a `substitution-box', or S-box, that
takes a byte B as input and returns the byte S[B] as
output, where bytes are viewed as unsigned integers from
0 through 255. E.g., if B == 5 the S-box returns S[5].
The data encryption algorithm inputs and outputs 16 bit
blocks. These are divided into a high order byte, HB,
and a low order byte LB, so block B == 256 * HB + LB.
The encryption algorithm is:
Input B = 256 * HB + LB.
For round R = 1 though 16:
HB = HB xor P[R].
LB = LB xor S[HB].
swap HB and LB.
Finishing:
swap HB and LB (undo the round 16 swap).
LB = LB xor P[17];
HB = HB xor P[18];
Output B = 256 * HB + LB.
Note that P[1], ..., P[18] are accessed in order by the
encryption algorithm. Decryption uses the same algori-
thm except that P[1], ..., P[18] are used in the reverse
order (P[18] is used in round 1 and P[1] is xor'ed at
the end into HB).
The main idea in Blowfish is the method of computing the
subkeys. In fact, the idea is to have a lot of subkeys
(full Blowfish as 1042 32-bit subkeys). Computing the
subkeys takes a long time, so changing the key in MB or
Blowfish is slow, and has been made so in order to have
a secure algorithm in which encrypting the data given
the subkeys is fast.
To initialize the subkey vector K[1], ..., K[18+256] you
need as input a password, which is any string of
characters. Let the bytes of the password be W[1],
W[2], ..., W[N] where N is the length of the password.
The MB subkey computation algorithm is then:
Input W[1], ..., W[N].
For i from 1 through 18+256:
K[i] = 7 ** i mod 256;
For i from 1 through N:
K[i] = K[i] xor W[i];
Set B = 0, a 16 bit value.
For round Q from 1 through (18 + 256)/2:
Encrypt B to obtain Encrypted-B
Set B = Encrypted-B
Let B = 256 * HB + LB as above.
Set K[2*Q-1] = HB and K[2*Q] = LB.
Output K[1], ..., K[18+256].
Note that the output B of the encryption in round Q be-
comes the input B to the encryption in round Q+1. Also
the subkeys at the end of round Q are the subkeys used
in the encryption in round Q+1. Thus B and the subkeys
keep changing as Q advances. The subkeys at the end of
round Q = (18+256)/2 are the final output of the subkey
computation algorithm.
Input
-----
Lines each of which contains a password and some inte-
gers to be encrypted using the password, all followed
by the integer -1 (which is NOT to be encrypted). These
are separated from each other by whitespace. No line is
longer than 80 characters.
The password is a string of one or more letters and
digits, each interpreted as a byte equal to the ASCII
code of the letter or digit (ASCII codes are the codes
used to represent characters as integers in modern
computers, and all ASCII codes are between 0 and 127).
The integers to be encrypted are all in the range from 0
through 65535 (= 2**16 - 1), and each integer represents
a 16 bit block.
Input ends with an end of file.
Output
------
For each input line, one output line, in the same format
as the input line, except that each integer to be en-
crypted is replaced by the result of encrypting it.
Sample Input
------ -----
abcdefg 0 1 2 3 4 5 -1
2hotfudge 28647 64826 42873 60872 53872 7648 29640 -1
Sample Output
------ ------
abcdefg 61669 41297 34644 22212 18368 679 -1
2hotfudge 37515 44577 40580 64732 42141 33306 62416 -1
Further Information
------- -----------
Blowfish was invented by Bruce Schneier, and is describ-
ed at
www.schneier.com/paper-blowfish-fse.html
Blowfish is one of a large number of `Feistel ciphers'.
The full algorithm uses 32 bit subkeys, 64 bit blocks,
and 4 S-boxes that are applied to the 4 bytes of a
32-bit half-block to get 4 32-bit half-blocks that are
combined using addition and exclusive-or to make one
32-bit half-block. The subkeys are initially set to
the fractional digits of PI, which are assumed to be
random. Short passwords are extended by cycling through
their bytes. However, like MB full Blowfish also has 16
rounds, 18 P values, and the same control flow as MB.
File: blowfish.txt
Author: Bob Walton
Date: Tue Oct 10 02:26:24 EDT 2006
The authors have placed this file in the public domain;
they make no warranty and accept no liability for this
file.