Кездейсоқ сандар генераторы

Жұмыс түрі: Курстық жұмыс
Тегін: Антиплагиат
Көлемі: 27 бет
Таңдаулыға:

1 Кездейсоқ сандарды генерациялау

1.1 Ақиқат кездейсоқ сандар және олрды қолданудың мәселелері

Кілтті генерациялау үшін бізге кездейсоқ сандарды генерациялауыш
(random number generator - RNG) керек. Жақсы кездейсоқтықтың генерациясы –
расында да көптеген криптографиялық операциялардың ең қажетті және сонымен
қатар аса ауыр бөліктерінің бірі.
Біз кездейсоқтықтың өзімен расында нені білдіретінін онша толық
қарастырмаймыз. Осы терминнің көптеген әдемі математикалық анықтамалары
бар, бірақ олардың бәрі бұл жобада қарастыру үшін өте ауыр. Ал формальсыз
емес жағынан егер де қолданушы кездейсоқтықпен күресу үшін белсенді
әрекеттер қолданатын болса да, кездейсоқтықты қаскүнем үшін болжамсыз
мәліметтер мәндері ретінде анықтауға болады.
Көптеген криптографиялық функцияларға жақсы кездейсоқ сандардың
генераторлары керек. Біз А және Б қолданушыларға белгілі кілт бар деп
жорамалдадық. Бұл кілт бір жерде шығарылу керек. Кілттерді таңдау үшін
кілттерді басқару жүйесі кездейсоқ сандардың генераторын қолданады. Егер
генератор онша мықты болмаса, нашар кілт алынады. Тап осы жағдай Netscape
шолушысының ерте нұсқаларының бірінде болды.
Кездейсоқтықтың өлшемі энтропия (entropy) деп аталады. Мен бұл жерде
осы сұрақтың математикалық бөліктерін келтіріп жатпаймын, жай ғана
энтропияның не екенін түсіндіру үшін барлығын жасауға тырысамын. Егер бізде
мүлде кездейсоқ түрмен таңдалатын 32-биттік сөз болса, онда оның 32 бит
энтропиясы болады. Егер де 32-биттік сөз әрқайсысының шығу ықтималдығы 25%-
ға тең тек 4 мән қабылдай алатын болса, онда бұл сөз тек 2 бит энтропияға
ие болады. Энтропия мәндегі биттің санын емес, осы мәнде сіздің қаншаға
сенімсіз екендігіңізді көрсетеді. Көбірек суреттеу үшін энтропияны қысудың
тамаша алгоритімін қолдану кезінде мәнді беру үшін керек биттің орташа саны
ретінде қарастыруға болады. Назар аударыңыздар, мәннің энтропиясы осы мән
туралы қанша білетініңізге байланысты. 32-биттік кездейсоқ сөздің 32 бит
энтропиясы бар. Енді осы сөздің мәні туралы келесілер нақты белгілі деп
қарастырайық: сөздің 18 биті 0-ге тең, ал 16 бит – 1-ге тең. Бұндай
талаптарға жуықтап 228,8 мән қанағаттандырады, осыдан шығатыны, сөздің
энтропиясы тек 28,8 битті құрайды. Басқа сөзбен айтқанда, неғұрлым мән
туралы көбірек білсек, соғұрлым оның энтропиясы аз болады.
Кездейсоқ үлестірілуі бір қалыпты болмайтын мәндер үшін энтропияны
есептеп шығару біраз қиындау. Х айнымалысының энтропиясын анықтаудың ең кең
тараған түрі келесі түрде құралады:

мұндағы Р(Х=х) – Х айнымалысының х мәнін қабылдау ықтималдығы. Біз бұл
формуланы қолданбаймыз, сондықтан оны есте сақтаудың керегі жоқ. Энтропия
туралы айтқанда математиктер тап осы анықтамаға жүгінеді. Математикада
энтропияның тағы да бірнеше анықтамалары бар; ғалымдардың анықтаманың не
ананы, не мынаны таңдауы ғалымның нақты немен айналысатынына байланысты.
Және біздің энтропияны физикадағы нақты термодинамикаға жататын энтропиямен
шатастырмаңдар.
Тамаша әлемде ақиқат кездейсоқ сандарды қолданған дұрыс болар еді.
Өкінішке орай, біздің әлем тамаша емес және онда шындығында кездейсоқ
мәліметтер табу өте қиын.
Кәдімгі компьютерлерде энтропияның бірнеше көздері бар. Осындай
көздердің мысалы ретінде көбінесе перненің дәл басылу уақыты мен тышқанның
орын ауыстыруының дәл уақыты келтіріледі. Кезінде кейбір ғалымдар қатты
дискіге жету уақытының оның корпусының ішіндегі турбуленттікпен шақырылған
тербелістерінің кездейсоқтығына зертеулер жүргізген. Осы барлық
энтропиялардың көздері күмән туғызады, өйткені кейбір нақты жағдайларда
қаскүнем кездейсоқтықтың көзінің үстінен есептеулер жүргізуі немесе осы
көзге әсер етуі мүмкін.
Көптеген өңдеушілер әр түрлі көздерден алынуы мүмкін энтропияның
санына оптимистік көзбен қарайды. Біз перненің бір басылуы кезінде уақытқа
байланысты 1-2 байт кездейсоқ мәліметтерді шығарған бағдарламалық
қамтамасыздандырылуды көрдік. Өкінішке орай, біз бұл оптимистікпен
келіспейміз. Перненің кәсіби машинстпен басылу уақытын бірнеше
миллисекундқа дейінгі дәлдікпен болжауға болады. Ал перненің басылу уақытын
өлшеуге болатын пернетақтаны сканерлеу жиілігін дәлдік шектейді. Басылып
жатқан мәліметтерді де, тіпті қолданушы жай ғана бірінші кездескен
пернелерді басатын болса, кездейсоқтық деп атауға болмайды. Одан әрі
жаманы, әрқашан қаскүнемде кездейсоқ оқиғалар туралы қосымша ақпараттың
бар болуының қаупі болады. Пернені басқан кезде шығатын дыбыстарды әрбір
перненің басылу уақытын анықтауға мүмкіндік беретіндіктен микрофонға жазып
алуға болады. Энтропияның ана не мына мәліметтерде бар санын бағалағанда
өте сақ болыңыздар. Анығында, біз өте ақылды және белсенді қаскүнеммен
кездесіп отырмыз.
Өзін кездейсоқ түрде ұстайтын көптеген физикалық процестер бар.
Мысалы, кванттық физиканың заңдары бойынша кейбір бөлшектердің жүрісі толық
кездейсоқтық болып табылады. Осы кездейсоқ жүрісті өзіміздің жүйеде қолдану
үшін есептеп шығарсақ жақсы болар еді. Техникалық жағынан бұл әрине мүмкін.
Өкінішке орай, қаскүнемдерде бұл жерде де өздерінің жолдары болады.
Біріншіден, ол болжанатындай етіп кванттық бөлшектердің жүрісіне ықпал
тигізуі мүмкін. Екіншіден, ол жай ғана біздің өлшеулерді ұрлап кете алады.
Егер қаскүнем өлшеулерді алатын болса, онда мәліметтер бәрібір кездейсоқ
болып қалады, бірақ, оның ойынша, ешқандай да энтропияға ие болмайды (егер
қаскүнем дәл мәнді білетін болса, онда ол мән оған энтропия болып
саналмайды). Мүмкін, қаскүнем біздің құралдардың көрсетулерін өзгертетін
күшті радиосәуле шығара алады. Тіпті біз кванттық физиканың заңдарын
қолданатын бірнеше шабуылдарды суреттей аламыз. Мысалы, біз өлшейін деп
жатқан кездейсоқтықты бұзу үшін Эйнштейн-Подольский-Розен породоксы
қолданылуы мүмкін. Осыған ұқсас пікірлер энтропияның басқа да көздеріне,
мысалы, резистордың жылу кедергілері немесе жартылай өткізгіштіктік
стабилитрондағы туннел әсері қолданылады.
Кейбір қазіргі заманғы компьютерлерде енгізілген ақиқат кездейсоқ
сандардың генераторлары бар. Бұл, сөзсіз оларға жеке генераторларды қолдану
алдында түбегейлі артықшылықтар береді, өйткені, кейбір шабуылдардың кейбір
түрлерінің орындалуына айтарлықтай кедергі жасайды. Әйтсе де мұндай
кездейсоқ сандар генераторы әлі де операциялық жүйеге қол жетерліктей
болады, сондықтан қосымшалар қауіпсіз мәліметтер алу үшін оған толық сенуі
керек.
Ақиқат кездейсоқ сандарды алудың қиындығынан басқа, оларды практикада
қолданудың басқа да бірнеше мәселелері бар. Біріншіден, олар әрқашан қол
жететіндей болмайды. Егер кездейсоқ сандар пернені басу уақытының негізінде
шығарылатын болса, қолданушы кенеттен жазуды тоқтататын болса, сіз ешқандай
мәлімет алмайсыз. Егер сіздің қосымшаңыз пернетақтасы жоқ компьютерге
орнатылған Web-сервер болатын болса, бұл нағыз мәселе болуы мүмкін. Осыған
ұқсас тағы бір мәселе ақиқат кездейсоқ сандардың көлемі әрқашан
шектеулілігімен байланысты. Егер сізге үлкен көлемді кездейсоқ сандар керек
болса, көптеген қосымшаларға мүлде қолайсыз болатын олар шығарылғанша
тосуға тура келеді.
Екінші мәселе кездейсоқ сандардың физикалық генераторлары секілді
ақиқат кездейсоқ сандардың көздері сынып қалуы немес бет қайтару
мүмкіндігінде. Кей кездерде генератордың іс-әрекеті болжамды болуы мүмкін.
Өйткені ақиқат кездейсоқ сандардың генераторы күрделірек, олар компьютердің
классикалық компоненттеріне қарағанда тез істен шығуы мүмкін. Егер сіздің
жүйеңіз ақиқат кездейсоқ сандардан тікелей тәуелді болса, ол бет қайтарған
уақытта сіздің жолыңызда үлкен кедергілер болады.
Және үшінші мәселе – ол нақты физикалық оқиғалардан алына алатын
энтропиияның бағалану қиындығы. Бірақ егер кездейсоқ сандардың генераторы
ретінде белгіленген, арнайы осыған жасалған құрал қолданылмайтын болса,
алынып жатқан энтропияның санын анықтау өте қиын болады.

1.2 Жалғанкездейсоқ сандар және оларды қолданудың мәселелері

Ақиқат кездейсоқ сандардың орнына жақсы құрал ретінде жалғанкездейсоқ
сандар қолданылады. Шындығында, жалғанкездейсоқ сандар жалпы кездейсоқ
болып саналмайды. Олар детерминантты алгоритмнің көмегімен кейбір бастапқы
сандардың (seed) негізінде табылады. Бастапқы санды біле отырып келесі
барлық жалғанкездейсоқ сандарды болжауға болады. Классикалық
жалғанкездейсоқ сандардың генераторлары (pseudorandom number generator -
PRNG) ақылды қаскүнемнен ешқалай сақтандырылмаған. Олар шабуылдарды тоқтату
үшін емес, статистикалық бұрмалауларды жою үшін жасалынған. Дональд Кнуттың
(Donald Knuth) The Art of Computer Programming кітабының екінші томында
кездейсоқ сандардың генераторларының толық суреттемесі жазылған, бірақ
олардың барлығы статистикалық кездейсоқтыққа қатысты зерттелген. Біз
қарсыластың кездейсоқ сандардың шығаруына қолданылатын алгоритмді
білетіндігінен бастауымыз керек. Алгоритммен шығарылған бірнеше
жалғанкездейсоқ сандарды біле отырып қаскүнем кейбір алдыңғы (немесе
өткендегі) кездейсоқ сандардың биттерін болжай ала ма? Көптеген классикалық
жалғанкездейсоқ сандардың генераторлары үшін жауап ақиқат болуы мүмкін.
Жалғанкездейсоқ сандардың криптографиялық генераторларына бұл мүмкін емес
жағдай.
Криптографиялық жүйенің контексінде жалғанкездейсоқ сандардың
генераторларына одан да гөрі қатаң сұранымдар келтіріледі. Егер қаскүнем
генератормен құрылған кездейсоқ сандардың толық қатарын білетін болса да,
ол онда қалған кездейсоқ сандар туралы қандай да бір ақпаратты болжауға
мүмкіндігі болмауға тиіс. Біз бұндай жалғанкездейсоқ сандардың
генераторларын криптографикалық мықты деп атаймыз. Жалғанкездейсоқ
сандардың классикалық генераторлары керегі жоқ болғандықтан, әрі қарай біз
тек криптографикалық мықты генераторлар туралы айтатын боламыз.
Сіздің бағдарламалық кітапханаңызда бар жай кездейсоқ функцияларды
ұмытыңыздар. Олардың біреуі де криптографиялық жүйелерде қолдануға
жарамайды. Көптеген бағдарламалық кітапханалар жеңіл статистикалық
тесттерден де өте алмайтын жалғанкездейсоқ сандардың генераторларымен
беріледі. Ешқашан, егер құжаттамасында олар криптографиялық мықты деп
жазылмаған болса, кітапханалық генераторларды қолданбаңыздар.

1.3 Ақиқат кездейсоқ сандар және жалғанкездейсоқ сандардың
генераторлары.

Ақиқат кездейсоқ сандарды біз тек жалғанкездейсоқ сандардың
генераторларына кіріс беретін бастапқы сандарды табу үшін ғана қолданамыз.
Бізде бастапқы сан табылғаннан кейін генератор өмірге кездейсоқ (толығырақ
жалғанкездейсоқ) сандардың кез-келген санын шығара алады. Керек болған
жағдайда біз ақиқат кездейсоқ сандарды кездейсоқ сандардың генераторының
бастапқы санына қоса аламыз. Бұл, егер қаскүнем қандай да бір түрмен
бастапқы санды біліп алған болса да, ақырғының шығыс мәліметтері ешқашан
толық болжамды болмайтындығына кепілдік бере алады.
Ақиқат кездейсоқ сандар жалғанкездейсоқ сандардан гөрі жақсырақ деген
теориялық ой бар. Кейбір криптографиялық хаттамалар үшін ақиқат кездейсоқ
сандарды қолдану кезінде шабуылдың белгілі кейбір түрлері мүмкін
болмайтындығын дәлелдеуге болады. Мұндай хаттама сөзсіз қорғалған
(unconditionally secure) деп аталады. Егер де жалғанкездейсоқ сандардың
генераторларын қолданатын болсақ, хаттама қаскүнем бұл генераторды бұза
алмайды деген шарт болған жағдайда ғана қауіпсіз болады. Мұндай хаттама
есептеулер бойынша қорғалған (computationally secure) деп аталады. Бұл
айырмашылықтың толық білетін теоретиктер үшін ғана мағынасы болады. Барлық
криптографиялық хаттамалар көбіне арқашан есептеуіш жақындалуға
негізделген. Бұндай жақындалудың нақты бір шабуыл түріне байланысты
шығарылуы жақсы жақсаруға әкелмейді. Сонымен қатар, сөзсіз сақталуды
қамтамасыз етуге қажетті ақиқат кездейсоқ сандардың шығаруы соншалықты
қиын, мұндай сандарды қолдану әрекеті жүйенің қауіпсіздігін тек бұзуы
мүмкін. Ақиқат кездейсоқ сандардың генераторының кез-келген нашар орны
қауіпсіздіктің жоғалуына әкеліп соғады. Басқа жағынан қарағанда, егер
ақиқат кездейсоқ сандарды жалғанкездейсоқ сандардың генераторына бастапқы
санды табу үшін ғана қолдансақ, онда өзімізге әр түрлі энтропиялардың
көздерін қолдануды жасай алу, сөзсіз, біздің расында да қауіпсіз жүйені
құруымыздың мүмкіндіктерін көтереді.

1.4 Жалғанкездейсоқ сандардың генераторына шабуылдардың моделдері.

Жалғанкездейсоқ сандардың генераторлары салыстырмалы аз зерттелген.
Кездейсоқ (жалғанкездейсоқ) сандардың генерациясының шарты кейбір бастапқы
санның негізінде біраз жеңіл. Мәселе кездейсоқ санды қайдан алу және оны
қалай құпия сақтауда болып отыр. Бұл мәселенің ең жақсы шешімі болып
қазіргі кезде бізге белгілісі Yarrow деп аталатын генераторы табылады. Бұл
белгілі шабуыл түрлерінен жүйені қорғауға тырысып жатқан жалғанкездейсоқ
сандардың генераторы бізбен Джон Келсимен (John Kelsey) бірге бірнеше жыл
бұрын жасалынып шығарылған.
Уақыттың әрбір сәтінде жалғанкездейсоқ сандардың генераторында ішкі
күйі бар. Кездейсоқ сандарды алудың сұранымдары жалғанкездейсоқ сандарды
генерациялайтын криптографиялық алгоритммен қызмет етіледі. Бұл алгоритм,
сонымен қатар, генератор келесі жолы осы кездейсоқ сандарды шығармауды
кепілдеу үшін генератордың ішкі күйін жаңартады. Бұл процесс онша қиын
емес; осы тапсырмаларды орындауды кез-келген кэштау функциясы немесе
блоктық шифр істей алады.
Жалғанкездейсоқ сандардың генераторларына шабуылдаудың әр түрлі
формалары бар. Бәрінен бұрын қаскүнем генератордың ішкі күйін оның шығыс
мәліметтеріне негізделе отырып құрғысы келіп тырысатын тура шабуылды атап
өту керек. Бұл қазіргі заманғы криптографиялардың әрекеттерін қолдана
отырып өте оңай қарсы тұруға болатын криптошабуылдың классикалық түрі.
Егер қаскүнем қандай да бір этапта генератордың ішкі күйін ала алатын
болса, жағдай нашарлайды. Қазір бізді оның қалай болатыны қызықтырмайды.
Мүмкін ақпарат шығысы бағдарламалық қамтамасыздандырудың қандайда бір
қателігінен, немесе компьютер бірінші рет жүктелгендіктен әлі кездейсоқ
бастапқы саны болған жоқ, немесе, айталық, қаскүнем бастапқы санның файлын
дискіден оқып алды. Барлық осы жағдайларда генератормен өте жаман нәрселер
бола бастайды. Егер қаскүнем жалғанкездейсоқ сандардың классикалық
генераторларының ішкі жағдайын біле алатын болса, ол барлық келесі шығыс
мәліметтерінің және барлық ішкі күйдің жаңартуларының мәндерін жүргізе
алады. Осыдан шығатыны, егер жалғанкездейсоқ сандардың генераторына
шабуылдың қандай да бір уақытта сәтті аяқталатын болса, бұл генератор
ешқашан қауіпсіз жағдайға келе алмайды.
Қаскүнемге ішкі күйі белгілі генератордың қауіпсіздігін қайта құру өте
қиын. Ол үшін ақиқат кездейсоқ сандарды генерациялауға болатын қандай да
бір энтропия көзі керек болады. Жеңілдік үшін бізде уақыттың болжамсыз
кезінде энтропияның керекті санын беретін бір немесе бірнеше көздер бар деп
есептейміз (әдетте оқиғалар деп атайтын бірнеше үлестер түрінде).
Тіпті егер біз генератордың ішкі күйін оқиғалардың шығуы кезінде пайда
болған энтропияның бірнеше санымен араластырсақ та, қаскүнемде әлі де
шабуыл жолдары болады. Ол генераторға кездейсоқ мәліметтерді алу туралы жиі
сұраныстар жібере алады. Осындай екі сұраныстың арасындағы уақыт аралығында
генератордың ішкі күйіне қосылатын энтропиялардың жалпы саны, айталық, 30
битпен шектелген болғандықтан қаскүнем жай ғана кездейсоқ кіріс
мәліметтерінің мүмкін нұсқаларын қолданып шыға алады және аралыстырудан
кейін алынған жаңа ішкі күйді анықтай алады. Бұл қазіргі заманғы
технологиялардың көмегімен мүмкін болатын 230 жуық қадам керек. Дұрыс
шешімді тапқаннан кейін қаскүнем генератормен берілетін сол алдыңғы
кездейсоқ мәліметтердің көмегімен оңай тексере алады.
Аталған шабуыл түрімен күресу үшін жасауға болатын әрекеттердің ең
жақсысы – бұл энтропиясы бар кіріс оқиғалардың тобын ұйымдастыру. Біз
энтропияларды қаскүнем жинаған кездейсоқ мәліметтерді біз энтропияларды
аралыстарған кезде болжай алмайтындай жағдайға жеткенше жинаймыз. Сонымен,
ол үшін қанша энтропия керек болады? Біздің қауіпсіздік деңгейіне деген
сұранысымызға байланысты қаскүнем шабуыл жасау үшін кем дегенде 2128 қадам
жіберуі керек, ол үшін 128 бит энтропия керек. Бірақ бұл жерде біз маңызды
бір мәселеге кезігеміз: энтропия санының қандай да бір бағалауын алу тіпті
мүмкін болған жағдайда да өте қиын. Энтропияны бағалау қаскүнемнің қанша
білуіне немесе білу мүмкіндігіне байланысты айтарлықтай тәуелді болады, ал
бұл ақпарат жүйе құрастырушыларына құру кезеңінде әлі белгісіз. Міне,
Yarrow генераторының мәселесі осында тұр. Ол энтропияны бағалауды қолдана
отырып көздің энтропиясын есептеуге тырысады, ал барлық жағдайлар үшін
дұрыс бағалауды алу практика жағынан мүмкін емес.
Жүйе құрастырушылары осы бөліммен жұмыс жасаған кезде Yarrow
генераторын жетілдірген. Жаңа шешім Fortuna (Фортунаның атына – соқыр
жағдай мен сәттің ежелгіримдік құдайының атына) деген атқа ие болды.
Fortuna энтропияны бағалаудан бас тарта отырып оны анықтау керегінің
мәселесінен шығарды. Әрі қарай көбінесе ЖКСГ (жалғанкездейсоқ кездейсоқ
сандар генерациялау) Fortuna-ның толық қарастыру туралы айтылады.
Fortuna үш бөліктен тұрады. Генератор бекітілген ұзындықтың бастапқы
санын кіріске алады және жалғанкездейсоқ мәліметтердің кез келген санын
береді. Аккумулятор әр түрлі көздерден энтропияларды жинап толтыра
бастайды, сонымен қатар генератордың бастапқы санын уақыт арасында өзгертіп
отырады. Және ақырғысы, бастапқы санның файлының басқару жүйесі генератор
кездейсоқ мәліметтерді тіпті компьютердің қайта жүктеуінен кейін де шығара
алатынына кепіл береді.

2 Кездейсоқ сандар генераторының тәжірибеде іске асырылуы

2.1 Кездейсоқ сандар генераторының құралдары

Генератор белгіленген ұзындықтың кейбір жағдайын кез келген ұзындықтың
шығыс мәліметтеріне ауыстырады. Генератор ретінде біз AES-ұқсас блоктық
шифрды қолданамыз. Өздеріңізге ұнайтынын таңдаңыздар – AES (Rijndael),
Serpent немесе Twofish. Генератордың ішкі күйінде 256-биттік блоктық
шифрдың кілті және 128-биттік есептеуіш болады.
Өзінің мәні бойынша генератор – бұл тек қана есептеуіш жағдайында
жұмыс жасайтын блоктық шифр. Еске салайық, есептеуіш жағдайы немесе CTR
мәліметтердің біз шығыстар ретінде қолданатын кездейсоқ ағынын
генерациялайды. Қауіпсіздікті жоғарылату үшін блогтық шифрдың жұмыс
режиміне тағы бірнеше жетілдірулерді қосамыз.
Егер қолданушы немесе қосымша кездейсоқ мәліметтер сұрайтын болса,
генератор өзінің алгоритмін қосып жалғанкездейсоқ мәліметтер шығарады. Енді
қаскүнем генератордың күйін кезекті сұраныстан кейін алуға мүмкіндігі
болсын деп есептейік. Егер генератормен берілген алдыңғы нәтижелер
дескридитацияланбаса жақсы болар еді. Ол үшін әрбір сұраныстан кейін тағы
256 бит жалғанкездейсоқ мәліметтерді генерациялаймыз және оларды шифрлаудың
жаңа кілті ретінде қолданамыз. Ескі кілт осы кезде алдыңғы сұраныстар
туралы ақпараттың шығуын болдыртпау үшін жойылады.
Генерацияланған мәліметтер статистикалық кездейсоқтыққа ие болуы үшін
бір мезгілде аса көп мәліметтерді генерациялап керегі жоқ. Расында да,
ақиқат кездейсоқ мәліметтерде блоктың мәндері қайталануы мүмкін, ал
есептеуіш режиміндегі шығыс мәліметтері ешқашан қайталанатын блоктарды
шығармайды. Бұл мәселені шешудің бірнеше жолдары бар. Мысалы, практика
жағынан блогтың ақиқат кездейсоқ кезегінен статистикалық ауытқуын
болдырмайтын тексті шифрлаудың блогының тек бір жартысын қолдануға болады.
Блогтық шифрлаудың орнына екінің бірі ретінде жалғанкездейсоқ функцияны
(pseudorandom function) қолдануға болады, бірақ бізге әлі жақсы зерттелген
және тиімді ұсыныстар кездескен жоқ. Осы жағдайда жасауға болатындардың ең
оңайы – ол бір сұранысқа берілетін кездейсоқ мәліметтердің байт санын
шектеу. Бұл ақиқат кездейсоқ кезектіктен статистикалық ауытқуын қиындатады.
Егер бізге 264 мәліметтер блогын бір ғана кілттің көмегімен
генерациялау керек болатын болса, біз блоктардың мәндерінің арасында
қайшылықтардың пайда болғанын күтер едік. Осындай өлшемді сұраныстардың
бірнеше қайталаулары генератордың шығыс мәліметтері ақиқат кездейсоқ емес
екендігін тез көрсетер еді; оларға қайшылықтардың санының күтілімі
жетпейді. Сондықтан біз бір сұранысқа берілетін мәліметтердің максималды
өлшемін 216 блоктармен (яғни, 220 байт) шектейміз. Кездейсоқ сандардың
тамаша генераторы үшін 216 мәліметтер блогтарының арасынан қайшылықтардың
табылу ықтималдығы жуықтап 2-97 құрайды, сондықтан қайшылықтың толық
жоқтығы жуықтап 297 сұраныс жасағаннан кейін ғана табылуы мүмкін.
Қаскүнемге жасауға керекті жұмыстың жалпы саны жуықтағанда 2113 қадамды
құрайды. Бұл, әрине, біз ойлағандай 2128 қадамнан аз, бірақ сонда да онша
жаман емес.
Біз аса төмен (расында, кішкене аса төмен) қауіпсіздік деңгейіне
келісе отырып өзіміздің принциптерге қарсы тұратынымызды білеміз. Өкінішке
орай, бұл шешімнің жақсы жақсы жолы жоқ секілді. Бізде толық 128-биттік
деңгейлі қауіпсіздікті жалғанкездейсоқ сандардың генераторын жасауға
болатын керекті криптографиялық функциялар жоқ. Біз SHA-256 функциясын
қолдануға болар еді, бірақ ол өте баяу. Адамдар әрқашан жалғанкездейсоқ
сандардың жақсы криптографиялық генераторларын қолдану туралы ойлайды және
осының қолдануына қарсы аргумент болып жылдамдық болады. Қауіпсіздікдіктің
тағы бірнеше битін алу үшін генератордың жұмыс жасау жылдамдығының көрінген
төмендеуін қолданушылардың негізгі массасын нақты келтіре алмайды. Олардың
көбі барлық жүйенің қауіпсіздік деңгейін толық құртқанша, басқа, расында да
жаман генераторды таңдайды.
Егер бізде 256-биттік көлемді блоктың блоктық шифры болса, онда
коллозия сұрағы ешқашан тұрмас еді. Расында, практикада келтірілген
шабуылдың ешқандай серезный қаупі жоқ. Оны орындауға қаскүнем жасау керек
болатын керекті 2113 қадам жетпес еді. Шабуыл жасалынып жатқан компьютерге
де шифрлаудың 2113 операциясын жасау керек болады. Көріп отырғандай, мұндай
шабуылдың сәтілігі қаскүнемнің компьютерінің жұмыс жасау жылдамдығымен
қатар қолданушының да компьютерінің жұмыс жасау жылдамдығына байланысты.
Көптеген қолданушылар өздерінің компьютерлерінің есептеу жылдамдығын
қаскүнемге көмектесу үшін үлкейтіп жатпайды. Шынында, бізге шешу
қауіпсіздігіне қарай осындай аргументтерді қолданған ұнамайды. Олар өте
біркелкі емес, және егер жалғанкездейсоқ сандардың генераторы бір кезде
непривычный айналада қолданылатын болса, бұл аргументтер жұмыс істемеуі
мүмкін. Сонда да, осы жағдайды ескере отырып біздің шешім біз келе алатын
ең жақсы компромис болады.
Әрбір сұранысты орындауды аяқтағаннан кейін біз блогтық шифрдың кілтін
есептеген кезде есептеуішті қайта бастамаймыз. Бұл екінші деңгейлі жағдай,
бірақ ол қысқа циклдардың мәселесінен шығуға көмектеседі. Бізге әрбір
сұранысты орындағаннан кейін есептеуішті қайта бастау керек болсын делік.
Егер кілттің мәні бір кезде екінші рет қайталанса, ал барлық сұраныстар
есептелген мәліметтер көлемін алатын болса, онда кілттің келесі мәні де дәл
солай екінші рет қайталанады. Аяғында кілттің мәнінің қысқа циклін алуға
болады. Расында бұндай жағдай аз мүмкіндікті, әйтсе де, есептеуішті қайта
бастамай бұл мәселеден толық құтылуға болады. Есептеуіштің ұзындығы 128 бит
болғандықтан, біз ешқашан есептеуіштің мәнін (2128 блоктың генерациясы
біздің компьютерлердің есептеуіш мүмкіндіктерінен асып түседі)
қайаламаймыз, яғни ол қандай да бір циклдардың пайда болуын автоматты түрде
болдырмайды. Оған қоса генератордың кілті әлі жоқтығын 0 есептеуіш мәнін
қолдана аламыз, сол себепті, мәліметтер бере алмайды.
Назар аударыңыздар: бір сұранысқа жауапқа беріле алатын максималды
мәліметтер көлемінің 1 Мбайтқа дейінгі шегі өте алмайтындай емес. Егер
сізге кездейсоқ мәліметтердің мегабайттан көп мәндері керек болса жай ғана
сұранысты қайталаңыз. Шындығында жүйенің орындалуы осындай қайталанатын
сұраныстарды автоматты түрде орындайтын интерфейс болуы мүмкін.
Генератор өзі өте пайдалы модуль болып табылады. Ол көптеген
орындауларда тек Fortuna ЖКСГ (жалған кездейсоқ сандар генераторы)
компоненті ретінде ғана емес, сонымен қатар оның интерфейсінің бөлігі
ретінде қолданылуы мүмкін деп есептейміз. Мысалға Монте-Карло әдісімен
модельдеуді орындайтын бағдарламаны алсақ. Біз бұл моделдеу кездейсоқ
болуын қалаймыз делік. Онымен қоса, біз керек болған кезде керекті
есептеулерді (мысалы, отладка немесе тексеру үшін) жасауға болатындай болуы
керек. Ол үшін бағдарлама басында бір рет операциялық жүйенің орнатылған
кездейсоқ сандар генераторын шақыруға болады. Оның көмегімен біз кездейсоқ
бастапқы санды аламыз. Бұл сан бағдарламаның шығыс мәліметтерінің бөлігі
ретінде алынуы мүмкін, одан кейін біздің генератормен моделдеуге керекті
қалған кездейсоқ мәліметтерді есептеуге қолданылуы мүмкін. Генератордың
шығыс бастапқы санын біле отырып барлық есептеулердің дұрыстығын бақылап
отыруға болады. Ол үшін бағдарламаны тағы да сол кіріс мәліметтерімен және
бастапқы сандарымен жіберу жеткілікті. Ал отладка үшін моделдеудің сол бір
ғана процесі қайта-қайта жіберіле алады, сонымен қатар, оның әрекеті
әрқашан біркелкі болады – тек бастапқы кіріс саны өзгеріссіз болғандай.
Енді генератордың жұмысын толығырақ қарастырайық.
Біз кілт пен есептеуіштің мәндерін генераторға бастапқы санның
берілмегенін білдіретіндей нөлге тең деп аламыз.

функция InitiaizeGenerator
выход G Генератор күйі.
К кілтінің және С есептеуішінің мәндерін нолге тең деп қоямыз.
(К, С)((0, 0)
Күйді құрамыз.
G ( (K, C)
Return G

Reseed функциясы генератордың күйін туынды ұзындықты кіріс жолдың
көмегімен жаңартады. Бұл деңгейде кіріс жолы нені құрайтыны бізге керек
емес. Кіріс жолының бар кілттің көмегімен тиянақты араласқанын дәләел беру
үшін кэштау фукнциясын қолданамыз.

функция Reseed
вход: G Генератордың күйі; осы функциямен өзгереді.
s Жаңа немесе қосымша бастапқы сан.
Кэштау функциясының көмегімен жаңа кілтті есептеп шығарамыз.
K ( SHAd – 256(K s)
Есептеуіштің мәнін ол нолге тең болмагандай етіп бір мәнге көбейтеміз
және генераторға бастапқы санның берілгені туралы белгі қоямыз. Берілген
жағдайда С 16-байттық бүтін сан ретінде, байттың мәні онша емесі бірінші
жазылатындай форматта берілген түрінде қарастырылады.
С ( С + 1

Бұл жерде С есептеуішінің мәні бүтін сан ретінде қарастырылады.
Кейінірек ол ашық текстің блогы ретінде берілетін болады. Бір мәннің
басқаға ауысуына мәні онша емесі бірінші жазылатын бүтін санның жазу
форматы туралы келісімді қолданатын боламыз. Ашық тексттің блогы дегеніміз
– 16 байттан: p0, ... , p15 тұратын блок. Ол бүтінсанды мәнге сәйкес келеді

Осы келісімді қолдана отырып біз С-ті 16-байттық жол ретінде де, бүтін
сан ертінде де қарастыра аламыз.
Келесі функция кездейсоқ мәліметтердің блоктарының берілген санын
генерациялайды. Бұл жалғанкездейсоқ сандардың генераторының өзімен ғана
қолданылатын ішкі функция. Генератордан тыс кез келген объект бұл функцияға
доступы болмауы керек.

функция GenerateBlocks
вход: G Генератор күйі; осы функциямен өзгереді.
k Генерациялауға керекті блоктардың саны.
выход: r 16к байт ұзындықты жалғанкездейсоқ жол.
assert C ≠ 0
Бос жолдан бастаймыз.
r ( €
Оған керекті блоктар санын қосамыз.
for i = 1, ... , k do
r ( r E (K, C)
C ( C + 1
od
return r

Сіздер ойлағандай, Е (К, С) – бұл кірісіне К кілті берілетін және С ашық
текст блогы берілетін блоктық шифрдың шифрлау функциясы. Басында
GenerateBlocks функциясы С мәні нолге тең еместігін тексереді (бұл берілген
генератордың кірісіне әлі ешқашан бастапқы сан берілмегенін білдірер еді).
Цикл басталмас бұрын r айнымалысына бос жол меншіктеледі, содан кейін оған
кезекпен әрбір келесі есептелінген блок қосылып отырады. Осындай түрмен
құрылған жол функцияның шығыс мәні болып табылады.

PseudoRandomData функциясы генератордың қолданушысының сұранысы
бойынша кездейсоқ мәліметтер генерацияланады. Ол 220 байтқа дейінгі
ұзындықты жалғанкездейсоқ жолдарды алуға көмектеседі және әрбір сұраныстан
кейін генерацияланған мәліметтер туралы кез келген ақпарат жойылатынын
гарантирват етеді.

функция PseudoRandomData
вход: G Генератор күйі; осы функциямен өзгереді.
n Генерациялауға керекті кездейсоқ
мәліметтердің
байттар саны.
выход: r n байт ұзындықты жалғанкездейсоқ жол.
Шығыс жолдың ұзындығын ақиқат кездейсоқ мәліметтерден
статистикалық ауытқуын азайту үшін шектейміз. Берілген
жолдың ұзындығы теріс емес екендігіне көзімізді
жеткіземіз.
assert 0 ≤ n ≤ 220
Шығыс мәліметтерін генерациялаймыз.
r ( первые – n – байт (GenerateBlocks(G, [n16]))
Кілттің мәнін болашақта осы мәліметтердің болуы мүмкін
дискредитациясынан құтылу үшін өзгертеміз.
K ( GenerateBlocks (G, 2)
return r

Көріп отырғандай, PseudoRandomData функциясының нәтижесі
GenerateBlocks функциясының шақырылу жолымен генерацияланады. Олардың
арасындағы бір ғана айырмашылық бар, ол PseudoRandomData функциясының
нәтижесінің керекті байт санына дейін усеченияда тұр. (Оператор [...] – бұл
үстінен дөңгелектеу операторы). Осыдан кейін біз жаңа кілтті құру үшін тағы
да екі мәліметтер блогын генерациялаймыз. Ескі К кілті жойылғаннан кейін
ешкім r мәнін қайта есептеп шығара алмайды. Егер PseudoRandomData функциясы
r мәнінің көшірмесін сақтамай осы мән сақталған жады облысын тазалап
тастаса, онда функцияның жұмысының аяғында генераторда r туралы қандай да
бір ақпараттың шығуына жай ғана жолдар қалмайды. Сол себептен, қандай да
бір уақытта болуы мүмкін келесі генератордың бұзылуы еш жағдайда келесі
шығыс мәліметтерінің құпиялылығына әсер ете алмайды. Ол тек болашақтағы
шығыс мәліметтерге – оның шешімімен аккумулятор жұмыс жасайтын мәселеге
қауіп төндіре алады.
Алдында айтып кеткендей, PseudoRandomData функциясы шығара алатын
мәліметтер көлемі шектеулі. Біз кездейсоқ жолдардың үлкен көлемін
PseudoRandomData функциясының көп рет шақыруының көмегімен шығара алатын
жолын айтып жатпаймыз. Назар аударыңыздар: функцияның бір шақыруында
алынатын шығыс мәліметтердің максималды көлемін үлкейтіп керегі жоқ,
өйткені, ол ақиқат кездейсоқ реттіліктен статистикалық ауытқуын үлкейтеді.
PseudoRandomData функциясының қайталанатын шақыруларын орындау
эффективностын төмендеуіне әкелмейді. Қосымша шығындар тек әрбір кездейсоқ
мәліметтердің генерацияланған мегабайтына жүйе тағы 32 байт кездейсоқ
мәліметтерді (жаңа кілтті құру үшін) генерациялауында және блоктық шифрдың
ішкі кілттерінің қайта санауын жүргізуінде болып отыр. Барлық бізбен
берілген блоктық шифрларға мұндай шығындар аз болып есептеледі.
Алдында айтылған Fortuna генераторы жалғанкездейсоқ сандардың
криптографиялық күшті генераторы болып ол бастапқы санды кез келген
ұзындықты жалғанкездейсоқ жолға ауыстыру мағынасында табылады. Fortuna
генераторының жұмыс жылдамдығы практика жағынан қолданылып жатқан блоктық
шифрдың жұмыс жылдамдығына тең. РС-үйлесімді процессорларлы жүйелерде
жалғанкездейсоқ мәліметтердің бір байтының генерациясы үлкен сұраныстарда
процессордың жұмысының 20-дан кем циклын алады. Сол себепті, біздің
генератор көптеген кітапханалық жалғанкездейсоқ сандардың генерациясының
функцияларының орнына ауыстыруға жеңіл қолданылуы мүмкін.
Аккумулятор ақиқат кездейсоқ мәліметтерді әр түрлі энтропия
көздерінен жинап генератордың бастапқы санын жаңартуда қолданады.
Біздің айналамызда бірнеше энтропия көздері бар дегеннен бастаймыз.
Әрбір көз кез келген уақытта энтропиясы бар оқиғаны генерациялай алады.
Бізді энтропияның көзі не болып ненің қолданылатыны қызықтырмайды. Бізге
кем дегенде бір көздің қаскүнемге болжамды болмайтындай мәліметтерді
генерацияласа жеткілікті. Біз қаскүнемнің қалай әрекет ететінін
білмегендіктен барлық болжамсыз болып саналатын мәліметтерді энтропия
көздеріне айналдырудың мәні бар. Жеке жағдайларда жаман емес кездейсоқ
мәліметтердің көздері ретінде пернені басу және тышқанның ауысу уақытын
ұсынуға болады. Мүмкіндігінше көбірек уақыттық энтропия көздерін табуға
тырысыңыздар. Сіз пернені басудың дәл уақытын, тышқанды ауыстырудың және
пернесінің басу дыбыстарын, сонымен бірге, қатты дискілердің және
принтерлердің жауаптарын қолдана (мүмкін болса бір мезгілде) аласыз. Егер
қаскүнем кейбір көздерден мәліметтерді көшіріп алса немесе болжап алса,
қорқынышты емес; ең негізгісі, ол барлық көздерге осыны жасай алмаса
жеткілікті.
Энтропия көздерін жасау құрастырушыдан көп уақыт пен күшті сұрауы
мүмкін. Заң бойынша, энтропия көздері операциялық жүйенің аппараттық
қамтамасыздандыруының драйверлеріне енгізілуі керек. Бұны қолданушы
деңгейінде жүзеге асыру практика жағынан мүмкін емес.
Әрбір көзді біз оның 0-ден 255-ке дейінгі аралықта орналасқан ерекше
номерінің көмегімен анықтаймыз. Құрастырушылар көдердің номерінің қалай –
статистикалық немесе динамикалық болатынын өздері шешеді. Әрбір оқиғаның
мәліметтері өзімен реттелген байттарды береді. Энтропия көздері тек
болжауға болмайтын оқиға мәліметтерінен тұруы керек. Мысалы, уақыт туралы
ақпарат дәл таймердің көп мәні бар екі немесе төрт байтымен берілуі мүмкін.
Бұл мәліметтерге жыл, ай немесе күнді енгізудің мәні жоқ – қаскүнем оларды
былай да біледі.
Біз әр түрлі көздерден жиналған оқиғалардың конкатенациясын
орындаймыз. Осындай конкатенацияның нәтижесінде алынған жол оқиғаларды
ерекше түрде кодтайтынына кепілдік беру үшін оны қатты структуралау керек.
Әрбір оқиға үш немесе одан көп мәліметтер байтымен кодталады. Біріншісі
кездейсоқ мәліметтердің көздерінің номерінен тұрады; екіншісі – қосымша
мәліметтер байтының санынан тұрады; келесі байттар көздерден алынған
мәліметтерден тұрады.
Әрине, қаскүнем кейбір энтропия көздерімен генерацияланған оқиғалар
туралы ақпаратты алатын болады. Осындай жағдайды жасау үшін, кейбір көздер
қаскүнемнің толық билігінде ораласқан деп есептейміз. Ақырғысы осы
көздермен қашан және қандай оқиғалар генерацияланатынын таңдайды. Одан
басқа, басқа қолданушылар секілді қаскүнем кез келген уақытта
жалғанкездейсоқ сандардың генераторынан кездейсоқ мәліметтерді сұрауы
мүмкін.
Генератордың бастапқы санын жаңарту үшін оқиғаларды пулда жинау керек.
Ақырғысы қаскүнем пулдағы оқиғаларда болатын мүмкін мәндерді таңдап ала
алмайтындай жеткілікті үлкен болуы керек. Бастапқы санның кездейсоқ
оқиғалардың жеткілікті үлкен пулдың көмегімен жаңаруы қаскүнем ие бола
алатын генератордың жағдайы туралы барлық ақпаратты мәнсіз қылады. Өкінішке
орай, біз генератордың бастапқы санын жаңарпай тұрып пулда қанша оқиғаны
жинау керектігін білмейміз. Yarrow-да бұл мәселені біз энтропияның
бағалауын және әр түрлі эвристикалық ережелерді қолдана отырып шештік.
Fortuna болса, одан гөрі сәтті әдіспен әрекет етеді.
Бізде 32 пул бар: Р0, ..., Р31. Теория жағынан әрбір пул шексіз
ұзындықты байттар жолын құрайды. Практикада болса, барлығы біраз басқаша
құралған. Алынған жол хештау функциясы үшін ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.