1
/*
2
*******************************************************************************
3
\file ec2.c
4
\brief Elliptic curves over binary fields
5
\project bee2 [cryptographic library]
6
\author (C) Sergey Agievich [agievich@{bsu.by|gmail.com}]
7
\created 2012.06.26
8
\version 2014.07.15
9
\license This program is released under the GNU General Public License 
10
version 3. See Copyright Notices in bee2/info.h.
11
*******************************************************************************
12
*/
13

14
#include "bee2/core/mem.h"
15
#include "bee2/core/stack.h"
16
#include "bee2/core/util.h"
17
#include "bee2/math/ec2.h"
18
#include "bee2/math/gf2.h"
19
#include "bee2/math/pri.h"
20
#include "bee2/math/ww.h"
21
#include "bee2/math/zz.h"
22

23
/*
24
*******************************************************************************
25
Общие положения
26

27
Ссылки на все реализованные алгоритмы имеются на сайте
28
http://www.hyperelliptic.org/efd. Там же можно найти соглашения по
29
обозначению сложности алгоритмов. В этих обозначениях фигурируют
30
следующие формальные выражения:
31
	add -- сложение или вычитание в GF(2^m),
32
	c -- умножение на малую константу c в GF(2^m),
33
	*A -- умножение на коэффициент A в GF(2^m),
34
	*B -- умножение на коэффициент B в GF(2^m),
35
	S -- возведение в квадрат в GF(2^m),
36
	M -- умножение в GF(2^m),
37
	D -- деление в GF(2^m).
38

39
При общей оценке сложности считается, что 1D = 24M, 1*B = 1M и 1S = 0M.
40
Аддитивные операции игнорируются. В общем случае 1*A = 1M, но в наиболее
41
распространенных на практике случаях A \in {0, 1} и 1*A = 0M.
42

43
\warning Соотношение 1D = 24M получено экспериментальным путем
44
на платформе x86 и возможно требует пересмотра.
45
На упомянутом сайте http://www.hyperelliptic.org/efd используется другое
46
соотношение: 1D = 10M. Считаем его слишком оптимистичным
47
(по отношению к D).
48

49
Используются обозначения:
50
	A <- A + A -- сложение аффинных точек,
51
	A <- 2A -- удвоение аффинной точки;
52
	P <- P + P -- сложение проективных точек;
53
	P <- P + A -- добавление к проективной точке аффинной;
54
	P <- 2P -- удвоение проективной точки;
55
	P <- 2A -- удвоение аффинной точки с переходом к проективным координатам.
56
*******************************************************************************
57
*/
58

59
#define ec2SeemsOnA(a, ec)\
60
	(gf2IsIn(ecX(a), (ec)->f) && gf2IsIn(ecY(a, (ec)->f->n), (ec)->f))
61

62
#define ec2SeemsOn3(a, ec)\
63
	(ec2SeemsOnA(a, ec) && gf2IsIn(ecZ(a, (ec)->f->n), (ec)->f))
64

65
/*
66
*******************************************************************************
67
Кривая в проективных координатах Лопеса -- Дахаба (LD):
68
	x = X / Z, y = Y / Z^2,
69
	O = (1 : 0 : 0),
70
	-(X : Y : Z) = (X : ZX + Y : Z).
71

72
\warning Ошибка в книге [Hankerson D., Menezes A., Vanstone S. Guide to
73
Elliptic Curve Cryptography, Springer, 2004] при определении обратной
74
точки в LD-координатах.
75

76
В функции ec2DblLD() выполняется удвоение P <- 2P. Реализован алгоритм
77
dbl-2005-l [Lange, 2005]. Сложность алгоритма:
78
	4M + 4S + 1*A + 5add \approx 5M,
79
причем умножение на A не выполняется, если A \in {0, 1}.
80

81
\todo Ссравнить с алгоритмом dbl-2005-dl.
82

83
В функции ec2DblALD() выполняется удвоение P <- 2A (Z-координата
84
проективной точки равняется 1). Реализован алгоритм
85
mdbl-2005-dl [Doche-Lange, 2005]. Сложность алгоритма:
86
	1M + 3S + 1*A + 1*B + 4add \approx 3M.
87
причем умножение на A не выполняется, если A \in {0, 1}.
88

89
В функции ec2AddLD() выполняется сложение P <- P + P.
90
Реализован алгоритм add-2005-dl [Doche-Lange-Takagi, 2005].
91
Сложность алгоритма:
92
	13M + 4S + 9add \approx 13M.
93

94
В функции ec2AddALD() выполняется сложение P <- P + A (Z-координата
95
второго слагаемого равняется 1).
96
Реализован алгоритм madd-2005-dl [Doche, Lange, Al-Daoude, 2005].
97
Сложность алгоритма:
98
		8M + 5S + 1*A + 9add \approx 9M,
99
причем умножение на A не выполняется, если A \in {0, 1}.
100

101
Целевые функции ci(l), определенные в описании реализации ecMul() в ec.c,
102
принимают следующий вид (считаем, что коэффициент A \in {0, 1}):
103
	c1(l) = l/3 8;
104
	c2(l, w) = 26 + (2^{w-2} - 2)26 + l/(w + 1) 8;
105
	c3(l, w) = 2 + (2^{w-2} - 2)13 + l/(w + 1) 13.
106

107
Расчеты показывают, что
108
	с1(l) <= min_w c2(l), l <= 39,
109
	min_w c2(l, w) <= min_w c3(l, w).
110
Поэтому для практически используемых размерностей l (39 <= l)
111
первая и третья стратегии являются проигрышными. Реализована только стратегия 2.
112

113
\todo Реализовать быстрые формулы для особенных B:
114
B = 1 (кривые Коблица),	известен \sqrt{B}.
115

116
\todo Реализовать редакции функций с A \in {0, 1}.
117

118
\todo Исследовать расширенные LD-координаты (дополнительно поддерживается Z^2).
119
*******************************************************************************
120
*/
121

122
// [3n]b <- [2n]a (P <- A)
123 1
static bool_t ec2FromALD(word b[], const word a[], const ec_o* ec,
124
	void* stack)
125
{
126 1
	const size_t n = ec->f->n;
127
	// pre
128 1
	ASSERT(ecIsOperable(ec) && ec->d == 3);
129 1
	ASSERT(ec2SeemsOnA(a, ec));
130 1
	ASSERT(a == b || wwIsDisjoint2(a, 2 * n, b, 3 * n));
131
	// xb <- xa
132 1
	qrCopy(ecX(b), ecX(a), ec->f);
133
	// yb <- ya
134 1
	qrCopy(ecY(b, n), ecY(a, n), ec->f);
135
	// zb <- 1
136 1
	qrSetUnity(ecZ(b, n), ec->f);
137 1
	return TRUE;
138
}
139

140
// [2n]b <- [3n]a (A <- P)
141 1
static bool_t ec2ToALD(word b[], const word a[], const ec_o* ec, void* stack)
142
{
143 1
	const size_t n = ec->f->n;
144
	// переменные в stack
145 1
	word* t1 = (word*)stack;
146 1
	stack = t1 + n;
147
	// pre
148 1
	ASSERT(ecIsOperable(ec) && ec->d == 3);
149 1
	ASSERT(ec2SeemsOn3(a, ec));
150 1
	ASSERT(a == b || wwIsDisjoint2(a, 3 * n, b, 2 * n));
151
	// a == O => b <- O
152 1
	if (qrIsZero(ecZ(a, n), ec->f))
153 1
		return FALSE;
154
	// t1 <- za^{-1}
155 1
	qrInv(t1, ecZ(a, n), ec->f, stack);
156
	// xb <- xa t1
157 1
	qrMul(ecX(b), ecX(a), t1, ec->f, stack);
158
	// t1 <- t1^2
159 1
	qrSqr(t1, t1, ec->f, stack);
160
	// yb <- ya t1
161 1
	qrMul(ecY(b, n), ecY(a, n), t1, ec->f, stack);
162
	// b != O
163 1
	return TRUE;
164
}
165

166 1
static size_t ec2ToALD_deep(size_t n, size_t f_deep)
167
{
168 1
	return O_OF_W(n) + f_deep;
169
}
170

171
// [3n]b <- -[3n]a (P <- -P)
172 0
static void ec2NegLD(word b[], const word a[], const ec_o* ec, void* stack)
173
{
174 0
	const size_t n = ec->f->n;
175
	// переменные в stack
176 0
	word* t1 = (word*)stack;
177 0
	stack = t1 + n;
178
	// pre
179 0
	ASSERT(ecIsOperable(ec) && ec->d == 3);
180 0
	ASSERT(ec2SeemsOn3(a, ec));
181 0
	ASSERT(wwIsSameOrDisjoint(a, b, 3 * n));
182
	// t1 <- xa * za
183 0
	qrMul(t1, ecX(a), ecZ(a, n), ec->f, stack);
184
	// b <- (xa, ya + t1, za)
185 0
	wwCopy(b, a, 3 * n);
186 0
	gf2Add2(ecY(b, n), t1, ec->f);
187
}
188

189 1
static size_t ec2NegLD_deep(size_t n, size_t f_deep)
190
{
191 1
	return O_OF_W(n) + f_deep;
192
}
193

194
// [3n]b <- 2[3n]a (P <- 2P)
195 1
static void ec2DblLD(word b[], const word a[], const ec_o* ec, void* stack)
196
{
197 1
	const size_t n = ec->f->n;
198
	// переменные в stack
199 1
	word* t1 = (word*)stack;
200 1
	word* t2 = t1 + n;
201 1
	stack = t2 + n;
202
	// pre
203 1
	ASSERT(ecIsOperable(ec) && ec->d == 3);
204 1
	ASSERT(ec2SeemsOn3(a, ec));
205 1
	ASSERT(wwIsSameOrDisjoint(a, b, 3 * n));
206
	// za == 0 или xa == 0? => b <- O
207 1
	if (qrIsZero(ecZ(a, n), ec->f) || qrIsZero(ecX(a), ec->f))
208
	{
209 1
		qrSetZero(ecZ(b, n), ec->f);
210 1
		return;
211
	}
212
	// t1 <- xa za [A]
213 1
	qrMul(t1, ecX(a), ecZ(a, n), ec->f, stack);
214
	// zb <- t1^2 [A^2]
215 1
	qrSqr(ecZ(b, n), t1, ec->f, stack);
216
	// t2 <- xa^2 [B]
217 1
	qrSqr(t2, ecX(a), ec->f, stack);
218
	// xb <- ya + t2 [C]
219 1
	gf2Add(ecX(b), ecY(a, n), t2, ec->f);
220
	// t1 <- t1 xb [D]
221 1
	qrMul(t1, t1, ecX(b), ec->f, stack);
222
	// xb <- xb^2 + t1 [C^2 + D]
223 1
	qrSqr(ecX(b), ecX(b), ec->f, stack);
224 1
	gf2Add2(ecX(b), t1, ec->f);
225
	// t1 <- t1 + zb [Z3 + D]
226 1
	gf2Add2(t1, ecZ(b, n), ec->f);
227
	// yb <- t2^2 zb [B^2 Z3]
228 1
	qrSqr(ecY(b, n), t2, ec->f, stack);
229 1
	qrMul(ecY(b, n), ecY(b, n), ecZ(b, n), ec->f, stack);
230
	// xb <- xb + A * zb [C^2 + D + a2 * Z3]
231 1
	if (qrIsUnity(ec->A, ec->f))
232 1
		gf2Add2(ecX(b), ecZ(b, n), ec->f);
233 1
	else if (!qrIsZero(ec->A, ec->f))
234
	{
235 0
		qrMul(t2, ec->A, ecZ(b, n), ec->f, stack);
236 0
		gf2Add2(ecX(b), t2, ec->f);
237
	}
238
	// t1 <- t1 xb [(Z3 + D)X3]
239 1
	qrMul(t1, t1, ecX(b), ec->f, stack);
240
	// yb <- yb + t1 [(Z3 + D)X3 + B^2 Z3]
241 1
	gf2Add2(ecY(b, n), t1, ec->f);
242
}
243

244 1
static size_t ec2DblLD_deep(size_t n, size_t f_deep)
245
{
246 1
	return O_OF_W(2 * n) + f_deep;
247
}
248

249
// [3n]b <- 2[2n]a (P <- 2A)
250 1
static void ec2DblALD(word b[], const word a[], const ec_o* ec, void* stack)
251
{
252 1
	const size_t n = ec->f->n;
253
	// переменные в stack
254 1
	word* t1 = (word*)stack;
255 1
	stack = t1 + n;
256
	// pre
257 1
	ASSERT(ecIsOperable(ec) && ec->d == 3);
258 1
	ASSERT(ec2SeemsOnA(a, ec));
259 1
	ASSERT(a == b || wwIsDisjoint2(a, 2 * n, b, 3 * n));
260
	// xa == 0? => b <- O
261 1
	if (qrIsZero(ecX(a), ec->f))
262
	{
263 0
		qrSetZero(ecZ(b, n), ec->f);
264 0
		return;
265
	}
266
	// zb <- xa^2 [C]
267 1
	qrSqr(ecZ(b, n), ecX(a), ec->f, stack);
268
	// xb <- zb^2 + B [C^2 + a6]
269 1
	qrSqr(ecX(b), ecZ(b, n), ec->f, stack);
270 1
	gf2Add2(ecX(b), ec->B, ec->f);
271
	// yb <- ya^2 + B [Y1^2 + a6]
272 1
	qrSqr(ecY(b, n), ecY(a, n), ec->f, stack);
273 1
	gf2Add2(ecY(b, n), ec->B, ec->f);
274
	// yb <- yb + A zb [Y1^2 + a2*Z3 + a6]
275 1
	if (qrIsUnity(ec->A, ec->f))
276 1
		gf2Add2(ecY(b, n), ecZ(b, n), ec->f);
277 1
	else if (!qrIsZero(ec->A, ec->f))
278
	{
279 0
		qrMul(t1, ec->A, ecZ(b, n), ec->f, stack);
280 0
		gf2Add2(ecY(b, n), t1, ec->f);
281
	}
282
	// yb <- yb xb [(Y1^2 + a2*Z3 + a6) * X3]
283 1
	qrMul(ecY(b, n), ecY(b, n), ecX(b), ec->f, stack);
284
	// t1 <- B zb [a6 * Z3]
285 1
	qrMul(t1, ec->B, ecZ(b, n), ec->f, stack);
286
	// yb <- yb + t1 [(Y1^2 + a2*Z3 + a6) * X3 + a6 * Z3]
287 1
	gf2Add2(ecY(b, n), t1, ec->f);
288
}
289

290 1
static size_t ec2DblALD_deep(size_t n, size_t f_deep)
291
{
292 1
	return O_OF_W(n) + f_deep;
293
}
294

295
// [3n]c <- [3n]a + [3n]b (P <- P + P)
296 1
static void ec2AddLD(word c[], const word a[], const word b[],
297
	const ec_o* ec, void* stack)
298
{
299 1
	const size_t n = ec->f->n;
300
	// переменные в stack
301 1
	word* t1 = (word*)stack;
302 1
	word* t2 = t1 + n;
303 1
	word* t3 = t2 + n;
304 1
	word* t4 = t3 + n;
305 1
	word* t5 = t4 + n;
306 1
	word* t6 = t5 + n;
307 1
	stack = t6 + n;
308
	// pre
309 1
	ASSERT(ecIsOperable(ec) && ec->d == 3);
310 1
	ASSERT(ec2SeemsOn3(a, ec));
311 1
	ASSERT(ec2SeemsOn3(b, ec));
312 1
	ASSERT(wwIsSameOrDisjoint(a, c, 3 * n));
313 1
	ASSERT(wwIsSameOrDisjoint(b, c, 3 * n));
314
	// a == O => c <- b
315 1
	if (qrIsZero(ecZ(a, n), ec->f))
316
	{
317 1
		wwCopy(c, b, 3 * n);
318 1
		return;
319
	}
320
	// b == O => c <- a
321 1
	if (qrIsZero(ecZ(b, n), ec->f))
322
	{
323 0
		wwCopy(c, a, 3 * n);
324 0
		return;
325
	}
326
	// t1 <- xa zb [A]
327 1
	qrMul(t1, ecX(a), ecZ(b, n), ec->f, stack);
328
	// t2 <- xb za [B]
329 1
	qrMul(t2, ecX(b), ecZ(a, n), ec->f, stack);
330
	// t3 <- ya zb^2 [G]
331 1
	qrSqr(t3, ecZ(b, n), ec->f, stack);
332 1
	qrMul(t3, t3, ecY(a, n), ec->f, stack);
333
	// t4 <- yb za^2 [H]
334 1
	qrSqr(t4, ecZ(a, n), ec->f, stack);
335 1
	qrMul(t4, t4, ecY(b, n), ec->f, stack);
336
	// A == B => a == \pm b
337 1
	if (qrCmp(t1, t2, ec->f) == 0)
338
	{
339
		// t3 == t4 => a == b => c <- 2a
340 1
		if (qrCmp(t3, t4, ec->f) == 0)
341 0
			ec2DblLD(c, a, ec, stack);
342
		// t3 != t4 => a == -b => c <- O
343
		else
344 1
			qrSetZero(ecZ(c, n), ec->f);
345 1
		return;
346
	}
347
	// t5 <- t1 + t2 [E]
348 1
	gf2Add(t5, t1, t2, ec->f);
349
	// t6 <- t3 + t4 [I]
350 1
	gf2Add(t6, t3, t4, ec->f);
351
	// t5 <- t5 t6 [J]
352 1
	qrMul(t5, t5, t6, ec->f, stack);
353
	// xc <- t1^2 [C]
354 1
	qrSqr(ecX(c), t1, ec->f, stack);
355
	// yc <- t2^2 [D]
356 1
	qrSqr(ecY(c, n), t2, ec->f, stack);
357
	// t6 <- xc + yc [ec->f]
358 1
	gf2Add(t6, ecX(c), ecY(c, n), ec->f);
359
	// zc <- t6 za zb [ec->f * Z1 * Z2]
360 1
	qrMul(ecZ(c, n), ecZ(a, n), ecZ(b, n), ec->f, stack);
361 1
	qrMul(ecZ(c, n), t6, ecZ(c, n), ec->f, stack);
362
	// t4 <- t1 (t4 + yc) [A * (H + D)]
363 1
	gf2Add2(t4, ecY(c, n), ec->f);
364 1
	qrMul(t4, t1, t4, ec->f, stack);
365
	// xc <- t2 (xc + t3) + t4 [B * (C + G) + A * (H + D)]
366 1
	gf2Add2(ecX(c), t3, ec->f);
367 1
	qrMul(ecX(c), t2, ecX(c), ec->f, stack);
368 1
	gf2Add2(ecX(c), t4, ec->f);
369
	// t1 <- t1 t5 [A * J]
370 1
	qrMul(t1, t1, t5, ec->f, stack);
371
	// t3 <- t3 t6 [ec->f * G]
372 1
	qrMul(t3, t3, t6, ec->f, stack);
373
	// t1 <- (t1 + t3) t6 [(A * J + ec->f * G) * ec->f]
374 1
	gf2Add2(t1, t3, ec->f);
375 1
	qrMul(t1, t1, t6, ec->f, stack);
376
	// yc <- (t5 + zc) xc [(J + Z3) * X3]
377 1
	gf2Add(ecY(c, n), t5, ecZ(c, n), ec->f);
378 1
	qrMul(ecY(c, n), ecY(c, n), ecX(c), ec->f, stack);
379
	// yc <- yc + t1 [(A * J + ec->f * G) * ec->f + (J + Z3) * X3]
380 1
	gf2Add2(ecY(c, n), t1, ec->f);
381
}
382

383 1
static size_t ec2AddLD_deep(size_t n, size_t f_deep)
384
{
385 1
	return O_OF_W(6 * n) +
386 1
		utilMax(2,
387
			f_deep,
388
			ec2DblLD_deep(n, f_deep));
389
}
390

391
// [3n]c <- [3n]a + [2n]b (P <- P + A)
392 1
static void ec2AddALD(word c[], const word a[], const word b[],
393
	const ec_o* ec, void* stack)
394
{
395 1
	const size_t n = ec->f->n;
396
	// переменные в stack
397 1
	word* t1 = (word*)stack;
398 1
	word* t2 = t1 + n;
399 1
	word* t3 = t2 + n;
400 1
	word* t4 = t3 + n;
401 1
	stack = t4 + n;
402
	// pre
403 1
	ASSERT(ecIsOperable(ec) && ec->d == 3);
404 1
	ASSERT(ec2SeemsOn3(a, ec));
405 1
	ASSERT(ec2SeemsOnA(b, ec));
406 1
	ASSERT(wwIsSameOrDisjoint(a,  c, 3 * n));
407 1
	ASSERT(b == c || wwIsDisjoint2(b, 2 * n, c, 3 * n));
408
	// a == O => c <- (xb : yb : 1)
409 1
	if (qrIsZero(ecZ(a, n), ec->f))
410
	{
411 1
		qrCopy(ecX(c), ecX(b), ec->f);
412 1
		qrCopy(ecY(c, n), ecY(b, n), ec->f);
413 1
		qrSetUnity(ecZ(c, n), ec->f);
414 1
		return;
415
	}
416
	// t1 <- ya + yb za^2 [A]
417 1
	qrSqr(t1, ecZ(a, n), ec->f, stack);
418 1
	qrMul(t1, ecY(b, n), t1, ec->f, stack);
419 1
	gf2Add2(t1, ecY(a, n), ec->f);
420
	// t2 <- xa + xb za [B]
421 1
	qrMul(t2, ecX(b), ecZ(a, n), ec->f, stack);
422 1
	gf2Add2(t2, ecX(a), ec->f);
423
	// t2 == 0 => a == \pm b
424 1
	if (qrIsZero(t2, ec->f))
425
	{
426
		// t1 == 0 => a == b => c <- 2b
427 1
		if (qrIsZero(t1, ec->f))
428 0
			ec2DblALD(c, b, ec, stack);
429
		// t1 != 0 => a == -b => c <- O
430
		else
431 1
			qrSetZero(ecZ(c, n), ec->f);
432 1
		return;
433
	}
434
	// t3 <- t2 za [C]
435 1
	qrMul(t3, t2, ecZ(a, n), ec->f, stack);
436
	// zc <- t3^2 [C^2]
437 1
	qrSqr(ecZ(c, n), t3, ec->f, stack);
438
	// t4 <- xb zc [D]
439 1
	qrMul(t4, ecX(b), ecZ(c, n), ec->f, stack);
440
	// yc <- xb + yb [X2 + Y2]
441 1
	gf2Add(ecY(c, n), ecX(b), ecY(b, n), ec->f);
442
	// xc <- t2^2 + t1 + A t3 [B^2 + A + a2 * C]
443 1
	qrSqr(ecX(c), t2, ec->f, stack);
444 1
	gf2Add2(ecX(c), t1, ec->f);
445 1
	if (qrIsUnity(ec->A, ec->f))
446 1
		gf2Add2(ecX(c), t3, ec->f);
447 1
	else if (!qrIsZero(ec->A, ec->f))
448
	{
449 0
		qrMul(t2, ec->A, t3, ec->f, stack);
450 0
		gf2Add2(ecX(c), t2, ec->f);
451
	}
452
	// xc <- xc t3 + t1^2 [C * (A + B^2 + a2 * C) + A^2]
453 1
	qrMul(ecX(c), ecX(c), t3, ec->f, stack);
454 1
	qrSqr(t2, t1, ec->f, stack);
455 1
	gf2Add2(ecX(c), t2, ec->f);
456
	// yc <- yc zc^2 [(Y2 + X2) * Z3^2]
457 1
	qrSqr(t2, ecZ(c, n), ec->f, stack);
458 1
	qrMul(ecY(c, n), ecY(c, n), t2, ec->f, stack);
459
	// t4 <- t4 + xc [D + X3]
460 1
	gf2Add2(t4, ecX(c), ec->f);
461
	// t1 <- t1 t3 + zc [A * C + Z3]
462 1
	qrMul(t1, t1, t3, ec->f, stack);
463 1
	gf2Add2(t1, ecZ(c, n), ec->f);
464
	// t1 <- t1 t4 [(D + X3)(A * C + Z3)]
465 1
	qrMul(t1, t1, t4, ec->f, stack);
466
	// yc <- yc + t1 [(D + X3)(A * C + Z3) + (Y2 + X2) * Z3^2]
467 1
	gf2Add2(ecY(c, n), t1, ec->f);
468
}
469

470 1
static size_t ec2AddALD_deep(size_t n, size_t f_deep)
471
{
472 1
	return O_OF_W(4 * n) +
473 1
		utilMax(2,
474
			f_deep,
475
			ec2DblALD_deep(n, f_deep));
476
}
477

478
// [3n]c <- [3n]a - [3n]b (P <- P - P)
479 1
static void ec2SubLD(word c[], const word a[], const word b[],
480
	const ec_o* ec, void* stack)
481
{
482 1
	const size_t n = ec->f->n;
483
	// переменные в stack
484 1
	word* t = (word*)stack;
485 1
	stack = t + 3 * n;
486
	// pre
487 1
	ASSERT(ecIsOperable(ec) && ec->d == 3);
488 1
	ASSERT(ec2SeemsOn3(a, ec));
489 1
	ASSERT(ec2SeemsOn3(b, ec));
490 1
	ASSERT(wwIsSameOrDisjoint(a, c, 3 * n));
491 1
	ASSERT(wwIsSameOrDisjoint(b, c, 3 * n));
492
	// t <- -b
493 1
	qrMul(ecY(t, n), ecX(b), ecZ(b, n), ec->f, stack);
494 1
	gf2Add2(ecY(t, n), ecY(b, n), ec->f);
495 1
	qrCopy(ecX(t), ecX(b), ec->f);
496 1
	qrCopy(ecZ(t, n), ecZ(b, n), ec->f);
497
	// c <- a + t
498 1
	ec2AddLD(c, a, t, ec, stack);
499
}
500

501 1
static size_t ec2SubLD_deep(size_t n, size_t f_deep)
502
{
503 1
	return O_OF_W(3 * n) +
504 1
		utilMax(2,
505
			f_deep,
506
			ec2AddLD_deep(n, f_deep));
507
}
508

509
// [3n]c <- [3n]a - [2n]b (P <- P - A)
510 1
static void ec2SubALD(word c[], const word a[], const word b[],
511
	const ec_o* ec, void* stack)
512
{
513 1
	const size_t n = ec->f->n;
514
	// переменные в stack
515 1
	word* t = (word*)stack;
516 1
	stack = t + 2 * n;
517
	// pre
518 1
	ASSERT(ecIsOperable(ec) && ec->d == 3);
519 1
	ASSERT(ec2SeemsOn3(a, ec));
520 1
	ASSERT(ec2SeemsOnA(b, ec));
521 1
	ASSERT(wwIsSameOrDisjoint(a,  c, 3 * n));
522 1
	ASSERT(b == c || wwIsDisjoint2(b, 2 * n, c, 3 * n));
523
	// t <- -b
524 1
	wwCopy(t, b, 2 * n);
525 1
	gf2Add2(ecY(t, n), ecX(t), ec->f);
526
	// c <- a + t
527 1
	ec2AddALD(c, a, t, ec, stack);
528
}
529

530 1
static size_t ec2SubALD_deep(size_t n, size_t f_deep)
531
{
532 1
	return O_OF_W(2 * n) + ec2AddALD_deep(n, f_deep);
533
}
534

535 1
bool_t ec2CreateLD(ec_o* ec, const qr_o* f, const octet A[], const octet B[],
536
	void* stack)
537
{
538 1
	ASSERT(memIsValid(ec, sizeof(ec_o)));
539 1
	ASSERT(gf2IsOperable(f));
540 1
	ASSERT(memIsValid(A, f->no));
541 1
	ASSERT(memIsValid(B, f->no));
542
	// обнулить
543 1
	memSetZero(ec, sizeof(ec_o));
544
	// зафикисровать размерности
545 1
	ec->d = 3;
546
	// запомнить базовое поле
547 1
	ec->f = f;
548
	// сохранить коэффициенты
549 1
	ec->A = (word*)ec->descr;
550 1
	ec->B = ec->A + f->n;
551 1
	if (!qrFrom(ec->A, A, ec->f, stack) || !qrFrom(ec->B, B, ec->f, stack))
552 0
		return FALSE;
553
	// подготовить буферы для описания группы точек
554 1
	ec->base = ec->B + f->n;
555 1
	ec->order = ec->base + 2 * f->n;
556
	// настроить интерфейсы
557 1
	ec->froma = ec2FromALD;
558 1
	ec->toa = ec2ToALD;
559 1
	ec->neg = ec2NegLD;
560 1
	ec->add = ec2AddLD;
561 1
	ec->adda = ec2AddALD;
562 1
	ec->sub = ec2SubLD;
563 1
	ec->suba = ec2SubALD;
564 1
	ec->dbl = ec2DblLD;
565 1
	ec->dbla = ec2DblALD;
566 1
	ec->deep = utilMax(8,
567
		ec2ToALD_deep(f->n, f->deep),
568
		ec2NegLD_deep(f->n, f->deep),
569
		ec2AddLD_deep(f->n, f->deep),
570
		ec2AddALD_deep(f->n, f->deep),
571
		ec2SubLD_deep(f->n, f->deep),
572
		ec2SubALD_deep(f->n, f->deep),
573
		ec2DblLD_deep(f->n, f->deep),
574
		ec2DblALD_deep(f->n, f->deep));
575
	// настроить заголовок
576 1
	ec->hdr.keep = sizeof(ec_o) + O_OF_W(5 * f->n + 1);
577 1
	ec->hdr.p_count = 6;
578 1
	ec->hdr.o_count = 1;
579
	// все нормально
580 1
	return TRUE;
581
}
582

583 1
size_t ec2CreateLD_keep(size_t n)
584
{
585 1
	return sizeof(ec_o) + O_OF_W(5 * n + 1);
586
}
587

588 1
size_t ec2CreateLD_deep(size_t n, size_t f_deep)
589
{
590 1
	return utilMax(8,
591
		ec2ToALD_deep(n, f_deep),
592
		ec2NegLD_deep(n, f_deep),
593
		ec2AddLD_deep(n, f_deep),
594
		ec2AddALD_deep(n, f_deep),
595
		ec2SubLD_deep(n, f_deep),
596
		ec2SubALD_deep(n, f_deep),
597
		ec2DblLD_deep(n, f_deep),
598
		ec2DblALD_deep(n, f_deep));
599
}
600

601
/*
602
*******************************************************************************
603
Свойства кривой
604
*******************************************************************************
605
*/
606

607 1
bool_t ec2IsValid(const ec_o* ec, void* stack)
608
{
609
	// кривая работоспособна? поле ec->f корректно?
610
	// ec->deep >= ec->f->deep?
611
	// A, B \in ec->f, B != 0?
612 1
	return ecIsOperable2(ec) &&
613 1
		gf2IsValid(ec->f, stack) &&
614 1
		ec->deep >= ec->f->deep &&
615 1
		gf2IsIn(ec->A, ec->f) &&
616 1
		gf2IsIn(ec->B, ec->f) &&
617 1
		!qrIsZero(ec->B, ec->f);
618
}
619

620 1
size_t ec2IsValid_deep(size_t n)
621
{
622 1
	return gf2IsValid_deep(n);
623
}
624

625 1
bool_t ec2SeemsValidGroup(const ec_o* ec, void* stack)
626
{
627 1
	size_t n = ec->f->n;
628
	// переменные в stack
629 1
	word* t1 = (word*)stack;
630 1
	word* t2 = t1 + n + 1;
631 1
	word* t3 = t2 + n + 2;
632 1
	stack = t3 + 2 * n;
633
	// pre
634 1
	ASSERT(ecIsOperable(ec));
635
	// ecIsOperableGroup(ec) == TRUE? base \in ec?
636 1
	if (!ecIsOperableGroup(ec) ||
637 1
		!ec2IsOnA(ec->base, ec, stack))
638 0
		return FALSE;
639
	// [n + 1]t1 <- 2^m
640 1
	wwSetZero(t1, n + 1);
641 1
	wwFlipBit(t1, gf2Deg(ec->f));
642
	// [n + 2]t2 <- order * cofactor
643 1
	t2[n + 1] = zzMulW(t2, ec->order, n + 1, ec->cofactor);
644
	// t2 <- |t2 - (2^m + 1)|
645 1
	if (zzSubW2(t2, n + 2, 1))
646 0
		return FALSE;
647 1
	if (wwCmp2(t2, n + 2, t1, n + 1) >= 0)
648 1
		t2[n + 1] -= zzSub2(t2, t1, n + 1);
649
	else
650 1
		zzSub(t2, t1, t2, n + 1);
651
	// n <- длина t2
652 1
	n = wwWordSize(t2, n + 2);
653
	// n > ec->f->n => t2^2 > 4 2^m
654 1
	if (n > ec->f->n)
655 0
		return FALSE;
656
	// [2n]t3 <- ([n]t2)^2
657 1
	zzSqr(t3, t2, n, stack);
658
	// t1 <- 4 2^m
659 1
	wwFlipBit(t1, gf2Deg(ec->f));
660 1
	wwFlipBit(t1, gf2Deg(ec->f) + 2);
661
	// условие Хассе: t3 <= 4 2^m?
662 1
	return wwCmp2(t3, 2 * n, t3, ec->f->n + 1) <= 0;
663
}
664

665 1
size_t ec2SeemsValidGroup_deep(size_t n, size_t f_deep)
666
{
667 1
	return O_OF_W(4 * n + 3) +
668 1
		utilMax(2,
669
			ec2IsOnA_deep(n, f_deep),
670
			zzSqr_deep(n));
671
}
672

673 1
bool_t ec2IsSafeGroup(const ec_o* ec, size_t mov_threshold, void* stack)
674
{
675 1
	size_t n1 = ec->f->n + 1;
676
	// переменные в stack
677 1
	word* t1 = (word*)stack;
678 1
	word* t2 = t1 + n1;
679 1
	stack = t2 + n1;
680
	// pre
681 1
	ASSERT(ecIsOperable(ec));
682 1
	ASSERT(ecIsOperableGroup(ec));
683
	// order -- простое?
684 1
	n1 = wwWordSize(ec->order, n1);
685 1
	if (!priIsPrime(ec->order, n1, stack))
686 0
		return FALSE;
687
	// t1 <- 2^m
688 1
	wwSetZero(t1, ec->f->n + 1);
689 1
	wwFlipBit(t1, gf2Deg(ec->f));
690
	// order == 2^m?
691 1
	if (wwCmp2(t1, ec->f->n + 1, ec->order, n1) == 0)
692 0
		return FALSE;
693
	// проверка MOV
694 1
	if (mov_threshold)
695
	{
696 1
		zzMod(t1, t1, ec->f->n + 1, ec->order, n1, stack);
697 1
		wwCopy(t2, t1, n1);
698 1
		if (wwCmpW(t2, n1, 1) == 0)
699 0
			return FALSE;
700 1
		while (--mov_threshold)
701
		{
702 1
			zzMulMod(t2, t2, t1, ec->order, n1, stack);
703 1
			if (wwCmpW(t2, n1, 1) == 0)
704 0
				return FALSE;
705
		}
706
	}
707
	// все нормально
708 1
	return TRUE;
709
}
710

711 1
size_t ec2IsSafeGroup_deep(size_t n)
712
{
713 1
	const size_t n1 = n + 1;
714 1
	return O_OF_W(2 * n1) +
715 1
		utilMax(3,
716
			priIsPrime_deep(n1),
717
			zzMod_deep(n + 1, n1),
718
			zzMulMod_deep(n1));
719
}
720

721
/*
722
*******************************************************************************
723
Арифметика аффинных точек
724

725
Сложение A <- A + A:
726
		1D + 2M + 1S + 9add \approx 26M
727

728
Удвоение A <- 2A:
729
		1D + 2M + 1S + 6add \approx 26M
730
*******************************************************************************
731
*/
732

733 1
bool_t ec2IsOnA(const word a[], const ec_o* ec, void* stack)
734
{
735 1
	const size_t n = ec->f->n;
736
	// переменные в stack
737 1
	word* t1 = (word*)stack;
738 1
	word* t2 = t1 + n;
739 1
	stack = t2 + n;
740
	// pre
741 1
	ASSERT(ecIsOperable(ec));
742
	// xa, ya \in ec->f?
743 1
	if (!ec2SeemsOnA(a, ec))
744 0
		return FALSE;
745
	// t1 <- (xa + A)xa^2 + B
746 1
	qrSqr(t1, ecX(a), ec->f, stack);
747 1
	gf2Add(t2, ecX(a), ec->A, ec->f);
748 1
	qrMul(t1, t1, t2, ec->f, stack);
749 1
	gf2Add2(t1, ec->B, ec->f);
750
	// t2 <- ya(ya + xa)
751 1
	gf2Add(t2, ecX(a), ecY(a, n), ec->f);
752 1
	qrMul(t2, t2, ecY(a, n), ec->f, stack);
753
	// t1 == t2?
754 1
	return qrCmp(t1, t2, ec->f) == 0;
755
}
756

757 1
size_t ec2IsOnA_deep(size_t n, size_t f_deep)
758
{
759 1
	return O_OF_W(2 * n) + f_deep;
760
}
761

762 1
void ec2NegA(word b[], const word a[], const ec_o* ec)
763
{
764 1
	const size_t n = ec->f->n;
765
	// pre
766 1
	ASSERT(ecIsOperable(ec));
767 1
	ASSERT(ec2SeemsOnA(a, ec));
768 1
	ASSERT(wwIsSameOrDisjoint(a, b, 3 * n));
769
	// b <- (xa, ya + xa)
770 1
	qrCopy(ecX(b), ecX(a), ec->f);
771 1
	gf2Add(ecY(b, n), ecX(a), ecY(a, n), ec->f);
772
}
773

774 0
bool_t ec2AddAA(word c[], const word a[], const word b[], const ec_o* ec,
775
	void* stack)
776
{
777 0
	const size_t n = ec->f->n;
778
	// переменные в stack
779 0
	word* t1 = (word*)stack;
780 0
	word* t2 = t1 + n;
781 0
	word* t3 = t2 + n;
782 0
	stack = t3 + n;
783
	// pre
784 0
	ASSERT(ecIsOperable(ec));
785 0
	ASSERT(ec2SeemsOnA(a, ec));
786 0
	ASSERT(ec2SeemsOnA(b, ec));
787 0
	ASSERT(wwIsDisjoint(a, c, 2 * n));
788
	// xa == xb => (xa, ya) == \pm(xb, yb)
789 0
	if (qrCmp(ecX(a), ecX(b), ec->f) == 0)
790
	{
791
		// (xa, ya) == -(xb, yb)?
792 0
		if (qrCmp(ecY(a, n), ecY(b, n), ec->f) != 0)
793 0
			return FALSE;
794
		// xa == 0 => 2(xa, ya) == O
795 0
		if (qrIsZero(ecX(a), ec->f))
796 0
			return FALSE;
797
		// t1 <- ya / xa + xa [\lambda]
798 0
		qrDiv(t1, ecY(a, n), ecX(a), ec->f, stack);
799 0
		gf2Add2(t1, ecX(a), ec->f);
800
		// t2 <- xa
801 0
		qrCopy(t2, ecX(a), ec->f);
802
		// xc <- t1^2 + t1 + A [xa^2 + B / xa^2]
803 0
		qrSqr(ecX(c), t1, ec->f, stack);
804 0
		gf2Add2(ecX(c), t1, ec->f);
805 0
		gf2Add2(ecX(c), ec->A, ec->f);
806
		// t2 <- t1 * (t2 + xc) [\lambda(xa + xc)]
807 0
		gf2Add2(t2, ecX(c), ec->f);
808 0
		qrMul(t2, t1, t2, ec->f, stack);
809
		// yc <- ya + t2 + xc
810 0
		gf2Add(ecY(c, n), ecY(a, n), t2, ec->f);
811 0
		gf2Add2(ecY(c, n), ecX(c), ec->f);
812
		// получена аффинная точка
813 0
		return TRUE;
814
	}
815
	// t1 <- xa
816 0
	qrCopy(t1, ecX(a), ec->f);
817
	// xc <- xa + xb
818 0
	gf2Add(ecX(c), ecX(a), ecX(b), ec->f);
819
	// t2 <- ya + yb
820 0
	gf2Add(t2, ecY(a, n), ecY(b, n), ec->f);
821
	// t2 <- t2 / xc [\lambda]
822 0
	qrDiv(t2, t2, ecX(c), ec->f, stack);
823
	// t3 <- t2^2 [\lambda^2]
824 0
	qrSqr(t3, t2, ec->f, stack);
825
	// xc <- xc + t2 + t3 + A [\lambda^2 + \lambda + (xa + xb) + A]
826 0
	gf2Add2(ecX(c), t2, ec->f);
827 0
	gf2Add2(ecX(c), t3, ec->f);
828 0
	gf2Add2(ecX(c), ec->A, ec->f);
829
	// t1 <- t1 + xc [xa + xc]
830 0
	gf2Add2(t1, ecX(c), ec->f);
831
	// t1 <- t1 * t2 [(xa + xc)\lambda]
832 0
	qrMul(t1, t1, t2, ec->f, stack);
833
	// yc <- xc + ya + t1 [(xa + xc)\lambda + xc + ya]
834 0
	gf2Add(ecY(c, n), ecY(a, n), ecX(c), ec->f);
835 0
	gf2Add2(ecY(c, n), t1, ec->f);
836
	// получена аффинная точка
837 0
	return TRUE;
838
}
839

840 0
size_t ec2AddAA_deep(size_t n, size_t f_deep)
841
{
842 0
	return O_OF_W(3 * n) + f_deep;
843
}
844

845 0
bool_t ec2SubAA(word c[], const word a[], const word b[], const ec_o* ec,
846
	void* stack)
847
{
848 0
	const size_t n = ec->f->n;
849
	// переменные в stack
850 0
	word* t = (word*)stack;
851 0
	stack = t + 2 * n;
852
	// t <- -b
853 0
	ec2NegA(t, b, ec);
854
	// с <- a + t
855 0
	return ec2AddAA(c, a, t, ec, stack);
856
}
857

858 0
size_t ec2SubAA_deep(size_t n, size_t f_deep)
859
{
860 0
	return O_OF_W(2 * n) + ec2AddAA_deep(n, f_deep);
861
}

Read our documentation on viewing source code .

Loading