Method for generating pseudo-random numbers

Details Method for generating pseudo-random numbers Method for generating pseudo-random numbers

1998-03-04

2001-09-04

Hayes, Gail (Department: 2131)

Cryptography

Key management

Having particular key generator

C380S028000, C380S045000, C380S046000, C380S047000, C708S250000, C708S251000

Reexamination Certificate

active

06285761

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to cryptography and, in particular, to pseudo-random number generators.
BACKGROUND OF THE RELATED ART
Pseudo-random generators are used in some forms of cryptography to provide secured communication means for the transmission of messages between a transmitter and a receiver. Security is provided such that only an intended receiver can understand a message (e.g., voice or data) transmitted by an authorized transmitter, and only the authorized transmitter can send the message to the intended receiver. The challenge of cryptography is to change a message into a form that only the intended receiver can comprehend. This must be done in a way that is both economical for the transmitter and for the intended receiver. At the same time, it must be very difficult (in terms of time and/or processing capabilities) for an unauthorized receiver (i.e., not the intended receiver) to comprehend the message. As unauthorized receivers and unauthorized transmitters become more sophisticated, the need for secured communications become greater.
FIG. 1
depicts a functional block diagram of a transmitter
10
in the prior art having a cryptographic device for encrypting messages. The cryptographic device comprising pseudo-random number (PN) generator
12
and XOR operator
14
. PN generator
12
is defined by the following modular exponential function:
x
i
=g
x
i−1
mod
p
  (equation 1)
wherein x
i
is a value comprising m bits, p is a prime number comprising k bits, g is a generator of integer mod p, and 1<i≦n. Since equation 1 is a modular exponential function, the value of m should be less than or equal to k (i.e., m≦k). Value x
i
is generated initially by providing PN generator
12
with seed value x
0
, which is a secret value comprising m bits and known only to the authorized transmitter and the intended receiver. Thus, value x
1
is equal to g
x
0
mod p . Value x
1
is used to generate x
2
(i.e., x
2
=g
x
1
mod p), which is then used to generate x
3
, and so on.
PN generator
12
outputs a pseudo-random number z
i
comprising a d bit size segment of x
i
. The pseudo-random number z
i
is then used to encrypt a d bit size segment of a message to be transmitted. Specifically, XOR operator
14
receives as inputs the message segment and the pseudo-random number z
i
. The message segment is XOR with the pseudo-random number z
i
to produce a d bit size encrypted message segment. The values of d, m, and k depend, in part, on the degree of cryptographic security (or difficulty) sought to be attained, as will be described herein.
Cryptographic security depends on two factors: (1) the degree of difficulty in solving a discrete logarithm problem for x
i
, and (2) the degree of difficulty in breaking the pseudo-random number generator given one or more pseudo-random numbers z
i
(comprising d bits). Assuming all m bits of x
i
are available, solving a discrete logarithm problem for x
i
involves the determination of x
i−1
such that x
i
=g
x
i−1
mod p. A discrete logarithm problem is considered computationally hard, and therefore cryptographically secure, if 2
c
number of operations are required to solve it, wherein c represents a cryptographic security threshold level. The standard belief is that a discrete logarithm problem is hard if it takes at least 2
64
number of operations to solve it (i.e., c≧64).
A discrete logarithm problem can be solved by a variety of techniques. The two most efficient techniques being the well-known index calculus technique and square root technique. To solve the discrete logarithm problem for x
i
using the index calculus technique, it would require
operations
index
=O(
2
&agr;{square root over (log
2
+L p×log
2
+L log
2
+L p)})
  (equation 2)
number of operations, wherein &agr; is a constant. If c=64, the hard threshold (of 2
64
number of operations) is met when p comprises at least 512 bits (i.e., k≧512). Thus, the value selected for k is dependent upon the value of c. By contrast, to solve the discrete logarithm problem for x
i
using the square root technique, it would require
operations
sq-rt
={square root over (2
m
+L )}  (equation 3)
number of operations. If c=64, the hard threshold is met when x
i
comprises at least 128 bits (i.e., m≧128). Thus, the value of m is also dependent upon the value of c.
As mentioned earlier, solving the discrete logarithm problem for x
i
assumes all m bits of x
i
are available. If only d bit size segments of x
i
(i.e., pseudo-random number z
i
) are available, then the predecessor step to solving the discrete logarithm problem for x
i
is to somehow determine all m bits of x
i
. This is the aforementioned second factor of cryptographic security, which involves breaking the pseudo-random number generator given one or more pseudo-random number z
i
. A pseudo-random number generator is considered cryptographically secure if, given one or more pseudo-random numbers z
i
, all m bits of x
i
would be difficult to predict or determine. It is believed that if the PN generator outputs smaller bit size pseudo-random numbers z
i
(i.e., small segments of x
i
), less data would be available to a cryptanalyst to use to predict any other bits of x
i
. The exact size of pseudo-random number z
i
being outputted would depend on the degree of cryptographic security sought to be attained—that is, the value of d is dependent upon the value of c.
Blum-Micali presented a PN generator which outputted pseudo-random numbers z
i
comprising only the most significant bit of x
i
, i.e., d=1. Blum-Micali showed that the degree of difficulty in breaking this PN generator is equivalent to the degree of difficulty in solving a discrete logarithm problem for the modular exponential function of x
i
. Thus, if solving the discrete logarithm problem for x
i
is hard, then breaking Blum-Micali's PN generator (outputting pseudo-random numbers z
i
comprising only the most significant bit) is also hard.
By contrast, Peralta presented a successor PN generator which outputted pseudo-random numbers z
i
comprising log
2
m most significant bits, i.e., d=log
2
m. For example, if x
i
comprises 512 bits, then the PN generator would output pseudo-random numbers z
i
comprising no more than the nine (i.e., log
2
512) most significant bits of x
i
. Or if x
i
comprises 1024 bits, then the PN generator would output pseudo-random numbers z
i
comprising no more than the ten (i.e., log
2
1024) most significant bits of x
i
. Peralta showed that the degree of difficulty in breaking this PN generator is also equivalent to the degree of difficulty in solving the discrete logarithm problem for the modular exponential function of x
i
. Thus, if solving the discrete logarithm problem for x
i
is hard, then breaking Peralta's PN generator (outputting pseudo-random numbers z
i
comprising only log
2
m most significant bits) is also hard.
Although encryption processes that use the PN generators presented by Blum-Micali and/or Peralta are cryptographically secure, these PN generators output pseudo-random numbers z
i
comprising no more than log
2
m bits of x
i
. Since log
2
m is a relatively small value, only small bit size segments of messages can be encrypted for every pseudo-random numbers z
i
outputted by the PN generator. This results in a slower encryption process because more pseudo-random numbers z
i
have to then be outputted to encrypt the entire message. Accordingly, there exists a need for a pseudo-random number generator that outputs larger bit size pseudo-random numbers z
i
and is cryptographically secure.
SUMMARY OF THE INVENTION
The present invention is a method for outputting larger bit size pseudo-random number z
i
that is cryptographically secure. Since larger bit size pseudo-random numbers are being outputted, larger bit size segments of messages may be encrypted resulting in a speedier encryption process than encryption processes of the prior art.

Affiliated with

Also associated with

Rating

Method for generating pseudo-random numbers does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method for generating pseudo-random numbers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for generating pseudo-random numbers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2495611