Let us write

where p₁ is odd, and

where q₁ is odd. Since

we have that

Hence

and

Now, the condition (p - 1) | [ur becomes 2ⁱp₁ | ur. Since p₁ | r and r is odd, it is necessary and sufficient that 2ⁱ | u. Hence, u = k2ⁱ, 0 ≤ k ≤ p₁ - 1, and the number of solutions to the congruence w^r ≡ 1 (mod p) is p₁.

By an identical argument, the congruence w^r ≡ 1 (mod q) has exactly q1 solutions. We can combine any solution modulo p with any solution modulo q to obtain a unique solution modulo n, using the Chinese remainder theorem. Consequently, the number of solutions to the congruence w^r ≡ (mod n) is p₁q₁.

The next step is to consider a congruence (mod n) for a fixed value t (where 0 ≤ t ≤ s - 1). Again, we first look at the congruence modulo p and then modulo q (note that (mod n) if and only if (mod p) and (mod q). First, consider (mod p). Writing w = g^u, as above, we get

Since g^(p-1)/2 ≡ -1 (mod p), we have that

Since p - 1 = 2ⁱp₁, we get

Taking out a common factor of p₁, this becomes

Now, if t ≥ i, then there can be no solutions since 2ⁱ⁺¹ | 2^t+1 but . On the other hand, if t ≤ i - 1, then u is a solution if and only if u is an odd multiple of 2^i-t-1 (note that r/p₁ is an odd integer). So, the number of solutions in this case is

By similar reasoning, the congruence (mod q) has no solutions if t ≥ j, and 2^tq₁ solutions if t ≤ j - 1. Using the Chinese remainder theorem, we see that the number of solutions of (mod n) is

Now, t can range from 0 to s - 1. Without loss of generality, suppose i ≤ j; then the number of solutions is 0 if t ≥ i. The total number of “bad” choices for w is at most

Recall that p - 1 = 2ⁱp₁ and q - 1 = 2^jq₁. Now, j ≥ i ≥ 1 so p₁q₁ < n/4. We also have that

Hence, we obtain

Since at most (n - 1)/2 choices for w are “bad,” it follows that at least (n - 1)/2 choices are “good” and hence the probability of success of the algorithm is at least 1/2.

4.6.2 Partial Information Concerning Plaintext Bits

The other result we will discuss concerns partial information about the plaintext that might be “leaked” by an RSA encryption. Two examples of partial information that we consider are the following:

1.  given y = e_K(x), compute parity(y), where parity(y) denotes the low-order bit of x

2.  given y = e_K(x), compute half(y), where half(y) = 0 if 0 ≤ x < n/2 and half(y) = 1 if n/2 < x ≤ n - 1.

We will prove that, given y = e_K(x), any algorithm that computes parity(y) or half(y) can be used as an oracle to construct an algorithm that computes the plaintext x. What this means is that, given a ciphertext, computing the low-order bit of the plaintext is polynomially equivalent to determining the whole plaintext!

First, we prove that computing parity(y) is polynomially equivalent to computing half(y). This follows from the following two easily proved identities (see the exercises):

and from the multiplicative rule e_K(x₁)e_K(x₂) = e_K (x₁x₂).

We will show how to compute x = d_K(y), given a hypothetical algorithm (oracle) which computes half(y). The algorithm is presented in Figure 4.11. In steps 2-4, we compute

for 0 ≤ i ≤ log₂ n. We observe that

and so on. Hence, we can find x by a binary search technique, which is done in steps 7-11. Here is a small example to illustrate.

Figure 4.11  Decrypting RSA ciphertext, given an oracle for computing half(y)

Example 4.12

Suppose n = 1457, b = 779, and we have a ciphertext y = 722. e_K(2) is computed to be 946. Suppose, using our oracle for half, that we obtain the following values y_i in step 3 of the algorithm:

Then the binary search proceeds as shown in Figure 4.12. Hence, the plaintext is x = [999.55] = 999.