1 /* $OpenBSD: sntrup761.c,v 1.6 2023/01/11 02:13:52 djm Exp $ */
4 * Public Domain, Authors:
5 * - Daniel J. Bernstein
6 * - Chitchanok Chuengsatiansup
8 * - Christine van Vredendaal
13 #ifdef USE_SNTRUP761X25519
16 #include "crypto_api.h"
18 #define int8 crypto_int8
19 #define uint8 crypto_uint8
20 #define int16 crypto_int16
21 #define uint16 crypto_uint16
22 #define int32 crypto_int32
23 #define uint32 crypto_uint32
24 #define int64 crypto_int64
25 #define uint64 crypto_uint64
27 /* from supercop-20201130/crypto_sort/int32/portable4/int32_minmax.inc */
28 #define int32_MINMAX(a,b) \
30 int64_t ab = (int64_t)b ^ (int64_t)a; \
31 int64_t c = (int64_t)b - (int64_t)a; \
39 /* from supercop-20201130/crypto_sort/int32/portable4/sort.c */
42 static void crypto_sort_int32(void *array,long long n)
44 long long top,p,q,r,i,j;
49 while (top < n - top) top += top;
51 for (p = top;p >= 1;p >>= 1) {
53 while (i + 2 * p <= n) {
54 for (j = i;j < i + p;++j)
55 int32_MINMAX(x[j],x[j+p]);
58 for (j = i;j < n - p;++j)
59 int32_MINMAX(x[j],x[j+p]);
63 for (q = top;q > p;q >>= 1) {
64 if (j != i) for (;;) {
65 if (j == n - q) goto done;
67 for (r = q;r > p;r >>= 1)
68 int32_MINMAX(a,x[j + r]);
76 while (i + p <= n - q) {
77 for (j = i;j < i + p;++j) {
79 for (r = q;r > p;r >>= 1)
80 int32_MINMAX(a,x[j+r]);
85 /* now i + p > n - q */
89 for (r = q;r > p;r >>= 1)
90 int32_MINMAX(a,x[j+r]);
100 /* from supercop-20201130/crypto_sort/uint32/useint32/sort.c */
102 /* can save time by vectorizing xor loops */
103 /* can save time by integrating xor loops with int32_sort */
105 static void crypto_sort_uint32(void *array,long long n)
107 crypto_uint32 *x = array;
109 for (j = 0;j < n;++j) x[j] ^= 0x80000000;
110 crypto_sort_int32(array,n);
111 for (j = 0;j < n;++j) x[j] ^= 0x80000000;
114 /* from supercop-20201130/crypto_kem/sntrup761/ref/uint32.c */
117 CPU division instruction typically takes time depending on x.
118 This software is designed to take time independent of x.
119 Time still varies depending on m; user must ensure that m is constant.
120 Time also varies on CPUs where multiplication is variable-time.
121 There could be more CPU issues.
122 There could also be compiler issues.
125 static void uint32_divmod_uint14(uint32 *q,uint16 *r,uint32 x,uint16 m)
127 uint32 v = 0x80000000;
133 /* caller guarantees m > 0 */
134 /* caller guarantees m < 16384 */
135 /* vm <= 2^31 <= vm+m-1 */
136 /* xvm <= 2^31 x <= xvm+x(m-1) */
140 qpart = (x*(uint64)v)>>31;
141 /* 2^31 qpart <= xv <= 2^31 qpart + 2^31-1 */
142 /* 2^31 qpart m <= xvm <= 2^31 qpart m + (2^31-1)m */
143 /* 2^31 qpart m <= 2^31 x <= 2^31 qpart m + (2^31-1)m + x(m-1) */
144 /* 0 <= 2^31 newx <= (2^31-1)m + x(m-1) */
145 /* 0 <= newx <= (1-1/2^31)m + x(m-1)/2^31 */
146 /* 0 <= newx <= (1-1/2^31)(2^14-1) + (2^32-1)((2^14-1)-1)/2^31 */
148 x -= qpart*m; *q += qpart;
151 qpart = (x*(uint64)v)>>31;
152 /* 0 <= newx <= (1-1/2^31)m + x(m-1)/2^31 */
153 /* 0 <= newx <= m + 49146(2^14-1)/2^31 */
154 /* 0 <= newx <= m + 0.4 */
157 x -= qpart*m; *q += qpart;
162 x += mask&(uint32)m; *q += mask;
169 static uint16 uint32_mod_uint14(uint32 x,uint16 m)
173 uint32_divmod_uint14(&q,&r,x,m);
177 /* from supercop-20201130/crypto_kem/sntrup761/ref/int32.c */
179 static void int32_divmod_uint14(int32 *q,uint16 *r,int32 x,uint16 m)
185 uint32_divmod_uint14(&uq,&ur,0x80000000+(uint32)x,m);
186 uint32_divmod_uint14(&uq2,&ur2,0x80000000,m);
187 ur -= ur2; uq -= uq2;
188 mask = -(uint32)(ur>>15);
189 ur += mask&m; uq += mask;
194 static uint16 int32_mod_uint14(int32 x,uint16 m)
198 int32_divmod_uint14(&q,&r,x,m);
202 /* from supercop-20201130/crypto_kem/sntrup761/ref/paramsmenu.h */
203 /* pick one of these three: */
208 /* pick one of these two: */
209 #define SNTRUP /* Streamlined NTRU Prime */
210 #undef LPR /* NTRU LPRime */
212 /* from supercop-20201130/crypto_kem/sntrup761/ref/params.h */
216 /* menu of parameter choices: */
219 /* what the menu means: */
224 #define Rounded_bytes 1007
226 #define Rq_bytes 1158
236 #elif defined(SIZE653)
239 #define Rounded_bytes 865
251 #elif defined(SIZE857)
254 #define Rounded_bytes 1152
256 #define Rq_bytes 1322
267 #error "no parameter set defined"
276 /* from supercop-20201130/crypto_kem/sntrup761/ref/Decode.h */
281 /* Decode(R,s,M,len) */
282 /* assumes 0 < M[i] < 16384 */
283 /* produces 0 <= R[i] < M[i] */
287 /* from supercop-20201130/crypto_kem/sntrup761/ref/Decode.c */
289 static void Decode(uint16 *out,const unsigned char *S,const uint16 *M,long long len)
294 else if (M[0] <= 256)
295 *out = uint32_mod_uint14(S[0],M[0]);
297 *out = uint32_mod_uint14(S[0]+(((uint16)S[1])<<8),M[0]);
300 uint16 R2[(len+1)/2];
301 uint16 M2[(len+1)/2];
302 uint16 bottomr[len/2];
303 uint32 bottomt[len/2];
305 for (i = 0;i < len-1;i += 2) {
306 uint32 m = M[i]*(uint32) M[i+1];
308 bottomt[i/2] = 256*256;
309 bottomr[i/2] = S[0]+256*S[1];
311 M2[i/2] = (((m+255)>>8)+255)>>8;
312 } else if (m >= 16384) {
316 M2[i/2] = (m+255)>>8;
325 Decode(R2,S,M2,(len+1)/2);
326 for (i = 0;i < len-1;i += 2) {
327 uint32 r = bottomr[i/2];
330 r += bottomt[i/2]*R2[i/2];
331 uint32_divmod_uint14(&r1,&r0,r,M[i]);
332 r1 = uint32_mod_uint14(r1,M[i+1]); /* only needed for invalid inputs */
341 /* from supercop-20201130/crypto_kem/sntrup761/ref/Encode.h */
346 /* Encode(s,R,M,len) */
347 /* assumes 0 <= R[i] < M[i] < 16384 */
351 /* from supercop-20201130/crypto_kem/sntrup761/ref/Encode.c */
353 /* 0 <= R[i] < M[i] < 16384 */
354 static void Encode(unsigned char *out,const uint16 *R,const uint16 *M,long long len)
366 uint16 R2[(len+1)/2];
367 uint16 M2[(len+1)/2];
369 for (i = 0;i < len-1;i += 2) {
371 uint32 r = R[i]+R[i+1]*m0;
372 uint32 m = M[i+1]*m0;
385 Encode(out,R2,M2,(len+1)/2);
389 /* from supercop-20201130/crypto_kem/sntrup761/ref/kem.c */
399 /* return -1 if x!=0; else return 0 */
400 static int int16_nonzero_mask(int16 x)
402 uint16 u = x; /* 0, else 1...65535 */
403 uint32 v = u; /* 0, else 1...65535 */
404 v = -v; /* 0, else 2^32-65535...2^32-1 */
405 v >>= 31; /* 0, else 1 */
406 return -v; /* 0, else -1 */
411 /* return -1 if x<0; otherwise return 0 */
412 static int int16_negative_mask(int16 x)
417 /* alternative with gcc -fwrapv: */
418 /* x>>15 compiles to CPU's arithmetic right shift */
421 /* ----- arithmetic mod 3 */
425 /* F3 is always represented as -1,0,1 */
426 /* so ZZ_fromF3 is a no-op */
428 /* x must not be close to top int16 */
429 static small F3_freeze(int16 x)
431 return int32_mod_uint14(x+1,3)-1;
434 /* ----- arithmetic mod q */
436 #define q12 ((q-1)/2)
438 /* always represented as -q12...q12 */
439 /* so ZZ_fromFq is a no-op */
441 /* x must not be close to top int32 */
442 static Fq Fq_freeze(int32 x)
444 return int32_mod_uint14(x+q12,q)-q12;
449 static Fq Fq_recip(Fq a1)
455 ai = Fq_freeze(a1*(int32)ai);
463 /* ----- Top and Right */
468 static int8 Top(Fq C)
470 return (tau1*(int32)(C+tau0)+16384)>>15;
473 static Fq Right(int8 T)
475 return Fq_freeze(tau3*(int32)T-tau2);
479 /* ----- small polynomials */
483 /* 0 if Weightw_is(r), else -1 */
484 static int Weightw_mask(small *r)
489 for (i = 0;i < p;++i) weight += r[i]&1;
490 return int16_nonzero_mask(weight-w);
493 /* R3_fromR(R_fromRq(r)) */
494 static void R3_fromRq(small *out,const Fq *r)
497 for (i = 0;i < p;++i) out[i] = F3_freeze(r[i]);
500 /* h = f*g in the ring R3 */
501 static void R3_mult(small *h,const small *f,const small *g)
507 for (i = 0;i < p;++i) {
509 for (j = 0;j <= i;++j) result = F3_freeze(result+f[j]*g[i-j]);
512 for (i = p;i < p+p-1;++i) {
514 for (j = i-p+1;j < p;++j) result = F3_freeze(result+f[j]*g[i-j]);
518 for (i = p+p-2;i >= p;--i) {
519 fg[i-p] = F3_freeze(fg[i-p]+fg[i]);
520 fg[i-p+1] = F3_freeze(fg[i-p+1]+fg[i]);
523 for (i = 0;i < p;++i) h[i] = fg[i];
526 /* returns 0 if recip succeeded; else -1 */
527 static int R3_recip(small *out,const small *in)
529 small f[p+1],g[p+1],v[p+1],r[p+1];
533 for (i = 0;i < p+1;++i) v[i] = 0;
534 for (i = 0;i < p+1;++i) r[i] = 0;
536 for (i = 0;i < p;++i) f[i] = 0;
537 f[0] = 1; f[p-1] = f[p] = -1;
538 for (i = 0;i < p;++i) g[p-1-i] = in[i];
543 for (loop = 0;loop < 2*p-1;++loop) {
544 for (i = p;i > 0;--i) v[i] = v[i-1];
548 swap = int16_negative_mask(-delta) & int16_nonzero_mask(g[0]);
549 delta ^= swap&(delta^-delta);
552 for (i = 0;i < p+1;++i) {
553 t = swap&(f[i]^g[i]); f[i] ^= t; g[i] ^= t;
554 t = swap&(v[i]^r[i]); v[i] ^= t; r[i] ^= t;
557 for (i = 0;i < p+1;++i) g[i] = F3_freeze(g[i]+sign*f[i]);
558 for (i = 0;i < p+1;++i) r[i] = F3_freeze(r[i]+sign*v[i]);
560 for (i = 0;i < p;++i) g[i] = g[i+1];
565 for (i = 0;i < p;++i) out[i] = sign*v[p-1-i];
567 return int16_nonzero_mask(delta);
572 /* ----- polynomials mod q */
574 /* h = f*g in the ring Rq */
575 static void Rq_mult_small(Fq *h,const Fq *f,const small *g)
581 for (i = 0;i < p;++i) {
583 for (j = 0;j <= i;++j) result = Fq_freeze(result+f[j]*(int32)g[i-j]);
586 for (i = p;i < p+p-1;++i) {
588 for (j = i-p+1;j < p;++j) result = Fq_freeze(result+f[j]*(int32)g[i-j]);
592 for (i = p+p-2;i >= p;--i) {
593 fg[i-p] = Fq_freeze(fg[i-p]+fg[i]);
594 fg[i-p+1] = Fq_freeze(fg[i-p+1]+fg[i]);
597 for (i = 0;i < p;++i) h[i] = fg[i];
603 static void Rq_mult3(Fq *h,const Fq *f)
607 for (i = 0;i < p;++i) h[i] = Fq_freeze(3*f[i]);
610 /* out = 1/(3*in) in Rq */
611 /* returns 0 if recip succeeded; else -1 */
612 static int Rq_recip3(Fq *out,const small *in)
614 Fq f[p+1],g[p+1],v[p+1],r[p+1];
620 for (i = 0;i < p+1;++i) v[i] = 0;
621 for (i = 0;i < p+1;++i) r[i] = 0;
623 for (i = 0;i < p;++i) f[i] = 0;
624 f[0] = 1; f[p-1] = f[p] = -1;
625 for (i = 0;i < p;++i) g[p-1-i] = in[i];
630 for (loop = 0;loop < 2*p-1;++loop) {
631 for (i = p;i > 0;--i) v[i] = v[i-1];
634 swap = int16_negative_mask(-delta) & int16_nonzero_mask(g[0]);
635 delta ^= swap&(delta^-delta);
638 for (i = 0;i < p+1;++i) {
639 t = swap&(f[i]^g[i]); f[i] ^= t; g[i] ^= t;
640 t = swap&(v[i]^r[i]); v[i] ^= t; r[i] ^= t;
645 for (i = 0;i < p+1;++i) g[i] = Fq_freeze(f0*g[i]-g0*f[i]);
646 for (i = 0;i < p+1;++i) r[i] = Fq_freeze(f0*r[i]-g0*v[i]);
648 for (i = 0;i < p;++i) g[i] = g[i+1];
652 scale = Fq_recip(f[0]);
653 for (i = 0;i < p;++i) out[i] = Fq_freeze(scale*(int32)v[p-1-i]);
655 return int16_nonzero_mask(delta);
660 /* ----- rounded polynomials mod q */
662 static void Round(Fq *out,const Fq *a)
665 for (i = 0;i < p;++i) out[i] = a[i]-F3_freeze(a[i]);
668 /* ----- sorting to generate short polynomial */
670 static void Short_fromlist(small *out,const uint32 *in)
675 for (i = 0;i < w;++i) L[i] = in[i]&(uint32)-2;
676 for (i = w;i < p;++i) L[i] = (in[i]&(uint32)-3)|1;
677 crypto_sort_uint32(L,p);
678 for (i = 0;i < p;++i) out[i] = (L[i]&3)-1;
681 /* ----- underlying hash function */
683 #define Hash_bytes 32
685 /* e.g., b = 0 means out = Hash0(in) */
686 static void Hash_prefix(unsigned char *out,int b,const unsigned char *in,int inlen)
688 unsigned char x[inlen+1];
693 for (i = 0;i < inlen;++i) x[i+1] = in[i];
694 crypto_hash_sha512(h,x,inlen+1);
695 for (i = 0;i < 32;++i) out[i] = h[i];
698 /* ----- higher-level randomness */
700 static uint32 urandom32(void)
706 out[0] = (uint32)c[0];
707 out[1] = ((uint32)c[1])<<8;
708 out[2] = ((uint32)c[2])<<16;
709 out[3] = ((uint32)c[3])<<24;
710 return out[0]+out[1]+out[2]+out[3];
713 static void Short_random(small *out)
718 for (i = 0;i < p;++i) L[i] = urandom32();
719 Short_fromlist(out,L);
724 static void Small_random(small *out)
728 for (i = 0;i < p;++i) out[i] = (((urandom32()&0x3fffffff)*3)>>30)-1;
733 /* ----- Streamlined NTRU Prime Core */
737 /* h,(f,ginv) = KeyGen() */
738 static void KeyGen(Fq *h,small *f,small *ginv)
745 if (R3_recip(ginv,g) == 0) break;
748 Rq_recip3(finv,f); /* always works */
749 Rq_mult_small(h,finv,g);
752 /* c = Encrypt(r,h) */
753 static void Encrypt(Fq *c,const small *r,const Fq *h)
757 Rq_mult_small(hr,h,r);
761 /* r = Decrypt(c,(f,ginv)) */
762 static void Decrypt(small *r,const Fq *c,const small *f,const small *ginv)
771 Rq_mult_small(cf,c,f);
776 mask = Weightw_mask(ev); /* 0 if weight w, else -1 */
777 for (i = 0;i < w;++i) r[i] = ((ev[i]^1)&~mask)^1;
778 for (i = w;i < p;++i) r[i] = ev[i]&~mask;
783 /* ----- NTRU LPRime Core */
787 /* (G,A),a = KeyGen(G); leaves G unchanged */
788 static void KeyGen(Fq *A,small *a,const Fq *G)
793 Rq_mult_small(aG,G,a);
797 /* B,T = Encrypt(r,(G,A),b) */
798 static void Encrypt(Fq *B,int8 *T,const int8 *r,const Fq *G,const Fq *A,const small *b)
804 Rq_mult_small(bG,G,b);
806 Rq_mult_small(bA,A,b);
807 for (i = 0;i < I;++i) T[i] = Top(Fq_freeze(bA[i]+r[i]*q12));
810 /* r = Decrypt((B,T),a) */
811 static void Decrypt(int8 *r,const Fq *B,const int8 *T,const small *a)
816 Rq_mult_small(aB,B,a);
817 for (i = 0;i < I;++i)
818 r[i] = -int16_negative_mask(Fq_freeze(Right(T[i])-aB[i]+4*w+1));
823 /* ----- encoding I-bit inputs */
827 #define Inputs_bytes (I/8)
828 typedef int8 Inputs[I]; /* passed by reference */
830 static void Inputs_encode(unsigned char *s,const Inputs r)
833 for (i = 0;i < Inputs_bytes;++i) s[i] = 0;
834 for (i = 0;i < I;++i) s[i>>3] |= r[i]<<(i&7);
843 static const unsigned char aes_nonce[16] = {0};
845 static void Expand(uint32 *L,const unsigned char *k)
848 crypto_stream_aes256ctr((unsigned char *) L,4*p,aes_nonce,k);
849 for (i = 0;i < p;++i) {
850 uint32 L0 = ((unsigned char *) L)[4*i];
851 uint32 L1 = ((unsigned char *) L)[4*i+1];
852 uint32 L2 = ((unsigned char *) L)[4*i+2];
853 uint32 L3 = ((unsigned char *) L)[4*i+3];
854 L[i] = L0+(L1<<8)+(L2<<16)+(L3<<24);
864 #define Seeds_bytes 32
866 static void Seeds_random(unsigned char *s)
868 randombytes(s,Seeds_bytes);
873 /* ----- Generator, HashShort */
877 /* G = Generator(k) */
878 static void Generator(Fq *G,const unsigned char *k)
884 for (i = 0;i < p;++i) G[i] = uint32_mod_uint14(L[i],q)-q12;
887 /* out = HashShort(r) */
888 static void HashShort(small *out,const Inputs r)
890 unsigned char s[Inputs_bytes];
891 unsigned char h[Hash_bytes];
895 Hash_prefix(h,5,s,sizeof s);
897 Short_fromlist(out,L);
902 /* ----- NTRU LPRime Expand */
906 /* (S,A),a = XKeyGen() */
907 static void XKeyGen(unsigned char *S,Fq *A,small *a)
916 /* B,T = XEncrypt(r,(S,A)) */
917 static void XEncrypt(Fq *B,int8 *T,const int8 *r,const unsigned char *S,const Fq *A)
924 Encrypt(B,T,r,G,A,b);
927 #define XDecrypt Decrypt
931 /* ----- encoding small polynomials (including short polynomials) */
933 #define Small_bytes ((p+3)/4)
935 /* these are the only functions that rely on p mod 4 = 1 */
937 static void Small_encode(unsigned char *s,const small *f)
942 for (i = 0;i < p/4;++i) {
953 static void Small_decode(small *f,const unsigned char *s)
958 for (i = 0;i < p/4;++i) {
960 *f++ = ((small)(x&3))-1; x >>= 2;
961 *f++ = ((small)(x&3))-1; x >>= 2;
962 *f++ = ((small)(x&3))-1; x >>= 2;
963 *f++ = ((small)(x&3))-1;
966 *f++ = ((small)(x&3))-1;
969 /* ----- encoding general polynomials */
973 static void Rq_encode(unsigned char *s,const Fq *r)
978 for (i = 0;i < p;++i) R[i] = r[i]+q12;
979 for (i = 0;i < p;++i) M[i] = q;
983 static void Rq_decode(Fq *r,const unsigned char *s)
988 for (i = 0;i < p;++i) M[i] = q;
990 for (i = 0;i < p;++i) r[i] = ((Fq)R[i])-q12;
995 /* ----- encoding rounded polynomials */
997 static void Rounded_encode(unsigned char *s,const Fq *r)
1002 for (i = 0;i < p;++i) R[i] = ((r[i]+q12)*10923)>>15;
1003 for (i = 0;i < p;++i) M[i] = (q+2)/3;
1007 static void Rounded_decode(Fq *r,const unsigned char *s)
1012 for (i = 0;i < p;++i) M[i] = (q+2)/3;
1014 for (i = 0;i < p;++i) r[i] = R[i]*3-q12;
1017 /* ----- encoding top polynomials */
1021 #define Top_bytes (I/2)
1023 static void Top_encode(unsigned char *s,const int8 *T)
1026 for (i = 0;i < Top_bytes;++i)
1027 s[i] = T[2*i]+(T[2*i+1]<<4);
1030 static void Top_decode(int8 *T,const unsigned char *s)
1033 for (i = 0;i < Top_bytes;++i) {
1041 /* ----- Streamlined NTRU Prime Core plus encoding */
1045 typedef small Inputs[p]; /* passed by reference */
1046 #define Inputs_random Short_random
1047 #define Inputs_encode Small_encode
1048 #define Inputs_bytes Small_bytes
1050 #define Ciphertexts_bytes Rounded_bytes
1051 #define SecretKeys_bytes (2*Small_bytes)
1052 #define PublicKeys_bytes Rq_bytes
1054 /* pk,sk = ZKeyGen() */
1055 static void ZKeyGen(unsigned char *pk,unsigned char *sk)
1062 Small_encode(sk,f); sk += Small_bytes;
1066 /* C = ZEncrypt(r,pk) */
1067 static void ZEncrypt(unsigned char *C,const Inputs r,const unsigned char *pk)
1073 Rounded_encode(C,c);
1076 /* r = ZDecrypt(C,sk) */
1077 static void ZDecrypt(Inputs r,const unsigned char *C,const unsigned char *sk)
1082 Small_decode(f,sk); sk += Small_bytes;
1084 Rounded_decode(c,C);
1090 /* ----- NTRU LPRime Expand plus encoding */
1094 #define Ciphertexts_bytes (Rounded_bytes+Top_bytes)
1095 #define SecretKeys_bytes Small_bytes
1096 #define PublicKeys_bytes (Seeds_bytes+Rounded_bytes)
1098 static void Inputs_random(Inputs r)
1100 unsigned char s[Inputs_bytes];
1103 randombytes(s,sizeof s);
1104 for (i = 0;i < I;++i) r[i] = 1&(s[i>>3]>>(i&7));
1107 /* pk,sk = ZKeyGen() */
1108 static void ZKeyGen(unsigned char *pk,unsigned char *sk)
1113 XKeyGen(pk,A,a); pk += Seeds_bytes;
1114 Rounded_encode(pk,A);
1118 /* c = ZEncrypt(r,pk) */
1119 static void ZEncrypt(unsigned char *c,const Inputs r,const unsigned char *pk)
1125 Rounded_decode(A,pk+Seeds_bytes);
1126 XEncrypt(B,T,r,pk,A);
1127 Rounded_encode(c,B); c += Rounded_bytes;
1131 /* r = ZDecrypt(C,sk) */
1132 static void ZDecrypt(Inputs r,const unsigned char *c,const unsigned char *sk)
1139 Rounded_decode(B,c);
1140 Top_decode(T,c+Rounded_bytes);
1146 /* ----- confirmation hash */
1148 #define Confirm_bytes 32
1150 /* h = HashConfirm(r,pk,cache); cache is Hash4(pk) */
1151 static void HashConfirm(unsigned char *h,const unsigned char *r,const unsigned char *pk,const unsigned char *cache)
1154 unsigned char x[Hash_bytes*2];
1157 Hash_prefix(x,3,r,Inputs_bytes);
1158 for (i = 0;i < Hash_bytes;++i) x[Hash_bytes+i] = cache[i];
1160 unsigned char x[Inputs_bytes+Hash_bytes];
1163 for (i = 0;i < Inputs_bytes;++i) x[i] = r[i];
1164 for (i = 0;i < Hash_bytes;++i) x[Inputs_bytes+i] = cache[i];
1166 Hash_prefix(h,2,x,sizeof x);
1169 /* ----- session-key hash */
1171 /* k = HashSession(b,y,z) */
1172 static void HashSession(unsigned char *k,int b,const unsigned char *y,const unsigned char *z)
1175 unsigned char x[Hash_bytes+Ciphertexts_bytes+Confirm_bytes];
1178 Hash_prefix(x,3,y,Inputs_bytes);
1179 for (i = 0;i < Ciphertexts_bytes+Confirm_bytes;++i) x[Hash_bytes+i] = z[i];
1181 unsigned char x[Inputs_bytes+Ciphertexts_bytes+Confirm_bytes];
1184 for (i = 0;i < Inputs_bytes;++i) x[i] = y[i];
1185 for (i = 0;i < Ciphertexts_bytes+Confirm_bytes;++i) x[Inputs_bytes+i] = z[i];
1187 Hash_prefix(k,b,x,sizeof x);
1190 /* ----- Streamlined NTRU Prime and NTRU LPRime */
1192 /* pk,sk = KEM_KeyGen() */
1193 static void KEM_KeyGen(unsigned char *pk,unsigned char *sk)
1197 ZKeyGen(pk,sk); sk += SecretKeys_bytes;
1198 for (i = 0;i < PublicKeys_bytes;++i) *sk++ = pk[i];
1199 randombytes(sk,Inputs_bytes); sk += Inputs_bytes;
1200 Hash_prefix(sk,4,pk,PublicKeys_bytes);
1203 /* c,r_enc = Hide(r,pk,cache); cache is Hash4(pk) */
1204 static void Hide(unsigned char *c,unsigned char *r_enc,const Inputs r,const unsigned char *pk,const unsigned char *cache)
1206 Inputs_encode(r_enc,r);
1207 ZEncrypt(c,r,pk); c += Ciphertexts_bytes;
1208 HashConfirm(c,r_enc,pk,cache);
1211 /* c,k = Encap(pk) */
1212 static void Encap(unsigned char *c,unsigned char *k,const unsigned char *pk)
1215 unsigned char r_enc[Inputs_bytes];
1216 unsigned char cache[Hash_bytes];
1218 Hash_prefix(cache,4,pk,PublicKeys_bytes);
1220 Hide(c,r_enc,r,pk,cache);
1221 HashSession(k,1,r_enc,c);
1224 /* 0 if matching ciphertext+confirm, else -1 */
1225 static int Ciphertexts_diff_mask(const unsigned char *c,const unsigned char *c2)
1227 uint16 differentbits = 0;
1228 int len = Ciphertexts_bytes+Confirm_bytes;
1230 while (len-- > 0) differentbits |= (*c++)^(*c2++);
1231 return (1&((differentbits-1)>>8))-1;
1234 /* k = Decap(c,sk) */
1235 static void Decap(unsigned char *k,const unsigned char *c,const unsigned char *sk)
1237 const unsigned char *pk = sk + SecretKeys_bytes;
1238 const unsigned char *rho = pk + PublicKeys_bytes;
1239 const unsigned char *cache = rho + Inputs_bytes;
1241 unsigned char r_enc[Inputs_bytes];
1242 unsigned char cnew[Ciphertexts_bytes+Confirm_bytes];
1247 Hide(cnew,r_enc,r,pk,cache);
1248 mask = Ciphertexts_diff_mask(c,cnew);
1249 for (i = 0;i < Inputs_bytes;++i) r_enc[i] ^= mask&(r_enc[i]^rho[i]);
1250 HashSession(k,1+mask,r_enc,c);
1253 /* ----- crypto_kem API */
1256 int crypto_kem_sntrup761_keypair(unsigned char *pk,unsigned char *sk)
1262 int crypto_kem_sntrup761_enc(unsigned char *c,unsigned char *k,const unsigned char *pk)
1268 int crypto_kem_sntrup761_dec(unsigned char *k,const unsigned char *c,const unsigned char *sk)
1273 #endif /* USE_SNTRUP761X25519 */