+/* Copyright (c) 1998,2011,2014 Apple Inc. All Rights Reserved.
+ *
+ * NOTICE: USE OF THE MATERIALS ACCOMPANYING THIS NOTICE IS SUBJECT
+ * TO THE TERMS OF THE SIGNED "FAST ELLIPTIC ENCRYPTION (FEE) REFERENCE
+ * SOURCE CODE EVALUATION AGREEMENT" BETWEEN APPLE, INC. AND THE
+ * ORIGINAL LICENSEE THAT OBTAINED THESE MATERIALS FROM APPLE,
+ * INC. ANY USE OF THESE MATERIALS NOT PERMITTED BY SUCH AGREEMENT WILL
+ * EXPOSE YOU TO LIABILITY.
+ ***************************************************************************
+ *
+ * ellipticProj.c - elliptic projective algebra routines.
+ *
+ * Revision History
+ * ----------------
+ * 1 Sep 1998 at Apple
+ * Created.
+ *
+ **************************************************************
+
+ PROJECTIVE FORMAT
+
+ Functions are supplied herein for projective format
+ of points. Alternative formats differ in their
+ range of applicability, efficiency, and so on.
+ Primary advantages of the projective format herein are:
+ -- No explicit inversions (until perhaps one such at the end of
+ an elliptic multiply operation)
+ -- Fairly low operation count (~11 muls for point doubling,
+ ~16 muls for point addition)
+
+ The elliptic curve is over F_p, with p > 3 prime, and Weierstrass
+ parameterization:
+
+ y^2 = x^3 + a x + b
+
+ The projective-format coordinates are actually stored in
+ the form {X, Y, Z}, with true x,y
+ coordinates on the curve given by {x,y} = {X/Z^2, Y/Z^3}.
+ The function normalizeProj() performs the
+ transformation from projective->true.
+ (The other direction is trivial, i.e. {x,y} -> {x,y,1} will do.)
+ The basic point multiplication function is
+
+ ellMulProj()
+
+ which obtains the result k * P for given point P and integer
+ multiplier k. If true {x,y} are required for a multiple, one
+ passes a point P = {X, Y, 1} to ellMulProj(), then afterwards
+ calls normalizeProj(),
+
+ Projective format is an answer to the typical sluggishness of
+ standard elliptic arithmetic, whose explicit inversion in the
+ field is, depending of course on the machinery and programmer,
+ costly. Projective format is thus especially interesting for
+ cryptography.
+
+ REFERENCES
+
+ perspective," Springer-Verlag, manuscript
+
+ Solinas J 1998, IEEE P1363 Annex A (draft standard)
+
+***********************************************************/
+
+#include "ckconfig.h"
+#if CRYPTKIT_ELL_PROJ_ENABLE
+
+#include "ellipticProj.h"
+#include "falloc.h"
+#include "curveParams.h"
+#include "elliptic.h"
+#include "feeDebug.h"
+
+/*
+ * convert REC-style smulg to generic imulg
+ */
+#define smulg(s, g) imulg((unsigned)s, g)
+
+pointProj newPointProj(unsigned numDigits)
+{
+ pointProj pt;
+
+ pt = (pointProj) fmalloc(sizeof(pointProjStruct));
+ pt->x = newGiant(numDigits);
+ pt->y = newGiant(numDigits);
+ pt->z = newGiant(numDigits);
+ return(pt);
+}
+
+void freePointProj(pointProj pt)
+{
+ clearGiant(pt->x); freeGiant(pt->x);
+ clearGiant(pt->y); freeGiant(pt->y);
+ clearGiant(pt->z); freeGiant(pt->z);
+ ffree(pt);
+}
+
+void ptopProj(pointProj pt1, pointProj pt2)
+{
+ gtog(pt1->x, pt2->x);
+ gtog(pt1->y, pt2->y);
+ gtog(pt1->z, pt2->z);
+}
+
+/**************************************************************
+ *
+ * Elliptic curve operations
+ *
+ **************************************************************/
+
+/* Begin projective-format functions for
+
+ y^2 = x^3 + a x + b.
+
+ These are useful in elliptic curve cryptography (ECC).
+ A point is kept as a triple {X,Y,Z}, with the true (x,y)
+ coordinates given by
+
+ {x,y} = {X/Z^2, Y/Z^3}
+
+ The function normalizeProj() performs the inverse conversion to get
+ the true (x,y) pair.
+ */
+
+void ellDoubleProj(pointProj pt, curveParams *cp)
+/* pt := 2 pt on the curve. */
+{
+ giant x = pt->x, y = pt->y, z = pt->z;
+ giant t1;
+ giant t2;
+ giant t3;
+
+ if(isZero(y) || isZero(z)) {
+ int_to_giant(1,x); int_to_giant(1,y); int_to_giant(0,z);
+ return;
+ }
+ t1 = borrowGiant(cp->maxDigits);
+ t2 = borrowGiant(cp->maxDigits);
+ t3 = borrowGiant(cp->maxDigits);
+
+ if((cp->a->sign >= 0) || (cp->a->n[0] != 3)) { /* Path prior to Apr2001. */
+ gtog(z,t1); gsquare(t1); feemod(cp, t1);
+ gsquare(t1); feemod(cp, t1);
+ mulg(cp->a, t1); feemod(cp, t1); /* t1 := a z^4. */
+ gtog(x, t2); gsquare(t2); feemod(cp, t2);
+ smulg(3, t2); /* t2 := 3x^2. */
+ addg(t2, t1); feemod(cp, t1); /* t1 := slope m. */
+ } else { /* New optimization for a = -3 (post Apr 2001). */
+ gtog(z, t1); gsquare(t1); feemod(cp, t1); /* t1 := z^2. */
+ gtog(x, t2); subg(t1, t2); /* t2 := x-z^2. */
+ addg(x, t1); smulg(3, t1); /* t1 := 3(x+z^2). */
+ mulg(t2, t1); feemod(cp, t1); /* t1 := slope m. */
+ }
+ mulg(y, z); addg(z,z); feemod(cp, z); /* z := 2 y z. */
+ gtog(y, t2); gsquare(t2); feemod(cp, t2); /* t2 := y^2. */
+ gtog(t2, t3); gsquare(t3); feemod(cp, t3); /* t3 := y^4. */
+ gshiftleft(3, t3); /* t3 := 8 y^4. */
+ mulg(x, t2); gshiftleft(2, t2); feemod(cp, t2); /* t2 := 4xy^2. */
+ gtog(t1, x); gsquare(x); feemod(cp, x);
+ subg(t2, x); subg(t2, x); feemod(cp, x); /* x done. */
+ gtog(t1, y); subg(x, t2); mulg(t2, y); subg(t3, y);
+ feemod(cp, y);
+ returnGiant(t1);
+ returnGiant(t2);
+ returnGiant(t3);
+}
+
+void ellAddProj(pointProj pt0, pointProj pt1, curveParams *cp)
+/* pt0 := pt0 + pt1 on the curve. */
+{
+ giant x0 = pt0->x, y0 = pt0->y, z0 = pt0->z,
+ x1 = pt1->x, y1 = pt1->y, z1 = pt1->z;
+ giant t1;
+ giant t2;
+ giant t3;
+ giant t4;
+ giant t5;
+ giant t6;
+ giant t7;
+
+ if(isZero(z0)) {
+ gtog(x1,x0); gtog(y1,y0); gtog(z1,z0);
+ return;
+ }
+ if(isZero(z1)) return;
+
+ t1 = borrowGiant(cp->maxDigits);
+ t2 = borrowGiant(cp->maxDigits);
+ t3 = borrowGiant(cp->maxDigits);
+ t4 = borrowGiant(cp->maxDigits);
+ t5 = borrowGiant(cp->maxDigits);
+ t6 = borrowGiant(cp->maxDigits);
+ t7 = borrowGiant(cp->maxDigits);
+
+ gtog(x0, t1); gtog(y0,t2); gtog(z0, t3);
+ gtog(x1, t4); gtog(y1, t5);
+ if(!isone(z1)) {
+ gtog(z1, t6);
+ gtog(t6, t7); gsquare(t7); feemod(cp, t7);
+ mulg(t7, t1); feemod(cp, t1);
+ mulg(t6, t7); feemod(cp, t7);
+ mulg(t7, t2); feemod(cp, t2);
+ }
+ gtog(t3, t7); gsquare(t7); feemod(cp, t7);
+ mulg(t7, t4); feemod(cp, t4);
+ mulg(t3, t7); feemod(cp, t7);
+ mulg(t7, t5); feemod(cp, t5);
+ negg(t4); addg(t1, t4); feemod(cp, t4);
+ negg(t5); addg(t2, t5); feemod(cp, t5);
+ if(isZero(t4)) {
+ if(isZero(t5)) {
+ ellDoubleProj(pt0, cp);
+ } else {
+ int_to_giant(1, x0); int_to_giant(1, y0);
+ int_to_giant(0, z0);
+ }
+ goto out;
+ }
+ addg(t1, t1); subg(t4, t1); feemod(cp, t1);
+ addg(t2, t2); subg(t5, t2); feemod(cp, t2);
+ if(!isone(z1)) {
+ mulg(t6, t3); feemod(cp, t3);
+ }
+ mulg(t4, t3); feemod(cp, t3);
+ gtog(t4, t7); gsquare(t7); feemod(cp, t7);
+ mulg(t7, t4); feemod(cp, t4);
+ mulg(t1, t7); feemod(cp, t7);
+ gtog(t5, t1); gsquare(t1); feemod(cp, t1);
+ subg(t7, t1); feemod(cp, t1);
+ subg(t1, t7); subg(t1, t7); feemod(cp, t7);
+ mulg(t7, t5); feemod(cp, t5);
+ mulg(t2, t4); feemod(cp, t4);
+ gtog(t5, t2); subg(t4,t2); feemod(cp, t2);
+ if(t2->n[0] & 1) { /* Test if t2 is odd. */
+ addg(cp->basePrime, t2);
+ }
+ gshiftright(1, t2);
+ gtog(t1, x0); gtog(t2, y0); gtog(t3, z0);
+out:
+ returnGiant(t1);
+ returnGiant(t2);
+ returnGiant(t3);
+ returnGiant(t4);
+ returnGiant(t5);
+ returnGiant(t6);
+ returnGiant(t7);
+}
+
+
+void ellNegProj(pointProj pt, curveParams *cp)
+/* pt := -pt on the curve. */
+{
+ negg(pt->y); feemod(cp, pt->y);
+}
+
+void ellSubProj(pointProj pt0, pointProj pt1, curveParams *cp)
+/* pt0 := pt0 - pt1 on the curve. */
+{
+ ellNegProj(pt1, cp);
+ ellAddProj(pt0, pt1,cp);
+ ellNegProj(pt1, cp);
+}
+
+/*
+ * Simple projective multiply.
+ *
+ * pt := pt * k, result normalized.
+ */
+void ellMulProjSimple(pointProj pt0, giant k, curveParams *cp)
+{
+ pointProjStruct pt1; // local, giants borrowed
+
+ CKASSERT(isone(pt0->z));
+ CKASSERT(cp->curveType == FCT_Weierstrass);
+
+ /* ellMulProj assumes constant pt0, can't pass as src and dst */
+ pt1.x = borrowGiant(cp->maxDigits);
+ pt1.y = borrowGiant(cp->maxDigits);
+ pt1.z = borrowGiant(cp->maxDigits);
+ ellMulProj(pt0, &pt1, k, cp);
+ normalizeProj(&pt1, cp);
+ CKASSERT(isone(pt1.z));
+
+ ptopProj(&pt1, pt0);
+ returnGiant(pt1.x);
+ returnGiant(pt1.y);
+ returnGiant(pt1.z);
+}
+
+void ellMulProj(pointProj pt0, pointProj pt1, giant k, curveParams *cp)
+/* General elliptic multiplication;
+ pt1 := k*pt0 on the curve,
+ with k an arbitrary integer.
+ */
+{
+ giant x = pt0->x, y = pt0->y, z = pt0->z,
+ xx = pt1->x, yy = pt1->y, zz = pt1->z;
+ int ksign, hlen, klen, b, hb, kb;
+ giant t0;
+
+ CKASSERT(cp->curveType == FCT_Weierstrass);
+ if(isZero(k)) {
+ int_to_giant(1, xx);
+ int_to_giant(1, yy);
+ int_to_giant(0, zz);
+ return;
+ }
+ t0 = borrowGiant(cp->maxDigits);
+ ksign = k->sign;
+ if(ksign < 0) negg(k);
+ gtog(x,xx); gtog(y,yy); gtog(z,zz);
+ gtog(k, t0); addg(t0, t0); addg(k, t0); /* t0 := 3k. */
+ hlen = bitlen(t0);
+ klen = bitlen(k);
+ for(b = hlen-2; b > 0; b--) {
+ ellDoubleProj(pt1,cp);
+ hb = bitval(t0, b);
+ if(b < klen) kb = bitval(k, b); else kb = 0;
+ if((hb != 0) && (kb == 0))
+ ellAddProj(pt1, pt0, cp);
+ else if((hb == 0) && (kb !=0))
+ ellSubProj(pt1, pt0, cp);
+ }
+ if(ksign < 0) {
+ ellNegProj(pt1, cp);
+ k->sign = -k->sign;
+ }
+ returnGiant(t0);
+}
+
+void normalizeProj(pointProj pt, curveParams *cp)
+/* Obtain actual x,y coords via normalization:
+ {x,y,z} := {x/z^2, y/z^3, 1}.
+ */
+
+{ giant x = pt->x, y = pt->y, z = pt->z;
+ giant t1;
+
+ CKASSERT(cp->curveType == FCT_Weierstrass);
+ if(isZero(z)) {
+ int_to_giant(1,x); int_to_giant(1,y);
+ return;
+ }
+ t1 = borrowGiant(cp->maxDigits);
+ binvg_cp(cp, z); // was binvaux(p, z);
+ gtog(z, t1);
+ gsquare(z); feemod(cp, z);
+ mulg(z, x); feemod(cp, x);
+ mulg(t1, z); mulg(z, y); feemod(cp, y);
+ int_to_giant(1, z);
+ returnGiant(t1);
+}
+
+static int
+jacobi_symbol(giant a, curveParams *cp)
+/* Standard Jacobi symbol (a/cp->basePrime).
+ basePrime must be odd, positive. */
+{
+ int t = 1, u;
+ giant t5 = borrowGiant(cp->maxDigits);
+ giant t6 = borrowGiant(cp->maxDigits);
+ giant t7 = borrowGiant(cp->maxDigits);
+ int rtn;
+
+ gtog(a, t5); feemod(cp, t5);
+ gtog(cp->basePrime, t6);
+ while(!isZero(t5)) {
+ u = (t6->n[0]) & 7;
+ while((t5->n[0] & 1) == 0) {
+ gshiftright(1, t5);
+ if((u==3) || (u==5)) t = -t;
+ }
+ gtog(t5, t7); gtog(t6, t5); gtog(t7, t6);
+ u = (t6->n[0]) & 3;
+ if(((t5->n[0] & 3) == 3) && ((u & 3) == 3)) t = -t;
+ modg(t6, t5);
+ }
+ if(isone(t6)) {
+ rtn = t;
+ }
+ else {
+ rtn = 0;
+ }
+ returnGiant(t5);
+ returnGiant(t6);
+ returnGiant(t7);
+
+ return rtn;
+}
+
+static void
+powFp2(giant a, giant b, giant w2, giant n, curveParams *cp)
+/* Perform powering in the field F_p^2:
+ a + b w := (a + b w)^n (mod p), where parameter w2 is a quadratic
+ nonresidue (formally equal to w^2).
+ */
+{
+ int j;
+ giant t6;
+ giant t7;
+ giant t8;
+ giant t9;
+
+ if(isZero(n)) {
+ int_to_giant(1,a);
+ int_to_giant(0,b);
+ return;
+ }
+ t6 = borrowGiant(cp->maxDigits);
+ t7 = borrowGiant(cp->maxDigits);
+ t8 = borrowGiant(cp->maxDigits);
+ t9 = borrowGiant(cp->maxDigits);
+ gtog(a, t8); gtog(b, t9);
+ for(j = bitlen(n)-2; j >= 0; j--) {
+ gtog(b, t6);
+ mulg(a, b); addg(b,b); feemod(cp, b); /* b := 2 a b. */
+ gsquare(t6); feemod(cp, t6);
+ mulg(w2, t6); feemod(cp, t6);
+ gsquare(a); addg(t6, a); feemod(cp, a);
+ /* a := a^2 + b^2 w2. */
+ if(bitval(n, j)) {
+ gtog(b, t6); mulg(t8, b); feemod(cp, b);
+ gtog(a, t7); mulg(t9, a); addg(a, b); feemod(cp, b);
+ mulg(t9, t6); feemod(cp, t6);
+ mulg(w2, t6); feemod(cp, t6);
+ mulg(t8, a); addg(t6, a); feemod(cp, a);
+ }
+ }
+ returnGiant(t6);
+ returnGiant(t7);
+ returnGiant(t8);
+ returnGiant(t9);
+ return;
+}
+
+static void
+powermodg(
+ giant x,
+ giant n,
+ curveParams *cp
+)
+/* x becomes x^n (mod basePrime). */
+{
+ int len, pos;
+ giant scratch2 = borrowGiant(cp->maxDigits);
+
+ gtog(x, scratch2);
+ int_to_giant(1, x);
+ len = bitlen(n);
+ pos = 0;
+ while (1)
+ {
+ if (bitval(n, pos++))
+ {
+ mulg(scratch2, x);
+ feemod(cp, x);
+ }
+ if (pos>=len)
+ break;
+ gsquare(scratch2);
+ feemod(cp, scratch2);
+ }
+ returnGiant(scratch2);
+}
+
+static int sqrtmod(giant x, curveParams *cp)
+/* If Sqrt[x] (mod p) exists, function returns 1, else 0.
+ In either case x is modified, but if 1 is returned,
+ x:= Sqrt[x] (mod p).
+ */
+{
+ int rtn;
+ giant t0 = borrowGiant(cp->maxDigits);
+ giant t1 = borrowGiant(cp->maxDigits);
+ giant t2 = borrowGiant(cp->maxDigits);
+ giant t3 = borrowGiant(cp->maxDigits);
+ giant t4 = borrowGiant(cp->maxDigits);
+
+ giant p = cp->basePrime;
+
+ feemod(cp, x); /* Justify the argument. */
+ gtog(x, t0); /* Store x for eventual validity check on square root. */
+ if((p->n[0] & 3) == 3) { /* The case p = 3 (mod 4). */
+ gtog(p, t1);
+ iaddg(1, t1); gshiftright(2, t1);
+ powermodg(x, t1, cp);
+ goto resolve;
+ }
+ /* Next, handle case p = 5 (mod 8). */
+ if((p->n[0] & 7) == 5) {
+ gtog(p, t1); int_to_giant(1, t2);
+ subg(t2, t1); gshiftright(2, t1);
+ gtog(x, t2);
+ powermodg(t2, t1, cp); /* t2 := x^((p-1)/4) % p. */
+ iaddg(1, t1);
+ gshiftright(1, t1); /* t1 := (p+3)/8. */
+ if(isone(t2)) {
+ powermodg(x, t1, cp); /* x^((p+3)/8) is root. */
+ goto resolve;
+ } else {
+ int_to_giant(1, t2); subg(t2, t1);
+ /* t1 := (p-5)/8. */
+ gshiftleft(2,x);
+ powermodg(x, t1, cp);
+ mulg(t0, x); addg(x, x); feemod(cp, x);
+ /* 2x (4x)^((p-5)/8. */
+ goto resolve;
+ }
+ }
+
+ /* Next, handle tougher case: p = 1 (mod 8). */
+ int_to_giant(2, t1);
+ while(1) { /* Find appropriate nonresidue. */
+ gtog(t1, t2);
+ gsquare(t2); subg(x, t2); feemod(cp, t2);
+ if(jacobi_symbol(t2, cp) == -1) break;
+ iaddg(1, t1);
+ } /* t2 is now w^2 in F_p^2. */
+ int_to_giant(1, t3);
+ gtog(p, t4); iaddg(1, t4); gshiftright(1, t4);
+ powFp2(t1, t3, t2, t4, cp);
+ gtog(t1, x);
+
+resolve:
+ gtog(x,t1); gsquare(t1); feemod(cp, t1);
+ if(gcompg(t0, t1) == 0) {
+ rtn = 1; /* Success. */
+ }
+ else {
+ rtn = 0; /* no square root */
+ }
+ returnGiant(t0);
+ returnGiant(t1);
+ returnGiant(t2);
+ returnGiant(t3);
+ returnGiant(t4);
+ return rtn;
+}
+
+
+void findPointProj(pointProj pt, giant seed, curveParams *cp)
+/* Starting with seed, finds a random (projective) point {x,y,1} on curve.
+ */
+{
+ giant x = pt->x, y = pt->y, z = pt->z;
+
+ CKASSERT(cp->curveType == FCT_Weierstrass);
+ feemod(cp, seed);
+ while(1) {
+ gtog(seed, x);
+ gsquare(x); feemod(cp, x); // x := seed^2
+ addg(cp->a, x); // x := seed^2 + a
+ mulg(seed,x); // x := seed^3 + a*seed
+ addg(cp->b, x);
+ feemod(cp, x); // x := seed^3 + a seed + b.
+ /* test cubic form for having root. */
+ if(sqrtmod(x, cp)) break;
+ iaddg(1, seed);
+ }
+ gtog(x, y);
+ gtog(seed,x);
+ int_to_giant(1, z);
+}
+
+#endif /* CRYPTKIT_ELL_PROJ_ENABLE */
projects / apple / security.git / blobdiff