Ақиқат кездейсоқ сандар және жалғанкездейсоқ сандардың генераторлары
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
Кездейсоқ сандар генераторы
КЕЗДЕЙСОҚ САНДАР ГЕНЕРАТОРЫМЕН БАҒДАРЛАМАЛАУ ЕРЕКШЕЛІКТЕРІ
Мәтіндерді шифрлау
Әр түрлі операциялық жүйелерде шифрлеудің программалық құралдары
Кездейсоқ сандар генераторлары
Кілттерді басқару жүйелері
Жаппай қызмет көрсету жүйелері
Сұратудың станцияда болуының орта уақыты
Дискілерді қорғау əдістері
Кездейсоқ сандарды қолдану