cryptix.util.math

Class TrinomialLFSR

java.lang.Object

cryptix.util.math.BigRegister

cryptix.util.math.TrinomialLFSR

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable

public class TrinomialLFSR
extends BigRegister
implements java.lang.Cloneable, java.io.Serializable

A class that implements a special category of Linear Feedback Shift Register (LFSR). Formally speaking, it implements a Fibonacci LFSR --LFSR(II)-- with a Monic, Non-Singular, Trinomial Connection (Characteristic) function of the form f(x) = x ^L + x^K + 1.

Menezes et al. define a generalised LFSR --with an L-degree connection polynomial-- as follows:

An LFSR of length L consists of L stages (or delay elements) numbered 0, 1, ..., L-1, each capable of storing one bit and having one input and one output; and a clock which controls the movement of data. During each unit of time the following operations are performed:

• the contents of stage 0 is output and forms part of the output sequence;
• the contents of stage i is moved to stage i-1 for each i, 1 <= i <= L-1; and
• the new contents of stage L-1 is the feedback bit s_j which is calculated by adding together modulo 2 the previous contents of a fixed subset of stages 0, 1, ..., L-1 also called taps.

Such an LFSR, referred to as a Fibonacci LFSR, Type II LFSR , or simply LFSR(II), is denoted by <L, C(D)>, where C(D) is called the connection or characteristic polynomial and is defined as:

C(D) = 1 + c₁D + c ₂D² + ... + c_LD^L Î Z₂[D]

A Linear Feedback Shift Register (LFSR) with a trinomial function of the form 1 + x^K + x^L as its connection polynomial can be schematised as follows:

  +--------------------XOR<-------------------------------+
  |                     ^                                 |
  |                     |                                 |
  |   +-----+-----+-----+-----+-----+-----+-----+-----+   |
  |   |stage|     |stage|stage|     |stage|stage|stage|   |
  +---| L-1 | ... | L-K |L-K-1| ... |  2  |  1  |  0  |---+--> output
      +-----+-----+-----+-----+-----+-----+-----+-----+
        K+1         L-1    0          K-3   K-2   K-1
      <------- Powers of the polynomial terms -------->
 
 

The following, collected from the references, are properties and curiosities inherent to such objects:

• Choosing a primitive trinomial over Z ₂, ensures that each of the LFSR's 2^L - 1 initial states produces an output sequence with maximum possible period 2 ^L - 1.
• If 2^L - 1 is a prime (a Mersenne prime), then every irreducible polynomial of degree L in Z₂[x] is also primitive.
• Irreducible trinomials, f(x), of degree L can be used to represent the elements of the finite field F₂L = Z₂ [x]/(f(x)), the set of all polynomials in Z ₂[x] of degree less than L where the addition and multiplication of polynomials is performed modulo f(x).
• If f(x) is a primitive polynomial of degree L, then x^L f(x ^-1) = f'(x) is also a primitive polynomial. This is easily shown using the definition of a primitive polynomial, and the properties of modulo-2 arithmetic. A little thought shows that the register taps of f'(x) are the mirror image of those of f(x). And the sequence produced by the tap-reversed generator is the time reversal of the original.

Some terms and conventions associated with LFSRs, and used in this implementation, are:

• tap-sequence: the powers of the terms of the polynomial. In a monic (starts with 1 + ...), non- singular (the term x^L for an L-long register is part of the polynomial function) trinomial, the sequence consists of 3 elements: 0, K, and L.
• mid-tap: the second/middle value of the tap sequence of a monic, non-singular trinomial.
• state: the value of the LFSR's contents. Also used to represent the coefficients of a polynomial in the field F₂L.
• terms of a polynomial: the correspondence between the LFSR stages and the powers of x (the polynomial invariate) in the GF[₂L] with f(x) = x^L + x^K + 1 is such that the term with degree 0 is at stage L - K - 1; the term with degree 1 is at stage L - K - 2, etc... After stage 0, the relationship restarts from stage L - 1. The reason for this gymnastic is to facilitate computing the successive powers of x --based on the mathematical fact that g(x) = x is a generator of the monic primitive f(x)-- which in turn are used in the computation of polynomial multiplication modulo f(x) . When so ordered, multiplying a polynomial p(x) by x ^t modulo f(x) is as simple as loading the LFSR's register with the terms of the polynomial, and clocking it by t cycles.

Finally, Menezes et al. lists (Table 4.9, p.162) some primitive polynomials of degree m over Z₂, 2^m - 1 a Mersenne prime. The following is an excerpt from this table for values of m, m <= 4096 and k, 1 <= k <= m/2, for which the monic, non-singular trinomial x^m + x^k + 1 is irreducible over Z₂.

    m  |  k
 ------+------------------------------
    2  |    1
    3  |    1
    5  |    2
    7  |    1,    3
   17  |    3,    5,     6
   31  |    3,    6,     7,   13
   89  |   38
  127  |    1,    7,    15,   30,  63
  521  |   32,   48,   158,  168
  607  |  105,  147,   273
 1279  |  216,  418
 2281  |  715,  915,  1029
 3217  |   67,  576
 

Implementation Notes:

In order to increase performance of this class, and since it's extending BigRegister, which assumes a bit numbering using bit index 0 as the rightmost one, our LFSR will actually look like so:

     +------------------->XOR--------------------------------+
     |                     ^                                 |
     |                     |                                 |
     |   +-----+-----+-----+-----+-----+-----+-----+-----+   |
     |   | bit |     | bit | bit |     | bit | bit | bit |   |
  <--+---| L-1 | ... | L-K |L-K-1| ... |  2  |  1  |  0  |<--+
         +-----+-----+-----+-----+-----+-----+-----+-----+
           K-1          0    L-1         K+2   K+1    K
         <------- Powers of the polynomial terms -------->
 

Obtaining a normal representation of the powers of the polynomial is done by left rotating the LFSR's contents by K positions.

Clocking the LFSR consists of executing the following pseudo-code:

     out = getBit(L-1);
     in = out ^ getBit(L-K-1);
     shiftLeft(1);
     if (in == 1) setBit(0);
 

References:

1. [HAC] A. J. Menezes, P. C. van Oorschot, S. A. Vanstone, Handbook of Applied Cryptography CRC Press 1997, pp 195-212.

2. [AC2] Bruce Schneier, Applied Cryptography, 2nd edition, John Wiley & Sons, Inc. 1996, pp 372-428.

3. [LFSR] Arthur H. M. Ross, Linear Feedback Shift Registers, WWW page www.cdg.org/a_ross/LFSR.html

Copyright © 1995-1997 Systemics Ltd on behalf of the Cryptix Development Team.
All rights reserved.

$Revision: 1.2 $

Since:

Cryptix 2.2.2

Author:

Raif S. Naffah

See Also:

Serialized Form

Field Summary

Fields inherited from class cryptix.util.math.BigRegister

MAXIMUM_SIZE

Constructor Summary

Constructors

Constructor and Description
TrinomialLFSR(int l, int k) Define an LFSR with L stages and with a connection trinomial of the form: xL + xK + 1.

Method Summary

Modifier and Type	Method and Description
void	add(TrinomialLFSR gx) Compute this += gx (mod f(x)).
void	clock(int ticks) Repeatedly invoke the engineClock() method until the LFSR has been clocked ticks times.
java.lang.Object	clone() Return a reference to a duplicate of this.
int	compareTo(TrinomialLFSR x) Compare this LFSR to the argument, returning -1, 0 or 1 for less than, equal to, or greater than comparison.
int	degreeAt(int index) Return the power of the term xresult relative to the given register's index.
protected void	engineClock(int ticks) Clock the register ticks steps.
int	getMidTap() Return the degree/power of the mid-tap element in this LFSR.
int	getSize() Return the number of elements in this LFSR, which is also the degree of the trinomial.
int	getSlice() Return the maximum number of meaningful bits in this LFSR, which is also the maximum number of bits that can be processed in one operation without loss of desired output sequence.
int	indexOfX(int degree) Return the register's index relative to the polynomial term xdegree.
boolean	isSameGroup(TrinomialLFSR x) Return true iff the argument is a polynomial that belongs to the same Group as this.
boolean	isSameValue(TrinomialLFSR x) Return true if the TrinomialLFSR x has equal characteristics and contents to this one; false otherwise.
void	multiply(TrinomialLFSR gx) Compute this *= gx (mod f(x)).
static TrinomialLFSR	multiply(TrinomialLFSR p, TrinomialLFSR q) Return the product of the two arguments modulo f(x)), where both arguments are members of the same polynomial group with the same monic trinomial f(x).
long	next(int count) Return the value of the leftmost count bits of this LFSR and clock it by as many ticks.
void	pow(BigRegister n) Raise this to the nth power modulo f(x)).
void	resetX(int n) Set the LFSR's initial state to a value that corresponds to the polynomial term of the designated degree.
void	setX(int n) Set (to one) this LFSR's polynomial term of the given degree.
void	subtract(TrinomialLFSR gx) Compute this -= gx (mod f(x)).
BigRegister	toBigRegister() Return the state of this LFSR as a BigRegister object where now the powers of the polynomial terms are ordered in ascending succession starting from power 0 at index 0.
java.lang.String	toPolynomial() Return a formatted String representation of the polynomial form represented by this LFSR's state.
java.lang.String	toString() Return a formatted String representation of the binary contents of this.
TrinomialLFSR	trinomialOne() Return a TrinomialLFSR object whose state is set to the powers of the polynomial p(x) such that p(x) = 1 in the polynomial Group defined over the trinomial function of this object.
TrinomialLFSR	trinomialX() Return a TrinomialLFSR object whose state is set to the powers of the polynomial p(x) such that p(x) = x in the polynomial Group defined over the trinomial function of this object.

Methods inherited from class cryptix.util.math.BigRegister

and, andNot, atRandom, atRandom, byteValue, clearBit, compareTo, countSetBits, flipBit, getBit, getBits, highestSetBit, intValue, invertOrder, isSameValue, load, load, longValue, lowestSetBit, not, or, reset, rotateLeft, rotateRight, setBit, setBits, shiftLeft, shiftRight, testBit, toByteArray, valueOf, xor

Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

TrinomialLFSR

public TrinomialLFSR(int l,
                     int k)

Define an LFSR with L stages and with a connection trinomial of the form: x^L + x^K + 1.

Parameters:

l - Size of the register; ie. number of levels/stages of this LFSR. Is also the degree of the connection trinomial.

k - Degree/power of the mid-tap within the LFSR.

Throws:

java.lang.IllegalArgumentException - If k <= 0 or k >= l.

Method Detail

clone

public java.lang.Object clone()

Description copied from class: BigRegister

Return a reference to a duplicate of this.

Overrides:

clone in class BigRegister

clock

public void clock(int ticks)

Repeatedly invoke the engineClock() method until the LFSR has been clocked ticks times.

Parameters:

ticks - Number of steps to clock the FSR by. If it is <= 0 nothing happens.

engineClock

protected void engineClock(int ticks)

Clock the register ticks steps.

Parameters:

ticks - Number of steps to clock the register. It is the responsibility of the caller to ensure that this value never exceeds that of slice.

next

public long next(int count)

Return the value of the leftmost count bits of this LFSR and clock it by as many ticks. Note however that only the minimum of count and slice bits, among those returned, are meaningful.

Parameters:

count - Number of leftmost bits to consider. If this value is zero then return 0.

Returns:

The value of the leftmost count bits right justified in a long.

add

public void add(TrinomialLFSR gx)

Compute this += gx (mod f(x)). Note that this operation is only meaningful, when the monic trinomial is primitive.

Parameters:

gx - A representation of the terms of a polynomial to add to this.

Throws:

java.lang.IllegalArgumentException - If the argument is not in the same group as this.

subtract

public void subtract(TrinomialLFSR gx)

Compute this -= gx (mod f(x)). Note that this operation is only meaningful, when the monic trinomial is primitive. When such is the case the result is the same as that obtained by the add() method since in F₂n every polynomial is its own additive inverse.

Parameters:

gx - A representation of the terms of a polynomial to subtract from this.

Throws:

java.lang.IllegalArgumentException - If the argument is not in the same group as this.

multiply

public void multiply(TrinomialLFSR gx)

Compute this *= gx (mod f(x)). Note that this operation is only meaningful, when the monic trinomial is primitive.

Parameters:

gx - A representation of the terms of a polynomial to multiply by this.

Throws:

java.lang.IllegalArgumentException - If the argument is not in the same group as this.

multiply

public static TrinomialLFSR multiply(TrinomialLFSR p,
                                     TrinomialLFSR q)

Return the product of the two arguments modulo f(x)), where both arguments are members of the same polynomial group with the same monic trinomial f(x). Note that this operation is only meaningful, when the monic trinomial is primitive.

Parameters:

p - A representation of the terms of the first polynomial multiplicand.

q - A representation of the terms of the second polynomial multiplicand.

Returns:

The product of the two arguments modulo f(x)).

Throws:

java.lang.IllegalArgumentException - If the arguments are not from the same group.

pow

public void pow(BigRegister n)

Raise this to the nth power modulo f(x)). Note that this operation is only meaningful, when the monic trinomial is primitive.

Parameters:

n - Bit representation of the power to raise this polynomial representation to.

Throws:

java.lang.IllegalArgumentException - If the argument's size is greater than that of this.

resetX

public void resetX(int n)

Set the LFSR's initial state to a value that corresponds to the polynomial term of the designated degree.

Parameters:

n - Reset the register's contents to all zeroes except for a 1 at the index position corresponding to the term xⁿ.

Throws:

java.lang.IllegalArgumentException - If the argument value is negative or greater than or equal to this LFSR's trinomial degree.

setX

public void setX(int n)

Set (to one) this LFSR's polynomial term of the given degree. The other stages, in contrast to the resetX() method, are unaffected.

Parameters:

n - Set (to one) the register position of the term xⁿ.

Throws:

java.lang.IllegalArgumentException - If the argument value is negative or greater than or equal to this LFSR's trinomial degree.

indexOfX

public int indexOfX(int degree)

Return the register's index relative to the polynomial term x^degree.

Parameters:

degree - The power of the invariate x, for which the register's index is to be found.

Returns:

The register's index relative to the polynomial term x^degree.

Throws:

java.lang.IllegalArgumentException - If the argument value is negative or greater than or equal to this LFSR's trinomial degree.

degreeAt

public int degreeAt(int index)

Return the power of the term x^result relative to the given register's index.

Parameters:

index - The register's index relative to the polynomial term x^result.

Returns:

The power of the invariate x relative to the given register's index.

Throws:

java.lang.IllegalArgumentException - If the argument value is negative or greater than or equal to this LFSR's trinomial degree.

trinomialOne

public TrinomialLFSR trinomialOne()

Return a TrinomialLFSR object whose state is set to the powers of the polynomial p(x) such that p(x) = 1 in the polynomial Group defined over the trinomial function of this object.

Returns:

A TrinomialLFSR object whose state is set to the powers of the polynomial p(x) such that p(x) = 1 in the polynomial Group defined over the trinomial function of this object.

trinomialX

public TrinomialLFSR trinomialX()

Return a TrinomialLFSR object whose state is set to the powers of the polynomial p(x) such that p(x) = x in the polynomial Group defined over the trinomial function of this object.

Returns:

A TrinomialLFSR object whose state is set to the powers of the polynomial p(x) such that p(x) = x in the polynomial Group defined over the trinomial function of this object.

getSize

public int getSize()

Return the number of elements in this LFSR, which is also the degree of the trinomial.

Overrides:

getSize in class BigRegister

Returns:

The number of elements in this LFSR.

getMidTap

public int getMidTap()

Return the degree/power of the mid-tap element in this LFSR.

Returns:

The degree/power of the mid-tap element in this LFSR.

getSlice

public int getSlice()

Return the maximum number of meaningful bits in this LFSR, which is also the maximum number of bits that can be processed in one operation without loss of desired output sequence.

Returns:

The maximum number of meaningful bits in this LFSR.

isSameValue

public boolean isSameValue(TrinomialLFSR x)

Return true if the TrinomialLFSR x has equal characteristics and contents to this one; false otherwise.

NOTE: the equals method is not used, because this is a mutable object (see the requirements for equals in the Java Language Spec).

Returns:

true iff x has equal characteristics and contents.

compareTo

public int compareTo(TrinomialLFSR x)

Compare this LFSR to the argument, returning -1, 0 or 1 for less than, equal to, or greater than comparison.

Returns:

-1, 0, +1 If the contents of this object are respectively less than, equal to, or greater than those of the argument.

isSameGroup

public boolean isSameGroup(TrinomialLFSR x)

Return true iff the argument is a polynomial that belongs to the same Group as this.

Returns:

true iff the argument is a polynomial that belongs to the same Group as this.

toBigRegister

public BigRegister toBigRegister()

Return the state of this LFSR as a BigRegister object where now the powers of the polynomial terms are ordered in ascending succession starting from power 0 at index 0.

Returns:

The state of this LFSR as a BigRegister object where now the powers of the polynomial terms are ordered in ascending succession starting from power 0 at index 0.

toString

public java.lang.String toString()

Return a formatted String representation of the binary contents of this.

Overrides:

toString in class BigRegister

Returns:

A formatted string representation of the binary contents of this.

toPolynomial

public java.lang.String toPolynomial()

Return a formatted String representation of the polynomial form represented by this LFSR's state.

Returns:

A formatted string representation of the binary contents of this.