Cryptography Reference
In-Depth Information
12.2.2
RSA PRBG
The RSA PRBG as specified in Algorithm 12.3 employs the fact that the RSA
function is a (conjectured) one-way function (see Section 7.2.2) and that the LSB
is a hard-core predicate of it. Similar to the RSA public key cryptosystem, the RSA
PRBG takes as input a large integer
n
(that is the product of two large primes
p
and
q
)
and
e
(that is a randomly chosen integer between 2 and
φ
(
n
)
1 with
gcd
(
e, φ
(
n
)) =
1). The PRBG is then initialized by randomly selecting a seed
x
0
−
Z
n
.
=
s
0
from
It then generates an output bit
b
i
by computing
x
i
=
x
i−
1
(mod
n
) and setting
b
i
=
lsb
(
x
i
) for
i
1. Again, a potentially infinite bit sequence (
b
i
)
i≥
1
can be
generated along this way. It is the output of the RSA PRBG.
≥
Algorithm 12.3
The RSA PRBG.
(
n, e
)
x
0
∈
R
Z
n
for
i
=1to
∞
do
x
i
← x
i−
1
(mod
n
)
b
i
← lsb
(
x
i
)
output
b
i
(
b
i
)
i≥
1
If, for example,
e
=3, then generating an output bit requires only one modular
multiplication and one modular squaring. This is efficient. The efficiency of the RSA
PRBG can be further improved by extracting the
j
least significant bits of
x
i
(instead
of only the LSB), where
j
=
c
log log
n
for a constant
c
.
In either case, the security of the RSA PRBG is based on the IFA (see
Definition 7.10). This means that anybody who is able to factorize large integers
can also break the security of the RSA PRBG.
12.2.3
BBS PRBG
The BBS PRBG [10] as specified in Algorithm 12.4 employs the fact that the
modular square function restricted to Blum integers is a (conjectured) one-way
function (see Section 7.2.2), and that—similar to the RSA function—the LSB is
a hard-core predicate of it. The BBS PRBG takes as input a Blum integer
n
(i.e.,
an integer
n
that is the product of two primes
p
and
q
, each of them congruent to
3 modulo 4). Similar to the RSA PRBG, the BBS PRBG is initialized by randomly
selecting a seed
x
0
=
s
0
from
Z
n
. It then generates an output bit
b
i
by computing
x
i
=
x
i−
1
(mod
n
) and setting
b
i
=
lsb
(
x
i
) for
i
≥
1. A potentially infinite bit
sequence (
b
i
)
i≥
1
is the output of the BBS PRBG.
