Quadratic Ciphers - Introduction to Cryptography with Java Applets - page 183

The correct root is marked. We decrypt the second block by solving

2 (mod 48010717)

22338920 P

for P . We get the following roots, with the correct one again marked:

P 39784853 (mod 48010717)

P 28879295 (mod 48010717)

P 8225864 (mod 48010717)

→ P 19131422 (mod 48010717).

We solve this third congruence

2 (mod 48010717)

40412478 P

for P to decrypt the third block. The roots we obtain are:

P 36711428 (mod 48010717)

→ P 6040410 (mod 48010717)

P 11299289 (mod 48010717)

P 41970307 (mod 48010717).

You can surely see the problem of deciding between four roots during decryption. In this
case, deciding was easy because of our alphabet (no character

≥ 26). In general, how do we

know which solution for is the correct one? The answer is, if we didn't write the message,

we don't know. The correct root may be any of the four roots, and there is no way of know-
ing in advance which one it will be. This poses a problem for this cryptosystem: What if two
(or more) roots could both be construed as a valid message? One solution may be to tag the
blocks with special character(s) which do not otherwise appear in the messages. For instance,
in our example we use only the characters A = 00 through Z = 25; we could use the num-
ber 26 to tag the beginning of each block, as in:

P

SHOO TNOW GEEK

converts to

28705651 20676817 47296051.

Now, in front of each block, we place the tag, 26:

2628705651 2620676817 2647296051

and encipher this message. Thus, the block size of the enciphered message is greater than
that of the plaintext. This is not a problem; many cipher systems exhibit different plain-
text/ciphertext block sizes. When we decrypt, the tags will reappear, which we then remove
from the message and convert back to characters. Similar tagging schemes can be used for
messages that use ASCII character encoding and Unicode. You should remember that some
messages, however, are not text at all, but may be any type of binary stream whatsoever.