JP2003050545A - A pseudorandom number generation method using fixed-point arithmetic - Google Patents

Abstract

(57) [Summary] [Problem] To generate a time series of a logistic map which is uniquely controlled by an initial value by performing calculation by fixed point calculation, obtain a pseudo random number, and use it as a PN signal of a stream cipher. A calculation method for performing a fixed-point calculation of a logistic map and a calculation performed by installing the calculation on a chip (FPGA or the like) of an integrated circuit by a bit operation to generate a pseudo-random number at high speed.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION Encryption, frequency multiplexing, and compression / decompression are problems in high-speed communication. The present invention relates to a high-speed pseudo-random number generation method for realizing stream encryption in real time (sequentially) on a network or the like. In particular, it aims to provide a dedicated processor.

Pseudo-random numbers of good quality (not converging to zero, not converging to 1 and not entering a cycle) enable one-to-one (EXOR operation, cipher code does not expand) stream ciphers in communication. The encryption code is uniquely controlled by the encryption key (initial value).

[0003]

2. Description of the Related Art In order to generate good quality pseudo-random numbers, it is necessary to maintain the calculation accuracy as high as possible. Therefore, 64-bit (12-bit exponent part, 52-bit mantissa part) double precision floating point arithmetic is used. These are the OS
It is possible above. Such a soft calculation method determines the processing speed depending on the length of the program, and is not suitable for high-speed pseudo random number generation. Also, depending on the CPU and OS, it becomes expensive.

The situation is the same for industrial CPUs.
In general, many industrial general-purpose CPUs guarantee only single-precision arithmetic, and the OS is also poor, making them unsuitable for generating pseudo-random numbers at high speed in software.

A dedicated chip using an FPGA or a gate array has a possibility of practical use as an industrial technology. In that case, the condition that it converges to zero and that it does not enter the cycle must be cleared. Even if it enters the cycle, if it is sufficiently long as compared with a PN (Pseudo Noise) signal (which is said to require 100,000 bits or more) that uses the cycle, it can be regarded as not entering the cycle. .

[0006]

When the pseudo-random number generation is realized by the integrated circuit chip, the Lyapunov exponent λ = I
Logistic map X _{t + 1} = 4X _t (1- that is known to generate chaos of n2 = 0.693 ...
It is reasonable to install X _t ), X _t = X _{t + 1} on the chip. In the binary calculation, the multiplication of X _t and (1-X _t ) is the two's complement of X _t and X _t (0 and 1 of each bit of X _t are exchanged, and 1 is added to the least significant digit). Is replaced by the multiplication of. On the other hand, the operation to multiply the calculation result of X _t (1-X _t ) by 4 is 1
Can be performed with a shift that replaces 100 with 100, and in practice it is not necessary to perform the operation.

The above calculation means a fixed point calculation.
The multiplication between complementary codes is replaced with the operation of shifting and adding, so that the carry of addition does not suffer, X _t (1-X _t ) becomes a value smaller than 0.25, and binary When viewed in code, the most significant bit is always (00).
Carries cannot be spread here.

The single-precision floating-point arithmetic using a general-purpose CPU is superior to the fixed-point arithmetic in terms of calculation accuracy. As far as logistic map calculations are concerned, single-precision floating-point arithmetic is immediately 00 ...
It converges to 0, and pseudo-random number generation fails.

[0009]

[Means for Solving the Problems] In fixed-point arithmetic of a logistic map, the reason why convergence to zero is avoided is that the arithmetic result of the number of significant figures that is twice the effective number is calculated once for each calculation loop. It is possible, however, because only the upper half is fed back to X _t and the lower bits are truncated. Therefore, the calculation result is always smaller than the true value by cutting off the lower bits. The main reason for avoiding the convergence to zero is the truncation of the lower bits when X _t = 0.999 .... Every time the calculation loop is repeated, the correction is automatically performed, and the correction value is always different, which makes it difficult to enter the cycle.

The length of the cycle is determined by the calculated value to be fed back, that is, the number of significant figures. If the effective number is 20 decimal digits, the period is about 20,000 bits, whereas if the number is 30 digits, the period is about 450,000 bits. A significant digit can be selected according to the length of the required PN signal, but 31-bit fixed point is an example of a good choice when implemented as an integrated circuit chip.

[0011]

[Function] Fixed-point arithmetic does not require a program,
Since the calculation is executed only by the data flow type bit shift operation, it is aimed at speeding up. In addition, the output may take the significant figure output for calculation as it is,
The calculation result is twice as long as the significant figure. It may be arranged as it is as an output and used as an element forming a pseudo random number. The longer the number of significant digits that can be generated in one loop, the faster the chip.

The distribution of the series of zeros and the series of ones of the pseudo random numbers in which the effective numbers are taken out as they are and arranged is a probability distribution. This is natural because it is the result of calculating a logistic map (where symmetry is guaranteed). However, since the lower bits are truncated and fed back each time the calculation is repeated, the total number of 0s is 0.10 to 0.20%.
However, such a deviation can be ignored when the pseudo random number is used as the PN signal of the stream cipher. On the contrary, it can be said that a sufficiently small correction that affects the probability distribution to that extent effectively prevents the convergence of zero.

A simulator and a tester are required to realize a high-speed pseudo-random number generation chip. The bit shift operation of fixed-point arithmetic may be directly implemented on the OS of the digital computer. On the other hand, the mapping of the logistic map is executed by 64-bit double precision floating point arithmetic on the OS of the digital computer, the result is once converted to binary fraction 52 bits, and the necessary fractional digits are rounded down. The calculation of the mapping is performed again by returning to the 64-bit double precision floating point arithmetic. The simulator can be configured in this way. Regarding the execution speed, when compared with the CPU having the same clock frequency, the latter soft method is 4 to 6 times faster than the former hard method.

[0014]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT A block diagram of fixed point arithmetic of a logistic map is shown in FIG. Block 1 is the binary code for X. In this embodiment, a 6-bit code is used as a concrete example for the sake of simplicity. Block 2 is (1-
X _t ) is a binary code. (1-X _t ) is represented by the two's complement of X _t . Blocks 1 and 2 are complementary inversion bits except for the least significant bit.

The multiplication unit 3 uses the binary code of block 1 as
It is shifted along 1 of block 2 and arranged, and added up and down to obtain. The multiplication result of X _t (1-X _t ) is shown in block 4. It is not necessary to add the multiplication parts together as shown in the figure. The third row may be added to the value obtained by adding the upper two rows, and the fourth row may be added to the result. It is easier to carry and it is suitable for hardware implementation.

The result of multiplication of X _t (1-X _t ) is always 0.25 or less in decimal fraction. Therefore, the first 2 bits of the block 4 are always 00. This means that the binary code of block 1 and block 2 are complementary, so that the carry propagation in block 3 is limited.

The block 5 is a quadruple operation unit. Quadruple multiplication is an operation of replacing a bit that is 1 with 100 and performing addition. The result is block 6. Comparing block 5 and block 6, quadruple multiplication requires only shift operation, only moving the leading 2 bits 00 of block 5 to the least significant 2 bits 00 of block 6, does not require operation I understand.

The upper 6 bits of block 6 are fed back to block 1. The lower 6 bits of block 6 are truncated. This operation is repeated. The truncation of the lower 6 bits means that the value to be fed back is always subtracted from the true value.

How much the binary code length of the block 1 should be depends on how high the quality of the pseudo-random number is required. As for the pseudo-random number, the blocks 1 may be sequentially arranged, or the blocks 4 or 6 may be arranged as they are. It is better to arrange blocks 4 or 6 into a pseudo-random number.
Pseudo-random numbers can be generated twice as fast as arranging only block 1. The example in which the binary code length of block 1 is 31 is a length (approximately 1
This is a typical example in which a balance between the 5,000 mapping length) and the required PN signal length (about 100,000 bits) is taken.

The operation of FIG. 1 is for explaining the operation method by extracting the binary code below the decimal point in fixed point display. Therefore, it can be considered that each block has a decimal point at the beginning. Compared to floating point, the number of significant digits that can be handled is limited, and at first glance it seems that computational power is insufficient, but it has good symmetry like a logistic map, and it is a function that is normalized between 0 and 1. This is a convenient method when the mapping is made into a dedicated chip.

【The invention's effect】

The present invention uses an FPGA and a gate array,
We aim to realize the logistic map calculation formula in one chip by repeating the bit operation of binary code. When designing and testing integrated circuits, they can be realized by using double-precision arithmetic, which improves design ease and testability.

It is well known that general purpose OSs employ floating point arithmetic. The calculation of the map of the logistic map is not suitable for floating point arithmetic. The deeper the calculation around 1.0 or around the origin, the more the convergence to zero is unavoidable. Fixed-point arithmetic has the opposite effect. The present proposal succeeded in the generation of pseudo-random numbers by effectively utilizing this advantage.

The digital computer comprises a CPU, an O
S, which is open to the language, has adopted the floating point arithmetic method to support a wide range of numerical operations from large numbers to small numbers. On the other hand, returning to the gate level of the integrated circuit, the hardware is suitable for fixed-point arithmetic. It does not depend on the OS or language. This is the reason why high-speed pseudo-random number generation is successful.

[Brief description of drawings]

FIG. 1 is an explanatory diagram showing fixed point arithmetic according to the present invention.

[Explanation of symbols] 1 ... X 2 ... 1-X 3 ... Multiplication section 4 ... The result of X (1-X) 5 ... multiplication by 4 Results of 6 ... 4X (1-X)

   ─────────────────────────────────────────────────── ─── Continued front page    (72) Inventor Hajime Konno             Chiba Prefecture Inzai City Hara 4-5th Avenue 8 Building 1002 F-term (reference) 5J104 FA08 NA19

Claims (2)

[Claims] 1. A pseudo-random number characterized by adopting a fixed-point operation for calculating a logistic map for generating chaos when generating a pseudo-random number as a PN signal for stream encryption of information in high-speed communication. How to generate. 2. A fixed point arithmetic of a logistic map for generating chaos is installed in a chip of an integrated circuit when generating a pseudo random number as a PN signal for stream encryption of information in high speed communication. Pseudo-random number generation method.