summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authordjm@openbsd.org <djm@openbsd.org>2019-01-21 22:18:24 +0000
committerDamien Miller <djm@mindrot.org>2019-01-22 09:20:14 +1100
commit533cfb01e49a2a30354e191669dc3159e03e99a7 (patch)
tree45cd439f8fd7d6270a6d26ddd77c4a16948a0ebb
parentd50ab3cd6fb859888a26b4d4e333239b4f6bf573 (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
-rw-r--r--sntrup4591761.c109
-rw-r--r--sntrup4591761.sh47
2 files changed, 79 insertions, 77 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
6do { \ 6#define int32_sort_h
7 int32 ab = b ^ a; \ 7
8 int32 c = b - a; \ 8
9 c ^= ab & (c ^ b); \ 9static 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 17static void minmax(crypto_int32 *x,crypto_int32 *y)
18 18{
19 19 crypto_uint32 xi = *x;
20static 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
31static 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
diff --git a/sntrup4591761.sh b/sntrup4591761.sh
index 5540ca4d9..2a0a4200b 100644
--- a/sntrup4591761.sh
+++ b/sntrup4591761.sh
@@ -1,28 +1,28 @@
1#!/bin/sh 1#!/bin/sh
2FILES=" 2FILES="
3 supercop-20181216/crypto_sort/int32/portable3/int32_minmax.inc 3 libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/int32_sort.h
4 supercop-20181216/crypto_sort/int32/portable3/sort.c 4 libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/int32_sort.c
5 supercop-20181216/crypto_kem/sntrup4591761/ref/small.h 5 libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/small.h
6 supercop-20181216/crypto_kem/sntrup4591761/ref/mod3.h 6 libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/mod3.h
7 supercop-20181216/crypto_kem/sntrup4591761/ref/modq.h 7 libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/modq.h
8 supercop-20181216/crypto_kem/sntrup4591761/ref/params.h 8 libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/params.h
9 supercop-20181216/crypto_kem/sntrup4591761/ref/r3.h 9 libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/r3.h
10 supercop-20181216/crypto_kem/sntrup4591761/ref/rq.h 10 libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/rq.h
11 supercop-20181216/crypto_kem/sntrup4591761/ref/swap.h 11 libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/swap.h
12 supercop-20181216/crypto_kem/sntrup4591761/ref/dec.c 12 libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/dec.c
13 supercop-20181216/crypto_kem/sntrup4591761/ref/enc.c 13 libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/enc.c
14 supercop-20181216/crypto_kem/sntrup4591761/ref/keypair.c 14 libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/keypair.c
15 supercop-20181216/crypto_kem/sntrup4591761/ref/r3_mult.c 15 libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/r3_mult.c
16 supercop-20181216/crypto_kem/sntrup4591761/ref/r3_recip.c 16 libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/r3_recip.c
17 supercop-20181216/crypto_kem/sntrup4591761/ref/randomsmall.c 17 libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/randomsmall.c
18 supercop-20181216/crypto_kem/sntrup4591761/ref/randomweightw.c 18 libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/randomweightw.c
19 supercop-20181216/crypto_kem/sntrup4591761/ref/rq.c 19 libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/rq.c
20 supercop-20181216/crypto_kem/sntrup4591761/ref/rq_mult.c 20 libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/rq_mult.c
21 supercop-20181216/crypto_kem/sntrup4591761/ref/rq_recip3.c 21 libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/rq_recip3.c
22 supercop-20181216/crypto_kem/sntrup4591761/ref/rq_round3.c 22 libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/rq_round3.c
23 supercop-20181216/crypto_kem/sntrup4591761/ref/rq_rounded.c 23 libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/rq_rounded.c
24 supercop-20181216/crypto_kem/sntrup4591761/ref/small.c 24 libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/small.c
25 supercop-20181216/crypto_kem/sntrup4591761/ref/swap.c 25 libpqcrypto-20180314/crypto_kem/sntrup4591761/ref/swap.c
26" 26"
27### 27###
28 28
@@ -40,7 +40,6 @@ for i in $FILES; do
40 grep -v "extern crypto_int32 small_random32" | 40 grep -v "extern crypto_int32 small_random32" |
41 sed -e "s/crypto_kem_/crypto_kem_sntrup4591761_/g" \ 41 sed -e "s/crypto_kem_/crypto_kem_sntrup4591761_/g" \
42 -e "s/smaller_mask/smaller_mask_${b}/g" \ 42 -e "s/smaller_mask/smaller_mask_${b}/g" \
43 -e "s/void crypto_sort/void crypto_sort_int32/" \
44 -e "s/^extern void /static void /" \ 43 -e "s/^extern void /static void /" \
45 -e "s/^void /static void /" 44 -e "s/^void /static void /"
46 echo 45 echo