Cryptography Reference
In-Depth Information
Key-generation on security parameter n :
(1) Select at random two n -bit primes, P and Q , each congruent to
3mod4.
(2) Compute
= P +1) / 4) ( n ) mod P − 1, d Q
d P
= Q +
1) / 4) ( n ) mod Q − 1, c P
= Q
·
( Q 1 mod P ), and c Q
= P
·
( P 1 mod Q ).
( N, T ),
N
PQ
T
The
output
key-pair
is
where
=
and
=
( P, Q, N, c P ,d P ,c Q ,d Q ).
(Note: for every s , it holds that ( s 2 ) ( P +1) / 4
≡ s (mod P ), and so
( s 2 ( n ) ) d P ≡ s (mod P ). Thus, raising to the d P -th power modulo P is
equivalent to taking the 2 -th root modulo P . To recover roots modulo N ,we
use the Chinese Remainder Theorem with the corresponding coecients c P
and c Q .)
Encryption of message x ∈{
( n ) using the encryption-key N :
(1) Uniformly select s 0 ∈{ 1 , ..., N} .
(2) For i =1 , .., ( n ) + 1, compute s i ← s i− 1 mod N and σ i =lsb( s i ).
The ciphertext is ( s ( n )+1 ,y ), where y = x ⊕ σ 1 σ 2 ···σ ( n ) .
(Note: s 1 plays the role played by r in the general scheme.)
Decryption of
0 , 1
}
the
ciphertext
( r, y )
using
the
encryption-key
T
=
( P, Q, N, c P ,d P ,c Q ,d Q ):
(1) Let s ← r d P mod P ,and s ← r d Q mod Q .
(2) Let s 1 ← c P · s + c Q · s mod N .
(3) For i =1 , .., ( n ), compute σ i =lsb( s i )and s i +1 ← s i
mod N .
The plaintext is y ⊕ σ 1 σ 2 ···σ ( n ) .
Note: lsb is a hard-core of the modular squaring function (3).
Fig. 5.3 The Blum-Goldwasser Public-Key Encryption Scheme (30). For simplicity we
assume that , which is polynomially bounded (e.g., ( n )= n ), is known at key-generation
time.
the encryption-key ( N,e )), the encryption algorithm uniformly selects
an element, r , in the set of residues mod N , and produces the ciphertext
( r e mod N,σ ⊕ lsb( r )), where lsb( r ) denotes the least significant bit of
r (which is a hard-core of the RSA function (3)). To decrypt the cipher-
text ( y, τ ) (using the decryption-key ( N,d )), the decryption algorithm
just computes τ
lsb( y d mod N ). Turning to the second scheme, we
assume the intractability of factoring large integers, and use squaring
modulo a composite as a trapdoor permutation over the corresponding
quadratic residues (while using composites that are the product of two     Search WWH ::

Custom Search