1
/*
2
*******************************************************************************
3
\file belt_fmt.c
4
\brief STB 34.101.31 (belt): FMT (format preserving encryption)
5
\project bee2 [cryptographic library]
6
\author (C) Sergey Agievich [agievich@{bsu.by|gmail.com}]
7
\created 2017.09.28
8
\version 2020.03.24
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/u16.h"
18
#include "bee2/core/u32.h"
19
#include "bee2/core/util.h"
20
#include "bee2/crypto/belt.h"
21
#include "bee2/math/ww.h"
22
#include "bee2/math/zz.h"
23
#include "belt_lcl.h"
24

25
/*
26
*******************************************************************************
27
Минимальное число 64-битовых блоков для размещения слова из ZZ_mod^count.
28

29
Необходимо вычислить ceil(log2(mod) * count / 64).
30

31
Реализован следующий алгоритм:
32

33
1. c <- 1588 / 2291 (диофантово приближение ln 2 через цепные дроби).
34
2. 2^k <- ближайшая к mod степень двойки.
35
3. x <- (m - 2^k)/ 2^k.
36
4. y <- x(60 + 60x + 11x^2)/(60 + 60x + 36x^2 + 3x^3) 
37
   (аппроксимация Паде для ln(1 + x)).
38
5. b <- ceil((k + y / c) * count / 64).
39
6. Возвратить b.
40

41
Аргумент ceil() на предпоследнем шаге можно записать следующим образом:
42
\code
43
	count * (4764 k (8^k + 9 4^k mod + 9 2^k mod^2 + mod^3) - 
44
			   2291(11 8^k + 27 4^k mod - 27 2^k mod^2 - 11 mod^3)) / 
45
	304896 * (8^k + 9 4^k mod + 9 2^k mod^2 + mod^3)
46
\endcode
47

48
Алгоритм правильно работает для mod <= 65536 и count <= 300 за исключением
49
следующих сочетаний (mod, count):
50
\code
51
	(49667, 160).
52
\endcode
53

54
Проверка:
55
\code
56
	#include <math.h>
57
	...
58
	u32 mod;
59
	size_t count;
60
	for (mod = 2; mod <= 65536; ++mod)
61
		for (count = 1; count <= 300; ++count)
62
		{
63
			long double b = log(mod) / log(2.0);
64
			b *= count, b /= 64.0;
65
			if ((size_t)ceil(b) != beltFMTCalcB(mod, count))
66
				ASSERT(0);
67
		}
68
\endcode
69

70
\remark Используется соглашение sizeof(word) >= sizeof(u16): mod либо 
71
умещается в word, либо равняется 65536.
72
*******************************************************************************
73
*/
74

75 1
static size_t beltFMTCalcB(u32 mod, size_t count)
76
{
77 1
	const size_t m = W_OF_B(128);
78
	word num[W_OF_B(128)];
79
	word den[W_OF_B(128)];
80
	size_t k;
81
	word stack[W_OF_B(128) * 5];
82 1
	word* t0 = stack; 
83 1
	word* t1 = t0 + m; 
84 1
	word* t2 = t1 + m; 
85 1
	word* t3 = t2 + m; 
86 1
	word* t4 = t3 + m; 
87
	// pre
88 1
	ASSERT(2 <= mod && mod <= 65536);
89 1
	ASSERT(1 <= count && count <= 300);
90
	// обработать особые сочетания (mod, count)
91 1
	if (mod == 49667 && count == 320)
92 0
		return 39;
93
	// обработать mod, который не умещается в 16 битов
94 1
	if (mod == 65536)
95 1
		return (16 * count + 63) / 64;
96
	// k <- ceil(log2(mod))
97 1
	k = B_PER_W - wordCLZ((word)mod);
98 1
	ASSERT(k > 0);
99 1
	if ((U32_1 << k) - mod > mod - (U32_1 << (k - 1)))
100 1
		--k;
101
	// t0 <- 8^k
102 1
	wwSetZero(t0, m);
103 1
	wwSetBit(t0, 3 * k, 1);
104
	// t1 <- 4^k mod 
105 1
	wwSetZero(t1, m);
106 1
	wwSetBit(t1, 2 * k, 1);
107 1
	zzMulW(t1, t1, m, mod);
108
	// t2 <- 2^k mod^2
109 1
	wwSetZero(t2, m);
110 1
	wwSetBit(t2, k, 1);
111 1
	zzMulW(t2, t2, m, mod);
112 1
	zzMulW(t2, t2, m, mod);
113
	// t3 <- mod^3
114 1
	wwSetW(t3, m, mod);
115 1
	zzMulW(t3, t3, m, mod);
116 1
	zzMulW(t3, t3, m, mod);
117
	// den <- t0 + 9 * t1 + 9 * t2 + t3
118 1
	wwCopy(den, t0, m);
119 1
	zzAdd2(den, t3, m);
120 1
	wwCopy(t4, t1, m);
121 1
	zzAdd2(t4, t2, m);
122 1
	zzMulW(t4, t4, m, 9);
123 1
	zzAdd2(den, t4, m);
124
	// num <- den * 4767 k 
125 1
	wwCopy(num, den, m);
126 1
	zzMulW(num, num, m, 4764);
127 1
	zzMulW(num, num, m, (word)k);
128
	// num <- count * (num - 25201 t0 - 61857 t1 + 61857 t2 + 25201 t3)
129 1
	zzMulW(t3, t3, m, 25201);
130 1
	zzAdd2(num, t3, m);
131 1
	zzMulW(t2, t2, m, 61857u);
132 1
	zzAdd2(num, t2, m);
133 1
	zzMulW(t1, t1, m, 61857u);
134 1
	zzSub2(num, t1, m);
135 1
	zzMulW(t0, t0, m, 25201);
136 1
	zzSub2(num, t0, m);
137 1
	zzMulW(num, num, m, (word)count);
138
	// den <- 304896 * den
139 1
	zzMulW(den, den, m, 768);
140 1
	zzMulW(den, den, m, 397);
141
	// num <- num + den - 1
142 1
	zzAdd2(num, den, m);
143 1
	zzSubW2(num, m, 1);
144
	// num <- num / den
145 1
	for (k = m; den[k - 1] == 0; --k);
146 1
	ASSERT(zzDiv_deep(m, k) <= sizeof(stack));
147 1
	zzDiv(den, num, num, m, den, k, stack);
148
	// возврат
149 1
	return (size_t)den[0];
150
}
151

152
/*
153
*******************************************************************************
154
belt-32block
155
*******************************************************************************
156
*/
157

158 1
void belt32BlockEncr(octet block[24], const u32 key[8])
159
{
160 1
	u32* t = (u32*)block;
161 1
	u32From(t, block, 24);
162
	// round #1
163 1
	beltBlockEncr3(t + 2, t + 3, t + 4, t + 5, key);
164 1
	t[2] ^= 1, t[0] ^= t[2], t[1] ^= t[3];
165
	// round #2
166 1
	beltBlockEncr3(t + 4, t + 5, t + 0, t + 1, key);
167 1
	t[4] ^= 2, t[2] ^= t[4], t[3] ^= t[5];
168
	// round #3
169 1
	beltBlockEncr3(t + 0, t + 1, t + 2, t + 3, key);
170 1
	t[0] ^= 3, t[4] ^= t[0], t[5] ^= t[1];
171
	// возврат
172 1
	u32To(block, 24, t);
173
}
174

175
/*
176
*******************************************************************************
177
Конвертации
178
*******************************************************************************
179
*/
180

181 1
static void beltStr2Bin(octet bin[], size_t b, u32 mod, 
182
	const u16 str[], size_t count)
183
{
184
	word* a;
185
	size_t m;
186
	// подготовить память
187 1
	memSetZero(bin, 8 * b);
188
	// особый случай: mod может не уложиться в word
189 1
	if (mod == 65536)
190
	{
191 1
		u16To(bin, 2 * count, str);
192 1
		return;
193
	}
194
	// конвертировать
195 1
	ASSERT(2 <= mod && mod < 65536);
196 1
	ASSERT(count >= 1);
197 1
	--count;
198
	EXPECT(str[count] < mod);
199 1
	a = (word*)bin;
200 1
	m = W_OF_O(8 * b);
201 1
	a[0] = (word)str[count];
202 1
	while (count--)
203
	{
204 1
		zzMulW(a, a, m, mod);
205
		EXPECT(str[count] < mod);
206 1
		zzAddW2(a, m, (word)str[count]);
207
	}
208 1
	wwTo(bin, 8 * b, a);
209
}
210

211 1
static void beltBin2StrAdd(u32 mod, u16 str[], size_t count, 
212
	octet bin[], size_t b)
213
{
214
	register u32 t;
215
	word* a;
216
	size_t m;
217
	// особый случай: mod может не уложиться в word
218 1
	if (mod == 65536)
219
	{
220 1
		u16* uu = (u16*)bin;
221 1
		u16From(uu, bin, 8 * b);
222 1
		while (count--)
223 1
			str[count] += uu[count];
224 1
		return;
225
	}
226
	// настроить память
227 1
	m = W_OF_O(8 * b);
228 1
	a = (word*)bin;
229 1
	wwFrom(a, bin, 8 * b);
230
	// конвертировать и сложить
231 1
	ASSERT(2 <= mod && mod < 65536);
232 1
	while (count--)
233
	{
234 1
		t = (u32)zzModW(a, m, mod);
235 1
		t += str[0], t %= mod;
236 1
		str[0] = (u16)t, ++str;
237 1
		zzDivW(a, a, m, mod);
238
	}
239 1
	t = 0;
240
}
241

242 1
static void beltBin2StrSub(word mod, u16 str[], size_t count, 
243
	octet bin[], size_t b)
244
{
245
	register u32 t;
246
	word* a;
247
	size_t m;
248
	// особый случай: mod может не уложиться в word
249 1
	if (mod == 65536)
250
	{
251 1
		u16* uu = (u16*)bin;
252 1
		u16From(uu, bin, 8 * b);
253 1
		while (count--)
254 1
			str[count] -= uu[count];
255 1
		return;
256
	}
257
	// настроить память
258 1
	m = W_OF_O(8 * b);
259 1
	a = (word*)bin;
260 1
	wwFrom(a, bin, 8 * b);
261
	// конвертировать и вычесть
262 1
	ASSERT(2 <= mod && mod <= 65536);
263 1
	while (count--)
264
	{
265 1
		t = (u32)zzModW(a, m, mod);
266 1
		t = str[0] + mod - t, t %= mod;
267 1
		str[0] = (u16)t, ++str;
268 1
		zzDivW(a, a, m, mod);
269
	}
270 1
	t = 0;
271
}
272

273
/*
274
*******************************************************************************
275
Шифрование с сохранением формата (FMT)
276

277
\remark После одного beltKWPStart() выполняются многократные обращения 
278
к beltKWPStepE(). Для корректной работы перед каждым обращением в состоянии
279
механизма KWP сбрасывается счетчик тактов:
280
\code
281
	st->kwp->round = 0;
282
\endcode
283
*******************************************************************************
284
*/
285

286
typedef struct
287
{
288
	belt_wbl_st wbl[1];		/*< состояние механизма WBL */
289
	u32 mod;				/*< модуль */
290
	size_t n1;				/*< длина левой половинки */
291
	size_t n2;				/*< длина правой половинки */
292
	size_t b1;				/*< число блоков для обработки левой половинки */
293
	size_t b2;				/*< число блоков для обработки правой половинки */
294
	octet iv[4 + 16 + 4];	/*< формат || синхропосылка || формат */
295
	octet buf[];			/*< вспомогательный буфер */
296
} belt_fmt_st;
297

298 1
size_t beltFMT_keep(u32 mod, size_t count)
299
{
300 1
	ASSERT(2 <= mod && mod <= 65536);
301 1
	ASSERT(2 <= count && count <= 600);
302 1
	return sizeof(belt_fmt_st) + 8 * (beltFMTCalcB(mod, (count + 1) / 2) + 1);
303
}
304

305 1
void beltFMTStart(void* state, u32 mod, size_t count, const octet key[], 
306
	size_t len)
307
{
308 1
	belt_fmt_st* st = (belt_fmt_st*)state;
309 1
	ASSERT(2 <= mod && mod <= 65536);
310 1
	ASSERT(2 <= count && count <= 600);
311 1
	ASSERT(memIsValid(state, beltFMT_keep(mod, count)));
312
	// инициализировать состояние
313 1
	beltWBLStart(st->wbl, key, len);
314 1
	st->mod = mod;
315 1
	st->n1 = (count + 1) / 2;
316 1
	st->n2 = count / 2;
317 1
	st->b1 = beltFMTCalcB(mod, st->n1);
318 1
	st->b2 = beltFMTCalcB(mod, st->n2);
319
#if (OCTET_ORDER == LITTLE_ENDIAN)
320 1
	((u16*)st->iv)[0] = (u16)mod;
321 1
	((u16*)st->iv)[1] = (u16)count;
322
#else
323
	((u16*)st->iv)[0] = u16Rev((u16)mod);
324
	((u16*)st->iv)[1] = u16Rev((u16)count);
325
#endif
326 1
	memCopy(st->iv + 20, st->iv, 4);
327
}
328

329 1
void beltFMTStepE(u16 buf[], const octet iv[16], void* state)
330
{
331 1
	belt_fmt_st* st = (belt_fmt_st*)state;
332
	size_t i;
333 1
	ASSERT(memIsValid(state, sizeof(belt_fmt_st)));
334 1
	ASSERT(memIsValid(state, beltFMT_keep(st->mod, st->n1 + st->n2)));
335 1
	ASSERT(memIsNullOrValid(iv, 16));
336 1
	ASSERT(memIsValid(buf, 2 * st->n1 + 2 * st->n2));
337
	// подготовить синхропосылку
338 1
	if (iv)
339 1
		memCopy(st->iv + 4, iv, 16);
340
	else
341 1
		memSetZero(st->iv + 4, 16);
342
	// такты
343 1
	for (i = 0; i < 3; ++i)
344
	{
345
		// первая половинка
346 1
		beltStr2Bin(st->buf, st->b2, st->mod, buf + st->n1, st->n2);
347 1
		memCopy(st->buf + st->b2 * 8, beltH() + 8 * i, 4);
348 1
		memCopy(st->buf + st->b2 * 8 + 4, st->iv + 8 * i, 4);
349 1
		if (st->b2 == 1)
350 1
			beltBlockEncr(st->buf, st->wbl->key);
351 1
		else if (st->b2 == 2)
352 1
			belt32BlockEncr(st->buf, st->wbl->key);
353
		else
354 0
			beltWBLStepE(st->buf, 8 * st->b2 + 8, st->wbl);
355 1
		beltBin2StrAdd(st->mod, buf, st->n1, st->buf, st->b2 + 1);
356
		// вторая половинка
357 1
		beltStr2Bin(st->buf, st->b1, st->mod, buf, st->n1);
358 1
		memCopy(st->buf + st->b1 * 8, beltH() + 8 * i + 4, 4);
359 1
		memCopy(st->buf + st->b1 * 8 + 4, st->iv + 8 * i + 4, 4);
360 1
		if (st->b1 == 1)
361 1
			beltBlockEncr(st->buf, st->wbl->key);
362 1
		else if (st->b1 == 2)
363 1
			belt32BlockEncr(st->buf, st->wbl->key);
364
		else
365 1
			beltWBLStepE(st->buf, 8 * st->b1 + 8, st->wbl);
366 1
		beltBin2StrAdd(st->mod, buf + st->n1, st->n2, st->buf, st->b1 + 1);
367
	}
368
}
369

370 1
void beltFMTStepD(u16 buf[], const octet iv[16], void* state)
371
{
372 1
	belt_fmt_st* st = (belt_fmt_st*)state;
373
	size_t i;
374 1
	ASSERT(memIsValid(state, sizeof(belt_fmt_st)));
375 1
	ASSERT(memIsValid(state, beltFMT_keep(st->mod, st->n1 + st->n2)));
376 1
	ASSERT(memIsNullOrValid(iv, 16));
377 1
	ASSERT(memIsValid(buf, 2 * st->n1 + 2 * st->n2));
378
	// подготовить синхропосылку
379 1
	if (iv)
380 1
		memCopy(st->iv + 4, iv, 16);
381
	else
382 1
		memSetZero(st->iv + 4, 16);
383
	// такты
384 1
	for (i = 3; i--;)
385
	{
386
		// вторая половинка
387 1
		beltStr2Bin(st->buf, st->b1, st->mod, buf, st->n1);
388 1
		memCopy(st->buf + st->b1 * 8, beltH() + 8 * i + 4, 4);
389 1
		memCopy(st->buf + st->b1 * 8 + 4, st->iv + 8 * i + 4, 4);
390 1
		if (st->b1 == 1)
391 1
			beltBlockEncr(st->buf, st->wbl->key);
392 1
		else if (st->b1 == 2)
393 1
			belt32BlockEncr(st->buf, st->wbl->key);
394
		else
395 1
			beltWBLStepE(st->buf, 8 * st->b1 + 8, st->wbl);
396 1
		beltBin2StrSub(st->mod, buf + st->n1, st->n2, st->buf, st->b1 + 1);
397
		// первая половинка
398 1
		beltStr2Bin(st->buf, st->b2, st->mod, buf + st->n1, st->n2);
399 1
		memCopy(st->buf + st->b2 * 8, beltH() + 8 * i, 4);
400 1
		memCopy(st->buf + st->b2 * 8 + 4, st->iv + 8 * i, 4);
401 1
		if (st->b2 == 1)
402 1
			beltBlockEncr(st->buf, st->wbl->key);
403 1
		else if (st->b2 == 2)
404 1
			belt32BlockEncr(st->buf, st->wbl->key);
405
		else
406 0
			beltWBLStepE(st->buf, 8 * st->b2 + 8, st->wbl);
407 1
		beltBin2StrSub(st->mod, buf, st->n1, st->buf, st->b2 + 1);
408
	}	
409
}
410

411 1
err_t beltFMTEncr(u16 dest[], u32 mod, const u16 src[], size_t count,
412
	const octet key[], size_t len, const octet iv[16])
413
{
414
	void* state;
415
	// проверить входные данные
416 1
	if (count < 2 ||
417 1
		len != 16 && len != 24 && len != 32 ||
418 1
		!memIsValid(src, 2 * count) ||
419 1
		!memIsNullOrValid(iv, 16) ||
420 1
		!memIsValid(key, len) ||
421 1
		!memIsValid(dest, 2 * count) ||
422 1
		iv && !memIsDisjoint2(dest, 2 * count, iv, 16))
423 0
		return ERR_BAD_INPUT;
424 1
	if (count > 600)
425 0
		return ERR_NOT_IMPLEMENTED;
426
	// создать состояние
427 1
	state = blobCreate(beltFMT_keep(mod, count));
428 1
	if (state == 0)
429 0
		return ERR_OUTOFMEMORY;
430
	// зашифровать
431 1
	beltFMTStart(state, mod, count, key, len);
432 1
	memMove(dest, src, 2 * count);
433 1
	beltFMTStepE(dest, iv, state);
434
	// завершить
435 1
	blobClose(state);
436 1
	return ERR_OK;
437
}
438

439 1
err_t beltFMTDecr(u16 dest[], u32 mod, const u16 src[], size_t count,
440
	const octet key[], size_t len, const octet iv[16])
441
{
442
	void* state;
443
	// проверить входные данные
444 1
	if (count < 2 ||
445 1
		len != 16 && len != 24 && len != 32 ||
446 1
		!memIsValid(src, 2 * count) ||
447 1
		!memIsNullOrValid(iv, 16) ||
448 1
		!memIsValid(key, len) ||
449 1
		!memIsValid(dest, 2 * count) ||
450 1
		iv && !memIsDisjoint2(dest, 2 * count, iv, 16))
451 0
		return ERR_BAD_INPUT;
452 1
	if (count > 600)
453 0
		return ERR_NOT_IMPLEMENTED;
454
	// создать состояние
455 1
	state = blobCreate(beltFMT_keep(mod, count));
456 1
	if (state == 0)
457 0
		return ERR_OUTOFMEMORY;
458
	// зашифровать
459 1
	beltFMTStart(state, mod, count, key, len);
460 1
	memMove(dest, src, 2 * count);
461 1
	beltFMTStepD(dest, iv, state);
462
	// завершить
463 1
	blobClose(state);
464 1
	return ERR_OK;
465
}

Read our documentation on viewing source code .

Loading