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

⊕