/
Ecc.hh
160 lines (130 loc) · 4.18 KB
/
Ecc.hh
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
//
// Created by algys on 4/26/18.
//
#ifndef DLEQ_ECC_HH
#define DLEQ_ECC_HH
#include <utility>
#include "BigNum.h"
typedef BigNum::Num<256> UInt256;
typedef BigNum::Num<272> UInt272;
typedef BigNum::Num<576> UInt576;
class Curve {
public:
UInt256 p;
UInt256 a;
UInt256 b;
UInt256 n;
struct {
UInt256 x;
UInt256 y;
} G;
};
const UInt256 fromString(std::string const & str)
{
UInt256 ret;
auto i = 0;
while (i < str.size() && isdigit(str[i]))
{
auto t = ret * 10u;
ret = t;
ret = ret + (unsigned)(str[i] - '0');
i++;
}
return ret;
}
// Secp256k1 curve
const Curve Secp256k1 = {
fromString("115792089237316195423570985008687907853269984665640564039457584007908834671663"), //115792089237316195423570985008687907853269984665640564039457584007908834671663
UInt256(0),
UInt256(7),
fromString("115792089237316195423570985008687907852837564279074904382605163141518161494337"), //115792089237316195423570985008687907852837564279074904382605163141518161494337
{
fromString("55066263022277343669578718895168534326250603453777594175500187360389116729240"), //55066263022277343669578718895168534326250603453777594175500187360389116729240
fromString("32670510020758816978083085130507043184471273380659243275938904335757337482424") //32670510020758816978083085130507043184471273380659243275938904335757337482424
}
};
class Point {
public:
Point() :
_curve{Secp256k1}
{ }
Point(UInt256 const & x, UInt256 const & y) :
_x{x}, _y{y}, _curve{Secp256k1}
{ }
Point(Curve curve, UInt256 const & x, UInt256 const & y) :
_x{x}, _y{y}, _curve{std::move(curve)}
{ }
//R = P + Q
Point add(Point const & point) const{
if (identity())
return point;
if (point.identity())
return *this;
if (x() == point.x()) {
if (y() == point.y())
return dbl();
else
return identityPoint();
}
auto t1 = (UInt272)y() + curve().p - point.y();
auto t2 = (UInt272)x() + curve().p - point.x();
auto m = div(t1, t2);
return lineIntersect(point, m);
}
//R = P+P
Point dbl() const{
if (identity())
return *this;
auto t = div(x() * x() * 3 + curve().a , y() * 2);
return lineIntersect(*this, t);
}
Point scalarMult(UInt256 scalar) const {
Point q = *this;
Point r = identityPoint();
while(scalar > 0) {
if ((scalar[0] & 1) != 0)
r = r.add(q);
scalar = scalar >> 1;
if (scalar != 0)
q = q.dbl();
}
return r;
}
bool isOnCurve() const {
auto y2 = modExp(y(), UInt256(2), curve().p);
auto x3ab = mul((UInt272)modExp(x(), UInt256(2), curve().p) + curve().a, x()) + curve().b;
return y2 == x3ab;
}
friend bool operator== (Point const & lhs, Point const & rhs) {
return lhs._x == rhs._x && lhs._y == rhs._y;
}
friend bool operator!= (Point const & lhs, Point const & rhs) {
return !(lhs == rhs);
}
const Curve & curve() const { return _curve; }
const UInt256 & x() const { return _x; }
const UInt256 & y() const { return _y; }
bool identity() const { return curve().p == x(); }
Point identityPoint() const{
return {curve().p, 0};
}
private:
UInt256 mul(UInt256 const & a, UInt256 const & b) const{
return ((a * b) % curve().p);
}
UInt256 div(UInt576 const & num, UInt576 const & den) const{
auto invDen = modInv((BigNum::Num<257>)(den % curve().p), (BigNum::Num<257>)curve().p);
return mul(num % curve().p, invDen);
}
Point lineIntersect(Point const & point, UInt256 const & m) const{
auto v = ((UInt272)y() + curve().p - (m * x()) % curve().p) % curve().p;
auto x = (m * m + curve().p + curve().p - this->x() - point.x()) % curve().p;
auto y = ((UInt272)curve().p + curve().p - (m * x) % curve().p - v) % curve().p;
return {curve(), x, y};
}
private:
Curve _curve{};
UInt256 _x{};
UInt256 _y{};
};
#endif //DLEQ_ECC_HH