All Packages Class Hierarchy This Package Previous Next Index
java.lang.Object
|
+----cryptix.util.math.BigRegister
|
+----cryptix.util.math.TrinomialLFSR
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:
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:
Some terms and conventions associated with LFSRs, and used in this implementation, are:
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.
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:
Copyright © 1995-1997
Systemics Ltd on behalf of the
Cryptix Development Team.
All rights reserved.
$Revision: 1.2 $
L stages and with a connection
trinomial of the form: xL +
xK + 1.
this += gx (mod f(x)).
engineClock() method until
the LFSR has been clocked ticks times.
this.
this.
this *= gx (mod f(x)).
count bits of
this LFSR and clock it by as many ticks.
this to the nth power modulo
f(x)).
this -= gx (mod f(x)).
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.
String representation of the
polynomial form represented by this LFSR's state.
String representation of the binary
contents of this.
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 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.
public TrinomialLFSR(int l,
int k)
L stages and with a connection
trinomial of the form: xL +
xK + 1.
public Object clone()
this.
public void clock(int ticks)
engineClock() method until
the LFSR has been clocked ticks times.
protected void engineClock(int ticks)
slice.
public long next(int count)
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.
count bits
right justified in a long.
public void add(TrinomialLFSR gx)
this += gx (mod f(x)). Note that this
operation is only meaningful, when the monic trinomial is primitive.
this.
this.
public void subtract(TrinomialLFSR gx)
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.
this.
this.
public void multiply(TrinomialLFSR gx)
this *= gx (mod f(x)). Note that this
operation is only meaningful, when the monic trinomial is primitive.
this.
this.
public static TrinomialLFSR multiply(TrinomialLFSR p,
TrinomialLFSR q)
public void pow(BigRegister n)
this to the nth power modulo
f(x)). Note that this operation is only meaningful,
when the monic trinomial is primitive.
size is greater than that of this.
public void resetX(int n)
this
LFSR's trinomial degree.
public void setX(int n)
stages, in contrast
to the resetX() method, are unaffected.
this
LFSR's trinomial degree.
public int indexOfX(int degree)
this
LFSR's trinomial degree.
public int degreeAt(int index)
this
LFSR's trinomial degree.
public TrinomialLFSR trinomialOne()
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 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.
public TrinomialLFSR trinomialX()
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 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.
public int getSize()
public int getMidTap()
public int getSlice()
public boolean isSameValue(TrinomialLFSR x)
NOTE: the equals method is not used, because this is
a mutable object (see the requirements for equals in the Java Language
Spec).
public int compareTo(TrinomialLFSR x)
public boolean isSameGroup(TrinomialLFSR x)
this.
this.
public BigRegister toBigRegister()
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.
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.
public String toString()
String representation of the binary
contents of this.
this.
public String toPolynomial()
String representation of the
polynomial form represented by this LFSR's state.
this.
All Packages Class Hierarchy This Package Previous Next Index