Crypto++  5.6.5 Free C++ class library of cryptographic schemes
ecp.h
Go to the documentation of this file.
1 // ecp.h - written and placed in the public domain by Wei Dai
2
3 //! \file ecp.h
4 //! \brief Classes for Elliptic Curves over prime fields
5
6 #ifndef CRYPTOPP_ECP_H
7 #define CRYPTOPP_ECP_H
8
9 #include "cryptlib.h"
10 #include "integer.h"
11 #include "algebra.h"
12 #include "modarith.h"
13 #include "eprecomp.h"
14 #include "smartptr.h"
15 #include "pubkey.h"
16
17 NAMESPACE_BEGIN(CryptoPP)
18
19 //! \class ECPPoint
20 //! \brief Elliptical Curve Point over GF(p), where p is prime
21 struct CRYPTOPP_DLL ECPPoint
22 {
23 #ifndef CRYPTOPP_MAINTAIN_BACKWARDS_COMPATIBILITY_562
24  virtual ~ECPPoint() {}
25 #endif
26
27  //! \brief Construct an ECPPoint
28  //! \details identity is set to <tt>true</tt>
29  ECPPoint() : identity(true) {}
30
31  //! \brief Construct an ECPPoint from coordinates
32  //! \details identity is set to <tt>false</tt>
33  ECPPoint(const Integer &x, const Integer &y)
34  : x(x), y(y), identity(false) {}
35
36  bool operator==(const ECPPoint &t) const
37  {return (identity && t.identity) || (!identity && !t.identity && x==t.x && y==t.y);}
38  bool operator< (const ECPPoint &t) const
39  {return identity ? !t.identity : (!t.identity && (x<t.x || (x==t.x && y<t.y)));}
40
41  Integer x, y;
42  bool identity;
43 };
44
45 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractGroup<ECPPoint>;
46
47 //! \class ECP
48 //! \brief Elliptic Curve over GF(p), where p is prime
49 class CRYPTOPP_DLL ECP : public AbstractGroup<ECPPoint>
50 {
51 public:
52  typedef ModularArithmetic Field;
53  typedef Integer FieldElement;
54  typedef ECPPoint Point;
55
56 #ifndef CRYPTOPP_MAINTAIN_BACKWARDS_COMPATIBILITY_562
57  virtual ~ECP() {}
58 #endif
59
60  //! \brief Construct an ECP
61  ECP() {}
62
63  //! \brief Copy construct an ECP
64  //! \param ecp the other ECP object
65  //! \param convertToMontgomeryRepresentation flag indicating if the curve should be converted to a MontgomeryRepresentation
66  //! \sa ModularArithmetic, MontgomeryRepresentation
67  ECP(const ECP &ecp, bool convertToMontgomeryRepresentation = false);
68
69  //! \brief Construct an ECP
70  //! \param modulus the prime modulus
71  //! \param a Field::Element
72  //! \param b Field::Element
73  ECP(const Integer &modulus, const FieldElement &a, const FieldElement &b)
74  : m_fieldPtr(new Field(modulus)), m_a(a.IsNegative() ? modulus+a : a), m_b(b) {}
75
76  //! \brief Construct an ECP from BER encoded parameters
77  //! \param bt BufferedTransformation derived object
78  //! \details This constructor will decode and extract the the fields fieldID and curve of the sequence ECParameters
80
81  //! \brief Encode the fields fieldID and curve of the sequence ECParameters
82  //! \param bt BufferedTransformation derived object
83  void DEREncode(BufferedTransformation &bt) const;
84
85  bool Equal(const Point &P, const Point &Q) const;
86  const Point& Identity() const;
87  const Point& Inverse(const Point &P) const;
88  bool InversionIsFast() const {return true;}
89  const Point& Add(const Point &P, const Point &Q) const;
90  const Point& Double(const Point &P) const;
91  Point ScalarMultiply(const Point &P, const Integer &k) const;
92  Point CascadeScalarMultiply(const Point &P, const Integer &k1, const Point &Q, const Integer &k2) const;
93  void SimultaneousMultiply(Point *results, const Point &base, const Integer *exponents, unsigned int exponentsCount) const;
94
95  Point Multiply(const Integer &k, const Point &P) const
96  {return ScalarMultiply(P, k);}
97  Point CascadeMultiply(const Integer &k1, const Point &P, const Integer &k2, const Point &Q) const
98  {return CascadeScalarMultiply(P, k1, Q, k2);}
99
100  bool ValidateParameters(RandomNumberGenerator &rng, unsigned int level=3) const;
101  bool VerifyPoint(const Point &P) const;
102
103  unsigned int EncodedPointSize(bool compressed = false) const
104  {return 1 + (compressed?1:2)*GetField().MaxElementByteLength();}
105  // returns false if point is compressed and not valid (doesn't check if uncompressed)
106  bool DecodePoint(Point &P, BufferedTransformation &bt, size_t len) const;
107  bool DecodePoint(Point &P, const byte *encodedPoint, size_t len) const;
108  void EncodePoint(byte *encodedPoint, const Point &P, bool compressed) const;
109  void EncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const;
110
111  Point BERDecodePoint(BufferedTransformation &bt) const;
112  void DEREncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const;
113
114  Integer FieldSize() const {return GetField().GetModulus();}
115  const Field & GetField() const {return *m_fieldPtr;}
116  const FieldElement & GetA() const {return m_a;}
117  const FieldElement & GetB() const {return m_b;}
118
119  bool operator==(const ECP &rhs) const
120  {return GetField() == rhs.GetField() && m_a == rhs.m_a && m_b == rhs.m_b;}
121
122 private:
123  clonable_ptr<Field> m_fieldPtr;
124  FieldElement m_a, m_b;
125  mutable Point m_R;
126 };
127
128 CRYPTOPP_DLL_TEMPLATE_CLASS DL_FixedBasePrecomputationImpl<ECP::Point>;
129 CRYPTOPP_DLL_TEMPLATE_CLASS DL_GroupPrecomputation<ECP::Point>;
130
131 //! \class EcPrecomputation
132 //! \brief Elliptic Curve precomputation
133 //! \tparam EC elliptic curve field
134 template <class EC> class EcPrecomputation;
135
136 //! \class EcPrecomputation<ECP>
137 //! \brief ECP precomputation specialization
138 //! \details Implementation of <tt>DL_GroupPrecomputation<ECP::Point></tt> with input and output
139 //! conversions for Montgomery modular multiplication.
140 //! \sa DL_GroupPrecomputation, ModularArithmetic, MontgomeryRepresentation
141 template<> class EcPrecomputation<ECP> : public DL_GroupPrecomputation<ECP::Point>
142 {
143 public:
144  typedef ECP EllipticCurve;
145
146 #ifndef CRYPTOPP_MAINTAIN_BACKWARDS_COMPATIBILITY_562
147  virtual ~EcPrecomputation() {}
148 #endif
149
150  // DL_GroupPrecomputation
151  bool NeedConversions() const {return true;}
152  Element ConvertIn(const Element &P) const
153  {return P.identity ? P : ECP::Point(m_ec->GetField().ConvertIn(P.x), m_ec->GetField().ConvertIn(P.y));};
154  Element ConvertOut(const Element &P) const
155  {return P.identity ? P : ECP::Point(m_ec->GetField().ConvertOut(P.x), m_ec->GetField().ConvertOut(P.y));}
156  const AbstractGroup<Element> & GetGroup() const {return *m_ec;}
157  Element BERDecodeElement(BufferedTransformation &bt) const {return m_ec->BERDecodePoint(bt);}
158  void DEREncodeElement(BufferedTransformation &bt, const Element &v) const {m_ec->DEREncodePoint(bt, v, false);}
159
160  // non-inherited
161  void SetCurve(const ECP &ec)
162  {
163  m_ec.reset(new ECP(ec, true));
164  m_ecOriginal = ec;
165  }
166  const ECP & GetCurve() const {return *m_ecOriginal;}
167
168 private:
169  value_ptr<ECP> m_ec, m_ecOriginal;
170 };
171
172 NAMESPACE_END
173
174 #endif
virtual void SimultaneousMultiply(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
Multiplies a base to multiple exponents in a group.
Definition: algebra.cpp:256
Elliptical Curve Point over GF(p), where p is prime.
Definition: ecp.h:21
This file contains helper classes/functions for implementing public key algorithms.
bool InversionIsFast() const
Determine if inversion is fast.
Definition: ecp.h:88
Elliptic Curve over GF(p), where p is prime.
Definition: ecp.h:49
virtual Element ScalarMultiply(const Element &a, const Integer &e) const
Performs a scalar multiplication.
Definition: algebra.cpp:90
Abstract base classes that provide a uniform interface to this library.
Classes for automatic resource management.
Ring of congruence classes modulo n.
Definition: modarith.h:34
Interface for random number generators.
Definition: cryptlib.h:1201
Classes for performing mathematics over different fields.
Interface for buffered transformations.
Definition: cryptlib.h:1367
bool operator==(const OID &lhs, const OID &rhs)
Compare two OIDs for equality.
virtual const Element & Identity() const =0
Provides the Identity element.
virtual const Element & Double(const Element &a) const
Doubles an element in the group.
Definition: algebra.cpp:15
ECPPoint(const Integer &x, const Integer &y)
Construct an ECPPoint from coordinates.
Definition: ecp.h:33
bool operator<(const OID &lhs, const OID &rhs)
Compare two OIDs for ordering.
A pointer which can be copied and cloned.
Definition: smartptr.h:108
Multiple precision integer with arithmetic operations.
Definition: integer.h:45
virtual const Element & Add(const Element &a, const Element &b) const =0
ECPPoint()
Construct an ECPPoint.
Definition: ecp.h:29
virtual bool Equal(const Element &a, const Element &b) const =0
Compare two elements for equality.
Classes for precomputation in a group.
virtual const Element & Inverse(const Element &a) const =0
Inverts the element in the group.
Elliptic Curve precomputation.
Definition: ec2n.h:122
ECP()
Construct an ECP.
Definition: ecp.h:61
Multiple precision integer with arithmetic operations.
Class file for performing modular arithmetic.
Crypto++ library namespace.
ECP(const Integer &modulus, const FieldElement &a, const FieldElement &b)
Construct an ECP.
Definition: ecp.h:73
virtual Element CascadeScalarMultiply(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const
TODO.
Definition: algebra.cpp:97