Botan  1.11.15
src/lib/math/ec_gfp/curve_gfp.cpp
Go to the documentation of this file.
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 }