Botan
1.11.15
|
00001 /* 00002 * Elliptic curves over GF(p) Montgomery Representation 00003 * (C) 2014 Jack Lloyd 00004 * 00005 * Botan is released under the Simplified BSD License (see license.txt) 00006 */ 00007 00008 #include <botan/curve_gfp.h> 00009 #include <botan/internal/curve_nistp.h> 00010 #include <botan/internal/mp_core.h> 00011 #include <botan/internal/mp_asmi.h> 00012 00013 namespace Botan { 00014 00015 namespace { 00016 00017 class CurveGFp_Montgomery : public CurveGFp_Repr 00018 { 00019 public: 00020 CurveGFp_Montgomery(const BigInt& p, const BigInt& a, const BigInt& b) : 00021 m_p(p), m_a(a), m_b(b), 00022 m_p_words(m_p.sig_words()), 00023 m_p_dash(monty_inverse(m_p.word_at(0))) 00024 { 00025 const BigInt r = BigInt::power_of_2(m_p_words * BOTAN_MP_WORD_BITS); 00026 00027 m_r2 = (r * r) % p; 00028 m_a_r = (m_a * r) % p; 00029 m_b_r = (m_b * r) % p; 00030 } 00031 00032 const BigInt& get_a() const override { return m_a; } 00033 00034 const BigInt& get_b() const override { return m_b; } 00035 00036 const BigInt& get_p() const override { return m_p; } 00037 00038 const BigInt& get_a_rep() const override { return m_a_r; } 00039 00040 const BigInt& get_b_rep() const override { return m_b_r; } 00041 00042 size_t get_p_words() const override { return m_p_words; } 00043 00044 void to_curve_rep(BigInt& x, secure_vector<word>& ws) const override; 00045 00046 void from_curve_rep(BigInt& x, secure_vector<word>& ws) const override; 00047 00048 void curve_mul(BigInt& z, const BigInt& x, const BigInt& y, 00049 secure_vector<word>& ws) const override; 00050 00051 void curve_sqr(BigInt& z, const BigInt& x, 00052 secure_vector<word>& ws) const override; 00053 private: 00054 BigInt m_p, m_a, m_b; 00055 size_t m_p_words; // cache of m_p.sig_words() 00056 00057 // Montgomery parameters 00058 BigInt m_r2, m_a_r, m_b_r; 00059 word m_p_dash; 00060 }; 00061 00062 void CurveGFp_Montgomery::to_curve_rep(BigInt& x, secure_vector<word>& ws) const 00063 { 00064 const BigInt tx = x; 00065 curve_mul(x, tx, m_r2, ws); 00066 } 00067 00068 void CurveGFp_Montgomery::from_curve_rep(BigInt& x, secure_vector<word>& ws) const 00069 { 00070 const BigInt tx = x; 00071 curve_mul(x, tx, 1, ws); 00072 } 00073 00074 void CurveGFp_Montgomery::curve_mul(BigInt& z, const BigInt& x, const BigInt& y, 00075 secure_vector<word>& ws) const 00076 { 00077 if(x.is_zero() || y.is_zero()) 00078 { 00079 z = 0; 00080 return; 00081 } 00082 00083 const size_t output_size = 2*m_p_words + 1; 00084 ws.resize(2*(m_p_words+2)); 00085 00086 z.grow_to(output_size); 00087 z.clear(); 00088 00089 bigint_monty_mul(z.mutable_data(), output_size, 00090 x.data(), x.size(), x.sig_words(), 00091 y.data(), y.size(), y.sig_words(), 00092 m_p.data(), m_p_words, m_p_dash, 00093 &ws[0]); 00094 } 00095 00096 void CurveGFp_Montgomery::curve_sqr(BigInt& z, const BigInt& x, 00097 secure_vector<word>& ws) const 00098 { 00099 if(x.is_zero()) 00100 { 00101 z = 0; 00102 return; 00103 } 00104 00105 const size_t output_size = 2*m_p_words + 1; 00106 00107 ws.resize(2*(m_p_words+2)); 00108 00109 z.grow_to(output_size); 00110 z.clear(); 00111 00112 bigint_monty_sqr(z.mutable_data(), output_size, 00113 x.data(), x.size(), x.sig_words(), 00114 m_p.data(), m_p_words, m_p_dash, 00115 &ws[0]); 00116 } 00117 00118 } 00119 00120 // Default implementation 00121 void CurveGFp_Repr::normalize(BigInt& x, secure_vector<word>& ws, size_t bound) const 00122 { 00123 const BigInt& p = get_p(); 00124 const word* prime = p.data(); 00125 const size_t p_words = get_p_words(); 00126 00127 while(x.is_negative()) 00128 x += p; 00129 00130 x.grow_to(p_words + 1); 00131 00132 if(ws.size() < p_words + 1) 00133 ws.resize(p_words + 1); 00134 00135 for(size_t i = 0; bound == 0 || i < bound; ++i) 00136 { 00137 const word* xd = x.data(); 00138 word borrow = 0; 00139 00140 for(size_t i = 0; i != p_words; ++i) 00141 ws[i] = word_sub(xd[i], prime[i], &borrow); 00142 ws[p_words] = word_sub(xd[p_words], 0, &borrow); 00143 00144 if(borrow) 00145 break; 00146 00147 x.swap_reg(ws); 00148 } 00149 } 00150 00151 std::shared_ptr<CurveGFp_Repr> 00152 CurveGFp::choose_repr(const BigInt& p, const BigInt& a, const BigInt& b) 00153 { 00154 #if defined(BOTAN_HAS_CURVEGFP_NISTP_M32) 00155 if(p == CurveGFp_P192::prime()) 00156 return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P192(a, b)); 00157 if(p == CurveGFp_P224::prime()) 00158 return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P224(a, b)); 00159 if(p == CurveGFp_P256::prime()) 00160 return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P256(a, b)); 00161 if(p == CurveGFp_P384::prime()) 00162 return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P384(a, b)); 00163 #endif 00164 00165 if(p == CurveGFp_P521::prime()) 00166 return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P521(a, b)); 00167 00168 return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_Montgomery(p, a, b)); 00169 } 00170 00171 }