summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/lib/libcrypto/bn/bn.h4
-rw-r--r--src/lib/libcrypto/bn/bn_gcd.c158
-rw-r--r--src/lib/libcrypto/bn/bn_lcl.h4
-rw-r--r--src/lib/libcrypto/bn/bn_x931p.c4
-rw-r--r--src/lib/libcrypto/rsa/rsa_chk.c4
-rw-r--r--src/lib/libcrypto/rsa/rsa_gen.c6
6 files changed, 170 insertions, 10 deletions
diff --git a/src/lib/libcrypto/bn/bn.h b/src/lib/libcrypto/bn/bn.h
index 5d5de7e43a..0dde08a368 100644
--- a/src/lib/libcrypto/bn/bn.h
+++ b/src/lib/libcrypto/bn/bn.h
@@ -1,4 +1,4 @@
1/* $OpenBSD: bn.h,v 1.35 2017/01/21 11:00:46 beck Exp $ */ 1/* $OpenBSD: bn.h,v 1.36 2017/01/25 06:15:44 beck Exp $ */
2/* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com) 2/* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com)
3 * All rights reserved. 3 * All rights reserved.
4 * 4 *
@@ -452,7 +452,9 @@ char * BN_bn2dec(const BIGNUM *a);
452int BN_hex2bn(BIGNUM **a, const char *str); 452int BN_hex2bn(BIGNUM **a, const char *str);
453int BN_dec2bn(BIGNUM **a, const char *str); 453int BN_dec2bn(BIGNUM **a, const char *str);
454int BN_asc2bn(BIGNUM **a, const char *str); 454int BN_asc2bn(BIGNUM **a, const char *str);
455#ifndef LIBRESSL_INTERNAL
455int BN_gcd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx); 456int BN_gcd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx);
457#endif
456int BN_kronecker(const BIGNUM *a,const BIGNUM *b,BN_CTX *ctx); /* returns -2 for error */ 458int BN_kronecker(const BIGNUM *a,const BIGNUM *b,BN_CTX *ctx); /* returns -2 for error */
457#ifndef LIBRESSL_INTERNAL 459#ifndef LIBRESSL_INTERNAL
458BIGNUM *BN_mod_inverse(BIGNUM *ret, 460BIGNUM *BN_mod_inverse(BIGNUM *ret,
diff --git a/src/lib/libcrypto/bn/bn_gcd.c b/src/lib/libcrypto/bn/bn_gcd.c
index 30896e4763..e2574c3304 100644
--- a/src/lib/libcrypto/bn/bn_gcd.c
+++ b/src/lib/libcrypto/bn/bn_gcd.c
@@ -1,4 +1,4 @@
1/* $OpenBSD: bn_gcd.c,v 1.13 2017/01/21 23:02:53 beck Exp $ */ 1/* $OpenBSD: bn_gcd.c,v 1.14 2017/01/25 06:15:44 beck Exp $ */
2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3 * All rights reserved. 3 * All rights reserved.
4 * 4 *
@@ -114,6 +114,8 @@
114#include "bn_lcl.h" 114#include "bn_lcl.h"
115 115
116static BIGNUM *euclid(BIGNUM *a, BIGNUM *b); 116static BIGNUM *euclid(BIGNUM *a, BIGNUM *b);
117static BIGNUM *BN_gcd_no_branch(BIGNUM *in, const BIGNUM *a, const BIGNUM *n,
118 BN_CTX *ctx);
117 119
118int 120int
119BN_gcd(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx) 121BN_gcd(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx)
@@ -156,6 +158,21 @@ err:
156 return (ret); 158 return (ret);
157} 159}
158 160
161int
162BN_gcd_ct(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx)
163{
164 if (BN_gcd_no_branch(r, in_a, in_b, ctx) == NULL)
165 return 0;
166 return 1;
167}
168
169int
170BN_gcd_nonct(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx)
171{
172 return BN_gcd(r, in_a, in_b, ctx);
173}
174
175
159static BIGNUM * 176static BIGNUM *
160euclid(BIGNUM *a, BIGNUM *b) 177euclid(BIGNUM *a, BIGNUM *b)
161{ 178{
@@ -704,3 +721,142 @@ err:
704 bn_check_top(ret); 721 bn_check_top(ret);
705 return (ret); 722 return (ret);
706} 723}
724
725/*
726 * BN_gcd_no_branch is a special version of BN_mod_inverse_no_branch.
727 * that returns the GCD.
728 */
729static BIGNUM *
730BN_gcd_no_branch(BIGNUM *in, const BIGNUM *a, const BIGNUM *n,
731 BN_CTX *ctx)
732{
733 BIGNUM *A, *B, *X, *Y, *M, *D, *T, *R = NULL;
734 BIGNUM local_A, local_B;
735 BIGNUM *pA, *pB;
736 BIGNUM *ret = NULL;
737 int sign;
738
739 if (in == NULL)
740 goto err;
741 R = in;
742
743 bn_check_top(a);
744 bn_check_top(n);
745
746 BN_CTX_start(ctx);
747 if ((A = BN_CTX_get(ctx)) == NULL)
748 goto err;
749 if ((B = BN_CTX_get(ctx)) == NULL)
750 goto err;
751 if ((X = BN_CTX_get(ctx)) == NULL)
752 goto err;
753 if ((D = BN_CTX_get(ctx)) == NULL)
754 goto err;
755 if ((M = BN_CTX_get(ctx)) == NULL)
756 goto err;
757 if ((Y = BN_CTX_get(ctx)) == NULL)
758 goto err;
759 if ((T = BN_CTX_get(ctx)) == NULL)
760 goto err;
761
762 BN_one(X);
763 BN_zero(Y);
764 if (BN_copy(B, a) == NULL)
765 goto err;
766 if (BN_copy(A, n) == NULL)
767 goto err;
768 A->neg = 0;
769
770 if (B->neg || (BN_ucmp(B, A) >= 0)) {
771 /* Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked,
772 * BN_div_no_branch will be called eventually.
773 */
774 pB = &local_B;
775 BN_with_flags(pB, B, BN_FLG_CONSTTIME);
776 if (!BN_nnmod(B, pB, A, ctx))
777 goto err;
778 }
779 sign = -1;
780 /* From B = a mod |n|, A = |n| it follows that
781 *
782 * 0 <= B < A,
783 * -sign*X*a == B (mod |n|),
784 * sign*Y*a == A (mod |n|).
785 */
786
787 while (!BN_is_zero(B)) {
788 BIGNUM *tmp;
789
790 /*
791 * 0 < B < A,
792 * (*) -sign*X*a == B (mod |n|),
793 * sign*Y*a == A (mod |n|)
794 */
795
796 /* Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked,
797 * BN_div_no_branch will be called eventually.
798 */
799 pA = &local_A;
800 BN_with_flags(pA, A, BN_FLG_CONSTTIME);
801
802 /* (D, M) := (A/B, A%B) ... */
803 if (!BN_div_ct(D, M, pA, B, ctx))
804 goto err;
805
806 /* Now
807 * A = D*B + M;
808 * thus we have
809 * (**) sign*Y*a == D*B + M (mod |n|).
810 */
811 tmp = A; /* keep the BIGNUM object, the value does not matter */
812
813 /* (A, B) := (B, A mod B) ... */
814 A = B;
815 B = M;
816 /* ... so we have 0 <= B < A again */
817
818 /* Since the former M is now B and the former B is now A,
819 * (**) translates into
820 * sign*Y*a == D*A + B (mod |n|),
821 * i.e.
822 * sign*Y*a - D*A == B (mod |n|).
823 * Similarly, (*) translates into
824 * -sign*X*a == A (mod |n|).
825 *
826 * Thus,
827 * sign*Y*a + D*sign*X*a == B (mod |n|),
828 * i.e.
829 * sign*(Y + D*X)*a == B (mod |n|).
830 *
831 * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at
832 * -sign*X*a == B (mod |n|),
833 * sign*Y*a == A (mod |n|).
834 * Note that X and Y stay non-negative all the time.
835 */
836
837 if (!BN_mul(tmp, D, X, ctx))
838 goto err;
839 if (!BN_add(tmp, tmp, Y))
840 goto err;
841
842 M = Y; /* keep the BIGNUM object, the value does not matter */
843 Y = X;
844 X = tmp;
845 sign = -sign;
846 }
847
848 /*
849 * The while loop (Euclid's algorithm) ends when
850 * A == gcd(a,n);
851 */
852
853 if (!BN_copy(R, A))
854 goto err;
855 ret = R;
856err:
857 if ((ret == NULL) && (in == NULL))
858 BN_free(R);
859 BN_CTX_end(ctx);
860 bn_check_top(ret);
861 return (ret);
862}
diff --git a/src/lib/libcrypto/bn/bn_lcl.h b/src/lib/libcrypto/bn/bn_lcl.h
index 75c35499a8..c010410cd1 100644
--- a/src/lib/libcrypto/bn/bn_lcl.h
+++ b/src/lib/libcrypto/bn/bn_lcl.h
@@ -1,4 +1,4 @@
1/* $OpenBSD: bn_lcl.h,v 1.26 2017/01/21 11:00:46 beck Exp $ */ 1/* $OpenBSD: bn_lcl.h,v 1.27 2017/01/25 06:15:44 beck Exp $ */
2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3 * All rights reserved. 3 * All rights reserved.
4 * 4 *
@@ -603,5 +603,7 @@ BIGNUM *BN_mod_inverse_ct(BIGNUM *ret, const BIGNUM *a, const BIGNUM *n,
603 BN_CTX *ctx); 603 BN_CTX *ctx);
604BIGNUM *BN_mod_inverse_nonct(BIGNUM *ret, const BIGNUM *a, const BIGNUM *n, 604BIGNUM *BN_mod_inverse_nonct(BIGNUM *ret, const BIGNUM *a, const BIGNUM *n,
605 BN_CTX *ctx); 605 BN_CTX *ctx);
606int BN_gcd_ct(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx);
607int BN_gcd_nonct(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx);
606__END_HIDDEN_DECLS 608__END_HIDDEN_DECLS
607#endif 609#endif
diff --git a/src/lib/libcrypto/bn/bn_x931p.c b/src/lib/libcrypto/bn/bn_x931p.c
index 84c998d4e1..45b61c9128 100644
--- a/src/lib/libcrypto/bn/bn_x931p.c
+++ b/src/lib/libcrypto/bn/bn_x931p.c
@@ -1,4 +1,4 @@
1/* $OpenBSD: bn_x931p.c,v 1.9 2017/01/21 11:00:46 beck Exp $ */ 1/* $OpenBSD: bn_x931p.c,v 1.10 2017/01/25 06:15:44 beck Exp $ */
2/* Written by Dr Stephen N Henson (steve@openssl.org) for the OpenSSL 2/* Written by Dr Stephen N Henson (steve@openssl.org) for the OpenSSL
3 * project 2005. 3 * project 2005.
4 */ 4 */
@@ -171,7 +171,7 @@ BN_X931_derive_prime_ex(BIGNUM *p, BIGNUM *p1, BIGNUM *p2, const BIGNUM *Xp,
171 goto err; 171 goto err;
172 if (!BN_sub_word(pm1, 1)) 172 if (!BN_sub_word(pm1, 1))
173 goto err; 173 goto err;
174 if (!BN_gcd(t, pm1, e, ctx)) 174 if (!BN_gcd_ct(t, pm1, e, ctx))
175 goto err; 175 goto err;
176 if (BN_is_one(t) 176 if (BN_is_one(t)
177 /* X9.31 specifies 8 MR and 1 Lucas test or any prime test 177 /* X9.31 specifies 8 MR and 1 Lucas test or any prime test
diff --git a/src/lib/libcrypto/rsa/rsa_chk.c b/src/lib/libcrypto/rsa/rsa_chk.c
index 91616d17cb..dd9104f304 100644
--- a/src/lib/libcrypto/rsa/rsa_chk.c
+++ b/src/lib/libcrypto/rsa/rsa_chk.c
@@ -1,4 +1,4 @@
1/* $OpenBSD: rsa_chk.c,v 1.11 2017/01/21 11:00:47 beck Exp $ */ 1/* $OpenBSD: rsa_chk.c,v 1.12 2017/01/25 06:15:44 beck Exp $ */
2/* ==================================================================== 2/* ====================================================================
3 * Copyright (c) 1999 The OpenSSL Project. All rights reserved. 3 * Copyright (c) 1999 The OpenSSL Project. All rights reserved.
4 * 4 *
@@ -129,7 +129,7 @@ RSA_check_key(const RSA *key)
129 ret = -1; 129 ret = -1;
130 goto err; 130 goto err;
131 } 131 }
132 r = BN_gcd(m, i, j, ctx); 132 r = BN_gcd_ct(m, i, j, ctx);
133 if (!r) { 133 if (!r) {
134 ret = -1; 134 ret = -1;
135 goto err; 135 goto err;
diff --git a/src/lib/libcrypto/rsa/rsa_gen.c b/src/lib/libcrypto/rsa/rsa_gen.c
index 300b292b7b..e09dccb4a8 100644
--- a/src/lib/libcrypto/rsa/rsa_gen.c
+++ b/src/lib/libcrypto/rsa/rsa_gen.c
@@ -1,4 +1,4 @@
1/* $OpenBSD: rsa_gen.c,v 1.20 2017/01/21 11:00:47 beck Exp $ */ 1/* $OpenBSD: rsa_gen.c,v 1.21 2017/01/25 06:15:44 beck Exp $ */
2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3 * All rights reserved. 3 * All rights reserved.
4 * 4 *
@@ -138,7 +138,7 @@ rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb)
138 goto err; 138 goto err;
139 if (!BN_sub(r2, rsa->p, BN_value_one())) 139 if (!BN_sub(r2, rsa->p, BN_value_one()))
140 goto err; 140 goto err;
141 if (!BN_gcd(r1, r2, rsa->e, ctx)) 141 if (!BN_gcd_ct(r1, r2, rsa->e, ctx))
142 goto err; 142 goto err;
143 if (BN_is_one(r1)) 143 if (BN_is_one(r1))
144 break; 144 break;
@@ -168,7 +168,7 @@ rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb)
168 } 168 }
169 if (!BN_sub(r2, rsa->q, BN_value_one())) 169 if (!BN_sub(r2, rsa->q, BN_value_one()))
170 goto err; 170 goto err;
171 if (!BN_gcd(r1, r2, rsa->e, ctx)) 171 if (!BN_gcd_ct(r1, r2, rsa->e, ctx))
172 goto err; 172 goto err;
173 if (BN_is_one(r1)) 173 if (BN_is_one(r1))
174 break; 174 break;
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-21 15:56:27 +0000