Дәріс №11. Тақырыбы: Дифференциалды криптоанализ
Дифференциалды криптоталдау DES сияқты криптожүйелер
жүктеу/скачать 177,62 Kb.
|
| Дифференциалды криптоталдау DES сияқты криптожүйелер
(Реферат) (AJ Menezes және SA Vanstone (ed.): Advances in Cryptology - Crypto '90, LNCS 537, 2-21 беттер, 1991. © Springer-Verlag Berlin Heidelberg 1991) Эли Бихам, Ади Шамир Вейцман атындағы ғылым институты Қолданбалы математика кафедрасы Аннотация. Деректерді шифрлау стандарты (DES) азаматтық мақсаттар үшін ең танымал және кеңінен қолданылатын криптожүйе болып табылады. Оны 70-жылдардың ортасында Ұлттық стандарттар бюросы қабылдаған IBM әзірледі және осы уақытқа дейін ашық әдебиеттерде жарияланған барлық шабуылдарға сәтті төтеп берді. Бұл мақалада біз компьютерде бірнеше минут ішінде сегіз раундқа дейін DES-ті бұзатын криптоаналитикалық шабуылдың жаңа түрін әзірлеп жатырмыз, сонымен қатар DES-ті дөрекі күшпен шабуылға қарағанда 15 раундқа дейін тез жоя алады. Бұл жаңа шабуылды DES сияқты әртүрлі алмастыру/алмастыру криптожүйелеріне қолдануға болады және дизайн ережелерінің (жарияланбаған) маңыздылығын көрсетеді. Кіріспе Итеративті криптожүйелер – әлсіз функцияны n рет қайта қолдануға негізделген криптографиялық күшті функциялар тобы. Әрбір итерация дөңгелек деп аталады, ал криптожүйе n-дөңгелек криптожүйе деп аталады. Дөңгелек функциясы алдыңғы айналымның және ішкі кілттің шығу функциясы болып табылады, ол кілтті тарату алгоритмімен есептелетін негізгі тәуелді мән болып табылады. Дөңгелек функция әдетте S-қораптарына, разрядты ауыстыруларға, арифметикалық операцияларға және эксклюзивті НЕМЕСЕ операцияларына (⊕ және XOR арқылы белгіленеді) негізделген. S-қораптары - кіріс биттерінің аз санын шығыс биттердің аз санына салыстыратын сызықты емес іздеу кестелері. Олар, әдетте, криптожүйенің жалғыз сызықты емес бөлігі болып табылады, сондықтан криптожүйенің қауіпсіздігі олардың таңдауына сыни тұрғыдан байланысты. Битті ауыстыру келесі раундтағы әрбір S-қораптың кіріс биттері мүмкіндігінше көп S-жәшіктерінің шығысына тәуелді болатындай етіп S-жәшіктеріндегі шығыс биттерінің ретін өзгерту үшін қолданылады. Эксклюзивті НЕМЕСЕ операциясы ішкі кілтті деректермен араластыру үшін жиі пайдаланылады. Көп жағдайда шифрлау алгоритмі белгілі деп болжанады, ал мәліметтердің құпиялылығы тек кездейсоқ таңдалған кілттің құпиялылығына байланысты. Lucifer [7] деп аталатын бірінші ұсынылған итеративті криптожүйе IBM-де өз өнімдерінде деректер қауіпсіздігінің өсіп келе жатқан қажеттілігін қанағаттандыру үшін әзірленді. Люцифердің дөңгелек функциясы сызықты емес S-жәшіктері мен биттік ауыстырудың тіркесімі болып табылады. Кіріс биттері қатарынан төрт биттен тұратын топтарға бөлінеді. Әрбір топ төрт бит шығаратын қайтымды S-қорап түрлендіруімен кодталған. Барлық S-қораптарының бұл шығыс биттері келесі айналымға жіберілген кезде оларды араластыру үшін ауыстырылады. Люциферде тек екі бекітілген S-қораптары (S0 және S1) таңдалды. Әрбір S-қорапты пайдалану кілтке байланысты. Шифрды шешу инверттелген S-қораптарды пайдаланып, қарама-қарсы бағытта деректерді беру арқылы жүзеге асырылады. Деректерді шифрлау стандарты (DES) [14] — Люцифердің жетілдірілген нұсқасы. Оны IBM әзірлеген және АҚШ Ұлттық Стандарттар Бюросы (NBS) құпия санатқа жатпайтын (мысалы, қаржылық транзакциялар және электрондық пошта хабарламалары) құпия деректерге арналған стандартты криптожүйе ретінде қабылдаған. DES белгілі және кеңінен қолданылатын криптожүйеге айналды. DES пернесі ұзындығы 56 бит, блок өлшемі 64 бит. Бұл блок әрқайсысы 32 биттен тұратын екі жартыға бөлінген. Дөңгелек функцияның негізгі бөлігі F функциясы болып табылады, ол 48 биттік ішкі кілт пен сегіз (алты биттен төрт битке дейін) S-қорапшасын пайдаланып деректердің оң жартысында жұмыс істейді. F функциясының 32 шығыс биттері деректердің сол жақ жартысына қосылатын модуль 2 (XOR) болып табылады және екі жартысы ауыстырылады. DES алгоритмінің толық сипаттамасы [14] берілген. Бұл жұмыста бастапқы ауыстырудың (IP) бар болуы және оның кері ауыстырылуы ескерілмейді, өйткені олардың криптоталдау үшін мағынасы жоқ. DES криптоанализіне арналған кең көлемді әдебиет 1977 жылы қабылданғаннан бері жарияланды. Дегенмен, ашық әдебиеттерде криптоанализдің күрделілігін дөрекі күштің жартысынан азына дейін төмендететін жеңілдету әдістері ешқашан хабарланған жоқ. 50% қысқарту [9] (ашық мәтінді таңдау шабуылында) комплемент симметриясына негізделген. P_1 = P ̅_2 бар екі анық/шифр мәтін жұбы (P1, T1) және (P2, T2) болса, криптоталдау бұл симметрияны пайдалана алады. Диффи мен Хеллман [6] параллельді компьютерде бір күнде бүкіл кілт кеңістігін толық іздеуді ұсынды. Олар бұл көліктің құнын 20 миллион АҚШ долларына бағалап отыр.
Олар сондай-ақ жеті раундтан тұратын DES-тің сәл өзгертілген нұсқасын 2 азайту коэффициентімен шешуге болатынын көрсетті. Дегенмен, олар ортадағы соққының бұл түрі сегіз және одан да көп раундтары бар DES-ке қолданылмайтынын дәлелдеді. Сол жылы Дональд В.Дэвис [3] белгілі ашық мәтінмен DES-ке криптоаналитикалық шабуылды сипаттады. Жеткілікті деректерді ескере отырып, ол кілт биттері арасында 16 сызықтық сілтеме жасай алады, осылайша келесі кілттерді іздеу үшін операциялар санын 240-қа дейін азайтады. Ол көрші S-жәшіктерінің шығыстары арасындағы корреляцияны пайдаланады, себебі олардың кірістері келесіден алынған. , әйтпесе, бит тарату операциясының нәтижесінде пайда болатын бірдей бит жұптары. Бұл корреляция S-қорапшасының кіріс биттерін өзгерту үшін пайдаланылатын төрт негізгі бит арасындағы сызықтық қатынасты аша алады. DES (IP емес) нәтижесінің екі 32 биттік жартысы бұл шығыстарды бір-бірінен тәуелсіз алады, сондықтан көршілес S-жәшіктерінің әрбір жұбын екі рет пайдалануға болады, бұл 16 бит негізгі ақпаратты береді. Бұл талдау ашық мәтінді P немесе шифрланған T талап етпейді, бірақ P⊕T пайдаланады және кездейсоқ енгізулердің үлкен санын қажет етеді. S-қораптарының жұптары олар жасайтын корреляция дәрежесімен ерекшеленеді, сондықтан, мысалы, S7 / S8 жұбы үшін шамамен 1017 үлгі қажет, ал S2 / S3 жұбы үшін шамамен 1021 үлгі қажет. Шамамен 1023 үлгімен барлығы S3 / S4 жұбын қоспағанда, нәтижелер беруі керек (яғни, жалпы алғанда 14 бит негізгі ақпарат). Барлық жұптарды пайдалану үшін криптоаналитикке шамамен 1026 үлгі қажет болады. S-қораптары корреляцияны азайту үшін жасалмаған сияқты, бірақ олар осыған байланысты кездейсоқ таңдаудан біршама жақсырақ. Қажетті үлгілердің көп саны бұл талдауды қатал күшпен толық айналымды DES-ке қарағанда әлдеқайда қиындатады, бірақ DES-тің 8-раундтық нұсқасы үшін 1012 немесе 1013 (шамамен 240) үлгі өлшемі практикалық. Осылайша, Дэвистің талдауы бұрын жарияланған шабуылдарға қарағанда көбірек раундтарды қамтуға мүмкіндік береді. Соңғы онжылдықта DES нұсқалары болып табылатын бірнеше криптожүйелер ұсынылды. Шаумюллер-Билл осындай үш криптожүйені ұсынды [15, 17]. Олардың екеуі (C80 және C82 деп аталады) F функциясы қайтымсыз функциялармен ауыстырылған DES құрылымына негізделген. Жалпыланған DES схемасы (GDES) деп аталатын үшінші нұсқа - DES жылдамдығын арттыру әрекеті. GDES-те бастапқы F DES функциясы бар 16 раунд бар, бірақ екі бөліктен көп бөлікке бөлінген блок өлшемі ұлғайған. Ол GDES DES шифрлау жылдамдығын оның күшін төмендетпей арттырады деп мәлімдейді. Басқа нұсқа - деректерді жылдам шифрлау алгоритмі (Feal). Feal 8-биттік микропроцессорларда тиімді пайдалануға арналған. Феалдың екі нұсқасы бар. Feal-4 деп аталатын бірінші нұсқасы [19] төрт раундтан тұрады. Feal-4-ті Ден-Боер [4] ашық мәтінді және 100-10 000 шифрлауды таңдау арқылы бұзды. Feal жасаушылар сегіз раундтан және ішкі кілттері бар ашық мәтінді және шифрлық мәтінді 2 модульді қосудың (XOR) қосымша операциялары бар Feal-8 деп аталатын жаңа нұсқаны жасау арқылы жауап берді [l8,13]. Екі нұсқа да криптографиялық тұрғыдан бірнеше жолмен DES-тен жоғары деп сипатталады. Бұл мақалада біз DES сияқты көптеген итеративті криптожүйелерге қолдануға болатын шабуылдың жаңа түрін сипаттаймыз. Бұл тек алынған шифрлық мәтіндерді пайдаланатын ашық мәтіндік шабуыл. Бұл шабуылдың негізгі құралы ашық мәтінде белгілі бір айырмашылықтары бар жұп шифрленген мәтіндер болып табылады. Бұл екі ашық мәтінді кездейсоқ таңдауға болады, егер олар айырмашылық шартын қанағаттандырса және криптоаналитик олардың мағыналарын білу қажет болмаса. Шабуыл статистикалық сипатта және сирек жағдайларда сәтсіздікке ұшырауы мүмкін. жүктеу/скачать 177,62 Kb. Достарыңызбен бөлісу:
|