Cryptography – Key management – Having particular key generator
Reexamination Certificate
2000-10-18
2004-08-31
Morse, Gregory (Department: 2131)
Cryptography
Key management
Having particular key generator
C380S265000, C708S209000, C708S252000, C708S253000, C377S054000, C377S064000, C377S067000, C377S072000, C365S078000
Reexamination Certificate
active
06785389
ABSTRACT:
FIELD OF THE INVENTION
The present invention generally relates bitstream generators that use linear feed shift registers.
BACKGROUND OF THE INVENTION
Bitstream generators are typically used to generate bit stream ciphers. A specific family of bitstream generators is a family of bitstream generators that use linear feed shift registers (LFSRs) to generate stream ciphers. This family of bitstream generators is well known in the art and described, for example, in the following publications:
Applied Cryptography, Protocols Algorithms and Source Code in C
, second edition, by Bruce Schneier, John Wiley & Sons Inc., 1996, pages 381-388; and
Handbook of Applied Cryptography
, by Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone, CRC Press LLC, 1997, pages 202-211.
The disclosures of all references mentioned above and throughout the present specification are hereby incorporated herein by reference.
SUMMARY OF THE INVENTION
The present invention seeks to provide an improved bitstream generator that provides better security of a bit stream generated thereby.
In a preferred embodiment of the present invention, a bitstream generator includes a plurality of linear feed shift registers (LFSRs) each of which may be assigned different assignments during different time periods. The output of the bitstream generator is typically used to generate at least one of the following: a bit stream cipher; a hash function; and a pseudo-random binary sequence (PRBS). The bit stream cipher, the hash function and the PRBS may be each used for various application schemes, such as authentication schemes, signature schemes, validation schemes, and verification schemes, and also for various applications, such as integrity check applications, and encryption applications.
The plurality of LFSRs may operate in a “horserace” mode of operation by assigning different assignments to at least some of the plurality of the LFSRs during different “race” time periods. During a first time period, at least a first one of the plurality of LFSRs is assigned as a generator, and at least a second one of the plurality of LFSRs is assigned as an assignor.
Preferably, all the generators produce LFSR output bits that preferably undergo a selection operation and a combination operation in a first combiner. The first combiner is controlled by a control logic unit and is preferably ultimately operative to generate a single output bit every clock cycle. A collection of such single output bits generated during many time periods forms a stream of bits that may be used as described above.
Preferably, all the assignors produce LFSR output bits that preferably undergo a selection operation, a combination operation, and a scrambling operation in a second combiner. The second combiner is ultimately preferably operative to generate a series of decision bits during the first time period. The series of decision bits is preferably used as an entry to a policy table that preferably determines assignments of each of at least some of the plurality of LFSRs as either a generator or an assignor for a second time period following the first time period. The assignments determined by the policy table are effected by the control logic unit through control of the operation of the plurality of the LFSRs and the second combiner.
It is appreciated that an assignment as an assignor may also include an assignment as a combined assignor and lag generator. The lag generator is preferably operative to determine a lag of N shifts for a specific LFSR during a specific time period, where N is an integer number. Thus, during the specific time period, the specific LFSR performs less bit shifts than an LFSR for which a lag is not determined.
In a preferred embodiment of the present invention at least a third one of the plurality of the LFSRs may be assigned, during the first time period, an assignment as a time-period assignor. All the time-period assignors produce LFSR output bits that undergo a selection operation, a combination operation, and a scrambling operation in a third combiner to ultimately generate a series of time decision bits during the first time period. The series of time decision bits is preferably used as an input to another policy table that determines the second time period, that is, a start time of the second time period, and a duration of the second time period. The start time of the second time period and the duration of the second time period are preferably effected by the control logic unit through control of the operation of the plurality of the LFSRs and the third combiner.
There is thus provided in accordance with a preferred embodiment of the present invention a bitstream generator including a plurality of linear feed shift registers (LFSRs) operative to generate a bit stream and including at least a first LFSR operative, when assigned as a generator during a first time period including at least one clock cycle, to provide an output bit in each clock cycle within the first time period, and at least a second LFSR operative, when assigned as an assignor during the first time period, to provide in each clock cycle an output bit for determining assignments of at least some of the plurality of LFSRs for a second time period following the first time period, the assignments including: assignment as a generator and assignment as an assignor, and a first combiner operative to combine output bits from all of the at least a first LFSR being assigned as generators thereby to produce during each clock cycle a single output bit which is provided to the bit stream.
Preferably, the first combiner includes at least one combinatorial selection logic device which is operative to combine the output bits from all of the at least a first LFSR being assigned as generators to produce a set of intermediate bits, a generator lookup table (LUT) operatively associated with the at least one combinatorial selection logic device and operative to combine the set of intermediate bits to form a single output bit, and an output buffer, operatively associated with the generator LUT and operative to output the single output bit. The combinatorial selection logic device may preferably include a multiplexer (MUX).
Additionally, the bitstream generator may include a second combiner operative to combine output bits from all of the at least a second LFSR that are assigned as assignors to produce a series of decision bits which are applied as an entry to a policy table to determine assignments of each of at least some of the plurality of LFSRs for the second time period. Preferably, the second combiner includes at least one combinatorial selection logic device which is operative to combine the output bits from all of the at least a second LFSR that are assigned as assignors to produce a set of bits every clock cycle, an assignor LUT operatively associated with the at least one combinatorial selection logic device and operative to combine the set of bits to form a single intermediate bit every clock cycle, and a scrambling buffer, operatively associated with the assignor LUT and operative to perform scrambling operations on all intermediate bits generated during the first time period and to output a series of decision bits to the policy table.
Preferably, the assignment as an assignor also includes an assignment as a combined assignor and lag generator. The lag generator is preferably operative to determine, during the first time period, a lag having a length of an integer number N of shifts for an LFSR for the second time period.
Additionally, the bitstream generator also includes at least a third LFSR operative, when assigned as a time-period assignor during the first time period, to provide an output bit for determining a start time and a, length of the second time period.
Further additionally, the bitstream generator also includes a third combiner operative to combine output bits from all of the at least a third LFSR that are assigned as time-period assignors to produce a series of time decision bits, and a policy table operatively associated with the third combiner a
Kipnis Aviad
Sella Yaron
Callahan Paul
Darby & Darby
Morse Gregory
NDS Limited
LandOfFree
System for bitstream generation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for bitstream generation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for bitstream generation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3345331