Annotation of src/usr.bin/ssh/sntrup761.c, Revision 1.4
1.4 ! dtucker 1: /* $OpenBSD: $ */
1.1 djm 2:
3: /*
4: * Public Domain, Authors:
5: * - Daniel J. Bernstein
6: * - Chitchanok Chuengsatiansup
7: * - Tanja Lange
8: * - Christine van Vredendaal
9: */
10:
11: #include <string.h>
12: #include "crypto_api.h"
13:
14: #define CRYPTO_NAMESPACE(s) s
1.4 ! dtucker 15:
! 16: /* from supercop-20201130/crypto_sort/int32/portable4/int32_minmax.inc */
! 17: #define int32_MINMAX(a,b) \
! 18: do { \
! 19: int64_t ab = (int64_t)b ^ (int64_t)a; \
! 20: int64_t c = (int64_t)b - (int64_t)a; \
! 21: c ^= ab & (c ^ b); \
! 22: c >>= 31; \
! 23: c &= ab; \
! 24: a ^= c; \
! 25: b ^= c; \
! 26: } while(0)
1.1 djm 27:
28: /* from supercop-20201130/crypto_sort/int32/portable4/sort.c */
29: #define int32 crypto_int32
30:
31:
32: static void crypto_sort_int32(void *array,long long n)
33: {
34: long long top,p,q,r,i,j;
35: int32 *x = array;
36:
37: if (n < 2) return;
38: top = 1;
39: while (top < n - top) top += top;
40:
41: for (p = top;p >= 1;p >>= 1) {
42: i = 0;
43: while (i + 2 * p <= n) {
44: for (j = i;j < i + p;++j)
45: int32_MINMAX(x[j],x[j+p]);
46: i += 2 * p;
47: }
48: for (j = i;j < n - p;++j)
49: int32_MINMAX(x[j],x[j+p]);
50:
51: i = 0;
52: j = 0;
53: for (q = top;q > p;q >>= 1) {
54: if (j != i) for (;;) {
55: if (j == n - q) goto done;
56: int32 a = x[j + p];
57: for (r = q;r > p;r >>= 1)
58: int32_MINMAX(a,x[j + r]);
59: x[j + p] = a;
60: ++j;
61: if (j == i + p) {
62: i += 2 * p;
63: break;
64: }
65: }
66: while (i + p <= n - q) {
67: for (j = i;j < i + p;++j) {
68: int32 a = x[j + p];
69: for (r = q;r > p;r >>= 1)
70: int32_MINMAX(a,x[j+r]);
71: x[j + p] = a;
72: }
73: i += 2 * p;
74: }
75: /* now i + p > n - q */
76: j = i;
77: while (j < n - q) {
78: int32 a = x[j + p];
79: for (r = q;r > p;r >>= 1)
80: int32_MINMAX(a,x[j+r]);
81: x[j + p] = a;
82: ++j;
83: }
84:
85: done: ;
86: }
87: }
88: }
89:
90: /* from supercop-20201130/crypto_sort/uint32/useint32/sort.c */
91:
92: /* can save time by vectorizing xor loops */
93: /* can save time by integrating xor loops with int32_sort */
94:
95: static void crypto_sort_uint32(void *array,long long n)
96: {
97: crypto_uint32 *x = array;
98: long long j;
99: for (j = 0;j < n;++j) x[j] ^= 0x80000000;
100: crypto_sort_int32(array,n);
101: for (j = 0;j < n;++j) x[j] ^= 0x80000000;
102: }
103:
104: /* from supercop-20201130/crypto_kem/sntrup761/ref/uint64.h */
105: #ifndef UINT64_H
106: #define UINT64_H
107:
108:
109: typedef uint64_t uint64;
110:
111: #endif
112:
113: /* from supercop-20201130/crypto_kem/sntrup761/ref/uint16.h */
114: #ifndef UINT16_H
115: #define UINT16_H
116:
117: typedef uint16_t uint16;
118:
119: #endif
120:
121: /* from supercop-20201130/crypto_kem/sntrup761/ref/uint32.h */
122: #ifndef UINT32_H
123: #define UINT32_H
124:
125: #define uint32_div_uint14 CRYPTO_NAMESPACE(uint32_div_uint14)
126: #define uint32_mod_uint14 CRYPTO_NAMESPACE(uint32_mod_uint14)
127: #define uint32_divmod_uint14 CRYPTO_NAMESPACE(uint32_divmod_uint14)
128:
129:
130: typedef uint32_t uint32;
131:
132: /*
133: assuming 1 <= m < 16384:
134: q = uint32_div_uint14(x,m) means q = x/m
135: r = uint32_mod_uint14(x,m) means r = x/m
136: uint32_moddiv_uint14(&q,&r,x,m) means q = x/m, r = x%m
137: */
138:
139: extern uint32 uint32_div_uint14(uint32,uint16);
140: extern uint16 uint32_mod_uint14(uint32,uint16);
141: static void uint32_divmod_uint14(uint32 *,uint16 *,uint32,uint16);
142:
143: #endif
144:
145: /* from supercop-20201130/crypto_kem/sntrup761/ref/int8.h */
146: #ifndef INT8_H
147: #define INT8_H
148:
149: typedef int8_t int8;
150:
151: #endif
152:
153: /* from supercop-20201130/crypto_kem/sntrup761/ref/int16.h */
154: #ifndef INT16_H
155: #define INT16_H
156:
157: typedef int16_t int16;
158:
159: #endif
160:
161: /* from supercop-20201130/crypto_kem/sntrup761/ref/int32.h */
162: #ifndef INT32_H
163: #define INT32_H
164:
165: #define int32_div_uint14 CRYPTO_NAMESPACE(int32_div_uint14)
166: #define int32_mod_uint14 CRYPTO_NAMESPACE(int32_mod_uint14)
167: #define int32_divmod_uint14 CRYPTO_NAMESPACE(int32_divmod_uint14)
168:
169:
170:
171: /*
172: assuming 1 <= m < 16384:
173: q = int32_div_uint14(x,m) means q = x/m
174: r = int32_mod_uint14(x,m) means r = x/m
175: int32_moddiv_uint14(&q,&r,x,m) means q = x/m, r = x%m
176: */
177:
178: extern int32 int32_div_uint14(int32,uint16);
179: extern uint16 int32_mod_uint14(int32,uint16);
180: static void int32_divmod_uint14(int32 *,uint16 *,int32,uint16);
181:
182: #endif
183:
184: /* from supercop-20201130/crypto_kem/sntrup761/ref/uint32.c */
185:
186: /*
187: CPU division instruction typically takes time depending on x.
188: This software is designed to take time independent of x.
189: Time still varies depending on m; user must ensure that m is constant.
190: Time also varies on CPUs where multiplication is variable-time.
191: There could be more CPU issues.
192: There could also be compiler issues.
193: */
194:
195: static void uint32_divmod_uint14(uint32 *q,uint16 *r,uint32 x,uint16 m)
196: {
197: uint32 v = 0x80000000;
198: uint32 qpart;
199: uint32 mask;
200:
201: v /= m;
202:
203: /* caller guarantees m > 0 */
204: /* caller guarantees m < 16384 */
205: /* vm <= 2^31 <= vm+m-1 */
206: /* xvm <= 2^31 x <= xvm+x(m-1) */
207:
208: *q = 0;
209:
210: qpart = (x*(uint64)v)>>31;
211: /* 2^31 qpart <= xv <= 2^31 qpart + 2^31-1 */
212: /* 2^31 qpart m <= xvm <= 2^31 qpart m + (2^31-1)m */
213: /* 2^31 qpart m <= 2^31 x <= 2^31 qpart m + (2^31-1)m + x(m-1) */
214: /* 0 <= 2^31 newx <= (2^31-1)m + x(m-1) */
215: /* 0 <= newx <= (1-1/2^31)m + x(m-1)/2^31 */
216: /* 0 <= newx <= (1-1/2^31)(2^14-1) + (2^32-1)((2^14-1)-1)/2^31 */
217:
218: x -= qpart*m; *q += qpart;
219: /* x <= 49146 */
220:
221: qpart = (x*(uint64)v)>>31;
222: /* 0 <= newx <= (1-1/2^31)m + x(m-1)/2^31 */
223: /* 0 <= newx <= m + 49146(2^14-1)/2^31 */
224: /* 0 <= newx <= m + 0.4 */
225: /* 0 <= newx <= m */
226:
227: x -= qpart*m; *q += qpart;
228: /* x <= m */
229:
230: x -= m; *q += 1;
231: mask = -(x>>31);
232: x += mask&(uint32)m; *q += mask;
233: /* x < m */
234:
235: *r = x;
236: }
237:
238: uint32 uint32_div_uint14(uint32 x,uint16 m)
239: {
240: uint32 q;
241: uint16 r;
242: uint32_divmod_uint14(&q,&r,x,m);
243: return q;
244: }
245:
246: uint16 uint32_mod_uint14(uint32 x,uint16 m)
247: {
248: uint32 q;
249: uint16 r;
250: uint32_divmod_uint14(&q,&r,x,m);
251: return r;
252: }
253:
254: /* from supercop-20201130/crypto_kem/sntrup761/ref/int32.c */
255:
256: static void int32_divmod_uint14(int32 *q,uint16 *r,int32 x,uint16 m)
257: {
258: uint32 uq,uq2;
259: uint16 ur,ur2;
260: uint32 mask;
261:
262: uint32_divmod_uint14(&uq,&ur,0x80000000+(uint32)x,m);
263: uint32_divmod_uint14(&uq2,&ur2,0x80000000,m);
264: ur -= ur2; uq -= uq2;
265: mask = -(uint32)(ur>>15);
266: ur += mask&m; uq += mask;
267: *r = ur; *q = uq;
268: }
269:
270: int32 int32_div_uint14(int32 x,uint16 m)
271: {
272: int32 q;
273: uint16 r;
274: int32_divmod_uint14(&q,&r,x,m);
275: return q;
276: }
277:
278: uint16 int32_mod_uint14(int32 x,uint16 m)
279: {
280: int32 q;
281: uint16 r;
282: int32_divmod_uint14(&q,&r,x,m);
283: return r;
284: }
285:
286: /* from supercop-20201130/crypto_kem/sntrup761/ref/paramsmenu.h */
287: /* pick one of these three: */
288: #define SIZE761
289: #undef SIZE653
290: #undef SIZE857
291:
292: /* pick one of these two: */
293: #define SNTRUP /* Streamlined NTRU Prime */
294: #undef LPR /* NTRU LPRime */
295:
296: /* from supercop-20201130/crypto_kem/sntrup761/ref/params.h */
297: #ifndef params_H
298: #define params_H
299:
300: /* menu of parameter choices: */
301:
302:
303: /* what the menu means: */
304:
305: #if defined(SIZE761)
306: #define p 761
307: #define q 4591
308: #define Rounded_bytes 1007
309: #ifndef LPR
310: #define Rq_bytes 1158
311: #define w 286
312: #else
313: #define w 250
314: #define tau0 2156
315: #define tau1 114
316: #define tau2 2007
317: #define tau3 287
318: #endif
319:
320: #elif defined(SIZE653)
321: #define p 653
322: #define q 4621
323: #define Rounded_bytes 865
324: #ifndef LPR
325: #define Rq_bytes 994
326: #define w 288
327: #else
328: #define w 252
329: #define tau0 2175
330: #define tau1 113
331: #define tau2 2031
332: #define tau3 290
333: #endif
334:
335: #elif defined(SIZE857)
336: #define p 857
337: #define q 5167
338: #define Rounded_bytes 1152
339: #ifndef LPR
340: #define Rq_bytes 1322
341: #define w 322
342: #else
343: #define w 281
344: #define tau0 2433
345: #define tau1 101
346: #define tau2 2265
347: #define tau3 324
348: #endif
349:
350: #else
351: #error "no parameter set defined"
352: #endif
353:
354: #ifdef LPR
355: #define I 256
356: #endif
357:
358: #endif
359:
360: /* from supercop-20201130/crypto_kem/sntrup761/ref/Decode.h */
361: #ifndef Decode_H
362: #define Decode_H
363:
364: #define Decode CRYPTO_NAMESPACE(Decode)
365:
366: /* Decode(R,s,M,len) */
367: /* assumes 0 < M[i] < 16384 */
368: /* produces 0 <= R[i] < M[i] */
369: static void Decode(uint16 *,const unsigned char *,const uint16 *,long long);
370:
371: #endif
372:
373: /* from supercop-20201130/crypto_kem/sntrup761/ref/Decode.c */
374:
375: static void Decode(uint16 *out,const unsigned char *S,const uint16 *M,long long len)
376: {
377: if (len == 1) {
378: if (M[0] == 1)
379: *out = 0;
380: else if (M[0] <= 256)
381: *out = uint32_mod_uint14(S[0],M[0]);
382: else
383: *out = uint32_mod_uint14(S[0]+(((uint16)S[1])<<8),M[0]);
384: }
385: if (len > 1) {
386: uint16 R2[(len+1)/2];
387: uint16 M2[(len+1)/2];
388: uint16 bottomr[len/2];
389: uint32 bottomt[len/2];
390: long long i;
391: for (i = 0;i < len-1;i += 2) {
392: uint32 m = M[i]*(uint32) M[i+1];
393: if (m > 256*16383) {
394: bottomt[i/2] = 256*256;
395: bottomr[i/2] = S[0]+256*S[1];
396: S += 2;
397: M2[i/2] = (((m+255)>>8)+255)>>8;
398: } else if (m >= 16384) {
399: bottomt[i/2] = 256;
400: bottomr[i/2] = S[0];
401: S += 1;
402: M2[i/2] = (m+255)>>8;
403: } else {
404: bottomt[i/2] = 1;
405: bottomr[i/2] = 0;
406: M2[i/2] = m;
407: }
408: }
409: if (i < len)
410: M2[i/2] = M[i];
411: Decode(R2,S,M2,(len+1)/2);
412: for (i = 0;i < len-1;i += 2) {
413: uint32 r = bottomr[i/2];
414: uint32 r1;
415: uint16 r0;
416: r += bottomt[i/2]*R2[i/2];
417: uint32_divmod_uint14(&r1,&r0,r,M[i]);
418: r1 = uint32_mod_uint14(r1,M[i+1]); /* only needed for invalid inputs */
419: *out++ = r0;
420: *out++ = r1;
421: }
422: if (i < len)
423: *out++ = R2[i/2];
424: }
425: }
426:
427: /* from supercop-20201130/crypto_kem/sntrup761/ref/Encode.h */
428: #ifndef Encode_H
429: #define Encode_H
430:
431: #define Encode CRYPTO_NAMESPACE(Encode)
432:
433: /* Encode(s,R,M,len) */
434: /* assumes 0 <= R[i] < M[i] < 16384 */
435: static void Encode(unsigned char *,const uint16 *,const uint16 *,long long);
436:
437: #endif
438:
439: /* from supercop-20201130/crypto_kem/sntrup761/ref/Encode.c */
440:
441: /* 0 <= R[i] < M[i] < 16384 */
442: static void Encode(unsigned char *out,const uint16 *R,const uint16 *M,long long len)
443: {
444: if (len == 1) {
445: uint16 r = R[0];
446: uint16 m = M[0];
447: while (m > 1) {
448: *out++ = r;
449: r >>= 8;
450: m = (m+255)>>8;
451: }
452: }
453: if (len > 1) {
454: uint16 R2[(len+1)/2];
455: uint16 M2[(len+1)/2];
456: long long i;
457: for (i = 0;i < len-1;i += 2) {
458: uint32 m0 = M[i];
459: uint32 r = R[i]+R[i+1]*m0;
460: uint32 m = M[i+1]*m0;
461: while (m >= 16384) {
462: *out++ = r;
463: r >>= 8;
464: m = (m+255)>>8;
465: }
466: R2[i/2] = r;
467: M2[i/2] = m;
468: }
469: if (i < len) {
470: R2[i/2] = R[i];
471: M2[i/2] = M[i];
472: }
473: Encode(out,R2,M2,(len+1)/2);
474: }
475: }
476:
477: /* from supercop-20201130/crypto_kem/sntrup761/ref/kem.c */
478:
479: #ifdef LPR
480: #endif
481:
482:
483: /* ----- masks */
484:
485: #ifndef LPR
486:
487: /* return -1 if x!=0; else return 0 */
488: static int int16_nonzero_mask(int16 x)
489: {
490: uint16 u = x; /* 0, else 1...65535 */
491: uint32 v = u; /* 0, else 1...65535 */
492: v = -v; /* 0, else 2^32-65535...2^32-1 */
493: v >>= 31; /* 0, else 1 */
494: return -v; /* 0, else -1 */
495: }
496:
497: #endif
498:
499: /* return -1 if x<0; otherwise return 0 */
500: static int int16_negative_mask(int16 x)
501: {
502: uint16 u = x;
503: u >>= 15;
504: return -(int) u;
505: /* alternative with gcc -fwrapv: */
506: /* x>>15 compiles to CPU's arithmetic right shift */
507: }
508:
509: /* ----- arithmetic mod 3 */
510:
511: typedef int8 small;
512:
513: /* F3 is always represented as -1,0,1 */
514: /* so ZZ_fromF3 is a no-op */
515:
516: /* x must not be close to top int16 */
517: static small F3_freeze(int16 x)
518: {
519: return int32_mod_uint14(x+1,3)-1;
520: }
521:
522: /* ----- arithmetic mod q */
523:
524: #define q12 ((q-1)/2)
525: typedef int16 Fq;
526: /* always represented as -q12...q12 */
527: /* so ZZ_fromFq is a no-op */
528:
529: /* x must not be close to top int32 */
530: static Fq Fq_freeze(int32 x)
531: {
532: return int32_mod_uint14(x+q12,q)-q12;
533: }
534:
535: #ifndef LPR
536:
537: static Fq Fq_recip(Fq a1)
538: {
539: int i = 1;
540: Fq ai = a1;
541:
542: while (i < q-2) {
543: ai = Fq_freeze(a1*(int32)ai);
544: i += 1;
545: }
546: return ai;
547: }
548:
549: #endif
550:
551: /* ----- Top and Right */
552:
553: #ifdef LPR
554: #define tau 16
555:
556: static int8 Top(Fq C)
557: {
558: return (tau1*(int32)(C+tau0)+16384)>>15;
559: }
560:
561: static Fq Right(int8 T)
562: {
563: return Fq_freeze(tau3*(int32)T-tau2);
564: }
565: #endif
566:
567: /* ----- small polynomials */
568:
569: #ifndef LPR
570:
571: /* 0 if Weightw_is(r), else -1 */
572: static int Weightw_mask(small *r)
573: {
574: int weight = 0;
575: int i;
576:
577: for (i = 0;i < p;++i) weight += r[i]&1;
578: return int16_nonzero_mask(weight-w);
579: }
580:
581: /* R3_fromR(R_fromRq(r)) */
582: static void R3_fromRq(small *out,const Fq *r)
583: {
584: int i;
585: for (i = 0;i < p;++i) out[i] = F3_freeze(r[i]);
586: }
587:
588: /* h = f*g in the ring R3 */
589: static void R3_mult(small *h,const small *f,const small *g)
590: {
591: small fg[p+p-1];
592: small result;
593: int i,j;
594:
595: for (i = 0;i < p;++i) {
596: result = 0;
597: for (j = 0;j <= i;++j) result = F3_freeze(result+f[j]*g[i-j]);
598: fg[i] = result;
599: }
600: for (i = p;i < p+p-1;++i) {
601: result = 0;
602: for (j = i-p+1;j < p;++j) result = F3_freeze(result+f[j]*g[i-j]);
603: fg[i] = result;
604: }
605:
606: for (i = p+p-2;i >= p;--i) {
607: fg[i-p] = F3_freeze(fg[i-p]+fg[i]);
608: fg[i-p+1] = F3_freeze(fg[i-p+1]+fg[i]);
609: }
610:
611: for (i = 0;i < p;++i) h[i] = fg[i];
612: }
613:
614: /* returns 0 if recip succeeded; else -1 */
615: static int R3_recip(small *out,const small *in)
616: {
617: small f[p+1],g[p+1],v[p+1],r[p+1];
618: int i,loop,delta;
619: int sign,swap,t;
620:
621: for (i = 0;i < p+1;++i) v[i] = 0;
622: for (i = 0;i < p+1;++i) r[i] = 0;
623: r[0] = 1;
624: for (i = 0;i < p;++i) f[i] = 0;
625: f[0] = 1; f[p-1] = f[p] = -1;
626: for (i = 0;i < p;++i) g[p-1-i] = in[i];
627: g[p] = 0;
628:
629: delta = 1;
630:
631: for (loop = 0;loop < 2*p-1;++loop) {
632: for (i = p;i > 0;--i) v[i] = v[i-1];
633: v[0] = 0;
634:
635: sign = -g[0]*f[0];
636: swap = int16_negative_mask(-delta) & int16_nonzero_mask(g[0]);
637: delta ^= swap&(delta^-delta);
638: delta += 1;
639:
640: for (i = 0;i < p+1;++i) {
641: t = swap&(f[i]^g[i]); f[i] ^= t; g[i] ^= t;
642: t = swap&(v[i]^r[i]); v[i] ^= t; r[i] ^= t;
643: }
644:
645: for (i = 0;i < p+1;++i) g[i] = F3_freeze(g[i]+sign*f[i]);
646: for (i = 0;i < p+1;++i) r[i] = F3_freeze(r[i]+sign*v[i]);
647:
648: for (i = 0;i < p;++i) g[i] = g[i+1];
649: g[p] = 0;
650: }
651:
652: sign = f[0];
653: for (i = 0;i < p;++i) out[i] = sign*v[p-1-i];
654:
655: return int16_nonzero_mask(delta);
656: }
657:
658: #endif
659:
660: /* ----- polynomials mod q */
661:
662: /* h = f*g in the ring Rq */
663: static void Rq_mult_small(Fq *h,const Fq *f,const small *g)
664: {
665: Fq fg[p+p-1];
666: Fq result;
667: int i,j;
668:
669: for (i = 0;i < p;++i) {
670: result = 0;
671: for (j = 0;j <= i;++j) result = Fq_freeze(result+f[j]*(int32)g[i-j]);
672: fg[i] = result;
673: }
674: for (i = p;i < p+p-1;++i) {
675: result = 0;
676: for (j = i-p+1;j < p;++j) result = Fq_freeze(result+f[j]*(int32)g[i-j]);
677: fg[i] = result;
678: }
679:
680: for (i = p+p-2;i >= p;--i) {
681: fg[i-p] = Fq_freeze(fg[i-p]+fg[i]);
682: fg[i-p+1] = Fq_freeze(fg[i-p+1]+fg[i]);
683: }
684:
685: for (i = 0;i < p;++i) h[i] = fg[i];
686: }
687:
688: #ifndef LPR
689:
690: /* h = 3f in Rq */
691: static void Rq_mult3(Fq *h,const Fq *f)
692: {
693: int i;
694:
695: for (i = 0;i < p;++i) h[i] = Fq_freeze(3*f[i]);
696: }
697:
698: /* out = 1/(3*in) in Rq */
699: /* returns 0 if recip succeeded; else -1 */
700: static int Rq_recip3(Fq *out,const small *in)
701: {
702: Fq f[p+1],g[p+1],v[p+1],r[p+1];
703: int i,loop,delta;
704: int swap,t;
705: int32 f0,g0;
706: Fq scale;
707:
708: for (i = 0;i < p+1;++i) v[i] = 0;
709: for (i = 0;i < p+1;++i) r[i] = 0;
710: r[0] = Fq_recip(3);
711: for (i = 0;i < p;++i) f[i] = 0;
712: f[0] = 1; f[p-1] = f[p] = -1;
713: for (i = 0;i < p;++i) g[p-1-i] = in[i];
714: g[p] = 0;
715:
716: delta = 1;
717:
718: for (loop = 0;loop < 2*p-1;++loop) {
719: for (i = p;i > 0;--i) v[i] = v[i-1];
720: v[0] = 0;
721:
722: swap = int16_negative_mask(-delta) & int16_nonzero_mask(g[0]);
723: delta ^= swap&(delta^-delta);
724: delta += 1;
725:
726: for (i = 0;i < p+1;++i) {
727: t = swap&(f[i]^g[i]); f[i] ^= t; g[i] ^= t;
728: t = swap&(v[i]^r[i]); v[i] ^= t; r[i] ^= t;
729: }
730:
731: f0 = f[0];
732: g0 = g[0];
733: for (i = 0;i < p+1;++i) g[i] = Fq_freeze(f0*g[i]-g0*f[i]);
734: for (i = 0;i < p+1;++i) r[i] = Fq_freeze(f0*r[i]-g0*v[i]);
735:
736: for (i = 0;i < p;++i) g[i] = g[i+1];
737: g[p] = 0;
738: }
739:
740: scale = Fq_recip(f[0]);
741: for (i = 0;i < p;++i) out[i] = Fq_freeze(scale*(int32)v[p-1-i]);
742:
743: return int16_nonzero_mask(delta);
744: }
745:
746: #endif
747:
748: /* ----- rounded polynomials mod q */
749:
750: static void Round(Fq *out,const Fq *a)
751: {
752: int i;
753: for (i = 0;i < p;++i) out[i] = a[i]-F3_freeze(a[i]);
754: }
755:
756: /* ----- sorting to generate short polynomial */
757:
758: static void Short_fromlist(small *out,const uint32 *in)
759: {
760: uint32 L[p];
761: int i;
762:
763: for (i = 0;i < w;++i) L[i] = in[i]&(uint32)-2;
764: for (i = w;i < p;++i) L[i] = (in[i]&(uint32)-3)|1;
765: crypto_sort_uint32(L,p);
766: for (i = 0;i < p;++i) out[i] = (L[i]&3)-1;
767: }
768:
769: /* ----- underlying hash function */
770:
771: #define Hash_bytes 32
772:
773: /* e.g., b = 0 means out = Hash0(in) */
774: static void Hash_prefix(unsigned char *out,int b,const unsigned char *in,int inlen)
775: {
776: unsigned char x[inlen+1];
777: unsigned char h[64];
778: int i;
779:
780: x[0] = b;
781: for (i = 0;i < inlen;++i) x[i+1] = in[i];
782: crypto_hash_sha512(h,x,inlen+1);
783: for (i = 0;i < 32;++i) out[i] = h[i];
784: }
785:
786: /* ----- higher-level randomness */
787:
788: static uint32 urandom32(void)
789: {
790: unsigned char c[4];
791: uint32 out[4];
792:
793: randombytes(c,4);
794: out[0] = (uint32)c[0];
795: out[1] = ((uint32)c[1])<<8;
796: out[2] = ((uint32)c[2])<<16;
797: out[3] = ((uint32)c[3])<<24;
798: return out[0]+out[1]+out[2]+out[3];
799: }
800:
801: static void Short_random(small *out)
802: {
803: uint32 L[p];
804: int i;
805:
806: for (i = 0;i < p;++i) L[i] = urandom32();
807: Short_fromlist(out,L);
808: }
809:
810: #ifndef LPR
811:
812: static void Small_random(small *out)
813: {
814: int i;
815:
816: for (i = 0;i < p;++i) out[i] = (((urandom32()&0x3fffffff)*3)>>30)-1;
817: }
818:
819: #endif
820:
821: /* ----- Streamlined NTRU Prime Core */
822:
823: #ifndef LPR
824:
825: /* h,(f,ginv) = KeyGen() */
826: static void KeyGen(Fq *h,small *f,small *ginv)
827: {
828: small g[p];
829: Fq finv[p];
830:
831: for (;;) {
832: Small_random(g);
833: if (R3_recip(ginv,g) == 0) break;
834: }
835: Short_random(f);
836: Rq_recip3(finv,f); /* always works */
837: Rq_mult_small(h,finv,g);
838: }
839:
840: /* c = Encrypt(r,h) */
841: static void Encrypt(Fq *c,const small *r,const Fq *h)
842: {
843: Fq hr[p];
844:
845: Rq_mult_small(hr,h,r);
846: Round(c,hr);
847: }
848:
849: /* r = Decrypt(c,(f,ginv)) */
850: static void Decrypt(small *r,const Fq *c,const small *f,const small *ginv)
851: {
852: Fq cf[p];
853: Fq cf3[p];
854: small e[p];
855: small ev[p];
856: int mask;
857: int i;
858:
859: Rq_mult_small(cf,c,f);
860: Rq_mult3(cf3,cf);
861: R3_fromRq(e,cf3);
862: R3_mult(ev,e,ginv);
863:
864: mask = Weightw_mask(ev); /* 0 if weight w, else -1 */
865: for (i = 0;i < w;++i) r[i] = ((ev[i]^1)&~mask)^1;
866: for (i = w;i < p;++i) r[i] = ev[i]&~mask;
867: }
868:
869: #endif
870:
871: /* ----- NTRU LPRime Core */
872:
873: #ifdef LPR
874:
875: /* (G,A),a = KeyGen(G); leaves G unchanged */
876: static void KeyGen(Fq *A,small *a,const Fq *G)
877: {
878: Fq aG[p];
879:
880: Short_random(a);
881: Rq_mult_small(aG,G,a);
882: Round(A,aG);
883: }
884:
885: /* B,T = Encrypt(r,(G,A),b) */
886: static void Encrypt(Fq *B,int8 *T,const int8 *r,const Fq *G,const Fq *A,const small *b)
887: {
888: Fq bG[p];
889: Fq bA[p];
890: int i;
891:
892: Rq_mult_small(bG,G,b);
893: Round(B,bG);
894: Rq_mult_small(bA,A,b);
895: for (i = 0;i < I;++i) T[i] = Top(Fq_freeze(bA[i]+r[i]*q12));
896: }
897:
898: /* r = Decrypt((B,T),a) */
899: static void Decrypt(int8 *r,const Fq *B,const int8 *T,const small *a)
900: {
901: Fq aB[p];
902: int i;
903:
904: Rq_mult_small(aB,B,a);
905: for (i = 0;i < I;++i)
906: r[i] = -int16_negative_mask(Fq_freeze(Right(T[i])-aB[i]+4*w+1));
907: }
908:
909: #endif
910:
911: /* ----- encoding I-bit inputs */
912:
913: #ifdef LPR
914:
915: #define Inputs_bytes (I/8)
916: typedef int8 Inputs[I]; /* passed by reference */
917:
918: static void Inputs_encode(unsigned char *s,const Inputs r)
919: {
920: int i;
921: for (i = 0;i < Inputs_bytes;++i) s[i] = 0;
922: for (i = 0;i < I;++i) s[i>>3] |= r[i]<<(i&7);
923: }
924:
925: #endif
926:
927: /* ----- Expand */
928:
929: #ifdef LPR
930:
931: static const unsigned char aes_nonce[16] = {0};
932:
933: static void Expand(uint32 *L,const unsigned char *k)
934: {
935: int i;
936: crypto_stream_aes256ctr((unsigned char *) L,4*p,aes_nonce,k);
937: for (i = 0;i < p;++i) {
938: uint32 L0 = ((unsigned char *) L)[4*i];
939: uint32 L1 = ((unsigned char *) L)[4*i+1];
940: uint32 L2 = ((unsigned char *) L)[4*i+2];
941: uint32 L3 = ((unsigned char *) L)[4*i+3];
942: L[i] = L0+(L1<<8)+(L2<<16)+(L3<<24);
943: }
944: }
945:
946: #endif
947:
948: /* ----- Seeds */
949:
950: #ifdef LPR
951:
952: #define Seeds_bytes 32
953:
954: static void Seeds_random(unsigned char *s)
955: {
956: randombytes(s,Seeds_bytes);
957: }
958:
959: #endif
960:
961: /* ----- Generator, HashShort */
962:
963: #ifdef LPR
964:
965: /* G = Generator(k) */
966: static void Generator(Fq *G,const unsigned char *k)
967: {
968: uint32 L[p];
969: int i;
970:
971: Expand(L,k);
972: for (i = 0;i < p;++i) G[i] = uint32_mod_uint14(L[i],q)-q12;
973: }
974:
975: /* out = HashShort(r) */
976: static void HashShort(small *out,const Inputs r)
977: {
978: unsigned char s[Inputs_bytes];
979: unsigned char h[Hash_bytes];
980: uint32 L[p];
981:
982: Inputs_encode(s,r);
983: Hash_prefix(h,5,s,sizeof s);
984: Expand(L,h);
985: Short_fromlist(out,L);
986: }
987:
988: #endif
989:
990: /* ----- NTRU LPRime Expand */
991:
992: #ifdef LPR
993:
994: /* (S,A),a = XKeyGen() */
995: static void XKeyGen(unsigned char *S,Fq *A,small *a)
996: {
997: Fq G[p];
998:
999: Seeds_random(S);
1000: Generator(G,S);
1001: KeyGen(A,a,G);
1002: }
1003:
1004: /* B,T = XEncrypt(r,(S,A)) */
1005: static void XEncrypt(Fq *B,int8 *T,const int8 *r,const unsigned char *S,const Fq *A)
1006: {
1007: Fq G[p];
1008: small b[p];
1009:
1010: Generator(G,S);
1011: HashShort(b,r);
1012: Encrypt(B,T,r,G,A,b);
1013: }
1014:
1015: #define XDecrypt Decrypt
1016:
1017: #endif
1018:
1019: /* ----- encoding small polynomials (including short polynomials) */
1020:
1021: #define Small_bytes ((p+3)/4)
1022:
1023: /* these are the only functions that rely on p mod 4 = 1 */
1024:
1025: static void Small_encode(unsigned char *s,const small *f)
1026: {
1027: small x;
1028: int i;
1029:
1030: for (i = 0;i < p/4;++i) {
1031: x = *f++ + 1;
1032: x += (*f++ + 1)<<2;
1033: x += (*f++ + 1)<<4;
1034: x += (*f++ + 1)<<6;
1035: *s++ = x;
1036: }
1037: x = *f++ + 1;
1038: *s++ = x;
1039: }
1040:
1041: static void Small_decode(small *f,const unsigned char *s)
1042: {
1043: unsigned char x;
1044: int i;
1045:
1046: for (i = 0;i < p/4;++i) {
1047: x = *s++;
1048: *f++ = ((small)(x&3))-1; x >>= 2;
1049: *f++ = ((small)(x&3))-1; x >>= 2;
1050: *f++ = ((small)(x&3))-1; x >>= 2;
1051: *f++ = ((small)(x&3))-1;
1052: }
1053: x = *s++;
1054: *f++ = ((small)(x&3))-1;
1055: }
1056:
1057: /* ----- encoding general polynomials */
1058:
1059: #ifndef LPR
1060:
1061: static void Rq_encode(unsigned char *s,const Fq *r)
1062: {
1063: uint16 R[p],M[p];
1064: int i;
1065:
1066: for (i = 0;i < p;++i) R[i] = r[i]+q12;
1067: for (i = 0;i < p;++i) M[i] = q;
1068: Encode(s,R,M,p);
1069: }
1070:
1071: static void Rq_decode(Fq *r,const unsigned char *s)
1072: {
1073: uint16 R[p],M[p];
1074: int i;
1075:
1076: for (i = 0;i < p;++i) M[i] = q;
1077: Decode(R,s,M,p);
1078: for (i = 0;i < p;++i) r[i] = ((Fq)R[i])-q12;
1079: }
1080:
1081: #endif
1082:
1083: /* ----- encoding rounded polynomials */
1084:
1085: static void Rounded_encode(unsigned char *s,const Fq *r)
1086: {
1087: uint16 R[p],M[p];
1088: int i;
1089:
1090: for (i = 0;i < p;++i) R[i] = ((r[i]+q12)*10923)>>15;
1091: for (i = 0;i < p;++i) M[i] = (q+2)/3;
1092: Encode(s,R,M,p);
1093: }
1094:
1095: static void Rounded_decode(Fq *r,const unsigned char *s)
1096: {
1097: uint16 R[p],M[p];
1098: int i;
1099:
1100: for (i = 0;i < p;++i) M[i] = (q+2)/3;
1101: Decode(R,s,M,p);
1102: for (i = 0;i < p;++i) r[i] = R[i]*3-q12;
1103: }
1104:
1105: /* ----- encoding top polynomials */
1106:
1107: #ifdef LPR
1108:
1109: #define Top_bytes (I/2)
1110:
1111: static void Top_encode(unsigned char *s,const int8 *T)
1112: {
1113: int i;
1114: for (i = 0;i < Top_bytes;++i)
1115: s[i] = T[2*i]+(T[2*i+1]<<4);
1116: }
1117:
1118: static void Top_decode(int8 *T,const unsigned char *s)
1119: {
1120: int i;
1121: for (i = 0;i < Top_bytes;++i) {
1122: T[2*i] = s[i]&15;
1123: T[2*i+1] = s[i]>>4;
1124: }
1125: }
1126:
1127: #endif
1128:
1129: /* ----- Streamlined NTRU Prime Core plus encoding */
1130:
1131: #ifndef LPR
1132:
1133: typedef small Inputs[p]; /* passed by reference */
1134: #define Inputs_random Short_random
1135: #define Inputs_encode Small_encode
1136: #define Inputs_bytes Small_bytes
1137:
1138: #define Ciphertexts_bytes Rounded_bytes
1139: #define SecretKeys_bytes (2*Small_bytes)
1140: #define PublicKeys_bytes Rq_bytes
1141:
1142: /* pk,sk = ZKeyGen() */
1143: static void ZKeyGen(unsigned char *pk,unsigned char *sk)
1144: {
1145: Fq h[p];
1146: small f[p],v[p];
1147:
1148: KeyGen(h,f,v);
1149: Rq_encode(pk,h);
1150: Small_encode(sk,f); sk += Small_bytes;
1151: Small_encode(sk,v);
1152: }
1153:
1154: /* C = ZEncrypt(r,pk) */
1155: static void ZEncrypt(unsigned char *C,const Inputs r,const unsigned char *pk)
1156: {
1157: Fq h[p];
1158: Fq c[p];
1159: Rq_decode(h,pk);
1160: Encrypt(c,r,h);
1161: Rounded_encode(C,c);
1162: }
1163:
1164: /* r = ZDecrypt(C,sk) */
1165: static void ZDecrypt(Inputs r,const unsigned char *C,const unsigned char *sk)
1166: {
1167: small f[p],v[p];
1168: Fq c[p];
1169:
1170: Small_decode(f,sk); sk += Small_bytes;
1171: Small_decode(v,sk);
1172: Rounded_decode(c,C);
1173: Decrypt(r,c,f,v);
1174: }
1175:
1176: #endif
1177:
1178: /* ----- NTRU LPRime Expand plus encoding */
1179:
1180: #ifdef LPR
1181:
1182: #define Ciphertexts_bytes (Rounded_bytes+Top_bytes)
1183: #define SecretKeys_bytes Small_bytes
1184: #define PublicKeys_bytes (Seeds_bytes+Rounded_bytes)
1185:
1186: static void Inputs_random(Inputs r)
1187: {
1188: unsigned char s[Inputs_bytes];
1189: int i;
1190:
1191: randombytes(s,sizeof s);
1192: for (i = 0;i < I;++i) r[i] = 1&(s[i>>3]>>(i&7));
1193: }
1194:
1195: /* pk,sk = ZKeyGen() */
1196: static void ZKeyGen(unsigned char *pk,unsigned char *sk)
1197: {
1198: Fq A[p];
1199: small a[p];
1200:
1201: XKeyGen(pk,A,a); pk += Seeds_bytes;
1202: Rounded_encode(pk,A);
1203: Small_encode(sk,a);
1204: }
1205:
1206: /* c = ZEncrypt(r,pk) */
1207: static void ZEncrypt(unsigned char *c,const Inputs r,const unsigned char *pk)
1208: {
1209: Fq A[p];
1210: Fq B[p];
1211: int8 T[I];
1212:
1213: Rounded_decode(A,pk+Seeds_bytes);
1214: XEncrypt(B,T,r,pk,A);
1215: Rounded_encode(c,B); c += Rounded_bytes;
1216: Top_encode(c,T);
1217: }
1218:
1219: /* r = ZDecrypt(C,sk) */
1220: static void ZDecrypt(Inputs r,const unsigned char *c,const unsigned char *sk)
1221: {
1222: small a[p];
1223: Fq B[p];
1224: int8 T[I];
1225:
1226: Small_decode(a,sk);
1227: Rounded_decode(B,c);
1228: Top_decode(T,c+Rounded_bytes);
1229: XDecrypt(r,B,T,a);
1230: }
1231:
1232: #endif
1233:
1234: /* ----- confirmation hash */
1235:
1236: #define Confirm_bytes 32
1237:
1238: /* h = HashConfirm(r,pk,cache); cache is Hash4(pk) */
1239: static void HashConfirm(unsigned char *h,const unsigned char *r,const unsigned char *pk,const unsigned char *cache)
1240: {
1241: #ifndef LPR
1242: unsigned char x[Hash_bytes*2];
1243: int i;
1244:
1245: Hash_prefix(x,3,r,Inputs_bytes);
1246: for (i = 0;i < Hash_bytes;++i) x[Hash_bytes+i] = cache[i];
1247: #else
1248: unsigned char x[Inputs_bytes+Hash_bytes];
1249: int i;
1250:
1251: for (i = 0;i < Inputs_bytes;++i) x[i] = r[i];
1252: for (i = 0;i < Hash_bytes;++i) x[Inputs_bytes+i] = cache[i];
1253: #endif
1254: Hash_prefix(h,2,x,sizeof x);
1255: }
1256:
1257: /* ----- session-key hash */
1258:
1259: /* k = HashSession(b,y,z) */
1260: static void HashSession(unsigned char *k,int b,const unsigned char *y,const unsigned char *z)
1261: {
1262: #ifndef LPR
1263: unsigned char x[Hash_bytes+Ciphertexts_bytes+Confirm_bytes];
1264: int i;
1265:
1266: Hash_prefix(x,3,y,Inputs_bytes);
1267: for (i = 0;i < Ciphertexts_bytes+Confirm_bytes;++i) x[Hash_bytes+i] = z[i];
1268: #else
1269: unsigned char x[Inputs_bytes+Ciphertexts_bytes+Confirm_bytes];
1270: int i;
1271:
1272: for (i = 0;i < Inputs_bytes;++i) x[i] = y[i];
1273: for (i = 0;i < Ciphertexts_bytes+Confirm_bytes;++i) x[Inputs_bytes+i] = z[i];
1274: #endif
1275: Hash_prefix(k,b,x,sizeof x);
1276: }
1277:
1278: /* ----- Streamlined NTRU Prime and NTRU LPRime */
1279:
1280: /* pk,sk = KEM_KeyGen() */
1281: static void KEM_KeyGen(unsigned char *pk,unsigned char *sk)
1282: {
1283: int i;
1284:
1285: ZKeyGen(pk,sk); sk += SecretKeys_bytes;
1286: for (i = 0;i < PublicKeys_bytes;++i) *sk++ = pk[i];
1287: randombytes(sk,Inputs_bytes); sk += Inputs_bytes;
1288: Hash_prefix(sk,4,pk,PublicKeys_bytes);
1289: }
1290:
1291: /* c,r_enc = Hide(r,pk,cache); cache is Hash4(pk) */
1292: static void Hide(unsigned char *c,unsigned char *r_enc,const Inputs r,const unsigned char *pk,const unsigned char *cache)
1293: {
1294: Inputs_encode(r_enc,r);
1295: ZEncrypt(c,r,pk); c += Ciphertexts_bytes;
1296: HashConfirm(c,r_enc,pk,cache);
1297: }
1298:
1299: /* c,k = Encap(pk) */
1300: static void Encap(unsigned char *c,unsigned char *k,const unsigned char *pk)
1301: {
1302: Inputs r;
1303: unsigned char r_enc[Inputs_bytes];
1304: unsigned char cache[Hash_bytes];
1305:
1306: Hash_prefix(cache,4,pk,PublicKeys_bytes);
1307: Inputs_random(r);
1308: Hide(c,r_enc,r,pk,cache);
1309: HashSession(k,1,r_enc,c);
1310: }
1311:
1312: /* 0 if matching ciphertext+confirm, else -1 */
1313: static int Ciphertexts_diff_mask(const unsigned char *c,const unsigned char *c2)
1314: {
1315: uint16 differentbits = 0;
1316: int len = Ciphertexts_bytes+Confirm_bytes;
1317:
1318: while (len-- > 0) differentbits |= (*c++)^(*c2++);
1319: return (1&((differentbits-1)>>8))-1;
1320: }
1321:
1322: /* k = Decap(c,sk) */
1323: static void Decap(unsigned char *k,const unsigned char *c,const unsigned char *sk)
1324: {
1325: const unsigned char *pk = sk + SecretKeys_bytes;
1326: const unsigned char *rho = pk + PublicKeys_bytes;
1327: const unsigned char *cache = rho + Inputs_bytes;
1328: Inputs r;
1329: unsigned char r_enc[Inputs_bytes];
1330: unsigned char cnew[Ciphertexts_bytes+Confirm_bytes];
1331: int mask;
1332: int i;
1333:
1334: ZDecrypt(r,c,sk);
1335: Hide(cnew,r_enc,r,pk,cache);
1336: mask = Ciphertexts_diff_mask(c,cnew);
1337: for (i = 0;i < Inputs_bytes;++i) r_enc[i] ^= mask&(r_enc[i]^rho[i]);
1338: HashSession(k,1+mask,r_enc,c);
1339: }
1340:
1341: /* ----- crypto_kem API */
1342:
1343:
1344: int crypto_kem_sntrup761_keypair(unsigned char *pk,unsigned char *sk)
1345: {
1346: KEM_KeyGen(pk,sk);
1347: return 0;
1348: }
1349:
1350: int crypto_kem_sntrup761_enc(unsigned char *c,unsigned char *k,const unsigned char *pk)
1351: {
1352: Encap(c,k,pk);
1353: return 0;
1354: }
1355:
1356: int crypto_kem_sntrup761_dec(unsigned char *k,const unsigned char *c,const unsigned char *sk)
1357: {
1358: Decap(k,c,sk);
1359: return 0;
1360: }
1361:
![[BACK]](/icons/back.gif){kind=icon}
Return to sntrup761.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / ssh