Cryptography: Theory and Practice by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95 |
Previous | Table of Contents | Next |
Let us write
where p1 is odd, and
where q1 is odd. Since
we have that
Hence
and
Now, the condition (p - 1) | [ur becomes 2ip1 | ur. Since p1 | r and r is odd, it is necessary and sufficient that 2i | u. Hence, u = k2i, 0 ≤ k ≤ p1 - 1, and the number of solutions to the congruence wr ≡ 1 (mod p) is p1.
By an identical argument, the congruence wr ≡ 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 wr ≡ (mod n) is p1q1.
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 = gu, as above, we get
Since g(p-1)/2 ≡ -1 (mod p), we have that
Since p - 1 = 2ip1, we get
Taking out a common factor of p1, this becomes
Now, if t ≥ i, then there can be no solutions since 2i+1 | 2t+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 2i-t-1 (note that r/p1 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 2tq1 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 = 2ip1 and q - 1 = 2jq1. Now, j ≥ i ≥ 1 so p1q1 < 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.
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:
We will prove that, given y = eK(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 eK(x1)eK(x2) = eK (x1x2).
We will show how to compute x = dK(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 ≤ log2 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. eK(2) is computed to be 946. Suppose, using our oracle for half, that we obtain the following values yi 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.
Previous | Table of Contents | Next |
Copyright © CRC Press LLC