1. Field of the Invention
The present invention relates to a pseudorandom number generator that generates a chaotic stream of pseudorandom numbers, to a method for stream encrypting, and to a stream encrypting communication method.
2. Description of the Related Art
With the widespread application of digital computers, networks connecting computers have exhibited rapid development, bringing with it the need to transfer huge quantities of information, and multi-user communication is expected to be able to meet this need.
The purpose of achieving widespread use of multi-user communication is to achieve reliable transfer of huge amounts of information and to reap the benefits of sharing single communication circuit. Beyond this purpose, however, there are also the aims of achieving a robust social infrastructure, preventing unauthorized access, and assuring confidentiality.
In next-generation multi-user communication systems, CDMA (code division multiple access) systems, making use of spectral diversity with good immunity to interference, will become the systems of choice. In such spread-spectrum systems, pseudorandom number generators will be key devices. Because noise generated by actual physical mechanisms lacks repeatability, it is not usable as a practical technology in industry. In its place, there is a need for pseudorandom number generators capable of generating diverse and repeatable binary streams that can be treated as pseudorandom numbers.
The term pseudorandom noise is used interchangeably with the term pseudorandom number. Because true pseudorandom numbers, for example, as would be generated by tossing a coin, are not repeatable, they are not applicable to industrial technologies. On the other hand, unless a series of numbers can defy prediction, it cannot not be expected to offer sufficient scrambling or dispersion. Thus, the needs of industry require that these conflicting goals be met in developing an ideal pseudorandom number generator.
In the past, an M series generated by feedback shift register circuits has been known for use as pseudorandom number generators. Because if the period of an M series is made long, it is possible to achieve a time sequence that is not much different from a true series of random numbers, these are often used in place of true random numbers.
In order to achieve sufficient communication security, it is necessary to assure that the content being communicated be invisible. For this reason, it is desirable that a pseudorandom number series be used that has a low auto-correlation and cross-correlation function. With feedback shift register circuit as used in the past, however, it was difficult to generate a large number of periodic sequences with a low auto-correlation and cross-correlation function.
A chaotic stream is known to include all frequency components, and is extremely close to representing random numbers. For this reason, it is known that, if it is possible to make a chaotic stream periodic, it could be used as pseudorandom numbers.
However, because a chaotic stream repeats diversion and conversion in an unpredictable manner, it is not usable as is, and requires the addition of a means for control of the chaotic stream.
Accordingly, it is an object of the present invention, in view of the above-described background, to provide a pseudorandom number based on a chaotic stream that includes all frequency components, which uses a novel concept of non-linear quantizing, in which decimal parts are discarded so as to achieve integer scaling. The result being control of the chaotic stream so as to achieve generation of a large number of types of time series with low auto-correlation and cross-correlation functions,
Another object of the present invention is to provide a method for stream encrypting, which uses a binary stream obtained from a pseudorandom number generator to generate, for use, for example, in communication, encrypted text that achieves an optimal high level of security.
It is yet another object of the present invention to provide a stream encrypting communication method using an encrypted text code obtained from a stream encrypting method that enables stream encrypted communication with an extremely high level of security.
To achieve the above-noted objects, a first aspect of the present invention includes a one dimensional mapping circuit for generating chaos having non-linear input-output characteristics, an AD converter for converting an analog output of the one dimensional mapping circuit, a sample-and-hold circuit for holding and outputting a digitally converted value from the AD converter in response to an external clock, and a DA converter for outputting an analog converted value in response to the output of the sample-and-hold circuit as feedback to the one dimensional mapping circuit, (forming a chaos-generating loop), wherein the quantizing divisions of at least one of the AD converter and the DA converter are made non-linear, and a binary sequence is output responsive to the output of the sample-and-hold circuit.
According to this aspect of the present invention, with the one dimensional mapping circuit (with non-linear input-output characteristics) forming a chaos-generating loop via a sample-and-hold circuit and the like, a mapping function whereby chaos is generated is provided. By using the AD converter or the DA converter (hereinafter collectively referred to as the non-linear quantizer), the input-output characteristics of this one dimensional mapping circuit having self-feedback (the mapping at each step is suppressed), a periodic time series may be obtained from the generated chaos. The output of the sample-and-hold circuit is applied, for example, to a general decoder, and a binary sequence {Y(t)xe2x88x92t} is extracted from the decoder output, where t is the discrete time.
If the chaos contains all frequency components, and non-linear quantizing is used to observe its internal condition, the chaos is converted to a multiple-value integer sequence, which encompasses all combinations of integer sequences. By including a non-linear quantizer within the chaos-generating loop, it is possible to simultaneously extract the period and random numbers, and it is intrinsically guaranteed to be possible to extract all combinations thereof.
A second aspect of the present invention is a variation of the first aspect, wherein the pseudorandom number generator has an AD converter with linear quantizing divisions and a DA converter with non-linear quantizing divisions.
According to the second aspect of the present invention, by using an AD convener with linear quantizing divisions and DA converter with non-linear quantizing divisions, it is possible to broaden the dynamic range of the one dimensional mapping circuit.
A third aspect of the present invention is a variation on the pseudorandom number generator of the first aspect, wherein the one dimensional mapping circuit is implemented by a CMOS inverter, and wherein the AD converter is configured so as to include an AD weighting resistive array and a comparator array that compares the relative size of an output obtained from a synthesized resistance of the AD weighting resistive array and the analog output from the one dimensional mapping circuit. The sample-and-hold circuit is implemented as a flip-flop array that captures and holds the digital output of the AD converter in response to an external clock, and wherein the DA converter is configured so as to include a DA weighting resistive array. Further, a switching array outputs an output obtained from the synthesized resistance of the DA weighting resistive array in response to the digital output from the sample-and-hold circuit as feedback to the one dimensional mapping circuit.
According to the third aspect as described above, it is possible to implement the pseudorandom number generator using a CMOS integrated circuit.
A fourth aspect of the present invention is a variation on the pseudorandom number generator of the third aspect, wherein an exclusive-OR array is inserted which takes the exclusive-OR of the outputs of each comparator making up the comparator array. The exclusive-OR array is provided between the AD converter and the sample-and-hold circuit.
The above-noted aspects of the present invention are described as pseudorandom number generators having a chaos-generating loop that includes one one dimensional mapping circuit. In contrast to these, there are other aspects of the present invention which are pseudorandom number generators having a chaos-generating loop that includes a pair of one dimensional mapping circuits.
More specifically, a fifth aspect of the present invention has a chaos-generating loop that includes a pair of one dimensional mapping circuits for generating chaos having non-linear input-output characteristics, a pair of CMOS switches which alternately open and close an output side path of the one dimensional mapping circuits, in synchronization with an external clock, and a pair of feedback loops that cross-connect the analog outputs of each of the one dimensional mapping circuits, via the CMOS switches, as feedback to the inputs of the other of the one dimensional mapping circuits, and a pair of AD converters that perform digital conversion of the analog outputs of the one dimensional mapping circuits that are extracted via the CMOS switches. In the chaos-generating loop, according to the elapse of the discrete time established by an external clock, the outputs of the one dimensional mapping circuits are alternately mapped, so as to output, via each of the AD converters, a binary sequence that is a chaos sequence.
In the pseudorandom number generator of the fifth aspect as described above, the binary stream extracted by the alternating method noted above is a random arrangement of data comprised of mixed 0 and 1 values. By obtaining a binary stream arranged as a combined time series from these binary data streams, it is possible to generate pseudorandom numbers in a chaos stream.
If the world is viewed from the standpoint of chaos, the same event never occurs twice. In terms of the individual input-output characteristics of the individual one dimensional mapping circuits, it is considerably difficult to maintain total symmetry. Additionally, it is quite difficult to maintain total coincidence in the correlation of input-output characteristics of each of the pair of one dimensional mapping circuits, and it is additionally true that there is no assurance that the two AD converters perform identical quantizing. In removing such causes for uncertainty the present invention is extremely effective in providing a hardware implementation of a mass-producible pseudorandom number generator on a single integrated circuit.
According to the fifth aspect of the present invention as described above, because repeated alternate mapping is performed by the pair of one dimensional mapping circuits, and the analog outputs obtained by mapping in this manner are fed back by cross-connection, the binary stream obtained exhibits a fine disturbance of 1 and 0 values, acting in combination with divergence and convergence of the analog outputs created by the pair of one dimensional mapping circuits and the initial value sensitivity characteristic of chaos. It is expected that the characteristic variation properties of chaos will contribute to the improvement of the robustness of stream encrypting.
In a pseudorandom number generator configured as described above, if a long time series is to be generated, this can be done by repeating mapping in the chaos-generating loop. If it is assumed that a time series of a PN signal will be extracted as a time series of a prescribed length from a long time series generated in this manner, it is necessary that the auto-correlation and cross-correlation functions of the extracted time series be sufficiently small. That is, it is required that there be no overlaps in the correlation if the phase is shifted one bit at a time. This is to assure the robustness of the code.
Furthermore, there is a need, not only for a large number of types of extracted time series, but for the ability to reliably generate long time series that are different from one another, by changing the initial value, even starting from one one dimensional mapping circuit. In chaos generation, the initial value is given as a real number, and because there is an infinity of real numbers this cannot be applied to industrial technology. This being the case, in a sixth aspect of the present invention, an applied voltage corresponding to a real number is applied, via a DA converter.
Specifically, the sixth aspect of the present invention is a variation of the pseudorandom number generator of the fifth aspect, which further has a DA converter that performs an analog conversion of an initial value given in the form of a digital signal, and a CMOS switch, which performs opening and closing of an output side path of the DA converter, synchronized to an external clock.
In the above-noted sixth aspect of the present invention, an applied voltage is given via a DA converter, which corresponds to a real number. By increasing the quantizing resolution of the DA converter, the increase in the number of initial value types enables an increase in the number of extractable time series. This is an extremely important element in maintaining sensitivity with respect to initial value in the practical application of chaos to industry.
According to the sixth aspect of the present invention, because initial value sensitivity is given via a DA converter, using a pair of binary streams that differ in their staring points, regardless of how these streams are phase shifted and overlapped, there is no coincidence therebetween, and it is possible to achieve a time series with a sufficiently low auto-correlation and cross-correlation function.
It is desirable that the design be such that the input-output characteristics of the one dimensional mapping circuits that are used as elements in the pseudorandom number generator can be adjusted from outside.
From the above-noted standpoint, a seventh aspect of the present invention is a variation of the pseudorandom number generator of the fifth aspect, designed so that at least one of the pair of one dimensional mapping circuits has input-output characteristics that can be individually adjusted by means of an external adjustment voltage. By doing this, because the input-output characteristics of the one dimensional mapping circuit are externally adjustable, it is possible to further increase the number of extractable chaotic streams.
An eighth aspect of the present invention is a method for stream encrypting, whereby a binary stream generated by a pseudorandom number generator according to the first or fifth aspect of the present invention is used to perform stream encrypting, thereby obtaining an encrypted text code, whereby the above-noted stream encrypting is achieved by an exclusive-OR operation performed between a binary stream obtained from the pseudorandom number generator and the plain text to be encrypted.
According to the eighth aspect of the present invention, the encrypted text is generated by performing stream encrypting using a binary stream obtained from a pseudorandom number generator. Further, according to the present invention, because the stream encrypting is done by an exclusive-OR operation between the binary stream and the plain text to be encrypted, it is possible to achieve a stream encrypting method capable of producing encrypted text with an extremely high degree of security for applications such as communications.
A ninth aspect of the present invention is a stream encrypting communications method that uses an encrypted text obtained by the stream encrypting method of the eighth aspect of the present invention.
According to the ninth aspect of the present invention, because stream encrypted communication is performed using an encrypted text obtained by the stream encrypting method of the present invention, it is possible to perform stream encrypted communication with an extremely high degree of security. More specifically, it is possible to implement an asynchronous multiple user stream encrypted communication system in which a user, possessing the same pseudorandom number generator as was used in encrypting, can achieve synchronous playback, expansion, mixing, and transfer of the encrypted text.