Cryptography Reference
In-Depth Information
Another approach to solve this difficulty would be to attach to the message
additional information that allows it to be recovered uniquely. For example, let c
be a ciphertext and m p :=
c ( p + 1 )/ 4 mod p , m q :=
c ( p + 1 )/ 4 mod q , and
r mod n
,
±
the four square roots of c with the notations used in Algorithm 8.2.
Then, since m p and m q are quadratic residues modulo p and q , respectively, and
r
s mod n
}
m p (
mod p
)
, r
m q (
mod q
)
, it follows that (as we have already remarked), r
is a quadratic residue modulo both p and q . Thus the Jacobi symbol of r is n =
1
and, since by Euler's criterion p
=−
1 whenever p is a Blum prime, we also
have that p
q
1 and hence n
=
=
=−
1.
Also, one sees that s
≡−
m p
(
mod p
)
and s
m q
(
mod q
)
so that s is a
quadratic non-residue modulo p and a quadratic residue modulo q , hence n =−
1
and, similarly, n =−
1. Thus if we add as information the Jacobi symbol of the
message, it serves to discard one of the pairs
±
r ,
±
s and, assuming for example that
the discarded pair is
±
r , it tells us that m is equal to s or
s . One of these integers is
<
/
>
/
2 so, if we add this bit of information to the Jacobi symbol,
the plaintext is uniquely determined. All this information can be easily gathered
at encryption time because Algorithm 2.7 can be used to efficiently compute the
Jacobi symbol of m without knowing the prime factorization of n . In contrast with
this, deciding whether a given m
n
2 and the other
n
∈ Z n is a quadratic residue is an instance of the
quadratic residuosity 4 problem , which is thought to be hard in general, although it
is no harder than factoring (and it might be easier) because it becomes easy once the
factorization of n
=
pq is known, as a consequence of Proposition 2.14. Of course,
a necessary condition for m to be a quadratic residue modulo n is that n =
1.
The preceding discussion also suggests a concrete method to make the plaintext
uniquely recoverable by restricting the message space. We may format the message
prior to encryption—using appropriate padding, etc.—so that viewed as an element
of
Z n , m is
2 and has Jacobi symbol equal to 1. By what we have just seen, only
one of the square roots of the ciphertext will satisfy these conditions.
<
n
/
8.4.1.1 The Security of Plain Rabin Encryption
Let us now examine the security of plain Rabin encryption. We start by noticing that
it satisfies the weakest security notion:
Proposition 8.6
Under
the
factoring
assumption,
plain
Rabin
encryption
is
OW-CPA secure.
Proof This follows fromTheorem 3.8, according to which
is a family of one-
way trapdoor permutations under the factoring assumption. More explicitly, let n be
a product of two randomly chosen k -bit Blum primes and suppose that there exists
a PPT algorithm that inverts BW n . Then a PPT algorithm that factors n proceeds by
{
BW n }
4 An alternative term, often preferred by number theorists, is residuacity .
 
 
Search WWH ::




Custom Search