aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--checks/ec_tests.cpp214
-rw-r--r--checks/pk_bench.cpp6
-rw-r--r--doc/credits.txt5
-rw-r--r--doc/license.txt1
-rw-r--r--doc/log.txt5
-rw-r--r--src/math/bigint/bigint.h6
-rw-r--r--src/math/bigint/mp_core.h10
-rw-r--r--src/math/numbertheory/curve_gfp.h49
-rw-r--r--src/math/numbertheory/point_gfp.cpp258
-rw-r--r--src/math/numbertheory/point_gfp.h53
-rw-r--r--src/pubkey/pubkey.cpp11
-rw-r--r--src/pubkey/pubkey.h12
12 files changed, 345 insertions, 285 deletions
diff --git a/checks/ec_tests.cpp b/checks/ec_tests.cpp
index 485639e76..d86645dbc 100644
--- a/checks/ec_tests.cpp
+++ b/checks/ec_tests.cpp
@@ -6,19 +6,12 @@
#include <botan/build.h>
-#include "validate.h"
-
-#if !defined(BOTAN_HAS_ECDSA)
-
-void do_ec_tests(RandomNumberGenerator&) { return; }
-
-#else
-
#include <botan/bigint.h>
#include <botan/numthry.h>
#include <botan/curve_gfp.h>
#include <botan/point_gfp.h>
#include <botan/ecdsa.h>
+#include <botan/oids.h>
using namespace Botan;
@@ -26,7 +19,7 @@ using namespace Botan;
#include <assert.h>
#include "getopt.h"
-
+#include "validate.h"
#include "common.h"
#define CHECK_MESSAGE(expr, print) try { if(!(expr)) std::cout << print << "\n"; } catch(std::exception& e) { std::cout << __FUNCTION__ << ": " << e.what() << "\n"; }
@@ -34,6 +27,12 @@ using namespace Botan;
namespace {
+std::ostream& operator<<(std::ostream& out, const PointGFp& point)
+ {
+ out << "(" << point.get_affine_x() << " " << point.get_affine_y() << ")";
+ return out;
+ }
+
PointGFp create_random_point(RandomNumberGenerator& rng,
const CurveGFp& curve)
{
@@ -63,8 +62,6 @@ void test_point_turn_on_sp_red_mul()
std::cout << "." << std::flush;
// setting up expected values
- std::string test_str("test");
- BigInt test_bi(3);
BigInt exp_Qx(std::string("466448783855397898016055842232266600516272889280"));
BigInt exp_Qy(std::string("1110706324081757720403272427311003102474457754220"));
BigInt exp_Qz(1);
@@ -87,13 +84,13 @@ void test_point_turn_on_sp_red_mul()
BigInt d("459183204582304");
PointGFp r1 = d * p_G;
- CHECK(r1.get_affine_x() != BigInt("0"));
+ CHECK(r1.get_affine_x() != 0);
PointGFp p_G2(p_G);
PointGFp r2 = d * p_G2;
CHECK_MESSAGE(r1 == r2, "error with point mul after extra turn on sp red mul");
- CHECK(r1.get_affine_x() != BigInt("0"));
+ CHECK(r1.get_affine_x() != 0);
PointGFp p_r1 = r1;
PointGFp p_r2 = r2;
@@ -101,15 +98,15 @@ void test_point_turn_on_sp_red_mul()
p_r1 *= 2;
p_r2 *= 2;
CHECK_MESSAGE(p_r1.get_affine_x() == p_r2.get_affine_x(), "error with mult2 after extra turn on sp red mul");
- CHECK(p_r1.get_affine_x() != BigInt("0"));
- CHECK(p_r2.get_affine_x() != BigInt("0"));
+ CHECK(p_r1.get_affine_x() != 0);
+ CHECK(p_r2.get_affine_x() != 0);
r1 *= 2;
r2 *= 2;
CHECK_MESSAGE(r1 == r2, "error with mult2 after extra turn on sp red mul");
CHECK_MESSAGE(r1.get_affine_x() == r2.get_affine_x(), "error with mult2 after extra turn on sp red mul");
- CHECK(r1.get_affine_x() != BigInt("0"));
+ CHECK(r1.get_affine_x() != 0);
r1 += p_G;
r2 += p_G2;
@@ -129,10 +126,6 @@ void test_coordinates()
{
std::cout << "." << std::flush;
- //Setting up expected values
- BigInt exp_x(std::string("1340569834321789103897171369812910390864714275730"));
- BigInt exp_y(std::string("1270827321510686389126940426305655825361326281787"));
- BigInt exp_z(std::string("407040228325808215747982915914693784055965283940"));
BigInt exp_affine_x(std::string("16984103820118642236896513183038186009872590470"));
BigInt exp_affine_y(std::string("1373093393927139016463695321221277758035357890939"));
@@ -156,13 +149,6 @@ void test_coordinates()
PointGFp point_exp(secp160r1, exp_affine_x, exp_affine_y);
point_exp.check_invariants();
- if(p1.get_x() != exp_x)
- std::cout << p1.get_x() << " != " << exp_x << "\n";
- if(p1.get_y() != exp_y)
- std::cout << p1.get_y() << " != " << exp_y << "\n";
- if(p1.get_z() != exp_z)
- std::cout << p1.get_z() << " != " << exp_z << "\n";
-
CHECK_MESSAGE( p1.get_affine_x() == exp_affine_x, " p1_x = " << p1.get_affine_x() << "\n" << "exp_x = " << exp_affine_x << "\n");
CHECK_MESSAGE( p1.get_affine_y() == exp_affine_y, " p1_y = " << p1.get_affine_y() << "\n" << "exp_y = " << exp_affine_y << "\n");
}
@@ -184,7 +170,6 @@ void test_point_transformation ()
{
std::cout << "." << std::flush;
-
// get a vailid point
EC_Domain_Params dom_pars(OID("1.3.132.0.8"));
PointGFp p = dom_pars.get_base_point();
@@ -192,60 +177,33 @@ void test_point_transformation ()
// get a copy
PointGFp q = p;
- //turn on montg.
- CHECK_MESSAGE( p.get_x() == q.get_x(), "projective_x changed while turning on montg.!");
- CHECK_MESSAGE( p.get_y() == q.get_y(), "projective_y changed while turning on montg.!");
- CHECK_MESSAGE( p.get_z() == q.get_z(), "projective_z changed while turning on montg.!");
- CHECK_MESSAGE( p.get_affine_x() == q.get_affine_x(), "affine_x changed while turning on montg.!");
- CHECK_MESSAGE( p.get_affine_y() == q.get_affine_y(), "affine_y changed while turning on montg.!");
+ CHECK_MESSAGE( p.get_affine_x() == q.get_affine_x(), "affine_x changed during copy");
+ CHECK_MESSAGE( p.get_affine_y() == q.get_affine_y(), "affine_y changed during copy");
}
void test_point_mult ()
{
std::cout << "." << std::flush;
- // setting up expected values
- std::string test_str("test");
- BigInt test_bi(3);
- BigInt exp_Qx(std::string("466448783855397898016055842232266600516272889280"));
- BigInt exp_Qy(std::string("1110706324081757720403272427311003102474457754220"));
- BigInt exp_Qz(1);
+ EC_Domain_Params secp160r1(OIDS::lookup("secp160r1"));
+
+ const CurveGFp& curve = secp160r1.get_curve();
- // performing calculation to test
- std::string p_secp = "ffffffffffffffffffffffffffffffff7fffffff";
- std::string a_secp = "ffffffffffffffffffffffffffffffff7ffffffc";
- std::string b_secp = "1c97befc54bd7a8b65acf89f81d4d4adc565fa45";
std::string G_secp_comp = "024a96b5688ef573284664698968c38bb913cbfc82";
- SecureVector<byte> sv_p_secp = decode_hex(p_secp);
- SecureVector<byte> sv_a_secp = decode_hex(a_secp);
- SecureVector<byte> sv_b_secp = decode_hex(b_secp);
SecureVector<byte> sv_G_secp_comp = decode_hex(G_secp_comp);
- BigInt bi_p_secp = BigInt::decode(sv_p_secp.begin(), sv_p_secp.size());
- BigInt bi_a_secp = BigInt::decode(sv_a_secp.begin(), sv_a_secp.size());
- BigInt bi_b_secp = BigInt::decode(sv_b_secp.begin(), sv_b_secp.size());
- CurveGFp secp160r1(bi_p_secp, bi_a_secp, bi_b_secp);
- PointGFp p_G = OS2ECP(sv_G_secp_comp, secp160r1);
+ PointGFp p_G = OS2ECP(sv_G_secp_comp, curve);
- SecureVector<byte> sv_G_dec = EC2OSP(p_G,0x01);
- std::string str_d_U = "aa374ffc3ce144e6b073307972cb6d57b2a4e982";
- SecureVector<byte> sv_d_U = decode_hex(str_d_U);
- BigInt d_U = BigInt::decode(sv_d_U.begin(), sv_d_U.size());
+ BigInt d_U("0xaa374ffc3ce144e6b073307972cb6d57b2a4e982");
PointGFp Q_U = d_U * p_G;
- CHECK( Q_U.get_x() == exp_Qx);
- CHECK( Q_U.get_y() == exp_Qy);
- CHECK( Q_U.get_z() == exp_Qz);
+
+ CHECK(Q_U.get_affine_x() == BigInt("466448783855397898016055842232266600516272889280"));
+ CHECK(Q_U.get_affine_y() == BigInt("1110706324081757720403272427311003102474457754220"));
}
void test_point_negative()
{
std::cout << "." << std::flush;
- //Setting up expected values
- BigInt exp_p1_x(std::string("1340569834321789103897171369812910390864714275730"));
- BigInt exp_p1_y(std::string("1270827321510686389126940426305655825361326281787"));
- BigInt exp_p1_neg_x(std::string("1340569834321789103897171369812910390864714275730"));
- BigInt exp_p1_neg_y(std::string("190674315820216529076744406410627194292458777540"));
-
// performing calculation to test
std::string p_secp = "ffffffffffffffffffffffffffffffff7fffffff";
std::string a_secp = "ffffffffffffffffffffffffffffffff7ffffffc";
@@ -263,17 +221,13 @@ void test_point_negative()
PointGFp p1 = p_G *= 2;
- CHECK( p1.get_x() == exp_p1_x);
- CHECK( p1.get_y() == exp_p1_y);
- //cout << "p1.y_proj = " << p1.get_y() << "\n";
+ CHECK(p1.get_affine_x() == BigInt("16984103820118642236896513183038186009872590470"));
+ CHECK(p1.get_affine_y() == BigInt("1373093393927139016463695321221277758035357890939"));
+
PointGFp p1_neg = p1.negate();
- //cout << "p1_neg.y_proj = " << p1_neg.get_y() << "\n";
- //p1.negate();
- BigInt calc_y_value = p1_neg.get_y();
- BigInt calc_z_value = p1_neg.get_z();
- CHECK( p1_neg.get_x() == exp_p1_neg_x);
- CHECK_MESSAGE( calc_y_value == exp_p1_neg_y, "calc_y_value = " << calc_y_value << "\nexp_p1_neg_v = " << exp_p1_neg_y);
- //CHECK_MESSAGE( calc_z_value == exp_p1_neg_y, "calc_y_value = " << calc_y_value << "\nexp_p1_neg_v = " << exp_p1_neg_y);
+
+ CHECK(p1_neg.get_affine_x() == BigInt("16984103820118642236896513183038186009872590470"));
+ CHECK(p1_neg.get_affine_y() == BigInt("88408243403763901739989511495005261618427168388"));
}
void test_zeropoint()
@@ -288,11 +242,10 @@ void test_zeropoint()
BigInt bi_b_secp("0x1c97befc54bd7a8b65acf89f81d4d4adc565fa45");
CurveGFp secp160r1(bi_p_secp, bi_a_secp, bi_b_secp);
- BigInt bi_p1_xval ("1340569834321789103897171369812910390864714275730");
- BigInt bi_p1_yval ("1270827321510686389126940426305655825361326281787");
- BigInt bi_p1_zval ("407040228325808215747982915914693784055965283940");
+ PointGFp p1(secp160r1,
+ BigInt("16984103820118642236896513183038186009872590470"),
+ BigInt("1373093393927139016463695321221277758035357890939"));
- PointGFp p1(secp160r1, bi_p1_xval, bi_p1_yval, bi_p1_zval);
p1.check_invariants();
p1 -= p1;
@@ -330,8 +283,6 @@ void test_calc_with_zeropoint()
{
std::cout << "." << std::flush;
-
-
std::string G_secp_comp = "024a96b5688ef573284664698968c38bb913cbfc82";
SecureVector<byte> sv_G_secp_comp = decode_hex ( G_secp_comp );
BigInt bi_p_secp("0xffffffffffffffffffffffffffffffff7fffffff");
@@ -339,11 +290,9 @@ void test_calc_with_zeropoint()
BigInt bi_b_secp("0x1c97befc54bd7a8b65acf89f81d4d4adc565fa45");
CurveGFp curve(bi_p_secp, bi_a_secp, bi_b_secp);
- BigInt bi_p1_xval ("1340569834321789103897171369812910390864714275730");
- BigInt bi_p1_yval ("1270827321510686389126940426305655825361326281787");
- BigInt bi_p1_zval ("407040228325808215747982915914693784055965283940");
-
- PointGFp p(curve, bi_p1_xval, bi_p1_yval, bi_p1_zval);
+ PointGFp p(curve,
+ BigInt("16984103820118642236896513183038186009872590470"),
+ BigInt("1373093393927139016463695321221277758035357890939"));
p.check_invariants();
CHECK_MESSAGE( !p.is_zero(), "created is zeropoint, shouldn't be!");
@@ -365,11 +314,6 @@ void test_add_point()
{
std::cout << "." << std::flush;
- //Setting up expected values
- BigInt exp_add_x(std::string("1435263815649099438763411093143066583800699119469"));
- BigInt exp_add_y(std::string("1300090790154238148372364036549849084558669436512"));
- BigInt exp_add_z(std::string("562006223742588575209908669014372619804457947208"));
-
// precalculation
std::string p_secp = "ffffffffffffffffffffffffffffffff7fffffff";
std::string a_secp = "ffffffffffffffffffffffffffffffff7ffffffc";
@@ -388,9 +332,12 @@ void test_add_point()
PointGFp p0 = p_G;
PointGFp p1 = p_G *= 2;
- PointGFp expected(secp160r1, exp_add_x, exp_add_y, exp_add_z);
-
p1 += p0;
+
+ PointGFp expected(secp160r1,
+ BigInt("704859595002530890444080436569091156047721708633"),
+ BigInt("1147993098458695153857594941635310323215433166682"));
+
CHECK(p1 == expected);
}
@@ -423,7 +370,10 @@ void test_sub_point()
p1 -= p0;
- PointGFp expected(secp160r1, exp_sub_x, exp_sub_y, exp_sub_z);
+ PointGFp expected(secp160r1,
+ BigInt("425826231723888350446541592701409065913635568770"),
+ BigInt("203520114162904107873991457957346892027982641970"));
+
CHECK(p1 == expected);
}
@@ -453,7 +403,7 @@ void test_mult_point()
PointGFp p0 = p_G;
PointGFp p1 = p_G *= 2;
- p1 *= p0.get_x();
+ p1 *= p0.get_affine_x();
PointGFp expected(secp160r1, exp_mult_x, exp_mult_y);
@@ -464,28 +414,6 @@ void test_basic_operations()
{
std::cout << "." << std::flush;
-
- // set up expected values
- BigInt exp_p1_x(std::string("1340569834321789103897171369812910390864714275730"));
- BigInt exp_p1_y(std::string("1270827321510686389126940426305655825361326281787"));
- BigInt exp_p1_z(std::string("407040228325808215747982915914693784055965283940"));
-
- BigInt exp_p0_x(std::string("425826231723888350446541592701409065913635568770"));
- BigInt exp_p0_y(std::string("203520114162904107873991457957346892027982641970"));
- BigInt exp_p0_z(std::string("1"));
-
- BigInt exp_plus_x(std::string("1435263815649099438763411093143066583800699119469"));
- BigInt exp_plus_y(std::string("1300090790154238148372364036549849084558669436512"));
- BigInt exp_plus_z(std::string("562006223742588575209908669014372619804457947208"));
-
- BigInt exp_minus_x(std::string("112913490230515010376958384252467223283065196552"));
- BigInt exp_minus_y(std::string("143464803917389475471159193867377888720776527730"));
- BigInt exp_minus_z(std::string("562006223742588575209908669014372619804457947208"));
-
- BigInt exp_mult_x(std::string("43638877777452195295055270548491599621118743290"));
- BigInt exp_mult_y(std::string("56841378500012376527163928510402662349220202981"));
- BigInt exp_mult_z(std::string("1"));
-
// precalculation
std::string p_secp = "ffffffffffffffffffffffffffffffff7fffffff";
std::string a_secp = "ffffffffffffffffffffffffffffffff7ffffffc";
@@ -503,37 +431,43 @@ void test_basic_operations()
PointGFp p_G = OS2ECP ( sv_G_secp_comp, secp160r1 );
PointGFp p0 = p_G;
- PointGFp p1 = p_G *= 2;
- // check that all points have correct values
- CHECK( p1.get_x() == exp_p1_x);
- CHECK( p1.get_y() == exp_p1_y);
- CHECK( p1.get_z() == exp_p1_z);
+ PointGFp expected(secp160r1,
+ BigInt("425826231723888350446541592701409065913635568770"),
+ BigInt("203520114162904107873991457957346892027982641970"));
- PointGFp expected(secp160r1, exp_p0_x, exp_p0_y, exp_p0_z);
CHECK(p0 == expected);
+ PointGFp p1 = p_G *= 2;
+
+ CHECK(p1.get_affine_x() == BigInt("16984103820118642236896513183038186009872590470"));
+ CHECK(p1.get_affine_y() == BigInt("1373093393927139016463695321221277758035357890939"));
+
PointGFp simplePlus= p1 + p0;
- PointGFp exp_simplePlus(secp160r1, exp_plus_x, exp_plus_y, exp_plus_z);
- CHECK(simplePlus == exp_simplePlus);
+ PointGFp exp_simplePlus(secp160r1,
+ BigInt("704859595002530890444080436569091156047721708633"),
+ BigInt("1147993098458695153857594941635310323215433166682"));
+ if(simplePlus != exp_simplePlus)
+ std::cout << simplePlus << " != " << exp_simplePlus << "\n";
PointGFp simpleMinus= p1 - p0;
- PointGFp exp_simpleMinus(secp160r1, exp_minus_x, exp_minus_y, exp_minus_z);
+ PointGFp exp_simpleMinus(secp160r1,
+ BigInt("425826231723888350446541592701409065913635568770"),
+ BigInt("203520114162904107873991457957346892027982641970"));
+
CHECK(simpleMinus == exp_simpleMinus);
PointGFp simpleMult= p1 * 123456789;
- CHECK( simpleMult.get_x() == exp_mult_x);
- CHECK( simpleMult.get_y() == exp_mult_y);
- CHECK( simpleMult.get_z() == exp_mult_z);
+
+ CHECK(simpleMult.get_affine_x() == BigInt("43638877777452195295055270548491599621118743290"));
+ CHECK(simpleMult.get_affine_y() == BigInt("56841378500012376527163928510402662349220202981"));
// check that all initial points hasn't changed
- CHECK( p1.get_x() == exp_p1_x);
- CHECK( p1.get_y() == exp_p1_y);
- CHECK( p1.get_z() == exp_p1_z);
+ CHECK(p1.get_affine_x() == BigInt("16984103820118642236896513183038186009872590470"));
+ CHECK(p1.get_affine_y() == BigInt("1373093393927139016463695321221277758035357890939"));
- CHECK( p0.get_x() == exp_p0_x);
- CHECK( p0.get_y() == exp_p0_y);
- CHECK( p0.get_z() == exp_p0_z);
+ CHECK(p0.get_affine_x() == BigInt("425826231723888350446541592701409065913635568770"));
+ CHECK(p0.get_affine_y() == BigInt("203520114162904107873991457957346892027982641970"));
}
void test_enc_dec_compressed_160()
@@ -760,11 +694,9 @@ void test_more_zeropoint()
BigInt bi_b("0x1c97befc54bd7a8b65acf89f81d4d4adc565fa45");
CurveGFp curve(bi_p, bi_a, bi_b);
- BigInt bi_p1_xval ("1340569834321789103897171369812910390864714275730");
- BigInt bi_p1_yval ("1270827321510686389126940426305655825361326281787");
- BigInt bi_p1_zval ("407040228325808215747982915914693784055965283940");
-
- PointGFp p1(curve, bi_p1_xval, bi_p1_yval, bi_p1_zval);
+ PointGFp p1(curve,
+ BigInt("16984103820118642236896513183038186009872590470"),
+ BigInt("1373093393927139016463695321221277758035357890939"));
p1.check_invariants();
PointGFp minus_p1 = -p1;
@@ -881,5 +813,3 @@ void do_ec_tests(RandomNumberGenerator& rng)
std::cout << std::endl;
}
-#endif
-
diff --git a/checks/pk_bench.cpp b/checks/pk_bench.cpp
index a09d3a090..6893917fd 100644
--- a/checks/pk_bench.cpp
+++ b/checks/pk_bench.cpp
@@ -296,7 +296,9 @@ void benchmark_ecdsa(RandomNumberGenerator& rng,
const char* domains[] = { "1.3.132.0.6", // secp112r1
"1.3.132.0.28", // secp128r1
"1.3.132.0.30", // secp160r2
+ "1.2.840.10045.3.1.1", // secp192r1
"1.3.132.0.33", // secp224r1
+ "1.2.840.10045.3.1.7", // secp256r1
"1.3.132.0.34", // secp384r1
"1.3.132.0.35", // secp512r1
NULL };
@@ -310,7 +312,7 @@ void benchmark_ecdsa(RandomNumberGenerator& rng,
u32bit hashbits = pbits;
- if(hashbits < 160)
+ if(hashbits <= 192)
hashbits = 160;
if(hashbits == 521)
hashbits = 512;
@@ -328,7 +330,7 @@ void benchmark_ecdsa(RandomNumberGenerator& rng,
ECDSA_PrivateKey key(rng, params);
keygen_timer.stop();
- PK_Signer sig(key, padding);
+ PK_Signer sig(key, padding, IEEE_1363, DISABLE_FAULT_PROTECTION);
PK_Verifier ver(key, padding);
benchmark_sig_ver(ver, sig, verify_timer,
diff --git a/doc/credits.txt b/doc/credits.txt
index 67b318842..63ceae483 100644
--- a/doc/credits.txt
+++ b/doc/credits.txt
@@ -20,6 +20,9 @@ N: Martin Doering
E: [email protected]
D: GF(p) arithmetic
+N: Olivier de Gaalon
+D: SQLite encryption codec (src/wrap/sqlite)
+
N: Matthew Gregan
D: Binary file I/O support, allocator fixes
@@ -64,7 +67,7 @@ D: GP(p) arithmetic
N: Vaclav Ovsik
E: [email protected]
-D: Perl XS module
+D: Perl XS module (src/wrap/perl-xs)
N: Luca Piccarreta
E: [email protected]
diff --git a/doc/license.txt b/doc/license.txt
index 599bf7f63..6d9143ee1 100644
--- a/doc/license.txt
+++ b/doc/license.txt
@@ -3,6 +3,7 @@ Botan (http://botan.randombit.net/) is distributed under these terms:
Copyright (C) 1999-2010 Jack Lloyd
2001 Peter J Jones
2004-2007 Justin Karneges
+ 2004 Vaclav Ovsik
2005 Matthew Gregan
2005-2006 Matt Johnston
2006 Luca Piccarreta
diff --git a/doc/log.txt b/doc/log.txt
index 042fe6f17..3a37e3a5e 100644
--- a/doc/log.txt
+++ b/doc/log.txt
@@ -1,5 +1,10 @@
* 1.9.5-dev, ????-??-??
+ - Numerous ECC optimizations
+ - Allow PK_Signer's fault protection checks to be toggled off
+ - Remove all runtime options
+ - Fix crash in MemoryRegion if Allocator::get failed
+ - Fix small compilation problem on FreeBSD
* 1.9.4, 2010-03-09
- Add the Ajisai SSLv3/TLSv1.0 implementation
diff --git a/src/math/bigint/bigint.h b/src/math/bigint/bigint.h
index 2612850c3..3756da51f 100644
--- a/src/math/bigint/bigint.h
+++ b/src/math/bigint/bigint.h
@@ -462,11 +462,11 @@ class BOTAN_DLL BigInt
BigInt(RandomNumberGenerator& rng, u32bit bits);
/**
- * Create BigInt from unsigned 32 bit integer value and an
- * also specify the sign of the value
+ * Create BigInt of specified size, all zeros
+ * @param sign the sign
* @param n integer value
*/
- BigInt(Sign, u32bit n);
+ BigInt(Sign sign, u32bit n);
/**
* Create a number of the specified type and size
diff --git a/src/math/bigint/mp_core.h b/src/math/bigint/mp_core.h
index ea27a77a7..a2a89186d 100644
--- a/src/math/bigint/mp_core.h
+++ b/src/math/bigint/mp_core.h
@@ -86,12 +86,12 @@ void bigint_comba_sqr16(word[64], const word[32]);
/*
* High Level Multiplication/Squaring Interfaces
*/
-void bigint_mul(word[], u32bit, word[],
- const word[], u32bit, u32bit,
- const word[], u32bit, u32bit);
+void bigint_mul(word z[], u32bit z_size, word workspace[],
+ const word x[], u32bit x_size, u32bit x_sw,
+ const word y[], u32bit y_size, u32bit y_sw);
-void bigint_sqr(word[], u32bit, word[],
- const word[], u32bit, u32bit);
+void bigint_sqr(word z[], u32bit z_size, word workspace[],
+ const word x[], u32bit x_size, u32bit x_sw);
}
diff --git a/src/math/numbertheory/curve_gfp.h b/src/math/numbertheory/curve_gfp.h
index de6bed099..a7be8987c 100644
--- a/src/math/numbertheory/curve_gfp.h
+++ b/src/math/numbertheory/curve_gfp.h
@@ -34,29 +34,59 @@ class BOTAN_DLL CurveGFp
* @param b second coefficient
*/
CurveGFp(const BigInt& p, const BigInt& a, const BigInt& b) :
- p(p), a(a), b(b), reducer_p(p) {}
+ p(p), a(a), b(b), reducer_p(p)
+ {
+ r = 1;
+ r <<= p.sig_words() * BOTAN_MP_WORD_BITS;
+
+ r_inv = inverse_mod(r, p);
+
+ p_dash = (((r * r_inv) - 1) / p).word_at(0);
+
+ a_r = reducer_p.multiply(a, r);
+ }
// CurveGFp(const CurveGFp& other) = default;
// CurveGFp& operator=(const CurveGFp& other) = default;
/**
* Get coefficient a
- * @result coefficient a
+ * @return coefficient a
*/
const BigInt& get_a() const { return a; }
/**
* Get coefficient b
- * @result coefficient b
+ * @return coefficient b
*/
const BigInt& get_b() const { return b; }
/**
* Get prime modulus of the field of the curve
- * @result prime modulus of the field of the curve
+ * @return prime modulus of the field of the curve
*/
const BigInt& get_p() const { return p; }
+ /**
+ * @return Montgomery parameter r
+ */
+ const BigInt& get_r() const { return r; }
+
+ /**
+ * @return Montgomery parameter r^-1
+ */
+ const BigInt& get_r_inv() const { return r_inv; }
+
+ /**
+ * @return a * r mod p
+ */
+ const BigInt& get_a_r() const { return a_r; }
+
+ /**
+ * @return Montgomery parameter p-dash
+ */
+ word get_p_dash() const { return p_dash; }
+
const Modular_Reducer& mod_p() const { return reducer_p; }
/**
@@ -68,6 +98,11 @@ class BOTAN_DLL CurveGFp
std::swap(a, other.a);
std::swap(b, other.b);
std::swap(p, other.p);
+ std::swap(reducer_p, other.reducer_p);
+
+ std::swap(r, other.r);
+ std::swap(r_inv, other.r_inv);
+ std::swap(p_dash, other.p_dash);
}
bool operator==(const CurveGFp& other) const
@@ -76,7 +111,13 @@ class BOTAN_DLL CurveGFp
}
private:
+ // Curve parameters
BigInt p, a, b;
+
+ // Montgomery parameters
+ BigInt r, r_inv, a_r;
+ word p_dash;
+
Modular_Reducer reducer_p;
};
diff --git a/src/math/numbertheory/point_gfp.cpp b/src/math/numbertheory/point_gfp.cpp
index db422c8aa..15a979d89 100644
--- a/src/math/numbertheory/point_gfp.cpp
+++ b/src/math/numbertheory/point_gfp.cpp
@@ -9,86 +9,121 @@
#include <botan/point_gfp.h>
#include <botan/numthry.h>
+#include <botan/mp_core.h>
namespace Botan {
-namespace {
+PointGFp::PointGFp(const CurveGFp& curve) :
+ curve(curve),
+ coord_x(0),
+ coord_y(curve.get_r()),
+ coord_z(0)
+ {
+ }
-BigInt decompress_point(bool yMod2,
- const BigInt& x,
- const CurveGFp& curve)
+PointGFp::PointGFp(const CurveGFp& curve, const BigInt& x, const BigInt& y) :
+ curve(curve)
{
- BigInt xpow3 = x * x * x;
+ const Modular_Reducer& mod_p = curve.mod_p();
- BigInt g = curve.get_a() * x;
- g += xpow3;
- g += curve.get_b();
- g = g % curve.get_p();
+ coord_x = mod_p.multiply(curve.get_r(), x);
+ coord_y = mod_p.multiply(curve.get_r(), y);
+ coord_z = mod_p.reduce(curve.get_r());
+ }
- BigInt z = ressol(g, curve.get_p());
+BigInt PointGFp::monty_mult(const BigInt& a, const BigInt& b,
+ MemoryRegion<word>& workspace)
+ {
+ if(a.is_zero() || b.is_zero())
+ return 0;
- if(z < 0)
- throw Illegal_Point("error during decompression");
+ const BigInt& p = curve.get_p();
+ const u32bit p_size = (workspace.size() - 1) / 2;
- if(z.get_bit(0) != yMod2)
- z = curve.get_p() - z;
+ const word p_dash = curve.get_p_dash();
- return z;
- }
+ workspace.clear();
-}
+ bigint_simple_mul(workspace,
+ a.data(), a.sig_words(),
+ b.data(), b.sig_words());
-// arithmetic operators
-PointGFp& PointGFp::operator+=(const PointGFp& rhs)
- {
- if(rhs.is_zero())
- return *this;
+ bigint_monty_redc(workspace, workspace.size(),
+ p.data(), p_size, p_dash);
+
+ BigInt result;
+ result.grow_to(p_size);
+ copy_mem(result.get_reg().begin(), &workspace[p_size], p_size);
+ return result;
+ }
+
+void PointGFp::add(const PointGFp& rhs, MemoryRegion<word>& ws)
+ {
if(is_zero())
{
- *this = rhs;
- return *this;
+ coord_x = rhs.coord_x;
+ coord_y = rhs.coord_y;
+ coord_z = rhs.coord_z;
+ return;
}
+ else if(rhs.is_zero())
+ return;
const Modular_Reducer& mod_p = curve.mod_p();
- BigInt rhs_z2 = mod_p.square(rhs.coord_z);
- BigInt U1 = mod_p.multiply(coord_x, rhs_z2);
- BigInt S1 = mod_p.multiply(coord_y, mod_p.multiply(rhs.coord_z, rhs_z2));
+ BigInt rhs_z2 = monty_mult(rhs.coord_z, rhs.coord_z, ws);
+ BigInt U1 = monty_mult(coord_x, rhs_z2, ws);
+ BigInt S1 = monty_mult(coord_y, monty_mult(rhs.coord_z, rhs_z2, ws), ws);
- BigInt lhs_z2 = mod_p.square(coord_z);
- BigInt U2 = mod_p.multiply(rhs.coord_x, lhs_z2);
- BigInt S2 = mod_p.multiply(rhs.coord_y, mod_p.multiply(coord_z, lhs_z2));
+ BigInt lhs_z2 = monty_mult(coord_z, coord_z, ws);
+ BigInt U2 = monty_mult(rhs.coord_x, lhs_z2, ws);
+ BigInt S2 = monty_mult(rhs.coord_y, monty_mult(coord_z, lhs_z2, ws), ws);
BigInt H = mod_p.reduce(U2 - U1);
+
BigInt r = mod_p.reduce(S2 - S1);
if(H.is_zero())
{
if(r.is_zero())
{
- mult2();
- return *this;
+ mult2(ws);
+ return;
}
*this = PointGFp(curve); // setting myself to zero
- return *this;
+ return;
}
- U2 = mod_p.square(H);
+ U2 = monty_mult(H, H, ws);
+
+ S2 = monty_mult(U2, H, ws);
- S2 = mod_p.multiply(U2, H);
+ U2 = monty_mult(U1, U2, ws);
- U2 = mod_p.multiply(U1, U2);
+ BigInt x = mod_p.reduce(monty_mult(r, r, ws) - S2 - U2*2);
- BigInt x = mod_p.reduce(mod_p.square(r) - S2 - mod_p.multiply(2, U2));
- BigInt y = mod_p.reduce(mod_p.multiply(r, (U2-x)) - mod_p.multiply(S1, S2));
- BigInt z = mod_p.multiply(mod_p.multiply(coord_z, rhs.coord_z), H);
+ U2 -= x;
+ if(U2.is_negative())
+ U2 += curve.get_p();
+
+ BigInt y = monty_mult(r, U2, ws) - monty_mult(S1, S2, ws);
+ if(y.is_negative())
+ y += curve.get_p();
+
+ BigInt z = monty_mult(monty_mult(coord_z, rhs.coord_z, ws), H, ws);
coord_x = x;
coord_y = y;
coord_z = z;
+ }
+// arithmetic operators
+PointGFp& PointGFp::operator+=(const PointGFp& rhs)
+ {
+ SecureVector<word> ws(2 * curve.get_p().sig_words() + 1);
+ add(rhs, ws);
return *this;
}
@@ -106,6 +141,8 @@ PointGFp& PointGFp::operator-=(const PointGFp& rhs)
PointGFp& PointGFp::operator*=(const BigInt& scalar)
{
+ SecureVector<word> ws(2 * curve.get_p().sig_words() + 1);
+
if(scalar.abs() <= 2) // special cases for small values
{
u32bit value = scalar.abs().to_u32bit();
@@ -119,7 +156,7 @@ PointGFp& PointGFp::operator*=(const BigInt& scalar)
}
else if(value == 2)
{
- this->mult2();
+ this->mult2(ws);
if(scalar.is_negative())
this->negate();
}
@@ -133,31 +170,31 @@ PointGFp& PointGFp::operator*=(const BigInt& scalar)
if(scalar.is_negative())
P.negate();
- for(int i = scalar.bits() - 1; i >= 0; --i)
- {
- H.mult2();
- if(scalar.get_bit(i))
- H += P;
- }
+ u32bit scalar_bits = scalar.bits();
+
+ PointGFp P2 = P * 2;
+ PointGFp P3 = P2 + P;
- if(!H.is_zero()) // cannot convert if H == O
+ for(u32bit i = 0; i < scalar_bits - 1; i += 2)
{
- /**
- * Convert H to an equivalent point with z == 1, thus x and y
- * correspond to their affine coordinates
- */
- if(H.coord_z != 1)
- {
- const Modular_Reducer& mod_p = curve.mod_p();
+ u32bit nibble = scalar.get_substring(scalar_bits - i - 2, 2);
- BigInt z_inv = inverse_mod(H.coord_z, curve.get_p());
+ H.mult2(ws);
+ H.mult2(ws);
- BigInt z_inv_2 = mod_p.square(z_inv);
+ if(nibble == 3)
+ H.add(P3, ws);
+ else if(nibble == 2)
+ H.add(P2, ws);
+ else if(nibble == 1)
+ H.add(P, ws);
+ }
- H.coord_x = mod_p.multiply(H.coord_x, z_inv_2);
- H.coord_y = mod_p.multiply(H.coord_y, mod_p.multiply(z_inv, z_inv_2));
- H.coord_z = 1;
- }
+ if(scalar_bits % 2)
+ {
+ H.mult2(ws);
+ if(scalar.get_bit(0))
+ H.add(P, ws);
}
*this = H;
@@ -165,7 +202,7 @@ PointGFp& PointGFp::operator*=(const BigInt& scalar)
}
// *this *= 2
-void PointGFp::mult2()
+void PointGFp::mult2(MemoryRegion<word>& ws)
{
if(is_zero())
return;
@@ -177,22 +214,32 @@ void PointGFp::mult2()
const Modular_Reducer& mod_p = curve.mod_p();
- BigInt y_2 = mod_p.square(coord_y);
+ BigInt y_2 = monty_mult(coord_y, coord_y, ws);
+
+ BigInt S = mod_p.reduce(4 * monty_mult(coord_x, y_2, ws));
+
+ BigInt z4 = monty_mult(coord_z, coord_z, ws);
+ z4 = monty_mult(z4, z4, ws);
- BigInt S = mod_p.multiply(4, mod_p.multiply(coord_x, y_2));
+ BigInt a_z4 = monty_mult(curve.get_a_r(), z4, ws);
- BigInt a_z4 = mod_p.multiply(curve.get_a(),
- mod_p.square(mod_p.square(coord_z)));
+ BigInt M = mod_p.reduce(a_z4 + 3 * monty_mult(coord_x, coord_x, ws));
- BigInt M = mod_p.reduce(a_z4 + 3 * mod_p.square(coord_x));
+ BigInt x = mod_p.reduce(monty_mult(M, M, ws) - 2*S);
- BigInt x = mod_p.reduce(mod_p.square(M) - mod_p.multiply(2, S));
+ BigInt U = mod_p.reduce(monty_mult(y_2, y_2, ws) << 3);
- BigInt U = mod_p.multiply(8, mod_p.square(y_2));
+ S -= x;
+ while(S.is_negative())
+ S += curve.get_p();
- BigInt y = mod_p.reduce(mod_p.multiply(M, S - x) - U);
+ BigInt y = monty_mult(M, S, ws) - U;
+ if(y.is_negative())
+ y += curve.get_p();
- BigInt z = mod_p.multiply(2, mod_p.multiply(coord_y, coord_z));
+ BigInt z = 2 * monty_mult(coord_y, coord_z, ws);
+ if(z >= curve.get_p())
+ z -= curve.get_p();
coord_x = x;
coord_y = y;
@@ -206,8 +253,11 @@ BigInt PointGFp::get_affine_x() const
const Modular_Reducer& mod_p = curve.mod_p();
- BigInt z2 = mod_p.square(coord_z);
- return mod_p.multiply(coord_x, inverse_mod(z2, curve.get_p()));
+ BigInt x = mod_p.multiply(curve.get_r_inv(), coord_x);
+ BigInt z = mod_p.multiply(curve.get_r_inv(), coord_z);
+
+ BigInt z2 = mod_p.square(z);
+ return mod_p.multiply(x, inverse_mod(z2, curve.get_p()));
}
BigInt PointGFp::get_affine_y() const
@@ -217,8 +267,11 @@ BigInt PointGFp::get_affine_y() const
const Modular_Reducer& mod_p = curve.mod_p();
- BigInt z3 = mod_p.cube(coord_z);
- return mod_p.multiply(coord_y, inverse_mod(z3, curve.get_p()));
+ BigInt y = mod_p.multiply(curve.get_r_inv(), coord_y);
+ BigInt z = mod_p.multiply(curve.get_r_inv(), coord_z);
+
+ BigInt z3 = mod_p.cube(z);
+ return mod_p.multiply(y, inverse_mod(z3, curve.get_p()));
}
void PointGFp::check_invariants() const
@@ -235,21 +288,25 @@ void PointGFp::check_invariants() const
const Modular_Reducer& mod_p = curve.mod_p();
- BigInt y2 = mod_p.square(coord_y);
- BigInt x3 = mod_p.cube(coord_x);
+ BigInt x = mod_p.multiply(curve.get_r_inv(), coord_x);
+ BigInt y = mod_p.multiply(curve.get_r_inv(), coord_y);
+ BigInt z = mod_p.multiply(curve.get_r_inv(), coord_z);
+
+ BigInt y2 = mod_p.square(y);
+ BigInt x3 = mod_p.cube(x);
- BigInt ax = mod_p.multiply(coord_x, curve.get_a());
+ BigInt ax = mod_p.multiply(x, curve.get_a());
- if(coord_z == 1)
+ if(z == 1)
{
if(mod_p.reduce(x3 + ax + curve.get_b()) != y2)
throw Illegal_Point("Invalid ECP point: y^2 != x^3 + a*x + b");
}
- BigInt z2 = mod_p.square(coord_z);
- BigInt z3 = mod_p.multiply(coord_z, z2);
+ BigInt z2 = mod_p.square(z);
+ BigInt z3 = mod_p.multiply(z, z2);
- BigInt ax_z4 = mod_p.multiply(mod_p.multiply(z3, coord_z), ax);
+ BigInt ax_z4 = mod_p.multiply(mod_p.multiply(z3, z), ax);
BigInt b_z6 = mod_p.multiply(curve.get_b(), mod_p.square(z3));
@@ -268,10 +325,15 @@ void PointGFp::swap(PointGFp& other)
bool PointGFp::operator==(const PointGFp& other) const
{
- return (coord_x == other.coord_x &&
- coord_y == other.coord_y &&
- coord_z == other.coord_z &&
- get_curve() == other.get_curve());
+ if(get_curve() != other.get_curve())
+ return false;
+
+ // If this is zero, only equal if other is also zero
+ if(is_zero())
+ return other.is_zero();
+
+ return (get_affine_x() == other.get_affine_x() &&
+ get_affine_y() == other.get_affine_y());
}
// encoding and decoding
@@ -326,6 +388,32 @@ SecureVector<byte> EC2OSP(const PointGFp& point, byte format)
throw Invalid_Argument("illegal point encoding format specification");
}
+namespace {
+
+BigInt decompress_point(bool yMod2,
+ const BigInt& x,
+ const CurveGFp& curve)
+ {
+ BigInt xpow3 = x * x * x;
+
+ BigInt g = curve.get_a() * x;
+ g += xpow3;
+ g += curve.get_b();
+ g = g % curve.get_p();
+
+ BigInt z = ressol(g, curve.get_p());
+
+ if(z < 0)
+ throw Illegal_Point("error during decompression");
+
+ if(z.get_bit(0) != yMod2)
+ z = curve.get_p() - z;
+
+ return z;
+ }
+
+}
+
PointGFp OS2ECP(const byte data[], u32bit data_len,
const CurveGFp& curve)
{
diff --git a/src/math/numbertheory/point_gfp.h b/src/math/numbertheory/point_gfp.h
index 2f31421fc..eaebccf49 100644
--- a/src/math/numbertheory/point_gfp.h
+++ b/src/math/numbertheory/point_gfp.h
@@ -46,32 +46,18 @@ class BOTAN_DLL PointGFp
PointGFp() {}
/**
- * Construct the point O
+ * Construct the zero point
* @param curve The base curve
*/
- PointGFp(const CurveGFp& curve) :
- curve(curve), coord_x(0), coord_y(1), coord_z(0) {}
+ PointGFp(const CurveGFp& curve);
/**
- * Construct a point given its affine coordinates
+ * Construct a point from its affine coordinates
* @param curve the base curve
* @param x affine x coordinate
* @param y affine y coordinate
*/
- PointGFp(const CurveGFp& curve,
- const BigInt& x, const BigInt& y) :
- curve(curve), coord_x(x), coord_y(y), coord_z(1) {}
-
- /**
- * Construct a point given its jacobian projective coordinates
- * @param curve the base curve
- * @param x jacobian projective x coordinate
- * @param y jacobian projective y coordinate
- * @param z jacobian projective z coordinate
- */
- PointGFp(const CurveGFp& curve,
- const BigInt& x, const BigInt& y, const BigInt& z) :
- curve(curve), coord_x(x), coord_y(y), coord_z(z) {}
+ PointGFp(const CurveGFp& curve, const BigInt& x, const BigInt& y);
//PointGFp(const PointGFp& other) = default;
//PointGFp& operator=(const PointGFp& other) = default;
@@ -129,24 +115,6 @@ class BOTAN_DLL PointGFp
BigInt get_affine_y() const;
/**
- * get the jacobian projective x coordinate
- * @result jacobian projective x coordinate
- */
- const BigInt& get_x() const { return coord_x; }
-
- /**
- * get the jacobian projective y coordinate
- * @result jacobian projective y coordinate
- */
- const BigInt& get_y() const { return coord_y; }
-
- /**
- * get the jacobian projective z coordinate
- * @result jacobian projective z coordinate
- */
- const BigInt& get_z() const { return coord_z; }
-
- /**
* Is this the point at infinity?
* @result true, if this point is at infinity, false otherwise.
*/
@@ -173,9 +141,20 @@ class BOTAN_DLL PointGFp
bool operator==(const PointGFp& other) const;
private:
/**
+ * Montgomery multiplication/reduction
+ */
+ BigInt monty_mult(const BigInt& x, const BigInt& y,
+ MemoryRegion<word>& workspace);
+
+ /**
+ * Point addition
+ */
+ void add(const PointGFp& other, MemoryRegion<word>& workspace);
+
+ /**
* Point doubling
*/
- void mult2();
+ void mult2(MemoryRegion<word>& workspace);
CurveGFp curve;
BigInt coord_x, coord_y, coord_z;
diff --git a/src/pubkey/pubkey.cpp b/src/pubkey/pubkey.cpp
index 751f20583..abdf4ee55 100644
--- a/src/pubkey/pubkey.cpp
+++ b/src/pubkey/pubkey.cpp
@@ -117,7 +117,8 @@ SecureVector<byte> PK_Decryptor_EME::dec(const byte msg[],
*/
PK_Signer::PK_Signer(const Private_Key& key,
const std::string& emsa_name,
- Signature_Format format)
+ Signature_Format format,
+ Fault_Protection prot)
{
Algorithm_Factory::Engine_Iterator i(global_state().algorithm_factory());
@@ -129,14 +130,14 @@ PK_Signer::PK_Signer(const Private_Key& key,
if(!op)
op = engine->get_signature_op(key);
- if(!verify_op)
+ if(!verify_op && prot == ENABLE_FAULT_PROTECTION)
verify_op = engine->get_verify_op(key);
- if(op && verify_op)
+ if(op && (verify_op || prot == DISABLE_FAULT_PROTECTION))
break;
}
- if(!op || !verify_op)
+ if(!op || (!verify_op && prot == ENABLE_FAULT_PROTECTION))
throw Lookup_Error("PK_Signer: No working engine for " +
key.algo_name());
@@ -202,7 +203,7 @@ SecureVector<byte> PK_Signer::signature(RandomNumberGenerator& rng)
SecureVector<byte> plain_sig = op->sign(encoded, encoded.size(), rng);
- if(!self_test_signature(encoded, plain_sig))
+ if(verify_op && !self_test_signature(encoded, plain_sig))
throw Internal_Error("PK_Signer consistency check failed");
if(op->message_parts() == 1 || sig_format == IEEE_1363)
diff --git a/src/pubkey/pubkey.h b/src/pubkey/pubkey.h
index c31aed67b..eeb4d5841 100644
--- a/src/pubkey/pubkey.h
+++ b/src/pubkey/pubkey.h
@@ -24,6 +24,14 @@ namespace Botan {
enum Signature_Format { IEEE_1363, DER_SEQUENCE };
/**
+* Enum marking if protection against fault attacks should be used
+*/
+enum Fault_Protection {
+ ENABLE_FAULT_PROTECTION,
+ DISABLE_FAULT_PROTECTION
+};
+
+/**
* Public Key Encryptor
*/
class BOTAN_DLL PK_Encryptor
@@ -174,10 +182,12 @@ class BOTAN_DLL PK_Signer
* @param emsa the EMSA to use
* An example would be "EMSA1(SHA-224)".
* @param format the signature format to use
+ * @param prot says if fault protection should be enabled
*/
PK_Signer(const Private_Key& key,
const std::string& emsa,
- Signature_Format format = IEEE_1363);
+ Signature_Format format = IEEE_1363,
+ Fault_Protection prot = ENABLE_FAULT_PROTECTION);
~PK_Signer() { delete op; delete verify_op; delete emsa; }
private:
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-21 06:52:36 +0000