430
Relations, Functions, and Matrices
• Running bit strings through permutation functions f (i) = j such that the
new bit value at position i in the string is the old bit value at position j
• Combining bit strings from the plaintext and the key using a bitwise
exclusive-ORoperation ! (two 0s or two 1s result in a 0 bit, while a single
0 and a single 1 result in a 1 bit)
• Changing the key by splitting the bit string in half and performing a circular left shift on each half of 1 bit or 2 bits, depending on the round number
It’s easy to look at a bit string and see informally what the result of a circular
left shift will be. But, as in the case of the Caesar cipher, we’d like to put the shift
on a mathematical (algorithmic) footing, and the mod function comes into play.
example 53
Consider a 5-bit binary string x, such as 11010. A 1-bit circular left shift of x would
involve moving bits as follows—
1
1
0
1
0
—resulting in
1
0
1
0
1
Thinking of 11010 as a binary number, each column represents a power of 2, as
opposed to the powers of 10 that our decimal numbers represent. The decimal
equivalent of x = 11010 is therefore
1 # 2
4
+ 1 # 2
3
+ 0 # 2
2
+ 1 # 2
1
+ 0 # 2
0
= 16 + 8 + 2 = 26
and the decimal equivalent of y = 10101 is 16 + 4 + 1 = 21.
To mathematically compute y from x, we can carry out the following steps.
While all steps are done on binary strings, we will also show the decimal equivalents. Multiplication of a binary string by 2 moves the digits one column to the left,
padding the rightmost column with 0; multiplication by 2
−4
moves the digits four
columns to the right, padding the four leftmost columns with 0, just as happens
when multiplying a decimal number by 10 or by 10
−4
, respectively.
binary
Decimal
x = 11010
26
let p = x mod 2
4
= 01010
10 (26 mod 16)
let q = p # 2 = 10100
20
let s = x ! p = 10000
16
let t = s # 2
−4
= 00001
1
let y = q + t = 10101
21