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