Cryptographic Applications - Introduction to Cryptography with Java Applets - page 327

4. Pad the message x with zeros, if necessary, to make the bitlength of x a perfect multiple

of n /2. Divide x up into t blocks, each of bitlength n /2 ( t may be 1). Add another n /2 bit

block, which is the ( n /2) bit representation of b . We represent this as:

x = x 1 , x 2 , . . . , x t , x t 1 .

Note that each of the blocks is a multiple of 8.

5. For each i from 1 through t , divide x i into 4-bit blocks; insert the bits 1111 before each

4-bit block. This produces an n -bit block, say y i , from each x i . Then divide x t 1 into 4-
bit blocks, but this time, insert the bits 1010 before each 4-bit block. This yields the
expanded message

y = y 1 , y 2 , . . . , y t , y t 1 .

6. Now, to compute the digest. For i from 1 through t + 1 do the following:

F i = lnr of (( H i 1 y i ) OR A) 257 modulo M (where OR means bitwise inclu-

• Compute

sive-or, and represents bitwise exclusive-or).

G i be the n F i .

• Let rightmost bits of

H i = G i H i 1 .

• Compute

7. The digest is H t 1 .

E XAMPLE . We will again use very small numbers. Let the message be x = 45 = 101101
(binary), and so the bitlength b of x is b = 6 = 110 (binary). Let p = 6911 and q = 6947; thus,
M = 48010717 = 10110111001001010111011101 (binary). The bitlength m of M is 26, so
we choose n = 16. The IV (initialization vector) H 0 is 0, and the constant A is
1111000000000000 (binary). We pad the message with zeros so that it is a multiple of 16/2
= 8; that is,

x = 10110100.

Now we divide this up into 8 bit blocks; in this case, there is only one such block ( t = 1).

We append another block, which is the 8-bit representation of b , or 00000110. So, we have

x 1 = 10110100
x 2 = 00000110.
We divide the message up by splitting each block x i (where i ≤ t ) into 4-bit blocks, and
inserting 1111 before each such 4-bit block. For x 1 this yields
y 1 = 1111101111110100.
The last block is split in the same way, but 1010 is inserted before each block. Hence,
for x 2 we have

y 2 = 1010000010100110.

Now, to produce the digest: