Cryptography Reference
In-Depth Information
using RSA than to employ RSA on the plain message. Such a heuristic can be placed
on firm ground if the following
conjecture
is supported: Assume that the first
n
2 least
significant bits of the argument constitute a hard-core function of RSA with
n
-bit-long
moduli. Then, encrypting
n
/
2-bit messages by padding the message with
n
/
2 random
bits and applying RSA (with an
n
-bit modulus) on the result will constitute a secure
public-key encryption system, hereafter referred to as
Randomized RSA
.
An alternative public-key encryption scheme is presented in [35]. That encryption
scheme augments Construction 3.4.4 (of a pseudorandom generator based on one-way
permutations) as follows:
/
Key generation:
As before, the key-generation algorithm consists of selecting
at random a permutation
p
α
together with a trapdoor.
Encrypting:
To encrypt the
n
-bit string
x
(using public key
p
α
), the encryption
algorithm uniformly selects an element
s
in the domain of
p
α
and produces the
ciphertext (
p
n
α
(
s
)
,
x
⊕
G
α
(
s
)), where
b
p
n
−
1
α
(
s
)
G
α
(
s
)
=
b
(
s
)
·
b
(
p
α
(
s
))
···
(We use the notation
p
i
+
1
α
(
x
)
=
p
α
(
p
i
α
(
x
)) and
p
−
(
i
+
1)
α
(
x
)
=
p
−
1
α
(
p
−
i
α
(
x
)).)
Decrypting:
To decrypt the ciphertext (
y
,
z
) using the private key, the decryption
p
−
n
α
algorithm first recovers
s
=
(
y
) and then outputs
z
⊕
G
α
(
s
).
Assuming that factoring Blum integers (i.e., products of two primes each congruent
to 3 (mod 4)) is hard, one can use the modular squaring function in the role of the
trapdoor permutation and the least significant bit (denoted lsb) in the role of its hard-core
predicate [35, 5, 208, 82]. This yields a secure public-key encryption scheme (depicted
in Figure B.1) with efficiency comparable to that of RSA. Recall that RSA itself is
not secure (as it employs a deterministic encryption algorithm), whereas Randomized
Private key: Two
n
/
2-bit-long primes,
p
and
q
, each congruent to 3
(mod 4).
def
=
pq
.
Public key: Their product
N
Encryption of message
x
∈{
0
,
1
}
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
.
Decryption of the ciphertext (
r
,
y
):
4)
n
4)
n
Precomputed:
d
p
=
((
p
+
1)
/
mod
p
−
1,
d
q
=
((
q
+
1)
/
mod
q
−
1,
(
q
−
1
(
p
−
1
c
p
=
q
·
mod
p
), and
c
q
=
p
·
mod
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
.
Figure B.1:
The Blum-Goldwasser public-key encryption scheme [35].
