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