Linear Ciphers - Introduction to Cryptography with Java Applets - page 116

First, regroup the letters into blocks of size four,

HOWD YDOO

and convert each letter into its numerical equivalent, grouping the digits together to form a
large integer. Each character gets two digits; A = 00, B = 01, and so on. Leading zeros are
significant.

07142203 24031414

Note that the largest integer which can appear in a block of size four in the ordinary
alphabet is ZZZZ = 25252525. Thus, we will choose 25252526 as our modulus. To construct
an affine cipher mapping,

C mP + b (mod 25252526)

we choose any shift b between 1 and 25252525, and any multiplier m relatively prime to
25252526. Say we choose b = 23210025 and m = 21035433. (Verify that this choice of m
is relatively prime to 25252526.) We use these values to map each block to another. For the
first block we get

C 21035433 7142203 + 23210025 = 150239355888924 8007496 (mod 25252526)

and for the second we compute

C 21035433 24031414 + 23210025 = 505511222302287 20470469 (mod
25252526).

This gives us the enciphered message

08007496 20470469

and this is the message that is sent. Note that no digit pair greater than 25 has an equivalent
in the ordinary alphabet, and the digit pairs 74, 96, 47, and 69 all appear in the above mes-
sage. (Now you can see why we took 00, 01, . . . , 99 as our alphabet.) Note that if there are
less than eight digits in the block, we add leading zeros. To decrypt, we must find an inverse
modulo 25252526 of m = 21035433. A quick computation with the extended Euclidean
algorithm reveals m = 5174971. Using this value and the congruence

P m ( C b ) (mod n )

we can convert the first enciphered block back to its plaintext form,

P 5174971(8007496 23210025) 7142203 (mod 25252526)

and then the second

P 5174971(20470469 23210025) 24031414 (mod 25252526)

which returns us to our plaintext message

HOWD YDOO