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

Careful planning is necessary to ensure that a tagging scheme will work properly; that is,
will not cause confusion on the receiving end. We will soon discuss a type of tagging which
is most often employed with Rabin cipher implementations.

We actually have been rather presumptuous throughout this chapter, and we should cor-
rect this now. The Rabin cipher says both primes + 3. A nat-

ural question to ask now is, “OK, we know there are infinitely many primes, but are there
infinitely many primes of the form 4

p and q must be of the form 4 k

+ 3?” This is important because we must be able to
freely select such primes for this cipher. But what if such primes eventually “run out,” and
we are left only with primes of the form 4

k

k + 1? The next result assures us that this does not

happen.

PROPOSITION 33 There are infinitely many primes of the form 4 k + 3.

Proof. First note that if we have any two integers both of the form 4 k + 1, their product

is also of the form 4 + 1 we have

mn = (4 j + 1)(4 i + 1) = 16 ji + 4 i + 4 j + 1 = 4(4 ji + i + j ) + 1. (*)
Hence, mn is also of the form 4 k + 1 (where k here is equal to 4 ji + i + j ). Given this, we
now assume there are finitely many primes congruent to 3 modulo 4. Thus, we can list them
in a finite sequence starting with the smallest prime congruent to 3 modulo 4, and pro-
gressing through them in order to the largest, say p 0 = 3, p 1 = 7, p 2 = 11, . . . , p n . Now, con-
sider the integer

k + 1, since if m = 4 j + 1 and n = 4 i

N p 1 p 2 ... p n + 3

= 4

which must contain a prime factor of the form 4 k + 3, for if not, its prime factors would all be

congruent to 1 modulo 4, and hence their product N would also be congruent to 1 modulo 4, a

contradiction. However, now note that 3

N

; for if 3| N, we also have 3|( N 3) = 4 p 1 p 2 ... p n ,

another contradiction (since p 0 = 3 does not appear in the sequence 4 p 1 p 2 ... p n ). Likewise, none

of the other primes p i (1

≤ i ≤ n

) divides N , since if we have some p i | N , we then also have p i |( N

4 p 1 p 2 ... p n ) = 3, which is ridiculous because all of the primes p i ( i = 1, 2, . . . , n ) are larger

than 3. Since no prime of the form 4 must

have such a prime as a factor, we can only conclude that our assumption is incorrect. There must
be infinitely many primes congruent to 3 modulo 4.

k + 3 in the list p 1 , p 2 , . . . , p n can divide N , and N

10.2

WEAKNESSES OF THE RABIN CIPHER
The Rabin cipher is quite secure, provided the proper precautions are taken. (Of course, the
necessity of taking the proper precautions is true of any cipher.) As presented here, the Rabin
cipher has certain weaknesses which can be exploited. We describe these weaknesses below.

Chosen Ciphertext Attack A chosen ciphertext attack is when an adversary has

the ability to pass a single ciphertext message (of his choice) through an individual's
decryption machine. The adversary may even have access to the decryption machine