![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
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 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 By similar reasoning, the congruence 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. 4.6.2 Partial Information Concerning Plaintext BitsThe 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.
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.
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |