EC.zip_ECC cryptography_cryptography_ecc_ecc java_zip

/* * $Log: ECField.java,v $ * Revision 1.2 2001/08/19 01:59:47 stuart * gfNew() * */ package bmsi.security; import java.util.Random; import java.math.BigInteger; /** * Algebraic operations on the finite field GF(2^m). * * This public domain software was written by Stuart D. Gathman, * based on C software written by Paulo S.L.M. Barreto * <pbarreto@nw.com.br> based on original C++ software written by * George Barwood <george.barwood@dial.pipex.com> * * THIS SOFTWARE IS PROVIDED BY THE AUTHORS ''AS IS'' AND ANY EXPRESS * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * * References * ========== * * 1. Erik De Win <erik.dewin@esat.kuleuven.ac.be> et alii: * "A Fast Software Implementation for Arithmetic Operations in GF(2^n)", * presented at Asiacrypt96 (preprint). * * Change log * ========== * * 1997.09.15: * -- Fixed a bug in gfTrace() which would give wrong values (and * possibly also addressing error once in a while) for every field * where where GF_TM0 != 1. Thanks to Dave Dahm <Dave.Dahm@unisys.com> * for pointing out this bug and providing debugging data. */ public class ECField implements ECParam255 { private static final int BITS_PER_LUNIT = 16; /** Maximum units in a field point. */ private static final int GF_POINT_UNITS = 2*(GF_K+1); private static final int BASE = 1 << GF_L; static final char TOGGLE = (char)(BASE - 1); // used by ECTest //private final int GF_POINT_UNITS = 2*(GF_K+1); //private final int BASE = 1 << GF_L; //private final int TOGGLE = BASE - 1; // index range is [0..(BASE-2)] private static final char[] expt = new char[BASE]; // index range is [1..(BASE-1)], but logt[0] is set to (BASE-1) private static final char[] logt = new char[BASE]; private static final char[] nzt = { 1, GF_NZT }; /* Initialize the log and exponent tables. */ static { int root, i, j; root = BASE | GF_RP; expt[0] = 1; for (i = 1; i < BASE; i++) { j = expt[i-1] << 1; if ((j & BASE) != 0) { j ^= root; } expt[i] = (char)j; } for (i = 0; i < TOGGLE; i++) { logt[expt[i]] = (char)i; } logt[0] = TOGGLE; /* a trick used by gfMultiply, gfSquare, gfAddMul */ } /** Allocate a new polynomial. */ static char[] gfNew() { return new char[GF_POINT_UNITS]; } static char[] gfNew(char[] q) { char[] p = new char[GF_POINT_UNITS]; System.arraycopy(q,0,p,0,q[0] + 1); return p; } static boolean gfEqual(char[] p,char[] q) { int n = p[0] + 1; for (int i = 0; i < n; ++i) if (p[i] != q[i]) return false; return true; } /* public boolean equals(Object obj) { if (!(obj instanceof ECField)) return false; ECField q = (ECField)obj; int n = p[0] + 1; for (int i = 0; i <= n; ++i) if (p[i] != q.p[i]) return false; return true; } */ static void gfClear(char[] p) { for (int i = 0; i < p.length; ++i) p[i] = 0; } static void gfCopy(char[] p, char[] q) { System.arraycopy(q,0,p,0,q[0] + 1); } /** Set p := q + r */ static void gfAdd(char[] p, char[] q, char[] r) { int i; if (q[0] > r[0]) { /* xor the the common-degree coefficients: */ for (i = 1; i <= r[0]; i++) { p[i] = (char)(q[i] ^ r[i]); } /* invariant: i == r[0] + 1 */ System.arraycopy(q,i,p,i,q[0] - r[0]); /* deg(p) inherits the value of deg(q): */ p[0] = q[0]; } else if (q[0] < r[0]) { /* xor the the common-degree coefficients: */ for (i = 1; i <= q[0]; i++) { p[i] = (char)(q[i] ^ r[i]); } /* invariant: i == q[0] + 1 */ System.arraycopy(r,i,p,i,r[0] - q[0]); /* deg(p) inherits the value of deg(r): */ p[0] = r[0]; } else { /* deg(q) == deg(r) */ /* scan to determine deg(p): */ for (i = q[0]; i > 0; i--) { if ((q[i] ^ r[i]) != 0) break; } /* xor the the common-degree coefficients, if any is left: */ for (p[0] = (char)i; i > 0; i--) { p[i] = (char)(q[i] ^ r[i]); } } } /** reduce p mod the irreducible trinomial x^GF_K + x^GF_T + 1 */ private static void gfReduce (char[] p) { int i; for (i = p[0]; i > GF_K; i--) { p[i - GF_K] ^= p[i]; p[i + GF_T - GF_K] ^= p[i]; p[i] = 0; } if (p[0] > GF_K) { /* scan to update deg(p): */ p[0] = GF_K; while (p[0] != 0 && p[p[0]] == 0) { p[0]--; } } } /** set r := p * q mod (x^GF_K + x^GF_T + 1) */ static void gfMultiply(char[] r, char[] p, char[] q) { int x, log_pi, log_qj; char[] lg = new char[GF_K + 2]; // clear after use if (r == p || r == q) throw new IllegalArgumentException("destination cannot overlap source"); if (p[0] != 0 && q[0] != 0) { /* precompute logt[q[j]] to reduce table lookups: */ for (int j = q[0]; j != 0; j--) { lg[j] = logt[q[j]]; } /* perform multiplication: */ gfClear(r); for (int i = p[0]; i != 0; i--) { if ((log_pi = logt[p[i]]) != TOGGLE) { /* p[i] != 0 */ for (int j = q[0]; j != 0; j--) { if ((log_qj = lg[j]) != TOGGLE) { /* q[j] != 0 */ /* r[i+j-1] ^= expt[(logt[p[i]] + logt[q[j]]) % TOGGLE]; */ r[i+j-1] ^= expt[ (x = log_pi + log_qj) >= TOGGLE ? x - TOGGLE : x ]; } } } } r[0] = (char)(p[0] + q[0] - 1); /* reduce r mod (x^GF_K + x^GF_T + 1): */ gfReduce(r); } else { /* set r to the null polynomial: */ r[0] = 0; } /* destroy potentially sensitive data: */ x = log_pi = log_qj = 0; gfClear(lg); } /** set r := p^2 mod (x^GF_K + x^GF_T + 1). */ static void gfSquare(char[] r,char[] p) { if (p[0] != 0) { /* in what follows, note that (x != 0) => (x^2 = exp((2 * log(x)) % TOGGLE)): */ int i = p[0]; int x = logt[p[i]]; if (x != TOGGLE) { /* p[i] != 0 */ r[2*i - 1] = expt[(x += x) >= TOGGLE ? x - TOGGLE : x]; } else { r[2*i - 1] = 0; } for (i = p[0] - 1; i != 0; i--) { r[2*i] = 0; x = logt[p[i]]; if (x != TOGGLE) { /* p[i] != 0 */ r[2*i - 1] = expt[(x += x) >= TOGGLE ? x - TOGGLE : x]; } else { r[2*i - 1] = 0; } } r[0] = (char)(2*p[0] - 1); /* reduce r mod (x^GF_K + x^GF_T + 1): */ gfReduce(r); } else { r[0] = 0; } } private static void assert(boolean cond) { if (!cond) throw new RuntimeException("Assertion failed"); } /** sets p := (b^(-1))*p mod (x^GF_K + x^GF_T + 1) */ static void gfSmallDiv(char[] p, char b) { int x, lb = logt[b]; assert(b != 0); for (int i = p[0]; i > 0; i--) { if ((x = logt[p[i]]) != TOGGLE) { /* p[i] != 0 */ p[i] = expt[(x += TOGGLE - lb) >= TOGGLE ? x - TOGGLE : x]; } } } private static void gfAddMul( final char[] a, final int alpha, final int j, final char[] b) { final int la = logt[alpha]; int i = b[0]; int x = j + i; int a0 = a[0]; while (a0 < x) a[++a0] = 0; while (i > 0) { if ((x = logt[b[i]]) != TOGGLE) /* b[i] != 0 */ //a[j+i] ^= expt[(x += la) % TOGGLE]; // 30ms/invert slower a[j + i] ^= expt[(x += la) >= TOGGLE ? x - TOGGLE : x]; --i; } while (a0 > 0 && a[a0]==0) --a0; a[0] = (char)a0; } /** sets b := a^(-1) mod (x^GF_K + x^GF_T + 1) warning: a and b must not o