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

Thus, the decryption machine will return 4 square roots modulo n of C *, say s 1 , s 2 , s 3 ,

s 4 . One of these 4 values will be congruent to zx modulo n , and another will be congruent

to zx modulo n . However, the remaining 2 roots will be congruent to neither zx nor zx

modulo n . Choose one from the latter category, say s i , and compute s i x where x is an

inverse of , and can

be used in the same manner as the chosen ciphertext attack described previously to obtain
a prime factor of

x modulo n . This value s i x is congruent to neither z nor z modulo n

n .

Redundancy One solution to the chosen ciphertext problem and the adaptive chosen
ciphertext problem is to ensure that the decryption machine returns only the correct plain-
text message and withholds the other 3 roots. We can do this by padding with redundancy.
For example, we can pad each block with 8 characters, where these characters are the first
8 characters of that block. Using this, the decryption machine will be able to distinguish the
correct root from the other roots, as (with very high probability) only one root will possess
the required redundancy.
Another form of redundancy is to append a “digest” of each block. A digest, in this case,
is a fixed-size compressed version of the block. See Chapter 16 on cryptographic applica-
tions for more information about message digests/hashes.
Now, if an adversary computes an enciphered message from some random plaintext mes-
sage , giving him no new

information. This is also the case even if he attempts to disguise the message in the manner
described using an adaptive chosen plaintext attack.

z to the decryption machine, it will only return the correct root z

Weak Primes If the primes p and q for the Rabin cipher are not chosen carefully, the
Pollard p 1 method can be used to factor n (see Chapter 12 on factorization techniques).
Specifically, p (also q ) must be chosen so that p 1 does not consist entirely of small fac-
tors.
For example, consider the prime p = 10888869450418352160768000001 = 27! + 1. Then
p 1 = 27!, and so the largest factor of p 1 is 27—a very small integer when compared
to p . The Pollard p 1 method of factorization uses this fact to find the prime p . One solu-
tion to this problem is to choose p so that p = 2 t + 1, where t is prime. Then we have p 1
= 2 t , and so p 1 has a large prime factor, namely t .
For similar reasons, we also want to avoid primes p such that p + 1 consists entirely of
small factors. When we generate primes with the intent of avoiding these weaknesses to
factoring methods, we call such primes strong primes.

10.3 STRONG PRIMES

Definition
A prime number p is said to be a strong prime if integers r , s , and t exist such that:

(a) p 1 has a large prime factor r

(b) p + 1 has a large prime factor s

(c) r 1 has a large prime factor t .