Cryptography: Theory and Practice:The RSA System and Factoring | Modern Cryptography: Theory and Practice

Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210 Pub Date: 03/17/95

Table of Contents

Example 4.13

Let’s illustrate the encryption and decryption procedures for the Rabin Cryptosystem with a toy example. Suppose n = 77 = 7 × 11 and B = 9. Then the encryption function is

and the decryption function is

Suppose Bob wants to decrypt the ciphertext y = 22. It is first necessary to find the square roots of 23 modulo 7 and modulo 11. Since 7 and 11 are both congruent to 3 modulo 4, we use our formula:

Figure 4.14 Factoring a Rabin modulus, given a decryption oracle

and

Using the Chinese remainder theorem, we compute the four square roots of 23 modulo 77 to be ±10, ±32 mod 77. Finally, the four possible plaintexts are:

It can be verified that each of these plaintexts encrypts to the ciphertext 22.

We now discuss the security of the Rabin Cryptosystem. We will prove that any hypothetical decryption algorithm A can be used as an oracle in a Las Vegas algorithm that factors the modulus n with probability at least 1/2. This algorithm is depicted in Figure 4.14.

There are several points of explanation needed. First, observe that

so a value x will be returned in step 3. Next, we look at step 4 and note that (mod n). It follows that x₁ ≡ ±r (mod n) or x₁ ≡ ±ωr (mod n), where ω is one of the non-trivial square roots of 1 modulo n. In the second case, we have

but n does not divide either factor on the right side. Hence, computation of gcd(x₁ + r, n) (or gcd(x₁ - r, n)) must yield either p or q, and the factorization of n is accomplished.

Let’s compute the probability of success of this algorithm, over all n - 1 choices for the random value r. For two non-zero residues r₁ and r₂, define

It is easy to see that r ~ r for all r; r₁ ~ r₂ implies r₂ ~ r₁; and r₁ ~ r₂ and r₂ ~ r₃ together imply r₁ ~ r₃. This says that the relation ~ is an equivalence relation. The equivalence classes of all have cardinality four: the equivalence class containing r is the set

where ω is a non-trivial square root of 1 modulo n.

In the algorithm presented in Figure 4.14, any two values r in the same equivalence class will yield the same value y. Now consider the value x returned by the oracle A when given y. We have

If r = ±y, then the algorithm fails; while it succeeds if r = ±ωy. Since r is chosen at random, it is equally likely to be any of these four possible values. We conclude that the probability of success of the algorithm is 1/2.

It is interesting that the Rabin Cryptosystem is provably secure against a chosen plaintext attack. However, the system is completely insecure against a chosen ciphertext attack. In fact the algorithm in Figure 4.14, that we used to prove security against a chosen plaintext attack, also can be used to break the Rabin Cryptosystem in a chosen ciphertext attack! In the chosen ciphertext attack, the oracle A is replaced by Bob’s decryption algorithm.

4.8 Factoring Algorithms

There is a huge amount of literature on factoring algorithms, and a careful treatment would require more pages than we have in this book. We will just try to give a brief overview here, including an informal discussion of the best current factoring algorithms and their use in practice. The three algorithms that are most effective on very large numbers are the quadratic sieve, the elliptic curve algorithm and the number field sieve. Other well-known algorithms that were precursors include Pollard’s rho-method and p - 1 algorithm, Williams’ p + 1 algorithm, the continued fraction algorithm, and of course, trial division.

Throughout this section, we suppose that the integer n that we wish to factor is odd. Trial division consists of dividing n by every odd integer up to . If n < 10¹², say, this is a perfectly reasonable factorization method, but for larger n we generally need to use more sophisticated techniques.

Figure 4.15 The p - 1 factoring algorithm

Table of Contents