-/**************************************************************
- *
- * ellproj.c
- *
- Fast algorithms for fundamental elliptic curve arithmetic,
- projective format. Such algorithms apply in domains such as:
- -- factoring
- -- primality studies (e.g. rigorous primality proofs)
- -- elliptic curve cryptography (ECC)
-
- 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 normalize_proj() 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
-
- ell_mul_proj()
-
- 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 ell_mul_proj(), then afterwards
- calls normalize_proj(),
-
- 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
-
- Crandall R and Pomerance C 1998, "Prime numbers: a computational
- perspective," Springer-Verlag, manuscript
-
- Solinas J 1998, IEEE P1363 Annex A (draft standard)
-
- LEGAL AND PATENT NOTICE
-
- This and related PSI library source code is intended solely for
- educational and research applications, and should not be used
- for commercial purposes without explicit permission from PSI
- (not to mention proper clearance of legal restrictions beyond
- the purview of PSI).
- The code herein will not perform cryptography per se,
- although the number-theoretical algorithms herein -- all of which
- are in the public domain -- can be used in principle to effect
- what is known as elliptic curve cryptography (ECC). Note that
- there are strict constraints on how cryptography may be used,
- especially in regard to exportability.
- Therefore one should avoid any casual distribution of actual
- cryptographic software. Along similar lines, because of various
- patents, proprietary to Apple Computer, Inc., and perhaps to other
- organizations, one should not tacitly assume that an ECC scheme is
- unconstrained. For example,the commercial use of certain fields
- F_p^k (i.e., fixation of certain primes p) is covered in Apple
- patents.
-
- * Updates:
- * 3 Apr 98 REC Creation
- *
- * c. 1998 Perfectly Scientific, Inc.
- * All Rights Reserved.
- *
- *
- *************************************************************/
-
-/* include files */
-
-#include <stdio.h>
-#include <math.h>
-#include <stdlib.h>
-#include <time.h>
-#ifdef _WIN32
-
-#include <process.h>
-
-#endif
-
-#include <string.h>
-#include "giants.h"
-#include "ellproj.h"
-#include "tools.h"
-
-/* global variables */
-
-static giant t0 = NULL, t1 = NULL, t2 = NULL, t3 = NULL, t4 = NULL,
- t5 = NULL, t6 = NULL, t7 = NULL;
-
-/**************************************************************
- *
- * Maintenance functions
- *
- **************************************************************/
-
-point_proj
-new_point_proj(int shorts)
-{
- point_proj pt;
-
- if(t0 == NULL) init_ell_proj(shorts);
- pt = (point_proj) malloc(sizeof(point_struct_proj));
- pt->x = newgiant(shorts);
- pt->y = newgiant(shorts);
- pt->z = newgiant(shorts);
- return(pt);
-}
-
-void
-free_point_proj(point_proj pt)
-{
- free(pt->x); free(pt->y); free(pt->z);
- free(pt);
-}
-
-void
-ptop_proj(point_proj pt1, point_proj pt2)
-{
- gtog(pt1->x, pt2->x);
- gtog(pt1->y, pt2->y);
- gtog(pt1->z, pt2->z);
-}
-
-void
-init_ell_proj(int shorts)
-/* Called by new_point_proj(), to set up giant registers. */
-{
- t0 = newgiant(shorts);
- t1 = newgiant(shorts);
- t2 = newgiant(shorts);
- t3 = newgiant(shorts);
- t4 = newgiant(shorts);
- t5 = newgiant(shorts);
- t6 = newgiant(shorts);
- t7 = newgiant(shorts);
-}
-
-
-/**************************************************************
- *
- * 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 normalize_proj() performs the inverse conversion to get
- the true (x,y) pair.
- */
-
-void
-ell_double_proj(point_proj pt, giant a, giant p)
-/* pt := 2 pt on the curve. */
-{
- giant x = pt->x, y = pt->y, z = pt->z;
-
- if(isZero(y) || isZero(z)) {
- itog(1,x); itog(1,y); itog(0,z);
- return;
- }
- gtog(z,t1); squareg(t1); modg(p, t1);
- squareg(t1); modg(p, t1);
- mulg(a, t1); modg(p, t1); /* t1 := a z^4. */
- gtog(x, t2); squareg(t2); smulg(3, t2); modg(p, t2); /* t2 := 3x^2. */
- addg(t2, t1); modg(p, t1); /* t1 := slope m. */
- mulg(y, z); addg(z,z); modg(p, z); /* z := 2 y z. */
- gtog(y, t2); squareg(t2); modg(p, t2); /* t2 := y^2. */
- gtog(t2, t3); squareg(t3); modg(p, t3); /* t3 := y^4. */
- gshiftleft(3, t3); /* t3 := 8 y^4. */
- mulg(x, t2); gshiftleft(2, t2); modg(p, t2); /* t2 := 4xy^2. */
- gtog(t1, x); squareg(x); modg(p, x);
- subg(t2, x); subg(t2, x); modg(p, x); /* x done. */
- gtog(t1, y); subg(x, t2); mulg(t2, y); subg(t3, y);
- modg(p, y);
-}
-/*
-elldouble[pt_] := Block[{x,y,z,m,y2,s},
- x = pt[[1]]; y = pt[[2]]; z = pt[[3]];
- If[(y==0) || (z==0), Return[{1,1,0}]];
- m = Mod[3 x^2 + a Mod[Mod[z^2,p]^2,p],p];
- z = Mod[2 y z, p];
- y2 = Mod[y^2,p];
- s = Mod[4 x y2,p];
- x = Mod[m^2 - 2s,p];
- y = Mod[m(s - x) - 8 y2^2,p];
- Return[{x,y,z}];
-];
-*/
-
-void
-ell_add_proj(point_proj pt0, point_proj pt1, giant a, giant p)
-/* 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;
-
- if(isZero(z0)) {
- gtog(x1,x0); gtog(y1,y0); gtog(z1,z0);
- return;
- }
- if(isZero(z1)) return;
- gtog(x0, t1); gtog(y0,t2); gtog(z0, t3);
- gtog(x1, t4); gtog(y1, t5);
- if(!isone(z1)) {
- gtog(z1, t6);
- gtog(t6, t7); squareg(t7); modg(p, t7);
- mulg(t7, t1); modg(p, t1);
- mulg(t6, t7); modg(p, t7);
- mulg(t7, t2); modg(p, t2);
- }
- gtog(t3, t7); squareg(t7); modg(p, t7);
- mulg(t7, t4); modg(p, t4);
- mulg(t3, t7); modg(p, t7);
- mulg(t7, t5); modg(p, t5);
- negg(t4); addg(t1, t4); modg(p, t4);
- negg(t5); addg(t2, t5); modg(p, t5);
- if(isZero(t4)) {
- if(isZero(t5)) {
- ell_double_proj(pt0, a, p);
- } else {
- itog(1, x0); itog(1, y0); itog(0, z0);
- }
- return;
- }
- addg(t1, t1); subg(t4, t1); modg(p, t1);
- addg(t2, t2); subg(t5, t2); modg(p, t2);
- if(!isone(z1)) {
- mulg(t6, t3); modg(p, t3);
- }
- mulg(t4, t3); modg(p, t3);
- gtog(t4, t7); squareg(t7); modg(p, t7);
- mulg(t7, t4); modg(p, t4);
- mulg(t1, t7); modg(p, t7);
- gtog(t5, t1); squareg(t1); modg(p, t1);
- subg(t7, t1); modg(p, t1);
- subg(t1, t7); subg(t1, t7); modg(p, t7);
- mulg(t7, t5); modg(p, t5);
- mulg(t2, t4); modg(p, t4);
- gtog(t5, t2); subg(t4,t2); modg(p, t2);
- if(t2->n[0] & 1) { /* Test if t2 is odd. */
- addg(p, t2);
- }
- gshiftright(1, t2);
- gtog(t1, x0); gtog(t2, y0); gtog(t3, z0);
-}
-
-/*
-elladd[pt0_, pt1_] := Block[
- {x0,y0,z0,x1,y1,z1,
- t1,t2,t3,t4,t5,t6,t7},
- x0 = pt0[[1]]; y0 = pt0[[2]]; z0 = pt0[[3]];
- x1 = pt1[[1]]; y1 = pt1[[2]]; z1 = pt1[[3]];
- If[z0 == 0, Return[pt1]];
- If[z1 == 0, Return[pt0]];
-
- t1 = x0;
- t2 = y0;
- t3 = z0;
- t4 = x1;
- t5 = y1;
- If[(z1 != 1),
- t6 = z1;
- t7 = Mod[t6^2, p];
- t1 = Mod[t1 t7, p];
- t7 = Mod[t6 t7, p];
- t2 = Mod[t2 t7, p];
- ];
- t7 = Mod[t3^2, p];
- t4 = Mod[t4 t7, p];
- t7 = Mod[t3 t7, p];
- t5 = Mod[t5 t7, p];
- t4 = Mod[t1-t4, p];
- t5 = Mod[t2 - t5, p];
- If[t4 == 0, If[t5 == 0,
- Return[elldouble[pt0]],
- Return[{1,1,0}]
- ]
- ];
- t1 = Mod[2t1 - t4,p];
- t2 = Mod[2t2 - t5, p];
- If[z1 != 1, t3 = Mod[t3 t6, p]];
- t3 = Mod[t3 t4, p];
- t7 = Mod[t4^2, p];
- t4 = Mod[t4 t7, p];
- t7 = Mod[t1 t7, p];
- t1 = Mod[t5^2, p];
- t1 = Mod[t1-t7, p];
- t7 = Mod[t7 - 2t1, p];
- t5 = Mod[t5 t7, p];
- t4 = Mod[t2 t4, p];
- t2 = Mod[t5-t4, p];
- If[EvenQ[t2], t2 = t2/2, t2 = (p+t2)/2];
- Return[{t1, t2, t3}];
-];
-*/
-
-void
-ell_neg_proj(point_proj pt, giant p)
-/* pt := -pt on the curve. */
-{
- negg(pt->y); modg(p, pt->y);
-}
-
-void
-ell_sub_proj(point_proj pt0, point_proj pt1, giant a, giant p)
-/* pt0 := pt0 - pt1 on the curve. */
-{
- ell_neg_proj(pt1, p);
- ell_add_proj(pt0, pt1,a,p);
- ell_neg_proj(pt1,p);
-}
-
-void
-ell_mul_proj(point_proj pt0, point_proj pt1, giant k, giant a, giant p)
-/* 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;
-
- if(isZero(k)) {
- itog(1, xx);
- itog(1, yy);
- itog(0, zz);
- return;
- }
- 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--) {
- ell_double_proj(pt1,a,p);
- hb = bitval(t0, b);
- if(b < klen) kb = bitval(k, b); else kb = 0;
- if((hb != 0) && (kb == 0))
- ell_add_proj(pt1, pt0, a, p);
- else if((hb == 0) && (kb !=0))
- ell_sub_proj(pt1, pt0, a, p);
- }
- if(ksign < 0) {
- ell_neg_proj(pt1, p);
- k->sign = -k->sign;
- }
-}
-
-/*
-elliptic[pt_, k_] := Block[{pt2, hh, kk, hb, kb, lenh, lenk},
- If[k==0, Return[{1,1,0}]];
- hh = Reverse[bitList[3k]];
- kk = Reverse[bitList[k]];
- pt2 = pt;
- lenh = Length[hh];
- lenk = Length[kk];
- Do[
- pt2 = elldouble[pt2];
- hb = hh[[b]];
- If[b <= lenk, kb = kk[[b]], kb = 0];
- If[{hb,kb} == {1,0},
- pt2 = elladd[pt2, pt],
- If[{hb, kb} == {0,1},
- pt2 = ellsub[pt2, pt]]
- ]
- ,{b, lenh-1, 2,-1}
- ];
- Return[pt2];
-];
-*/
-
-void
-normalize_proj(point_proj pt, giant p)
-/* 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;
-
- if(isZero(z)) {
- itog(1,x); itog(1,y);
- return;
- }
- binvaux(p, z); gtog(z, t1);
- squareg(z); modg(p, z);
- mulg(z, x); modg(p, x);
- mulg(t1, z); mulg(z, y); modg(p, y);
- itog(1, z);
-}
-
-/*
-normalize[pt_] := Block[{z,z2,z3},
- If[pt[[3]] == 0, Return[pt]];
- z = ellinv[pt[[3]]];
- z2 = Mod[z^2,p];
- z3 = Mod[z z2,p];
- Return[{Mod[pt[[1]] z2, p], Mod[pt[[2]] z3, p], 1}];
- ];
-*/
-
-
-void
-find_point_proj(point_proj pt, giant seed, giant a, giant b, giant p)
-/* Starting with seed, finds a random (projective) point {x,y,1} on curve.
- */
-{ giant x = pt->x, y = pt->y, z = pt->z;
-
- modg(p, seed);
- while(1) {
- gtog(seed, x);
- squareg(x); modg(p, x);
- addg(a, x);
- mulg(seed,x); addg(b, x);
- modg(p, x); /* x := seed^3 + a seed + b. */
- if(sqrtmod(p, x)) break; /* Test if cubic form has root. */
- iaddg(1, seed);
- }
- gtog(x, y);
- gtog(seed,x);
- itog(1, z);
-}
projects / apple / security.git / blobdiff