# # # patch "ChangeLog" # from [8881f6ba679b68d2d935ae7e1292eb0e3d660aa1] # to [c92a8c2478fc886a4b70f03fbfc8d3931b775d36] # # patch "botan/asn1_dn.cpp" # from [c90dcbbb9b75257b4c1318de177368dffc807b1d] # to [2ac38d99270767117113538597ee7054451bf39f] # # patch "botan/base.cpp" # from [296db55bc172f248ad5effe0001475b37a04b64f] # to [6d341d612412367f4b66ec654f30b59dbd69c870] # # patch "botan/big_base.cpp" # from [9a81e6579e4d5fa4eae67951d421e2257f990648] # to [457b2869f411f8d9312b710e1546c491ecfc7a20] # # patch "botan/big_ops2.cpp" # from [a7129d4c1c8855a50906c6210a1e6b6d3c37d915] # to [bdb204364eb9957de831cda899ec3979ff971db8] # # patch "botan/big_ops3.cpp" # from [af27d7710afd7dae10689bf007ceb29713c1ca32] # to [3ed38b0c462fe0da79327dab4a4e1d96989cf65a] # # patch "botan/big_rand.cpp" # from [2409e28c2f9eccf2f08383be22454bd462bb3584] # to [4541fc4ea65f0a9fcc7b5741fa618a6302884fad] # # patch "botan/bigint.h" # from [613fc3aec6f498730a3431ba1394b5e46eba1106] # to [500263c7ed0583d73a3d4291ecac823f9ce28d3d] # # patch "botan/blinding.cpp" # from [4b2356d837f6957a9997bd35e2334a044e3ed5f6] # to [57d0d0adedcb70339c09939e9e88ef95f37357f9] # # patch "botan/blinding.h" # from [ac3050bb8acdb4d1fa77680e7c4602ef30778021] # to [296b45b8f600d94a9fc559c53ba894cd295e0eaa] # # patch "botan/botan.h" # from [76631677430121056a988cfa6e8c53112a813a5c] # to [0179c2c7a09623165c143900f9351b03842cef39] # # patch "botan/def_alg.cpp" # from [b3f2228ad990d77ed9f3c44715153b2993cb5cf5] # to [4159950766418fa2c83cde48483ab8e895ec95c6] # # patch "botan/def_mode.cpp" # from [a1267f1d3cc1c225d91dd630ff5231f6af48bae2] # to [868874d5c5cfe43b1d5be02163446f0fdde981f7] # # patch "botan/def_ops.cpp" # from [367e4d60c52f360117249e7b6c1d3804ca0db1f4] # to [de18acdf50872ad425a7a2b20c2da4745b9df983] # # patch "botan/def_powm.cpp" # from [973942544f22958b8db2cf0fd91eb6e588b732de] # to [c0632ec6e1c5499467760bb99c31765c0d6ee90b] # # patch "botan/def_powm.h" # from [b86729eec211b555859a04b3179593f5e958f63a] # to [c651a1990e9c5f92109014f725290c5698a0098b] # # patch "botan/der_enc.cpp" # from [e70973207fdf7ce3ad5a9c7c5c48f51a5de10ea1] # to [b7b2e39d5732ac958858aa4edd2e02c97a46a79e] # # patch "botan/divide.cpp" # from [b7ae7fc20fed92414c2adaa124c51d508785ba7f] # to [49536741943e641f26492391157a8e329ce67a1c] # # patch "botan/emsa1.cpp" # from [c1f50b7abac1a37e8bf7dfcb06e36beda025dc85] # to [1dd0e80f0dc5bfbd718e2edc2e6de80fa482b50c] # # patch "botan/engine.cpp" # from [af6d1fb7827625d968315b490b84756861c17f7c] # to [c3736b30d68bf5728e77645032802f8f2943965c] # # patch "botan/filter.h" # from [7b951b0e26db1861c7a779fdc8e5cf83dc743cbb] # to [ed08b34ed42c560fe30f6b89cd6b3369ea851c37] # # patch "botan/inifile.cpp" # from [7df6bc16b85ae545ef9ea941a185f7993d5b0321] # to [1929d5986440376b38c0f5910651b23061f3752c] # # patch "botan/init.h" # from [825be479b4ab221415be4b0fcd663df176337c5e] # to [5642c339e1e691cd07535eb81216f85ec9749521] # # patch "botan/kdf.cpp" # from [e6b66452265f1bfd7e865837bb283bcc1a16b78c] # to [875f93344551fe6e76ca4c86660937d2ec190c60] # # patch "botan/keypair.cpp" # from [91cccf8c1a165d8e0d4da18b36d38b1b0e06210d] # to [b989bff406ff022391d3484840d085d4060715de] # # patch "botan/libstate.cpp" # from [0c010d07846f8903044e1d56b158314c00a93bc8] # to [57652d70403e5025e38b263123515f880befe127] # # patch "botan/libstate.h" # from [7fb554cb2261eecafd96ba55ab777c2ac452ae24] # to [d341953a56d43101af13d0f91d4559f4d9733655] # # patch "botan/make_prm.cpp" # from [92eadd5a0197ce5cdd5a80b7ef146e1c4beb737c] # to [e9f4a2387ea8bd55d93d4c93ba73fc8ebf028212] # # patch "botan/mem_ops.h" # from [92bb05e9488560a8270d4a78b8fbb1ab78fc2eba] # to [34941d88cfa5ddaf14b9ff3826b0b621a0ab53e8] # # patch "botan/mem_pool.cpp" # from [008f77e32528d87b389a1de2122ed1deff9185df] # to [05fc27f4a05b71ab53b2f5f5fd0fb9bbe57f9909] # # patch "botan/mem_pool.h" # from [dbc05bb8b4dfc24bd07cfef84fd84d5541e8ff43] # to [93a52922bc80de93c9d55a3aa7186339ac94c269] # # patch "botan/mgf1.cpp" # from [29ebaaf6613d812554b3d553f52aae167eaf3ea4] # to [4bfd485e042f369b4fe63795d322a58a040d5610] # # patch "botan/mp_asm.cpp" # from [6bbc7da9aa14f2a3851944eb594a5c0500c637a3] # to [05eb2769a29c6c07d628340d508a13630fb7072e] # # patch "botan/mp_asm.h" # from [993bac9e1839b558d2679d07423b9c87797e8ec0] # to [c3fffadbd9d2c62f894a4112423da7a6f82fb77a] # # patch "botan/mp_asmi.h" # from [9a3768c28ba06cf6435a8131e52b5d01a73bcf3e] # to [f385ef7bad73f4d2cbc77a3bdb9c1dda9d8c8286] # # patch "botan/mp_core.h" # from [2247e0cd44d00ef46302f75bf74230b6bf4ba765] # to [db979ea2eeca9075d1775a7955afccc4502eda26] # # patch "botan/mp_misc.cpp" # from [da1628dfed644709a2b6e1ea22f0ee352e617b1b] # to [de05320fc3a8f2735f5dff92ee6e9b821fac4a4e] # # patch "botan/mp_mul.cpp" # from [76e5669ba8841469d4bd5647f467a20094fe5e15] # to [f2d1306395f75a0f325301d98a416a755abc4283] # # patch "botan/mp_numth.cpp" # from [ee21088447a4ea56f7703a8f48428619f20f2c9e] # to [115cec8f3c0c2bee00a8e7cc20da04eeee89a9c9] # # patch "botan/mp_sqr.cpp" # from [e80b8be2f66892e1d9c161a54956a42df08975d5] # to [d81181c581f15a26731a297aa31fd66cfd1a4a72] # # patch "botan/numthry.cpp" # from [dc52a7d8bd533fef023056d599d9791a0a932dab] # to [e769699e0e76d55ab3382be2032a97fce22f733f] # # patch "botan/numthry.h" # from [e7a209c8c3b650b8627798c12d01a57a009dfe89] # to [b52efe2ea7d807608717f2b5e5a8ea430e1907a1] # # patch "botan/out_buf.cpp" # from [2489a9bec82d69346621189012595616f879bf93] # to [84c593b7de4a4e21920b9a68146f9b061ae8384a] # # patch "botan/pem.cpp" # from [eef9e1120e7547f53786198636a799358f419260] # to [d18edca4aece3b15d7383d0fc8c98109cc50f484] # # patch "botan/pk_algs.cpp" # from [4eaf5dca76443211e7486ca651ae5521d7cb7181] # to [004d3768624059675382b2c999587af76e10c943] # # patch "botan/pk_core.cpp" # from [460ac1a0935469301fcb2e28f7b2561340cc4ef7] # to [bc6d8c019e76bff51ffef875a0f4f14e996949a6] # # patch "botan/pkcs5.cpp" # from [573e3e5f7867ba0e29237a8ce982dd990d7151e8] # to [a86a2c094f40ac695129fccd11be68e872206e8b] # # patch "botan/policy.cpp" # from [e6c56d910f2460a72d41603c4a32b99aa4a6c145] # to [813fe31d7f72e934ac221a5b08edec78dab19890] # # patch "botan/pow_mod.cpp" # from [622ad0b2f9cc40a01000c02e1e486e4bd40140b6] # to [9d95b94f7939eda78fceec8380fec8e394296656] # # patch "botan/powm_fw.cpp" # from [b1a47e40d185947a51ffcb41597568c748b5fdda] # to [b6598037d0f1f141294c33f3aa0f46caf921ccd4] # # patch "botan/powm_mnt.cpp" # from [a9e9d38aa4b3a66ef19d4974bb2e78625c77aa66] # to [81992708ed35a17cfd114f18604aa712d2609f6b] # # patch "botan/reducer.cpp" # from [c9bfcbf3595d7d6f59a1e04275a68eb89054b10e] # to [23b3888f2cf65aa90bea12dfa8d60e3027d649a9] # # patch "botan/reducer.h" # from [5958c1b425b899e44d943db154b4707818789d2b] # to [cf802c2483d8e46c6ac2b42268012f0d4dd33afa] # # patch "botan/secmem.h" # from [7e435e885f9a0f44a51989c8f70615d0f88aabb3] # to [19762c45fca26ca29ba735d42d5343ab3f4b0976] # # patch "botan/x509_ca.cpp" # from [aa8c7dcf99a2c1e9e8db19bcdf7a6fe9bf18eecb] # to [569c0382bfcb001cc5ca92e359c84686a165dbde] # # patch "botan/x509_obj.cpp" # from [cc7e829b3d3013e84ed72e06fdb17e9264f766a2] # to [497e4b4edbbfff5066d44b17971cb09e4ddf525d] # # patch "botan/x509cert.cpp" # from [c72dbb61b0aba0c216ae0affca5de53fb130d086] # to [68dc18245e93b289fee40af838929d72efe83840] # ============================================================ --- ChangeLog 8881f6ba679b68d2d935ae7e1292eb0e3d660aa1 +++ ChangeLog c92a8c2478fc886a4b70f03fbfc8d3931b775d36 @@ -1,3 +1,7 @@ +2006-01-30 Matt Johnston + + * botan/: import of Botan 1.5.4 + 2006-01-27 Matthew Gregan * monotone.texi: Clean up 'serve' syntax in a couple of places. ============================================================ --- botan/asn1_dn.cpp c90dcbbb9b75257b4c1318de177368dffc807b1d +++ botan/asn1_dn.cpp 2ac38d99270767117113538597ee7054451bf39f @@ -55,7 +55,7 @@ if(str == "") return; - typedef std::multimap::const_iterator rdn_iter; + typedef std::multimap::iterator rdn_iter; std::pair range = dn_info.equal_range(oid); for(rdn_iter j = range.first; j != range.second; ++j) @@ -219,7 +219,7 @@ ASN1_Tag string_type, const std::string& oid_str, bool must_exist = false) { - typedef std::multimap::const_iterator rdn_iter; + typedef std::multimap::iterator rdn_iter; const OID oid = OIDS::lookup(oid_str); const bool exists = (dn_info.find(oid) != dn_info.end()); ============================================================ --- botan/base.cpp 296db55bc172f248ad5effe0001475b37a04b64f +++ botan/base.cpp 6d341d612412367f4b66ec654f30b59dbd69c870 @@ -7,6 +7,7 @@ #include #include #include +#include namespace Botan { @@ -220,17 +221,25 @@ u32bit RandomNumberGenerator::add_entropy(EntropySource& source, bool slow_poll) { - SecureVector buffer(slow_poll ? 192 : 64); - u32bit bytes_gathered; + u32bit poll_for = 0; if(slow_poll) + poll_for = Config::get_u32bit("rng/slow_poll_request"); + else + poll_for = Config::get_u32bit("rng/fast_poll_request"); + + SecureVector buffer(poll_for ? poll_for : 256); + + u32bit bytes_gathered = 0; + + if(slow_poll) bytes_gathered = source.slow_poll(buffer, buffer.size()); else bytes_gathered = source.fast_poll(buffer, buffer.size()); add_entropy(buffer, bytes_gathered); - return entropy_estimate(buffer, buffer.size()); + return entropy_estimate(buffer, bytes_gathered); } /************************************************* ============================================================ --- botan/big_base.cpp 9a81e6579e4d5fa4eae67951d421e2257f990648 +++ botan/big_base.cpp 457b2869f411f8d9312b710e1546c491ecfc7a20 @@ -122,59 +122,6 @@ } /************************************************* -* Add n to this number * -*************************************************/ -void BigInt::add(word n) - { - if(!n) return; - word temp = reg[0]; - reg[0] += n; - if(reg[0] > temp) - return; - for(u32bit j = 1; j != size(); ++j) - if(++reg[j]) return; - grow_to(2*size()); - reg[size() / 2] = 1; - } - -/************************************************* -* Subtract n from this number * -*************************************************/ -void BigInt::sub(word n) - { - if(!n) return; - word temp = reg[0]; - reg[0] -= n; - if(reg[0] < temp) - return; - for(u32bit j = 1; j != size(); ++j) - if(reg[j]--) return; - reg.create(2); - flip_sign(); - reg[0] = n - temp; - } - -/************************************************* -* Prefix Increment Operator * -*************************************************/ -BigInt& BigInt::operator++() - { - if(is_negative()) sub(1); - else add(1); - return (*this); - } - -/************************************************* -* Prefix Decrement Operator * -*************************************************/ -BigInt& BigInt::operator--() - { - if(is_negative()) add(1); - else sub(1); - return (*this); - } - -/************************************************* * Return word n of this number * *************************************************/ word BigInt::word_at(u32bit n) const ============================================================ --- botan/big_ops2.cpp a7129d4c1c8855a50906c6210a1e6b6d3c37d915 +++ botan/big_ops2.cpp bdb204364eb9957de831cda899ec3979ff971db8 @@ -9,6 +9,8 @@ #include #include +#include + namespace Botan { /************************************************* @@ -127,15 +129,6 @@ if(mod == 0) throw BigInt::DivideByZero(); - if(power_of_2(mod)) - { - word result = (word_at(0) & (mod - 1)); - clear(); - reg.grow_to(2); - reg[0] = result; - return result; - } - word remainder = 0; u32bit size = sig_words(); @@ -143,7 +136,14 @@ remainder = bigint_modop(remainder, word_at(j-1), mod); clear(); reg.grow_to(2); - reg[0] = remainder; + + if(remainder && sign() == BigInt::Negative) + reg[0] = mod - remainder; + else + reg[0] = remainder; + + set_sign(BigInt::Positive); + return word_at(0); } ============================================================ --- botan/big_ops3.cpp af27d7710afd7dae10689bf007ceb29713c1ca32 +++ botan/big_ops3.cpp 3ed38b0c462fe0da79327dab4a4e1d96989cf65a @@ -131,14 +131,14 @@ if(mod == 0) throw BigInt::DivideByZero(); - if(power_of_2(mod)) - return (n.word_at(0) & (mod - 1)); - + const u32bit n_words = n.sig_words(); word remainder = 0; - u32bit size = n.sig_words(); - for(u32bit j = size; j > 0; --j) + for(u32bit j = n_words; j > 0; --j) remainder = bigint_modop(remainder, n.word_at(j-1), mod); + + if(remainder && n.sign() == BigInt::Negative) + return mod - remainder; return remainder; } ============================================================ --- botan/big_rand.cpp 2409e28c2f9eccf2f08383be22454bd462bb3584 +++ botan/big_rand.cpp 4541fc4ea65f0a9fcc7b5741fa618a6302884fad @@ -20,6 +20,8 @@ randomize(bits); else if(type == Power2) set_bit(bits); + else + throw Invalid_Argument("BigInt(NumberType): Unknown type"); } /************************************************* ============================================================ --- botan/bigint.h 613fc3aec6f498730a3431ba1394b5e46eba1106 +++ botan/bigint.h 500263c7ed0583d73a3d4291ecac823f9ce28d3d @@ -35,17 +35,14 @@ BigInt& operator<<=(u32bit); BigInt& operator>>=(u32bit); - BigInt& operator++(); - BigInt& operator--(); - BigInt operator++(int) { BigInt tmp = (*this); ++(*this); return tmp; } - BigInt operator--(int) { BigInt tmp = (*this); --(*this); return tmp; } + BigInt& operator++() { return (*this += 1); } + BigInt& operator--() { return (*this -= 1); } + BigInt operator++(int) { BigInt x = (*this); ++(*this); return x; } + BigInt operator--(int) { BigInt x = (*this); --(*this); return x; } BigInt operator-() const; bool operator !() const { return (!is_nonzero()); } - void add(word); - void sub(word); - s32bit cmp(const BigInt&, bool = true) const; bool is_even() const { return (get_bit(0) == 0); } bool is_odd() const { return (get_bit(0) == 1); } @@ -106,7 +103,7 @@ BigInt(Sign, u32bit); BigInt(NumberType, u32bit); private: - friend void modifying_divide(BigInt&, BigInt&, BigInt&); + friend void divide(const BigInt&, const BigInt&, BigInt&, BigInt&); void grow_to(u32bit n) const { reg.grow_to(n); } SecureVector reg; Sign signedness; ============================================================ --- botan/blinding.cpp 4b2356d837f6957a9997bd35e2334a044e3ed5f6 +++ botan/blinding.cpp 57d0d0adedcb70339c09939e9e88ef95f37357f9 @@ -1,10 +1,9 @@ /************************************************* * Blinder Source File * * (C) 1999-2006 The Botan Project * *************************************************/ #include -#include #include namespace Botan { @@ -12,65 +11,27 @@ /************************************************* * Blinder Constructor * *************************************************/ -Blinder::Blinder() +Blinder::Blinder(const BigInt& e, const BigInt& d, const BigInt& n) { - reducer = 0; - } + if(e < 1 || d < 1 || n < 1) + throw Invalid_Argument("Blinder: Arguments too small"); -/************************************************* -* Blinder Copy Constructor * -*************************************************/ -Blinder::Blinder(const Blinder& blinder) - { - reducer = 0; - initialize(blinder.e, blinder.d, blinder.n); + reducer = Modular_Reducer(n); + this->e = e; + this->d = d; } /************************************************* -* Blinder Assignment Operator * -*************************************************/ -Blinder& Blinder::operator=(const Blinder& blinder) - { - delete reducer; - reducer = 0; - - if(blinder.reducer) - initialize(blinder.e, blinder.d, blinder.n); - return (*this); - } - -/************************************************* -* Initialize a Blinder object * -*************************************************/ -void Blinder::initialize(const BigInt& e1, const BigInt& d1, const BigInt& n1) - { - if(e1 < 1 || d1 < 1 || n1 < 1) - throw Invalid_Argument("Blinder::initialize: Arguments too small"); - - e = e1; - d = d1; - n = n1; - delete reducer; - reducer = get_reducer(n); - } - -/************************************************* -* Blinder Destructor * -*************************************************/ -Blinder::~Blinder() - { - delete reducer; - } - -/************************************************* * Blind a number * *************************************************/ BigInt Blinder::blind(const BigInt& i) const { - if(!reducer) return i; - e = reducer->square(e); - d = reducer->square(d); - return reducer->multiply(i, e); + if(!reducer.initialized()) + return i; + + e = reducer.square(e); + d = reducer.square(d); + return reducer.multiply(i, e); } /************************************************* @@ -78,8 +39,9 @@ *************************************************/ BigInt Blinder::unblind(const BigInt& i) const { - if(!reducer) return i; - return reducer->multiply(i, d); + if(!reducer.initialized()) + return i; + return reducer.multiply(i, d); } } ============================================================ --- botan/blinding.h ac3050bb8acdb4d1fa77680e7c4602ef30778021 +++ botan/blinding.h 296b45b8f600d94a9fc559c53ba894cd295e0eaa @@ -7,6 +7,7 @@ #define BOTAN_BLINDER_H__ #include +#include namespace Botan { @@ -19,16 +20,11 @@ BigInt blind(const BigInt&) const; BigInt unblind(const BigInt&) const; - void initialize(const BigInt&, const BigInt&, const BigInt&); - Blinder& operator=(const Blinder&); - - Blinder(); - Blinder(const Blinder&); - ~Blinder(); + Blinder() {} + Blinder(const BigInt&, const BigInt&, const BigInt&); private: + Modular_Reducer reducer; mutable BigInt e, d; - BigInt n; - class ModularReducer* reducer; }; } ============================================================ --- botan/botan.h 76631677430121056a988cfa6e8c53112a813a5c +++ botan/botan.h 0179c2c7a09623165c143900f9351b03842cef39 @@ -11,4 +11,3 @@ #include #include #include - ============================================================ --- botan/def_alg.cpp b3f2228ad990d77ed9f3c44715153b2993cb5cf5 +++ botan/def_alg.cpp 4159950766418fa2c83cde48483ab8e895ec95c6 @@ -1,24 +1,63 @@ /************************************************* * Default Engine Algorithms Source File * * (C) 1999-2006 The Botan Project * *************************************************/ -#include +#include #include #include #include +#include +#include +#include #include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include #include +#include +#include +#include +#include #include +#include +#include +#include +#include +#include +#include +#include #include #include +#include +#include +#include +#include +#include #include +#include #include +#include #include namespace Botan { @@ -79,10 +118,36 @@ HANDLE_TYPE_NO_ARGS("AES-128", AES_128); HANDLE_TYPE_NO_ARGS("AES-192", AES_192); HANDLE_TYPE_NO_ARGS("AES-256", AES_256); + HANDLE_TYPE_NO_ARGS("Blowfish", Blowfish); + HANDLE_TYPE_NO_ARGS("CAST-128", CAST_128); + HANDLE_TYPE_NO_ARGS("CAST-256", CAST_256); HANDLE_TYPE_NO_ARGS("DES", DES); HANDLE_TYPE_NO_ARGS("DESX", DESX); HANDLE_TYPE_NO_ARGS("TripleDES", TripleDES); + HANDLE_TYPE_NO_ARGS("GOST", GOST); + HANDLE_TYPE_NO_ARGS("IDEA", IDEA); + HANDLE_TYPE_NO_ARGS("KASUMI", KASUMI); + HANDLE_TYPE_ONE_STRING("Luby-Rackoff", LubyRackoff); + HANDLE_TYPE_NO_ARGS("MARS", MARS); + HANDLE_TYPE_ONE_U32BIT("MISTY1", MISTY1, 8); + HANDLE_TYPE_NO_ARGS("RC2", RC2); + HANDLE_TYPE_ONE_U32BIT("RC5", RC5, 12); + HANDLE_TYPE_NO_ARGS("RC6", RC6); + HANDLE_TYPE_ONE_U32BIT("SAFER-SK", SAFER_SK, 10); + HANDLE_TYPE_NO_ARGS("SEED", SEED); + HANDLE_TYPE_NO_ARGS("Serpent", Serpent); + HANDLE_TYPE_NO_ARGS("Skipjack", Skipjack); + HANDLE_TYPE_NO_ARGS("Square", Square); + HANDLE_TYPE_NO_ARGS("TEA", TEA); + HANDLE_TYPE_NO_ARGS("Twofish", Twofish); + HANDLE_TYPE_NO_ARGS("XTEA", XTEA); + if(algo_name == "Lion") + { + if(name.size() != 4) + throw Invalid_Algorithm_Name(algo_spec); + return new Lion(name[1], name[2], to_u32bit(name[3])); + } return 0; } @@ -99,6 +164,8 @@ HANDLE_TYPE_ONE_U32BIT("ARC4", ARC4, 0); HANDLE_TYPE_ONE_U32BIT("RC4_drop", ARC4, 768); + HANDLE_TYPE_NO_ARGS("Turing", Turing); + HANDLE_TYPE_NO_ARGS("WiderWake4+1-BE", WiderWake_41_BE); return 0; } @@ -114,9 +181,30 @@ return 0; const std::string algo_name = deref_alias(name[0]); + HANDLE_TYPE_NO_ARGS("Adler32", Adler32); + HANDLE_TYPE_NO_ARGS("CRC24", CRC24); HANDLE_TYPE_NO_ARGS("CRC32", CRC32); + HANDLE_TYPE_NO_ARGS("FORK-256", FORK_256); + HANDLE_TYPE_NO_ARGS("HAS-160", HAS_160); + HANDLE_TYPE_NO_ARGS("MD2", MD2); + HANDLE_TYPE_NO_ARGS("MD4", MD4); + HANDLE_TYPE_NO_ARGS("MD5", MD5); + HANDLE_TYPE_NO_ARGS("RIPEMD-128", RIPEMD_128); + HANDLE_TYPE_NO_ARGS("RIPEMD-160", RIPEMD_160); HANDLE_TYPE_NO_ARGS("SHA-160", SHA_160); HANDLE_TYPE_NO_ARGS("SHA-256", SHA_256); + HANDLE_TYPE_NO_ARGS("SHA-384", SHA_384); + HANDLE_TYPE_NO_ARGS("SHA-512", SHA_512); + HANDLE_TYPE_TWO_U32BIT("Tiger", Tiger, 24); + HANDLE_TYPE_NO_ARGS("Whirlpool", Whirlpool); + + if(algo_name == "Parallel") + { + if(name.size() < 2) + throw Invalid_Algorithm_Name(algo_spec); + name.erase(name.begin()); + return new Parallel(name); + } return 0; } @@ -131,7 +219,9 @@ return 0; const std::string algo_name = deref_alias(name[0]); + HANDLE_TYPE_ONE_STRING("CMAC", CMAC); HANDLE_TYPE_ONE_STRING("HMAC", HMAC); + HANDLE_TYPE_NO_ARGS("X9.19-MAC", ANSI_X919_MAC); return 0; } @@ -149,6 +239,7 @@ HANDLE_TYPE_ONE_STRING("PBKDF1", PKCS5_PBKDF1); HANDLE_TYPE_ONE_STRING("PBKDF2", PKCS5_PBKDF2); + HANDLE_TYPE_ONE_STRING("OpenPGP-S2K", OpenPGP_S2K); return 0; } ============================================================ --- botan/def_mode.cpp a1267f1d3cc1c225d91dd630ff5231f6af48bae2 +++ botan/def_mode.cpp 868874d5c5cfe43b1d5be02163446f0fdde981f7 @@ -1,9 +1,9 @@ /************************************************* * Default Engine Source File * * (C) 1999-2006 The Botan Project * *************************************************/ -#include +#include #include #include #include @@ -20,47 +20,10 @@ namespace { /************************************************* -* Simply return a mode object of choice * -*************************************************/ -Keyed_Filter* get_mode(Cipher_Dir direction, const std::string& cipher, - const std::string& mode, const std::string& pad = "", - u32bit bits = 0) - { - if(mode == "ECB") - { - if(direction == ENCRYPTION) return new ECB_Encryption(cipher, pad); - else return new ECB_Decryption(cipher, pad); - } - else if(mode == "CFB") - { - if(direction == ENCRYPTION) return new CFB_Encryption(cipher, bits); - else return new CFB_Decryption(cipher, bits); - } - else if(mode == "CBC") - { - if(pad == "CTS") - { - if(direction == ENCRYPTION) return new CTS_Encryption(cipher); - else return new CTS_Decryption(cipher); - } - if(direction == ENCRYPTION) return new CBC_Encryption(cipher, pad); - else return new CBC_Decryption(cipher, pad); - } - else if(mode == "EAX") - { - if(direction == ENCRYPTION) return new EAX_Encryption(cipher, bits); - else return new EAX_Decryption(cipher, bits); - } - else - throw Internal_Error("get_mode: " + cipher + "/" + mode + "/" + pad); - } - -} -/************************************************* * Get a cipher object * *************************************************/ -Keyed_Filter* Default_Engine::get_cipher(const std::string& algo_spec, - Cipher_Dir direction) +Keyed_Filter* do_get_cipher(const std::string& algo_spec, + Cipher_Dir direction) { std::vector algo_parts = split_on(algo_spec, '/'); if(algo_parts.size() == 0) @@ -110,7 +73,46 @@ else if(mode == "CTR-BE") return new CTR_BE(cipher); else if(mode == "ECB" || mode == "CBC" || mode == "CTS" || mode == "CFB" || mode == "EAX") - return get_mode(direction, cipher, mode, padding, bits); + { + if(mode == "ECB") + { + if(direction == ENCRYPTION) + return new ECB_Encryption(cipher, padding); + else + return new ECB_Decryption(cipher, padding); + } + else if(mode == "CFB") + { + if(direction == ENCRYPTION) + return new CFB_Encryption(cipher, bits); + else + return new CFB_Decryption(cipher, bits); + } + else if(mode == "CBC") + { + if(padding == "CTS") + { + if(direction == ENCRYPTION) + return new CTS_Encryption(cipher); + else + return new CTS_Decryption(cipher); + } + if(direction == ENCRYPTION) + return new CBC_Encryption(cipher, padding); + else + return new CBC_Decryption(cipher, padding); + } + else if(mode == "EAX") + { + if(direction == ENCRYPTION) + return new EAX_Encryption(cipher, bits); + else + return new EAX_Decryption(cipher, bits); + } + else + throw Internal_Error("get_mode: " + cipher + "/" + + mode + "/" + padding); + } else return 0; } @@ -119,3 +121,14 @@ } } + +/************************************************* +* Get a cipher object * +*************************************************/ +Keyed_Filter* Default_Engine::get_cipher(const std::string& algo_spec, + Cipher_Dir direction) + { + return do_get_cipher(algo_spec, direction); + } + +} ============================================================ --- botan/def_ops.cpp 367e4d60c52f360117249e7b6c1d3804ca0db1f4 +++ botan/def_ops.cpp de18acdf50872ad425a7a2b20c2da4745b9df983 @@ -1,9 +1,9 @@ /************************************************* * Default Engine PK Operations Source File * * (C) 1999-2006 The Botan Project * *************************************************/ -#include +#include #include #include #include @@ -22,34 +22,34 @@ { return powermod_e_n(i); } BigInt private_op(const BigInt&) const; - IF_Operation* clone() const; + IF_Operation* clone() const { return new Default_IF_Op(*this); } Default_IF_Op(const BigInt&, const BigInt&, const BigInt&, const BigInt&, const BigInt&, const BigInt&, const BigInt&, const BigInt&); - ~Default_IF_Op() { delete reduce_by_p; } private: - const BigInt p, q, c; Fixed_Exponent_Power_Mod powermod_e_n, powermod_d1_p, powermod_d2_q; - ModularReducer* reduce_by_p; + Modular_Reducer reducer; + BigInt c, q; }; /************************************************* * Default_IF_Op Constructor * *************************************************/ Default_IF_Op::Default_IF_Op(const BigInt& e, const BigInt& n, const BigInt&, - const BigInt& px, const BigInt& qx, + const BigInt& p, const BigInt& q, const BigInt& d1, const BigInt& d2, - const BigInt& cx) : p(px), q(qx), c(cx) + const BigInt& c) { powermod_e_n = Fixed_Exponent_Power_Mod(e, n); - reduce_by_p = 0; if(d1 != 0 && d2 != 0 && p != 0 && q != 0) { powermod_d1_p = Fixed_Exponent_Power_Mod(d1, p); powermod_d2_q = Fixed_Exponent_Power_Mod(d2, q); - reduce_by_p = get_reducer(p); + reducer = Modular_Reducer(p); + this->c = c; + this->q = q; } } @@ -63,26 +63,11 @@ BigInt j1 = powermod_d1_p(i); BigInt j2 = powermod_d2_q(i); - j1 = reduce_by_p->reduce(sub_mul(j1, j2, c)); + j1 = reducer.reduce(sub_mul(j1, j2, c)); return mul_add(j1, q, j2); } /************************************************* -* Make a copy of this Default_IF_Op * -*************************************************/ -IF_Operation* Default_IF_Op::clone() const - { - Default_IF_Op* copy = new Default_IF_Op(*this); - copy->reduce_by_p = 0; - - if(p != 0) - copy->reduce_by_p = get_reducer(p); - - return copy; - } - - -/************************************************* * Default DSA Operation * *************************************************/ class Default_DSA_Op : public DSA_Operation @@ -98,6 +83,7 @@ const BigInt x, y; const DL_Group group; Fixed_Base_Power_Mod powermod_g_p, powermod_y_p; + Modular_Reducer reduce_p, reduce_q; }; /************************************************* @@ -108,6 +94,8 @@ { powermod_g_p = Fixed_Base_Power_Mod(group.get_g(), group.get_p()); powermod_y_p = Fixed_Base_Power_Mod(y, group.get_p()); + reduce_p = Modular_Reducer(group.get_p()); + reduce_q = Modular_Reducer(group.get_q()); } /************************************************* @@ -117,7 +105,6 @@ const byte sig[], u32bit sig_len) const { const BigInt& q = group.get_q(); - const BigInt& p = group.get_p(); if(sig_len != 2*q.bytes() || msg_len > q.bytes()) return false; @@ -130,10 +117,10 @@ return false; s = inverse_mod(s, q); - s = mul_mod(powermod_g_p(mul_mod(s, i, q)), - powermod_y_p(mul_mod(s, r, q)), p); + s = reduce_p.multiply(powermod_g_p(reduce_q.multiply(s, i)), + powermod_y_p(reduce_q.multiply(s, r))); - return (s % q == r); + return (reduce_q.reduce(s) == r); } /************************************************* @@ -148,8 +135,9 @@ const BigInt& q = group.get_q(); BigInt i(in, length); - BigInt r = powermod_g_p(k) % q; - BigInt s = mul_mod(inverse_mod(k, q), mul_add(x, r, i), q); + BigInt r = reduce_q.reduce(powermod_g_p(k)); + BigInt s = reduce_q.multiply(inverse_mod(k, q), mul_add(x, r, i)); + if(r.is_zero() || s.is_zero()) throw Internal_Error("Default_DSA_Op::sign: r or s was zero"); @@ -175,6 +163,7 @@ const BigInt x, y; const DL_Group group; Fixed_Base_Power_Mod powermod_g_p, powermod_y_p; + Modular_Reducer reducer_p, reducer_q; }; /************************************************* @@ -185,6 +174,8 @@ { powermod_g_p = Fixed_Base_Power_Mod(group.get_g(), group.get_p()); powermod_y_p = Fixed_Base_Power_Mod(y, group.get_p()); + reducer_p = Modular_Reducer(group.get_p()); + reducer_q = Modular_Reducer(group.get_q()); } /************************************************* @@ -192,7 +183,6 @@ *************************************************/ SecureVector Default_NR_Op::verify(const byte in[], u32bit length) const { - const BigInt& p = group.get_p(); const BigInt& q = group.get_q(); if(length != 2*q.bytes()) @@ -204,8 +194,8 @@ if(c.is_zero() || c >= q || d >= q) throw Invalid_Argument("Default_NR_Op::verify: Invalid signature"); - BigInt i = mul_mod(powermod_g_p(d), powermod_y_p(c), p); - return BigInt::encode((c - i) % q); + BigInt i = reducer_p.multiply(powermod_g_p(d), powermod_y_p(c)); + return BigInt::encode(reducer_q.reduce(c - i)); } /************************************************* @@ -224,10 +214,10 @@ if(f >= q) throw Invalid_Argument("Default_NR_Op::sign: Input is out of range"); - BigInt c = (powermod_g_p(k) + f) % q; + BigInt c = reducer_q.reduce(powermod_g_p(k) + f); if(c.is_zero()) throw Internal_Error("Default_NR_Op::sign: c was zero"); - BigInt d = (k - x * c) % q; + BigInt d = reducer_q.reduce(k - x * c); SecureVector output(2*q.bytes()); c.binary_encode(output + (output.size() / 2 - c.bytes())); @@ -251,6 +241,7 @@ const BigInt p; Fixed_Base_Power_Mod powermod_g_p, powermod_y_p; Fixed_Exponent_Power_Mod powermod_x_p; + Modular_Reducer reducer_p; }; /************************************************* @@ -261,6 +252,7 @@ { powermod_g_p = Fixed_Base_Power_Mod(group.get_g(), p); powermod_y_p = Fixed_Base_Power_Mod(y, p); + reducer_p = Modular_Reducer(p); if(x != 0) powermod_x_p = Fixed_Exponent_Power_Mod(x, p); @@ -277,7 +269,7 @@ throw Invalid_Argument("Default_ELG_Op::encrypt: Input is too large"); BigInt a = powermod_g_p(k); - BigInt b = mul_mod(m, powermod_y_p(k), p); + BigInt b = reducer_p.multiply(m, powermod_y_p(k)); SecureVector output(2*p.bytes()); a.binary_encode(output + (p.bytes() - a.bytes())); @@ -293,7 +285,7 @@ if(a >= p || b >= p) throw Invalid_Argument("Default_ELG_Op: Invalid message"); - return mul_mod(b, inverse_mod(powermod_x_p(a), p), p); + return reducer_p.multiply(b, inverse_mod(powermod_x_p(a), p)); } /************************************************* ============================================================ --- botan/def_powm.cpp 973942544f22958b8db2cf0fd91eb6e588b732de +++ botan/def_powm.cpp c0632ec6e1c5499467760bb99c31765c0d6ee90b @@ -1,10 +1,10 @@ /************************************************* * Modular Exponentiation Source File * * (C) 1999-2006 The Botan Project * *************************************************/ +#include #include -#include namespace Botan { ============================================================ --- botan/def_powm.h b86729eec211b555859a04b3179593f5e958f63a +++ botan/def_powm.h c651a1990e9c5f92109014f725290c5698a0098b @@ -1,9 +1,13 @@ /************************************************* * Modular Exponentiation Header File * * (C) 1999-2006 The Botan Project * *************************************************/ +#ifndef BOTAN_DEFAULT_MODEXP_H__ +#define BOTAN_DEFAULT_MODEXP_H__ + #include +#include #include namespace Botan { @@ -18,12 +22,12 @@ void set_base(const BigInt&); BigInt execute() const; - Modular_Exponentiator* copy() const; + Modular_Exponentiator* copy() const + { return new Fixed_Window_Exponentiator(*this); } Fixed_Window_Exponentiator(const BigInt&, Power_Mod::Usage_Hints); - ~Fixed_Window_Exponentiator(); private: - class ModularReducer* reducer; + Modular_Reducer reducer; BigInt exp; u32bit window_bits; std::vector g; @@ -40,17 +44,19 @@ void set_base(const BigInt&); BigInt execute() const; - Modular_Exponentiator* copy() const; + Modular_Exponentiator* copy() const + { return new Montgomery_Exponentiator(*this); } Montgomery_Exponentiator(const BigInt&, Power_Mod::Usage_Hints); private: - BigInt reduce(const BigInt&) const; - BigInt exp, modulus; BigInt R2, R_mod; std::vector g; word mod_prime; - u32bit exp_bits, window_bits; + u32bit mod_words, exp_bits, window_bits; Power_Mod::Usage_Hints hints; }; + } + +#endif ============================================================ --- botan/der_enc.cpp e70973207fdf7ce3ad5a9c7c5c48f51a5de10ea1 +++ botan/der_enc.cpp b7b2e39d5732ac958858aa4edd2e02c97a46a79e @@ -7,6 +7,7 @@ #include #include #include +#include namespace Botan { ============================================================ --- botan/divide.cpp b7ae7fc20fed92414c2adaa124c51d508785ba7f +++ botan/divide.cpp 49536741943e641f26492391157a8e329ce67a1c @@ -8,74 +8,64 @@ namespace Botan { +namespace { + /************************************************* -* Solve x = q * y + r * +* Handle signed operands, if necessary * *************************************************/ -void divide(const BigInt& x, const BigInt& y_arg, BigInt& q, BigInt& r) +void sign_fixup(const BigInt& x, const BigInt& y, BigInt& q, BigInt& r) { - BigInt y = y_arg; - r = x; - - r.set_sign(BigInt::Positive); - y.set_sign(BigInt::Positive); - - modifying_divide(r, y, q); - if(x.sign() == BigInt::Negative) { q.flip_sign(); - if(r.is_nonzero()) { --q; r = y_arg.abs() - r; } + if(r.is_nonzero()) { --q; r = y.abs() - r; } } - if(y_arg.sign() == BigInt::Negative) + if(y.sign() == BigInt::Negative) q.flip_sign(); } +} + /************************************************* * Solve x = q * y + r * *************************************************/ -void positive_divide(const BigInt& x, const BigInt& y_arg, - BigInt& q, BigInt& r) +void divide(const BigInt& x, const BigInt& y_arg, BigInt& q, BigInt& r) { + if(y_arg.is_zero()) + throw BigInt::DivideByZero(); + BigInt y = y_arg; r = x; - modifying_divide(r, y, q); - } -/************************************************* -* Solve x = q * y + r * -*************************************************/ -void modifying_divide(BigInt& x, BigInt& y, BigInt& q) - { - if(y.is_zero()) - throw BigInt::DivideByZero(); - if(x.is_negative() || y.is_negative()) - throw Invalid_Argument("Arguments to modifying_divide must be positive"); + r.set_sign(BigInt::Positive); + y.set_sign(BigInt::Positive); - s32bit compare = x.cmp(y); - if(compare == -1) { q = 0; return; } - if(compare == 0) { q = 1; x = 0; return; } + s32bit compare = r.cmp(y); + if(compare == -1) { q = 0; sign_fixup(x, y_arg, q, r); return; } + if(compare == 0) { q = 1; r = 0; sign_fixup(x, y_arg, q, r); return; } u32bit shifts = 0; while(y[y.sig_words()-1] < MP_WORD_TOP_BIT) - { x <<= 1; y <<= 1; ++shifts; } + { r <<= 1; y <<= 1; ++shifts; } - u32bit n = x.sig_words() - 1, t = y.sig_words() - 1; - q.reg.create(n - t + 1); + u32bit n = r.sig_words() - 1, t = y.sig_words() - 1; + q.get_reg().create(n - t + 1); if(n <= t) { - while(x > y) { x -= y; q.add(1); } - x >>= shifts; + while(r > y) { r -= y; q++; } + r >>= shifts; + sign_fixup(x, y_arg, q, r); return; } BigInt temp = y << (MP_WORD_BITS * (n-t)); - while(x >= temp) { x -= temp; ++q[n-t]; } + while(r >= temp) { r -= temp; ++q[n-t]; } for(u32bit j = n; j != t; --j) { - const word x_j0 = x.word_at(j); - const word x_j1 = x.word_at(j-1); + const word x_j0 = r.word_at(j); + const word x_j1 = r.word_at(j-1); const word y_t = y.word_at(t); if(x_j0 == y_t) @@ -84,17 +74,19 @@ q[j-t-1] = bigint_divop(x_j0, x_j1, y_t); while(bigint_divcore(q[j-t-1], y_t, y.word_at(t-1), - x_j0, x_j1, x.word_at(j-2))) + x_j0, x_j1, r.word_at(j-2))) --q[j-t-1]; - x -= (q[j-t-1] * y) << (MP_WORD_BITS * (j-t-1)); - if(x.is_negative()) + r -= (q[j-t-1] * y) << (MP_WORD_BITS * (j-t-1)); + if(r.is_negative()) { - x += y << (MP_WORD_BITS * (j-t-1)); + r += y << (MP_WORD_BITS * (j-t-1)); --q[j-t-1]; } } - x >>= shifts; + r >>= shifts; + + sign_fixup(x, y_arg, q, r); } } ============================================================ --- botan/emsa1.cpp c1f50b7abac1a37e8bf7dfcb06e36beda025dc85 +++ botan/emsa1.cpp 1dd0e80f0dc5bfbd718e2edc2e6de80fa482b50c @@ -71,7 +71,7 @@ u32bit offset = 0; while(our_coding[offset] == 0 && offset < our_coding.size()) - offset++; + ++offset; if(our_coding.size() - offset != coded.size()) return false; ============================================================ --- botan/engine.cpp af6d1fb7827625d968315b490b84756861c17f7c +++ botan/engine.cpp c3736b30d68bf5728e77645032802f8f2943965c @@ -5,7 +5,7 @@ #include #include -#include +#include namespace Botan { ============================================================ --- botan/filter.h 7b951b0e26db1861c7a779fdc8e5cf83dc743cbb +++ botan/filter.h ed08b34ed42c560fe30f6b89cd6b3369ea851c37 @@ -58,7 +58,7 @@ class Fanout_Filter : public Filter { protected: - void incr_owns() { filter_owns++; } + void incr_owns() { ++filter_owns; } void set_port(u32bit n) { Filter::set_port(n); } void set_next(Filter* f[], u32bit n) { Filter::set_next(f, n); } ============================================================ --- botan/inifile.cpp 7df6bc16b85ae545ef9ea941a185f7993d5b0321 +++ botan/inifile.cpp 1929d5986440376b38c0f5910651b23061f3752c @@ -98,7 +98,7 @@ while(std::getline(config, line)) { - line_no++; + ++line_no; line = strip_whitespace(line); ============================================================ --- botan/init.h 825be479b4ab221415be4b0fcd663df176337c5e +++ botan/init.h 5642c339e1e691cd07535eb81216f85ec9749521 @@ -6,8 +6,6 @@ #ifndef BOTAN_INIT_H__ #define BOTAN_INIT_H__ -#include -#include #include namespace Botan { ============================================================ --- botan/kdf.cpp e6b66452265f1bfd7e865837bb283bcc1a16b78c +++ botan/kdf.cpp 875f93344551fe6e76ca4c86660937d2ec190c60 @@ -57,7 +57,7 @@ output.append(hash_result, added); out_len -= added; - counter++; + ++counter; } return output; ============================================================ --- botan/keypair.cpp 91cccf8c1a165d8e0d4da18b36d38b1b0e06210d +++ botan/keypair.cpp b989bff406ff022391d3484840d085d4060715de @@ -48,7 +48,7 @@ if(!ver->verify_message(message, signature)) throw Self_Test_Failure("Signature key pair consistency failure"); - message[0]++; + ++message[0]; if(ver->verify_message(message, signature)) throw Self_Test_Failure("Signature key pair consistency failure"); } ============================================================ --- botan/libstate.cpp 0c010d07846f8903044e1d56b158314c00a93bc8 +++ botan/libstate.cpp 57652d70403e5025e38b263123515f880befe127 @@ -11,6 +11,24 @@ namespace Botan { +/************************************************* +* Botan's global state * +*************************************************/ +Library_State* global_lib_state = 0; + +Library_State& global_state() + { + if(!global_lib_state) + throw Invalid_State("Library was not intialized correctly"); + return (*global_lib_state); + } + +void set_global_state(Library_State* new_state) + { + delete global_lib_state; + global_lib_state = new_state; + } + namespace { /************************************************* ============================================================ --- botan/libstate.h 7fb554cb2261eecafd96ba55ab777c2ac452ae24 +++ botan/libstate.h d341953a56d43101af13d0f91d4559f4d9733655 @@ -78,6 +78,7 @@ * Global State * *************************************************/ Library_State& global_state(); +void set_global_state(Library_State*); } ============================================================ --- botan/make_prm.cpp 92eadd5a0197ce5cdd5a80b7ef146e1c4beb737c +++ botan/make_prm.cpp e9f4a2387ea8bd55d93d4c93ba73fc8ebf028212 @@ -151,7 +151,7 @@ UI::pulse(UI::PRIME_SEARCHING); bool passes_sieve = true; - counter++; + ++counter; p += modulo; for(u32bit j = 0; j != sieve.size(); ++j) ============================================================ --- botan/mem_ops.h 92bb05e9488560a8270d4a78b8fbb1ab78fc2eba +++ botan/mem_ops.h 34941d88cfa5ddaf14b9ff3826b0b621a0ab53e8 @@ -15,7 +15,7 @@ * Memory Manipulation Functions * *************************************************/ template inline void copy_mem(T* out, const T* in, u32bit n) - { if(n) std::memmove(out, in, sizeof(T)*n); } + { std::memmove(out, in, sizeof(T)*n); } template inline void clear_mem(T* ptr, u32bit n) { std::memset(ptr, 0, sizeof(T)*n); } @@ -24,7 +24,7 @@ { std::memset(ptr, val, sizeof(T)*n); } template inline bool same_mem(const T* p1, const T* p2, u32bit n) - { return (cmp_mem(p1, p2, n) == 0); } + { return (std::memcmp(p1, p2, sizeof(T)*n) == 0); } } ============================================================ --- botan/mem_pool.cpp 008f77e32528d87b389a1de2122ed1deff9185df +++ botan/mem_pool.cpp 05fc27f4a05b71ab53b2f5f5fd0fb9bbe57f9909 @@ -8,7 +8,10 @@ #include #include #include +#include +#include // testing + namespace Botan { namespace { @@ -28,24 +31,6 @@ return 16*1024; } -/************************************************* -* Return a metric of how 'empty' this bitmap is * -*************************************************/ -u32bit emptiness_metric(u64bit bitmap) - { - u32bit metric = 0; - -#if 0 - for(u32bit j = 0; j != 8; ++j) - if(get_byte(j, bitmap) == 0) - metric++; -#else - - -#endif - return metric; - } - } /************************************************* @@ -56,7 +41,6 @@ { buffer = static_cast(buf); bitmap = 0; - how_empty = emptiness_metric(bitmap); this->block_size = block_size; clear_mem(buffer, block_size * 64); @@ -66,60 +50,71 @@ } /************************************************* +* Compare a Memory_Block with a void pointer * +*************************************************/ +bool Pooling_Allocator::Memory_Block::operator<(const void* other) const + { + if(buffer <= other && other < (buffer + 64 * block_size)) + return false; + return (buffer < other); + } + +/************************************************* +* Compare two Memory_Block objects * +*************************************************/ +bool Pooling_Allocator::Memory_Block::operator<(const Memory_Block& blk) const + { + return (buffer < blk.buffer); + } + +/************************************************* * See if ptr is contained by this block * *************************************************/ bool Pooling_Allocator::Memory_Block::contains(void* ptr, u32bit length) const throw() { return (buffer <= ptr && - ((byte*)ptr+length*block_size) <= (buffer + 64 * block_size)); + ((byte*)ptr + length * block_size) <= (buffer + 64 * block_size)); } /************************************************* -* Find a spot for a new allocation * +* Allocate some memory, if possible * *************************************************/ -bool Pooling_Allocator::Memory_Block::can_alloc(u32bit& start, - u32bit n) const throw() +byte* Pooling_Allocator::Memory_Block::alloc(u32bit n) throw() { - start = 0; + if(n == 0 || n > 64) + return 0; - if(n == 0 || n > 64 || (n == 64 && bitmap)) - return false; - if(n == 64) - return true; - - const u64bit mask = ((u64bit)1 << n) - 1; - - for(u32bit j = 0; j != 64 - n; ++j) { - if((bitmap >> j) & mask) - continue; - - start = j; - return true; + if(bitmap) + return 0; + else + { + bitmap = ~bitmap; + return buffer; + } } - return false; - } + u64bit mask = ((u64bit)1 << n) - 1; + u32bit offset = 0; -/************************************************* -* Allocate some memory, if possible * -*************************************************/ -byte* Pooling_Allocator::Memory_Block::alloc(u32bit start, - u32bit n) throw() - { - if(start == 0 && n == 64) + while(bitmap & mask) { - bitmap = ~bitmap; - return buffer; + mask <<= 1; + ++offset; + + if((bitmap & mask) == 0) + break; + if(mask >> 63) + break; } - u64bit mask = (((u64bit)1 << n) - 1) << start; + if(bitmap & mask) + return 0; bitmap |= mask; - how_empty = emptiness_metric(bitmap); - return buffer + start * block_size; + return buffer + offset * block_size; } /************************************************* @@ -129,17 +124,15 @@ { clear_mem((byte*)ptr, blocks * block_size); - const u32bit start = ((byte*)ptr - buffer) / block_size; + const u32bit offset = ((byte*)ptr - buffer) / block_size; - if(start == 0 && blocks == 64) + if(offset == 0 && blocks == 64) bitmap = ~bitmap; else { for(u32bit j = 0; j != blocks; ++j) - bitmap &= ~((u64bit)1 << (j+start)); + bitmap &= ~((u64bit)1 << (j+offset)); } - - how_empty = emptiness_metric(bitmap); } /************************************************* @@ -149,6 +142,7 @@ PREF_SIZE(choose_pref_size(p_size)), BLOCK_SIZE(64), BITMAP_SIZE(64) { mutex = global_state().get_mutex(); + last_used = blocks.begin(); } /************************************************* @@ -226,29 +220,20 @@ Mutex_Holder lock(mutex); - if(n <= BITMAP_SIZE * BLOCK_SIZE) + if(n > BITMAP_SIZE * BLOCK_SIZE) + dealloc_block(ptr, n); + else { const u32bit block_no = round_up(n, BLOCK_SIZE) / BLOCK_SIZE; - std::multiset::iterator i = blocks.begin(); - while(i != blocks.end()) - { - if(i->contains(ptr, block_no)) - { - Memory_Block block = *i; - blocks.erase(i); + std::vector::iterator i = + std::lower_bound(blocks.begin(), blocks.end(), ptr); - block.free(ptr, block_no); - blocks.insert(block); - return; - } - ++i; - } - - throw Invalid_State("Pointer released to the wrong allocator"); + if(i != blocks.end() && i->contains(ptr, block_no)) + i->free(ptr, block_no); + else + throw Invalid_State("Pointer released to the wrong allocator"); } - - dealloc_block(ptr, n); } /************************************************* @@ -256,20 +241,22 @@ *************************************************/ byte* Pooling_Allocator::allocate_blocks(u32bit n) { - std::multiset::iterator i = blocks.begin(); + if(blocks.size() == 0) + return 0; - while(i != blocks.end()) + assert(last_used != blocks.end()); + + std::vector::iterator i = last_used + 1; + + while(i != last_used) { - u32bit start = 0; + if(i == blocks.end()) + i = blocks.begin(); - if(i->can_alloc(start, n)) + byte* mem = i->alloc(n); + if(mem) { - Memory_Block block = *i; - blocks.erase(i); - - byte* mem = block.alloc(start, n); - blocks.insert(block); - + last_used = i; return mem; } @@ -289,16 +276,22 @@ const u32bit in_blocks = round_up(in_bytes, BLOCK_SIZE) / TOTAL_BLOCK_SIZE; const u32bit to_allocate = in_blocks * TOTAL_BLOCK_SIZE; - byte* ptr = static_cast(alloc_block(to_allocate)); - + void* ptr = alloc_block(to_allocate); if(ptr == 0) throw Memory_Exhaustion(); allocated.push_back(std::make_pair(ptr, to_allocate)); for(u32bit j = 0; j != in_blocks; ++j) - blocks.insert( - Memory_Block(ptr + j * TOTAL_BLOCK_SIZE, BITMAP_SIZE, BLOCK_SIZE) + { + byte* byte_ptr = static_cast(ptr); + + blocks.push_back( + Memory_Block(byte_ptr + j * TOTAL_BLOCK_SIZE, BITMAP_SIZE, BLOCK_SIZE) ); + } + std::sort(blocks.begin(), blocks.end()); + last_used = std::lower_bound(blocks.begin(), blocks.end(), ptr); } + } ============================================================ --- botan/mem_pool.h dbc05bb8b4dfc24bd07cfef84fd84d5541e8ff43 +++ botan/mem_pool.h 93a52922bc80de93c9d55a3aa7186339ac94c269 @@ -11,7 +11,6 @@ #include #include #include -#include namespace Botan { @@ -40,23 +39,22 @@ { u64bit bitmap; byte* buffer; - u32bit block_size, how_empty; + u32bit block_size; Memory_Block(void*, u32bit, u32bit); - bool can_alloc(u32bit&, u32bit) const throw(); bool contains(void*, u32bit) const throw(); - - byte* alloc(u32bit, u32bit) throw(); + byte* alloc(u32bit) throw(); void free(void*, u32bit) throw(); - bool operator<(const Memory_Block& other) const - { return (how_empty > other.how_empty); } + bool operator<(const void*) const; + bool operator<(const Memory_Block&) const; }; const u32bit PREF_SIZE, BLOCK_SIZE, BITMAP_SIZE; - std::multiset blocks; + std::vector blocks; + std::vector::iterator last_used; std::vector > allocated; Mutex* mutex; }; ============================================================ --- botan/mgf1.cpp 29ebaaf6613d812554b3d553f52aae167eaf3ea4 +++ botan/mgf1.cpp 4bfd485e042f369b4fe63795d322a58a040d5610 @@ -33,7 +33,7 @@ out += xored; out_len -= xored; - counter++; + ++counter; } } ============================================================ --- botan/mp_asm.cpp 6bbc7da9aa14f2a3851944eb594a5c0500c637a3 +++ botan/mp_asm.cpp 05eb2769a29c6c07d628340d508a13630fb7072e @@ -19,10 +19,10 @@ { word carry = 0; - const u32bit blocks = y_size - (y_size % 4); + const u32bit blocks = y_size - (y_size % 8); - for(u32bit j = 0; j != blocks; j += 4) - word4_add2(x + j, y + j, &carry); + for(u32bit j = 0; j != blocks; j += 8) + carry = word8_add2(x + j, y + j, carry); for(u32bit j = blocks; j != y_size; ++j) x[j] = word_add(x[j], y[j], &carry); @@ -48,10 +48,10 @@ word carry = 0; - const u32bit blocks = y_size - (y_size % 4); + const u32bit blocks = y_size - (y_size % 8); - for(u32bit j = 0; j != blocks; j += 4) - word4_add3(z + j, x + j, y + j, &carry); + for(u32bit j = 0; j != blocks; j += 8) + carry = word8_add3(z + j, x + j, y + j, carry); for(u32bit j = blocks; j != y_size; ++j) z[j] = word_add(x[j], y[j], &carry); @@ -72,7 +72,8 @@ *************************************************/ void bigint_add2(word x[], u32bit x_size, const word y[], u32bit y_size) { - x[x_size] += bigint_add2_nc(x, x_size, y, y_size); + if(bigint_add2_nc(x, x_size, y, y_size)) + ++x[x_size]; } /************************************************* @@ -81,8 +82,8 @@ void bigint_add3(word z[], const word x[], u32bit x_size, const word y[], u32bit y_size) { - const u32bit top_word = (x_size > y_size ? x_size : y_size); - z[top_word] += bigint_add3_nc(z, x, x_size, y, y_size); + if(bigint_add3_nc(z, x, x_size, y, y_size)) + ++z[(x_size > y_size ? x_size : y_size)]; } /************************************************* @@ -92,10 +93,10 @@ { word carry = 0; - const u32bit blocks = y_size - (y_size % 4); + const u32bit blocks = y_size - (y_size % 8); - for(u32bit j = 0; j != blocks; j += 4) - word4_sub2(x + j, y + j, &carry); + for(u32bit j = 0; j != blocks; j += 8) + carry = word8_sub2(x + j, y + j, carry); for(u32bit j = blocks; j != y_size; ++j) x[j] = word_sub(x[j], y[j], &carry); @@ -117,10 +118,10 @@ { word carry = 0; - const u32bit blocks = y_size - (y_size % 4); + const u32bit blocks = y_size - (y_size % 8); - for(u32bit j = 0; j != blocks; j += 4) - word4_sub3(z + j, x + j, y + j, &carry); + for(u32bit j = 0; j != blocks; j += 8) + carry = word8_sub3(z + j, x + j, y + j, carry); for(u32bit j = blocks; j != y_size; ++j) z[j] = word_sub(x[j], y[j], &carry); @@ -139,15 +140,15 @@ *************************************************/ void bigint_linmul2(word x[], u32bit x_size, word y) { - const u32bit blocks = x_size - (x_size % 4); + const u32bit blocks = x_size - (x_size % 8); word carry = 0; - for(u32bit j = 0; j != blocks; j += 4) - word4_linmul2(x + j, y, &carry); + for(u32bit j = 0; j != blocks; j += 8) + carry = word8_linmul2(x + j, y, carry); for(u32bit j = blocks; j != x_size; ++j) - x[j] = word_mul(x[j], y, &carry); + x[j] = word_madd2(x[j], y, carry, &carry); x[x_size] = carry; } @@ -157,70 +158,78 @@ *************************************************/ void bigint_linmul3(word z[], const word x[], u32bit x_size, word y) { - const u32bit blocks = x_size - (x_size % 4); + const u32bit blocks = x_size - (x_size % 8); word carry = 0; - for(u32bit j = 0; j != blocks; j += 4) - word4_linmul3(z + j, x + j, y, &carry); + for(u32bit j = 0; j != blocks; j += 8) + carry = word8_linmul3(z + j, x + j, y, carry); for(u32bit j = blocks; j != x_size; ++j) - z[j] = word_mul(x[j], y, &carry); + z[j] = word_madd2(x[j], y, carry, &carry); z[x_size] = carry; } /************************************************* -* Fused Linear Multiply / Addition Operation * +* Simple O(N^2) Multiplication * *************************************************/ -void bigint_linmul_add(word z[], u32bit z_size, - const word x[], u32bit x_size, word y) +void bigint_simple_mul(word z[], const word x[], u32bit x_size, + const word y[], u32bit y_size) { - word carry = 0; + const u32bit blocks = y_size - (y_size % 8); - const u32bit blocks = x_size - (x_size % 8); + clear_mem(z, x_size + y_size); - for(u32bit j = 0; j != blocks; j += 8) - word8_madd3(z + j, y, x + j, &carry); + for(u32bit j = 0; j != x_size; ++j) + { + const word x_j = x[j]; + word carry = 0; - for(u32bit j = blocks; j != x_size; ++j) - word_madd(x[j], y, z[j], carry, z + j, &carry); + for(u32bit k = 0; k != blocks; k += 8) + carry = word8_madd3(z + j + k, y + k, x_j, carry); - word carry2 = 0; - z[x_size] = word_add(z[x_size], carry, &carry2); - carry = carry2; + for(u32bit k = blocks; k != y_size; ++k) + z[j+k] = word_madd3(x_j, y[k], z[j+k], carry, &carry); - for(u32bit j = x_size + 1; carry && j != z_size; ++j) - { - ++z[j]; - carry = !z[j]; + z[j+y_size] = carry; } - z[z_size] += carry; } /************************************************* -* Simple O(N^2) Multiplication * +* Montgomery Reduction Algorithm * *************************************************/ -void bigint_simple_mul(word z[], const word x[], u32bit x_size, - const word y[], u32bit y_size) +void montgomery_reduce(word z[], u32bit z_size, + const word x[], u32bit x_size, word u) { - const u32bit blocks = y_size - (y_size % 8); - - clear_mem(z, x_size + y_size); - for(u32bit j = 0; j != x_size; ++j) { - const word x_j = x[j]; + word* z_j = z + j; + + const word y = z_j[0] * u; word carry = 0; + const u32bit blocks = x_size - (x_size % 8); + for(u32bit k = 0; k != blocks; k += 8) - word8_madd3(z + j + k, x_j, y + k, &carry); + carry = word8_madd3(z_j + k, x + k, y, carry); - for(u32bit k = blocks; k != y_size; ++k) - word_madd(x_j, y[k], z[j+k], carry, z + (j+k), &carry); + for(u32bit k = blocks; k != x_size; ++k) + z_j[k] = word_madd3(x[k], y, z_j[k], carry, &carry); - z[j+y_size] = carry; + word carry2 = 0; + z_j[x_size] = word_add(z_j[x_size], carry, &carry2); + carry = carry2; + + for(u32bit k = x_size + 1; carry && k != z_size - j; ++k) + { + ++z_j[k]; + carry = !z_j[k]; + } } + + if(bigint_cmp(z + x_size, x_size + 1, x, x_size) >= 0) + bigint_sub2(z + x_size, x_size + 1, x, x_size); } } ============================================================ --- botan/mp_asm.h 993bac9e1839b558d2679d07423b9c87797e8ec0 +++ botan/mp_asm.h c3fffadbd9d2c62f894a4112423da7a6f82fb77a @@ -15,7 +15,7 @@ #elif (BOTAN_MP_WORD_BITS == 32) typedef Botan::u64bit dword; #elif (BOTAN_MP_WORD_BITS == 64) - #error BOTAN_MP_WORD_BITS can only be 64 with the mp_asm64 module + #error BOTAN_MP_WORD_BITS can be 64 only with assembly support #else #error BOTAN_MP_WORD_BITS must be 8, 16, 32, or 64 #endif @@ -25,11 +25,11 @@ extern "C" { /************************************************* -* Word Multiply * +* Word Multiply/Add * *************************************************/ -inline word word_mul(word a, word b, word* carry) +inline word word_madd2(word a, word b, word c, word* carry) { - dword z = (dword)a * b + (*carry); + dword z = (dword)a * b + c; *carry = (word)(z >> BOTAN_MP_WORD_BITS); return (word)z; } @@ -37,12 +37,11 @@ /************************************************* * Word Multiply/Add * *************************************************/ -inline void word_madd(word a, word b, word c, word d, - word* out_low, word* out_high) +inline word word_madd3(word a, word b, word c, word d, word* carry) { dword z = (dword)a * b + c + d; - *out_low = (word)z; - *out_high = (word)(z >> BOTAN_MP_WORD_BITS); + *carry = (word)(z >> BOTAN_MP_WORD_BITS); + return (word)z; } /************************************************* @@ -50,12 +49,9 @@ *************************************************/ inline void word3_muladd(word* w2, word* w1, word* w0, word a, word b) { - dword z = (dword)a * b + (*w0); - *w0 = (word)z; - - word t1 = (word)(z >> BOTAN_MP_WORD_BITS); - *w1 += t1; - *w2 += (*w1 < t1) ? 1 : 0; + *w0 = word_madd2(a, b, *w0, &a); + *w1 += a; + *w2 += (*w1 < a) ? 1 : 0; } /************************************************* @@ -63,17 +59,15 @@ *************************************************/ inline void word3_muladd_2(word* w2, word* w1, word* w0, word a, word b) { - dword z = (dword)a * b; - word t0 = (word)z; - word t1 = (word)(z >> BOTAN_MP_WORD_BITS); + a = word_madd2(a, b, 0, &b); - *w0 += t0; - *w1 += t1 + ((*w0 < t0) ? 1 : 0); - *w2 += (*w1 < t1) ? 1 : 0; + *w0 += a; + *w1 += b + ((*w0 < a) ? 1 : 0); + *w2 += (*w1 < b) ? 1 : 0; - *w0 += t0; - *w1 += t1 + ((*w0 < t0) ? 1 : 0); - *w2 += (*w1 < t1) ? 1 : 0; + *w0 += a; + *w1 += b + ((*w0 < a) ? 1 : 0); + *w2 += (*w1 < b) ? 1 : 0; } } ============================================================ --- botan/mp_asmi.h 9a3768c28ba06cf6435a8131e52b5d01a73bcf3e +++ botan/mp_asmi.h f385ef7bad73f4d2cbc77a3bdb9c1dda9d8c8286 @@ -25,26 +25,36 @@ } /************************************************* -* Four Word Block Addition, Two Argument * +* Eight Word Block Addition, Two Argument * *************************************************/ -inline void word4_add2(word x[4], const word y[4], word* carry) +inline word word8_add2(word x[8], const word y[8], word carry) { - x[0] = word_add(x[0], y[0], carry); - x[1] = word_add(x[1], y[1], carry); - x[2] = word_add(x[2], y[2], carry); - x[3] = word_add(x[3], y[3], carry); + x[0] = word_add(x[0], y[0], &carry); + x[1] = word_add(x[1], y[1], &carry); + x[2] = word_add(x[2], y[2], &carry); + x[3] = word_add(x[3], y[3], &carry); + x[4] = word_add(x[4], y[4], &carry); + x[5] = word_add(x[5], y[5], &carry); + x[6] = word_add(x[6], y[6], &carry); + x[7] = word_add(x[7], y[7], &carry); + return carry; } /************************************************* -* Four Word Block Addition, Three Argument * +* Eight Word Block Addition, Three Argument * *************************************************/ -inline void word4_add3(word z[4], const word x[4], - const word y[4], word* carry) +inline word word8_add3(word z[8], const word x[8], + const word y[8], word carry) { - z[0] = word_add(x[0], y[0], carry); - z[1] = word_add(x[1], y[1], carry); - z[2] = word_add(x[2], y[2], carry); - z[3] = word_add(x[3], y[3], carry); + z[0] = word_add(x[0], y[0], &carry); + z[1] = word_add(x[1], y[1], &carry); + z[2] = word_add(x[2], y[2], &carry); + z[3] = word_add(x[3], y[3], &carry); + z[4] = word_add(x[4], y[4], &carry); + z[5] = word_add(x[5], y[5], &carry); + z[6] = word_add(x[6], y[6], &carry); + z[7] = word_add(x[7], y[7], &carry); + return carry; } /************************************************* @@ -60,63 +70,84 @@ } /************************************************* -* Four Word Block Subtraction, Two Argument * +* Eight Word Block Subtraction, Two Argument * *************************************************/ -inline void word4_sub2(word x[4], const word y[4], word* carry) +inline word word8_sub2(word x[4], const word y[4], word carry) { - x[0] = word_sub(x[0], y[0], carry); - x[1] = word_sub(x[1], y[1], carry); - x[2] = word_sub(x[2], y[2], carry); - x[3] = word_sub(x[3], y[3], carry); + x[0] = word_sub(x[0], y[0], &carry); + x[1] = word_sub(x[1], y[1], &carry); + x[2] = word_sub(x[2], y[2], &carry); + x[3] = word_sub(x[3], y[3], &carry); + x[4] = word_sub(x[4], y[4], &carry); + x[5] = word_sub(x[5], y[5], &carry); + x[6] = word_sub(x[6], y[6], &carry); + x[7] = word_sub(x[7], y[7], &carry); + return carry; } /************************************************* -* Four Word Block Subtraction, Three Argument * +* Eight Word Block Subtraction, Three Argument * *************************************************/ -inline void word4_sub3(word z[4], const word x[4], - const word y[4], word* carry) +inline word word8_sub3(word z[8], const word x[8], + const word y[8], word carry) { - z[0] = word_sub(x[0], y[0], carry); - z[1] = word_sub(x[1], y[1], carry); - z[2] = word_sub(x[2], y[2], carry); - z[3] = word_sub(x[3], y[3], carry); + z[0] = word_sub(x[0], y[0], &carry); + z[1] = word_sub(x[1], y[1], &carry); + z[2] = word_sub(x[2], y[2], &carry); + z[3] = word_sub(x[3], y[3], &carry); + z[4] = word_sub(x[4], y[4], &carry); + z[5] = word_sub(x[5], y[5], &carry); + z[6] = word_sub(x[6], y[6], &carry); + z[7] = word_sub(x[7], y[7], &carry); + return carry; } /************************************************* -* Four Word Block Linear Multiplication * +* Eight Word Block Linear Multiplication * *************************************************/ -inline void word4_linmul2(word x[4], word y, word* carry) +inline word word8_linmul2(word x[4], word y, word carry) { - x[0] = word_mul(x[0], y, carry); - x[1] = word_mul(x[1], y, carry); - x[2] = word_mul(x[2], y, carry); - x[3] = word_mul(x[3], y, carry); + x[0] = word_madd2(x[0], y, carry, &carry); + x[1] = word_madd2(x[1], y, carry, &carry); + x[2] = word_madd2(x[2], y, carry, &carry); + x[3] = word_madd2(x[3], y, carry, &carry); + x[4] = word_madd2(x[4], y, carry, &carry); + x[5] = word_madd2(x[5], y, carry, &carry); + x[6] = word_madd2(x[6], y, carry, &carry); + x[7] = word_madd2(x[7], y, carry, &carry); + return carry; } /************************************************* -* Four Word Block Linear Multiplication * +* Eight Word Block Linear Multiplication * *************************************************/ -inline void word4_linmul3(word z[4], const word x[4], word y, word* carry) +inline word word8_linmul3(word z[8], const word x[8], word y, word carry) { - z[0] = word_mul(x[0], y, carry); - z[1] = word_mul(x[1], y, carry); - z[2] = word_mul(x[2], y, carry); - z[3] = word_mul(x[3], y, carry); + z[0] = word_madd2(x[0], y, carry, &carry); + z[1] = word_madd2(x[1], y, carry, &carry); + z[2] = word_madd2(x[2], y, carry, &carry); + z[3] = word_madd2(x[3], y, carry, &carry); + z[4] = word_madd2(x[4], y, carry, &carry); + z[5] = word_madd2(x[5], y, carry, &carry); + z[6] = word_madd2(x[6], y, carry, &carry); + z[7] = word_madd2(x[7], y, carry, &carry); + return carry; } /************************************************* -* Eight Word Block Multiply-Add * +* Eight Word Block Multiply/Add * *************************************************/ -inline void word8_madd3(word z[], word x, const word y[], word* carry) +inline word word8_madd3(word z[8], const word x[8], word y, word carry) { - word_madd(x, y[0], z[0], *carry, z + 0, carry); - word_madd(x, y[1], z[1], *carry, z + 1, carry); - word_madd(x, y[2], z[2], *carry, z + 2, carry); - word_madd(x, y[3], z[3], *carry, z + 3, carry); - word_madd(x, y[4], z[4], *carry, z + 4, carry); - word_madd(x, y[5], z[5], *carry, z + 5, carry); - word_madd(x, y[6], z[6], *carry, z + 6, carry); - word_madd(x, y[7], z[7], *carry, z + 7, carry); + z[0] = word_madd3(x[0], y, z[0], carry, &carry); + z[1] = word_madd3(x[1], y, z[1], carry, &carry); + z[2] = word_madd3(x[2], y, z[2], carry, &carry); + z[3] = word_madd3(x[3], y, z[3], carry, &carry); + z[4] = word_madd3(x[4], y, z[4], carry, &carry); + z[5] = word_madd3(x[5], y, z[5], carry, &carry); + z[6] = word_madd3(x[6], y, z[6], carry, &carry); + z[7] = word_madd3(x[7], y, z[7], carry, &carry); + return carry; } } ============================================================ --- botan/mp_core.h 2247e0cd44d00ef46302f75bf74230b6bf4ba765 +++ botan/mp_core.h db979ea2eeca9075d1775a7955afccc4502eda26 @@ -47,6 +47,11 @@ void bigint_linmul_add(word[], u32bit, const word[], u32bit, word); /************************************************* +* Modular Reduction * +*************************************************/ +void montgomery_reduce(word[], u32bit, const word[], u32bit, word); + +/************************************************* * Misc Utility Operations * *************************************************/ u32bit bigint_divcore(word, word, word, word, word, word); ============================================================ --- botan/mp_misc.cpp da1628dfed644709a2b6e1ea22f0ee352e617b1b +++ botan/mp_misc.cpp de05320fc3a8f2735f5dff92ee6e9b821fac4a4e @@ -6,6 +6,8 @@ #include #include +#include + namespace Botan { extern "C" { @@ -17,8 +19,8 @@ word x1, word x2, word x3) { word y0 = 0; - word_madd(q, y2, 0, 0, &y2, &y0); - word_madd(q, y1, y0, 0, &y1, &y0); + y2 = word_madd2(q, y2, 0, &y0); + y1 = word_madd2(q, y1, y0, &y0); if(y0 > x1) return 1; if(y0 < x1) return 0; @@ -79,11 +81,10 @@ *************************************************/ word bigint_modop(word n1, word n0, word d) { - word z0 = n1 / d, z1 = bigint_divop(n1, n0, d); - word carry = 0; - word_madd(z1, d, 0, 0, &z1, &carry); - word_madd(z0, d, carry, 0, &z0, &carry); - return (n0-z1); + word z0 = bigint_divop(n1, n0, d); + word dummy = 0; + z0 = word_madd2(z0, d, 0, &dummy); + return (n0-z0); } /************************************************* ============================================================ --- botan/mp_mul.cpp 76e5669ba8841469d4bd5647f467a20094fe5e15 +++ botan/mp_mul.cpp f2d1306395f75a0f325301d98a416a755abc4283 @@ -74,7 +74,9 @@ /************************************************* * Pick a good size for the Karatsuba multiply * *************************************************/ -u32bit karatsuba_size(u32bit x_size, u32bit x_sw, u32bit y_size, u32bit y_sw) +u32bit karatsuba_size(u32bit z_size, + u32bit x_size, u32bit x_sw, + u32bit y_size, u32bit y_sw) { if(x_sw > y_size || y_sw > x_size) return 0; @@ -96,12 +98,22 @@ } for(u32bit j = start; j <= end; ++j) - if(j % 2 == 0 && x_sw <= j && j <= x_size && y_sw <= j && j <= y_size) + { + if(j % 2) + continue; + + if(2*j > z_size) + return 0; + + if(x_sw <= j && j <= x_size && y_sw <= j && j <= y_size) { - if(j % 4 == 2 && (j+2) < x_size && (j+2) < y_size) - return (j+2); + if(j % 4 == 2 && + (j+2) <= x_size && (j+2) <= y_size && 2*(j+2) <= z_size) + return j+2; return j; } + } + return 0; } @@ -150,7 +162,7 @@ return; } - const u32bit N = karatsuba_size(x_size, x_sw, y_size, y_sw); + const u32bit N = karatsuba_size(z_size, x_size, x_sw, y_size, y_sw); if(N) { ============================================================ --- botan/mp_numth.cpp ee21088447a4ea56f7703a8f48428619f20f2c9e +++ botan/mp_numth.cpp 115cec8f3c0c2bee00a8e7cc20da04eeee89a9c9 @@ -60,20 +60,4 @@ return r; } -/************************************************* -* Multiply-Modulo Operation * -*************************************************/ -BigInt mul_mod(const BigInt& a, const BigInt& b, const BigInt& m) - { - if(a.is_negative() || b.is_negative()) - throw Invalid_Argument("mul_mod: First two arguments must be >= 0"); - if(m <= 0) - throw Invalid_Argument("mul_mod: Modulo must be positive"); - - BigInt r = a; - r *= b; - r %= m; - return r; - } - } ============================================================ --- botan/mp_sqr.cpp e80b8be2f66892e1d9c161a54956a42df08975d5 +++ botan/mp_sqr.cpp d81181c581f15a26731a297aa31fd66cfd1a4a72 @@ -63,7 +63,7 @@ /************************************************* * Pick a good size for the Karatsuba squaring * *************************************************/ -u32bit karatsuba_size(u32bit x_size, u32bit x_sw) +u32bit karatsuba_size(u32bit z_size, u32bit x_size, u32bit x_sw) { if(x_sw == x_size) { @@ -73,12 +73,18 @@ } for(u32bit j = x_sw; j <= x_size; ++j) - if(j % 2 == 0 && x_sw <= j && j <= x_size) - { - if(j % 4 == 2 && (j+2) < x_size) - return (j+2); - return j; - } + { + if(j % 2) + continue; + + if(2*j > z_size) + return 0; + + if(j % 4 == 2 && (j+2) <= x_size && 2*(j+2) <= z_size) + return j+2; + return j; + } + return 0; } @@ -114,7 +120,7 @@ return; } - const u32bit N = karatsuba_size(x_size, x_sw); + const u32bit N = karatsuba_size(z_size, x_size, x_sw); if(N) { ============================================================ --- botan/numthry.cpp dc52a7d8bd533fef023056d599d9791a0a932dab +++ botan/numthry.cpp e769699e0e76d55ab3382be2032a97fce22f733f @@ -1,10 +1,9 @@ /************************************************* * Number Theory Source File * * (C) 1999-2006 The Botan Project * *************************************************/ #include -#include #include #include @@ -76,7 +75,8 @@ if(n.is_zero()) return 0; u32bit bits = 0, max_bits = n.bits(); - while((n.get_bit(bits) == 0) && bits < max_bits) bits++; + while((n.get_bit(bits) == 0) && bits < max_bits) + ++bits; return bits; } @@ -349,7 +349,7 @@ for(u32bit j = 1; j != s; ++j) { UI::pulse(UI::PRIME_TESTING); - y = reducer->reduce(square(y)); + y = reducer.square(y); if(y == 1) return false; @@ -373,15 +373,7 @@ r = n_minus_1 >> s; pow_mod = Fixed_Exponent_Power_Mod(r, n); - reducer = get_reducer(n); + reducer = Modular_Reducer(n); } -/************************************************* -* Miller-Rabin Constructor * -*************************************************/ -MillerRabin_Test::~MillerRabin_Test() - { - delete reducer; - } - } ============================================================ --- botan/numthry.h e7a209c8c3b650b8627798c12d01a57a009dfe89 +++ botan/numthry.h b52efe2ea7d807608717f2b5e5a8ea430e1907a1 @@ -7,6 +7,7 @@ #define BOTAN_NUMBTHRY_H__ #include +#include #include namespace Botan { @@ -16,7 +17,6 @@ *************************************************/ BigInt mul_add(const BigInt&, const BigInt&, const BigInt&); BigInt sub_mul(const BigInt&, const BigInt&, const BigInt&); -BigInt mul_mod(const BigInt&, const BigInt&, const BigInt&); /************************************************* * Number Theory Functions * @@ -24,8 +24,6 @@ inline BigInt abs(const BigInt& n) { return n.abs(); } void divide(const BigInt&, const BigInt&, BigInt&, BigInt&); -void positive_divide(const BigInt&, const BigInt&, BigInt&, BigInt&); -void modifying_divide(BigInt&, BigInt&, BigInt&); BigInt gcd(const BigInt&, const BigInt&); BigInt lcm(const BigInt&, const BigInt&); @@ -81,16 +79,12 @@ { public: bool passes_test(const BigInt&); - MillerRabin_Test(const BigInt&); - ~MillerRabin_Test(); private: - MillerRabin_Test(const MillerRabin_Test&) {} - MillerRabin_Test& operator=(const MillerRabin_Test&) { return (*this); } BigInt n, r, n_minus_1; u32bit s; Fixed_Exponent_Power_Mod pow_mod; - class ModularReducer* reducer; + Modular_Reducer reducer; }; } ============================================================ --- botan/out_buf.cpp 2489a9bec82d69346621189012595616f879bf93 +++ botan/out_buf.cpp 84c593b7de4a4e21920b9a68146f9b061ae8384a @@ -67,7 +67,7 @@ { delete buffers[0]; buffers.pop_front(); - offset++; + ++offset; } else break; ============================================================ --- botan/pem.cpp eef9e1120e7547f53786198636a799358f419260 +++ botan/pem.cpp d18edca4aece3b15d7383d0fc8c98109cc50f484 @@ -69,7 +69,7 @@ if(!source.read_byte(b)) throw Decoding_Error("PEM: No PEM header found"); if(b == PEM_HEADER1[position]) - position++; + ++position; else if(position >= RANDOM_CHAR_LIMIT) throw Decoding_Error("PEM: Malformed PEM header"); else @@ -82,7 +82,7 @@ if(!source.read_byte(b)) throw Decoding_Error("PEM: No PEM header found"); if(b == PEM_HEADER2[position]) - position++; + ++position; else if(position) throw Decoding_Error("PEM: Malformed PEM header"); @@ -101,7 +101,7 @@ if(!source.read_byte(b)) throw Decoding_Error("PEM: No PEM trailer found"); if(b == PEM_TRAILER[position]) - position++; + ++position; else if(position) throw Decoding_Error("PEM: Malformed PEM trailer"); @@ -131,7 +131,7 @@ for(u32bit j = 0; j != got; ++j) { if(search_buf[j] == PEM_HEADER[index]) - index++; + ++index; else index = 0; if(index == PEM_HEADER.size()) ============================================================ --- botan/pk_algs.cpp 4eaf5dca76443211e7486ca651ae5521d7cb7181 +++ botan/pk_algs.cpp 004d3768624059675382b2c999587af76e10c943 @@ -5,6 +5,11 @@ #include #include +#include +#include +#include +#include +#include namespace Botan { @@ -14,6 +19,11 @@ X509_PublicKey* get_public_key(const std::string& alg_name) { if(alg_name == "RSA") return new RSA_PublicKey; + else if(alg_name == "DSA") return new DSA_PublicKey; + else if(alg_name == "DH") return new DH_PublicKey; + else if(alg_name == "NR") return new NR_PublicKey; + else if(alg_name == "RW") return new RW_PublicKey; + else if(alg_name == "ELG") return new ElGamal_PublicKey; else return 0; } @@ -24,6 +34,11 @@ PKCS8_PrivateKey* get_private_key(const std::string& alg_name) { if(alg_name == "RSA") return new RSA_PrivateKey; + else if(alg_name == "DSA") return new DSA_PrivateKey; + else if(alg_name == "DH") return new DH_PrivateKey; + else if(alg_name == "NR") return new NR_PrivateKey; + else if(alg_name == "RW") return new RW_PrivateKey; + else if(alg_name == "ELG") return new ElGamal_PrivateKey; else return 0; } ============================================================ --- botan/pk_core.cpp 460ac1a0935469301fcb2e28f7b2561340cc4ef7 +++ botan/pk_core.cpp bc6d8c019e76bff51ffef875a0f4f14e996949a6 @@ -39,7 +39,7 @@ { BigInt k = blinding_factor(n.bits()); if(k != 0) - blinder.initialize(power_mod(k, e, n), inverse_mod(k, n), n); + blinder = Blinder(power_mod(k, e, n), inverse_mod(k, n), n); } } @@ -190,7 +190,7 @@ BigInt k = blinding_factor(p.bits()); if(k != 0) - blinder.initialize(k, power_mod(k, x, p), p); + blinder = Blinder(k, power_mod(k, x, p), p); } } @@ -252,7 +252,7 @@ const BigInt& p = group.get_p(); BigInt k = blinding_factor(p.bits()); if(k != 0) - blinder.initialize(k, power_mod(inverse_mod(k, p), x, p), p); + blinder = Blinder(k, power_mod(inverse_mod(k, p), x, p), p); } /************************************************* ============================================================ --- botan/pkcs5.cpp 573e3e5f7867ba0e29237a8ce982dd990d7151e8 +++ botan/pkcs5.cpp a86a2c094f40ac695129fccd11be68e872206e8b @@ -98,7 +98,7 @@ key_len -= T_size; T += T_size; - counter++; + ++counter; } return key; ============================================================ --- botan/policy.cpp e6c56d910f2460a72d41603c4a32b99aa4a6c145 +++ botan/policy.cpp 813fe31d7f72e934ac221a5b08edec78dab19890 @@ -202,6 +202,8 @@ state->set_option("conf", "rng/es_files", "/dev/urandom:/dev/random"); state->set_option("conf", "rng/egd_path", "/var/run/egd-pool:/dev/egd-pool"); + state->set_option("conf", "rng/slow_poll_request", "256"); + state->set_option("conf", "rng/fast_poll_request", "64"); state->set_option("conf", "x509/validity_slack", "24h"); state->set_option("conf", "x509/v1_assume_ca", "false"); @@ -225,6 +227,7 @@ state->set_option("conf", "x509/exts/key_usage", "critical"); state->set_option("conf", "x509/exts/extended_key_usage", "yes"); state->set_option("conf", "x509/exts/crl_number", "yes"); + } /************************************************* ============================================================ --- botan/pow_mod.cpp 622ad0b2f9cc40a01000c02e1e486e4bd40140b6 +++ botan/pow_mod.cpp 9d95b94f7939eda78fceec8380fec8e394296656 @@ -114,6 +114,9 @@ return Power_Mod::NO_HINTS; } +/************************************************* +* Choose potentially useful hints * +*************************************************/ Power_Mod::Usage_Hints choose_exp_hints(const BigInt& e, const BigInt& n) { const u32bit e_bits = e.bits(); ============================================================ --- botan/powm_fw.cpp b1a47e40d185947a51ffcb41597568c748b5fdda +++ botan/powm_fw.cpp b6598037d0f1f141294c33f3aa0f46caf921ccd4 @@ -5,8 +5,6 @@ #include #include -#include -#include #include namespace Botan { @@ -42,7 +40,7 @@ if(hints & Power_Mod::EXP_IS_LARGE) window_bits += 2; if(hints & Power_Mod::BASE_IS_FIXED) - window_bits++; + ++window_bits; return window_bits; } @@ -67,7 +65,7 @@ g.resize((1 << window_bits) - 1); g[0] = base; for(u32bit j = 1; j != g.size(); ++j) - g[j] = reducer->multiply(g[j-1], g[0]); + g[j] = reducer.multiply(g[j-1], g[0]); } /************************************************* @@ -81,47 +79,24 @@ for(u32bit j = exp_nibbles; j > 0; --j) { for(u32bit k = 0; k != window_bits; ++k) - x = reducer->square(x); + x = reducer.square(x); u32bit nibble = exp.get_substring(window_bits*(j-1), window_bits); if(nibble) - x = reducer->multiply(x, g.at(nibble-1)); + x = reducer.multiply(x, g.at(nibble-1)); } return x; } /************************************************* -* Make a copy of this exponentiator * -*************************************************/ -Modular_Exponentiator* Fixed_Window_Exponentiator::copy() const - { - Fixed_Window_Exponentiator* out = - new Fixed_Window_Exponentiator(reducer->get_modulus(), hints); - - out->g = g; - out->exp = exp; - out->window_bits = window_bits; - - return out; - } - -/************************************************* * Fixed_Window_Exponentiator Constructor * *************************************************/ Fixed_Window_Exponentiator::Fixed_Window_Exponentiator(const BigInt& n, Power_Mod::Usage_Hints hints) { - reducer = get_reducer(n); + reducer = Modular_Reducer(n); this->hints = hints; window_bits = 0; } -/************************************************* -* Fixed_Window_Exponentiator Destructor * -*************************************************/ -Fixed_Window_Exponentiator::~Fixed_Window_Exponentiator() - { - delete reducer; - } - } ============================================================ --- botan/powm_mnt.cpp a9e9d38aa4b3a66ef19d4974bb2e78625c77aa66 +++ botan/powm_mnt.cpp 81992708ed35a17cfd114f18604aa712d2609f6b @@ -12,24 +12,6 @@ namespace { /************************************************* -* Perform the actual Montgomery reduction * -*************************************************/ -void montgomery_reduce(word* z, u32bit z_size, - const word* mod_bits, u32bit mod_size, - word mod_prime) - { - for(u32bit j = 0; j != mod_size; ++j) - bigint_linmul_add(z + j, z_size - j, - mod_bits, mod_size, z[j] * mod_prime); - - for(u32bit j = 0; j != mod_size + 1; ++j) - z[j] = z[j + mod_size]; - - if(bigint_cmp(z, mod_size + 1, mod_bits, mod_size) >= 0) - bigint_sub2(z, mod_size + 1, mod_bits, mod_size); - } - -/************************************************* * Try to choose a good window size * *************************************************/ u32bit choose_window_bits(u32bit exp_bits, u32bit base_bits, @@ -56,7 +38,7 @@ if(hints & Power_Mod::BASE_IS_FIXED) window_bits += 2; if(hints & Power_Mod::EXP_IS_LARGE) - window_bits++; + ++window_bits; return window_bits; } @@ -81,9 +63,34 @@ g.resize((1 << window_bits) - 1); - g[0] = reduce(((base >= modulus) ? (base % modulus) : base) * R2); + SecureVector z(2 * (mod_words + 1)); + + g[0] = (base >= modulus) ? (base % modulus) : base; + bigint_mul(z.begin(), z.size(), + g[0].data(), g[0].size(), g[0].sig_words(), + R2.data(), R2.size(), R2.sig_words()); + montgomery_reduce(z.begin(), z.size(), modulus.data(), mod_words, + mod_prime); + g[0].get_reg().set(z + mod_words, mod_words + 1); + + const BigInt& x = g[0]; + const u32bit x_sig = x.sig_words(); + for(u32bit j = 1; j != g.size(); ++j) - g[j] = reduce(g[j-1] * g[0]); + { + const BigInt& y = g[j-1]; + const u32bit y_sig = y.sig_words(); + + z.clear(); + bigint_mul(z.begin(), z.size(), + x.data(), x.size(), x_sig, + y.data(), y.size(), y_sig); + + montgomery_reduce(z.begin(), z.size(), modulus.data(), mod_words, + mod_prime); + + g[j].get_reg().set(z + mod_words, mod_words + 1); + } } /************************************************* @@ -91,24 +98,22 @@ *************************************************/ BigInt Montgomery_Exponentiator::execute() const { - const u32bit exp_nibbles = (exp.bits() + window_bits - 1) / window_bits; - const u32bit mod_size = modulus.sig_words(); + const u32bit exp_nibbles = (exp_bits + window_bits - 1) / window_bits; - BigInt z = R_mod; - SecureVector workspace(2 * (mod_size + 1)); + BigInt x = R_mod; + SecureVector z(2 * (mod_words + 1)); for(u32bit j = exp_nibbles; j > 0; --j) { for(u32bit k = 0; k != window_bits; ++k) { - workspace.clear(); - bigint_sqr(workspace.begin(), workspace.size(), - z.data(), z.size(), z.sig_words()); + z.clear(); + bigint_sqr(z.begin(), z.size(), + x.data(), x.size(), x.sig_words()); - const u32bit mod_size = modulus.sig_words(); - montgomery_reduce(workspace.begin(), workspace.size(), - modulus.data(), mod_size, mod_prime); - z.get_reg().set(workspace.begin(), mod_size + 1); + montgomery_reduce(z.begin(), z.size(), modulus.data(), mod_words, + mod_prime); + x.get_reg().set(z + mod_words, mod_words + 1); } u32bit nibble = exp.get_substring(window_bits*(j-1), window_bits); @@ -116,54 +121,27 @@ { const BigInt& y = g.at(nibble-1); - workspace.clear(); - bigint_mul(workspace.begin(), workspace.size(), - z.data(), z.size(), z.sig_words(), + z.clear(); + bigint_mul(z.begin(), z.size(), + x.data(), x.size(), x.sig_words(), y.data(), y.size(), y.sig_words()); - montgomery_reduce(workspace.begin(), workspace.size(), - modulus.data(), mod_size, mod_prime); - z.get_reg().set(workspace.begin(), mod_size + 1); + montgomery_reduce(z.begin(), z.size(), modulus.data(), mod_words, + mod_prime); + x.get_reg().set(z + mod_words, mod_words + 1); } } - workspace.clear(); - workspace.copy(z.data(), z.size()); + z.clear(); + z.copy(x.data(), x.size()); - montgomery_reduce(workspace.begin(), workspace.size(), - modulus.data(), mod_size, mod_prime); - - BigInt x; - x.get_reg().set(workspace.begin(), mod_size + 1); + montgomery_reduce(z.begin(), z.size(), modulus.data(), mod_words, + mod_prime); + x.get_reg().set(z + mod_words, mod_words + 1); return x; } /************************************************* -* Montgomery Reduction * -*************************************************/ -BigInt Montgomery_Exponentiator::reduce(const BigInt& n) const - { - const u32bit mod_size = modulus.sig_words(); - - SecureVector z(2 * (mod_size + 1)); - z.copy(n.data(), n.size()); - - montgomery_reduce(z.begin(), z.size(), modulus.data(), mod_size, mod_prime); - - BigInt x; - x.get_reg().set(z.begin(), mod_size + 1); - return x; - } - -/************************************************* -* Make a copy of this exponentiator * -*************************************************/ -Modular_Exponentiator* Montgomery_Exponentiator::copy() const - { - return new Montgomery_Exponentiator(*this); - } - -/************************************************* * Montgomery_Exponentiator Constructor * *************************************************/ Montgomery_Exponentiator::Montgomery_Exponentiator(const BigInt& mod, @@ -178,13 +156,15 @@ this->hints = hints; modulus = mod; + mod_words = modulus.sig_words(); + BigInt mod_prime_bn(BigInt::Power2, MP_WORD_BITS); mod_prime = (mod_prime_bn - inverse_mod(modulus, mod_prime_bn)).word_at(0); - R_mod = BigInt(BigInt::Power2, MP_WORD_BITS * modulus.sig_words()); + R_mod = BigInt(BigInt::Power2, MP_WORD_BITS * mod_words); R_mod %= modulus; - R2 = BigInt(BigInt::Power2, 2 * MP_WORD_BITS * modulus.sig_words()); + R2 = BigInt(BigInt::Power2, 2 * MP_WORD_BITS * mod_words); R2 %= modulus; } ============================================================ --- botan/reducer.cpp c9bfcbf3595d7d6f59a1e04275a68eb89054b10e +++ botan/reducer.cpp 23b3888f2cf65aa90bea12dfa8d60e3027d649a9 @@ -8,105 +8,91 @@ #include #include -namespace Botan { +#include // for testing -namespace { +namespace Botan { /************************************************* -* Barrett Reducer * +* Modular_Reducer Constructor * *************************************************/ -class Barrett_Reducer : public ModularReducer +Modular_Reducer::Modular_Reducer(const BigInt& mod) { - public: - BigInt multiply(const BigInt&, const BigInt&) const; - BigInt square(const BigInt& x) const - { return reduce(Botan::square(x)); } + if(mod <= 0) + throw Invalid_Argument("Modular_Reducer: modulus must be positive"); - BigInt reduce(const BigInt&) const; - const BigInt& get_modulus() const { return modulus; } + modulus = mod; + mod_words = modulus.sig_words(); - Barrett_Reducer(const BigInt&); - private: - BigInt modulus, mu; - mutable BigInt t1, t2; - u32bit max_bits, k; - }; + modulus_2 = Botan::square(modulus); + mod2_words = modulus_2.sig_words(); -/************************************************* -* Barrett_Reducer Constructor * -*************************************************/ -Barrett_Reducer::Barrett_Reducer(const BigInt& mod) : modulus(mod) - { - if(modulus <= 0) - throw Invalid_Argument("Barrett_Reducer: modulus must be positive"); - - if(modulus.size() > 8 && !power_of_2(modulus.size())) - modulus.grow_reg((1 << high_bit(modulus.size())) - modulus.size()); - - k = modulus.sig_words(); - mu.set_bit(MP_WORD_BITS * 2 * k); - mu /= modulus; - max_bits = MP_WORD_BITS * 2 * k; - - if(mu.size() > 8 && !power_of_2(mu.size())) - mu.grow_reg((1 << high_bit(mu.size())) - mu.size()); + mu = BigInt(BigInt::Power2, 2 * MP_WORD_BITS * mod_words) / modulus; + mu_words = mu.sig_words(); } /************************************************* * Barrett Reduction * *************************************************/ -BigInt Barrett_Reducer::reduce(const BigInt& x) const +BigInt Modular_Reducer::reduce(const BigInt& x) const { - if(x.is_positive() && x < modulus) + if(mod_words == 0) + throw Invalid_State("Modular_Reducer: Never initalized"); + + BigInt t1 = x; + t1.set_sign(BigInt::Positive); + + if(t1 < modulus) + { + if(x.is_negative() && t1.is_nonzero()) + return modulus - t1; return x; - if(x.bits() > max_bits) + } + + if(t1 >= modulus_2) return (x % modulus); - t1 = x; - t1.set_sign(BigInt::Positive); - - t1 >>= (MP_WORD_BITS * (k - 1)); + t1 >>= (MP_WORD_BITS * (mod_words - 1)); t1 *= mu; - t1 >>= (MP_WORD_BITS * (k + 1)); + t1 >>= (MP_WORD_BITS * (mod_words + 1)); t1 *= modulus; - t1.mask_bits(MP_WORD_BITS * (k+1)); + t1.mask_bits(MP_WORD_BITS * (mod_words+1)); - t2 = x; + BigInt t2 = x; t2.set_sign(BigInt::Positive); - t2.mask_bits(MP_WORD_BITS * (k+1)); + t2.mask_bits(MP_WORD_BITS * (mod_words+1)); - t2 -= t1; + t1 = t2 - t1; - if(t2.is_negative()) + if(t1.is_negative()) { - BigInt b_to_k1(BigInt::Power2, MP_WORD_BITS * (k+1)); - t2 += b_to_k1; + BigInt b_to_k1(BigInt::Power2, MP_WORD_BITS * (mod_words+1)); + t1 += b_to_k1; } - while(t2 >= modulus) - t2 -= modulus; - if(x.is_negative() && t2.is_nonzero()) - t2 = modulus - t2; + while(t1 >= modulus) + t1 -= modulus; - return t2; + if(x.is_negative() && t1.is_nonzero()) + t1 = modulus - t1; + + return t1; } /************************************************* * Multiply, followed by a reduction * *************************************************/ -BigInt Barrett_Reducer::multiply(const BigInt& x, const BigInt& y) const +BigInt Modular_Reducer::multiply(const BigInt& x, const BigInt& y) const { return reduce(x * y); } -} - /************************************************* -* Acquire a modular reducer * +* Square, followed by a reduction * *************************************************/ -ModularReducer* get_reducer(const BigInt& n) +BigInt Modular_Reducer::square(const BigInt& x) const { - return new Barrett_Reducer(n); + return reduce(Botan::square(x)); } + } ============================================================ --- botan/reducer.h 5958c1b425b899e44d943db154b4707818789d2b +++ botan/reducer.h cf802c2483d8e46c6ac2b42268012f0d4dd33afa @@ -11,25 +11,24 @@ namespace Botan { /************************************************* -* Modular Reducer Base Class * +* Modular Reducer * *************************************************/ -class ModularReducer +class Modular_Reducer { public: - virtual BigInt multiply(const BigInt&, const BigInt&) const = 0; - virtual BigInt square(const BigInt&) const = 0; - virtual BigInt reduce(const BigInt&) const = 0; + BigInt multiply(const BigInt&, const BigInt&) const; + BigInt square(const BigInt&) const; + BigInt reduce(const BigInt&) const; - virtual const BigInt& get_modulus() const = 0; + bool initialized() const { return (mod_words != 0); } - virtual ~ModularReducer() {} + Modular_Reducer() { mod_words = 0; } + Modular_Reducer(const BigInt&); + private: + BigInt modulus, modulus_2, mu; + u32bit mod_words, mod2_words, mu_words; }; -/************************************************* -* Get a modular reducer * -*************************************************/ -ModularReducer* get_reducer(const BigInt&); - } #endif ============================================================ --- botan/secmem.h 7e435e885f9a0f44a51989c8f70615d0f88aabb3 +++ botan/secmem.h 19762c45fca26ca29ba735d42d5343ab3f4b0976 @@ -31,11 +31,10 @@ T* end() { return (buf + size()); } const T* end() const { return (buf + size()); } - bool operator==(const MemoryRegion& in) const + bool operator==(const MemoryRegion& other) const { - if(size() == in.size() && std::equal(begin(), end(), in.begin())) - return true; - return false; + return (size() == other.size() && + same_mem(buf, other.buf, size())); } bool operator<(const MemoryRegion&) const; ============================================================ --- botan/x509_ca.cpp aa8c7dcf99a2c1e9e8db19bcdf7a6fe9bf18eecb +++ botan/x509_ca.cpp 569c0382bfcb001cc5ca92e359c84686a165dbde @@ -11,6 +11,7 @@ #include #include #include +#include #include #include ============================================================ --- botan/x509_obj.cpp cc7e829b3d3013e84ed72e06fdb17e9264f766a2 +++ botan/x509_obj.cpp 497e4b4edbbfff5066d44b17971cb09e4ddf525d @@ -6,6 +6,7 @@ #include #include #include +#include namespace Botan { ============================================================ --- botan/x509cert.cpp c72dbb61b0aba0c216ae0affca5de53fb130d086 +++ botan/x509cert.cpp 68dc18245e93b289fee40af838929d72efe83840 @@ -9,6 +9,7 @@ #include #include #include +#include namespace Botan {