#include "ckconfig.h"
#include "ellipticProj.h"
#include "falloc.h"
#include "curveParams.h"
#include "elliptic.h"
#include "feeDebug.h"
#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);
}
void ellDoubleProj(pointProj pt, curveParams *cp)
{
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)) {
gtog(z,t1); gsquare(t1); feemod(cp, t1);
gsquare(t1); feemod(cp, t1);
mulg(cp->a, t1); feemod(cp, t1);
gtog(x, t2); gsquare(t2); feemod(cp, t2);
smulg(3, t2);
addg(t2, t1); feemod(cp, t1);
} else {
gtog(z, t1); gsquare(t1); feemod(cp, t1);
gtog(x, t2); subg(t1, t2);
addg(x, t1); smulg(3, t1);
mulg(t2, t1); feemod(cp, t1);
}
mulg(y, z); addg(z,z); feemod(cp, z);
gtog(y, t2); gsquare(t2); feemod(cp, t2);
gtog(t2, t3); gsquare(t3); feemod(cp, t3);
gshiftleft(3, t3);
mulg(x, t2); gshiftleft(2, t2); feemod(cp, t2);
gtog(t1, x); gsquare(x); feemod(cp, x);
subg(t2, x); subg(t2, x); feemod(cp, x);
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)
{
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) {
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)
{
negg(pt->y); feemod(cp, pt->y);
}
void ellSubProj(pointProj pt0, pointProj pt1, curveParams *cp)
{
ellNegProj(pt1, cp);
ellAddProj(pt0, pt1,cp);
ellNegProj(pt1, cp);
}
void ellMulProjSimple(pointProj pt0, giant k, curveParams *cp)
{
pointProjStruct pt1;
CKASSERT(isone(pt0->z));
CKASSERT(cp->curveType == FCT_Weierstrass);
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)
{
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);
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)
{ 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); 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)
{
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)
{
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);
gsquare(t6); feemod(cp, t6);
mulg(w2, t6); feemod(cp, t6);
gsquare(a); addg(t6, a); feemod(cp, a);
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
)
{
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)
{
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);
gtog(x, t0);
if((p->n[0] & 3) == 3) {
gtog(p, t1);
iaddg(1, t1); gshiftright(2, t1);
powermodg(x, t1, cp);
goto resolve;
}
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);
iaddg(1, t1);
gshiftright(1, t1);
if(isone(t2)) {
powermodg(x, t1, cp);
goto resolve;
} else {
int_to_giant(1, t2); subg(t2, t1);
gshiftleft(2,x);
powermodg(x, t1, cp);
mulg(t0, x); addg(x, x); feemod(cp, x);
goto resolve;
}
}
int_to_giant(2, t1);
while(1) {
gtog(t1, t2);
gsquare(t2); subg(x, t2); feemod(cp, t2);
if(jacobi_symbol(t2, cp) == -1) break;
iaddg(1, t1);
}
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;
}
else {
rtn = 0;
}
returnGiant(t0);
returnGiant(t1);
returnGiant(t2);
returnGiant(t3);
returnGiant(t4);
return rtn;
}
void findPointProj(pointProj pt, giant seed, curveParams *cp)
{
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); addg(cp->a, x); mulg(seed,x); addg(cp->b, x);
feemod(cp, x);
if(sqrtmod(x, cp)) break;
iaddg(1, seed);
}
gtog(x, y);
gtog(seed,x);
int_to_giant(1, z);
}