1 /* Edwards curve operations
2 * Daniel Beer <dlbeer@gmail.com>, 9 Jan 2014
4 * This file is in the public domain.
9 /* Base point is (numbers wrapped):
11 * x = 151122213495354007725011514095885315114
12 * 54012693041857206046113283949847762202
13 * y = 463168356949264781694283940034751631413
14 * 07993866256225615783033603165251855960
16 * y is derived by transforming the original Montgomery base (u=9). x
17 * is the corresponding positive coordinate for the new curve equation.
20 const struct ed25519_pt ed25519_base
= {
22 0x1a, 0xd5, 0x25, 0x8f, 0x60, 0x2d, 0x56, 0xc9,
23 0xb2, 0xa7, 0x25, 0x95, 0x60, 0xc7, 0x2c, 0x69,
24 0x5c, 0xdc, 0xd6, 0xfd, 0x31, 0xe2, 0xa4, 0xc0,
25 0xfe, 0x53, 0x6e, 0xcd, 0xd3, 0x36, 0x69, 0x21
28 0x58, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
29 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
30 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
31 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66
34 0xa3, 0xdd, 0xb7, 0xa5, 0xb3, 0x8a, 0xde, 0x6d,
35 0xf5, 0x52, 0x51, 0x77, 0x80, 0x9f, 0xf0, 0x20,
36 0x7d, 0xe3, 0xab, 0x64, 0x8e, 0x4e, 0xea, 0x66,
37 0x65, 0x76, 0x8b, 0xd7, 0x0f, 0x5f, 0x87, 0x67
42 static const struct ed25519_pt ed25519_neutral
= {
49 /* Conversion to and from projective coordinates */
50 void ed25519_project(struct ed25519_pt
*p
,
51 const uint8_t *x
, const uint8_t *y
)
56 f25519_mul__distinct(p
->t
, x
, y
);
59 void ed25519_unproject(uint8_t *x
, uint8_t *y
,
60 const struct ed25519_pt
*p
)
62 uint8_t z1
[F25519_SIZE
];
64 f25519_inv__distinct(z1
, p
->z
);
65 f25519_mul__distinct(x
, p
->x
, z1
);
66 f25519_mul__distinct(y
, p
->y
, z1
);
72 /* Compress/uncompress points. We compress points by storing the x
73 * coordinate and the parity of the y coordinate.
75 * Rearranging the curve equation, we obtain explicit formulae for the
78 * x = sqrt((y^2-1) / (1+dy^2))
79 * y = sqrt((x^2+1) / (1-dx^2))
81 * Where d = (-121665/121666), or:
83 * d = 370957059346694393431380835087545651895
84 * 42113879843219016388785533085940283555
87 static const uint8_t ed25519_d
[F25519_SIZE
] = {
88 0xa3, 0x78, 0x59, 0x13, 0xca, 0x4d, 0xeb, 0x75,
89 0xab, 0xd8, 0x41, 0x41, 0x4d, 0x0a, 0x70, 0x00,
90 0x98, 0xe8, 0x79, 0x77, 0x79, 0x40, 0xc7, 0x8c,
91 0x73, 0xfe, 0x6f, 0x2b, 0xee, 0x6c, 0x03, 0x52
94 void ed25519_pack(uint8_t *c
, const uint8_t *x
, const uint8_t *y
)
96 uint8_t tmp
[F25519_SIZE
];
100 f25519_normalize(tmp
);
101 parity
= (tmp
[0] & 1) << 7;
108 uint8_t ed25519_try_unpack(uint8_t *x
, uint8_t *y
, const uint8_t *comp
)
110 const int parity
= comp
[31] >> 7;
111 uint8_t a
[F25519_SIZE
];
112 uint8_t b
[F25519_SIZE
];
113 uint8_t c
[F25519_SIZE
];
116 f25519_copy(y
, comp
);
119 /* Compute c = y^2 */
120 f25519_mul__distinct(c
, y
, y
);
122 /* Compute b = (1+dy^2)^-1 */
123 f25519_mul__distinct(b
, c
, ed25519_d
);
124 f25519_add(a
, b
, f25519_one
);
125 f25519_inv__distinct(b
, a
);
127 /* Compute a = y^2-1 */
128 f25519_sub(a
, c
, f25519_one
);
130 /* Compute c = a*b = (y^2-1)/(1-dy^2) */
131 f25519_mul__distinct(c
, a
, b
);
133 /* Compute a, b = +/-sqrt(c), if c is square */
137 /* Select one of them, based on the compressed parity bit */
138 f25519_select(x
, a
, b
, (a
[0] ^ parity
) & 1);
140 /* Verify that x^2 = c */
141 f25519_mul__distinct(a
, x
, x
);
145 return f25519_eq(a
, c
);
149 static const uint8_t ed25519_k
[F25519_SIZE
] = {
150 0x59, 0xf1, 0xb2, 0x26, 0x94, 0x9b, 0xd6, 0xeb,
151 0x56, 0xb1, 0x83, 0x82, 0x9a, 0x14, 0xe0, 0x00,
152 0x30, 0xd1, 0xf3, 0xee, 0xf2, 0x80, 0x8e, 0x19,
153 0xe7, 0xfc, 0xdf, 0x56, 0xdc, 0xd9, 0x06, 0x24
156 void ed25519_add(struct ed25519_pt
*r
,
157 const struct ed25519_pt
*p1
, const struct ed25519_pt
*p2
)
159 /* Explicit formulas database: add-2008-hwcd-3
161 * source 2008 Hisil--Wong--Carter--Dawson,
162 * http://eprint.iacr.org/2008/522, Section 3.1
163 * appliesto extended-1
166 * compute A = (Y1-X1)(Y2-X2)
167 * compute B = (Y1+X1)(Y2+X2)
168 * compute C = T1 k T2
169 * compute D = Z1 2 Z2
179 uint8_t a
[F25519_SIZE
];
180 uint8_t b
[F25519_SIZE
];
181 uint8_t c
[F25519_SIZE
];
182 uint8_t d
[F25519_SIZE
];
183 uint8_t e
[F25519_SIZE
];
184 uint8_t f
[F25519_SIZE
];
185 uint8_t g
[F25519_SIZE
];
186 uint8_t h
[F25519_SIZE
];
188 /* A = (Y1-X1)(Y2-X2) */
189 f25519_sub(c
, p1
->y
, p1
->x
);
190 f25519_sub(d
, p2
->y
, p2
->x
);
191 f25519_mul__distinct(a
, c
, d
);
193 /* B = (Y1+X1)(Y2+X2) */
194 f25519_add(c
, p1
->y
, p1
->x
);
195 f25519_add(d
, p2
->y
, p2
->x
);
196 f25519_mul__distinct(b
, c
, d
);
199 f25519_mul__distinct(d
, p1
->t
, p2
->t
);
200 f25519_mul__distinct(c
, d
, ed25519_k
);
203 f25519_mul__distinct(d
, p1
->z
, p2
->z
);
219 f25519_mul__distinct(r
->x
, e
, f
);
222 f25519_mul__distinct(r
->y
, g
, h
);
225 f25519_mul__distinct(r
->t
, e
, h
);
228 f25519_mul__distinct(r
->z
, f
, g
);
231 static void ed25519_double(struct ed25519_pt
*r
, const struct ed25519_pt
*p
)
233 /* Explicit formulas database: dbl-2008-hwcd
235 * source 2008 Hisil--Wong--Carter--Dawson,
236 * http://eprint.iacr.org/2008/522, Section 3.3
241 * compute E = (X1+Y1)^2-A-B
250 uint8_t a
[F25519_SIZE
];
251 uint8_t b
[F25519_SIZE
];
252 uint8_t c
[F25519_SIZE
];
253 uint8_t e
[F25519_SIZE
];
254 uint8_t f
[F25519_SIZE
];
255 uint8_t g
[F25519_SIZE
];
256 uint8_t h
[F25519_SIZE
];
259 f25519_mul__distinct(a
, p
->x
, p
->x
);
262 f25519_mul__distinct(b
, p
->y
, p
->y
);
265 f25519_mul__distinct(c
, p
->z
, p
->z
);
268 /* D = a A (alter sign) */
269 /* E = (X1+Y1)^2-A-B */
270 f25519_add(f
, p
->x
, p
->y
);
271 f25519_mul__distinct(e
, f
, f
);
286 f25519_mul__distinct(r
->x
, e
, f
);
289 f25519_mul__distinct(r
->y
, g
, h
);
292 f25519_mul__distinct(r
->t
, e
, h
);
295 f25519_mul__distinct(r
->z
, f
, g
);
298 void ed25519_smult(struct ed25519_pt
*r_out
, const struct ed25519_pt
*p
,
304 ed25519_copy(&r
, &ed25519_neutral
);
306 for (i
= 255; i
>= 0; i
--) {
307 const uint8_t bit
= (e
[i
>> 3] >> (i
& 7)) & 1;
310 ed25519_double(&r
, &r
);
311 ed25519_add(&s
, &r
, p
);
313 f25519_select(r
.x
, r
.x
, s
.x
, bit
);
314 f25519_select(r
.y
, r
.y
, s
.y
, bit
);
315 f25519_select(r
.z
, r
.z
, s
.z
, bit
);
316 f25519_select(r
.t
, r
.t
, s
.t
, bit
);
319 ed25519_copy(r_out
, &r
);