Cryptography Reference
In-Depth Information
x
0
is the seed which
generates the sequence. If any of these values are compromised, or can be guessed, this
generator cannot produce unpredictable numbers. It turns out that with this particular trans-
formation, this is rather easy to do; given a partial sequence of these random numbers, the
rest of the sequence can often be constructed even when
The values
a
,
b
, and
m
are parameters which define the generator;
a
,
b
,
m
, and
x
0
are unknown.
It should come as no surprise that many of the same transformations that we use to
encrypt data can also be used to generate random numbers. After all, the purposes of dis-
guising messages and the purposes of disguising the previous numbers and the seed in a
sequence of pseudorandom numbers are very similar. A random number generator able to
produce integers that cannot be predicted by an adversary are suitable for cryptography;
these are called cryptographically secure pseudorandom bit generators (CSPRBG). Descrip-
tions of two such generators follow; the first resembles Rabin, while the second resembles
RSA.
Blum-Blum-Shub Pseudorandom Bit Generator
To generate pseudorandom
numbers or bitstreams:
1.
Choose two secret strong primes,
p
and
q
, both congruent to 3 modulo 4. Form
n
=
pq
.
Choose
j
as a positive integer not exceeding log
2
(log
2
n
)
2.
Select a random integer seed
s
such that
•2
≤
s
<
n
•
s
and
n
are relatively prime.
Compute
x
0
= the lnr of
s
2
modulo
n
.
3.
Repeat for as long as desired:
x
i
= the lnr of
x
i
1
2
modulo
n
• Compute
.
z
i
be the
j
x
i
.
• Let
least significant bits of
4.
The output sequence is
z
1
,
z
2
,
z
3
, ....
E
XAMPLE
.
For this example we will use small primes; in reality, we must use large, strong
primes. Suppose we choose
p
= 11351,
q
= 11987. So
n
= 136064437. We compute
j
as 4,
the largest integer not exceeding log
2
(log
2
(
n
)) = 4.75594, and we will select as our seed
s
= 80331757. We wish to generate a stream of 2 blocks, each of bit length 4; we compute
the values
x
0
s
2
80331757
2
131273718 (mod 136064437)
x
1
x
0
2
131273718
2
47497112 (mod 136064437)
1000
base 2
(mod 2
4
) (the 4 least significant bits of
z
1
47497112
8
x
1
)
Search WWH ::
Custom Search