Дәріс №11. Тақырыбы: Дифференциалды криптоанализ
Дифференциалдық криптоанализға кіріспе
жүктеу/скачать 177,62 Kb.
|
11-Дәріс
| Дифференциалдық криптоанализға кіріспе
Дифференциалды криптоталдау – ашық мәтіндік жұптардағы ерекше айырмашылықтардың қабылданған шифрлық мәтін жұптарындағы айырмашылықтарға әсерін талдайтын әдіс. Бұл айырмашылықтар ықтимал кілттерге ықтималдықтарды тағайындау және ең ықтимал кілтті табу үшін пайдаланылуы мүмкін. Бұл әдіс, әдетте, белгілі бір айырмашылығы бар ашық мәтіннің көптеген жұптарында жұмыс істейді және шифрлық мәтіннің нәтижелі жұптарын ғана пайдаланады. DES сияқты криптожүйелер үшін бұл айырмашылық екі қарапайым мәтіннің 2 қосынды модулінің (XOR) бекітілген мәні ретінде таңдалады. Бұл бөлімде біз бұл айырмашылықтарды қалай талдауға және пайдалануға болатынын көрсетеміз. Осы шарттарда F DES функциясының әрекетін еске түсірейік. F функциясы кіріс ретінде 32 бит пен 48 биттік кілтті қабылдайды. Бұл кіріс (E кеңейту функциясы арқылы) 48 битке және 2 модулін қосуға (XOR) кілт арқылы кеңейтілген. Нәтиже S-қораптарына беріледі және алынған биттер ауыстырылады. DES өзінің кіріс биттеріне қатысты өте сызықты емес болып көрінгенімен, егер кіріс биттерінің белгілі бір комбинациялары бір уақытта өзгерсе, онда жеке аралық разрядтар бірнеше айналымнан кейін салыстырмалы түрде жоғары ықтималдықпен қолдануға жарамды түрде өзгереді. Біз бұл сипатты екі ашық мәтіннің 2 модулін қосудың (XOR) нақты мәнімен, аралық айналымның арнайы XOR мәнімен және сәйкес ықтималдықпен сипаттаймыз. Осындай екі шифрлау жұп деп аталады. Жұптардың XOR операциясы кілті бар модуль 2 қосу кезінде инвариантты және деректердің сол жартысы мен F функциясының шығысы арасындағы кеңейту E, ауыстыру P және модуль 2 қосу (XOR) операциясында сызықты болады. Осылайша, осы операциялардан кейін кіру кезінде мұндай XOR туралы жаңа ақпаратты алу өте оңай. DES сонымен қатар сызықты емес кестелер болып табылатын S-қораптарды қамтиды. Кіріс XOR жұбының мәнін білу XOR шығысының сәйкес мәнін білуге кепілдік бере алмайды. Дегенмен, S-box кірісіндегі әрбір XOR мәні ықтимал XOR мәндерінің ықтималдық үлестірілуін болжайды. Бұл бөлуде бірнеше XOR шығысының салыстырмалы түрде жоғары ықтималдығы бар. 1-кесте S1 ішіндегі бірнеше XOR кірістері үшін XOR шығыстарының таралуын сипаттайды. Кесте кестедегі мәндердің әрқайсысына әкелетін ықтимал жұптардың санын санайды. Әрбір кіріс XOR мәні жолға 16 мәнге бөлінген 64 мүмкін жұпты анықтайды. Осылайша, орташа мән төрт, 4/64 = 1/16 ықтималдығын білдіреді. Біз нөлдік XOR кірісінде бір ғана мүмкін XOR шығысы бар екенін көреміз, ол нөлге тең. Кестедегі көптеген мәндер мүмкін емес немесе ықтималдығы төмен. Дегенмен, ықтималдығы 1/4 (яғни 64-тің 16-сы) немесе оған жақын бірнеше мәндер бар.
DES өзінің кіріс биттеріне қатысты өте сызықты емес болып көрінгенімен, егер кіріс биттерінің белгілі бір комбинациялары бір уақытта өзгерсе, онда жеке аралық разрядтар бірнеше айналымнан кейін салыстырмалы түрде жоғары ықтималдықпен қолдануға жарамды түрде өзгереді. Біз бұл сипатты екі ашық мәтіннің 2 модулін қосудың (XOR) нақты мәнімен, аралық айналымның арнайы XOR мәнімен және сәйкес ықтималдықпен сипаттаймыз. Осындай екі шифрлау жұп деп аталады. Жұптардың XOR операциясы кілті бар модуль 2 қосу кезінде инвариантты және деректердің сол жартысы мен F функциясының шығысы арасындағы кеңейту E, ауыстыру P және модуль 2 қосу (XOR) операциясында сызықты болады. Осылайша, осы операциялардан кейін кіру кезінде мұндай XOR туралы жаңа ақпаратты алу өте оңай. DES сонымен қатар сызықты емес кестелер болып табылатын S-қораптарды қамтиды. Кіріс XOR жұбының мәнін білу XOR шығысының сәйкес мәнін білуге кепілдік бере алмайды. Дегенмен, S-box кірісіндегі әрбір XOR мәні ықтимал XOR мәндерінің ықтималдық үлестірілуін болжайды. Бұл бөлуде бірнеше XOR шығысының салыстырмалы түрде жоғары ықтималдығы бар. 1-кесте S1 ішіндегі бірнеше XOR кірістері үшін XOR шығыстарының таралуын сипаттайды. Кесте кестедегі мәндердің әрқайсысына әкелетін ықтимал жұптардың санын санайды. Әрбір кіріс XOR мәні жолға 16 мәнге бөлінген 64 мүмкін жұпты анықтайды. Осылайша, орташа мән төрт, 4/64 = 1/16 ықтималдығын білдіреді. Біз нөлдік XOR кірісінде бір ғана мүмкін XOR шығысы бар екенін көреміз, ол нөлге тең. Кестедегі көптеген мәндер мүмкін емес немесе ықтималдығы төмен. Дегенмен, ықтималдығы 1/4 (яғни 64-тің 16-сы) немесе оған жақын бірнеше мәндер бар. 1-кесте. XOR e S1 жұптарының ішінара таралу кестесі (х индекстері бар мәндер он алтылық). Біз бұл сипатты негізгі биттерді анықтау құралы ретінде пайдалана аламыз. Егер соңғы айналымдағы F-тің XOR шығысын таба алсақ, онда жұп шифрленген мәтіндер белгілі болса, сол F-де қолданылатын ықтимал ішкі кілттер жинағын сүзуге болады. Екі шифрленген мәтінмен F соңғы айналым функциясының XOR кірістерін және оның XOR шығыстарын есептеу оңай. Әр S-қораптың кіріс XOR мәндері және шығыс XOR мәндері белгілі болады. Егер k кіріс жұбы кестеде белгілі бір мәнге әкелуі мүмкін болса, онда ішкі кілттің сәйкес алты битінің дәл k мәндері мүмкін болады. Көптеген ішкі кілт мәндері тек бірнеше жұптан шығарылады. Дегенмен, ішкі кілт биттерінің нақты мағынасы барлық жұптарды қамтиды деп есептеледі және осылайша анықталуы мүмкін. Келесі кіріспе мысал үш айналымдық DES-ті бұзады. Бұл шабуылда нөлдік оң жарты және ерікті сол жартыдан тұратын ашық мәтіннің модуль 2 (XOR) қосындыларына сәйкес келетін шифр мәтіндерінің жұптары пайдаланылады. Алгоритмнің негізгі бөлігі әрбір S-жолағына кіретін алты кілттік бит үшін әрбір мүмкін мәнді көрсететін жұптардың санын есептейді. Шифрленген мәтіндердің әрбір жұбы үшін келесі әрекеттер орындалады: бірінші айналымдағы F функциясының XOR кірісі нөлге тең, сондықтан оның XOR шығысы нөлге тең болуы керек. Шифрланған мәтіннің сол жақ жартысы ашық мәтіннің сол жақ жартысының XOR мәні, бірінші айналымның шығысы және үшінші айналымның шығысы ретінде есептеледі (l = L ⊕ A ⊕ C, мұндағы L - сол жақ жартысы. ашық мәтін және l – шифрланған мәтіннің XOR-ның сол жақ жартысы (1-суретті қараңыз). Ашық мәтіннің XOR мәні бекітілген және шифрланған мәтіннің XOR мәні белгілі және бірінші айналымның XOR шығысы нөлге тең болғандықтан, үшінші раундтағы F XOR шығысын XOR сол жақ жартысының XOR ретінде есептеуге болады. ашық мәтін және шифрлық мәтіннің XOR сол жақ жартысы. Үшінші айналымдағы F функциясының кіріс мәндері жұп шифрленген мәтіндерден оңай шығарылады. Үшінші раундтағы әрбір S-қорап үшін келесі талдауды жасауға болады. Бұл мысалда біз тек үшінші айналымда S1-ге кіретін алты негізгі битті қалай табуға болатынын көрсетеміз. S1 XOR кірісі мен XOR шығысын F XOR кірісі мен XOR шығысынан оңай алуға болады. K берілген XOR кірісі мен шығысы бар S1 ішіндегі мүмкін кіріс жұптарының саны болсын. S-жолағы кірісінің нақты мәнін (SI арқылы белгіленеді) алу үшін алты кілттік битпен (SK арқылы белгіленеді) 2 модулі (XOR) қосылған кіріс биттерінің (SE арқылы белгіленген) мәні шифрленген мәтіннен алынады. . Осылайша, бұл жұп SK = SE ⊕ SI арқылы ұсынатын нақты k кілт мәндері бар. Мысалы, екі шифрлаудың үшінші раундында S1-ге кіретін шифрлық мәтін биттері SE = 1, S_E ^ * = 35 және XOR мәні D болса, SK мәні 2-кестеде пайда болуы керек. Осы кестедегі әрбір жол сипаттайды екі бірдей кірісі бар, бірақ екі ықтимал тапсырысы бар екі жұп. Әрбір жұп бір кілтті береді, сондықтан әрбір жол екі кілтті (атап айтқанда SE ⊕ SI және S_E ^ * ⊕ SI) береді. Жұптардың көп санымен S1 енгізетін кілт биттерінің әрбір мүмкін мәнін қабылдай отырып, жұптардың санын санай аламыз. Барлық жұптар қабылдайтын мән негізгі биттердің нақты мәні болуы керек.
2-кесте: S1 ішіндегі 34 → D үшін мүмкін пернелер, 1, 35 (он алтылық) кірісі бар. Енді біз n-дөңгелек сипаттамасы деп аталатын мүмкіндігінше көп айналымнан кейін аралық XOR ақпаратын алу үшін жаңа ашық мәтінді XOR ақпаратын алуға мүмкіндік беретін негізгі құралды сипаттаймыз. Әрбір n-дөңгелек сипаттама ΩP ашық мәтіннің нақты XOR мәніне, ΩT n-ші раундындағы деректердің нақты XOR мәніне және n-ші раундтағы. Енді біз n-дөңгелек сипаттамасы деп аталатын мүмкіндігінше көп айналымнан кейін аралық XOR ақпаратын алу үшін жаңа ашық мәтінді XOR ақпаратын алуға мүмкіндік беретін негізгі құралды сипаттаймыз. Әрбір n-дөңгелек сипаттама ΩP ашық мәтіннің нақты XOR мәніне, ΩT n-ші раундындағы деректердің нақты XOR мәніне және n-ші раундтағы деректердің XOR мәні ΩT болатын p ^ Ω ықтималдығына сәйкес келеді. , XOR ашық мәтіні ΩP болатын кездейсоқ жұптар пайдаланылғанда. Ашық мәтіндік XOR ΩP және n-ші раундтағы XOR деректері (нақты кілтті пайдаланған кезде) ΩT болатын кез келген жұп дұрыс жұп деп аталады. Кез келген басқа жұп қате жұп деп аталады. Осылайша, оң қолды жұптар барлық мүмкін жұптардың p ^ Ω бөлігін құрайды. Сипаттамалардың келесі мысалдарында біз бірінші айналымдағы F функциясының XOR кіріс және шығыс мәндерін сәйкесінше F функциясының XOR кіріс және шығыс мәндерін «және A» арқылы белгілейміз. екінші турда, тиісінше b «және В» және т.б. Келесі бір айналымдық сипаттаманың ықтималдығы 1 (кез келген L ' үшін). Бұл 1/4-тен жоғары ықтималдығы бар жалғыз раундтық статистика. Бұл сипаттама ерекше маңызды, өйткені ол DES тәрізді криптожүйелерді бұзу үшін қолданылатын барлық сипаттамаларға қатысады. Келесі бір раундтық статистиканың ықтималдығы 14/64 (кез келген L ' үшін). Екі сипаттаманы біріктіру олардың ықтималдықтарының көбейтіндісіне жақын ықтималдығы бар ұзынырақ сипаттаманы құруға мүмкіндік береді. Ω1 және Ω2 сипаттамаларын біріктіру, егер Ω_T ^ 1 екі жартысының ауыстырылған мәні Ω_P ^ 2-ге тең болса, жүзеге асырылуы мүмкін. Жоғарыда сипатталған екі сипаттаманы біріктіру арқылы (14/64) ^ 2≈0,05 ықтималдықпен келесі үш дөңгелек сипаттаманы алуға болады: Кейбір сипаттамалар өзіне жабысып қалуы мүмкін. Бұл сипаттамалар итеративті сипаттамалар деп аталады. Біз итеративті сипаттаманы өзімен кез келген рет біріктіре аламыз. Итеративті сипаттамалардың артықшылығы мынада: кез келген үлкен n үшін әрбір қосымша айналым үшін тіркелген ықтималдықты азайту коэффициенті бар n-дөңгелек сипаттамасын құруға болады, ал итеративті емес сипаттамаларда ықтималдықты азайту коэффициенті әдетте көшкін әсерінен артады. Итеративті сипаттамалардың бірнеше түрі бар, бірақ ең қарапайымдары ең пайдалы болып табылады. Бұл сипаттамалар F функциясы бар нөлдік емес XOR кірісіне негізделген, ол нөлдік XOR шығысына әкелуі мүмкін (яғни, екі түрлі кіріс бірдей шығысты береді). Бұл жұпта кем дегенде үш көрші S-қораптары ерекшеленетін болса, F DES функциясында мүмкін болады (сонымен бірге [5,1] қараңыз). Бұл сипаттамалардың құрылымы келесідей. XOR кірісі X және XOR шығысы нөлге тең болатын мүмкіндігінше көп жұптар алынуы үшін F-ге XOR кірісі X белгісімен белгіленеді. Осы сипаттамалардың ең жақсысы (X = 19 60 00 00) шамамен 1/234 ықтималдылыққа ие. Бұл сипаттама тоғыз немесе одан да көп раундтармен DES-ке қарсы шабуылдарда қолданылады. Көптеген сипаттамалардың статистикалық әрекеті әртүрлі жұптар қабылдаған барлық кілттердің қиылысуын іздеуге кедергі жасайды, өйткені қиылысу әдетте бос болады: дұрыс емес жұптар ықтимал мән ретінде міндетті түрде дұрыс кілтті көрсетпейді. Дегенмен, біз дұрыс кілт мәні сипаттама ықтималдығымен пайда болатын барлық дұрыс жұптардың нәтижесі болуы керек екенін білеміз. Барлық басқа мүмкін кілттік мәндер салыстырмалы түрде кездейсоқ бөлінеді: белгілі шифрленген мәтіндер жұбы бар күтілетін XOR мәні (әдетте жұптастырылған нақты мән емес) кез келген кілт мәнін, тіпті қате кілт мәндерін де мүмкін ете алады. дұрыс жұптар толығымен кездейсоқ. Демек, дұрыс кілт сипаттаманың (дұрыс жұптардан) және басқа кездейсоқ оқиғалардың (дұрыс емес жұптардан) ықтималдығымен пайда болады. Кілтті табу үшін біз қабылданған кілттердің әрқайсысының қайталану санын санауымыз керек. Егер жұптардың саны жеткілікті үлкен болса, онда ең жиі кездесетін кілт дұрыс кілт болуы мүмкін. жүктеу/скачать 177,62 Kb. Достарыңызбен бөлісу:
|