69
ПКГС ағынды шифрларда кілттер генераторлар ретінде пайдалану мүмкін.
Псевдокездейсоқ сандар генераторын пайдалану мақсаты салыстырмалы кішкене кілт
ұзындығы бар болғанда «шексіз» кілттік сөзді алу. Псевдокездейсоқ сандар генераторы
кездейсоққа ұқсайтын биттер тізбегін жасайды. Шынында, осындай тізбектер белгілі бір
ереже бойынша есептеледі және кездейсоқ болмайды, сондықтан олар жіберуші мен
алушы жағында да дәл қайталану мүмкін. Егер кілттер генераторы қосылған кезде бірдей
биттер тізбегін жасайтын болса, онда осындай жүйені бұзу оңай. Олай болса, ағын кілттер
генератордың шығысы кілт функциясы болу керек. Бұл жағдайда шифрлау кезіндегі
пайдаланған кілтті білгенде ғана хабарларды ашып оқуға болады.
Криптографиялық мақсатта пайдалану үшін псевдокездейсоқ сандар генератордың
келесі қасиеттері болу керек:
1. тізбек периоды өте үлкен болу керек;
2. жасалынатың тізбек нағыз кездейсоққа өте жақын болу керек;
3. түрлі мәндерді жасау ықтималдықатры дәл тең болу керек;
4. тек заңды алушы ғана хабарды ашып оқу үшін, кілттік биттер ағынды k
i
алған
кезде кейбір құпиялы кілтті пайдалану және еске алу керек.
Айтылған қасиеттер бар болғанда псевдокездейсоқ сандар тізбегі ағынды
шифрларда пайдалану мүмкін.
7.3 Псевдокездейсоқ сандардың сызықты конгруэнтті генераторы
Псевдокездейсоқ сандардың генераторы әртүрлі алгоритм бойынша жұмыс істеу
мүмкін. Ең қарапайым генератордың біреуі сызықты конгруэнтті генераторы, ол келесі
k
i
есептеу үшін
k
i
= (a k
i-1
+ b) mod c,
формуланы пайдалайды, мұндағы а, b, с — кейбір константалар, ал k
i-1
— алдыңғы
псевдокездейсоқ сан.
k
1
мәнің алу үшін бастапқы k
0
мәні беріледі.
Мысал ретінде алайық a=5, b=3, c=11 және k
0
=1 болсын. Бұл жағдайда жоғары
келтірілген формула арқылы біз 0 ден 10-ға дейін мәндер алаламыз (себебі c=11).
Тізбектің бірнеше элементтерін есептейік:
k
1
= (5 1 + 3) mod 11 = 8;
k
2
= (5 8 + 3) mod 11 = 10;
k
3
= (5 10 + 3) mod 11 = 9;
k
4
= (5 9 + 3) mod 11 = 4;
k
5
= (5 4 + 3) mod 11 = 1.
Алынған мәндер (8, 10, 9, 4, 1) кездейсоқ сандарға ұқсайды. Бірақ, келесі мән k
6
қайтадан 8-ге тең болады:
k
6
= (5 1 + 3) mod 11 = 8,
ал k
7
және k
8
мәндері 10 мен 9 сәйкес тең болады:
k
7
= (5 8 + 3) mod 11 = 10;
k
8
= (5 10 + 3) mod 11 = 9.
Сонымен, біздің псевдокездейсоқ сандар генераторымыз периодтық сандарды 8, 10,
9, 4, 1 жасай отырып қайталанады.
Өкінішке орай, бұл қасиет барлық сызықты конгруэнтті генераторларға сипатты.
Негізгі параметрлер мәнің a, b және c өзгертіп, период ұзындығына және k
i
мәндеріне әсер
етуге болады. Мысалы, с санның өсуі жалпы жағдайда период өсуіне келтіреді. Егер a, b
және c параметрлер дұрыс таңдап алынса, онда генератор максимал с периоды бар
кездейсоқ сандарды туғызып отырады. Бағдарламалық жүзеге асырғанда, с мәні әдетте 2
b-1
немесе 2
b
тең болып қойылады, мұнда b — сөз ұзындығы, бит.
70
Псевдокездейсоқ сандардың сызықты конгруэнтті генераторлардың артықшылығы
оның оңайлығы және псевдокездейсоқ мәнің алудың жоғары жылдамдығы. Сызықты
конгруэнтті генераторлар модельдеу және математикалық статистика есептерді шешу
үшін қолданылады, бірақ криптографиялық мақсатта оларды пайдалануға ұсынуға
болмайды, себебі криптоталдау мамандары ПКС тізбегін бірнеше мәні арқылы қалпына
келтіруді үйренген.
Мысалы, қарсылас k
0
, k
1
, k
2
, k
3
мәндерін анықтай алсын. Онда:
k
1
= (a k
0
+ b) mod c
k
2
= (a k
1
+ b) mod c
k
3
= (a k
2
+ b) mod c
Осы үш теңдеуден тұратын жүйені шешіп, a, b және c табуға болады.
Псевдокездейсоқ сандарды алу үшін квадраттық және кубтық генераторлар:
k
i
= (a
1
2
k
i-1
+ a
2
k
i-1
+ b) mod c
k
i
= (a
1
3
k
i-1
+ a
2
2
k
i-1
+ a
3
k
i-1
+ b) mod c
ұсынған болатын. Бірақ оларды да «алдын ала білу» себебінен криптографияда
пайдалануға болмайды.
7.4 Кешігуі бар Фибоначчи әдісі
Псевдокездейсоқ сандарды алудың басқа да схемалары бар.
Кешігуі бар Фибоначчи әдісі (Lagged Fibonacci Generator) — псевдокездейсоқ
сандарды генерациялау әдістерінің біреуі. Ол псевдокездейсоқ сандардың жоғары
«сапасын» алуға мүмкіндік береді. Фибоначчи датчиктерде нақты сандармен
арифметикалық операциялардың жылдамдығы бүтін санды арифметика жылдамдығымен
тең болғандықтан, олар жиі пайдаланады.
Фибоначчи датчиктің ең кең таралғанның біреуі келесі рекуррентты формулаға
негізделген:
b
i
a
i
b
i
a
i
b
i
a
i
b
i
a
i
i
k
k
åãåð
k
k
k
k
åãåð
k
k
k
,
1
,
мұндағы k
i
— [0,1] диапазондағы нақты сандар; a, b — оң бүтін сандар, генератор
параметрлері. Жұмыс үшін Фибоначчи датчигіне бұрыңғы генерацияланған кездейсоқ
сандарды max{a,b} білу қажет. Бағдарламалық жүзеге асыруда генерацияланған кездейсоқ
сандарды сақтау үшін a мен b параметрлерге тәуелді белгілі бір жад көлемі қажет болу
керек.
Мысал. Кешігуі бар Фибоначчи әдісі арқылы генерацияланатын алғашқы он
сандар тізбегін есептейік. Келесі бастапқы мәілметтерде a = 4, b = 1, k
0
=0.1; k
1
=0.7; k
2
=0.3;
k
3
=0.9; k
4
=0.5 бастаймыз k
5
-тен:
k
5
= k
1
- k
4
= 0.7 - 0.5 = 0.2;
k
6
= k
2
- k
5
= 0.3 - 0.2 = 0.1;
k
7
= k
3
- k
6
= 0.9 - 0.1 = 0.8;
k
8
= k
4
- k
7
+ 1 = 0.5 - 0.8 + 1 = 0.7;
k
9
= k
5
- k
8
+ 1 = 0.2 - 0.7 + 1 = 0.5;
k
10
= k
6
- k
9
+ 1 = 0.1 - 0.5 + 1 = 0.6;
k
11
= k
7
- k
10
= 0.8 - 0.6 = 0.2;
k
12
= k
8
- k
11
= 0.7 - 0.2 = 0.5;
k
13
= k
9
- k
12
+ 1 = 0.5 - 0.5 + 1 = 1;
k
14
= k
10
- k
13
+ 1 = 0.6 - 1 + 1 = 0.6.
Көрініп тұр, генерацияланған сандар тізбегі кездейсоққа сырттай ұқсайды.
Шынында да, зерттеуден белгілі, алынған кездейсоқ сандардың статистикалық қасиеттері
жақсы.
Достарыңызбен бөлісу: |
