Cryptography: Theory and Practice:The RSA System and Factoring

cryptography: theory and practice 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 ≤ kp1 - 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 ≤ ts - 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 ti, then there can be no solutions since 2i+1 | 2t+1 but . On the other hand, if ti - 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 tj, and 2tq1 solutions if tj - 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 ij; then the number of solutions is 0 if ti. The total number of “bad” choices for w is at most

Recall that p - 1 = 2ip1 and q - 1 = 2jq1. Now, ji ≥ 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 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 = eK(x), compute parity(y), where parity(y) denotes the low-order bit of x
2.  given y = eK(x), compute half(y), where half(y) = 0 if 0 ≤ x < n/2 and half(y) = 1 if n/2 < xn - 1.

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



Cryptography. Theory and Practice
Modern Cryptography: Theory and Practice
ISBN: 0130669431
EAN: 2147483647
Year: 1995
Pages: 133
Authors: Wenbo Mao

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net