Annotation of src/usr.bin/signify/fe25519.c, Revision 1.1
1.1 ! deraadt 1: /* $OpenBSD: fe25519.c,v 1.3 2013/12/09 11:03:45 markus Exp $ */
! 2:
! 3: /*
! 4: * Public Domain, Authors: Daniel J. Bernstein, Niels Duif, Tanja Lange,
! 5: * Peter Schwabe, Bo-Yin Yang.
! 6: * Copied from supercop-20130419/crypto_sign/ed25519/ref/fe25519.c
! 7: */
! 8:
! 9: #define WINDOWSIZE 1 /* Should be 1,2, or 4 */
! 10: #define WINDOWMASK ((1<<WINDOWSIZE)-1)
! 11:
! 12: #include "fe25519.h"
! 13:
! 14: static crypto_uint32 equal(crypto_uint32 a,crypto_uint32 b) /* 16-bit inputs */
! 15: {
! 16: crypto_uint32 x = a ^ b; /* 0: yes; 1..65535: no */
! 17: x -= 1; /* 4294967295: yes; 0..65534: no */
! 18: x >>= 31; /* 1: yes; 0: no */
! 19: return x;
! 20: }
! 21:
! 22: static crypto_uint32 ge(crypto_uint32 a,crypto_uint32 b) /* 16-bit inputs */
! 23: {
! 24: unsigned int x = a;
! 25: x -= (unsigned int) b; /* 0..65535: yes; 4294901761..4294967295: no */
! 26: x >>= 31; /* 0: yes; 1: no */
! 27: x ^= 1; /* 1: yes; 0: no */
! 28: return x;
! 29: }
! 30:
! 31: static crypto_uint32 times19(crypto_uint32 a)
! 32: {
! 33: return (a << 4) + (a << 1) + a;
! 34: }
! 35:
! 36: static crypto_uint32 times38(crypto_uint32 a)
! 37: {
! 38: return (a << 5) + (a << 2) + (a << 1);
! 39: }
! 40:
! 41: static void reduce_add_sub(fe25519 *r)
! 42: {
! 43: crypto_uint32 t;
! 44: int i,rep;
! 45:
! 46: for(rep=0;rep<4;rep++)
! 47: {
! 48: t = r->v[31] >> 7;
! 49: r->v[31] &= 127;
! 50: t = times19(t);
! 51: r->v[0] += t;
! 52: for(i=0;i<31;i++)
! 53: {
! 54: t = r->v[i] >> 8;
! 55: r->v[i+1] += t;
! 56: r->v[i] &= 255;
! 57: }
! 58: }
! 59: }
! 60:
! 61: static void reduce_mul(fe25519 *r)
! 62: {
! 63: crypto_uint32 t;
! 64: int i,rep;
! 65:
! 66: for(rep=0;rep<2;rep++)
! 67: {
! 68: t = r->v[31] >> 7;
! 69: r->v[31] &= 127;
! 70: t = times19(t);
! 71: r->v[0] += t;
! 72: for(i=0;i<31;i++)
! 73: {
! 74: t = r->v[i] >> 8;
! 75: r->v[i+1] += t;
! 76: r->v[i] &= 255;
! 77: }
! 78: }
! 79: }
! 80:
! 81: /* reduction modulo 2^255-19 */
! 82: void fe25519_freeze(fe25519 *r)
! 83: {
! 84: int i;
! 85: crypto_uint32 m = equal(r->v[31],127);
! 86: for(i=30;i>0;i--)
! 87: m &= equal(r->v[i],255);
! 88: m &= ge(r->v[0],237);
! 89:
! 90: m = -m;
! 91:
! 92: r->v[31] -= m&127;
! 93: for(i=30;i>0;i--)
! 94: r->v[i] -= m&255;
! 95: r->v[0] -= m&237;
! 96: }
! 97:
! 98: void fe25519_unpack(fe25519 *r, const unsigned char x[32])
! 99: {
! 100: int i;
! 101: for(i=0;i<32;i++) r->v[i] = x[i];
! 102: r->v[31] &= 127;
! 103: }
! 104:
! 105: /* Assumes input x being reduced below 2^255 */
! 106: void fe25519_pack(unsigned char r[32], const fe25519 *x)
! 107: {
! 108: int i;
! 109: fe25519 y = *x;
! 110: fe25519_freeze(&y);
! 111: for(i=0;i<32;i++)
! 112: r[i] = y.v[i];
! 113: }
! 114:
! 115: int fe25519_iszero(const fe25519 *x)
! 116: {
! 117: int i;
! 118: int r;
! 119: fe25519 t = *x;
! 120: fe25519_freeze(&t);
! 121: r = equal(t.v[0],0);
! 122: for(i=1;i<32;i++)
! 123: r &= equal(t.v[i],0);
! 124: return r;
! 125: }
! 126:
! 127: int fe25519_iseq_vartime(const fe25519 *x, const fe25519 *y)
! 128: {
! 129: int i;
! 130: fe25519 t1 = *x;
! 131: fe25519 t2 = *y;
! 132: fe25519_freeze(&t1);
! 133: fe25519_freeze(&t2);
! 134: for(i=0;i<32;i++)
! 135: if(t1.v[i] != t2.v[i]) return 0;
! 136: return 1;
! 137: }
! 138:
! 139: void fe25519_cmov(fe25519 *r, const fe25519 *x, unsigned char b)
! 140: {
! 141: int i;
! 142: crypto_uint32 mask = b;
! 143: mask = -mask;
! 144: for(i=0;i<32;i++) r->v[i] ^= mask & (x->v[i] ^ r->v[i]);
! 145: }
! 146:
! 147: unsigned char fe25519_getparity(const fe25519 *x)
! 148: {
! 149: fe25519 t = *x;
! 150: fe25519_freeze(&t);
! 151: return t.v[0] & 1;
! 152: }
! 153:
! 154: void fe25519_setone(fe25519 *r)
! 155: {
! 156: int i;
! 157: r->v[0] = 1;
! 158: for(i=1;i<32;i++) r->v[i]=0;
! 159: }
! 160:
! 161: void fe25519_setzero(fe25519 *r)
! 162: {
! 163: int i;
! 164: for(i=0;i<32;i++) r->v[i]=0;
! 165: }
! 166:
! 167: void fe25519_neg(fe25519 *r, const fe25519 *x)
! 168: {
! 169: fe25519 t;
! 170: int i;
! 171: for(i=0;i<32;i++) t.v[i]=x->v[i];
! 172: fe25519_setzero(r);
! 173: fe25519_sub(r, r, &t);
! 174: }
! 175:
! 176: void fe25519_add(fe25519 *r, const fe25519 *x, const fe25519 *y)
! 177: {
! 178: int i;
! 179: for(i=0;i<32;i++) r->v[i] = x->v[i] + y->v[i];
! 180: reduce_add_sub(r);
! 181: }
! 182:
! 183: void fe25519_sub(fe25519 *r, const fe25519 *x, const fe25519 *y)
! 184: {
! 185: int i;
! 186: crypto_uint32 t[32];
! 187: t[0] = x->v[0] + 0x1da;
! 188: t[31] = x->v[31] + 0xfe;
! 189: for(i=1;i<31;i++) t[i] = x->v[i] + 0x1fe;
! 190: for(i=0;i<32;i++) r->v[i] = t[i] - y->v[i];
! 191: reduce_add_sub(r);
! 192: }
! 193:
! 194: void fe25519_mul(fe25519 *r, const fe25519 *x, const fe25519 *y)
! 195: {
! 196: int i,j;
! 197: crypto_uint32 t[63];
! 198: for(i=0;i<63;i++)t[i] = 0;
! 199:
! 200: for(i=0;i<32;i++)
! 201: for(j=0;j<32;j++)
! 202: t[i+j] += x->v[i] * y->v[j];
! 203:
! 204: for(i=32;i<63;i++)
! 205: r->v[i-32] = t[i-32] + times38(t[i]);
! 206: r->v[31] = t[31]; /* result now in r[0]...r[31] */
! 207:
! 208: reduce_mul(r);
! 209: }
! 210:
! 211: void fe25519_square(fe25519 *r, const fe25519 *x)
! 212: {
! 213: fe25519_mul(r, x, x);
! 214: }
! 215:
! 216: void fe25519_invert(fe25519 *r, const fe25519 *x)
! 217: {
! 218: fe25519 z2;
! 219: fe25519 z9;
! 220: fe25519 z11;
! 221: fe25519 z2_5_0;
! 222: fe25519 z2_10_0;
! 223: fe25519 z2_20_0;
! 224: fe25519 z2_50_0;
! 225: fe25519 z2_100_0;
! 226: fe25519 t0;
! 227: fe25519 t1;
! 228: int i;
! 229:
! 230: /* 2 */ fe25519_square(&z2,x);
! 231: /* 4 */ fe25519_square(&t1,&z2);
! 232: /* 8 */ fe25519_square(&t0,&t1);
! 233: /* 9 */ fe25519_mul(&z9,&t0,x);
! 234: /* 11 */ fe25519_mul(&z11,&z9,&z2);
! 235: /* 22 */ fe25519_square(&t0,&z11);
! 236: /* 2^5 - 2^0 = 31 */ fe25519_mul(&z2_5_0,&t0,&z9);
! 237:
! 238: /* 2^6 - 2^1 */ fe25519_square(&t0,&z2_5_0);
! 239: /* 2^7 - 2^2 */ fe25519_square(&t1,&t0);
! 240: /* 2^8 - 2^3 */ fe25519_square(&t0,&t1);
! 241: /* 2^9 - 2^4 */ fe25519_square(&t1,&t0);
! 242: /* 2^10 - 2^5 */ fe25519_square(&t0,&t1);
! 243: /* 2^10 - 2^0 */ fe25519_mul(&z2_10_0,&t0,&z2_5_0);
! 244:
! 245: /* 2^11 - 2^1 */ fe25519_square(&t0,&z2_10_0);
! 246: /* 2^12 - 2^2 */ fe25519_square(&t1,&t0);
! 247: /* 2^20 - 2^10 */ for (i = 2;i < 10;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); }
! 248: /* 2^20 - 2^0 */ fe25519_mul(&z2_20_0,&t1,&z2_10_0);
! 249:
! 250: /* 2^21 - 2^1 */ fe25519_square(&t0,&z2_20_0);
! 251: /* 2^22 - 2^2 */ fe25519_square(&t1,&t0);
! 252: /* 2^40 - 2^20 */ for (i = 2;i < 20;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); }
! 253: /* 2^40 - 2^0 */ fe25519_mul(&t0,&t1,&z2_20_0);
! 254:
! 255: /* 2^41 - 2^1 */ fe25519_square(&t1,&t0);
! 256: /* 2^42 - 2^2 */ fe25519_square(&t0,&t1);
! 257: /* 2^50 - 2^10 */ for (i = 2;i < 10;i += 2) { fe25519_square(&t1,&t0); fe25519_square(&t0,&t1); }
! 258: /* 2^50 - 2^0 */ fe25519_mul(&z2_50_0,&t0,&z2_10_0);
! 259:
! 260: /* 2^51 - 2^1 */ fe25519_square(&t0,&z2_50_0);
! 261: /* 2^52 - 2^2 */ fe25519_square(&t1,&t0);
! 262: /* 2^100 - 2^50 */ for (i = 2;i < 50;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); }
! 263: /* 2^100 - 2^0 */ fe25519_mul(&z2_100_0,&t1,&z2_50_0);
! 264:
! 265: /* 2^101 - 2^1 */ fe25519_square(&t1,&z2_100_0);
! 266: /* 2^102 - 2^2 */ fe25519_square(&t0,&t1);
! 267: /* 2^200 - 2^100 */ for (i = 2;i < 100;i += 2) { fe25519_square(&t1,&t0); fe25519_square(&t0,&t1); }
! 268: /* 2^200 - 2^0 */ fe25519_mul(&t1,&t0,&z2_100_0);
! 269:
! 270: /* 2^201 - 2^1 */ fe25519_square(&t0,&t1);
! 271: /* 2^202 - 2^2 */ fe25519_square(&t1,&t0);
! 272: /* 2^250 - 2^50 */ for (i = 2;i < 50;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); }
! 273: /* 2^250 - 2^0 */ fe25519_mul(&t0,&t1,&z2_50_0);
! 274:
! 275: /* 2^251 - 2^1 */ fe25519_square(&t1,&t0);
! 276: /* 2^252 - 2^2 */ fe25519_square(&t0,&t1);
! 277: /* 2^253 - 2^3 */ fe25519_square(&t1,&t0);
! 278: /* 2^254 - 2^4 */ fe25519_square(&t0,&t1);
! 279: /* 2^255 - 2^5 */ fe25519_square(&t1,&t0);
! 280: /* 2^255 - 21 */ fe25519_mul(r,&t1,&z11);
! 281: }
! 282:
! 283: void fe25519_pow2523(fe25519 *r, const fe25519 *x)
! 284: {
! 285: fe25519 z2;
! 286: fe25519 z9;
! 287: fe25519 z11;
! 288: fe25519 z2_5_0;
! 289: fe25519 z2_10_0;
! 290: fe25519 z2_20_0;
! 291: fe25519 z2_50_0;
! 292: fe25519 z2_100_0;
! 293: fe25519 t;
! 294: int i;
! 295:
! 296: /* 2 */ fe25519_square(&z2,x);
! 297: /* 4 */ fe25519_square(&t,&z2);
! 298: /* 8 */ fe25519_square(&t,&t);
! 299: /* 9 */ fe25519_mul(&z9,&t,x);
! 300: /* 11 */ fe25519_mul(&z11,&z9,&z2);
! 301: /* 22 */ fe25519_square(&t,&z11);
! 302: /* 2^5 - 2^0 = 31 */ fe25519_mul(&z2_5_0,&t,&z9);
! 303:
! 304: /* 2^6 - 2^1 */ fe25519_square(&t,&z2_5_0);
! 305: /* 2^10 - 2^5 */ for (i = 1;i < 5;i++) { fe25519_square(&t,&t); }
! 306: /* 2^10 - 2^0 */ fe25519_mul(&z2_10_0,&t,&z2_5_0);
! 307:
! 308: /* 2^11 - 2^1 */ fe25519_square(&t,&z2_10_0);
! 309: /* 2^20 - 2^10 */ for (i = 1;i < 10;i++) { fe25519_square(&t,&t); }
! 310: /* 2^20 - 2^0 */ fe25519_mul(&z2_20_0,&t,&z2_10_0);
! 311:
! 312: /* 2^21 - 2^1 */ fe25519_square(&t,&z2_20_0);
! 313: /* 2^40 - 2^20 */ for (i = 1;i < 20;i++) { fe25519_square(&t,&t); }
! 314: /* 2^40 - 2^0 */ fe25519_mul(&t,&t,&z2_20_0);
! 315:
! 316: /* 2^41 - 2^1 */ fe25519_square(&t,&t);
! 317: /* 2^50 - 2^10 */ for (i = 1;i < 10;i++) { fe25519_square(&t,&t); }
! 318: /* 2^50 - 2^0 */ fe25519_mul(&z2_50_0,&t,&z2_10_0);
! 319:
! 320: /* 2^51 - 2^1 */ fe25519_square(&t,&z2_50_0);
! 321: /* 2^100 - 2^50 */ for (i = 1;i < 50;i++) { fe25519_square(&t,&t); }
! 322: /* 2^100 - 2^0 */ fe25519_mul(&z2_100_0,&t,&z2_50_0);
! 323:
! 324: /* 2^101 - 2^1 */ fe25519_square(&t,&z2_100_0);
! 325: /* 2^200 - 2^100 */ for (i = 1;i < 100;i++) { fe25519_square(&t,&t); }
! 326: /* 2^200 - 2^0 */ fe25519_mul(&t,&t,&z2_100_0);
! 327:
! 328: /* 2^201 - 2^1 */ fe25519_square(&t,&t);
! 329: /* 2^250 - 2^50 */ for (i = 1;i < 50;i++) { fe25519_square(&t,&t); }
! 330: /* 2^250 - 2^0 */ fe25519_mul(&t,&t,&z2_50_0);
! 331:
! 332: /* 2^251 - 2^1 */ fe25519_square(&t,&t);
! 333: /* 2^252 - 2^2 */ fe25519_square(&t,&t);
! 334: /* 2^252 - 3 */ fe25519_mul(r,&t,x);
! 335: }
![[BACK]](/icons/back.gif){kind=icon}
Return to fe25519.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / signify