А. Ж. Асамбаев криптография негіздері

 
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. 
Көрініп  тұр,  генерацияланған  сандар  тізбегі  кездейсоққа  сырттай  ұқсайды. 
Шынында да, зерттеуден белгілі, алынған кездейсоқ сандардың статистикалық қасиеттері 
жақсы. 

 
71 
Кешігуі  бар  Фибоначчи  әдісі  бойынша  құрастырылған  генераторлар  үшін 
ұсынылған  a  және  b  параметрлер  бар.  Мысалы,  зерттеушілер  келесі  мәндерді  ұсынады:  
(a,b) = (55, 24),  (17, 5)  немесе  (97,33). Алынған кездейсоқ сандардың сапасы  a константа 
мәніне тәуелді:  ол неғұрлым үлкен болса, кездейсоқ векторлар сақталынатын кеңістіктің 
өлшемі  соғұрлым  жоғары  болады.  Сонымен  бірге,  a  константаның  өсуімен  алгоритм 
пайдаланатын жад көлемі де өседі.  
Нәтижесінде (a,b) = (17,5) мәндері қарапайым қосымшалар үшін ұсынылады. (a,b) 
=  (55,24)  мәндері  көптік  криптографиялық  алгоритмдарға  қанағаттанған  сандарды  алуға 
мүмкіндік береді. (a,b) = (97,33) мәндері өте сапалы кездейсоқ сандарды алуға мүмкіндік 
береді  және  жоғары  өлшемі  бар  кездейсоқ  векторлармен  істейтін  алгоритмда 
пайдаланады.  
Кешігуі  бар  Фибоначчи  әдісіне  негізделген  ПКС  генераторы  криптографияда 
пайдаланған  болатын.  Одан  басқа,  олар  математикалық  және  статистикалық  есептерде 
қолданылады,  және  де  кездейсоқ  процестерді  модельдеуде.  Кешігуі  бар  Фибоначчи 
әдісіне негізделген ПКС генераторы танымал Matlab жүйеде пайдаланған. 
 
7.5 BBS алгоритм негізіндегі кездейсоқ сандар генераторы 
 
BBS  алгоритмы  (авторлар  аттарынан  —  L.Blum,  M.Blum,  M.Shub)  немесе 
квадратты қалдығы бар генераторы деп аталатын псевдокездейсоқ сандарды генерациялау 
алгоритмы  кең  тараған.  Криптография  мақсаты  үшін  бұл  әдіс  1986  жылы  ұсынылған 
болатын. 
Осы  әдісте,  алдымен  екі  үлкен  жай  сандар  p  мен  q  таңдап  алынады.  p  мен  q 
сандары  модулі  4  бойынша  3-пен  салыстырмалы  болу  керек,  яғни  p  мен  q-ны  4-ке 
бөлгенде  бірдей  қалдығы  3  алыну  керек.  Онан  әрі  M  =  p q  саны  есептеледі,  оны  бүтін 
Блюм саны деп атайды. Сосын М-мен өзара жай (яғни бірден басқа ортақ бөлгіштері жоқ) 
басқа кездейсоқ бүтін сан х таңдап алынады. Есептейміз х
0
 = х
2 
mod M. х
0 
– генератордың 
бастапқы саны деп аталады.  
Генератор  жұмысының  әрбір  n  қадамында  есептеледі  х
n+1 
=  х
n
2
  mod  M.  n-ші 
қадамның  нәтижесі  х
n+1 
санның  бір  (әдетте  кіші)  биты  болып  табылады.  Кейде  нәтиже 
ретінде жұптық битын қабылдайды, яғни элементтің екілік түріндегі бірліктер саны. Егер 
сан жазуында бірліктер саны жұп болса  - жұптық  битын 0-ге тең деп алады, тақ болса  - 
жұптық битын 1-ге тең деп қабылдайды.  
Мысалы, p = 11, q = 19 болсын (көз жеткендей,  11 mod 4 = 3, 19 mod 4 = 3). Онда 
M  =  p q  =  11 19  =  209.  М-мен  өзара  жай  х  таңдап  аламыз:  х  =  3  болсын.  Генератордың 
бастапқы саның х
0 
есептейік: 
х
0
 = х
2
 mod M = 32 mod 209 = 9 mod 209 = 9. 
BBS алгоритмы бойынша алғашқы он  х
i
 санды есептейік. Кездейсоқ бит ретінде  х
i
 
санның екілік түріндегі жазуында кіші битты аламыз:  
 
х
1 
= 9
2
 mod 209 = 81 mod 209 = 81 
кіші бит: 1 
х
2 
= 81
2
 mod 209 = 6561 mod 209 = 82 
кіші бит: 0 
х
3 
= 82
2
 mod 209 = 6724 mod 209 = 36 
кіші бит: 0 
х
4 
= 36
2
 mod 209 = 1296 mod 209 = 42 
кіші бит: 0 
х
5 
= 42
2
 mod 209 = 1764 mod 209 = 92 
кіші бит: 0 
х
6 
= 92
2
 mod 209 = 8464 mod 209 = 104 
кіші бит: 0 
х
7 
= 104
2
 mod 209 = 10816 mod 209 = 157  кіші бит: 1 
х
8 
= 157
2
 mod 209 = 24649 mod 209 = 196  кіші бит: 0 
х
9 
= 196
2
 mod 209 = 38416 mod 209 = 169  кіші бит: 1 

 
72 
х
10 
= 169
2
 mod 209 = 28561 mod 209 = 137 кіші бит: 1 
 
Тәжірибелік мақсаты үшін осы әдістің ең қызық қасиеті - тізбектін n-ші саның алу 
үшін  барлық  х
i
  санның  n  бұрыңғыларын  есептеу  қажет  емес.  Өйткені  мына  формула 
бойынша х
n
 тура алуға болады: 
M
x
x
q
p
n
n
mod
)]
1
)(
1
mod[(
2
0
 
Мысалы,  х
10
-нан
  
тура  х
0
-ды есептейік: 
137
209
mod
14976
209
mod
)
104
144
(
)
209
mod
42
)(
209
mod
26
(
)
209
mod
)
81
)((
209
mod
)
81
((
)
209
mod
81
)(
209
mod
81
(
209
mod
81
209
mod
)
9
(
209
mod
9
209
mod
209
mod
4
5
4
4
5
3
16
15
31
31
4
124
180
mod
1024
0
)]
1
19
)(
1
11
mod[(
2
0
10
10
x
x
x
 
 
Нәтижесінде,  шынында  да  рет-ретімен  есептегендей  мән  аламыз  -  137.  Есептеу 
күрделі  болып  көрінеді,  бірақ  оларды  кішкентай  процедура  немесе  программа  түрінде 
орындап, қажет болғанда пайдалануға болады.  
х
n
-ды  «тура»  алу  мүмкіндігі  BBS  алгоритмды  ағынды  шифрлауда  пайдалануға 
мүмкіндік  береді,  мысалы,  еркін  қатынауы  бар  файлдар  үшін  немесе  деректер  қорына 
жазулары бар файл фрагменттері үшін.  
BBS алгоритмның қауіпсіздігі үлкен М санды көбейткіштерге жіктеу күрделілігіне 
негізделген. Егер М жеткілікті үлкен болса, оны құпиялы түрде сақтаудың қажеті де жоқ; 
М-ды көбейткіштерге жіктемей ПКС генератордың шығыуын ешкім айталмайды. Себебі, 
n  = pq  (р  мен  q —  жай сандар) түрлі  сандарды көбейткіштерге жіктеу  өте қиын, егер біз 
тек  n-ды  ғана  білсек,  ал  р  мен  q  —  бірнеше  ондаған  немесе  жүздеген  биттен  тұратын 
үлкен сандар болса (бұл факторизациялау деп аталатын есеп).  
Одан  басқа,  BBS  генераторы  генерацияланған  кейбір  тізбекті  біле  отырып, 
қаскүнем не бұрыңғы не келесі биттерді анықтай алмайды. BBS генераторды сол жақ және 
оң жақ бағытта алдын ала болжауға болмайды. Бұл қасиеті криптография мақсатына өте 
пайдалы. 
Алгоритмның  ең  маңызды  кемшілігі  –  аса  жылдамды  еместігі,  сондықтан  оны 
нақты  уақыт  есептеуде  және  де,  өкінішке  орай,  ағынды  шифрлауда  пайдалануға 
болмайды. 
Дегенмен, бұл алгоритм үлкен периоды бар псевдокездейсоқ сандардың шынында 
жақсы тізбегін бергендіктен, оны шифрлауда кілттерді генерациялау үшін пайдалану жөн.  
 
 
Негізгі ұғымдар 
 
Stream cipher – ағынды шифр. 
BBS  алгоритмы  –  псевдокездейсоқ  сандарды  генерациялау  әдістерінің  біреуі. 
Алгоритм  аты  авторлар  есімдерінен  жиналған  -  L.Blum,  M.Blum,  M.Shub.  Алгоритм 
криптографияда  пайдалану  мүмкін.  BBS  алгоритмы  бойынша  келесі  x
n+1
  санды  есептеу 
үшін  пайдаланатын  формула:  х
n+1 
=  х
n
2
  mod  M,  мұнда  M  =  pq  екі  үлкен  p  мен  q  жай 
сандардың көбейтіндісі. 
Псевдокездейсоқ  сандар  генераторы  (ПКСГ)  –  сырттан  кездейсоққа  ұқсайтын 
биттер тізбегін жасайтын кейбір алгоритм немесе құрылғы.  
Псевдокездейсоқ  сандардың  сызықты  конгруэнтті  генераторы  -  ең  қарапайым 
генератордың біреуі, келесі k
i
 есептеу үшін  k
i 
= (a k
i-1
+b) mod c  формуланы пайдаланады, 
мұнда  а, b, с — кейбір константалар,  ал k
i-1
 — алдыңғы псевдокездейсоқ сан. 

 
73 
Кешігуі  бар  Фибоначчи  әдісі  -  псевдокездейсоқ  сандарды  генерациялау 
әдістерінің біреуі. Криптографияда пайдалану мүмкін. 
Ағынды  шифр  -  кіру  хабардың  шифрлауын  бір-бірден  биттер  (немесе  байттар) 
бойынша  операцияда  орындайтын  шифр.  Ағынды  шифрлау  алгоритмы  хабарды  бүтін 
сандар  блоктарға  бөлуді  қажет  етпейді.  Ағынды  шифрлар  нақты  уақытта  деректерді 
шифрлау үшін пайдаланады. 
 
 
Сұрақтар 
 
1. Блокты шифрдан ағынды шифрдың айырмашылығы неде? 
2. Айнымалы ұзындығы бар деректер ағынның шифрлауы қалай орындалады? 
3. Қандай сандар «псевдокездейсоқ» деп аталады? 
4.  Криптографиялық  мақсатта  пайдалану  үшін  псевдокездейсоқ  сандар 
генераторында қандай қасиеттері болу керек? 
5. Қандай псевдокездейсоқ сандар генераторын Сіз айтып бере аласыз? 
6. 
Псевдокездейсоқ 
сандар 
генераторлардын 
негізгі 
сипаттамаларын, 
артықшылықтарын және кемшіліктерін айтып беріңіз. 
 
 
Жаттығулар 
 
1.  Сызықты  конгруэнтты  ПКС  генератордың  алғашқы  он  сандар  тізбегін  және 
периодын түрлі параметрлер а, b және c (k
0
-ді 0-ге тең деп алыңыз) үшін анықтаңыз: 
 
а = 5,  b = 7  және  c = 17; 
 
а = 6,  b = 3  және  c = 23. 
 
2.  Кешігуі  бар  Фибоначчи  әдісімен  генерацияланған  k
а
-дан  басталатын  он  саннан 
тұратын тізбекті есептеңіз. Бастапқы мәліметтер:  
 
a = 3,  b = 1,  k
0 
= 0.6;  k
1 
= 0.3;  k
2 
= 0.5; 
 
a = 4,  b = 2,  k
0 
= 0.9;  k
1 
= 0.3;  k
2 
= 0.5;  k
3 
= 0.9. 
 
3. Сызықты конгруэнтты генераторы көмегімен алынған мәндер k
0
, k
1
, k
2
, k
3 
тең: k
0
 
= 1, k
1
 = 12, k
2
 = 3, k
3
 = 6. ПКС генератордың параметрлерін а, b және c табыңыз. 
 
4. Псевдокездейсоқ сандарды генерациялау BBS әдісі бойынша х
11 
есептеңіз, егер p 
= 11, q = 19, х = 3. 
 
 
 
 
 
8 
АҒЫНДЫ ШИФРЛАР ЖӘНЕ ПСЕВДОКЕЗДЕЙСОҚ САНДАРДЫҢ 
ГЕНЕРАТОРЛАРЫ
 
2 
бөлім

жүктеу/скачать 2,01 Mb.

Достарыңызбен бөлісу: