Cryptography Reference
In-Depth Information
Treating the other two square roots of x 2 (mod N ) as random integers it is natural to
conjecture that the probability that either of them has a specific pattern of their l least
significant bits is roughly 2 / 2 l . This conjecture is confirmed by experimental evidence.
Hence, the probability of decryption failure is approximately 1 / 2 l 1 .
Extra bits for Rabin : Send two extra bits of information to specify the square root. For
example, one could send the value b 1 =
( N ) of the Jacobi symbol (the set
{−
1 , 1
}
can be
encoded as a bit under the map x
1) / 2), together with the least significant bit b 2
of the message. The ciphertext space is now C κ =
( x
+
) ×{
2 and, for simplicity
(
Z
/N
Z
0 , 1
}
) .
These two bits allow unique decryption, since ( N )
of exposition, we take M κ =
(
Z
/N
Z
=
1, m and N
m have the same
Jacobi symbol, and if m is odd then N
m is even.
Indeed, when using the Chinese remainder theorem to compute square roots then one
computes m p and m q such that ( m p )
( m q )
=
=
1. Then decryption using the bits b 1 ,b 2
is: if b 1 =
1 then the decryption is
±
CRT ( m p , m q ) and if b 1 =−
1 then solution is
±
m p , m q ).
This scheme is close to optimal in terms of ciphertext expansion (though see Exer-
cise 24.2.6 for an improvement) and decryption never fails. The drawbacks are that the
ciphertext contains some information about the message (and so the scheme is not IND-
CPA secure), and encryption involves computing the Jacobi symbol, which typically
requires far more computational resources than the single squaring modulo N .
CRT (
q (mod 8) then ( N )
Williams :Let N
=
pq where p,q
3(mod4). If p
≡±
=−
1.
Hence, for every 1
2 x is a square modulo N
(see Exercise 24.6.3 ). Without loss of generality, we therefore assume that p
x<N exactly one of x , N
x ,2 x , N
3(mod8)
and q
7 (mod 8). The integer N is called a Williams integer in this situation.
Williams [ 566 ] suggests encoding a message 1
m <N/ 8
1 (alternatively, m
κ 5 ) as an integer x such that x is even and ( N )
M κ ={
0 , 1
}
=
1 (and so x or
x is a
square modulo N )by
if 2 m
+
1
4(2 m
+
1)
=
1 ,
N
x = P ( m )
=
if 2 m
+
1
2(2 m
+
1)
=−
1 .
N
P ( m ) 2 (mod N ).
To decrypt one computes square roots to obtain the unique even integer 1 <x<N
such that ( N )
The encryption of m is then c
=
1 and x 2
=
c (mod N ). If 8
|
x then decryption fails (return
). Other-
wise, return m
0(mod4).
Unlike the extra bits scheme, this does not reveal information about the ciphertext. It
is almost optimal from the point of view of ciphertext expansion. But it still requires the
encrypter to compute a Jacobi symbol (hence losing the performance advantage of Rabin
=
( x/ 2
1) / 2if x
2(mod4)and m
=
( x/ 4
1) / 2if x
Search WWH ::




Custom Search