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
— алдыңғы псевдокездейсоқ сан.
