diff options
author | djm@openbsd.org <djm@openbsd.org> | 2019-01-21 22:18:24 +0000 |
---|---|---|
committer | Damien Miller <djm@mindrot.org> | 2019-01-22 09:20:14 +1100 |
commit | 533cfb01e49a2a30354e191669dc3159e03e99a7 (patch) | |
tree | 45cd439f8fd7d6270a6d26ddd77c4a16948a0ebb /sntrup4591761.c | |
parent | d50ab3cd6fb859888a26b4d4e333239b4f6bf573 (diff) |
upstream: switch sntrup implementation source from supercop to
libpqcrypto; the latter is almost identical but doesn't rely on signed
underflow to implement an optimised integer sort; from markus@
OpenBSD-Commit-ID: cd09bbf0e0fcef1bedca69fdf7990dc360567cf8
Diffstat (limited to 'sntrup4591761.c')
-rw-r--r-- | sntrup4591761.c | 109 |
1 files changed, 56 insertions, 53 deletions
diff --git a/sntrup4591761.c b/sntrup4591761.c index d3ff549ae..9631b423e 100644 --- a/sntrup4591761.c +++ b/sntrup4591761.c | |||
@@ -1,26 +1,36 @@ | |||
1 | #include <string.h> | 1 | #include <string.h> |
2 | #include "crypto_api.h" | 2 | #include "crypto_api.h" |
3 | 3 | ||
4 | /* from supercop-20181216/crypto_sort/int32/portable3/int32_minmax.inc */ | 4 | /* from libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/int32_sort.h */ |
5 | #define int32_MINMAX(a,b) \ | 5 | #ifndef int32_sort_h |
6 | do { \ | 6 | #define int32_sort_h |
7 | int32 ab = b ^ a; \ | 7 | |
8 | int32 c = b - a; \ | 8 | |
9 | c ^= ab & (c ^ b); \ | 9 | static void int32_sort(crypto_int32 *,int); |
10 | c >>= 31; \ | 10 | |
11 | c &= ab; \ | 11 | #endif |
12 | a ^= c; \ | 12 | |
13 | b ^= c; \ | 13 | /* from libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/int32_sort.c */ |
14 | } while(0) | 14 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ |
15 | 15 | ||
16 | /* from supercop-20181216/crypto_sort/int32/portable3/sort.c */ | 16 | |
17 | #define int32 crypto_int32 | 17 | static void minmax(crypto_int32 *x,crypto_int32 *y) |
18 | 18 | { | |
19 | 19 | crypto_uint32 xi = *x; | |
20 | static void crypto_sort_int32(void *array,long long n) | 20 | crypto_uint32 yi = *y; |
21 | crypto_uint32 xy = xi ^ yi; | ||
22 | crypto_uint32 c = yi - xi; | ||
23 | c ^= xy & (c ^ yi); | ||
24 | c >>= 31; | ||
25 | c = -c; | ||
26 | c &= xy; | ||
27 | *x = xi ^ c; | ||
28 | *y = yi ^ c; | ||
29 | } | ||
30 | |||
31 | static void int32_sort(crypto_int32 *x,int n) | ||
21 | { | 32 | { |
22 | long long top,p,q,r,i; | 33 | int top,p,q,i; |
23 | int32 *x = array; | ||
24 | 34 | ||
25 | if (n < 2) return; | 35 | if (n < 2) return; |
26 | top = 1; | 36 | top = 1; |
@@ -29,22 +39,15 @@ static void crypto_sort_int32(void *array,long long n) | |||
29 | for (p = top;p > 0;p >>= 1) { | 39 | for (p = top;p > 0;p >>= 1) { |
30 | for (i = 0;i < n - p;++i) | 40 | for (i = 0;i < n - p;++i) |
31 | if (!(i & p)) | 41 | if (!(i & p)) |
32 | int32_MINMAX(x[i],x[i+p]); | 42 | minmax(x + i,x + i + p); |
33 | i = 0; | 43 | for (q = top;q > p;q >>= 1) |
34 | for (q = top;q > p;q >>= 1) { | 44 | for (i = 0;i < n - q;++i) |
35 | for (;i < n - q;++i) { | 45 | if (!(i & p)) |
36 | if (!(i & p)) { | 46 | minmax(x + i + p,x + i + q); |
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 | } | 47 | } |
45 | } | 48 | } |
46 | 49 | ||
47 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/small.h */ | 50 | /* from libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/small.h */ |
48 | #ifndef small_h | 51 | #ifndef small_h |
49 | #define small_h | 52 | #define small_h |
50 | 53 | ||
@@ -62,7 +65,7 @@ static void small_random_weightw(small *); | |||
62 | 65 | ||
63 | #endif | 66 | #endif |
64 | 67 | ||
65 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/mod3.h */ | 68 | /* from libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/mod3.h */ |
66 | #ifndef mod3_h | 69 | #ifndef mod3_h |
67 | #define mod3_h | 70 | #define mod3_h |
68 | 71 | ||
@@ -122,7 +125,7 @@ static inline small mod3_quotient(small num,small den) | |||
122 | 125 | ||
123 | #endif | 126 | #endif |
124 | 127 | ||
125 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/modq.h */ | 128 | /* from libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/modq.h */ |
126 | #ifndef modq_h | 129 | #ifndef modq_h |
127 | #define modq_h | 130 | #define modq_h |
128 | 131 | ||
@@ -212,7 +215,7 @@ static inline modq modq_quotient(modq num,modq den) | |||
212 | 215 | ||
213 | #endif | 216 | #endif |
214 | 217 | ||
215 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/params.h */ | 218 | /* from libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/params.h */ |
216 | #ifndef params_h | 219 | #ifndef params_h |
217 | #define params_h | 220 | #define params_h |
218 | 221 | ||
@@ -228,7 +231,7 @@ static inline modq modq_quotient(modq num,modq den) | |||
228 | 231 | ||
229 | #endif | 232 | #endif |
230 | 233 | ||
231 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/r3.h */ | 234 | /* from libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/r3.h */ |
232 | #ifndef r3_h | 235 | #ifndef r3_h |
233 | #define r3_h | 236 | #define r3_h |
234 | 237 | ||
@@ -239,7 +242,7 @@ extern int r3_recip(small *,const small *); | |||
239 | 242 | ||
240 | #endif | 243 | #endif |
241 | 244 | ||
242 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/rq.h */ | 245 | /* from libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/rq.h */ |
243 | #ifndef rq_h | 246 | #ifndef rq_h |
244 | #define rq_h | 247 | #define rq_h |
245 | 248 | ||
@@ -260,7 +263,7 @@ int rq_recip3(modq *,const small *); | |||
260 | 263 | ||
261 | #endif | 264 | #endif |
262 | 265 | ||
263 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/swap.h */ | 266 | /* from libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/swap.h */ |
264 | #ifndef swap_h | 267 | #ifndef swap_h |
265 | #define swap_h | 268 | #define swap_h |
266 | 269 | ||
@@ -268,7 +271,7 @@ static void swap(void *,void *,int,int); | |||
268 | 271 | ||
269 | #endif | 272 | #endif |
270 | 273 | ||
271 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/dec.c */ | 274 | /* from libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/dec.c */ |
272 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ | 275 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ |
273 | 276 | ||
274 | #ifdef KAT | 277 | #ifdef KAT |
@@ -334,7 +337,7 @@ int crypto_kem_sntrup4591761_dec( | |||
334 | return result; | 337 | return result; |
335 | } | 338 | } |
336 | 339 | ||
337 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/enc.c */ | 340 | /* from libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/enc.c */ |
338 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ | 341 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ |
339 | 342 | ||
340 | #ifdef KAT | 343 | #ifdef KAT |
@@ -380,7 +383,7 @@ int crypto_kem_sntrup4591761_enc( | |||
380 | return 0; | 383 | return 0; |
381 | } | 384 | } |
382 | 385 | ||
383 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/keypair.c */ | 386 | /* from libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/keypair.c */ |
384 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ | 387 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ |
385 | 388 | ||
386 | 389 | ||
@@ -416,7 +419,7 @@ int crypto_kem_sntrup4591761_keypair(unsigned char *pk,unsigned char *sk) | |||
416 | return 0; | 419 | return 0; |
417 | } | 420 | } |
418 | 421 | ||
419 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/r3_mult.c */ | 422 | /* from libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/r3_mult.c */ |
420 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ | 423 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ |
421 | 424 | ||
422 | 425 | ||
@@ -448,7 +451,7 @@ static void r3_mult(small *h,const small *f,const small *g) | |||
448 | h[i] = fg[i]; | 451 | h[i] = fg[i]; |
449 | } | 452 | } |
450 | 453 | ||
451 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/r3_recip.c */ | 454 | /* from libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/r3_recip.c */ |
452 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ | 455 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ |
453 | 456 | ||
454 | 457 | ||
@@ -574,7 +577,7 @@ int r3_recip(small *r,const small *s) | |||
574 | return smaller_mask_r3_recip(0,d); | 577 | return smaller_mask_r3_recip(0,d); |
575 | } | 578 | } |
576 | 579 | ||
577 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/randomsmall.c */ | 580 | /* from libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/randomsmall.c */ |
578 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ | 581 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ |
579 | 582 | ||
580 | 583 | ||
@@ -588,7 +591,7 @@ static void small_random(small *g) | |||
588 | } | 591 | } |
589 | } | 592 | } |
590 | 593 | ||
591 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/randomweightw.c */ | 594 | /* from libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/randomweightw.c */ |
592 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ | 595 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ |
593 | 596 | ||
594 | 597 | ||
@@ -600,11 +603,11 @@ static void small_random_weightw(small *f) | |||
600 | for (i = 0;i < p;++i) r[i] = small_random32(); | 603 | for (i = 0;i < p;++i) r[i] = small_random32(); |
601 | for (i = 0;i < w;++i) r[i] &= -2; | 604 | for (i = 0;i < w;++i) r[i] &= -2; |
602 | for (i = w;i < p;++i) r[i] = (r[i] & -3) | 1; | 605 | for (i = w;i < p;++i) r[i] = (r[i] & -3) | 1; |
603 | crypto_sort_int32(r,p); | 606 | int32_sort(r,p); |
604 | for (i = 0;i < p;++i) f[i] = ((small) (r[i] & 3)) - 1; | 607 | for (i = 0;i < p;++i) f[i] = ((small) (r[i] & 3)) - 1; |
605 | } | 608 | } |
606 | 609 | ||
607 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/rq.c */ | 610 | /* from libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/rq.c */ |
608 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ | 611 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ |
609 | 612 | ||
610 | 613 | ||
@@ -733,7 +736,7 @@ static void rq_decode(modq *f,const unsigned char *c) | |||
733 | *f++ = modq_freeze(c0 + q - qshift); | 736 | *f++ = modq_freeze(c0 + q - qshift); |
734 | } | 737 | } |
735 | 738 | ||
736 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/rq_mult.c */ | 739 | /* from libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/rq_mult.c */ |
737 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ | 740 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ |
738 | 741 | ||
739 | 742 | ||
@@ -765,7 +768,7 @@ static void rq_mult(modq *h,const modq *f,const small *g) | |||
765 | h[i] = fg[i]; | 768 | h[i] = fg[i]; |
766 | } | 769 | } |
767 | 770 | ||
768 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/rq_recip3.c */ | 771 | /* from libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/rq_recip3.c */ |
769 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ | 772 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ |
770 | 773 | ||
771 | 774 | ||
@@ -891,7 +894,7 @@ int rq_recip3(modq *r,const small *s) | |||
891 | return smaller_mask_rq_recip3(0,d); | 894 | return smaller_mask_rq_recip3(0,d); |
892 | } | 895 | } |
893 | 896 | ||
894 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/rq_round3.c */ | 897 | /* from libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/rq_round3.c */ |
895 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ | 898 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ |
896 | 899 | ||
897 | 900 | ||
@@ -903,7 +906,7 @@ static void rq_round3(modq *h,const modq *f) | |||
903 | h[i] = ((21846 * (f[i] + 2295) + 32768) >> 16) * 3 - 2295; | 906 | h[i] = ((21846 * (f[i] + 2295) + 32768) >> 16) * 3 - 2295; |
904 | } | 907 | } |
905 | 908 | ||
906 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/rq_rounded.c */ | 909 | /* from libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/rq_rounded.c */ |
907 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ | 910 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ |
908 | 911 | ||
909 | 912 | ||
@@ -1005,7 +1008,7 @@ static void rq_decoderounded(modq *f,const unsigned char *c) | |||
1005 | *f++ = modq_freeze(f1 * 3 + q - qshift); | 1008 | *f++ = modq_freeze(f1 * 3 + q - qshift); |
1006 | } | 1009 | } |
1007 | 1010 | ||
1008 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/small.c */ | 1011 | /* from libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/small.c */ |
1009 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ | 1012 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ |
1010 | 1013 | ||
1011 | 1014 | ||
@@ -1044,7 +1047,7 @@ static void small_decode(small *f,const unsigned char *c) | |||
1044 | *f++ = ((small) (c0 & 3)) - 1; | 1047 | *f++ = ((small) (c0 & 3)) - 1; |
1045 | } | 1048 | } |
1046 | 1049 | ||
1047 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/swap.c */ | 1050 | /* from libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/swap.c */ |
1048 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ | 1051 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ |
1049 | 1052 | ||
1050 | 1053 | ||