package org.bouncycastle.math.ec;
import java.math.BigInteger;
import java.util.Random;
public abstract class ECFieldElement
implements ECConstants
{
BigInteger x;
protected ECFieldElement(BigInteger x)
{
this.x = x;
}
public BigInteger toBigInteger()
{
return x;
}
public abstract String getFieldName();
public abstract ECFieldElement add(ECFieldElement b);
public abstract ECFieldElement subtract(ECFieldElement b);
public abstract ECFieldElement multiply(ECFieldElement b);
public abstract ECFieldElement divide(ECFieldElement b);
public abstract ECFieldElement negate();
public abstract ECFieldElement square();
public abstract ECFieldElement invert();
public abstract ECFieldElement sqrt();
public String toString()
{
return this.x.toString(2);
}
public static class Fp extends ECFieldElement
{
BigInteger q;
public Fp(BigInteger q, BigInteger x)
{
super(x);
if (x.compareTo(q) >= 0)
{
throw new IllegalArgumentException("x value too large in field element");
}
this.q = q;
}
/**
* return the field name for this field.
*
* @return the string "Fp".
*/
public String getFieldName()
{
return "Fp";
}
public BigInteger getQ()
{
return q;
}
public ECFieldElement add(ECFieldElement b)
{
return new Fp(q, x.add(b.x).mod(q));
}
public ECFieldElement subtract(ECFieldElement b)
{
return new Fp(q, x.subtract(b.x).mod(q));
}
public ECFieldElement multiply(ECFieldElement b)
{
return new Fp(q, x.multiply(b.x).mod(q));
}
public ECFieldElement divide(ECFieldElement b)
{
return new Fp(q, x.multiply(b.x.modInverse(q)).mod(q));
}
public ECFieldElement negate()
{
return new Fp(q, x.negate().mod(q));
}
public ECFieldElement square()
{
return new Fp(q, x.multiply(x).mod(q));
}
public ECFieldElement invert()
{
return new Fp(q, x.modInverse(q));
}
// D.1.4 91
/**
* return a sqrt root - the routine verifies that the calculation
* returns the right value - if none exists it returns null.
*/
public ECFieldElement sqrt()
{
if (!q.testBit(0))
{
throw new RuntimeException("not done yet");
}
// p mod 4 == 3
if (q.testBit(1))
{
// z = g^(u+1) + p, p = 4u + 3
ECFieldElement z = new Fp(q, x.modPow(q.shiftRight(2).add(ONE), q));
return z.square().equals(this) ? z : null;
}
// p mod 4 == 1
BigInteger qMinusOne = q.subtract(ECConstants.ONE);
BigInteger legendreExponent = qMinusOne.shiftRight(1);
if (!(x.modPow(legendreExponent, q).equals(ECConstants.ONE)))
{
return null;
}
BigInteger u = qMinusOne.shiftRight(2);
BigInteger k = u.shiftLeft(1).add(ECConstants.ONE);
BigInteger Q = this.x;
BigInteger fourQ = Q.shiftLeft(2).mod(q);
BigInteger U, V;
Random rand = new Random();
do
{
BigInteger P;
do
{
P = new BigInteger(q.bitLength(), rand);
}
while (P.compareTo(q) >= 0
|| !(P.multiply(P).subtract(fourQ).modPow(legendreExponent, q).equals(qMinusOne)));
BigInteger[] result = lucasSequence(q, P, Q, k);
U = result[0];
V = result[1];
if (V.multiply(V).mod(q).equals(fourQ))
{
// Integer division by 2, mod q
if (V.testBit(0))
{
V = V.add(q);
}
V = V.shiftRight(1);
//assert V.multiply(V).mod(q).equals(x);
return new ECFieldElement.Fp(q, V);
}
}
while (U.equals(ECConstants.ONE) || U.equals(qMinusOne));
return null;
// BigInteger qMinusOne = q.subtract(ECConstants.ONE);
// BigInteger legendreExponent = qMinusOne.shiftRight(1); //divide(ECConstants.TWO);
// if (!(x.modPow(legendreExponent, q).equals(ECConstants.ONE)))
// {
// return null;
// }
//
// Random rand = new Random();
// BigInteger fourX = x.shiftLeft(2);
//
// BigInteger r;
// do
// {
// r = new BigInteger(q.bitLength(), rand);
// }
// while (r.compareTo(q) >= 0
// || !(r.multiply(r).subtract(fourX).modPow(legendreExponent, q).equals(qMinusOne)));
//
// BigInteger n1 = qMinusOne.shiftRight(2); //.divide(ECConstants.FOUR);
// BigInteger n2 = n1.add(ECConstants.ONE); //q.add(ECConstants.THREE).divide(ECConstants.FOUR);
//
// BigInteger wOne = WOne(r, x, q);
// BigInteger wSum = W(n1, wOne, q).add(W(n2, wOne, q)).mod(q);
// BigInteger twoR = r.shiftLeft(1); //ECConstants.TWO.multiply(r);
//
// BigInteger root = twoR.modPow(q.subtract(ECConstants.TWO), q)
// .multiply(x).mod(q)
// .multiply(wSum).mod(q);
//
// return new Fp(q, root);
}
// private static BigInteger W(BigInteger n, BigInteger wOne, BigInteger p)
// {
// if (n.equals(ECConstants.ONE))
// {
// return wOne;
// }
// boolean isEven = !n.testBit(0);
// n = n.shiftRight(1);//divide(ECConstants.TWO);
// if (isEven)
// {
// BigInteger w = W(n, wOne, p);
// return w.multiply(w).subtract(ECConstants.TWO).mod(p);
// }
// BigInteger w1 = W(n.add(ECConstants.ONE), wOne, p);
// BigInteger w2 = W(n, wOne, p);
// return w1.multiply(w2).subtract(wOne).mod(p);
// }
//
// private BigInteger WOne(BigInteger r, BigInteger x, BigInteger p)
// {
// return r.multiply(r).multiply(x.modPow(q.subtract(ECConstants.TWO), q)).subtract(ECConstants.TWO).mod(p);
// }
private static BigInteger[] lucasSequence(
BigInteger p,
BigInteger P,
BigInteger Q,
BigInteger k)
{
int n = k.bitLength();
int s = k.getLowestSetBit();
BigInteger Uh = ECConstants.ONE;
BigInteger Vl = ECConstants.TWO;
BigInteger Vh = P;
BigInteger Ql = ECConstants.ONE;
BigInteger Qh = ECConstants.ONE;
for (int j = n - 1; j >= s + 1; --j)
{
Ql = Ql.multiply(Qh).mod(p);
if (k.testBit(j))
{
Qh = Ql.multiply(Q).mod(p);
Uh = Uh.multiply(Vh).mod(p);
Vl = Vh.multiply(Vl).subtract(P.multiply(Ql)).mod(p);
Vh = Vh.multiply(Vh).subtract(Qh.shiftLeft(1)).mod(p);
}
else
{
Qh = Ql;
Uh = Uh.multiply(Vl).subtract(Ql).mod(p);
Vh = Vh.multiply(Vl).subtract(P.multiply(Ql)).mod(p);
Vl = Vl.multiply(Vl).subtract(Ql.shiftLeft(1)).mod(p);
}
}
Ql = Ql.multiply(Qh).mod(p);
Qh = Ql.multiply(Q).mod(p);
Uh = Uh.multiply(Vl).subtract(Ql).mod(p);
Vl = Vh.multiply(Vl).subtract(P.multiply(Ql)).mod(p);
Ql = Ql.multiply(Qh).mod(p);
for (int j = 1; j <= s; ++j)
{
Uh = Uh.multiply(Vl).mod(p);
Vl = Vl.multiply(Vl).subtract(Ql.shiftLeft(1)).mod(p);
Ql = Ql.multiply(Ql).mod(p);
}
return new BigInteger[]{ Uh, Vl };
}
public boolean equals(Object other)
{
if (other == this)
{
return true;
}
if (!(other instanceof ECFieldElement.Fp))
{
return false;
}
ECFieldElement.Fp o = (ECFieldElement.Fp)other;
return q.equals(o.q) && x.equals(o.x);
}
public int hashCode()
{
return q.hashCode() ^ x.hashCode();
}
}
/**
* Class representing the Elements of the finite field
* F2m in polynomial basis (PB)
* representation. Both trinomial (TPB) and pentanomial (PPB) polynomial
* basis representations are supported. Gaussian normal basis (GNB)
* representation is not supported.
*/
public static class F2m extends ECFieldElement
{
/**
* Indicates gaussian normal basis representation (GNB). Number chosen
* according to X9.62. GNB is not implemented at present.
*/
public static final int GNB = 1;
/**
* Indicates trinomial basis representation (TPB). Number chosen
* according to X9.62.
*/
public static final int TPB = 2;
/**
* Indicates pentanomial basis representation (PPB). Number chosen
* according to X9.62.
*/
public static final int PPB = 3;
/**
* TPB or PPB.
*/
private int representation;
/**
* The exponent m of F2m.
*/
private int m;
/**
* TPB: The integer k where xm +
* xk + 1 represents the reduction polynomial
* f(z).
* PPB: The integer k1 where xm +
* xk3 + xk2 + xk1 + 1
* represents the reduction polynomial f(z).
*/
private int k1;
/**
* TPB: Always set to 0
* PPB: The integer k2 where xm +
* xk3 + xk2 + xk1 + 1
* represents the reduction polynomial f(z).
*/
private int k2;
/**
* TPB: Always set to 0
* PPB: The integer k3 where xm +
* xk3 + xk2 + xk1 + 1
* represents the reduction polynomial f(z).
*/
private int k3;
/**
* Constructor for PPB.
* @param m The exponent m of
* F2m.
* @param k1 The integer k1 where xm +
* xk3 + xk2 + xk1 + 1
* represents the reduction polynomial f(z).
* @param k2 The integer k2 where xm +
* xk3 + xk2 + xk1 + 1
* represents the reduction polynomial f(z).
* @param k3 The integer k3 where xm +
* xk3 + xk2 + xk1 + 1
* represents the reduction polynomial f(z).
* @param x The BigInteger representing the value of the field element.
*/
public F2m(
int m,
int k1,
int k2,
int k3,
BigInteger x)
{
super(x);
if ((k2 == 0) && (k3 == 0))
{
this.representation = TPB;
}
else
{
if (k2 >= k3)
{
throw new IllegalArgumentException(
"k2 must be smaller than k3");
}
if (k2 <= 0)
{
throw new IllegalArgumentException(
"k2 must be larger than 0");
}
this.representation = PPB;
}
if (x.signum() < 0)
{
throw new IllegalArgumentException("x value cannot be negative");
}
this.m = m;
this.k1 = k1;
this.k2 = k2;
this.k3 = k3;
}
/**
* Constructor for TPB.
* @param m The exponent m of
* F2m.
* @param k The integer k where xm +
* xk + 1 represents the reduction
* polynomial f(z).
* @param x The BigInteger representing the value of the field element.
*/
public F2m(int m, int k, BigInteger x)
{
// Set k1 to k, and set k2 and k3 to 0
this(m, k, 0, 0, x);
}
public String getFieldName()
{
return "F2m";
}
/**
* Checks, if the ECFieldElements a and b
* are elements of the same field F2m
* (having the same representation).
* @param a field element.
* @param b field element to be compared.
* @throws IllegalArgumentException if a and b
* are not elements of the same field
* F2m (having the same
* representation).
*/
public static void checkFieldElements(
ECFieldElement a,
ECFieldElement b)
{
if ((!(a instanceof F2m)) || (!(b instanceof F2m)))
{
throw new IllegalArgumentException("Field elements are not "
+ "both instances of ECFieldElement.F2m");
}
if ((a.x.signum() < 0) || (b.x.signum() < 0))
{
throw new IllegalArgumentException(
"x value may not be negative");
}
ECFieldElement.F2m aF2m = (ECFieldElement.F2m)a;
ECFieldElement.F2m bF2m = (ECFieldElement.F2m)b;
if ((aF2m.m != bF2m.m) || (aF2m.k1 != bF2m.k1)
|| (aF2m.k2 != bF2m.k2) || (aF2m.k3 != bF2m.k3))
{
throw new IllegalArgumentException("Field elements are not "
+ "elements of the same field F2m");
}
if (aF2m.representation != bF2m.representation)
{
// Should never occur
throw new IllegalArgumentException(
"One of the field "
+ "elements are not elements has incorrect representation");
}
}
/**
* Computes z * a(z) mod f(z), where f(z) is
* the reduction polynomial of this.
* @param a The polynomial a(z) to be multiplied by
* z mod f(z).
* @return z * a(z) mod f(z)
*/
private BigInteger multZModF(final BigInteger a)
{
// Left-shift of a(z)
BigInteger az = a.shiftLeft(1);
if (az.testBit(this.m))
{
// If the coefficient of z^m in a(z) equals 1, reduction
// modulo f(z) is performed: Add f(z) to to a(z):
// Step 1: Unset mth coeffient of a(z)
az = az.clearBit(this.m);
// Step 2: Add r(z) to a(z), where r(z) is defined as
// f(z) = z^m + r(z), and k1, k2, k3 are the positions of
// the non-zero coefficients in r(z)
az = az.flipBit(0);
az = az.flipBit(this.k1);
if (this.representation == PPB)
{
az = az.flipBit(this.k2);
az = az.flipBit(this.k3);
}
}
return az;
}
public ECFieldElement add(final ECFieldElement b)
{
// No check performed here for performance reasons. Instead the
// elements involved are checked in ECPoint.F2m
// checkFieldElements(this, b);
if (b.x.signum() == 0)
{
return this;
}
return new F2m(this.m, this.k1, this.k2, this.k3, this.x.xor(b.x));
}
public ECFieldElement subtract(final ECFieldElement b)
{
// Addition and subtraction are the same in F2m
return add(b);
}
public ECFieldElement multiply(final ECFieldElement b)
{
// Left-to-right shift-and-add field multiplication in F2m
// Input: Binary polynomials a(z) and b(z) of degree at most m-1
// Output: c(z) = a(z) * b(z) mod f(z)
// No check performed here for performance reasons. Instead the
// elements involved are checked in ECPoint.F2m
// checkFieldElements(this, b);
final BigInteger az = this.x;
BigInteger bz = b.x;
BigInteger cz;
// Compute c(z) = a(z) * b(z) mod f(z)
if (az.testBit(0))
{
cz = bz;
}
else
{
cz = ECConstants.ZERO;
}
for (int i = 1; i < this.m; i++)
{
// b(z) := z * b(z) mod f(z)
bz = multZModF(bz);
if (az.testBit(i))
{
// If the coefficient of x^i in a(z) equals 1, b(z) is added
// to c(z)
cz = cz.xor(bz);
}
}
return new ECFieldElement.F2m(m, this.k1, this.k2, this.k3, cz);
}
public ECFieldElement divide(final ECFieldElement b)
{
// There may be more efficient implementations
ECFieldElement bInv = b.invert();
return multiply(bInv);
}
public ECFieldElement negate()
{
// -x == x holds for all x in F2m
return this;
}
public ECFieldElement square()
{
// Naive implementation, can probably be speeded up using modular
// reduction
return multiply(this);
}
public ECFieldElement invert()
{
// Inversion in F2m using the extended Euclidean algorithm
// Input: A nonzero polynomial a(z) of degree at most m-1
// Output: a(z)^(-1) mod f(z)
// u(z) := a(z)
BigInteger uz = this.x;
if (uz.signum() <= 0)
{
throw new ArithmeticException("x is zero or negative, " +
"inversion is impossible");
}
// v(z) := f(z)
BigInteger vz = ECConstants.ONE.shiftLeft(m);
vz = vz.setBit(0);
vz = vz.setBit(this.k1);
if (this.representation == PPB)
{
vz = vz.setBit(this.k2);
vz = vz.setBit(this.k3);
}
// g1(z) := 1, g2(z) := 0
BigInteger g1z = ECConstants.ONE;
BigInteger g2z = ECConstants.ZERO;
// while u != 1
while (!(uz.equals(ECConstants.ZERO)))
{
// j := deg(u(z)) - deg(v(z))
int j = uz.bitLength() - vz.bitLength();
// If j < 0 then: u(z) <-> v(z), g1(z) <-> g2(z), j := -j
if (j < 0)
{
final BigInteger uzCopy = uz;
uz = vz;
vz = uzCopy;
final BigInteger g1zCopy = g1z;
g1z = g2z;
g2z = g1zCopy;
j = -j;
}
// u(z) := u(z) + z^j * v(z)
// Note, that no reduction modulo f(z) is required, because
// deg(u(z) + z^j * v(z)) <= max(deg(u(z)), j + deg(v(z)))
// = max(deg(u(z)), deg(u(z)) - deg(v(z)) + deg(v(z))
// = deg(u(z))
uz = uz.xor(vz.shiftLeft(j));
// g1(z) := g1(z) + z^j * g2(z)
g1z = g1z.xor(g2z.shiftLeft(j));
// if (g1z.bitLength() > this.m) {
// throw new ArithmeticException(
// "deg(g1z) >= m, g1z = " + g1z.toString(2));
// }
}
return new ECFieldElement.F2m(
this.m, this.k1, this.k2, this.k3, g2z);
}
public ECFieldElement sqrt()
{
throw new RuntimeException("Not implemented");
}
/**
* @return the representation of the field
* F2m, either of
* TPB (trinomial
* basis representation) or
* PPB (pentanomial
* basis representation).
*/
public int getRepresentation()
{
return this.representation;
}
/**
* @return the degree m of the reduction polynomial
* f(z).
*/
public int getM()
{
return this.m;
}
/**
* @return TPB: The integer k where xm +
* xk + 1 represents the reduction polynomial
* f(z).
* PPB: The integer k1 where xm +
* xk3 + xk2 + xk1 + 1
* represents the reduction polynomial f(z).
*/
public int getK1()
{
return this.k1;
}
/**
* @return TPB: Always returns 0
* PPB: The integer k2 where xm +
* xk3 + xk2 + xk1 + 1
* represents the reduction polynomial f(z).
*/
public int getK2()
{
return this.k2;
}
/**
* @return TPB: Always set to 0
* PPB: The integer k3 where xm +
* xk3 + xk2 + xk1 + 1
* represents the reduction polynomial f(z).
*/
public int getK3()
{
return this.k3;
}
public boolean equals(Object anObject)
{
if (anObject == this)
{
return true;
}
if (!(anObject instanceof ECFieldElement.F2m))
{
return false;
}
ECFieldElement.F2m b = (ECFieldElement.F2m)anObject;
return ((this.m == b.m) && (this.k1 == b.k1) && (this.k2 == b.k2)
&& (this.k3 == b.k3)
&& (this.representation == b.representation)
&& (this.x.equals(b.x)));
}
public int hashCode()
{
return x.hashCode() ^ m ^ k1 ^ k2 ^ k3;
}
}
}