All Packages Class Hierarchy This Package Previous Next Index
Class cryptix.util.math.TrinomialLFSR
java.lang.Object
|
+----cryptix.util.math.BigRegister
|
+----cryptix.util.math.TrinomialLFSR
- public class TrinomialLFSR
- extends BigRegister
- implements Cloneable, 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 + xK + 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
sj 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 + c1D + c
2D2
+ ... + cLDL
Î Z2[D]
A Linear Feedback Shift Register (LFSR) with a trinomial function of
the form 1 + xK + xL 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
2, ensures that each of the LFSR's 2L - 1 initial states produces an
output sequence with maximum possible period 2
L - 1.
- If 2L - 1 is a prime
(a Mersenne prime), then every irreducible polynomial of
degree L in Z2[x]
is also primitive.
- Irreducible trinomials, f(x), of degree L can
be used to represent the elements of the finite field F2L = Z2
[x]/(f(x)), the set of all polynomials in Z
2[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 xL 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 xL
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
F2L.
- terms of a polynomial: the correspondence between
the LFSR stages and the powers of x (the polynomial
invariate) in the GF[2L]
with f(x) = xL + xK + 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 Z2, 2m - 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 xm
+ xk + 1 is irreducible over
Z2.
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:
- [HAC]
A. J. Menezes, P. C. van Oorschot, S. A. Vanstone,
Handbook of Applied Cryptography
CRC Press 1997, pp 195-212.
- [AC2]
Bruce Schneier,
Applied Cryptography, 2nd edition,
John Wiley & Sons, Inc. 1996, pp 372-428.
- [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 $
- Author:
- Raif S. Naffah
-
TrinomialLFSR(int, int)
- Define an LFSR with
L
stages and with a connection
trinomial of the form: xL +
xK + 1.
-
add(TrinomialLFSR)
- Compute
this += gx (mod f(x))
.
-
clock(int)
- Repeatedly invoke the
engineClock()
method until
the LFSR has been clocked ticks
times.
-
clone()
- Return a reference to a duplicate of
this
.
-
compareTo(TrinomialLFSR)
- Compare this LFSR to the argument, returning -1, 0 or 1 for
less than, equal to, or greater than comparison.
-
degreeAt(int)
- Return the power of the term xresult
relative to the given register's index.
-
engineClock(int)
- Clock the register ticks steps.
-
getMidTap()
- Return the degree/power of the mid-tap element in this LFSR.
-
getSize()
- Return the number of elements in this LFSR, which is also
the degree of the trinomial.
-
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.
-
indexOfX(int)
- Return the register's index relative to the polynomial
term xdegree.
-
isSameGroup(TrinomialLFSR)
- Return true iff the argument is a polynomial that belongs to
the same Group as
this
.
-
isSameValue(TrinomialLFSR)
- Return true if the TrinomialLFSR x has equal characteristics
and contents to this one; false otherwise.
-
multiply(TrinomialLFSR)
- Compute
this *= gx (mod f(x))
.
-
multiply(TrinomialLFSR, TrinomialLFSR)
- 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).
-
next(int)
- Return the value of the leftmost
count
bits of
this LFSR and clock it by as many ticks.
-
pow(BigRegister)
- Raise
this
to the n
th power modulo
f(x)).
-
resetX(int)
- Set the LFSR's initial state to a value that corresponds
to the polynomial term of the designated degree.
-
setX(int)
- Set (to one) this LFSR's polynomial term of
the given degree.
-
subtract(TrinomialLFSR)
- Compute
this -= gx (mod f(x))
.
-
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.
-
toPolynomial()
- Return a formatted
String
representation of the
polynomial form represented by this
LFSR's state.
-
toString()
- Return a formatted
String
representation of the binary
contents of this
.
-
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.
-
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.
TrinomialLFSR
public TrinomialLFSR(int l,
int k)
- Define an LFSR with
L
stages and with a connection
trinomial of the form: xL +
xK + 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: IllegalArgumentException
- If k <= 0 or k >= l.
clone
public Object clone()
- 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: 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
F2n every polynomial is
its own additive inverse.
- Parameters:
- gx - A representation of the terms of a polynomial to
subtract from
this
.
- Throws: 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: 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: IllegalArgumentException
- If the arguments are not
from the same group.
pow
public void pow(BigRegister n)
- Raise
this
to the n
th 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: 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 xn.
- Throws: 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
xn.
- Throws: 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 xdegree.
- 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
xdegree.
- Throws: 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 xresult
relative to the given register's index.
- Parameters:
- index - The register's index relative to the polynomial term
xresult.
- Returns:
- The power of the invariate x relative to the given
register's index.
- Throws: 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.
- Returns:
- The number of elements in this LFSR.
- Overrides:
- getSize in class BigRegister
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 String toString()
- Return a formatted
String
representation of the binary
contents of this
.
- Returns:
- A formatted string representation of the binary contents
of
this
.
- Overrides:
- toString in class BigRegister
toPolynomial
public 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
.
All Packages Class Hierarchy This Package Previous Next Index