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

645782153478215784521784587216547821547264765686587157161289768792648947
56345234.

A remedy to this problem, called salt, is described shortly.

Forward Search Attack This attack is useful when the number of possible messages
is small or predictable in some way. If this is the case, an adversary simply needs to encrypt
all suspected messages (using public information) until a result is obtained that matches
some ciphertext.

10.4 SALT

Salt simply refers to adding random data to the end of each block. This helps solve certain
problems; in the case of the Rabin cipher, it certainly foils the forward search attack, as the
messages are no longer predictable. It also solves the square root problem for small mes-
sages, if enough salt is used. To solve the square root problem posed by using the Chinese
Remainder Theorem, we simply salt each block of each message differently (randomly)
every time the message is sent. Thus, no 2 entities will receive the same message because
of the random data tagged on the end. One who has the decrypting keys knows how much
salt has been added (this is agreed on beforehand), and so removes it after decryption. At
current levels of computing power, at least 64 bits of salt should be used (per block).

E XAMPLE . To foil a small message attack, we will add some salt to the small message in the
previous example. We will encipher using the same modulus.
P

=
239018479210648921764876589475621934521754012450100521345271645216354721
645782153478215784521784587216547821547264765686587157161289768792648947
56345234

3204985729038750923487509238750932759063428568293658792658926502
345732904573029875903245790234592437590279023457902709270927908270927309
827032198749812648917264891276489127648912764982136489721634897126984621
8946

.

By applying the enciphering transformation, we now obtain the ciphertext

2

P C

362553151149932290693370397428556816309612860797213471999021301363970532
507759737177005742323020709244386843096963830437628218686278812350788061
965619398198903437544832410128148805922800361293406046652128918390329775
694836555904101302789331938629983720911345280340650671106530527991109007
492490780768265310413373267274165164009328331195722273832191470040406895
818936053712468645971674045864005833135144807356844179852541177298341854
811520524357320450008042254589982743442715951668881225417413416712356390
000533491929103491130866508303679188401345886873831467662712090878394709
91344857388135329931312052597944482054859 (mod

n ).