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
⊕
