Annotation of src/usr.bin/ssh/sntrup4591761.c, Revision 1.1
1.1 ! djm 1: #include <string.h>
! 2: #include "crypto_api.h"
! 3:
! 4: /* from supercop-20181216/crypto_sort/int32/portable3/int32_minmax.inc */
! 5: #define int32_MINMAX(a,b) \
! 6: do { \
! 7: int32 ab = b ^ a; \
! 8: int32 c = b - a; \
! 9: c ^= ab & (c ^ b); \
! 10: c >>= 31; \
! 11: c &= ab; \
! 12: a ^= c; \
! 13: b ^= c; \
! 14: } while(0)
! 15:
! 16: /* from supercop-20181216/crypto_sort/int32/portable3/sort.c */
! 17: #define int32 crypto_int32
! 18:
! 19:
! 20: static void crypto_sort_int32(void *array,long long n)
! 21: {
! 22: long long top,p,q,r,i;
! 23: int32 *x = array;
! 24:
! 25: if (n < 2) return;
! 26: top = 1;
! 27: while (top < n - top) top += top;
! 28:
! 29: for (p = top;p > 0;p >>= 1) {
! 30: for (i = 0;i < n - p;++i)
! 31: if (!(i & p))
! 32: int32_MINMAX(x[i],x[i+p]);
! 33: i = 0;
! 34: for (q = top;q > p;q >>= 1) {
! 35: for (;i < n - q;++i) {
! 36: if (!(i & p)) {
! 37: int32 a = x[i + p];
! 38: for (r = q;r > p;r >>= 1)
! 39: int32_MINMAX(a,x[i+r]);
! 40: x[i + p] = a;
! 41: }
! 42: }
! 43: }
! 44: }
! 45: }
! 46:
! 47: /* from supercop-20181216/crypto_kem/sntrup4591761/ref/small.h */
! 48: #ifndef small_h
! 49: #define small_h
! 50:
! 51:
! 52: typedef crypto_int8 small;
! 53:
! 54: static void small_encode(unsigned char *,const small *);
! 55:
! 56: static void small_decode(small *,const unsigned char *);
! 57:
! 58:
! 59: static void small_random(small *);
! 60:
! 61: static void small_random_weightw(small *);
! 62:
! 63: #endif
! 64:
! 65: /* from supercop-20181216/crypto_kem/sntrup4591761/ref/mod3.h */
! 66: #ifndef mod3_h
! 67: #define mod3_h
! 68:
! 69:
! 70: /* -1 if x is nonzero, 0 otherwise */
! 71: static inline int mod3_nonzero_mask(small x)
! 72: {
! 73: return -x*x;
! 74: }
! 75:
! 76: /* input between -100000 and 100000 */
! 77: /* output between -1 and 1 */
! 78: static inline small mod3_freeze(crypto_int32 a)
! 79: {
! 80: a -= 3 * ((10923 * a) >> 15);
! 81: a -= 3 * ((89478485 * a + 134217728) >> 28);
! 82: return a;
! 83: }
! 84:
! 85: static inline small mod3_minusproduct(small a,small b,small c)
! 86: {
! 87: crypto_int32 A = a;
! 88: crypto_int32 B = b;
! 89: crypto_int32 C = c;
! 90: return mod3_freeze(A - B * C);
! 91: }
! 92:
! 93: static inline small mod3_plusproduct(small a,small b,small c)
! 94: {
! 95: crypto_int32 A = a;
! 96: crypto_int32 B = b;
! 97: crypto_int32 C = c;
! 98: return mod3_freeze(A + B * C);
! 99: }
! 100:
! 101: static inline small mod3_product(small a,small b)
! 102: {
! 103: return a * b;
! 104: }
! 105:
! 106: static inline small mod3_sum(small a,small b)
! 107: {
! 108: crypto_int32 A = a;
! 109: crypto_int32 B = b;
! 110: return mod3_freeze(A + B);
! 111: }
! 112:
! 113: static inline small mod3_reciprocal(small a1)
! 114: {
! 115: return a1;
! 116: }
! 117:
! 118: static inline small mod3_quotient(small num,small den)
! 119: {
! 120: return mod3_product(num,mod3_reciprocal(den));
! 121: }
! 122:
! 123: #endif
! 124:
! 125: /* from supercop-20181216/crypto_kem/sntrup4591761/ref/modq.h */
! 126: #ifndef modq_h
! 127: #define modq_h
! 128:
! 129:
! 130: typedef crypto_int16 modq;
! 131:
! 132: /* -1 if x is nonzero, 0 otherwise */
! 133: static inline int modq_nonzero_mask(modq x)
! 134: {
! 135: crypto_int32 r = (crypto_uint16) x;
! 136: r = -r;
! 137: r >>= 30;
! 138: return r;
! 139: }
! 140:
! 141: /* input between -9000000 and 9000000 */
! 142: /* output between -2295 and 2295 */
! 143: static inline modq modq_freeze(crypto_int32 a)
! 144: {
! 145: a -= 4591 * ((228 * a) >> 20);
! 146: a -= 4591 * ((58470 * a + 134217728) >> 28);
! 147: return a;
! 148: }
! 149:
! 150: static inline modq modq_minusproduct(modq a,modq b,modq c)
! 151: {
! 152: crypto_int32 A = a;
! 153: crypto_int32 B = b;
! 154: crypto_int32 C = c;
! 155: return modq_freeze(A - B * C);
! 156: }
! 157:
! 158: static inline modq modq_plusproduct(modq a,modq b,modq c)
! 159: {
! 160: crypto_int32 A = a;
! 161: crypto_int32 B = b;
! 162: crypto_int32 C = c;
! 163: return modq_freeze(A + B * C);
! 164: }
! 165:
! 166: static inline modq modq_product(modq a,modq b)
! 167: {
! 168: crypto_int32 A = a;
! 169: crypto_int32 B = b;
! 170: return modq_freeze(A * B);
! 171: }
! 172:
! 173: static inline modq modq_square(modq a)
! 174: {
! 175: crypto_int32 A = a;
! 176: return modq_freeze(A * A);
! 177: }
! 178:
! 179: static inline modq modq_sum(modq a,modq b)
! 180: {
! 181: crypto_int32 A = a;
! 182: crypto_int32 B = b;
! 183: return modq_freeze(A + B);
! 184: }
! 185:
! 186: static inline modq modq_reciprocal(modq a1)
! 187: {
! 188: modq a2 = modq_square(a1);
! 189: modq a3 = modq_product(a2,a1);
! 190: modq a4 = modq_square(a2);
! 191: modq a8 = modq_square(a4);
! 192: modq a16 = modq_square(a8);
! 193: modq a32 = modq_square(a16);
! 194: modq a35 = modq_product(a32,a3);
! 195: modq a70 = modq_square(a35);
! 196: modq a140 = modq_square(a70);
! 197: modq a143 = modq_product(a140,a3);
! 198: modq a286 = modq_square(a143);
! 199: modq a572 = modq_square(a286);
! 200: modq a1144 = modq_square(a572);
! 201: modq a1147 = modq_product(a1144,a3);
! 202: modq a2294 = modq_square(a1147);
! 203: modq a4588 = modq_square(a2294);
! 204: modq a4589 = modq_product(a4588,a1);
! 205: return a4589;
! 206: }
! 207:
! 208: static inline modq modq_quotient(modq num,modq den)
! 209: {
! 210: return modq_product(num,modq_reciprocal(den));
! 211: }
! 212:
! 213: #endif
! 214:
! 215: /* from supercop-20181216/crypto_kem/sntrup4591761/ref/params.h */
! 216: #ifndef params_h
! 217: #define params_h
! 218:
! 219: #define q 4591
! 220: /* XXX: also built into modq in various ways */
! 221:
! 222: #define qshift 2295
! 223: #define p 761
! 224: #define w 286
! 225:
! 226: #define rq_encode_len 1218
! 227: #define small_encode_len 191
! 228:
! 229: #endif
! 230:
! 231: /* from supercop-20181216/crypto_kem/sntrup4591761/ref/r3.h */
! 232: #ifndef r3_h
! 233: #define r3_h
! 234:
! 235:
! 236: static void r3_mult(small *,const small *,const small *);
! 237:
! 238: extern int r3_recip(small *,const small *);
! 239:
! 240: #endif
! 241:
! 242: /* from supercop-20181216/crypto_kem/sntrup4591761/ref/rq.h */
! 243: #ifndef rq_h
! 244: #define rq_h
! 245:
! 246:
! 247: static void rq_encode(unsigned char *,const modq *);
! 248:
! 249: static void rq_decode(modq *,const unsigned char *);
! 250:
! 251: static void rq_encoderounded(unsigned char *,const modq *);
! 252:
! 253: static void rq_decoderounded(modq *,const unsigned char *);
! 254:
! 255: static void rq_round3(modq *,const modq *);
! 256:
! 257: static void rq_mult(modq *,const modq *,const small *);
! 258:
! 259: int rq_recip3(modq *,const small *);
! 260:
! 261: #endif
! 262:
! 263: /* from supercop-20181216/crypto_kem/sntrup4591761/ref/swap.h */
! 264: #ifndef swap_h
! 265: #define swap_h
! 266:
! 267: static void swap(void *,void *,int,int);
! 268:
! 269: #endif
! 270:
! 271: /* from supercop-20181216/crypto_kem/sntrup4591761/ref/dec.c */
! 272: /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */
! 273:
! 274: #ifdef KAT
! 275: #endif
! 276:
! 277:
! 278: int crypto_kem_sntrup4591761_dec(
! 279: unsigned char *k,
! 280: const unsigned char *cstr,
! 281: const unsigned char *sk
! 282: )
! 283: {
! 284: small f[p];
! 285: modq h[p];
! 286: small grecip[p];
! 287: modq c[p];
! 288: modq t[p];
! 289: small t3[p];
! 290: small r[p];
! 291: modq hr[p];
! 292: unsigned char rstr[small_encode_len];
! 293: unsigned char hash[64];
! 294: int i;
! 295: int result = 0;
! 296: int weight;
! 297:
! 298: small_decode(f,sk);
! 299: small_decode(grecip,sk + small_encode_len);
! 300: rq_decode(h,sk + 2 * small_encode_len);
! 301:
! 302: rq_decoderounded(c,cstr + 32);
! 303:
! 304: rq_mult(t,c,f);
! 305: for (i = 0;i < p;++i) t3[i] = mod3_freeze(modq_freeze(3*t[i]));
! 306:
! 307: r3_mult(r,t3,grecip);
! 308:
! 309: #ifdef KAT
! 310: {
! 311: int j;
! 312: printf("decrypt r:");
! 313: for (j = 0;j < p;++j)
! 314: if (r[j] == 1) printf(" +%d",j);
! 315: else if (r[j] == -1) printf(" -%d",j);
! 316: printf("\n");
! 317: }
! 318: #endif
! 319:
! 320: weight = 0;
! 321: for (i = 0;i < p;++i) weight += (1 & r[i]);
! 322: weight -= w;
! 323: result |= modq_nonzero_mask(weight); /* XXX: puts limit on p */
! 324:
! 325: rq_mult(hr,h,r);
! 326: rq_round3(hr,hr);
! 327: for (i = 0;i < p;++i) result |= modq_nonzero_mask(hr[i] - c[i]);
! 328:
! 329: small_encode(rstr,r);
! 330: crypto_hash_sha512(hash,rstr,sizeof rstr);
! 331: result |= crypto_verify_32(hash,cstr);
! 332:
! 333: for (i = 0;i < 32;++i) k[i] = (hash[32 + i] & ~result);
! 334: return result;
! 335: }
! 336:
! 337: /* from supercop-20181216/crypto_kem/sntrup4591761/ref/enc.c */
! 338: /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */
! 339:
! 340: #ifdef KAT
! 341: #endif
! 342:
! 343:
! 344: int crypto_kem_sntrup4591761_enc(
! 345: unsigned char *cstr,
! 346: unsigned char *k,
! 347: const unsigned char *pk
! 348: )
! 349: {
! 350: small r[p];
! 351: modq h[p];
! 352: modq c[p];
! 353: unsigned char rstr[small_encode_len];
! 354: unsigned char hash[64];
! 355:
! 356: small_random_weightw(r);
! 357:
! 358: #ifdef KAT
! 359: {
! 360: int i;
! 361: printf("encrypt r:");
! 362: for (i = 0;i < p;++i)
! 363: if (r[i] == 1) printf(" +%d",i);
! 364: else if (r[i] == -1) printf(" -%d",i);
! 365: printf("\n");
! 366: }
! 367: #endif
! 368:
! 369: small_encode(rstr,r);
! 370: crypto_hash_sha512(hash,rstr,sizeof rstr);
! 371:
! 372: rq_decode(h,pk);
! 373: rq_mult(c,h,r);
! 374: rq_round3(c,c);
! 375:
! 376: memcpy(k,hash + 32,32);
! 377: memcpy(cstr,hash,32);
! 378: rq_encoderounded(cstr + 32,c);
! 379:
! 380: return 0;
! 381: }
! 382:
! 383: /* from supercop-20181216/crypto_kem/sntrup4591761/ref/keypair.c */
! 384: /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */
! 385:
! 386:
! 387: #if crypto_kem_sntrup4591761_PUBLICKEYBYTES != rq_encode_len
! 388: #error "crypto_kem_sntrup4591761_PUBLICKEYBYTES must match rq_encode_len"
! 389: #endif
! 390: #if crypto_kem_sntrup4591761_SECRETKEYBYTES != rq_encode_len + 2 * small_encode_len
! 391: #error "crypto_kem_sntrup4591761_SECRETKEYBYTES must match rq_encode_len + 2 * small_encode_len"
! 392: #endif
! 393:
! 394: int crypto_kem_sntrup4591761_keypair(unsigned char *pk,unsigned char *sk)
! 395: {
! 396: small g[p];
! 397: small grecip[p];
! 398: small f[p];
! 399: modq f3recip[p];
! 400: modq h[p];
! 401:
! 402: do
! 403: small_random(g);
! 404: while (r3_recip(grecip,g) != 0);
! 405:
! 406: small_random_weightw(f);
! 407: rq_recip3(f3recip,f);
! 408:
! 409: rq_mult(h,f3recip,g);
! 410:
! 411: rq_encode(pk,h);
! 412: small_encode(sk,f);
! 413: small_encode(sk + small_encode_len,grecip);
! 414: memcpy(sk + 2 * small_encode_len,pk,rq_encode_len);
! 415:
! 416: return 0;
! 417: }
! 418:
! 419: /* from supercop-20181216/crypto_kem/sntrup4591761/ref/r3_mult.c */
! 420: /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */
! 421:
! 422:
! 423: static void r3_mult(small *h,const small *f,const small *g)
! 424: {
! 425: small fg[p + p - 1];
! 426: small result;
! 427: int i, j;
! 428:
! 429: for (i = 0;i < p;++i) {
! 430: result = 0;
! 431: for (j = 0;j <= i;++j)
! 432: result = mod3_plusproduct(result,f[j],g[i - j]);
! 433: fg[i] = result;
! 434: }
! 435: for (i = p;i < p + p - 1;++i) {
! 436: result = 0;
! 437: for (j = i - p + 1;j < p;++j)
! 438: result = mod3_plusproduct(result,f[j],g[i - j]);
! 439: fg[i] = result;
! 440: }
! 441:
! 442: for (i = p + p - 2;i >= p;--i) {
! 443: fg[i - p] = mod3_sum(fg[i - p],fg[i]);
! 444: fg[i - p + 1] = mod3_sum(fg[i - p + 1],fg[i]);
! 445: }
! 446:
! 447: for (i = 0;i < p;++i)
! 448: h[i] = fg[i];
! 449: }
! 450:
! 451: /* from supercop-20181216/crypto_kem/sntrup4591761/ref/r3_recip.c */
! 452: /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */
! 453:
! 454:
! 455: /* caller must ensure that x-y does not overflow */
! 456: static int smaller_mask_r3_recip(int x,int y)
! 457: {
! 458: return (x - y) >> 31;
! 459: }
! 460:
! 461: static void vectormod3_product(small *z,int len,const small *x,const small c)
! 462: {
! 463: int i;
! 464: for (i = 0;i < len;++i) z[i] = mod3_product(x[i],c);
! 465: }
! 466:
! 467: static void vectormod3_minusproduct(small *z,int len,const small *x,const small *y,const small c)
! 468: {
! 469: int i;
! 470: for (i = 0;i < len;++i) z[i] = mod3_minusproduct(x[i],y[i],c);
! 471: }
! 472:
! 473: static void vectormod3_shift(small *z,int len)
! 474: {
! 475: int i;
! 476: for (i = len - 1;i > 0;--i) z[i] = z[i - 1];
! 477: z[0] = 0;
! 478: }
! 479:
! 480: /*
! 481: r = s^(-1) mod m, returning 0, if s is invertible mod m
! 482: or returning -1 if s is not invertible mod m
! 483: r,s are polys of degree <p
! 484: m is x^p-x-1
! 485: */
! 486: int r3_recip(small *r,const small *s)
! 487: {
! 488: const int loops = 2*p + 1;
! 489: int loop;
! 490: small f[p + 1];
! 491: small g[p + 1];
! 492: small u[loops + 1];
! 493: small v[loops + 1];
! 494: small c;
! 495: int i;
! 496: int d = p;
! 497: int e = p;
! 498: int swapmask;
! 499:
! 500: for (i = 2;i < p;++i) f[i] = 0;
! 501: f[0] = -1;
! 502: f[1] = -1;
! 503: f[p] = 1;
! 504: /* generalization: can initialize f to any polynomial m */
! 505: /* requirements: m has degree exactly p, nonzero constant coefficient */
! 506:
! 507: for (i = 0;i < p;++i) g[i] = s[i];
! 508: g[p] = 0;
! 509:
! 510: for (i = 0;i <= loops;++i) u[i] = 0;
! 511:
! 512: v[0] = 1;
! 513: for (i = 1;i <= loops;++i) v[i] = 0;
! 514:
! 515: loop = 0;
! 516: for (;;) {
! 517: /* e == -1 or d + e + loop <= 2*p */
! 518:
! 519: /* f has degree p: i.e., f[p]!=0 */
! 520: /* f[i]==0 for i < p-d */
! 521:
! 522: /* g has degree <=p (so it fits in p+1 coefficients) */
! 523: /* g[i]==0 for i < p-e */
! 524:
! 525: /* u has degree <=loop (so it fits in loop+1 coefficients) */
! 526: /* u[i]==0 for i < p-d */
! 527: /* if invertible: u[i]==0 for i < loop-p (so can look at just p+1 coefficients) */
! 528:
! 529: /* v has degree <=loop (so it fits in loop+1 coefficients) */
! 530: /* v[i]==0 for i < p-e */
! 531: /* v[i]==0 for i < loop-p (so can look at just p+1 coefficients) */
! 532:
! 533: if (loop >= loops) break;
! 534:
! 535: c = mod3_quotient(g[p],f[p]);
! 536:
! 537: vectormod3_minusproduct(g,p + 1,g,f,c);
! 538: vectormod3_shift(g,p + 1);
! 539:
! 540: #ifdef SIMPLER
! 541: vectormod3_minusproduct(v,loops + 1,v,u,c);
! 542: vectormod3_shift(v,loops + 1);
! 543: #else
! 544: if (loop < p) {
! 545: vectormod3_minusproduct(v,loop + 1,v,u,c);
! 546: vectormod3_shift(v,loop + 2);
! 547: } else {
! 548: vectormod3_minusproduct(v + loop - p,p + 1,v + loop - p,u + loop - p,c);
! 549: vectormod3_shift(v + loop - p,p + 2);
! 550: }
! 551: #endif
! 552:
! 553: e -= 1;
! 554:
! 555: ++loop;
! 556:
! 557: swapmask = smaller_mask_r3_recip(e,d) & mod3_nonzero_mask(g[p]);
! 558: swap(&e,&d,sizeof e,swapmask);
! 559: swap(f,g,(p + 1) * sizeof(small),swapmask);
! 560:
! 561: #ifdef SIMPLER
! 562: swap(u,v,(loops + 1) * sizeof(small),swapmask);
! 563: #else
! 564: if (loop < p) {
! 565: swap(u,v,(loop + 1) * sizeof(small),swapmask);
! 566: } else {
! 567: swap(u + loop - p,v + loop - p,(p + 1) * sizeof(small),swapmask);
! 568: }
! 569: #endif
! 570: }
! 571:
! 572: c = mod3_reciprocal(f[p]);
! 573: vectormod3_product(r,p,u + p,c);
! 574: return smaller_mask_r3_recip(0,d);
! 575: }
! 576:
! 577: /* from supercop-20181216/crypto_kem/sntrup4591761/ref/randomsmall.c */
! 578: /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */
! 579:
! 580:
! 581: static void small_random(small *g)
! 582: {
! 583: int i;
! 584:
! 585: for (i = 0;i < p;++i) {
! 586: crypto_uint32 r = small_random32();
! 587: g[i] = (small) (((1073741823 & r) * 3) >> 30) - 1;
! 588: }
! 589: }
! 590:
! 591: /* from supercop-20181216/crypto_kem/sntrup4591761/ref/randomweightw.c */
! 592: /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */
! 593:
! 594:
! 595: static void small_random_weightw(small *f)
! 596: {
! 597: crypto_int32 r[p];
! 598: int i;
! 599:
! 600: for (i = 0;i < p;++i) r[i] = small_random32();
! 601: for (i = 0;i < w;++i) r[i] &= -2;
! 602: for (i = w;i < p;++i) r[i] = (r[i] & -3) | 1;
! 603: crypto_sort_int32(r,p);
! 604: for (i = 0;i < p;++i) f[i] = ((small) (r[i] & 3)) - 1;
! 605: }
! 606:
! 607: /* from supercop-20181216/crypto_kem/sntrup4591761/ref/rq.c */
! 608: /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */
! 609:
! 610:
! 611: static void rq_encode(unsigned char *c,const modq *f)
! 612: {
! 613: crypto_int32 f0, f1, f2, f3, f4;
! 614: int i;
! 615:
! 616: for (i = 0;i < p/5;++i) {
! 617: f0 = *f++ + qshift;
! 618: f1 = *f++ + qshift;
! 619: f2 = *f++ + qshift;
! 620: f3 = *f++ + qshift;
! 621: f4 = *f++ + qshift;
! 622: /* now want f0 + 6144*f1 + ... as a 64-bit integer */
! 623: f1 *= 3;
! 624: f2 *= 9;
! 625: f3 *= 27;
! 626: f4 *= 81;
! 627: /* now want f0 + f1<<11 + f2<<22 + f3<<33 + f4<<44 */
! 628: f0 += f1 << 11;
! 629: *c++ = f0; f0 >>= 8;
! 630: *c++ = f0; f0 >>= 8;
! 631: f0 += f2 << 6;
! 632: *c++ = f0; f0 >>= 8;
! 633: *c++ = f0; f0 >>= 8;
! 634: f0 += f3 << 1;
! 635: *c++ = f0; f0 >>= 8;
! 636: f0 += f4 << 4;
! 637: *c++ = f0; f0 >>= 8;
! 638: *c++ = f0; f0 >>= 8;
! 639: *c++ = f0;
! 640: }
! 641: /* XXX: using p mod 5 = 1 */
! 642: f0 = *f++ + qshift;
! 643: *c++ = f0; f0 >>= 8;
! 644: *c++ = f0;
! 645: }
! 646:
! 647: static void rq_decode(modq *f,const unsigned char *c)
! 648: {
! 649: crypto_uint32 c0, c1, c2, c3, c4, c5, c6, c7;
! 650: crypto_uint32 f0, f1, f2, f3, f4;
! 651: int i;
! 652:
! 653: for (i = 0;i < p/5;++i) {
! 654: c0 = *c++;
! 655: c1 = *c++;
! 656: c2 = *c++;
! 657: c3 = *c++;
! 658: c4 = *c++;
! 659: c5 = *c++;
! 660: c6 = *c++;
! 661: c7 = *c++;
! 662:
! 663: /* f0 + f1*6144 + f2*6144^2 + f3*6144^3 + f4*6144^4 */
! 664: /* = c0 + c1*256 + ... + c6*256^6 + c7*256^7 */
! 665: /* with each f between 0 and 4590 */
! 666:
! 667: c6 += c7 << 8;
! 668: /* c6 <= 23241 = floor(4591*6144^4/2^48) */
! 669: /* f4 = (16/81)c6 + (1/1296)(c5+[0,1]) - [0,0.75] */
! 670: /* claim: 2^19 f4 < x < 2^19(f4+1) */
! 671: /* where x = 103564 c6 + 405(c5+1) */
! 672: /* proof: x - 2^19 f4 = (76/81)c6 + (37/81)c5 + 405 - (32768/81)[0,1] + 2^19[0,0.75] */
! 673: /* at least 405 - 32768/81 > 0 */
! 674: /* at most (76/81)23241 + (37/81)255 + 405 + 2^19 0.75 < 2^19 */
! 675: f4 = (103564*c6 + 405*(c5+1)) >> 19;
! 676:
! 677: c5 += c6 << 8;
! 678: c5 -= (f4 * 81) << 4;
! 679: c4 += c5 << 8;
! 680:
! 681: /* f0 + f1*6144 + f2*6144^2 + f3*6144^3 */
! 682: /* = c0 + c1*256 + c2*256^2 + c3*256^3 + c4*256^4 */
! 683: /* c4 <= 247914 = floor(4591*6144^3/2^32) */
! 684: /* f3 = (1/54)(c4+[0,1]) - [0,0.75] */
! 685: /* claim: 2^19 f3 < x < 2^19(f3+1) */
! 686: /* where x = 9709(c4+2) */
! 687: /* proof: x - 2^19 f3 = 19418 - (1/27)c4 - (262144/27)[0,1] + 2^19[0,0.75] */
! 688: /* at least 19418 - 247914/27 - 262144/27 > 0 */
! 689: /* at most 19418 + 2^19 0.75 < 2^19 */
! 690: f3 = (9709*(c4+2)) >> 19;
! 691:
! 692: c4 -= (f3 * 27) << 1;
! 693: c3 += c4 << 8;
! 694: /* f0 + f1*6144 + f2*6144^2 */
! 695: /* = c0 + c1*256 + c2*256^2 + c3*256^3 */
! 696: /* c3 <= 10329 = floor(4591*6144^2/2^24) */
! 697: /* f2 = (4/9)c3 + (1/576)c2 + (1/147456)c1 + (1/37748736)c0 - [0,0.75] */
! 698: /* claim: 2^19 f2 < x < 2^19(f2+1) */
! 699: /* where x = 233017 c3 + 910(c2+2) */
! 700: /* proof: x - 2^19 f2 = 1820 + (1/9)c3 - (2/9)c2 - (32/9)c1 - (1/72)c0 + 2^19[0,0.75] */
! 701: /* at least 1820 - (2/9)255 - (32/9)255 - (1/72)255 > 0 */
! 702: /* at most 1820 + (1/9)10329 + 2^19 0.75 < 2^19 */
! 703: f2 = (233017*c3 + 910*(c2+2)) >> 19;
! 704:
! 705: c2 += c3 << 8;
! 706: c2 -= (f2 * 9) << 6;
! 707: c1 += c2 << 8;
! 708: /* f0 + f1*6144 */
! 709: /* = c0 + c1*256 */
! 710: /* c1 <= 110184 = floor(4591*6144/2^8) */
! 711: /* f1 = (1/24)c1 + (1/6144)c0 - (1/6144)f0 */
! 712: /* claim: 2^19 f1 < x < 2^19(f1+1) */
! 713: /* where x = 21845(c1+2) + 85 c0 */
! 714: /* proof: x - 2^19 f1 = 43690 - (1/3)c1 - (1/3)c0 + 2^19 [0,0.75] */
! 715: /* at least 43690 - (1/3)110184 - (1/3)255 > 0 */
! 716: /* at most 43690 + 2^19 0.75 < 2^19 */
! 717: f1 = (21845*(c1+2) + 85*c0) >> 19;
! 718:
! 719: c1 -= (f1 * 3) << 3;
! 720: c0 += c1 << 8;
! 721: f0 = c0;
! 722:
! 723: *f++ = modq_freeze(f0 + q - qshift);
! 724: *f++ = modq_freeze(f1 + q - qshift);
! 725: *f++ = modq_freeze(f2 + q - qshift);
! 726: *f++ = modq_freeze(f3 + q - qshift);
! 727: *f++ = modq_freeze(f4 + q - qshift);
! 728: }
! 729:
! 730: c0 = *c++;
! 731: c1 = *c++;
! 732: c0 += c1 << 8;
! 733: *f++ = modq_freeze(c0 + q - qshift);
! 734: }
! 735:
! 736: /* from supercop-20181216/crypto_kem/sntrup4591761/ref/rq_mult.c */
! 737: /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */
! 738:
! 739:
! 740: static void rq_mult(modq *h,const modq *f,const small *g)
! 741: {
! 742: modq fg[p + p - 1];
! 743: modq result;
! 744: int i, j;
! 745:
! 746: for (i = 0;i < p;++i) {
! 747: result = 0;
! 748: for (j = 0;j <= i;++j)
! 749: result = modq_plusproduct(result,f[j],g[i - j]);
! 750: fg[i] = result;
! 751: }
! 752: for (i = p;i < p + p - 1;++i) {
! 753: result = 0;
! 754: for (j = i - p + 1;j < p;++j)
! 755: result = modq_plusproduct(result,f[j],g[i - j]);
! 756: fg[i] = result;
! 757: }
! 758:
! 759: for (i = p + p - 2;i >= p;--i) {
! 760: fg[i - p] = modq_sum(fg[i - p],fg[i]);
! 761: fg[i - p + 1] = modq_sum(fg[i - p + 1],fg[i]);
! 762: }
! 763:
! 764: for (i = 0;i < p;++i)
! 765: h[i] = fg[i];
! 766: }
! 767:
! 768: /* from supercop-20181216/crypto_kem/sntrup4591761/ref/rq_recip3.c */
! 769: /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */
! 770:
! 771:
! 772: /* caller must ensure that x-y does not overflow */
! 773: static int smaller_mask_rq_recip3(int x,int y)
! 774: {
! 775: return (x - y) >> 31;
! 776: }
! 777:
! 778: static void vectormodq_product(modq *z,int len,const modq *x,const modq c)
! 779: {
! 780: int i;
! 781: for (i = 0;i < len;++i) z[i] = modq_product(x[i],c);
! 782: }
! 783:
! 784: static void vectormodq_minusproduct(modq *z,int len,const modq *x,const modq *y,const modq c)
! 785: {
! 786: int i;
! 787: for (i = 0;i < len;++i) z[i] = modq_minusproduct(x[i],y[i],c);
! 788: }
! 789:
! 790: static void vectormodq_shift(modq *z,int len)
! 791: {
! 792: int i;
! 793: for (i = len - 1;i > 0;--i) z[i] = z[i - 1];
! 794: z[0] = 0;
! 795: }
! 796:
! 797: /*
! 798: r = (3s)^(-1) mod m, returning 0, if s is invertible mod m
! 799: or returning -1 if s is not invertible mod m
! 800: r,s are polys of degree <p
! 801: m is x^p-x-1
! 802: */
! 803: int rq_recip3(modq *r,const small *s)
! 804: {
! 805: const int loops = 2*p + 1;
! 806: int loop;
! 807: modq f[p + 1];
! 808: modq g[p + 1];
! 809: modq u[loops + 1];
! 810: modq v[loops + 1];
! 811: modq c;
! 812: int i;
! 813: int d = p;
! 814: int e = p;
! 815: int swapmask;
! 816:
! 817: for (i = 2;i < p;++i) f[i] = 0;
! 818: f[0] = -1;
! 819: f[1] = -1;
! 820: f[p] = 1;
! 821: /* generalization: can initialize f to any polynomial m */
! 822: /* requirements: m has degree exactly p, nonzero constant coefficient */
! 823:
! 824: for (i = 0;i < p;++i) g[i] = 3 * s[i];
! 825: g[p] = 0;
! 826:
! 827: for (i = 0;i <= loops;++i) u[i] = 0;
! 828:
! 829: v[0] = 1;
! 830: for (i = 1;i <= loops;++i) v[i] = 0;
! 831:
! 832: loop = 0;
! 833: for (;;) {
! 834: /* e == -1 or d + e + loop <= 2*p */
! 835:
! 836: /* f has degree p: i.e., f[p]!=0 */
! 837: /* f[i]==0 for i < p-d */
! 838:
! 839: /* g has degree <=p (so it fits in p+1 coefficients) */
! 840: /* g[i]==0 for i < p-e */
! 841:
! 842: /* u has degree <=loop (so it fits in loop+1 coefficients) */
! 843: /* u[i]==0 for i < p-d */
! 844: /* if invertible: u[i]==0 for i < loop-p (so can look at just p+1 coefficients) */
! 845:
! 846: /* v has degree <=loop (so it fits in loop+1 coefficients) */
! 847: /* v[i]==0 for i < p-e */
! 848: /* v[i]==0 for i < loop-p (so can look at just p+1 coefficients) */
! 849:
! 850: if (loop >= loops) break;
! 851:
! 852: c = modq_quotient(g[p],f[p]);
! 853:
! 854: vectormodq_minusproduct(g,p + 1,g,f,c);
! 855: vectormodq_shift(g,p + 1);
! 856:
! 857: #ifdef SIMPLER
! 858: vectormodq_minusproduct(v,loops + 1,v,u,c);
! 859: vectormodq_shift(v,loops + 1);
! 860: #else
! 861: if (loop < p) {
! 862: vectormodq_minusproduct(v,loop + 1,v,u,c);
! 863: vectormodq_shift(v,loop + 2);
! 864: } else {
! 865: vectormodq_minusproduct(v + loop - p,p + 1,v + loop - p,u + loop - p,c);
! 866: vectormodq_shift(v + loop - p,p + 2);
! 867: }
! 868: #endif
! 869:
! 870: e -= 1;
! 871:
! 872: ++loop;
! 873:
! 874: swapmask = smaller_mask_rq_recip3(e,d) & modq_nonzero_mask(g[p]);
! 875: swap(&e,&d,sizeof e,swapmask);
! 876: swap(f,g,(p + 1) * sizeof(modq),swapmask);
! 877:
! 878: #ifdef SIMPLER
! 879: swap(u,v,(loops + 1) * sizeof(modq),swapmask);
! 880: #else
! 881: if (loop < p) {
! 882: swap(u,v,(loop + 1) * sizeof(modq),swapmask);
! 883: } else {
! 884: swap(u + loop - p,v + loop - p,(p + 1) * sizeof(modq),swapmask);
! 885: }
! 886: #endif
! 887: }
! 888:
! 889: c = modq_reciprocal(f[p]);
! 890: vectormodq_product(r,p,u + p,c);
! 891: return smaller_mask_rq_recip3(0,d);
! 892: }
! 893:
! 894: /* from supercop-20181216/crypto_kem/sntrup4591761/ref/rq_round3.c */
! 895: /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */
! 896:
! 897:
! 898: static void rq_round3(modq *h,const modq *f)
! 899: {
! 900: int i;
! 901:
! 902: for (i = 0;i < p;++i)
! 903: h[i] = ((21846 * (f[i] + 2295) + 32768) >> 16) * 3 - 2295;
! 904: }
! 905:
! 906: /* from supercop-20181216/crypto_kem/sntrup4591761/ref/rq_rounded.c */
! 907: /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */
! 908:
! 909:
! 910: static void rq_encoderounded(unsigned char *c,const modq *f)
! 911: {
! 912: crypto_int32 f0, f1, f2;
! 913: int i;
! 914:
! 915: for (i = 0;i < p/3;++i) {
! 916: f0 = *f++ + qshift;
! 917: f1 = *f++ + qshift;
! 918: f2 = *f++ + qshift;
! 919: f0 = (21846 * f0) >> 16;
! 920: f1 = (21846 * f1) >> 16;
! 921: f2 = (21846 * f2) >> 16;
! 922: /* now want f0 + f1*1536 + f2*1536^2 as a 32-bit integer */
! 923: f2 *= 3;
! 924: f1 += f2 << 9;
! 925: f1 *= 3;
! 926: f0 += f1 << 9;
! 927: *c++ = f0; f0 >>= 8;
! 928: *c++ = f0; f0 >>= 8;
! 929: *c++ = f0; f0 >>= 8;
! 930: *c++ = f0;
! 931: }
! 932: /* XXX: using p mod 3 = 2 */
! 933: f0 = *f++ + qshift;
! 934: f1 = *f++ + qshift;
! 935: f0 = (21846 * f0) >> 16;
! 936: f1 = (21846 * f1) >> 16;
! 937: f1 *= 3;
! 938: f0 += f1 << 9;
! 939: *c++ = f0; f0 >>= 8;
! 940: *c++ = f0; f0 >>= 8;
! 941: *c++ = f0;
! 942: }
! 943:
! 944: static void rq_decoderounded(modq *f,const unsigned char *c)
! 945: {
! 946: crypto_uint32 c0, c1, c2, c3;
! 947: crypto_uint32 f0, f1, f2;
! 948: int i;
! 949:
! 950: for (i = 0;i < p/3;++i) {
! 951: c0 = *c++;
! 952: c1 = *c++;
! 953: c2 = *c++;
! 954: c3 = *c++;
! 955:
! 956: /* f0 + f1*1536 + f2*1536^2 */
! 957: /* = c0 + c1*256 + c2*256^2 + c3*256^3 */
! 958: /* with each f between 0 and 1530 */
! 959:
! 960: /* f2 = (64/9)c3 + (1/36)c2 + (1/9216)c1 + (1/2359296)c0 - [0,0.99675] */
! 961: /* claim: 2^21 f2 < x < 2^21(f2+1) */
! 962: /* where x = 14913081*c3 + 58254*c2 + 228*(c1+2) */
! 963: /* proof: x - 2^21 f2 = 456 - (8/9)c0 + (4/9)c1 - (2/9)c2 + (1/9)c3 + 2^21 [0,0.99675] */
! 964: /* at least 456 - (8/9)255 - (2/9)255 > 0 */
! 965: /* at most 456 + (4/9)255 + (1/9)255 + 2^21 0.99675 < 2^21 */
! 966: f2 = (14913081*c3 + 58254*c2 + 228*(c1+2)) >> 21;
! 967:
! 968: c2 += c3 << 8;
! 969: c2 -= (f2 * 9) << 2;
! 970: /* f0 + f1*1536 */
! 971: /* = c0 + c1*256 + c2*256^2 */
! 972: /* c2 <= 35 = floor((1530+1530*1536)/256^2) */
! 973: /* f1 = (128/3)c2 + (1/6)c1 + (1/1536)c0 - (1/1536)f0 */
! 974: /* claim: 2^21 f1 < x < 2^21(f1+1) */
! 975: /* where x = 89478485*c2 + 349525*c1 + 1365*(c0+1) */
! 976: /* proof: x - 2^21 f1 = 1365 - (1/3)c2 - (1/3)c1 - (1/3)c0 + (4096/3)f0 */
! 977: /* at least 1365 - (1/3)35 - (1/3)255 - (1/3)255 > 0 */
! 978: /* at most 1365 + (4096/3)1530 < 2^21 */
! 979: f1 = (89478485*c2 + 349525*c1 + 1365*(c0+1)) >> 21;
! 980:
! 981: c1 += c2 << 8;
! 982: c1 -= (f1 * 3) << 1;
! 983:
! 984: c0 += c1 << 8;
! 985: f0 = c0;
! 986:
! 987: *f++ = modq_freeze(f0 * 3 + q - qshift);
! 988: *f++ = modq_freeze(f1 * 3 + q - qshift);
! 989: *f++ = modq_freeze(f2 * 3 + q - qshift);
! 990: }
! 991:
! 992: c0 = *c++;
! 993: c1 = *c++;
! 994: c2 = *c++;
! 995:
! 996: f1 = (89478485*c2 + 349525*c1 + 1365*(c0+1)) >> 21;
! 997:
! 998: c1 += c2 << 8;
! 999: c1 -= (f1 * 3) << 1;
! 1000:
! 1001: c0 += c1 << 8;
! 1002: f0 = c0;
! 1003:
! 1004: *f++ = modq_freeze(f0 * 3 + q - qshift);
! 1005: *f++ = modq_freeze(f1 * 3 + q - qshift);
! 1006: }
! 1007:
! 1008: /* from supercop-20181216/crypto_kem/sntrup4591761/ref/small.c */
! 1009: /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */
! 1010:
! 1011:
! 1012: /* XXX: these functions rely on p mod 4 = 1 */
! 1013:
! 1014: /* all coefficients in -1, 0, 1 */
! 1015: static void small_encode(unsigned char *c,const small *f)
! 1016: {
! 1017: small c0;
! 1018: int i;
! 1019:
! 1020: for (i = 0;i < p/4;++i) {
! 1021: c0 = *f++ + 1;
! 1022: c0 += (*f++ + 1) << 2;
! 1023: c0 += (*f++ + 1) << 4;
! 1024: c0 += (*f++ + 1) << 6;
! 1025: *c++ = c0;
! 1026: }
! 1027: c0 = *f++ + 1;
! 1028: *c++ = c0;
! 1029: }
! 1030:
! 1031: static void small_decode(small *f,const unsigned char *c)
! 1032: {
! 1033: unsigned char c0;
! 1034: int i;
! 1035:
! 1036: for (i = 0;i < p/4;++i) {
! 1037: c0 = *c++;
! 1038: *f++ = ((small) (c0 & 3)) - 1; c0 >>= 2;
! 1039: *f++ = ((small) (c0 & 3)) - 1; c0 >>= 2;
! 1040: *f++ = ((small) (c0 & 3)) - 1; c0 >>= 2;
! 1041: *f++ = ((small) (c0 & 3)) - 1;
! 1042: }
! 1043: c0 = *c++;
! 1044: *f++ = ((small) (c0 & 3)) - 1;
! 1045: }
! 1046:
! 1047: /* from supercop-20181216/crypto_kem/sntrup4591761/ref/swap.c */
! 1048: /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */
! 1049:
! 1050:
! 1051: static void swap(void *x,void *y,int bytes,int mask)
! 1052: {
! 1053: int i;
! 1054: char xi, yi, c, t;
! 1055:
! 1056: c = mask;
! 1057:
! 1058: for (i = 0;i < bytes;++i) {
! 1059: xi = i[(char *) x];
! 1060: yi = i[(char *) y];
! 1061: t = c & (xi ^ yi);
! 1062: xi ^= t;
! 1063: yi ^= t;
! 1064: i[(char *) x] = xi;
! 1065: i[(char *) y] = yi;
! 1066: }
! 1067: }
! 1068:
![[BACK]](/icons/back.gif){kind=icon}
Return to sntrup4591761.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / ssh