agievich / bee2
1
/*
2
*******************************************************************************
3
\file bels.c
4
\brief STB 34.101.60 (bels): secret sharing algorithms
5
\project bee2 [cryptographic library]
6
\author (C) Sergey Agievich [agievich@{bsu.by|gmail.com}]
7
\created 2013.05.14
8
\version 2018.11.30
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/blob.h"
15
#include "bee2/core/err.h"
16
#include "bee2/core/mem.h"
17
#include "bee2/core/u32.h"
18
#include "bee2/core/util.h"
19
#include "bee2/crypto/bels.h"
20
#include "bee2/crypto/belt.h"
21
#include "bee2/math/pp.h"
22
#include "bee2/math/ww.h"
23
#include "bee2/math/zz.h"
24

25
#include "bee2/core/rng.h"
26

27
/*
28
*******************************************************************************
29
Открытые ключи
30
*******************************************************************************
31
*/
32

33
static const u32 m_16[17] = 
34
{
35
	0x00000087, 
36
	0x00000285, 0x00000C41, 0x00001821, 0x00008015, 
37
	0x00008301, 0x00020281, 0x00022081, 0x0002A001, 
38
	0x00080141, 0x00080205, 0x00082801, 0x0008A001,
39
	0x00108041, 0x00200025, 0x00200405, 0x00200C01,
40
};
41

42
static const u32 m_24[17] = 
43
{
44
	0x00000087, 
45
	0x00001209, 0x00001241, 0x00008601, 0x00008821, 
46
	0x0000C005, 0x00020049, 0x00020085, 0x00021009, 
47
	0x00060801, 0x00090201, 0x000A0081, 0x00200411,
48
	0x00228001, 0x00400209, 0x00420801, 0x00810401,
49
};
50

51
static const u32 m_32[17] = 
52
{
53
	0x00000425, 
54
	0x0001000B, 0x0001000D, 0x0001A001, 0x00020061, 
55
	0x00040085, 0x00200181, 0x00204005, 0x00280011, 
56
	0x00810201, 0x00820401, 0x0100000B, 0x01002801,
57
	0x01200009, 0x02000029, 0x02002009, 0x0800000B,
58
};
59

60 1
err_t belsStdM(octet m[], size_t len, size_t num)
61
{
62
	// проверить входные данные
63 1
	if ((len != 16 && len != 24 && len != 32) || 
64 1
		!memIsValid(m, len) || num > 16)
65 0
		return ERR_BAD_INPUT;
66
	// загрузить
67 1
	if (len == 16)
68 1
		u32To(m, 4, m_16 + num);
69 1
	else if (len == 24)
70 1
		u32To(m, 4, m_24 + num);
71
	else
72 1
		u32To(m, 4, m_32 + num);
73 1
	memSetZero(m + 4, len - 4);
74 1
	return ERR_OK;
75
}
76

77 1
err_t belsValM(const octet m0[], size_t len)
78
{
79
	size_t n;
80
	void* state;
81
	word* f0;
82
	void* stack;
83
	err_t code;
84
	// проверить входные данные
85 1
	if ((len != 16 && len != 24 && len != 32) || !memIsValid(m0, len))
86 0
		return ERR_BAD_INPUT;
87
	// создать состояние
88 1
	n = W_OF_O(len);
89 1
	state = blobCreate(n + 1 + ppIsIrred_deep(n + 1));
90 1
	if (state == 0)
91 0
		return ERR_OUTOFMEMORY;
92
	// раскладка состояния
93 1
	f0 = (word*)state;
94 1
	stack = f0 + n + 1;
95
	// загрузить многочлен
96 1
	wwFrom(f0, m0, len);
97 1
	f0[n] = 1;
98
	// неприводим?
99 1
	code = ppIsIrred(f0, n + 1, stack) ? ERR_OK : ERR_BAD_PUBKEY;
100
	// завершение
101 1
	blobClose(state);
102 1
	return code;
103
}
104

105
/*
106
*******************************************************************************
107
Генерация открытых ключей
108

109
\todo Изменить логику работы с gen_i: связать возврат ERR_BAD_ANG с 
110
B_PER_IMPOSSIBLE.
111
*******************************************************************************
112
*/
113

114 1
err_t belsGenM0(octet m0[], size_t len, gen_i ang, void* ang_state)
115
{
116
	size_t n, reps;
117
	void* state;
118
	word* f0;
119
	void* stack;
120
	// проверить генератор
121 1
	if (ang == 0)
122 0
		return ERR_BAD_ANG;
123
	// проверить входные данные
124 1
	if ((len != 16 && len != 24 && len != 32) || 
125 1
		!memIsValid(m0, len))
126 0
		return ERR_BAD_INPUT;
127
	// создать состояние
128 1
	n = W_OF_O(len);
129 1
	state = blobCreate(n + 1 + ppIsIrred_deep(n + 1));
130 1
	if (state == 0)
131 0
		return ERR_OUTOFMEMORY;
132
	// раскладка состояния
133 1
	f0 = (word*)state;
134 1
	stack = f0 + n + 1;
135
	// сгенерировать многочлен
136 1
	f0[n] = 1;
137 1
	for (reps = len * 8 * B_PER_IMPOSSIBLE * 3 / 4; reps--;)
138
	{
139 1
		ang(f0, len, ang_state);
140 1
		wwFrom(f0, f0, len);
141 1
		if (ppIsIrred(f0, n + 1, stack))
142
		{
143 1
			wwTo(m0, len, f0);
144 1
			break;
145
		}
146
	}
147
	// завершение
148 1
	blobClose(state);
149 1
	return reps != SIZE_MAX ? ERR_OK : ERR_BAD_ANG;
150
}
151

152 1
err_t belsGenMi(octet mi[], size_t len, const octet m0[], gen_i ang, 
153
	void* ang_state)
154
{
155
	size_t n, reps;
156
	err_t code;
157
	void* state;
158
	word* f0;
159
	word* u;
160
	word* f;
161
	void* stack;
162
	// проверить генератор
163 1
	if (ang == 0)
164 0
		return ERR_BAD_ANG;
165
	// проверить входные данные
166 1
	if ((len != 16 && len != 24 && len != 32) || 
167 1
		!memIsValid(m0, len) || !memIsValid(mi, len))
168 0
		return ERR_BAD_INPUT;
169
	EXPECT(belsValM(m0, len) == ERR_OK);
170
	// создать состояние
171 1
	n = W_OF_O(len);
172 1
	state = blobCreate(O_OF_W(2 * n + 2) + ppMinPolyMod_deep(n + 1));
173 1
	if (state == 0)
174 0
		return ERR_OUTOFMEMORY;
175
	// раскладка состояния
176 1
	f0 = (word*)state;
177 1
	f = f0 + n + 1;
178 1
	u = f;
179 1
	stack = f + n + 1;
180
	// загрузить многочлен
181 1
	wwFrom(f0, m0, len);
182 1
	f0[n] = 1;
183
	// попытки генерации
184 1
	for (reps = 3; reps--; )
185
	{
186 1
		ang(u, len, ang_state);
187 1
		wwFrom(u, u, len), u[n] = 0;
188
		// f <- минимальный многочлен элемента u
189 1
		ppMinPolyMod(f, u, f0, n + 1, stack);
190
		// f подходит?
191 1
		if (f[n] == 1 && wwCmp(f, f0, n) != 0)
192
		{
193 1
			wwTo(mi, len, f);
194 1
			break;
195
		}
196
	}
197
	// завершение
198 1
	if (reps != SIZE_MAX)
199 1
		code = ERR_OK;
200 0
	else if (wwEq(f, f0, n + 1))
201 0
		code = ERR_BAD_ANG;
202
	else 
203 0
		code = ERR_BAD_PUBKEY;
204 1
	blobClose(state);
205 1
	return code;
206
}
207

208 1
err_t belsGenMid(octet mid[], size_t len, const octet m0[], const octet id[], 
209
	size_t id_len)
210
{
211
	size_t n, reps;
212
	void* state;
213
	word* f0;
214
	word* f;
215
	word* u;
216
	void* stack;
217
	// проверить входные данные
218 1
	if ((len != 16 && len != 24 && len != 32) || 
219 1
		!memIsValid(m0, len) || !memIsValid(mid, len) || 
220 1
		!memIsValid(id, id_len))
221 0
		return ERR_BAD_INPUT;
222
	EXPECT(belsValM(m0, len) == ERR_OK);
223
	// создать состояние
224 1
	n = W_OF_O(len);
225 1
	state = blobCreate(O_OF_W(2 * n + 2) + 32 + O_PER_W +
226 1
		utilMax(2, 
227
			beltHash_keep(),
228
			ppMinPolyMod_deep(n + 1)));
229 1
	if (state == 0)
230 0
		return ERR_OUTOFMEMORY;
231
	// раскладка состояния
232 1
	f0 = (word*)state;
233 1
	f = f0 + n + 1;
234 1
	u = f + n + 1;
235 1
	stack = u + W_OF_O(32) + 1;
236
	// загрузить многочлен
237 1
	wwFrom(f0, m0, len);
238 1
	f0[n] = 1;
239
	// хэшировать
240 1
	beltHashStart(stack);
241 1
	beltHashStepH(id, id_len, stack);
242 1
	beltHashStepG((octet*)u, stack);
243 1
	wwFrom(u, u, 32);
244 1
	u[n] = 0;
245
	// попытки генерации
246 1
	for (reps = MAX2(3, B_PER_IMPOSSIBLE * 2 / len / 8); reps--;)
247
	{
248
		// f <- минимальный многочлен элемента u
249 1
		ppMinPolyMod(f, u, f0, n + 1, stack);
250
		// f подходит?
251 1
		if (f[n] == 1 && !wwEq(f, f0, n))
252
		{
253 1
			wwTo(mid, len, f);
254 1
			break;
255
		}
256
		// u <- u + 1
257 0
		zzAddW2(u, n, 1);
258
	}
259
	// завершение
260 1
	blobClose(state);
261 1
	return reps != SIZE_MAX ? ERR_OK : ERR_BAD_PUBKEY;
262
}
263

264
/*
265
*******************************************************************************
266
Разделение секрета
267
*******************************************************************************
268
*/
269

270 1
err_t belsShare(octet si[], size_t count, size_t threshold, size_t len, 
271
	const octet s[], const octet m0[], const octet mi[], 
272
	gen_i rng, void* rng_state)
273
{
274
	size_t n, i;
275
	void* state;
276
	word* f;
277
	word* k;
278
	word* c;
279
	void* stack;
280
	// проверить генератор
281 1
	if (rng == 0)
282 0
		return ERR_BAD_RNG;
283
	// проверить входные данные
284 1
	if ((len != 16 && len != 24 && len != 32) || 
285 1
		threshold == 0 || count < threshold ||
286 1
		!memIsValid(s, len) || !memIsValid(m0, len) || 
287 1
		!memIsValid(mi, len * count) || !memIsValid(si, len * count))
288 0
		return ERR_BAD_INPUT;
289
	EXPECT(belsValM(m0, len) == ERR_OK);
290
	// создать состояние
291 1
	n = W_OF_O(len);
292 1
	state = blobCreate(O_OF_W(2 * threshold * n + 1) + 
293 1
		utilMax(2, 
294 1
			ppMul_deep(threshold * n - n, n),
295
			ppMod_deep(threshold * n, n + 1)));
296 1
	if (state == 0)
297 0
		return ERR_OUTOFMEMORY;
298
	// раскладка состояния
299 1
	f = (word*)state;
300 1
	k = f + n + 1;
301 1
	c = k + threshold * n - n;
302 1
	stack = c + threshold * n;
303
	// сгенерировать k
304 1
	rng(k, threshold * len - len, rng_state);
305 1
	wwFrom(k, k, threshold * len - len);
306
	// c(x) <- (x^l + m0(x))k(x) + s(x)
307 1
	wwFrom(f, m0, len);
308 1
	ppMul(c, k, threshold * n - n, f, n, stack);
309 1
	wwXor2(c + n, k, threshold * n - n);
310 1
	wwFrom(f, s, len);
311 1
	wwXor2(c, f, n);
312
	// цикл по пользователям
313 1
	for (i = 0; i < count; ++i)
314
	{
315
		// f(x) <- x^l + mi(x)
316
		EXPECT(belsValM(mi + i * len, len) == ERR_OK);
317 1
		wwFrom(f, mi + i * len, len);
318 1
		f[n] = 1;
319
		// si(x) <- c(x) mod f(x)
320 1
		ppMod(f, c, threshold * n, f, n + 1, stack);
321 1
		wwTo(si + i * len, len, f);
322
	}
323
	// завершение
324 1
	blobClose(state);
325 1
	return ERR_OK;
326
}
327

328 1
err_t belsShare2(octet si[], size_t count, size_t threshold, size_t len, 
329
	const octet s[])
330
{
331
	size_t n, i;
332
	void* state;
333
	word* f;
334
	u32* K;
335
	octet* iv;
336
	word* k;
337
	word* c;
338
	void* stack;
339
	// проверить входные данные
340 1
	if ((len != 16 && len != 24 && len != 32) || 
341 1
		threshold == 0 || count < threshold || count > 16 ||
342 1
		!memIsValid(s, len) || !memIsValid(si, len * count))
343 0
		return ERR_BAD_INPUT;
344
	// создать состояние
345 1
	n = W_OF_O(len);
346 1
	state = blobCreate(O_OF_W(2 * threshold * n + 1) + 
347 1
		utilMax(4,
348
			beltCTR_keep(),
349 1
			32 + beltCompr_deep(),
350 1
			ppMul_deep(threshold * n - n, n),
351
			ppMod_deep(threshold * n, n + 1)));
352 1
	if (state == 0)
353 0
		return ERR_OUTOFMEMORY;
354
	// раскладка состояния
355 1
	f = (word*)state;
356 1
	iv = (octet*)state;
357 1
	k = f + n + 1;
358 1
	c = k + threshold * n - n;
359 1
	stack = c + threshold * n;
360 1
	K = (u32*)stack;
361
	// K <- belt-keyexpand(s)
362 1
	beltKeyExpand2(K, s, len);
363
	// K <- belt-compress(~K || K)
364 1
	memCopy(f, K, 32);
365 1
	memNeg(K, 32);
366 1
	beltCompr(K, (u32*)f, (octet*)stack + 32);
367 1
	u32To(stack, 32, K);
368
	// iv <- <n> || <t> || 0
369 1
	memSetZero(iv, 16);
370 1
	iv[0] = (octet)count;
371 1
	iv[4] = (octet)threshold;
372
	// k <- belt-ctr(0, K, iv)
373 1
	beltCTRStart(stack, stack, 32, iv);
374 1
	memSetZero(k, threshold * len - len);
375 1
	beltCTRStepE(k, threshold * len - len, stack);
376 1
	wwFrom(k, k, threshold * len - len);
377
	// c(x) <- (x^l + m0(x))k(x) + s(x)
378 1
	belsStdM(stack, len, 0);
379 1
	wwFrom(f, stack, len);
380 1
	ppMul(c, k, threshold * n - n, f, n, stack);
381 1
	wwXor2(c + n, k, threshold * n - n);
382 1
	wwFrom(f, s, len);
383 1
	wwXor2(c, f, n);
384
	// цикл по пользователям
385 1
	for (i = 0; i < count; ++i)
386
	{
387
		// f(x) <- x^l + mi(x)
388 1
		belsStdM(stack, len, i + 1);
389 1
		wwFrom(f, stack, len);
390 1
		f[n] = 1;
391
		// si(x) <- c(x) mod f(x)
392 1
		ppMod(f, c, threshold * n, f, n + 1, stack);
393 1
		wwTo(si + i * len, len, f);
394
	}
395
	// завершение
396 1
	blobClose(state);
397 1
	return ERR_OK;
398
}
399

400
/*
401
*******************************************************************************
402
Восстановление секрета
403

404
\todo Организовать вычисления так, чтобы не было медленных (без Карацубы)
405
умножений "маленького" многочлена на "большой".
406
*******************************************************************************
407
*/
408

409 1
err_t belsRecover(octet s[], size_t count, size_t len, const octet si[], 
410
	const octet m0[], const octet mi[])
411
{
412
	size_t n, i, deep;
413
	void* state;
414
	word* f;
415
	word* g;
416
	word* d;
417
	word* u;
418
	word* v;
419
	word* c;
420
	word* t;
421
	void* stack;
422
	// проверить входные данные
423 1
	if ((len != 16 && len != 24 && len != 32) || count == 0 || 
424 1
		!memIsValid(si, count * len) || !memIsValid(m0, len) || 
425 1
		!memIsValid(mi, len * count) || !memIsValid(s, len))
426 0
		return ERR_BAD_INPUT;
427
	EXPECT(belsValM(m0, len) == ERR_OK);
428
	// расчет глубины стека
429 1
	n = W_OF_O(len);
430 1
	deep = utilMax(2, 
431
		ppMul_deep(n, n), 
432
		ppMod_deep(count * n, n + 1));
433 1
	for (i = 1; i < count; ++i)
434 1
		deep = utilMax(6, 
435
			deep, 
436 1
			ppExGCD_deep(n + 1, i * n + 1),
437
			ppMul_deep(i * n, i * n),
438 1
			ppMul_deep(2 * i * n, n),
439
			ppMul_deep(2 * n, i * n),
440 1
			ppMod_deep((2 * i + 1) * n, (i + 1) * n + 1));
441 1
	deep += O_OF_W(
442
		n + 1 +			
443
		count * n + 1 +
444
		(count - 1) * n + 1 +
445
		(count - 1) * n + 1 +
446
		n + 1 +
447
		(2 * count - 1) * n + 
448
		MAX2((2 * count - 2) * n, (count + 1) * n));
449
	// создать состояние
450 1
	state = blobCreate(deep);
451 1
	if (state == 0)
452 0
		return ERR_OUTOFMEMORY;
453
	// раскладка состояния
454 1
	f = (word*)state;
455 1
	g = f + n + 1;
456 1
	d = g + count * n + 1;
457 1
	u = d + (count - 1) * n + 1;
458 1
	v = u + (count - 1) * n + 1;
459 1
	c = v + n + 1;
460 1
	t = c + (2 * count - 1) * n;
461 1
	stack = t + MAX2((2 * count - 2) * n, (count + 1) * n);
462
	// [n]c(x) <- s1(x)
463 1
	wwFrom(c, si, len);
464
	// [n + 1]g(x) <- x^l + m1(x)
465 1
	wwFrom(g, mi, len), g[n] = 1;
466
	// цикл по пользователям
467 1
	for (f[n] = 1, i = 1; i < count; ++i)
468
	{
469
		// [n + 1]f(x) <- x^l + mi(x)
470 1
		wwFrom(f, mi + i * len, len);
471
		// найти d(x) = \gcd(f(x), g(x)) и коэфф. Безу [i * n]u(x), [n]v(x)
472 1
		ppExGCD(d, u, v, f, n + 1, g, i * n + 1, stack);
473 1
		ASSERT(u[i * n] == 0 && v[n] == 0);
474
		// d(x) != 1? 
475 1
		if (wwCmpW(d, i * n + 1, 1) != 0)
476
		{
477 0
			blobClose(state);
478 0
			return ERR_BAD_PUBKEY;
479
		}
480
		// [2 * i * n]c(x) <- u(x)f(x)c(x)
481
		// (с помощью [2 * i * n]t)
482 1
		ppMul(t, u, i * n, c, i * n, stack);
483 1
		ppMul(c, t, 2 * i * n, f, n, stack);
484 1
		wwXor2(c + n, t, 2 * i * n);
485
		// c(x) <- c(x) + v(x)g(x)si(x)
486
		// (с помощью [2 * n]d и [(i + 2) * n]t)
487 1
		wwFrom(t, si + i * len, len);
488 1
		ppMul(d, v, n, t, n, stack);
489 1
		ppMul(t, d, 2 * n, g, i * n, stack);
490 1
		wwXor2(t + i * n, d, 2 * n);
491 1
		wwXor2(c, t, (i + 2) * n);
492
		// [(i + 1) * n + 1]g(x) <- g(x)f(x)
493
		// (с помощью [(i + 1) * n]t)
494 1
		ppMul(t, f, n, g, i * n, stack);
495 1
		wwXor2(t + n, g, i * n);
496 1
		wwXor2(t + i * n, f, n);
497 1
		wwCopy(g, t, (i + 1) * n);
498 1
		g[(i + 1) * n] = 1;
499
		// [(i + 1) * n]c(x) <- c(x) mod g(x)
500 1
		ppMod(c, c, (2 * i + 1) * n, g, (i + 1) * n + 1, stack);
501 1
		ASSERT(c[(i + 1) * n] == 0);
502
	}
503
	// [n]s(x) <- c(x) mod (x^l + m0(x))
504 1
	wwFrom(f, m0, len), f[n] = 1;
505 1
	ppMod(c, c, count * n, f, n + 1, stack);
506 1
	ASSERT(c[n] == 0);
507 1
	wwTo(s, len, c);
508
	// завершение
509 1
	blobClose(state);
510 1
	return ERR_OK;
511
}

Read our documentation on viewing source code .

Loading