#include "ckconfig.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "platform.h"
#include "giantIntegers.h"
#include "elliptic.h"
#include "ellipticProj.h"
#include "ckutilities.h"
#include "curveParams.h"
#include "feeDebug.h"
#include "ellipticMeasure.h"
#include "falloc.h"
#include "giantPortCommon.h"
#if FEE_PROFILE
unsigned numerDoubleTime;
unsigned numerPlusTime;
unsigned numerTimesTime;
unsigned denomDoubleTime;
unsigned denomTimesTime;
unsigned ellipticTime;
unsigned sigCompTime;
unsigned powerModTime;
unsigned ellAddTime;
unsigned whichCurveTime;
unsigned modgTime;
unsigned mulgTime;
unsigned binvauxTime;
unsigned gsquareTime;
unsigned numMulg;
unsigned numFeemod;
unsigned numGsquare;
unsigned numBorrows;
void clearProfile()
{
numerDoubleTime = 0;
numerPlusTime = 0;
numerTimesTime = 0;
denomDoubleTime = 0;
denomTimesTime = 0;
ellipticTime = 0;
sigCompTime = 0;
powerModTime = 0;
ellAddTime = 0;
whichCurveTime = 0;
modgTime = 0;
mulgTime = 0;
binvauxTime = 0;
gsquareTime = 0;
numMulg = 0;
numFeemod = 0;
numGsquare = 0;
numBorrows = 0;
}
#endif // FEE_PROFILE
#if ELL_PROFILE
unsigned ellOddTime;
unsigned ellEvenTime;
unsigned numEllOdds;
unsigned numEllEvens;
void clearEllProfile()
{
ellOddTime = 0;
ellEvenTime = 0;
numEllOdds = 0;
numEllEvens = 0;
}
#endif
#if ELLIPTIC_MEASURE
int doEllMeasure; int bitsInN;
int numFeeMods;
int numMulgs;
void dumpEll()
{
printf("\nbitlen(n) : %d\n", bitsInN);
printf("feemods : %d\n", numFeeMods);
printf("mulgs : %d\n", numMulgs);
}
#endif // ELLIPTIC_MEASURE
static void make_base(curveParams *par, giant result); static int keys_inconsistent(key pub1, key pub2);
static void ell_even(giant x1, giant z1, giant x2, giant z2, curveParams *par);
static void ell_odd(giant x1, giant z1, giant x2, giant z2, giant xxor,
giant zor, curveParams *par);
static void numer_double(giant x, giant z, giant res, curveParams *par);
static void numer_plus(giant x1, giant x2, giant res, curveParams *par);
static void denom_double(giant x, giant z, giant res, curveParams *par);
static void denom_times(giant x1, giant z1, giant x2, giant z2, giant res,
curveParams *par);
static void numer_times(giant x1, giant z1, giant x2, giant z2, giant res,
curveParams *par);
static void feepowermodg(curveParams *par, giant x, giant n);
static void curveOrderJustifyWithRecip(giant g, giant curveOrder, giant recip);
int which_curve(giant x, curveParams *par)
{
giant t1;
giant t2;
giant t3;
int result;
PROF_START;
t1 = borrowGiant(par->maxDigits);
t2 = borrowGiant(par->maxDigits);
t3 = borrowGiant(par->maxDigits);
gtog(x, t2); addg(par->c, t2);
mulg(x, t2); addg(par->a, t2);
feemod(par, t2);
mulg(x, t2); addg(par->b, t2);
feemod(par, t2);
gtog(t2, t1);
make_base(par, t3); iaddg(1, t3); gshiftright(1, t3);
feepowermodg(par, t1, t3);
if(gcompg(t1, t2) == 0)
result = CURVE_PLUS;
else
result = CURVE_MINUS;
returnGiant(t1);
returnGiant(t2);
returnGiant(t3);
PROF_END(whichCurveTime);
return result;
}
key new_public(curveParams *cp, int twist) {
key k;
k = (key) fmalloc(sizeof(keystruct));
k->cp = cp;
k->twist = twist;
k->x = newGiant(cp->maxDigits);
if((twist == CURVE_PLUS) && (cp->curveType == FCT_Weierstrass)) {
k->y = newGiant(cp->maxDigits);
}
else {
k->y = newGiant(1);
}
return(k);
}
key new_public_with_key(key old_key, curveParams *cp)
{
key result;
result = new_public(cp, old_key->twist);
CKASSERT((old_key->x != NULL) && (old_key->y != NULL));
CKASSERT((result->x != NULL) && (result->y != NULL));
gtog(old_key->x, result->x);
gtog(old_key->y, result->y);
return result;
}
void free_key(key pub) {
if(!pub) {
return;
}
if (pub->x) {
freeGiant(pub->x);
}
if (pub->y) {
freeGiant(pub->y);
}
ffree(pub);
}
void set_priv_key_giant(key k, giant privGiant)
{
curveParams *cp = k->cp;
if((k->twist == CURVE_PLUS) && (cp->curveType == FCT_Weierstrass)) {
pointProj pt1 = newPointProj(cp->maxDigits);
CKASSERT((cp->y1Plus != NULL) && (!isZero(cp->y1Plus)));
CKASSERT(k->y != NULL);
gtog(cp->x1Plus, pt1->x);
gtog(cp->y1Plus, pt1->y);
int_to_giant(1, pt1->z);
ellMulProjSimple(pt1, privGiant, cp);
gtog(pt1->x, k->x);
gtog(pt1->y, k->y);
freePointProj(pt1); }
else {
if(k->twist == CURVE_PLUS) {
gtog(cp->x1Plus, k->x);
}
else {
gtog(cp->x1Minus, k->x);
}
elliptic_simple(k->x, privGiant, k->cp);
}
}
int key_equal(key one, key two) {
if (keys_inconsistent(one, two)) return 0;
return !gcompg(one->x, two->x);
}
static void make_base(curveParams *par, giant result)
{
gtog(par->basePrime, result);
}
void make_base_prim(curveParams *cp)
{
giant tmp = borrowGiant(cp->maxDigits);
CKASSERT(cp->primeType != FPT_General);
int_to_giant(1, cp->basePrime);
gshiftleft((int)cp->q, cp->basePrime);
int_to_giant(cp->k, tmp);
subg(tmp, cp->basePrime);
returnGiant(tmp);
}
static int sequalg(int n, giant g) {
if((g->sign == 1) && (g->n[0] == n)) return(1);
return(0);
}
void elliptic_simple(giant x, giant n, curveParams *par) {
giant ztmp = borrowGiant(par->maxDigits);
giant cur_n = borrowGiant(par->maxDigits);
START_ELL_MEASURE(n);
int_to_giant(1, ztmp);
elliptic(x, ztmp, n, par);
binvg_cp(par, ztmp);
mulg(ztmp, x);
feemod(par, x);
END_ELL_MEASURE;
returnGiant(cur_n);
returnGiant(ztmp);
}
void elliptic(giant xx, giant zz, giant k, curveParams *par) {
int len = bitlen(k);
int pos = len - 2;
giant xs;
giant zs;
giant xorg;
giant zorg;
PROF_START;
if(sequalg(1,k)) return;
if(sequalg(2,k)) {
ell_even(xx, zz, xx, zz, par);
goto out;
}
zs = borrowGiant(par->maxDigits);
xs = borrowGiant(par->maxDigits);
zorg = borrowGiant(par->maxDigits);
xorg = borrowGiant(par->maxDigits);
gtog(xx, xorg); gtog(zz, zorg);
ell_even(xx, zz, xs, zs, par);
do {
if(bitval(k, pos--)) {
ell_odd(xs, zs, xx, zz, xorg, zorg, par);
ell_even(xs, zs, xs, zs, par);
} else {
ell_odd(xx, zz, xs, zs, xorg, zorg, par);
ell_even(xx, zz, xx, zz, par);
}
} while (pos >= 0); returnGiant(xs);
returnGiant(zs);
returnGiant(xorg);
returnGiant(zorg);
out:
PROF_END(ellipticTime);
}
void elliptic_add(giant x1, giant x2, giant x3, curveParams *par, int s) {
giant cur_n;
giant t1;
giant t2;
giant t3;
giant t4;
giant t5;
PROF_START;
cur_n = borrowGiant(par->maxDigits);
t1 = borrowGiant(par->maxDigits);
t2 = borrowGiant(par->maxDigits);
t3 = borrowGiant(par->maxDigits);
t4 = borrowGiant(par->maxDigits);
t5 = borrowGiant(par->maxDigits);
if(gcompg(x1, x2)==0) {
int_to_giant(1, t1);
numer_double(x1, t1, x3, par);
denom_double(x1, t1, t2, par);
binvg_cp(par, t2);
mulg(t2, x3); feemod(par, x3);
goto out;
}
numer_plus(x1, x2, t1, par);
int_to_giant(1, t3);
numer_times(x1, t3, x2, t3, t2, par);
int_to_giant(1, t4); int_to_giant(1, t5);
denom_times(x1, t4, x2, t5, t3, par);
binvg_cp(par, t3);
mulg(t3, t1); feemod(par, t1);
mulg(t3, t2); feemod(par, t2);
gtog(t1, t4); gsquare(t4); feemod(par, t4);
subg(t2, t4);
make_base(par, cur_n); iaddg(1, cur_n); gshiftright(2, cur_n);
feepowermodg(par, t4, cur_n);
gtog(t1, x3);
if(s != SIGN_PLUS) negg(t4);
addg(t4, x3);
feemod(par, x3);
out:
returnGiant(cur_n);
returnGiant(t1);
returnGiant(t2);
returnGiant(t3);
returnGiant(t4);
returnGiant(t5);
PROF_END(ellAddTime);
}
giant make_pad(giant privGiant, key publicKey) {
curveParams *par = publicKey->cp;
giant result = newGiant(par->maxDigits);
gtog(publicKey->x, result);
elliptic_simple(result, privGiant, par);
return result;
}
static void ell_even(giant x1, giant z1, giant x2, giant z2, curveParams *par) {
giant t1;
giant t2;
giant t3;
EPROF_START;
t1 = borrowGiant(par->maxDigits);
t2 = borrowGiant(par->maxDigits);
t3 = borrowGiant(par->maxDigits);
if(par->curveType == FCT_Montgomery) {
gtog(x1, t1); gsquare(t1); feemod(par, t1);
gtog(z1, t2); gsquare(t2); feemod(par, t2);
gtog(x1, t3); mulg(z1, t3); feemod(par, t3);
gtog(t3, z2); mulg(par->c, z2); feemod(par, z2);
addg(t1, z2); addg(t2, z2); mulg(t3, z2); gshiftleft(2, z2);
feemod(par, z2);
gtog(t1, x2); subg(t2, x2); gsquare(x2); feemod(par, x2);
}
else if((par->curveType == FCT_Weierstrass) && isZero(par->a)) {
gtog(x1, t1);
gsquare(t1); feemod(par, t1);
mulg(x1, t1); feemod(par, t1);
gtog(z1, t2);
gsquare(t2); feemod(par, t2);
mulg(z1, t2); feemod(par, t2);
mulg(par->b, t2); feemod(par, t2);
gtog(t1, t3); addg(t2, t3);
mulg(z1, t3); feemod(par, t3);
gshiftleft(2, t3); feemod(par, t3);
gshiftleft(3, t2);
subg(t2, t1);
mulg(x1, t1); feemod(par, t1);
gtog(t3, z2);
gtog(t1, x2);
}
else {
numer_double(x1, z1, t1, par);
denom_double(x1, z1, t2, par);
gtog(t1, x2); gtog(t2, z2);
}
returnGiant(t1);
returnGiant(t2);
returnGiant(t3);
EPROF_END(ellEvenTime);
EPROF_INCR(numEllEvens);
}
static void ell_odd(giant x1, giant z1, giant x2, giant z2, giant xxor,
giant zor, curveParams *par)
{
giant t1;
giant t2;
EPROF_START;
t1 = borrowGiant(par->maxDigits);
t2 = borrowGiant(par->maxDigits);
if(par->curveType == FCT_Montgomery) {
giant t3 = borrowGiant(par->maxDigits);
giant t4 = borrowGiant(par->maxDigits);
gtog(x1, t1); addg(z1, t1);
gtog(x2, t2); subg(z2, t2);
gtog(x1, t3); subg(z1, t3);
gtog(x2, t4); addg(z2, t4);
mulg(t2, t1); feemod(par, t1);
mulg(t4, t3); feemod(par, t3);
gtog(t1, z2); subg(t3, z2);
gsquare(z2); feemod(par, z2);
mulg(xxor, z2); feemod(par, z2);
gtog(t1, x2); addg(t3, x2);
gsquare(x2); feemod(par, x2);
mulg(zor, x2); feemod(par, x2);
returnGiant(t3);
returnGiant(t4);
}
else if((par->curveType == FCT_Weierstrass) && isZero(par->a)) {
giant t3 = borrowGiant(par->maxDigits);
giant t4 = borrowGiant(par->maxDigits);
gtog(x1, t1); mulg(x2, t1); feemod(par, t1);
gtog(z1, t2); mulg(z2, t2); feemod(par, t2);
gtog(x1, t3); mulg(z2, t3); feemod(par, t3);
gtog(z1, t4); mulg(x2, t4); feemod(par, t4);
gtog(t3, z2); subg(t4, z2); gsquare(z2); feemod(par, z2);
mulg(xxor, z2); feemod(par, z2);
gtog(t1, x2); gsquare(x2); feemod(par, x2);
addg(t4, t3); mulg(t2, t3); feemod(par, t3);
mulg(par->b, t3); feemod(par, t3);
addg(t3, t3); addg(t3, t3);
subg(t3, x2); mulg(zor, x2); feemod(par, x2);
returnGiant(t3);
returnGiant(t4);
}
else {
numer_times(x1, z1, x2, z2, t1, par);
mulg(zor, t1); feemod(par, t1);
denom_times(x1, z1, x2, z2, t2, par);
mulg(xxor, t2); feemod(par, t2);
gtog(t1, x2); gtog(t2, z2);
}
returnGiant(t1);
returnGiant(t2);
EPROF_END(ellOddTime);
EPROF_INCR(numEllOdds);
}
#define CURVE_PARAM_MISMATCH 1
#define TWIST_PARAM_MISMATCH 2
#define SIGNATURE_INVALID 3
static int keys_inconsistent(key pub1, key pub2){
if(!curveParamsEquivalent(pub1->cp, pub2->cp)) {
return CURVE_PARAM_MISMATCH;
}
if(pub1->twist != pub2->twist) {
return TWIST_PARAM_MISMATCH;
}
return 0;
}
int signature_compare(giant p0x, giant p1x, giant p2x, curveParams *par)
{
int ret = 0;
giant t1;
giant t2;
giant t3;
giant t4;
giant t5;
PROF_START;
t1 = borrowGiant(par->maxDigits);
t2 = borrowGiant(par->maxDigits);
t3 = borrowGiant(par->maxDigits);
t4 = borrowGiant(par->maxDigits);
t5 = borrowGiant(par->maxDigits);
if(gcompg(p1x, p2x) == 0) {
int_to_giant(1, t1);
numer_double(p1x, t1, t2, par);
denom_double(p1x, t1, t3, par);
mulg(p0x, t3); subg(t3, t2);
feemod(par, t2);
} else {
numer_plus(p1x, p2x, t1, par);
gshiftleft(1, t1); feemod(par, t1);
int_to_giant(1, t3);
numer_times(p1x, t3, p2x, t3, t2, par);
int_to_giant(1, t4); int_to_giant(1, t5);
denom_times(p1x, t4 , p2x, t5, t3, par);
mulg(p0x, t3); feemod(par, t3);
subg(t1, t3); mulg(p0x, t3);
feemod(par, t3);
addg(t3, t2);
feemod(par, t2);
}
if(!isZero(t2)) ret = SIGNATURE_INVALID;
returnGiant(t1);
returnGiant(t2);
returnGiant(t3);
returnGiant(t4);
returnGiant(t5);
PROF_END(sigCompTime);
return(ret);
}
static void numer_double(giant x, giant z, giant res, curveParams *par)
{
giant t1;
giant t2;
PROF_START;
t1 = borrowGiant(par->maxDigits);
t2 = borrowGiant(par->maxDigits);
gtog(x, t1); gsquare(t1); feemod(par, t1);
gtog(z, res); gsquare(res); feemod(par, res);
gtog(res, t2);
if(!isZero(par->a) ) {
if(!isone(par->a)) {
mulg(par->a, res); feemod(par, res);
}
subg(res, t1); feemod(par, t1);
}
gsquare(t1); feemod(par, t1);
if(isZero(par->b)) {
gtog(t1, res);
goto done;
}
if(par->curveType != FCT_Weierstrass) { gtog(z, res); mulg(par->c, res); feemod(par, res);
} else {
int_to_giant(0, res);
}
addg(x, res); addg(x, res); mulg(par->b, res);
feemod(par, res);
gshiftleft(2, res); mulg(z, res); feemod(par, res);
mulg(t2, res); feemod(par, res);
negg(res); addg(t1, res);
feemod(par, res);
done:
returnGiant(t1);
returnGiant(t2);
PROF_END(numerDoubleTime);
}
static void numer_plus(giant x1, giant x2, giant res, curveParams *par)
{
giant t1;
giant t2;
PROF_START;
t1 = borrowGiant(par->maxDigits);
t2 = borrowGiant(par->maxDigits);
gtog(x1, t1); mulg(x2, t1); feemod(par, t1);
gtog(x2, t2); addg(x1, t2); feemod(par, t2);
gtog(t1, res);
if(!isZero(par->a))
addg(par->a, res);
mulg(t2, res); feemod(par, res);
if(par->curveType == FCT_Weierstrass) { int_to_giant(0, t1);
}
else {
mulg(par->c, t1); feemod(par, t1);
}
if(!isZero(par->b))
addg(par->b, t1);
gshiftleft(1, t1);
addg(t1, res); feemod(par, res);
returnGiant(t1);
returnGiant(t2);
PROF_END(numerPlusTime);
}
static void denom_double(giant x, giant z, giant res, curveParams *par)
{
giant t1;
giant t2;
PROF_START;
t1 = borrowGiant(par->maxDigits);
t2 = borrowGiant(par->maxDigits);
gtog(x, res); gtog(z, t1);
if(par->curveType != FCT_Weierstrass) { gtog(par->c, t2); mulg(t1, t2); feemod(par, t2);
addg(t2, res);
}
mulg(x, res); feemod(par, res);
gsquare(t1); feemod(par, t1);
if(!isZero(par->a)) {
gtog(t1, t2);
mulg(par->a, t2); feemod(par, t2);
addg(t2, res);
}
mulg(x, res); feemod(par, res);
if(!isZero(par->b)) {
mulg(z, t1); feemod(par, t1);
mulg(par->b, t1); feemod(par, t1);
addg(t1, res);
}
mulg(z, res); gshiftleft(2, res);
feemod(par, res);
returnGiant(t1);
returnGiant(t2);
PROF_END(denomDoubleTime);
}
static void denom_times(giant x1, giant z1, giant x2, giant z2, giant res,
curveParams *par)
{
giant t1;
PROF_START;
t1 = borrowGiant(par->maxDigits);
gtog(x1, res); mulg(z2, res); feemod(par, res);
gtog(z1, t1); mulg(x2, t1); feemod(par, t1);
subg(t1, res); gsquare(res); feemod(par, res);
returnGiant(t1);
PROF_END(denomTimesTime);
}
static void numer_times(giant x1, giant z1, giant x2, giant z2, giant res,
curveParams *par)
{
giant t1;
giant t2;
giant t3;
giant t4;
PROF_START;
t1 = borrowGiant(par->maxDigits);
t2 = borrowGiant(par->maxDigits);
t3 = borrowGiant(par->maxDigits);
t4 = borrowGiant(par->maxDigits);
gtog(x1, t1); mulg(x2, t1); feemod(par, t1);
gtog(z1, t2); mulg(z2, t2); feemod(par, t2);
gtog(t1, res);
if(!isZero(par->a)) {
gtog(par->a, t3);
mulg(t2, t3); feemod(par, t3);
subg(t3, res);
}
gsquare(res); feemod(par, res);
if(isZero(par->b))
goto done;
if(par->curveType != FCT_Weierstrass) { gtog(par->c, t3);
mulg(t2, t3); feemod(par, t3);
} else int_to_giant(0, t3);
gtog(z1, t4); mulg(x2, t4); feemod(par, t4);
addg(t4, t3);
gtog(x1, t4); mulg(z2, t4); feemod(par, t4);
addg(t4, t3); mulg(par->b, t3); feemod(par, t3);
mulg(t2, t3); gshiftleft(2, t3); feemod(par, t3);
subg(t3, res);
feemod(par, res);
done:
returnGiant(t1);
returnGiant(t2);
returnGiant(t3);
returnGiant(t4);
PROF_END(numerTimesTime);
}
static void feepowermodg(curveParams *par, giant x, giant n)
{
int len, pos;
giant t1;
PROF_START;
t1 = borrowGiant(par->maxDigits);
gtog(x, t1);
int_to_giant(1, x);
len = bitlen(n);
pos = 0;
while(1) {
if(bitval(n, pos++)) {
mulg(t1, x);
feemod(par, x);
}
if(pos>=len) break;
gsquare(t1);
feemod(par, t1);
}
returnGiant(t1);
PROF_END(powerModTime);
}
void curveOrderJustify(giant g, giant curveOrder)
{
giant recip;
CKASSERT(!isZero(curveOrder));
recip = borrowGiant(2 * abs(g->sign));
make_recip(curveOrder, recip);
curveOrderJustifyWithRecip(g, curveOrder, recip);
returnGiant(recip);
}
static void curveOrderJustifyWithRecip(giant g, giant curveOrder, giant recip)
{
giant tmp;
CKASSERT(!isZero(curveOrder));
modg_via_recip(curveOrder, recip, g);
if(isZero(g)) {
dbgLog(("curveOrderJustify: case 1\n"));
int_to_giant(2, g);
return;
}
if(isone(g)) {
dbgLog(("curveOrderJustify: case 2\n"));
int_to_giant(2, g);
return;
}
tmp = borrowGiant(g->capacity);
gtog(g, tmp);
iaddg(1, tmp);
if(gcompg(tmp, curveOrder) == 0) {
dbgLog(("curveOrderJustify: case 3\n"));
int_to_giant(1, tmp);
subg(tmp, g);
}
returnGiant(tmp);
return;
}
#define RECIP_DEBUG 0
#if RECIP_DEBUG
#define recipLog(x) printf x
#else // RECIP_DEBUG
#define recipLog(x)
#endif // RECIP_DEBUG
void lesserX1OrderJustify(giant g, curveParams *cp)
{
giant lesserX1Ord = lesserX1Order(cp);
if(isZero(lesserX1Ord)) {
return;
}
if(isZero(cp->lesserX1OrderRecip)) {
if((lesserX1Ord == cp->x1OrderPlus) &&
(!isZero(cp->x1OrderPlusRecip))) {
recipLog((
"x1OrderPlusRecip --> lesserX1OrderRecip\n"));
gtog(cp->x1OrderPlusRecip, cp->lesserX1OrderRecip);
}
else {
recipLog(("calc lesserX1OrderRecip\n"));
make_recip(lesserX1Ord, cp->lesserX1OrderRecip);
}
}
else {
recipLog(("using existing lesserX1OrderRecip\n"));
}
curveOrderJustifyWithRecip(g, lesserX1Ord, cp->lesserX1OrderRecip);
}
void calcX1OrderPlusRecip(curveParams *cp)
{
if(isZero(cp->x1OrderPlusRecip)) {
if((cp->x1OrderPlus == lesserX1Order(cp)) &&
(!isZero(cp->lesserX1OrderRecip))) {
recipLog((
"lesserX1OrderRecip --> x1OrderPlusRecip\n"));
gtog(cp->lesserX1OrderRecip, cp->x1OrderPlusRecip);
}
else {
recipLog(("calc x1OrderPlusRecip\n"));
make_recip(cp->x1OrderPlus, cp->x1OrderPlusRecip);
}
}
else {
recipLog(("using existing x1OrderPlusRecip\n"));
}
}
void x1OrderPlusJustify(giant g, curveParams *cp)
{
CKASSERT(!isZero(cp->x1OrderPlus));
calcX1OrderPlusRecip(cp);
curveOrderJustifyWithRecip(g, cp->x1OrderPlus, cp->x1OrderPlusRecip);
}
void x1OrderPlusMod(giant g, curveParams *cp)
{
CKASSERT(!isZero(cp->x1OrderPlus));
calcX1OrderPlusRecip(cp);
modg_via_recip(cp->x1OrderPlus, cp->x1OrderPlusRecip, g);
}
#define FEEMOD_LOOP_TEST 0
#if FEEMOD_LOOP_TEST
unsigned feemodCalls = 0; unsigned feemodMultLoops = 0; #define FEEMOD_LOOP_INCR feemodLoops++
#define FEEMOD_CALL_INCR feemodCalls++
#else // FEEMOD_LOOP_TEST
#define FEEMOD_LOOP_INCR
#define FEEMOD_CALL_INCR
#endif // FEEMOD_LOOP_TEST
void
feemod(curveParams *par, giant x)
{
int sign, sign2;
giant t1;
giant t3;
giant t4;
giant t5;
#if FEEMOD_LOOP_TEST
unsigned feemodLoops = 0;
#endif
FEEMOD_CALL_INCR; INCR_FEEMODS; PROF_INCR(numFeemod);
switch(par->primeType) {
case FPT_Mersenne:
gmersennemod(par->q, x);
break;
case FPT_FEE:
sign = (x->sign < 0) ? -1 : 1;
sign2 = 1;
x->sign = abs(x->sign);
if(gcompg(par->basePrime, x) >= 0) {
goto outFee;
}
t1 = borrowGiant(par->maxDigits);
t3 = borrowGiant(par->maxDigits);
t4 = borrowGiant(par->maxDigits);
t5 = borrowGiant(par->maxDigits);
if( ((par->q & (GIANT_BITS_PER_DIGIT - 1)) == 0) &&
(par->k >= 0) &&
(par->k < GIANT_DIGIT_MASK)) {
int j, digits, excess, max;
giantDigit carry;
giantDigit termHi; giantDigit termLo;
giantDigit *p1, *p2;
digits = par->q >> GIANT_LOG2_BITS_PER_DIGIT;
while(bitlen(x) > par->q) {
excess = (x->sign) - digits;
max = (excess > digits) ? excess : digits;
carry = 0;
p1 = &x->n[0];
p2 = &x->n[digits];
if(excess <= digits) {
carry = VectorMultiply(par->k,
p2,
excess,
p1);
p1 += excess;
for(j = excess; j < digits; j++) {
termLo = giantAddDigits(*p1, carry, &carry);
*p1++ = termLo;
}
} else {
carry = VectorMultiply(par->k,
p2,
digits,
p1);
p1 += digits;
p2 += digits;
for(j = digits; j < excess; j++) {
giantMulDigits(par->k,
*p2++,
&termLo,
&termHi);
giantAddDouble(&termLo, &termHi, carry);
*p1++ = termLo;
carry = termHi;
}
}
if(carry > 0) {
x->n[max] = carry;
} else {
while(--max){
if(x->n[max] != 0) break;
}
}
x->sign = max + 1;
FEEMOD_LOOP_INCR;
}
} else {
int_to_giant(par->k, t4);
while(bitlen(x) > par->q) {
int_to_giant(1, t5);
gtog(x, t3);
extractbits(par->q, t3, x);
while(bitlen(t3) > par->q) {
gshiftright(par->q, t3);
extractbits(par->q, t3, t1);
PAUSE_ELL_MEASURE;
mulg(t4, t5);
mulg(t5, t1);
RESUME_ELL_MEASURE;
addg(t1, x);
}
FEEMOD_LOOP_INCR;
}
}
sign2 = (x->sign < 0)? -1: 1;
x->sign = abs(x->sign);
returnGiant(t1);
returnGiant(t3);
returnGiant(t4);
returnGiant(t5);
outFee:
if(gcompg(x, par->basePrime) >=0) subg(par->basePrime, x);
if(sign != sign2) {
giant t2 = borrowGiant(par->maxDigits);
gtog(par->basePrime, t2);
subg(x, t2);
gtog(t2, x);
returnGiant(t2);
}
break;
case FPT_General:
#if FEE_DEBUG
if(par->basePrimeRecip == NULL) {
CKRaise("feemod(PT_GENERAL): No basePrimeRecip!\n");
}
#endif
modg_via_recip(par->basePrime, par->basePrimeRecip, x);
break;
case FPT_Default:
CKASSERT(0);
break;
}
#if FEEMOD_LOOP_TEST
if(feemodLoops > 1) {
feemodMultLoops++;
if(feemodLoops > 2) {
printf("feemod while loop executed %d times\n", feemodLoops);
}
}
#endif
return;
}
void calcGiantSizes(curveParams *cp)
{
if(cp->primeType == FPT_General) {
cp->minBytes = (bitlen(cp->basePrime) + 7) / 8;
}
else {
cp->minBytes = giantMinBytes(cp->q, cp->k);
}
cp->maxDigits = giantMaxDigits(cp->minBytes);
}
unsigned giantMinBytes(unsigned q, int k)
{
unsigned kIsNeg = (k < 0) ? 1 : 0;
return (q + 7 + kIsNeg) / 8;
}
#define MIN_EXTRA_BYTES 20
unsigned giantMaxDigits(unsigned minBytes)
{
unsigned maxBytes = 4 * minBytes;
if((maxBytes - minBytes) < MIN_EXTRA_BYTES) {
maxBytes = minBytes + MIN_EXTRA_BYTES;
}
return BYTES_TO_GIANT_DIGITS(maxBytes);
}
int binvg_cp(curveParams *cp, giant x)
{
feemod(cp, x);
return(binvaux(cp->basePrime, x));
}
int binvg_x1OrderPlus(curveParams *cp, giant x)
{
x1OrderPlusMod(x, cp);
return(binvaux(cp->x1OrderPlus, x));
}