Encryption device and communication apparatus using same

In a modular multiplication circuit which operates under the conditions 0<N<2.sup.n, 0.ltoreq.A, B<2N, R=2.sup.n+2, a first multiplier performs multiplication between input values A and B. A second multiplier performs multiplication between the output of the first multiplier and [-(N.sup.-1 mod R)], which is decided by set parameters N and R, and outputs M. A third multiplier performs multiplication between the output M and the set parameter N and outputs the product M.times.N. An adder adds the output of the first multiplier and the output of the third multiplier, and a shift register shifts the sum leftward by n+2 bits. Thus, an output P=(A.times.B+M.times.N)/R is produced.

BACKGROUND OF THE INVENTION 
This invention relates to an encryption device for performing encoded 
communication in home banking, farm banking and electronic mail in a 
computer network and in various communication services such as electronic 
conferencing. Furthermore, the invention relates to an encryption device 
for performing encrypted communication using an encryption method that 
employs modular multiplication (quadratic residual ciphers, RSA ciphers, 
ElGamal ciphers, etc.), a key distribution method (DH-type key 
distribution method, an ID-based key distribution method, etc.), a 
zero-knowledge authentication system, etc. 
Further, the invention relates to a communication method and apparatus 
which employ random-number generation necessary in encrypted 
communication, particularly data concealment, originator/terminator 
authentication, distribution of encryption key and a zero-knowledge 
authentication protocol, etc. The invention relates also to a method and 
apparatus for random-number generation as necessary in a Monte Carlo 
simulation, by way of example. 
The importance of cryptographic techniques to protect the content of data 
has grown with the rapid advances that have recently been made in 
information communication systems using computer networks. In particular, 
high-speed encryption is becoming essential as computer networks are being 
developed for higher speed and larger volume. 
Among the foregoing, modular multiplication is a particularly important 
operation used in various cryptographic techniques. Various methods of 
encryption using modular multiplication will now be described. 
Two methods of encryption which are well known are a secret-key 
cryptosystem and a public-key cryptosystem. 
In a public-key cryptosystem, the encryption and decryption keys differ. 
The encryption key is known publicly but the decryption key is held in 
secrecy by the receiving party and it is difficult to infer the decryption 
key from the publicly disclosed encryption key. Ciphers based upon modular 
multiplication, such as RSA ciphers and ElGamal ciphers, are used widely 
in public-key cryptosystem. Attention is being given to the fact that 
these ciphers have an application called authentication in addition to a 
secret communication function. Authentication, which is a function for 
investigating whether a party transmitting communication text is correct 
or not, is also referred to as a digital signature. In a digital signature 
which uses these ciphers, secret signatures known only to the transmitting 
party are possible and cannot be forged. Accordingly, a digital signature 
is secure and often finds use as a form of authentication communication in 
financial facilities. 
In a secret-key cryptosystem, in which the same key is shared in secrecy by 
both the sending and receiving parties, use is made of random numbers 
referred to as quadratic residues obtained from an operation employed in 
modular multiplication. 
The above-mentioned public-key cryptosystem and secret-key cryptosystem 
methods are often used together with a key-delivery system or key 
distribution system. A well known example of the key-delivery system is 
DH-type key delivery developed by Diffie and Hellman. These systems also 
implement operations using modular multiplication. Furthermore, an 
ID-based key distribution method is attracting attention as a key 
distribution method. Modular multiplication is used in various key 
distribution methods. 
In addition, zero-knowledge authentication is available as an encryption 
technique. This is a method in which one party convinces another party of 
the fact that it possesses certain knowledge without letting the other 
party know of the content of the information. 
The details of the foregoing are described in "Modern Cryptographic Theory" 
[Denshi Joho Tsushin Gakkai (1986)], by Shinichi Ikeno and Kenji Koyama, 
and "Cryptography and Information Security", Shokodo (1990)], by Shigeo 
Tsujii and Masao Kasahara. 
It should be appreciated from the foregoing that if an efficient modular 
multiplication circuit and method can be realized, this will make it 
possible to implement a variety of encryption systems efficiently. 
A technique referred to as the Montgomery method (Montgomery, P. L: 
"Modulator Multiplication without Trial Division", Math. Of Computation, 
Vol. 44, 1985, pp. 519.about.521) is known as a method of performing 
modular multiplication of P=A.multidot.B.multidot.R.sup.-1 mod N (where R 
and N are relatively prime integers) The Montgomery method makes it 
possible to perform modular multiplication without division. This will now 
be described. 
[Description of Montgomery Method] 
A theorem derived by Montgomery is as follows: "When N and R are relatively 
prime integers and N'=-N.sup.-1 mod R holds, arbitrary integers T, 
(T+M.multidot.N)/R satisfy the following relationship: 
EQU (T+M.multidot.N)/R=T.multidot.R.sup.-1 mod N (A-1) 
where M=T.multidot.N' mod R holds. 
In accordance with the Montgomery method, therefore, in a case where 
modular multiplication: P=A.multidot.B.multidot.R.sup.-1 mod N is to be 
executed, this can be carried out in the manner 
EQU P=A.multidot.B.multidot.R.sup.-1 mod N=(A.multidot.B+M.multidot.N)/R(A-2) 
where 
EQU M=A.multidot.B.multidot.N' mod R (A-3) 
using an integer R which is prime with respect to N. 
In a case where N is an odd number, R is a prime integer with respect to N 
if R=2.sup.r (where r is any integer) holds. In this case, division by R 
entails a bit shift only and, hence, the operation of Equation (A-2) can 
be executed in simple fashion by multiplication and addition. 
With the Montgomery method, however, cases arise in which the range of 
output values of modular multiplication becomes larger than the range of 
input values. For example, letting the ranges of the values of inputs A 
and B be expressed by 
EQU 0.ltoreq.A, B&lt;N 
the operation of the Montgomery method indicated by Equations (A-2), (A-3) 
EQU P=(A.multidot.B+M.multidot.N)/R=(C+M).multidot.N/R 
where C=A.multidot.B/N is executed. 
If C+M&gt;R holds in this case, then (C+M)/R&gt;1 will hold and we will have 
EQU P=(A.multidot.B+M.multidot.N)/R&gt;N 
That is, there will be cases in which a value P&gt;N is outputted with respect 
to inputs of 0&lt;A, B&lt;N. 
As a consequence, it is difficult to repeat modular multiplication by a 
circuit or method which implements the Montgomery method. Further, the 
operation of modular multiplication generally used in cryptographic 
techniques is 
EQU Q=A.multidot.B mod N 
In order to realize such modular multiplication, it is necessary to repeat 
the Montgomery method a plurality of times. This makes it difficult to 
execute this operation efficiently using the Montgomery method. 
Further, with regard to a sequence of random numbers used in encrypted 
communication, it is required that random numbers generated after a 
certain point in time not be readily predictable from a sequence of random 
numbers generated up to this point in time. In the literature "Primality 
and Cryptography" (by Evangelos Kranakis, published by John Wiley & Sons, 
pp. 108.about.137), a sequence of pseudorandom numbers satisfying the 
above-mentioned requirement is described. 
Specifically, if we let a sequence of pseudorandom numbers be represented 
by b.sub.1, b.sub.2, . . . , a bit b.sub.i is given by 
EQU X.sub.i+1 =X.sub.i.sup.2 mod N (i=0, 1, 2, . . . ) (B-1) 
EQU b.sub.i =lsb(X.sub.i) (i=1, 2, . . . ) (B-2) 
where X.sub.0 is an initial value given arbitrarily and p, q are prime 
numbers in which p.ident.q.ident.3 (mod 4) holds (it should be noted that 
N=p.multidot.q holds and lsb represents least significant bit). A 
different method of generating a sequence of pseudorandom numbers is 
described in the literature "Cryptography and information Security" (by 
Shigeo Tsujii and Masao Kasahara, published by Shokodo, pp. 86). 
Specifically, if we let a sequence of pseudorandom numbers be represented 
by b.sub.1, b.sub.2, . . . , a bit b.sub.i is given by 
EQU x.sub.i+1 =x.sub.i.sup.e mod N (i=0, 1, 2, . . . ) (B-3) 
EQU b.sub.i =lsb(x.sub.i) (i=1, 2, . . . ) (B-4) 
where x.sub.0 is an initial value given arbitrarily p, q are prime numbers 
and e is a relatively prime number with respect to L (L is a least common 
multiple of p-1 and q-1). N=p.multidot.q holds and lsb represents least 
significant bit. 
It is known that obtaining b.sub.i+1 solely from the sequence of 
pseudorandom numbers b.sub.1, b.sub.2, . . . , b.sub.i generated by these 
methods would require an amount of labor tantamount to that needed to 
factorize N. In other words, it is known that the amount of computation 
for obtaining pseudorandom numbers to be generated from a certain point in 
time onward from a sequence of pseudorandom numbers generated up to this 
point in time is equivalent to the amount of computation needed to 
factorize N. However, in order to make the factorization of N difficult in 
terms of amount of computation, it is required that p, q be made of 
several hundred bits. Random numbers thus generated by a method through 
which it is made difficult, in terms of amount of computation, to predict 
random numbers to be generated from a certain point in time onward from a 
sequence of random numbers generated up to this point in time are referred 
to as pseudorandom numbers considered cryptologically secure. 
The operations of Equations (B-1) and (B-3) are included in the operation 
referred to as modular multiplication indicated by the following equation: 
EQU Q=.upsilon..multidot..nu. mod N (B-5) 
(where Q, .upsilon., .nu. are integers.) 
The above-mentioned Montgomery method is known as a method of performing 
modular multiplication efficiently. If the Montgomery method is used, the 
operation can be carried out without performing division by modulus N. As 
a result, processing can be executed more efficiently than with ordinary 
modular multiplication. 
If we let modular multiplication for a case in which the Montgomery method 
is used be represented by Mont (.upsilon., .nu.), then Mont (.upsilon., 
.nu.) will be given by 
EQU Mont (.upsilon., .nu.).ident..upsilon..multidot..nu..multidot.R.sup.-1 (mod 
N) (B-6) 
using R, which is a relatively prime number with respect to N. 
In order to obtain the computational result Mont (.upsilon., .nu.) of the 
above equation with the Montgomery method, the following operation is 
carried out: 
EQU Mont (.upsilon., .nu.)=(.upsilon..multidot..nu.+M.multidot.N)/R(B-7) 
where 
EQU M=.upsilon..multidot..nu..multidot.N' mod R (B-8) 
EQU N'=-N.sup.-1 mod R (B-9) 
In a case where N is an odd number, R and N are relatively prime integers 
if R=2.sup.t (where t is any integer) holds. In this case, division by R 
and modular multiplication essentially need not be performed and Mont 
(.upsilon., .nu.) can be executed at high speed solely by multiplication 
and addition. 
The procedure for performing a quadratic residue operation in a case where 
the Montgomery method is used is given by 
EQU y.sub.0 =R.multidot.X.sub.0 mod N (B-10) 
EQU y.sub.i+1 =R.sup.-1 .multidot.y.sub.i.sup.2 mod N (i=0, 1, 2, . . . )(B-11) 
using the same parameters as in Equation (B-1) and R, which is a relatively 
prime number with respect to N. 
In this case, when the sequences generated by Equations (B-1) and (B-11) 
are compared, we have 
EQU y.sub.i =R.multidot.X.sub.i mod N (i=0, 1, 2, . . . ) (B-12) 
and the sequence y.sub.i (i=0, 1, 2, . . . ) generated by Equation (B-11) 
is obtained by multiplying the sequence X.sub.i (i=0, 1, 2 . . . ) 
generated by Equation (B-1) by R. Accordingly, in order to generate 
b.sub.i, which is a series of the least significant bit of X.sub.i, as a 
pseudorandom number sequence which is cryptologically secure, it is 
required that the following operation be performed with regard to Yi 
obtained by computation: 
EQU X.sub.i =R.sup.-1 .multidot.y.sub.i mod N (i=0, 1, 2, . . . )(B-13) 
Equation (B-3) can be executed by repeating the modular exponentiation 
operation indicated by Equation (B-5). More specifically, the procedure 
for successively computing modular exponentiation x.sub.i+1 =x.sub.i.sup.e 
mod N (i=0, 1, 2, . . . ) by repeating modular multiplication is as 
indicated by "Algorithm 1" below. It should be noted that e is an integer 
comprising k bits and. is represented by e=[e.sub.k, e.sub.k-1, . . . 
e.sub.2, e.sub.1 ]. 
##EQU1## 
With the INPUT statement of line (**1), values of x.sub.0, e, N, s are 
entered. Here s is the iteration number of the residual operation. The FOR 
statement of line (**2) is a command for repeating the processing up to 
line (**9) from "0" to "s" in relation to the function i. This statement 
causes repetition of processing for successively obtaining the modular 
exponentiation x.sub.i+1 (i=0, 1, 2, . . . ,s). 
The procedure for computing the modular exponentiation x.sub.i+1 
=x.sup.i.sup.e mod N by repeating modular multiplication using the 
computation procedure of the Montgomery method is as shown below. It 
should be noted that R is a relatively prime integer with respect to N and 
e is an integer comprising k bits, as mentioned earlier, where e=[e.sub.k, 
e.sub.k-1, . . . e.sub.2, e.sub.1 ]. If this algorithm is executed, the 
series x.sub.i (i=0, 1, 2, . . . ,s), which is obtained by Equation (B-2), 
can be acquired. 
##EQU2## 
In a case where Equation (B-2) is computed by the Montgomery method in 
accordance with Algorithm 2, the series y.sub.i+1 (i=0, 1, 2, . . . , s) 
obtained as the output of the FOR-NEXT portion with respect to j is 
represented by 
EQU y.sub.0 =R.multidot.x.sub.0 mod N (B-14) 
EQU y.sub.i+1 =R.sup.-(e-1) .multidot.y.sub.i.sup.e mod N (i=0, 1, 2, . . . 
)(B-15) 
using the same parameters as in Equation (B-1) and R, which is a relatively 
prime number with respect to N. 
In this case, when the sequence x.sub.i+1 (i=0, 1, 2, . . . ) generated by 
Equation (B-3) and the sequence y.sub.i+1 (i=0, 1, 2, . . . ) generated by 
Equation (B-15) are compared, we have 
EQU y.sub.i =R.multidot.X.sub.i mod N (i=0, 1, 2, . . . ). (B-16) 
In other words, in a case where Equation (B-3) is computed by the 
Montgomery method in accordance with Algorithm 2, the sequence Yi+l (i=0, 
1, 2, . . . s) obtained as the output of the FOR-NEXT portion with respect 
to j is the relation of Equation (B-16) with regard to the sequence 
x.sub.i+1 (i=0, 1, 2, . . . s) obtained by Equation (B-3). 
Accordingly, in order to obtain the operational result x.sub.i+1 
(x.sub.i.sup.e mod N), which is obtained by Algorithm 1 of a modular 
exponentiation operation which does not employ the Montgomery method with 
regard to the input x.sub.i, by Algorithm 2 of a modular exponentiation 
operation which does employ the Montgomery method, it is necessary to 
correct x.sub.i to y.sub.i =Mont (x.sub.i,R.sub.R) (=R.multidot.x.sub.i 
mod N) by the equation (*1) of Algorithm 2 and correct y.sub.i+1, which is 
obtained as the output of the FOR-NEXT portion with respect to j to 
x.sub.i+1 =Mont (y.sub.i+1, 1) (=R.sup.-1 .multidot.y.sub.i+1 mod N) by 
equation (*3). 
However, in a case where the secure pseudorandom number generating method 
described above is used, it is required that p, q be made several hundred 
bits. As a result, a large amount of computation is involved. In 
particular, the amount of computation for the portions of Equations (B-1), 
(B-3) is large. Consequently, pseudorandom numbers Cannot be generated at 
high speed and generation/reproduction of communication data cannot be 
performed at a high speed on the basis of these pseudo-random numbers. 
SUMMARY OF THE INVENTION 
Accordingly, an object of the present invention is to provide an encryption 
device, as well as a communication apparatus using this device, in which 
it is possible to execute modular multiplication of 
P=A.multidot.B.multidot.R.sup.-1 mod N, without changing the ranges of 
input/output values, using the Montgomery method, whereby encryption is 
performed by executing modular multiplication efficiently. 
Another object of the present invention is to provide an encryption device, 
as well as a communication apparatus using this device, in which 
encryption is performed by executing modular multiplication of 
Q=A.multidot.B mod N efficiently by the Montgomery method. 
A further object of the present invention is to provide a communication 
method and apparatus in which secure pseudorandom numbers can be generated 
at a higher speed and more easily, wherein the pseudorandom numbers are 
used to perform generation/reproduction of communication data at a high 
speed. 
Other features and advantages of the present invention will be apparent 
from the following description taken in conjunction with the accompanying 
drawings, in which like reference characters designate the same or similar 
parts throughout the figures thereof.

DESCRIPTION OF THE PREFERRED EMBODIMENTS 
Preferred embodiments of the present invention will now be described with 
reference to the accompanying drawings. 
&lt;First Embodiment&gt; 
FIG. 1 is a diagram illustrating the configuration of an encryption system 
according to a first embodiment of the invention. This embodiment deals 
with an encryption system in an n vs. n communication arrangement of the 
kind shown in FIG. 1. Numeral 1 denotes a communication network. In this 
embodiment the network is a local communication network, such as a local 
area network (LAN) or a wide area communication network, such as a 
telephone circuit. Communication devices 2.sub.-1 .about.2.sub.-n are 
connected to the network 1 and to terminals 3.sub.-1 .about.3.sub.-n, 
which can be accessed by users. (When the communication devices are 
referred to generically below, the term "communication device 2" will be 
used.) The users employ the terminals 3.sub.-1 .about.3.sub.-n to create 
data. (When the terminals are referred to generically below, the term 
"terminal 3" will be used.) 
Encryption devices 4.sub.-1 .about.4.sub.-n encrypt input data that is to 
be transmitted and then output the encrypted data. (When the encryption 
devices are referred to generically below, the term "encryption device 4" 
will be used.) The encryption device 4 is incorporated in the 
communication device 2 (which is the case in encryption device 4.sub.-1), 
inserted between the communication device 2 and communication network 1 
(which is the case in encryption device 4.sub.-2), or is incorporated in 
the terminal 3 connected to the communication device 2 (which is the case 
in encryption device 4.sub.-1). Even if the encryption device 4 has not 
been connected to the communication device, it is possible to incorporate 
the encryption device in a portable device, such as an IC card, which can 
be used upon being connected to the communication device 2 or terminal 3 
when necessary. Users who employ the 10 communication devices 2 or 
terminals 3 perform secret communication, authentication communication or 
encrypted communication such as key distribution, zero-knowledge 
authentication, etc., by the encryption devices having modular 
multiplication circuits according to this embodiment. 
This encryption system is applicable to communication arrangements other 
than that shown in FIG. 1. For example, FIG. 2 is a diagram illustrating 
the manner in which the encryption system of this embodiment is applied to 
a memory arrangement. Numeral 5 in FIG. 2 denotes a magnetic disk for 
storing encrypted data transferred from access units 6.sub.-1 
.about.6.sub.-1. The access units 6.sub.-1 .about.6.sub.-n plant data, 
which has been encrypted by the respective encryption devices 4, in the 
magnetic disk 5. Thus, users are capable of utilizing the encryption 
system individually by means of encryption devices that employ the 
arithmetic circuits and method of this embodiment in a memory arrangement 
in the same manner as is done in a communication arrangement. 
A description will now be given of a communication method using RSA 
cryptosystem. Encryption and decryption are respectively represented by 
the following formulae: 
EQU Encryption: C=M.sup.e mod N 
EQU Decryption: M=C.sup.d mod N 
wherein M represents a plain text to be transmitted, C indicates a 
cryptogram, e indicates an encryption key opened to the public, d 
indicates a decryption key and N represents a modulus which is opened to 
public. 
Thus, encryption and decryption of an RSA cryptosystem can be executed 
modular exponentiation circuits which have constructions similar to each 
other. The following description, therefore, mainly refer to encryption. 
The modular multiplication C=M.sup.e mod N may be conducted simply by 
repeating modular multiplication of two numbers. When M and e are large, 
however, the amount of computation becomes huge. According to the 
invention, therefore, computation is executed in accordance with the 
following algorithm. In the algorithm shown below, e is an integer having 
k bits and is expressed by: 
EQU e=e.sub.k, e.sub.k-1 . . . , e.sub.2, e.sub.1. 
##EQU3## 
In this case, therefore, the modular exponentiation is conducted by 
repeating modular multiplication C=C.multidot.B mod N (B is M or C). 
A circuit capable of efficiently executing the algorithm is shown in FIG. 
18. Referring to FIG. 18, reference numerals 281 and 282 represent shift 
registers for respectively storing the values of M and e. Reference 
numerals 283 and 284 represent registers for respectively storing the 
values of N and C. Reference numerals 285 and 286 represent select 
switches for selecting the inputs and 287 represents a multiplexer for 
selecting the value of C in the register 284 for each m bits (m is an 
arbitrary integer) from the upper digits to transmit it in serial form. 
Reference numeral 288 represents a modular multiplication circuit for 
executing the calculation C=C.multidot.B mod N. Reference numeral 289 
represents a controller for discriminating whether or not ei=1 or i&gt;1 to 
control computations 1 and 2 of the Algorithm B or controlling a clear 
signal or a preset signal for the selector and the register at the time of 
the receipt of the signal or the initialization. The controller 289 can 
easily be formed by a counter, a ROM and some logic circuits. 
Then, the operation of the circuit shown in FIG. 18 will now be described. 
The circuit receives plain text M, public key e and public modulo N. 
Therefore, M, e and N are in serial or parallel form supplied to the 
register 283. At this time, the selector 285 selects M to supply M to the 
register 281. Simultaneously, initialization is performed in such a manner 
that C=1 by the clear signal or the preset signal for the register as an 
alternative to supplying the value of C to the register 284. 
After the input and the initialization has been completed, the modular 
multiplications in accordance with the calculations 1 and 2 are commenced. 
The difference between the computation 1 and the computation 2 lies in the 
fact that B is M or C in the modular multiplication C=C.multidot.B mod N. 
Therefore, in a case where the computation 1 is executed, the selector 286 
selects serial output M for each m bits from the register 281. In a case 
where the computation 2 is executed, the selector 286 selects serial 
output C for each m bits from the multiplexer 287. The serial output M for 
each m bits from the shift register 281 is again supplied to the shift 
register 281 via the selector 285. The modular multiplication circuit 288 
are constituted and operated as described above. The output C from the 
modular multiplication circuit 288 is, in parallel, supplied to the 
register 284 so as to be used in the next residue multiplication, so that 
the computations 1 and 2 are efficiently repeated. If the apparatus is 
arranged to receive C and d in place of M and e, a cryptogram can be 
decrypted. 
Input values and parameters are decided based upon the following condition 
in order to equalize the ranges of the input and output values in Equation 
(A-2) cited above. The condition is: 
"The range of P obtained from Equation (A-2) satisfies the relation 0&lt;P&lt;2N, 
where input values A and B satisfy the relations 0&lt;A and B&lt;2N, 
respectively, and parameters N and R satisfy the relations 0&lt;N&lt;2.sup.n and 
R=2.sup.n+2 (where n is any integer), respectively." 
The above-mentioned condition is validated as follows: 
"If R=2.sup.n+2 holds, M&lt;2.sup.n+2 is established from Equation (A-3). 
Since N&lt;2.sup.n holds, we have 2N+M/2&lt;R. Accordingly, on the basis of 
0.ltoreq.A, B&lt;2, we have 
EQU P=(A.multidot.B+M.multidot.N)/R&lt;(2N+M/2).multidot.2N/R&lt;2N. 
Since 0.ltoreq.P holds from Equations (A-2), (A-3), we have 0.ltoreq.P&lt;2N." 
Thus, if the conditions 0&lt;N&lt;2.sup.n, 0.ltoreq.A, B&lt;2N, R=2.sup.n+2 (where n 
is any integer) are satisfied, the, P outputted by the Montgomery method 
can be made to satisfy the relation 0.ltoreq.P&lt;2N, which is in a range 
which is the same as that of the input values A, B. Accordingly, a result 
P of modular multiplication, which falls within the range of the input 
values can be obtained at all time by executing modular multiplication 
based upon the Montgomery method using a circuit for setting the integers 
N, A, B, R which satisfy the above-mentioned conditions, and a circuit for 
operating on the integers N, A, B, R which satisfy the above-mentioned 
conditions. 
FIG. 3 is a block diagram showing an example of the configuration of a 
modular multiplication circuit according to the first embodiment. Numeral 
100 denotes the modular multiplication circuit, which includes a 
multiplier 101 for executing multiplication between input values A and B. 
The input values A, B, which are produced by the terminal 3, are items of 
data to be encrypted and transferred to the communication network 1 or a 
magnetic disk 5. 
A multiplier 102 executes multiplication between the output (A.times.B) of 
multiplier 101 and N'=(-N.sup.-1 mod R), which is decided by the set 
parameters N and R, and outputs lower n+2 bits of the product as 
A.times.B.times.N' mod R (output M). A multiplier 103 executes 
multiplication between this output M and the set parameter N and then 
outputs the product (M.times.N). An adder 104 adds the output (A.times.B) 
of multiplier 1 and the output (M.times.N) of multiplier 103. A shift 
register 105 executes the operation 1/2.sup.n+2 by shifting the output 
data from adder 104 leftward by n+2 bits. The shift register 105 produces 
the output P=[(A.times.B)+(M.times.N)]/2.sup.n+2. Numerals 110, 111 denote 
constant generating circuits for respectively outputting the constants 
-N.sup.-1 mod R and N. 
The modular multiplication circuit 100 is realized by the simple circuit 
construction described above. Furthermore, the output value P falls within 
the range of the input values A and B at all time owing to the fact that 
the input values A, B and parameters R, N are decided in accordance with 
the above-mentioned conditions. Accordingly, even if the encryption device 
4 uses cryptography that requires modular multiplication to be executed a 
plurality of times, it is possible to apply the modular multiplication 
circuit 100 to the encryption device 4. As a result, an encryption system 
in which modular multiplication can be utilized efficiently is 
constructed. 
&lt;Second Embodiment&gt; 
In the modular multiplication circuit according to the first embodiment, 
the output value P falls within the range of the input values A and B at 
all times in modular multiplication using the Montgomery method. In the 
second embodiment, modular multiplication represented by Q=A.multidot.B 
mod N, which is often used in encryption, executed by the modular 
multiplication circuit 288 in FIG. 18 for example, is implemented using 
the above-mentioned modular multiplication circuit. 
In order to obtain the above-mentioned output Q using the Montgomery 
method, it is required that the following two equations be executed 
continuously: 
EQU P=A.multidot.B.multidot.R.sup.-1 mod N=(A.multidot.B+M1.multidot.N)/R(A-4) 
EQU Q=P.multidot.R.sub.R .multidot.R.sup.-1 mod N=(P.multidot.R.sub.R 
+M2.multidot.N)/R (A-5) 
where 
M1=A.multidot.B.multidot.N' mod R 
M2=P.multidot.R.sub.R .multidot.N' mod R 
R.sub.R =R.sup.2 mod N. 
In this case, the output P indicated by Equation (A-4) satisfies the 
relation 0.ltoreq.P&lt;2N on the basis of the first embodiment, and 
0.ltoreq.R.sub.R &lt;N&lt;2N by definition. Accordingly, each parameter of 
Equation (A-5) also satisfies the conditions of the first embodiment, and 
therefore modular multiplication Q can be performed by a modular 
multiplication circuit whose construction is identical with that of the 
first embodiment, which implements the Montgomery method, on the basis of 
the output value P and set value R.sub.R. 
FIG. 4 is a diagram showing an example of the configuration of a modular 
multiplication circuit for obtaining the output Q in the second 
embodiment. Here the output value Q is obtained by an arrangement in which 
two of the above-mentioned modular multiplication circuits 100 are 
serially connected as shown. To facilitate the description, thereof the 
second stage of the modular multiplication circuit is designated by 
reference numeral 100'. Numeral 200 denotes a constant generator for 
generating RR obtained from the parameters N and R. The output R.sub.R is 
fed into the modular multiplication circuit 100'. When the output P of the 
modular multiplication circuit 100, which is obtained by the inputs A and 
B, and the output R.sub.R of the constant generator 200 are inputted to 
the modular multiplication circuit 100', M2 is obtained from the 
multiplier 102 and the output Q represented by Equation (A-5) is obtained. 
According to the second embodiment, two of the modular multiplication 
circuits 100 are used to obtain the output Q. However, the invention is 
not limited to this embodiment. For example, an arrangement is possible in 
which reliance is placed upon one modular multiplication circuit 100 by 
using a selector 301 and a selector 302, as shown in FIG. 5. 
FIG. 5 is a block diagram showing the configuration of a modification of 
the second embodiment. The selector 301 selects either the input value A 
or the output value (P) of the modular multiplication circuit 100, latches 
the selected value and outputs it to the modular multiplication circuit 
100. The selector 302 selects either the input value B or the output value 
(R.sub.R) of the constant generator 200, latches the selected value and 
outputs it to the modular multiplication circuit 100. A select signal 303, 
which is generated by a CPU or other suitable circuit (not shown), is a 
signal which changes over the selectors 301, 302. The select signal 303 
causes the selectors 301, 302 to select and latch the respective input 
values A, B at the timing at which the input values A, B are accepted. 
Accordingly, the modular multiplication circuit 100 produces the output 
value P. Next, in response to the select signal 303, the selectors 301, 
302 select and latch the output value P and constant R.sub.R, 
respectively. As a result, the inputs to the modular multiplication 
circuit 100 at this time are the output value P and the constant R.sub.R, 
and therefore the output value. Q is obtained from the modular 
multiplication circuit 100. 
By using the above-described modular multiplication circuit in the 
encryption system shown in FIG. 1, it is possible to construct an 
encryption system capable of executing modular multiplication efficiently. 
Thus, in accordance with each of the foregoing embodiments, modular 
multiplication can be executed while making the ranges of the input and 
output values of the Montgomery method the same. As a result, it is 
possible to execute efficiently an operation based upon repetition of the 
Montgomery method, and various encryption systems using modular 
multiplication that utilizes the Montgomery method can be constructed 
efficiently. Further, since Equations (A-2).about.(A-5) are indicative of 
integral operations, the arithmetic circuitry and techniques for realizing 
modular multiplication are not limited to those of the foregoing 
embodiment. For example, it is obvious that this can be realized by 
carrying out the arithmetic operations by software using a CPU or the 
like. 
Thus, in accordance with the embodiments as described above, modular 
multiplication represented by P=A.multidot.B.multidot.R.sup.-1 mod N can 
be executed, without changing the ranges of the input and output values, 
by using the Montgomery method. Accordingly, there is obtained an 
encryption device in which encryption using modular multiplication is 
performed efficiently. 
Furthermore, modular multiplication represented by Q=A.multidot.B and N can 
be executed efficiently by the Montgomery method, and there is obtained an 
encryption device in which encryption using modular multiplication is 
performed efficiently. 
&lt;Third Embodiment&gt; 
A method of generating pseudorandom numbers according to a third embodiment 
makes it possible to eliminate the operation of Equation (B-13) by using 
.alpha..sub.i, which is obtained directly by 
EQU .alpha..sub.i =lsb(y.sub.i) (i=0, 1, 2, . . . ) (B-17) 
from y.sub.i of Equation (B-12), as a cryptologically secure Sequence of 
pseudorandom numbers. The method raises the speed at which pseudorandom 
numbers are generated without detracting from the security of the 
outputted random numbers. 
The security of pseudorandom number generation using Equation (B-1) 
utilizes the fact that it is very difficult to obtain b.sub.i from 
X.sub.i+1, namely the fact that b.sub.i is a hard core bit of X.sub.i+1. A 
case in which pseudorandom numbers are generated using Equations (B-11), 
(B-17) also is such that it is very difficult to obtain .alpha..sub.i from 
y.sub.i+1, which is the result of multiplying X.sub.i+1 by a certain 
constant R. In other words, since .alpha..sub.i is a hard core bit of 
y.sub.i+1, the security of pseudorandom number generation using Equations 
(B-11) and (B-17) also is the same as that of pseudorandom number 
generation using Equation (B-1). 
In accordance with this embodiment, as described above, it is possible to 
generate a sequence of pseudorandom numbers having the same degree of 
security as that of Equation (B-1) at higher speed or with circuitry of a 
smaller scale without executing the processing of Equation (B-13). 
Generation/reproduction of communication data can be performed at high 
speed using the method of this embodiment. 
The fact that the security of pseudorandom number generation using 
equations (B-11) and (B-17) is the same as that of pseudorandom number 
generation using Equation (B-1) will be proven. First, however, the 
symbols used will be simply defined. For the details, see "Modern 
Cryptographic Theory" [by Shinichi Ikeno and Kenji Koyama, published in 
1986, Denshi Joho Tsushin Gakkai, pp. 14.about.15, 95.about.96) 
.cndot.Quadratic residue 
When there is a solution to X.sup.2 .ident.c (mod p), c is the quadratic 
residue of p. When there is no solution, c is the quadratic non-residue. 
.cndot.Legendre symbol (x/p): 
When p is a prime number and X.noteq.0 (mod p) holds, we have 
##EQU4## 
.cndot.Z*.sub.N : 
relatively prime with respect to N; an integer in the range of from 0 to 
N-1 
Jacobi symbol (x/N): 
With respect to x.epsilon.Z*.sub.N and N=p.multidot.q (where p, q are prime 
numbers), the Jacobi symbol (x/N) is represented by the following using 
the Legendre symbol (x/p): 
EQU (x/N)=(x/p) (x/q) 
EQU .cndot.Z*.sub.N (+1)={x.epsilon.Z*.sub.N .vertline.(x/N)=1} 
EQU .cndot.Z*.sub.N (-1)={x.epsilon.Z*.sub.N .vertline.(x/N)=1} 
EQU .cndot.Q.sub.1 ={x.epsilon.Z*.sub.N .vertline.(x/p)=(x/q)=1} 
EQU .cndot.Q.sub.2 ={x.epsilon.Z*.sub.N .vertline.(x/p)=(x/q)=-1} 
EQU .cndot.Q.sub.3 ={x.epsilon.Z*.sub.N .vertline.(x/p)=-(x/q)=1} 
EQU .cndot.Q.sub.4 ={x.epsilon.Z*.sub.N .vertline.(x/p)=-(x/q)=-1}. 
Illustrating that the security of pseudorandom number generation using 
Equations (B-11) and (B-17) is the same as the security of pseudorandom 
number generation using Equation (B-1) is equivalent to proving the 
following proposition: 
[Proposition] 
"If .alpha..sub.i can be inferred correctly from the pseudorandom number 
sequence .alpha..sub.i+1, .alpha..sub.i+2, . . . generated from Equations 
(B-11), (B-17), the quadratic residue thereof can be judged with respect 
to any c[c.epsilon.Z*.sub.N (+1)]." 
[Proof] 
When r.epsilon.Q.sub.1 holds, the following hold with respect to any c 
[c.epsilon.Z*.sub.N (+1)]: 
EQU b=R.multidot.c mod N 
EQU y.sub.i+1 =R.sup.-1 .multidot.b.sup.2 mod N 
and .alpha..sub.i+1, .alpha..sub.i+2, . . . are generated by Equations 
(B-11), (B-17), with y.sub.i+1 serving as an initial value. 
At this time we have 
EQU b.epsilon.Z*.sub.N (+1) 
EQU y.sub.i+1 .epsilon.Q.sub.1 
At this time, if we let the solution to 
EQU y.sub.i+1 =R.sup.-1 .multidot.z.sup.2 mod N 
EQU y.sub.i+1 .multidot.R=z.sup.2 mod N 
be Z.sub.j (j=1, 2, 3, 4) (where Z.sub.j .epsilon.Q.sub.j), then 
EQU .alpha..sub.i =lsb(z.sub.1) 
can be predicted from 
EQU Z.sub.1 .ident.-Z.sub.2 (mod N) 
EQU Z.sub.3 .ident.-Z.sub.4 (mod N) 
by assumption. Accordingly, 
if .alpha..sub.i =lsb (b) holds, then b.epsilon.Q.sub.1, at which time 
c.epsilon.Q.sub.1 holds; 
if .alpha..sub.1 .noteq.lsb (b) holds, then b.epsilon.Q.sub.2, at which 
time c.epsilon.Q.sub.2 holds. 
Similarly, the quadratic residue property of c can be judged also when 
R.epsilon.Q.sub.2, R.epsilon.Q.sub.3, R.epsilon.Q.sub.4 hold. 
Q.E.D. 
FIG. 6 is a diagram showing the configuration of a pseudorandom number 
generator 1101 according to this embodiment. The pseudorandom number 
generator 1101 comprises a quadratic-residue arithmetic unit 1102 and a 
logical operation unit 1103. 
The quadratic-residue arithmetic unit 1102 performs the operations, which 
are indicated by the following equations, in the form of a chain to 
generate y.sub.1, y.sub.2 from the initial value y.sub.0, N, which is the 
modulus of modular multiplication, and an arbitrary constant R, which is a 
relatively prime number with respect to N: 
EQU y.sub.i+1 =R.sup.-1 .multidot.y.sub.i.sup.2 mod N (i=0, 1, 2, . . . )(B-18) 
EQU N=p.multidot.q (B-19) 
where p, q are prime numbers of p.ident.q.ident.3 (mod 4). 
Further, R is an arbitrary number which is relatively prime with respect to 
N. 
The y.sub.1, y.sub.2, . . . y.sub.i+1 generated are outputted sequentially 
on output line 1105. 
The operational method represented by the foregoing equations is referred 
to as the Montgomery method, as mentioned earlier. According to the 
Montgomery method, the operations indicated by the following equations are 
actually performed in order to obtain the computational result y.sub.i+1. 
EQU y.sub.i+1 =(y.sub.i.sup.2 +M.multidot.N)/R(i=0, 1, 2, . . . )(B-20) 
where 
EQU M=y.sub.i.sup.2 -N' mod R (B-21) 
EQU N'=-N.sup.-1 mod R (B-22) 
Since N is an odd number, R and N are relatively prime integers if 
R=2.sup.t holds (where t is an arbitrary integer). In this case, division 
by R and a residual operation do not necessitate actual operations and 
y.sub.i+1 can be computed at high speed by multiplication and addition. 
In a case where the quadratic-residue arithmetic unit 1102 is constructed 
of hardware, for example, the operation based upon the Montgomery method 
can readily be executed by providing an adder, a multiplier and a basic 
arithmetic unit such as a shifter which performs a bit shift for division 
by R and a residual operation. Furthermore, use can be made of a 
Montgomery arithmetic circuit illustrated in the literature "Exponential 
Algorithm and Systolic Array Using the Montgomery Method" (Iwamura, 
Matsumoto, Imai; vol. 92, No. 134, pp. 49.about.54, 1992). 
The values of y.sub.1, y.sub.2, . . . outputted sequentially on output line 
1105 of the quadratic-residue arithmetic unit 1102 enter the 
logical-operation unit 1103. The latter extracts an arbitrary bit (or 
bits) in a range of lower-order log.sub.2 n (where n represents the number 
of digits of N in binary notation) bits of each of the entered y.sub.1, 
y.sub.2 and outputs these bits as a pseudorandom number on output line 
1106. For example, all of the lower-order log.sub.2 n bits may be 
outputted as a pseudorandom number or only the least significant bit may 
be outputted as a pseudorandom number. 
In a case where the logical operation unit 1103 is constituted by hardware, 
use can be made of a parallel-input, serial-output shift register which 
latches the entered y.sub.i (i=1, 2, . . . ) in parallel and outputs, in 
serial form, the lower-order log.sub.2 n bits. 
A case will now be described in which the above-described method of 
generating pseudorandom numbers is realized by software. 
FIG. 7 is a diagram showing the configuration of a data processor 115 in 
which a program for generating pseudorandom numbers has been loaded in 
order to realize the pseudorandom number generating method of the third 
embodiment by means of software. Here a CPU 110 controls the overall data 
processor 115 in which a program for generating pseudorandom numbers has 
been loaded. A keyboard 111 is for entering a command which starts the 
pseudorandom number generating program as well as the values of various 
parameters for the pseudorandom number generating program. The 
pseudorandom number generating program according to this embodiment is 
stored in a ROM 113 in advance. The program is executed by the CPU 110 
while the it is being read out. A RAM 114 is a working area used to 
execute the pseudorandom number generating program and stores the results 
of generating the pseUdorandom numbers. A communication interface 116 
encrypts an input text by using the pseudorandom numbers stored in the RAM 
114 and outputs the encrypted text on a communication line. 
FIG. 8 is a flowchart for describing the processing of the pseudorandom 
number generating program. This processing will now be described with 
reference to the flowchart. The basis of the pseudorandom number 
generating program is the execution of the operations of Equations 
(B-7).about.(B-9). 
At step S1, prime numbers which are 3 (mod 4) are selected arbitrarily and 
set as p, q. The operation p.multidot.q is performed and the result is set 
as N. Arbitrary numbers are set as t and R, which are relatively prime 
with respect to N and satisfy R=2.sup.t. In addition, "-N.sup.-1 mod R" is 
computed and the result is set as N'. 
An arbitrary initial value for generating random numbers is set as y.sub.0 
at step S2. 
The operation -N.sup.-1 mod 2.sup.t is performed at step S3 and the result 
is set as N'. 
Next, i, which indicates the number of repetitions of random number 
generation, is initialized to "0" at step S4. 
This is followed by step S5, at which "y.sub.i.sup.2 .multidot.N' mod 
2.sup.t " is computed and the result set as M. Although here the 
processing for dividing "y.sub.i.sup.2 .multidot.N'" by 2.sup.t is 
fundamental, the division can be executed at high speed since it will 
suffice if "y.sub.i.sup.2 .multidot.N'" is processed by a "t" bit shift. 
Next, at step S6, the operation "(y.sub.i.sup.2 +M.multidot.N)/2.sup.t " is 
performed and the result is set as y.sub.i+1. This division also can be 
processed at high speed since the "t" bit shift is fundamental. 
Next, at step S7, a series of bits of a prescribed number at prescribed 
positions is extracted from y.sub.i and set as rand(i). It should be noted 
that rand(i) is a one-dimensional array. 
The value of i is compared with a prescribed End value at step S8 and the 
program proceeds to step S9 if the value of i is less than the End value. 
It should be noted that the End value is has been set to correspond to the 
quantity of sequences of random numbers desired to be generated. This may 
be set from the keyboard 111 or by a separate program which calls the 
pseudorandom number generating program. 
This is followed by step S9, at which i is counted up in order to generate 
the next random number. Processing from step S5 onward is then executed 
again to continue the generation of subsequent random numbers. 
By executing the above-described processing, a series of pseudorandom 
number sequences is generated in the array area rand. 
The foregoing illustrates a method of generating pseudorandom numbers by 
the Montgomery method. In general, however, a modular multiplication can 
be performed with respect to a number C.multidot.X.sup.2 obtained by 
multiplying the result X.sup.2 of a quadratic operation by an arbitrary 
constant C, and pseudorandom numbers can be generated from a prescribed 
number of bits of y=C.multidot.X.sup.2 mod N obtained as a result. FIG. 9 
is a diagram showing the configuration of a pseudorandom number generator 
120 according to a modification of the third embodiment. The pseudorandom 
number generator 120 comprises a quadratic-residue arithmetic unit 121 and 
a logical operation unit 122. 
The quadratic-residue arithmetic unit 121 performs the operations, which 
are indicated by the following equations, in the form of a chain to 
generate y.sub.1, y.sub.2 from the initial value y.sub.0 and the arbitrary 
constant C: 
EQU y.sub.i+1 =C.multidot.y.sub.i.sup.2 mod N (i=0, 1, 2, . . . ) 
EQU N=p.multidot.q 
where p, q are prime numbers of p.ident.q.ident.3 (mod 4). 
Since the operations indicated in the quadratic-residue arithmetic unit 
121, namely 
EQU y.sub.i.sup.2 mod N 
EQU C.multidot.y.sub.i.sup.2 mod N 
are both modular multiplication operations, it will suffice if the 
quadratic-residue arithmetic unit 121 is arranged to perform modular 
multiplication operations. In a case where the unit is constituted by 
hardware, it is also possible to use a modular multiplication arithmetic 
circuit illustrated in the literature "Method of Constructing RSA 
Encryption Device by Parallel Processing" (Iwamura, Matsumoto, Imai; 
Denshi Joho Tsushin Gakkai Ronbun A, vol. J75-A, No. 8, pp. 
1301.about.1311, 1992). The output of the quadratic-residue arithmetic 
unit 121 enters the logical operation unit 122. The latter generates and 
outputs a sequence of random numbers from an arbitrary bit (or bits) in a 
range of lower-order log.sub.2 n (where n represents the number of digits 
of N in binary notation) bits of each of the entered y.sub.1, y.sub.2 . . 
. . 
The logical operation unit 122 is capable of outputting, as a pseudorandom 
number, arbitrary bits in a range of lower-order log.sub.2 n bits of each 
of the entered y.sub.1, y.sub.2, . . . . For example, all of the 
lower-order log.sub.2 n bits may be outputted as a pseudorandom number or 
only the least significant bit may be outputted as a pseudorandom number. 
In accordance with the third embodiment, as described in detail above, in a 
case where cryptologically secure pseudorandom numbers are generated by 
the Montgomery method, prescribed bits of y.sub.i obtained by Equation 
(B-11) are used as a pseudorandom number, thereby making it possible to 
dispense with the operation of Equation (B-13), which is necessary in the 
prior art, without detracting from security. By adopting this arrangement, 
a sequence of pseudorandom numbers having the same degree of security as 
that of the prior art can be generated at a high speed or by circuitry of 
a smaller scale. 
Thus, as described above, generation/reproduction of communication data can 
be performed at a high speed using the pseudorandom numbers generated by 
the method and apparatus of this embodiment. 
&lt;Fourth Embodiment&gt; 
The purpose of the pseudorandom number generator according to the fourth 
embodiment is to eliminate the operation indicated by equation (*3) of the 
above-described Algorithm 2, thereby making it possible to generate a 
sequence of a pseudorandom numbers at a higher speed or by circuitry of a 
smaller scale while maintaining a degree of security the same as that of 
Equation (B-3). 
First, the following is an Algorithm 3 for a case in which the operation of 
equation (*3) of Algorithm 2 has been eliminated: 
##EQU5## 
The series y.sub.i (i=0, 1, 2, . . . , s) obtained by executing Algorithm 3 
is indicated by Equation (B-15). A pseudorandom number generator according 
to the fourth embodiment for a case in which equation (*3) of Algorithm 2 
has been eliminated uses .alpha..sub.i obtained by 
EQU .alpha..sub.i =lsb(y.sub.i) (i=0, 1, 2, . . . ) (B-23) 
from y.sub.i of Equation (B-15) as a cryptologically secure pseudorandom 
number. 
The security of pseudorandom number generation using Equations (B-15) and 
(B-23) will be considered. The security of pseudorandom number generation 
using Equation (B-3) utilizes the fact that it is very difficult to obtain 
bi from x.sub.i+1, namely the fact that b.sub.i is a hard core bit of 
x.sub.i+1. The series y.sub.i (i=0, 1, 2, . . . ) obtained by Equation 
(B-15) are values obtained by multiplying the series x.sub.i (i=0, 1, 2, . 
. . ), which is obtained by Equation (B-3), by the constant R and taking 
the residue modulo N [see Equation (B-16)]. Accordingly, if it is very 
difficult to obtain b.sub.i =lsb (x.sub.i) from x.sub.i+1, then it will 
also be very difficult to obtain .alpha..sub.i =lsb 
(y.sub.i)[lsb(R.multidot.x.sub.i mod N)] from y.sub.i+1 
(=R.multidot.x.sub.i+1 mod N), which is the result of multiplying 
x.sub.i+1 by the constant R and taking the residue modulo N. In other 
words, since .alpha..sub.i is a hard core bit of y.sub.i+1, the security 
of pseudorandom numbers generation using Equations (B-15) and (B-23) also 
is the same as that of pseudorandom number generation using Equation 
(B-3). 
A processing flowchart for executing Algorithm 3 will now be described with 
reference to FIG. 10. 
Values of x.sub.0, e, N, s and R are entered at step S10. Here s is the 
number of repetitions of the modular multiplication. Further, R satisfies 
R=2.sup.t (where t is an integer). 
The operation Mont (x.sub.0, R.sub.R) is performed at step S11 and the 
result is set as y.sub.0. Here Mont (x.sub.0, R.sub.R) is a function, in 
which x.sub.0, R.sub.R are variables, for performing the operations of 
Equations (B-7), (B-8) and (B-9). It should be noted that Equation (B-9) 
can be computed in advance and N' is treated as a constant. In actuality, 
therefore, the operations of Equations (B-7), (B-8) are performed to 
obtain Mont (x.sub.0, R.sub.R). In the operations of Equations (B-7), 
(B-8), modulus R is expressed by 2.sup.t beforehand and therefore the 
required division can be executed by a bit-shift. 
A counter i of repetitions of the residual operation first is initialized 
to "0" at step S12. Whenever this step is entered, the counter i is 
incremented and processing proceeds to the next step. The count-up 
operation is performed up to s. 
Next, at step S13, the operation Mont (1, R.sub.R) is performed and the 
result is set as y.sub.i+1. 
This is followed by step S14, at which a bit pointer j for pointing to each 
bit of e is first set at k. Here k is the bit length of e and is assumed 
to be set in advance. Whenever this step is entered, a bit pointer j is 
decremented and processing proceeds to the next step. The countdown 
proceeds to 1. 
At step S15, it is determined whether the j-th bit e.sub.j designated by 
the bit pointer j is "1" or not. If the bit e.sub.j is "1", the program 
proceeds to step S16, the operation Mont (y.sub.i+1, y.sub.i) is performed 
and the result is set as y.sub.i+1. If the bit e.sub.j is "0", the program 
proceeds to step S17. 
It is determined at step S17 whether the bit pointer j is greater than "1" 
or not. If j is not greater than or equal to "1", then the program 
proceeds to step S19. If j is greater than "1", the program proceeds to 
step S18, the operation "Mont (y.sub.i+1, y.sub.i+1)" is performed and the 
result is set as y.sub.i+1. 
Next, at step S19, it is determined whether the bit pointer j is a value in 
the interval "k.about.1". If j is a value in this interval, then the 
program returns to the residual processing from step S14 onward. If j is 
outside this interval, then the program proceeds to step S100. 
At step S100, y.sub.i+1 (i=0, 1, 2, . . . ) is stored in a memory device or 
the like. 
Next, at step S101, it is determined whether the counter i is a value in 
the interval "0.about.s". If i is a value in this interval, then the 
program returns to residual processing from step S12 onward and the next 
residual processing operation is performed. If i is outside this interval, 
then residual processing is terminated. 
FIG. 11 is a diagram showing the configuration of a pseudorandom number 
generator 193 according to the fourth embodiment of the present invention. 
A modular exponentiation arithmetic unit 190 performs the following 
operation, in the form of a chain, using the initial value x.sub.0, N, 
which is the modulus of the modular exponentiation, the arbitrary constant 
R, which is a relatively prime number with respect to N, and the power e, 
and generates y.sub.1, y.sub.2, . . . : 
EQU y.sub.0 =R.multidot.x.sub.0 mod N (B-24) 
EQU y.sub.i+1 =R.sup.-(e-1) .multidot.y.sub.1.sup.e mod N (i=0, 1, 2, . . . 
)(B-25) 
Here N=p.multidot.q holds, where p, q are prime numbers and e (.gtoreq.2) 
is an arbitrary constant. 
The modular exponentiation arithmetic unit 190 executes Algorithm 3. The 
inputs to the modular exponentiation arithmetic unit 190 are the initial 
value x.sub.0, the power e, the modulus N of the arithmetic operation, the 
constant R, R.sub.R =R.sup.2 mod N, and the number of repetitions s with 
regard to i. The modular exponentiation arithmetic unit 190 which 
successively outputs y.sub.i+1 (i=0, 1, . . . , s), comprises an input 
buffer 194, a decision unit 196, a Montgomery operation unit 195, a memory 
198 and an output unit 197. The operating procedure of the modular 
exponentiation arithmetic unit 190 will now be described. 
(1) First, x.sub.0, e, n, R, R.sub.R, S are fed into the input buffer 194, 
whence e, s are input to the decision unit 196. The decision unit 196 
separates e into k bits of [e.sub.k, e.sub.k-1, . . . e.sub.2, e.sub.1 ]. 
Furthermore, i=0, j=k are set in two counters (not shown) with respect to 
i, j provided in the decision unit 196. The values of R, N fed in the 
input buffer 194 are set in the Montgomery operation unit 195, and the 
initial value x.sub.0 and R.sub.R of the Montgomery operation are held in 
the memory 198. 
(2) On the basis of x.sub.0, R.sub.R in memory 198, y.sub.0 is calculated 
in the Montgomery operation unit 195 and is held in the memory 198 as the 
initial value of the Montgomery operation together with y.sub.1 =R. 
(3) With respect to i=0, j=k, the decision circuit renders the decisions 
e.sub.j =1, j&gt;1 and outputs an address signal to the memory 198 in 
dependence upon the decisions. The memory 198 holds y.sub.i and y.sub.i+1, 
but y.sub.i+1 is updated from time to time by the output of the Montgomery 
operation unit 195. The memory 198 stores the output y.sub.i+1 of the 
Montgomery operation in response to the address signal from the decision 
unit 196. Further, in dependence upon the address signal from the decision 
unit 196, the content of the memory 198 is read out and y.sub.i+1 or 
y.sub.i enters the Montgomery operating unit 195. The Montgomery operation 
unit 195 performs the Montgomery operation in accordance with the output 
from the memory 198. The counter for j in the decision unit 196 is 
decremented by one count and this procedure is repeated until j=0 is 
attained. 
(4) When j=0 is established, the decision unit 196 issues an enable signal 
to the output unit 197, which latches y.sub.i+1 prevailing at the time of 
j=0. The output unit 197 outputs the latched y.sub.i+1 as the result of 
the modular exponentiation operation and, at the same time, y.sub.i+1 is 
held in the memory 198 as the next input of the Montgomery operation unit 
195. The counter for i in the decision unit 196 is incremented by one 
count, and steps (3), (4) of this procedure are repeated until i=s is 
attained. 
(5) The procedure is terminated. 
The output of the modular exponentiation arithmetic unit 190 enters the 
logical operation unit 191. The latter generates and outputs random 
numbers from an arbitrary bit (or bits) in a range of lower-order 
log.sub.2 n (where n represents the number of digits of N in binary 
notation) bits of each of the entered y.sub.1, y.sub.2 . . . . 
The logical operation unit 191 is capable of outputting, as a pseudorandom 
number, arbitrary bits in a range of lower-order log.sub.2 n bits of each 
of the entered y.sub.1, y.sub.2, . . . . For example, all of the 
lower-order log.sub.2 n bits may be outputted as a pseudorandom number or 
only the least significant bit may be outputted as a pseudorandom number. 
In a case where the logical operation unit is constituted by hardware, for 
example, it can be made by using a parallel-input, serial-output shift 
register which latches the entered y.sub.i (i=1, 2, . . . ) in parallel 
and sequentially outputs, in serial form, the lower order log.sub.2 n 
bits. 
In accordance with the fourth embodiment, as described in detail above, use 
is made of the computation procedure of Algorithm 3, which dispenses with 
the processing of equation (*3), which is necessary in the prior art in 
Algorithm 2. As a result, a sequence of pseudorandom numbers having the 
same degree of a security as that of Equation (B-3) can be generated at 
high speed or by circuitry of smaller scale. 
Thus, as described above, generation/reproduction of communication data can 
be performed at a high speed using the pseudorandom numbers generated by 
the method and apparatus of the fourth embodiment. 
&lt;Fifth Embodiment&gt; 
The purpose of the pseudorandom number generator according to the fifth 
embodiment is to eliminate both of the operations indicated by equation 
(*1) and equation (*3) of the above-described Algorithm 2, thereby making 
it possible to generate a sequence of pseudorandom numbers at a higher 
speed or by circuitry of smaller scale while maintaining a degree of 
security the same as that of Equation (B-3). 
Algorithm 4 of the fifth embodiment is as follows: 
##EQU6## 
The series y.sub.i (i=0, 1, 2, . . . , s) obtained by executing this 
algorithm is represented by the following using R, which is relatively 
prime with respect to N: 
EQU y.sub.0 =x.sub.0 mod N (B-26) 
EQU y.sub.i+1 =R.sup.-(e-1) .multidot.y.sub.i.sup.e mod N (i=0, 1, 2, . . . 
)(B-27) 
In this case, when the sequence x.sub.i (i=0, 1, 2, . . . ) generated by 
Equation (B-3) and the sequence y.sub.i (i=0, 1, 2, . . . ) generated by 
Equation (B-27) are compared, we have 
EQU y.sub.i =R**(1-e.sup.i).multidot.x.sub.i mod N (i=0, 1, 2, . . . ).(B-28) 
Here "R**(1-e.sup.i)" signifies the (1-e.sup.i)th power of R. 
A pseudorandom generator according to the fifth embodiment in which 
equations (*1), (*3) in Algorithm 2 are eliminated using a.sub.i ' 
obtained in accordance with 
EQU a.sub.i '=lsb(y.sub.i) (i=0, 1, 2, . . . ) (B-29) 
from y.sub.i of Equation (B-27) as a cryptologically secure sequence of 
pseudorandom numbers. 
In terms of security, this case also can be said to be the same as that in 
which equation (*3) in Algorithm 2 is eliminated. The series y.sub.i (i=0, 
1, 2, . . . ) obtained by Equation (B-27) are values obtained by 
multiplying the series x.sub.i (i=0, 1, 2, . . . ), which is obtained by 
Equation (B-3), by the constant R**(1-e.sup.i+1) and taking the residue at 
N [See Equation (B-28)]. 
Accordingly, if it is very difficult to obtain b.sub.i =lsb (x.sub.i) from 
x.sub.i+1, then it will also be very difficult to obtain 
EQU a.sub.i '=lsb(y.sub.i) (=lsb((R**(1-e.sup.i+1).multidot.x.sub.i) mod N)) 
from 
y.sub.i+1 (=(R**(1-e.sup.i+1).multidot.x.sub.i+1) mod N), which is the 
result of multiplying x.sub.i+1 by the constant R**(1-e.sup.i+1) and 
taking the residue modulo N. In other words, since a.sub.i ' is a hard 
core bit of y.sub.i+1, the security of pseudorandom number generation 
using Equations (B-27) and (B-29) also is the same as that of pseudorandom 
number generation using Equation (B-3). 
A flowchart for executing Algorithm 4 will now be described with reference 
to FIG. 12. 
Values of y.sub.0, e, N, s and R are entered at step S200. Here s is the 
number of repetitions of the residual operation. 
A counter i of repetitions of the residual operation first is initialized 
to "0" at step S201. Whenever this step is entered, the counter i is 
incremented and processing proceeds to the next step. The count-up 
operation is performed up to s. 
Next, at step S202, R is substituted for y.sub.i+1. 
This is followed by step S203, at which a bit pointer j for pointing to 
each bit of e is first set at k. Here k is the bit length of e and is 
assumed to be set in advance. Whenever this step is entered, a bit pointer 
j is decremented and processing proceeds to the next step. The countdown 
proceeds to 1. 
At step S204, it is determined whether the j-th bit e.sub.j designated by 
the bit pointer j is "1" or not. If the bit e.sub.j is "1", the program 
proceeds to step S205, the operation Mont (y.sub.i+1, y.sub.i) is 
performed and the result is set as y.sub.i+1. If the bit e.sub.j is "0", 
the program proceeds to step S206. 
It is determined at step S206 whether the bit pointer j is greater than "1" 
or not. If j is not greater than "1", then the program proceeds to step 
S208. If j is greater than or equal to "1", the program proceeds to step 
S207, the operation "Mont (y.sub.i+1, y.sub.i+1)" is performed and the 
result is set as y.sub.i+1. 
Next, at step S208, it is determined whether the bit pointer j is a value 
in the interval "k.about.1". If j is a value in this interval, then the 
program returns to the residual processing from step S203 onward. If j is 
outside this interval, then the program proceeds to step S209. 
At step S209, y.sub.i+1 (i=0, 1, 2, . . . ) is stored in a memory device or 
the like. 
Next, at step S210, it is determined whether the counter i is a value in 
the interval "0.about.s". If i is a value in this interval, then the 
program returns to modular multiplication from step S201 onward and the 
next residual processing operation is performed. If i is outside this 
interval, then residual processing is terminated. 
FIG. 13 is a diagram showing the configuration of a pseudorandom number 
generator 183 according to the fifth embodiment of the present invention. 
The pseudorandom number generator 183 has a modular exponentiation 
arithmetic unit 180 and a logical operation unit 181. The modular 
exponentiation arithmetic unit 180, which executes processing in 
accordance with Algorithm 4, has an input buffer 184 whose inputs are the 
initial value y.sub.0, N, which is the modulus of the residual operation, 
the arbitrary constant R, which is a relatively prime number with respect 
to N, and the power e. These inputs are made using the keyboard 11. Upon 
receiving the values of the inputs N, R, y.sub.0 and e from the input 
buffer 184, a Montgomery operation unit 185 performs an operation 
corresponding to the following equation to successively obtain a sequence 
of numbers y.sub.i+1 (i=0, 1, 2, . . . ), namely y.sub.1, y.sub.2, . . . : 
EQU y.sub.i+1 =R.sup.-(e-1) .multidot.y.sub.i.sup.e mod N (i=0, 1, 2, . . . 
)(B-30) 
where 
N=p.multidot.q 
p, q are prime numbers 
e: an arbitrary constant which satisfies e.gtoreq.2. 
It should be noted that p, q are assumed to have been set in advance and 
that N (=p.multidot.q) is assumed to have been computed in advance. The 
actual operational method used by the Montgomery operation unit 185 is not 
one in which the above equation is computed directly. Rather, the unit 185 
applies the Montgomery method and performs an operation based upon 
equivalent equations indicated by Equations (B-7).about.(B-9). 
More specifically, the operation Mont (u,v) based upon the Montgomery 
method used in Algorithm 4 performs the operations of Equations 
(B-7).about.(B-9) mentioned above. 
Since N is an odd number, R and N are relatively prime integers if 
R=2.sup.t holds (where t is an arbitrary integer). In this case, division 
by R and a residual operation are essentially unnecessary operations and 
Mont (u,v) can be computed at a high speed by multiplication and addition. 
Accordingly, a modular exponentiation operation capable of being 
implemented by repeated operations based upon the Montgomery method can be 
performed at a high speed as well. 
In a modular exponentiation operation, Algorithm 4 is executed. The inputs 
to the input buffer 184 of the modular exponentiation arithmetic unit 180 
are the initial value y.sub.0 (=x.sub.0), the power e, the modulus N of 
the operation, the constant R and the number s of repeated operations with 
respect to i. An output unit 187 of the modular exponentiation arithmetic 
unit 180 successively outputs y.sub.i+1 (i=0, 1, . . . , s). The modular 
exponentiation arithmetic unit 180 includes the input buffer 184, a 
decision unit 186, the Montgomery operation unit 185, a memory 188 and an 
output unit 187. The operating procedure of the modular exponentiation 
arithmetic unit 180 will now be described. 
(1) First, y.sub.0 =(x.sub.0), e, n, R, s are fed into the input buffer 
184, whence e, s are input to the decision unit 186. The latter separates 
e into k bits of [e.sub.k, e.sub.k-1, . . . e.sub.2, e.sub.1 ]. 
Furthermore, i=0, j=k are set in two counters with respect to i, j 
provided in the decision unit 186. The values of R, N fed in the input 
buffer 184 are set in the Montgomery operation unit 185, and the initial 
value y.sub.0 and y.sub.1 =R of the Montgomery operation are held in the 
memory 188. 
(2) With respect to i=0, j=k, the decision circuit renders the decisions 
e.sub.j =1, j&gt;1 and outputs an address signal to the memory 188 in 
dependence upon the decisions. The memory 188 holds y.sub.i and y.sub.i+1, 
but y.sub.i+1 is updated from time to time by the output of the Montgomery 
operation unit 185. The memory 188 stores the output y.sub.i+1 of the 
Montgomery operation unit 185 in response to the address signal from the 
decision unit 186. Further, in dependence upon the address signal from the 
decision unit 186, the content of the memory 188 is read out and y.sub.i+1 
or y.sub.i enters the Montgomery arithmetic unit 185. The Montgomery 
arithmetic unit 185 performs the Montgomery operation in accordance with 
the output from the memory 188. The counter for j in the decision unit 186 
is decremented by one count and this procedure is repeated until j=0 is 
attained. 
(3) If j=0 is established, the decision unit 186 issues an enable signal to 
the output unit 187, which latches y.sub.i+1 prevailing at the time of 
j=0. The output unit 187 outputs the latched y.sub.i+1 as the result of 
the modular exponential operation and, at the same time, y.sub.i+1 is held 
in the memory 188 as the next input of the Montgomery arithmetic unit 185. 
The counter for i in the decision unit 186 is incremented by one count, 
and steps (2), (3) of this procedure are repeated until i=s is attained. 
(4) The procedure is terminated. 
The input buffer 184 is constituted by a register for latching and holding 
each of the input values y.sub.0 (=x.sub.0), e, N and R. The decision unit 
186 can be constructed from a comparator for judging e.sub.j =1 and j&gt;1, a 
counter for counting i and j and a logic circuit for outputting an address 
designating signal and an enable signal. The memory 188 can be a RAM 
capable of being written/read at random, and the output unit 187 can be a 
register for latching and holding the output value of y.sub.i+1 in 
dependence upon the enable signal from the decision unit 186. 
In a case where the means for performing the Montgomery method is 
constituted by hardware, the basic components are an adder, a multiplier 
and a shifter which performs a bit shift in order to implement a modular 
multiplication operation based upon R. Furthermore, use can be made of a 
Montgomery arithmetic circuit illustrated in the literature "Exponential 
Algorithm and Systolic Array Using the Montgomery Method" (Iwamura, 
Matsumoto, Imai; Shingaku Giho, vol. 92, No. 134, pp. 49.about.54, 1992). 
The output of the modular exponentiation arithmetic unit 180 enters the 
logical operation unit 181. The latter generates and outputs pseudorandom 
numbers from an arbitrary bit (or bits) in a range of lower-order 
log.sub.2 n (where n represents the number of digits of N in binary 
notation) bits of each of the entered y.sub.1, y.sub.2 . . . . 
The logical operation unit 181 is capable of outputting, as a pseudorandom 
number, arbitrary bits in the range of lower-order log.sub.2 n bits of 
each of the entered y.sub.1, y.sub.2 . . . . For example, all of the 
lower-order log.sub.2 n bits may be outputted as a pseudorandom number or 
only the least significant bit may be outputted as a pseudorandom number. 
In a case where the logical operation unit is constituted by hardware, for 
example, use can be made of a parallel-input, serial-output shift register 
which latches the entered y.sub.i (i=1, 2, . . . ) in parallel and 
sequentially outputs, in serial form, the lower-order log.sub.2 n bits. 
In accordance with the fifth embodiment, as described in detail above, use 
is made of the computation procedure of Algorithm 4, which dispenses with 
the processing of equations (*1) and (*3), which are necessary in the 
prior art in Algorithm 2. As a result, a sequence of pseudorandom numbers 
having the same degree of security as that of Equation (B-3) can be 
generated at a high speed or by circuitry of a smaller scale. 
In this case, in addition to speeding up the modular multiplication 
operation based upon use of the Montgomery method, it is possible to 
dispense with a conversion for inputs and a conversion for obtaining an 
output as is necessary in Algorithm 2. As a result, an increase in the 
speed of overall operation can be expected. 
Thus, as described above, generation/reproduction of communication data can 
be generated by the method and apparatus of the fifth embodiment. 
&lt;Sixth Embodiment&gt; 
The third through fifth embodiments described above illustrate methods of 
generating pseudorandom numbers by the Montgomery method. In general, 
however, a residual operation can be applied to a number 
C.multidot.x.sup.e, which is obtained by multiplying the result x.sup.e of 
a power operation by an arbitrary constant C, and pseudorandom numbers can 
be generated from prescribed bits of y=C.multidot.x.sup.e mod N obtained 
as a result. 
FIG. 14 is a block diagram showing the configuration Of pseudorandom number 
generator 173 according to the sixth embodiment. A modular exponentiation 
arithmetic unit 170 performs the operation, which is indicated by the 
following equation, in the form of a chain to generate x.sub.1, x.sub.2 
from the initial value x.sub.0, N, which is the modulus of the residual 
operation, and the power e: 
EQU x.sub.i+1 =x.sub.i.sup.e mod N (i=0, 1, 2, . . . ) (B-31) 
where 
N=p.multidot.q 
p, q are prime numbers 
e (.gtoreq.2): an arbitrary constant. 
The modular multiplication unit 172 generates y.sub.1, y.sub.2, . . . y 
performing the following operation: 
EQU y.sub.i+1 =C.multidot.x.sub.i+1 mod N (i=0, 1, 2, . . . ) (B-32) 
from the input value x.sub.i+1 (i=0, 1, 2, . . . ) and N, which is the 
modulus of the residual operation. 
The modular exponentiation arithmetic unit 170 executes Algorithm 1. The 
inputs to the modular exponentiation arithmetic unit 170 are the initial 
value x.sub.0, the power e, the modulus N of the arithmetic operation and 
the number of repetitions s with regard to i. The modular exponentiation 
arithmetic unit 170, which successively outputs x.sub.i+1 (i=0, 1, . . . , 
s), comprises an input buffer 174, a decision unit 176, a modular 
multiplication unit 175, a memory 178 and an output unit 177. 
The operating procedure of the modular exponentiation arithmetic unit 170 
will now be described. 
(1) First, x.sub.0, e, N and s are fed into the input buffer 174, whence e, 
s are input to the decision unit 176. The latter separates e into k bits 
of [e.sub.k, e.sub.k-1, . . . e.sub.2, e.sub.1 ]. Furthermore, i=0, j=k 
are set in two counters (not shown) with respect to i, j provided in the 
decision unit 176. The values of R, N fed in the input buffer 174 are set 
in the modular multiplication unit 175, and the initial value x.sub.0 and 
x.sub.1 =1 of the modular multiplication operation are held in the memory 
178. 
(2) With respect to i=0, j=k, the decision unit 176 renders the decisions 
e.sub.j =1, j&gt;1 and outputs an address signal to the memory 178 in 
dependence upon the decisions. The memory 178 holds x.sub.i and x.sub.i+1, 
but x.sub.i+1 is updated from time to time by the output of the modular 
multiplication unit 175. The memory 178 stores the output x.sub.i+1 of the 
modular multiplication operation in response to the address signal from 
the decision unit 176. Further, in dependence upon the address signal from 
the decision unit 176, the content of the memory 178 is read out and 
x.sub.i+1 or x.sub.i is outputted to the modular multiplication unit 175. 
The modular multiplication unit 175 performs modular multiplication in 
accordance with the output from the memory 178. The counter for j in the 
decision unit 176 is decremented by one count and this procedure is 
repeated until j=0 is attained. 
(3) If j=0 is established, the decision unit 176 issues an enable signal to 
the output unit 177, which latches x.sub.i+1 prevailing at the time of 
j=0. The output unit 177 outputs the latched x.sub.i+1 as the result of 
the modular exponentiation operation and, at the same time, x.sub.i+1 is 
held in the memory 178 as the next input of the modular multiplication 
unit 175. The counter for i in the decision unit 176 is incremented by one 
count, and steps (2), (3) of this procedure are repeated until i=s is 
attained. 
(4) The procedure is terminated. 
The input buffer 174 is constituted by a register for latching and holding 
each of the input values x.sub.0, e, N and s. The decision unit 176 can be 
constructed from a comparator for judging e.sub.j =1 and j&gt;1, a counter 
for counting j and a logic circuit for outputting an address designating 
signal and an enable signal. The memory 178 can be a RAM capable of being 
written/read at random, and the output unit 177 can be a register for 
latching and holding the output value of x.sub.i+1 in dependence upon the 
enable signal from the decision unit 176. 
Thus, as set forth above, the modular exponentiation operation can be 
realized by repeating modular multiplication. In a case where the modular 
multiplication operation by the modular exponentiation operation unit 170 
and modular multiplication unit is implemented by hardware, for example, 
it is also possible to use a modular multiplication method illustrated in 
the literature "Method of Constructing RSA Encryption Device by Parallel 
Processing" (Iwamura, Matsumoto, Imai; Denshi Joho Tsushin Gakkai Ronbun 
A, vol. J75-A, No. 8, pp. 1301.about.1311, 1992). 
The output of a modular multiplication unit 172 enters a logical operation 
unit 171. The latter generates and outputs pseudorandom numbers from an 
arbitrary bit (or bits) in a range of lower-order log.sub.2 n (where n 
represents the number of digits of N in binary notation) bits of each of 
the entered y.sub.1, y.sub.2, . . . . 
The logical operation unit 171 is capable of outputting, as a pseudorandom 
number, arbitrary bits in a range of lower-order log.sub.2 n bits of each 
of the entered y.sub.1, y.sub.2, . . . . For example, all of the 
lower-order log.sub.2 n bits may be outputted as a pseudorandom number or 
only the least significant bit may be outputted as a pseudorandom number. 
Thus, as described above, generation/reproduction of communication data can 
be performed at high speed using the pseudorandom numbers generated by the 
method and apparatus of this embodiment. 
&lt;Seventh Embodiment&gt; 
As described thus far, pseudorandom numbers generated by the method of 
generating pseudorandom numbers set forth above is strongly resistant to 
analysis and, as a result, secure, encrypted communication can be realized 
by using these pseudorandom numbers in encryption. An application in 
encrypted communication using the random number generator of the foregoing 
embodiments will now be described in an encrypted communication network 
based upon encryption (stream encryption) in which an exclusive-OR 
operation is performed, bit by bit, between a communication text and 
random numbers. 
FIG. 15 is a diagram showing a common-key encrypted communication network 
130 in which a specific and secret encryption key is possessed by the 
subscribers to the network. The subscribers to the network are A, B, C, . 
. . , N. A communication network 134 makes possible communication among 
the subscribers A, B, C, . . . , N. Symbols K.sub.AB, K.sub.AC, . . . in 
the circles under the subscribers A, B, C, . . . , N signify encryption 
keys shared by subscribers. For example, symbols K.sub.AB, K.sub.AC, . . . 
indicate encryption keys shared by subscribers A-B, subscribers A-C, . . . 
, respectively. 
FIG. 16 is a block diagram showing the construction of a communication 
apparatus which includes an encryption device and a decryption device both 
using the random number generator of this embodiment. 
In FIG. 16, a random number generator 140 generates a sequence of 
pseudorandom numbers in accordance with any of the third through sixth 
embodiments described above. A gate 143 outputs the exclusive-OR between a 
communication text and a pseudorandom number outputted by the random 
number generator 140 and delivers the result of this operation as an 
encrypted text. On the other, an input encrypted text is applied to a gate 
149, which takes the exclusive-OR between this text and a pseudorandom 
number from the random number generator 140, thereby decoding the 
encrypted text into a communication text. 
FIG. 17 is a diagram showing secret communication between A and B in the 
encrypted communication system illustrated in FIGS. 15 and 16. 
In FIG. 17, encrypted communication from a receiver 145 used by a 
transmitting party A to a receiver 146 used by a receiving party B is 
carried out through the following procedure: 
(1) The transmitting party A sets all or part of the secret key K.sub.AB, 
which is shared with receiving party B, in the random number generator 140 
as the initial value thereof and generates a random-number sequence 
k.sub.i (141). 
(2) An exclusive-OR gate 143 computes, bit by bit, the exclusive-OR 
"m.sub.i (+) k.sub.i " between the random-number sequence k.sub.i (141) 
generated by the transmitting party A and a communication text m.sub.i 
(142) created in advance, and transmits the result, namely an encrypted 
text c.sub.i, to the receiver 146. 
(3) The receiving party B sets all or part of the secret key K.sub.AB, 
which is shared with transmitting party A, in a random number generator 
147 as the initial value thereof and generates a random-number sequence 
k.sub.i. 
(4) The receiving party B takes the exclusive-OR "c.sub.i (+) k.sub.i " 
between the generated random-number sequence k.sub.i and the received 
encrypted text c.sub.i (142) created in advance, whereby the output 
thereof is restored as the communication text m.sub.i (148). 
In accordance with this procedure, only the legitimate receiving party B 
knows the secret key K.sub.AB and therefore is capable of decrypting the 
received encrypted text into the original communication text. Other 
subscribers (C.about.N) do not know the secret key used at the time of the 
encrypted text and therefore cannot determine the content of the text. 
Secret communication is thus achieved. 
In a portable network in which an encryption key is not distributed 
beforehand as in FIG. 15 but is required to be owned jointly by the 
transmitting and receiving parties before encrypted communication, it is 
possible to realize encrypted communication through the same procedure if 
well-known key distribution is carried out. 
In the encrypted communication network illustrated in the seventh 
embodiment, a specific and secret key is shared by the parties 
transmitting and receiving a communication text. As a result, the fact 
that an encrypted text can be received and decoded into a meaningful 
communication text assures the receiving party of the fact that the 
communication text has been transmitted from another party possessing the 
key. Accordingly, with the secret communication system according to the 
seventh embodiment, authentication of transmitting and receiving parties 
in communication can be performed as well. 
Thus, as described above, generation/reproduction of communication data can 
be performed at a high speed using the pseudorandom numbers generated by 
the method and apparatus of this embodiment. 
&lt;Eighth Embodiment&gt; 
In a network of the type in which an encryption key is not distributed 
beforehand as in the seventh embodiment but is required to be owned 
jointly by the transmitting and receiving parties before encrypted 
communication, the well-known Diffie-Hellman method is available in which 
the encryption key can be shared safely even in a case where communication 
takes place over a communication line that is susceptible to wire tapping 
(W. Diffie and M. E. Hellman, "Direction in Cryptography", IEEE, IT, vol. 
IT-22, No. 6, 1976). The random numbers generated by the third through 
sixth embodiments can be used as the random numbers employed in this 
method. 
Since the transmitting party and receiving party need not possess the same 
random numbers used in this case, the initial value set in the random 
number generators in each party may be any respective value. 
In a case where cryptologically secure pseudorandom numbers are generated 
by the Montgomery method in accordance with the embodiment described in 
detail above, using prescribed bits of y.sub.i, obtained by Equation 
(B-15) or (B-25), as pseudorandom numbers makes it unnecessary to perform 
the operation of equation (*3) or equation (*1) and equation (*3), which 
is required in the prior art. As a result, it is possible to generate 
pseudorandom numbers having a degree of security the same as that of the 
prior art at a higher speed or with circuitry of a smaller scale. Further, 
generation/reproduction of communication data can be performed at high 
speed using the pseudorandom numbers generated. 
Thus, in accordance with the third through eighth embodiments as described 
above, secure pseudorandom numbers can be generated at a higher speed and 
more easily and generation/reproduction of communication data can be 
performed at a high speed. 
The present invention can be applied to a system constituted by a plurality 
of devices or to an apparatus comprising a single device. Furthermore, it 
goes without saying that the invention is applicable also to a case where 
the object of the invention is attained by supplying a program to a system 
or apparatus. 
As many apparently widely different embodiments of the present invention 
can be made without departing from the spirit and scope thereof, it is to 
be understood that the invention is not limited to the specific 
embodiments thereof except as defined in the appended claims.