Кездейсоқ сандарды генерациялау: ақиқат және жалған кездейсоқ генераторлар, шабуыл модельдері және практикадағы іске асыру

1 Кездейсоқ сандарды генерациялау 1.1 Ақиқат кездейсоқ сандар және олрды қолданудың мәселелері Кілтті генерациялау үшін бізге кездейсоқ сандарды генерациялауыш (random Біз кездейсоқтықтың өзімен расында нені білдіретінін онша толық Көптеген криптографиялық функцияларға жақсы кездейсоқ сандардың генераторлары керек. Кездейсоқтықтың өлшемі энтропия (entropy) деп аталады. Мен бұл Кездейсоқ үлестірілуі бір қалыпты болмайтын мәндер үшін энтропияны мұндағы Р(Х=х) – Х айнымалысының х мәнін қабылдау Тамаша әлемде «ақиқат кездейсоқ» сандарды қолданған дұрыс болар Кәдімгі компьютерлерде энтропияның бірнеше көздері бар. Осындай көздердің Көптеген өңдеушілер әр түрлі көздерден алынуы мүмкін энтропияның Өзін кездейсоқ түрде ұстайтын көптеген физикалық процестер бар. Кейбір қазіргі заманғы компьютерлерде енгізілген ақиқат кездейсоқ сандардың Ақиқат кездейсоқ сандарды алудың қиындығынан басқа, оларды практикада Екінші мәселе кездейсоқ сандардың физикалық генераторлары секілді ақиқат Және үшінші мәселе – ол нақты физикалық оқиғалардан 1.2 Жалғанкездейсоқ сандар және оларды қолданудың мәселелері Ақиқат кездейсоқ сандардың орнына жақсы құрал ретінде жалғанкездейсоқ Криптографиялық жүйенің контексінде жалғанкездейсоқ сандардың генераторларына одан да Сіздің бағдарламалық кітапханаңызда бар жай кездейсоқ функцияларды ұмытыңыздар. 1.3 Ақиқат кездейсоқ сандар және жалғанкездейсоқ сандардың генераторлары. Ақиқат кездейсоқ сандарды біз тек жалғанкездейсоқ сандардың генераторларына Ақиқат кездейсоқ сандар жалғанкездейсоқ сандардан гөрі жақсырақ деген 1.4 Жалғанкездейсоқ сандардың генераторына шабуылдардың моделдері. Жалғанкездейсоқ сандардың генераторлары салыстырмалы аз зерттелген. Кездейсоқ (жалғанкездейсоқ) Уақыттың әрбір сәтінде жалғанкездейсоқ сандардың генераторында ішкі күйі Жалғанкездейсоқ сандардың генераторларына шабуылдаудың әр түрлі формалары бар. Егер қаскүнем қандай да бір этапта генератордың ішкі Қаскүнемге ішкі күйі белгілі генератордың қауіпсіздігін қайта құру Тіпті егер біз генератордың ішкі күйін оқиғалардың шығуы Аталған шабуыл түрімен күресу үшін жасауға болатын әрекеттердің Жүйе құрастырушылары осы бөліммен жұмыс жасаған кезде Yarrow Fortuna үш бөліктен тұрады. Генератор бекітілген ұзындықтың бастапқы 2 Кездейсоқ сандар генераторының тәжірибеде іске асырылуы 2.1 Кездейсоқ сандар генераторының құралдары Генератор белгіленген ұзындықтың кейбір жағдайын кез келген ұзындықтың Өзінің мәні бойынша генератор – бұл тек қана Егер қолданушы немесе қосымша кездейсоқ мәліметтер сұрайтын болса, Генерацияланған мәліметтер статистикалық кездейсоқтыққа ие болуы үшін бір Егер бізге 264 мәліметтер блогын бір ғана кілттің Біз аса төмен (расында, кішкене аса төмен) қауіпсіздік Егер бізде 256-биттік көлемді блоктың блоктық шифры болса, Әрбір сұранысты орындауды аяқтағаннан кейін біз блогтық шифрдың Назар аударыңыздар: бір сұранысқа жауапқа беріле алатын максималды Генератор өзі өте пайдалы модуль болып табылады. Ол Енді генератордың жұмысын толығырақ қарастырайық. Біз кілт пен есептеуіштің мәндерін генераторға бастапқы санның функция InitiaizeGenerator выход G К кілтінің және С есептеуішінің мәндерін нолге тең (К, С)((0, 0) Күйді құрамыз. G ( (K, C) Return G Reseed функциясы генератордың күйін туынды ұзындықты кіріс жолдың функция Reseed вход: G s Жаңа Кэштау функциясының көмегімен жаңа кілтті есептеп шығарамыз. K ( SHAd – 256(K || s) Есептеуіштің мәнін ол нолге тең болмагандай етіп бір С ( С + 1 Бұл жерде С есептеуішінің мәні бүтін сан ретінде Осы келісімді қолдана отырып біз С-ті 16-байттық жол Келесі функция кездейсоқ мәліметтердің блоктарының берілген санын генерациялайды. функция GenerateBlocks вход: G k Генерациялауға керекті выход: r assert C ≠ 0 Бос жолдан бастаймыз. r ( € Оған керекті блоктар санын қосамыз. for i = 1, … , k do r ( r || E (K, C ( C + 1 od return r Сіздер ойлағандай, Е (К, С) – бұл кірісіне PseudoRandomData функциясы генератордың қолданушысының сұранысы бойынша кездейсоқ мәліметтер функция PseudoRandomData вход: G n байттар саны. выход: r Шығыс жолдың ұзындығын ақиқат кездейсоқ мәліметтерден статистикалық ауытқуын азайту үшін шектейміз. Берілген жолдың ұзындығы теріс емес екендігіне көзімізді жеткіземіз. assert 0 ≤ n ≤ 220 Шығыс мәліметтерін генерациялаймыз. r ( первые – n – байт (GenerateBlocks(G, Кілттің мәнін болашақта осы мәліметтердің болуы мүмкін дискредитациясынан құтылу үшін өзгертеміз. K ( GenerateBlocks (G, 2) return r Көріп отырғандай, PseudoRandomData функциясының нәтижесі GenerateBlocks функциясының шақырылу Алдында айтып кеткендей, PseudoRandomData функциясы шығара алатын мәліметтер Алдында айтылған Fortuna генераторы жалғанкездейсоқ сандардың криптографиялық күшті Аккумулятор ақиқат кездейсоқ мәліметтерді әр түрлі энтропия Біздің айналамызда бірнеше энтропия көздері бар дегеннен бастаймыз. Энтропия көздерін жасау құрастырушыдан көп уақыт пен күшті Әрбір көзді біз оның 0-ден 255-ке дейінгі аралықта Біз әр түрлі көздерден жиналған оқиғалардың конкатенациясын орындаймыз. Әрине, қаскүнем кейбір энтропия көздерімен генерацияланған оқиғалар туралы Генератордың бастапқы санын жаңарту үшін оқиғаларды пулда жинау Бізде 32 пул бар: Р0, ..., Р31. Теория Энтропияның әрбір көзі өзінің кездейсоқ оқиғаларын пулдар арасында Біз генератордың бастапқы санын әрбір Р0 пулының құрамының Көрсетілген жүйе автоматты түрде нақты жағдайға үйрене алады. Қаскүнеммен генератордың ішкі күйі туралы ақпарат ашылғаннан кейін < 256, шығады, сондықтан, < Басқа сөзбен айтқанда, қалпына келтіру моменттерінің арасындағы уақыт Бұл өте жақсы нәтиже. Біздің шешіміміз идеалдыдан 64 Осы уақытқа дейін біз бізде тек 32 пулдың Төменде аккумуляторды іске асырудың бірнеше ойлары келтірілген. Оқиғаларды пулдар арасында орналастыру Түсіп жатқан оқиғалар қандай да бір түрмен пулдар Біздің шешіміміз әрбір энтропия көзі оқиғамен бірге осы Аккумулятор әрбір энтропия көзі өзінің оқиғаларын пулдар арасында Бұндай ойды пайдалы деп те айтуға болмайды. Еске Оқиғаны тексеру уақыты Аккумуляторға оқиғану беру кезінде орындалуы мүмкін есептеулер санын Әрбір оқиғаны тексеруге керекті есептеулердің анықталған минималды көлемі Бір немесе бірнеше пулдар жұмысқа енгізілген бастапқы санның Бастапқы санның жаңаруы дәл кездейсоқ мәліметтерді алу сұранысын Осындай SHAd-256-ға ұқсас хештау функциясы кіріс хабарламаларын есептелген Жоғарыда айтылғандарды ескерсек, жұмыстың нәтижелілігін арттыру үшін пулдың Инициализациялау процедурасы әдеттегідей өте жеңіл. Осы уақытқа дейін функция InitializePRNG выход: R ЖКСГ күйі 32 пулдың әрқайсысына бос жолды орналастырамыз. for i = 0, …, 31 do Pi ( € od Жаңару есептеуішінің мәнін 0-ге тең деп қоямыз. ReseedCNT ( 0 Одан кейін генераторды инициализациялаймыз. G ( InitializeGenerator() Күйді жинаймыз. R ( (G, ReseedCNT, P0, …, P31) Return R Алдында айтылып кеткендей, RandomData функциясы генератор-қосымша үшін қабықты функция RandomData вход: R ЖКСГ күйі; осы функциямен n Генерациялауға керекті кездейсоқ мәліметтердің байт саны. выход: r If length(P0) ≥ MinPoolSize ˄ ақырғы жаңару > then Бізге жаңаруды орындау керек. ReseedCNT ( ReseedCNT + 1 Барлық пулдардың осы жаңару операцияссында қолдануға керекті хэш-кодтарын бір жолға біріктіреміз. s ( € for i = 0, …, 31 do if 2i | ReseedCNT then s ( s || SHAd – 256(Pi) Pi ( € Fi od Мәліметтерді алғаннан кейін біз жаңаруды орындай аламыз. Reseed (G, s) fi Егер ол керек болған жағдайда жаңару орындалды. Енді return PseudoRandomData (G, n) Басында RandomData функциясы Р0 пулының өлшемін MinPoolSize параметрімен Келесі қадам жаңару есептеуішін үлкейтуде болып отыр. Инициализациялау for … do циклы пулда сақталатын жол хэш-кодтарын Энтропия көздерін AddRandomEvent функциясы онда кезекті кездейсоқ оқиға функция AddRandomEvent вход: R ЖКСГ күйі; осы функциямен өзгертіледі. S Көздің 0, ..., 255 диапазонындағы нөмірі. i пулдың 0, ..., диапазонындағы нөмірі. Әрбір көз e Оқиға мәліметтері. Ұзындығы 1, ..., 32 диапазонында Алдымен параметрлердің тексеруін орындаймыз. assert 1 ≤ length (e) ≤ 32 ˄ Пулға мәліметтерді қосамыз. Pi ( Pi || s || length (e) Еске салайық, әрбір оқиға 2 + length (e) Біз оқиға мәліметтерінің ұзындығын 32 байтпен шектедік. Бұл Энтропия көздерінің кейбірінде AddRandomEvent функциясын шақыруға мүлдем уақыттары Архитектураның талғамы ретінде энтропия көздері жай ғана аккумулятор Біздің ЖКСГ кездейсоқ санның бірінші жаңаруынан кейін энтропияны Бұл мәселені шешу үшін бастапқы санның файлын қолдануға Келесі бөлімдерде бастапқы санның файлының басқарылуы суреттеледі. Басында Басында бастапқы санның файлын генерациялау керек. Бұл оңай функция WriteSeedFile вход: R ЖКСГ күйі; осы функциямен өзгертіледі. f Энтропияны жазуға керекті файл. write (f, RandomData (R, 64)) Бұл функция жай ғана 64 байт кездейсоқ мәліметтерді Көріп отырғандай, бізге бастапқы санның файлын оқу үшін функция UpdateSeedFile вход: R ЖКСГ күйі; осы функциямен өзгертіледі. f Жаңартатын файл. s ( read (f) assert length (s) = 64 Reseed (G, s) write (f, RandomData (R, 64)) Бұл функция бастапқы санның файлын оқиды, оның ұзындығын UpdateSeedFile функциясы ешкім ЖКСГ-ны генератордың күйінің жаңаруы мен Құрастырушы бастапқы санның файлы құпияда сақталады деп кепілдік Компьютерді қайта жүктегеннен кейін генераторда кездейсоқ мәліметтерді генерациялауға Компьютер жұмыс істеп тұрған кезде ол энтропияны әр Генератордың күйін жаңартамыз деп біз көптеген мәселелермен кездесеміз. Өмірде архивтердің бар екені белігіл жайт. Егер біз Осындай түрдегі шабуылдардан тікелей қорғау болмайды. Егер архивтеу Тағы бір бастапқы санның файлымен байланысты маңызды мәселе Генератордың күйін бастапқы санның файлының көмегімен жаңарта отырып, Кейбір файлдық жүйелер осындай мәселерді шешу үшін журналдарды Құрал мен операциялық жүйе тұрақты сақтауыштардағы файлдарды жаңартудың Жалғанкездейсоқ сандар генераторы бірінші рет іске қосылғанда, ол Егер де орнатушы бағдарлама операциялық жүйені тікелей кескіндеу 2.2 Әзірленген «Кездейсоқ сандарды генерациялау» бағдарламасының компьютерде жүзеге Аты ағылшынның random (сондықтан, ағылшын тілін біле отырып Кітапхана екі деңгейге бөлінеді: Кездейсоқ сандардың генераторының ядросы биттерді беруді қамтамасыз етеді. Random класы кездейсоқ сандардың генераторынан нақты мәндерді алу RandomGen класының StgGen данасы кем дегенде 30 бит Random класы өзінің ұйғарымында кездейсоқ сандардың берілу көзіне class Random a where randomR :: RandomGen g => (a, a) -> random :: RandomGen g => g -> randomRs :: RandomGen g => (a, a) -> randoms :: RandomGen g => g -> randomRIO :: (a,a) -> IO a randomIO :: IO a Методы по умолчанию randoms g = x : randoms g' where (x,g') = random g randomRs = ...аналогично... randomIO = getStdRandom random randomRIO range = getStdRandom (randomR range) 10