Учбово-методичний посібник для виконання лабораторних робіт з дисципліни „Основи теорії криптографії і криптоаналізу”, страница 22

Інші дослідники розширили ідеї Бояр, розробивши способи розкриття будь-якого поліноміального генератора. Були зламані й усічені лінійні конгруентні генератори, і усічені лінійні конгруентні генератори з невідомими параметрами.

Табл. 5.1. Константи для лінійних конгруентних генераторів

Переповняються при	a	b	m
220	106	1283	6075
221	211	1663	7875
222	421	1663	7875
223	430	2531	11979
	936	1399	6655
	1366	1283	6075
224	171	11213	53125
	859	2531	11979
	419	6173	29282
	967	3041	14406
225	141	28411	134456
	625	6571	31104
	1541	2957	14000
	1741	2731	12960
	1291	4621	21870
	205	29573	139968
226	421	17117	81000
	1255	6173	29282
	281	28411	134456
227	1093	18257	86436
	421	54773	259200
	1021	24631	116640
	1021	25673	121500
228	1277	24749	117128
	741	66037	312500
	2041	25673	121500
229	2311	25367	120050
	1807	45289	214326
	1597	51749	244944
	1861	49297	233280
	2661	36979	175000
	4081	25673	121500
	3661	30809	145800
230	3877	29573	139968
	3613	45289	214326
	1366	150889	714025
231	8121	28411	134456
	4561	51349	243000
	7141	54773	259200
232	9301	49297	233280
	4096	150889	714025
233	2416	374441	1771875
234	17221	107839	510300
	36261	66037	312500
235	84589	45989	217728

1.5.2.  Об'єднання лінійних конгруентних генераторів

Було зроблено ряд спроб об'єднання лінійних конгруентних генераторів. Криптографічна безпека отриманих результатів не підвищується, але вони мають більш довгі періоди і кращі характеристики в деяких статистичних тестах. [1] Для 32-бітових комп'ютерів можна використовувати наступний генератор:

static long s1=1;

static long s2=1;

inline long MODMULT (a, b, c, m, s)

{

q=s/a;

s=b*(s-a*q)-c*q;

if(s<0)s+=m;

}

double combinedLCG ()

{

long q;

long z;

MODMULT (53668,40014,12211,2147483563, s1);

MODMULT (52774,40692,3791,2147483399, s2);

z=s1-s2;

if(z<1)

z+=2147483562;

return z*4.656613e-10;

}

void initLCG (long InitSl, long InitS2)

{

s1=InitS1;

s2=InitS2;

}

Перемінні s1 і s2 глобальні і містять поточний стан генератора. Перед першим викликом їх необхідно проініціалізувати. Для перемінної s1 початкове значення повинне лежати в діапазоні між 1 і 2147483562, для перемінної s2 – між 1 і 2147483398. Період генератора близький до 10¹⁸. Константа b дорівнює 0.

1.5.3.  Регістри зрушення з лінійним зворотним зв'язком

Послідовності регістрів зрушення використовуються як у криптографії, так і в теорії кодування. [1]

Регістр зрушення з лінійним зворотним зв'язком складається з двох частин: регістра зрушення і функції зворотного зв'язку (див. мал. 5.1). Регістр зрушення являє собою послідовність бітів. (Кількість бітів визначається довжиноюрегістра зрушення. Якщо довжина дорівнює n бітам, то регістр називається n-бітовим регістромзрушення). Усякий раз, коли потрібно витягти бит, усі біти регістра зрушення зрушуються вправо на 1 позицію. Новий крайній лівий біт є функцією всіх інших бітів регістра. На виході регістра зрушення виявляється один, звичайно молодший значущий, біт. [6]

Визначення 5.3.1. Періодомрегістра зрушення називається довжина одержуваної послідовності до початку її повторення.

Найпростішим видом регістра зрушення із зворотним зв'язком є регістр зрушення з лінійним зворотним зв'язком (РЗЛЗЗ) (linear feedback shift register, або LFSR) (див. мал. 5.2). Зворотний зв'язок являє собою XOR (побітове додавання по модулю 2 деяких бітів регістра, послідовність цих бітів називається відвідною послідовністю(tab sequence). Іноді такий регістр називається конфігурацією Фібоначчі. Через простоту послідовності зворотного зв'язку для аналізу РЗЛЗЗ можна використовувати досить розвинуту математичну теорію. РЗЛЗЗ частіше інших регістрів зрушення використовуються в криптографії. [6]

На мал. 5.3 показаний 4-бітовий РЗЛЗЗ із відводом від першого і четвертого бітів. Якщо його проініціалізувати значенням 1111, то до повторення регістр буде приймати наступні внутрішні стани: