Method and device for self-clock controlled pseudo random...

Details Method and device for self-clock controlled pseudo random... Method and device for self-clock controlled pseudo random...

2000-12-20

2004-11-02

Ngo, Chuong Dinh (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S253000

Reexamination Certificate

active

06813625

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to an electrical device for self-clocked controlled pseudo random noise (PN) sequence generation.
BACKGROUND OF THE INVENTION
Pseudo random noise sequences (PN sequences) are used in many cryptographic and communication applications to provide randomly appearing symbols. Typically, cryptographic applications are methods to provide confidentiality of transmitted information through the use of stream ciphers. In communications systems PN sequences may e.g. be used as spreading sequences in spread-spectrum communications systems where they determine the hop sequence and/or the direct spreading sequence.
In general, a receiver of a spread-spectrum communications system will receive a digital signal/bit stream transmitted over a single carrier frequency which is combined from a digital signal/bit stream containing information such as a digitized voice and from a PN sequence used to code or encrypt the transmission. Typically, the length of the PN sequence stream is much larger than the length of the information stream.
The PN sequences are sometimes derived by using a maximal length polynomial. Constructions, whether hardware or software implemented, which form PN sequences in this manner are sometimes referred to as m-sequence generators. It is well known that the randomness properties of the sequences generated by the m-sequence generators are very limited as a result of linear relationships between the symbols of the sequence. This enables a prediction of the next symbol given sufficiently many, but small number of previous symbols. In various applications this is not desirable and, hence, there is a need for efficient techniques to enhance the unpredictability.
Clock control of the m-sequence generator is a well-known method that can be used to increase the unpredictability of m-sequence generators.
In most cryptographic applications the outputs of several such clock controlled m-sequence generators are combined to generate the final output sequence. Output bits generated by a combination of clock controlled m-sequence generators form the PN sequence which are used to e.g. encrypt or spread an information signal.
In known applications, e.g. in the ciphering generator A5/1 of the GSM cellular mobile telephone system, the clocking signals for controlling the stepping of the involved clocked m-sequence generators are derived from signals of the clocked m-sequence generators themselves, i.e. the generators are self-clocked.
The A5/1 generator will be described in more detail in connection with
FIG. 1
, which shows a schematic block diagram of the A5/1 generator.
In the A5/1 generator, three signals (
101
) are taken from three feedback registers (
104
) and combined by mapping means (
102
) in such a way as to derive three clock control signals (
103
) so that at least two feedback shift registers (
104
) and sometimes three are always stepped.
There are eight possible values for the combination of input signals (
101
) which are mapped to the four possible stepping patterns (0,1,1), (1,0,1), (1,1,0), and (1,1,1) (
103
) if at least two registers are to be stepped. Here (x,y,z) means that if x is 0, the first feedback register is not stepped, and if x is 1, the first feedback register is stepped. In the same way, y and z control the second and third feedback registers, respectively.
Since each feedback shift register (
104
) is stepped at least three times out of the four possible stepping patterns (
102
), each shift register (
104
) is stepped six times out of the eight possible combinations of the input signals (
101
), since these eight combinations are mapped to the four stepping patterns (
103
).
Such a uniformity of stepping each shift register (
104
), responsible for clocking/controlling the connected m-sequence generators (not shown), has an enhancing effect on the unpredictability of the final output PN sequence combined from the output of the m-sequence generators.
However, it is very hard in general to realise such a favourable clocking mechanism with presently known techniques, as e.g. used in A5/1, for other self-clocking methods and/or schemes; especially for methods using a higher number of shift registers (and thereby more m-sequence generators), which is needed e.g. for a higher degree of unpredictability.
Another problem with the prior art as described above is if e.g. four m-sequence generators (and thereby four shift registers) are needed e.g. for a higher degree of unpredictability, and only two shift registers are to be stepped at a time, 16 combinations of input values must be mapped to the 6 possible step patterns (0,0,1,1), (0,1,0,1), (1,0,0,1), (0,1,1,0), (1,0,1,0), (1,1,0,0). With presently known techniques some step patterns will be used more often since the 16 combinations are mapped to only 6 step patterns.
Further U.S. Pat. No. 4,817,145 discloses a generator for generating pseudo random binary cipher sequences comprising a number of subgenerators arranged in a cascaded scheme. A first subgenerator clocks/steps the other subgenerators and is always clocked itself by an external clock at a constant rate.
Even though this prior generator enhances the randomness of the output sequence it is relatively easier to cryptoanalyse since one part of the generator behaves regularly.
SUMMARY OF THE INVENTION
An object of the invention is to provide an electrical device for self clocked controlled PN sequence generation where a plurality of PN sequence generators are clocked uniformly with respect to the combinations of input signals.
Another object is to provide flexibility with respect to implementing clock control, so that more freedom with respect to step patterns is possible/available.
This object is achieved by an electrical device of the aforementioned type further comprising:
step pattern generation means adapted to select a step pattern, providing said plurality of clock values (C
t
), from a plurality of possible step patterns on the basis of a step pattern select signal (W
t
).
Hereby, a final output PN sequence generation will have an enhanced degree of unpredictability since the generation means are clocked uniformly.
Additionally, the uniformity is obtained on the basis of a step pattern select signal (W
t
) without using shift registers, which enhances the flexibility of the device, since the step pattern select signal (W
t
), responsible for controlling/clocking the sequence generation means, may be obtained by various combinations of different signals instead of mapping means in combination with shift registers.
The enhanced unpredictability and uniformity may be obtained for any number of sequence generation means and any number of stepping patterns.
If the step pattern select signal (W
t
) is derived on the basis of a combined value (U
t
) and one or more previously derived step pattern select signals (W
t−1
), a very simple and unpredictable way of deriving the step pattern select signal (W
t
) is obtained.
Additionally, the step pattern select signal (W
t
) may be provided by using little additional hardware.
In an alternative embodiment, the plurality of sequence generation means (
201
) is further adapted to output a plurality of step control values (u
t
), and the combined value (U
t
) is provided on the basis of the plurality of step control values (u
t
) and on the basis of a plurality of prior clock values (C
t−1
).
Hereby, an efficient and simple use of existing signals is obtained.
A simple way of calculating a step pattern select signal (W
t
) is obtained, if the number of the plurality of possible step patterns is 6, and the pattern select signal (W
t
) is derived as: U
t
+W
t−1
MOD 6.
In this way a very simple way of calculating the step pattern select signal (W
t
) is obtained by using existing signals, while still obtaining uniformity with respect to the clocking of the sequence generation means.
For another number of possible step patterns than 6 other modulo functions may be applied, e.g. MOD 4 for four possible step patterns.
Alternatively, if the

Affiliated with

Also associated with

Rating

Method and device for self-clock controlled pseudo random... does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3337872