Шифрлеу алгоритмі

 

Р4 орын ауыстыруын қолданғандағы нәтиже Ғ функциясының нәтижесі болып табылады.

 

Ауыстырып-қосқыш – функция 

f_k функциясы тек солдағы 4 битті өзгертеді. Сондықтан келесі шифрлеу алгоритміндегі операция бірінші және соңғы төрт битті тізбекті орнымен ауыстырып отыратын SW функциясын себебі f_k функциясын келесі рет шақырғанда соңғысы басқа төрттік битпен жұмыс істеу үшін қолдану болып табылады. Екінші рет f_k функциясын шақыру кезінде Е/Р, S0, S1 және Р4 функциялары бастапқы қалпында қалады, бірақ К₁ кілтінің орнына К₂ кілті қолданылады.

 

  S-DES талдау

S-DES алгоритмін бұзу  кезінде табысқа кенелуге барлық  мүмкін мәндерін қарапайым теру  көмегімен оңай юолып келеді, себебі 10-битті кілт жағдайында 2¹⁰ = 1024 нұсқасын теру болса жеткілікті. Шифрленген мәтін болса дешифрлеу үшін талдаушы барлық мүмкін кілт нұсқаларын қолдануға болады және алынған нәтижелерді ашық мәтінге келетін ұқсастығына талдайды.

Нағыз криптоталдау туралы не айтуға болады? Мынадай шарт бойынша талдаушы меншігінде ашық мәтіннің фрагменті (р₁, р₂, р₃, р₄, р₅, р₆, р₇, р₈) және сәйкесінше шифрленген мәтін фрагменті (с₁, с₂, с₃, с₄, с₅, с₅, с₆, с₇, с₈) болса, ал (k₁, k₂, k₃, k₄, k₅, k₆, k₇, k₈, k₉, k₁₀) кілті талдаушыда болмаса белгілі ашық мәтінді талдау әдісін қарастырып көрелік. Әрбір с_і элементін p_i k_i аргументінен g_i полинамеальді функция ретінде көрсетуге болады. Бұндай көрсетілуде шифрлеу алгоритм параметрлері 10 тәуелсізімен 8 сызықты емес теңдеумен шешіледі. Бұндай жүйе әр түрлі көптеген шешімдеріне ие болуы мүмкін, бірақ оның барлығы есептелуге және талдауға жатады. Алгоритмдегі барлық орын ауыстырулар және көмекші операциялар сызықты түрленумен беріледі. Сызықты еместік жүйеге S-матрицасымен келтіріледі. Осы матрицамен берілетін теңдеулерін жазып алайық. Жазуды оңайлату үшін (р_0,0 р_0,1      р_0,2      р_0,3) = (а, b, c, d),  (р_1,0      р_1,1      р_1,2      р_1,3) = (w, x, y, z) қоямыз, ал 4-битті нәтиже (q, r, s, t) түрінде жазып аламыз. Сонда S0 модулімен берілген операция келесі теңдеу түрінде болады

q=abcd+ab+ac+b+d,

r=abcd+abd+ab+ac+ad+a+c+1,

қосу операциясының  барлығы модуль 2 бойынша орындалады. Бұндай теңдеулер S1 модулінің жұмысын сипаттайды. Тұтас алғанда мәліметтер сызықты теңдеулермен сызықты емес теңдеулер шифрленген мәтіннің биттерін есептеу үшін күрделі полиномеальді айтылуды тудырады ол криптоталдаудың қиын екенін көресетеді. Проблеманың күрделілігін көрсету үшін екілік арифметикада  2¹⁰ мүшелеріне дейін ие болуы мүмкін 10 тәуелсізі бар полиномеальді теңдеу. Сондықтан 8 теңдеудің әр қайсысы орташа 2⁹ мүшеге ие болатынын күтуге болады. Бұл теңдеулерді қандайда бір символды математикалық операцияларды қолдайтын программалық пакет көмегімен тұрғызып көрсетуге әрекет етіп көруіңізге болады. Бұндай әрекеттерді өзіңіз тастап кетуіңіз мүмкін немесе символдарды байқамай программалық пакет есебіңізді орындай беруі мүмкін.

DES-пен байланыс

DES алгоритм кірісіне 64 битті блоктар  түсіріледі. Шифрлеу схемасы келесі  түрде болуы мүмкін

IP^-1 ° f_k16°  SW  °  f_k15  °  SW  °…° SW  °f_k1  °  IP.

Шифрлеу үшін негізінде он алты 48-биттік кілт астары генерирленетін 56-битті  кілт қолданылады. Бастапқы 56-биттік тізбекті орын ауыстырудан кейін жылжу операциясы дөңгелегі және 48-биттік тізбекті орын ауыстыру орындалады.

Шифрлеу алгоритмінің өзінде Ғ функциясы 4-битті тізбектерге  емес, ол 32-битті тізбекпен орындалатын  болады. Бірінші операциядан кейін диаграмма түрінде көрсетуге болатын кеңейту/орын ауыстыру (Е/Р) шығыс тізбегі 48-битті өлшемімен алынады.

Берілген матрицамен анықталатын  мән 48-битті кілт астарымен (XOR операциясы көмегімен) қосылады. Берілген матрицада 8 жол, әрқайсысы өзінің S-матрицасын береді. Әрбір S-матрицасы 4 жолдан және 16 бағаннан тұрады. Жоғарыдағы берілген матрицаның бірінші және соңғы биттерге S-матрицасы жолы таңдалынады, ал қалған 4 битке – бағандар.

Ең танымды осы уақыттық шифрлеу схемасы 1977 жылы АҚШ-та Стандарттар ұлттық бюросында қазіргі аты Стандарттар және технологиялар ұлттық институтында қабылданған DES (Data Encryption Standard – мәліметтерді стандартты шифрлеу) стандартында жатыр. Бұл стандарт ресми түрде Federal Information Processing Standard 46 (FIPS PUB 46)  атына ие болды. Осы стандарттарға сәйкес мәліметтер 56-битті кілтті қолданып 64-битті блокпен шифрленеді. Көп қадамды алгоритм 64-битті блок кірісіне келіп түсетін ақпаратты 64-битті блокты шифрленген мәтінді түрлендіреді. Сол алгоритм дәл сол кілтпен шифрленген мәтінді кері қайта ашық түрге айналдыруға қызмет етеді.

DES стандарты кең танымдылыққа  ие болды, бірнеше рет қауіпсіздік   дәрежесін қамтамасыз ететін  полемика объектісі де болды.  Бұл полемика мәнін түсіну  үшін DES құрылымының пайда болу кезін қарастырайық.

60-шы жылдардың соңында  IBM компьютердік криптография облысында  Хорст Файстель басқарған ғылыми-зерттеу  жобасын бастады. Жобамен жұмыс  істегеннен кейінгі нәтиже 1971 жылы  басқару жүйесінде дәл ақшаны  айналдырып қолдану үшін Ллойд банкісіне сатылған LUCIFER кодты атауы бар алгоритм құрылды.  LUCIFER шифрі өзінен 64-бит өлшемді блокты және 128 битті ұзындықты кілтті қолданған Файстель блокты шифрін ұсынады. LUCIFER жобасы нәтижесіне негізделген, IBM шифрдің идеалды түрде оны бір микросхемада орналастыруға болатын коммерциялық нұсқасын шығаруға әрекеттенді. Бұл бағытты Уолтер Тачман және Карл Мейер басқарды, зерттеуге тек IBM-нің мамандары ғана емес, сонымен қатар NSA (National Security Agency – Ұлттық қауіпсіздікті басқару) консультанттары мен техникалық мамандары қосылды. Олардың жұмысының нәтижеінде LUCIFER шифрінің жақсартылған нұсқасы шықты криптоталдауға үлкен тұрақтылығына ие, бірақ кілтінің бір микросхемада алгоритм орналасу үшін 56-битке азайтылды.

1973 жылы Ұлттық стандарттар бюросы шифрлеудің ең жақсы жалпымемлекеттік стандартын құру жобасына конкурс жариялады. IBM компаниясы конкурсқа Тачман-Мейер жобасы нәтижесін ұсынды. Олардың алгоритмі шарттсыз ұсынылғандардан ең жақсы және 1977 жылы (DES) мәліметтерді стандартты шифрлеуіне ие болды.

Ресми стандарт атағына  ие болмас бұрын IBM ұсынған алгоритм бүгінгі күнге дейін басылмаған қатты сынға түсті. Сынға негізінен  екі жері түсті, біріншісі, LUCIFER шифрінде 128-бит ұзындықты кілт қолданылды, ал стандарт бойынша ол 56 дейін кемітілген болатын. Жай ғана санап енгізу криптоталдауына жарамайды кілт ұзындығы жеткіліксіз. Екіншіден, DES ішкі құрылғысында S-матрицасы құпияландырылған. Сондықтан қолданушылар DES құрылымында ешқандай деффект жоқ екеніне сенімді бола алмады, оның көмегімен NSA мамандары кілттсіз хабарды шифрлеуден ала алмайтын болды. Ары қарайғы зерттеулер дифференциалды криптоталдау бойынша соңғы жұмыстар DES сенімді ішкі құрылымына ие болды. IBM жағындағы мамандардың сендіруі бойынша стандарт жобасына енгізілген өзгерту, жобаны бағалау кезінде көрінген алгоритмнің әлсіз жерлерін күшейту үшін NSA ұсынған S-матрицасын өзгерту енгізілді.

Қалай болғанымен де DES бүкіл әлемге шықты және өте танымал болды, әсіресе қаржылық қосымшаларда. 1994 жылы NIST DES-ті қолдануды федералды  стандарт ретінде тағы 5 жылға қабылдады және ақпаратты қауіпсіздікте қолдануға шақырды.

 

DES шифрлеу

DES шифрлеу процессі  төмендегі 1 суретте келтірілген.  Басқа да кез келген шифрлеу  схемасы сияқты бұнда да шифрлеу  функциясы кірісіне екі мәліметтер  типі ұсынылады – шифрлеу үшін қажетті ашық мәтін және кілт. Келтірілген жағдайда ашық мәтін ұзындығы 64 битке , ал кілт ұзындығы – 56 битке тең.

64-битті ашық мәтін блогы                               56-битті кілт

Шифрленген мәтіннің

64-биттік блогы 

 

2 сурет. DES шифрлеу алгоритмінің жалпы схемасы.

 

Суреттің сол жағынан көрініп  тұрғандай ашық мәтінді түрлендіру процесі үш кезеңнен тұрады. Алдымен 64 битті блок ашық мәтінді алғашқы  түрлендіру кірісіне өңдеу үшін түседі, нәтижесінде орын алмастырылған кіріс мәліметтері алынады. Содан кейін 16 раундтан тұратын кезеңді бір және сол функцияны қолданып, түрлендіру және орынға қою операцияларын қолданадады. Соңғы 16 раундтың шығысында 6 битті тізбек алынады, онда ашық мәтін және кілт функциялары болады. Алынған мәліметтер тізбегінің сол және оң жартылары орындарымен ауысады, алдын ала нәтиже құрайды. Бұл алдын ала нәтиже IP_-1 түрлендіру арқылы өтеді, ол бастапқыға кері, нәтижесінде шифрленген мәтін 64 битті блок алынады. Бастапқы және соңғы түрлендіруді алып тастаса, DES құрылымы Файстель шифр құрылымымен бірдей болады.

2 суреттің оң жағында 56 битті кілттің қалай қолданылатыны көрсетілген. Алдымен кілтке де түрлендіру функциясы қолданылады. Солға циклдік қозғалу көмегінен кейін кілтасты (подключ K_i) генерирленеді. Түрлендіру функциясы барлық раундта біреу ғана, бірақ генерирленген кілтастылар солға қарай циклдік қозғалу нәтижесінде әр түрлі болып кетеді және оның кірісіне кілттің әр түрлі биттері түседі.

   

(а) бастапқы түрлендіру (IP)

 

 

 

 

 

 

 

 

 

(б) бастапқыға кері (IP-1)

 

 

 

 

 

 

 

 

(в) кеңейтілумен түрлендіру (Е)

 

 

 

 

 

 

 

 

(г) түрлендіру (Р)

 

DES DES

 

 

 

 

Бастапқы түрлендіру

Бастапқы түрлендүру де, оған керісі де кестелік әдіспен  беріледі. Берілген екі функция кестелерінде бір-біріне сәйкес кері болып табылатынына көз жеткізу үшін, келесі 64-битті кіріс М тізбекті қарастырамыз.

 

М₁  М₂ М₃ М₄ М₅ М₆ М₇ М₈ 

М₉ М₁₀ М₁₁ М₁₂ М₁₃ М₁₄ М₁₅ М₁₆

М₁₇ М₁₈ М₁₉ М₂₀ М₂₁ М₂₂ М₂₃ М₂₄

М₂₅ М₂₆ М₂₇ М₂₈ М₂₉ М₃₀ М₃₁ М₃₂ 

М₃₃ М₃₄ М₃₅ М₃₆ М₃₇ М₃₈ М₃₉ М₄₀

М₄₁ М₄₂ М₄₃ М₄₄ М₄₅ М₄₆ М₄₇ М₄₈

М₄₉ М₅₀ М₅₁  М₅₂ М₅₃ М₅₄ М₅₅ М₅₆

М₅₇ М₅₈ М₅₉ М₆₀ М₆₁ М₆₂ М₆₃ М₆₄

 

Бұнда әрбір М_і  бір екілік санды ұсынады. Орын ауыстырудан кейін Х=IP(M) тізбегін келесі түрде аламыз.

 

М₅₈ М₅₀ М₄₂ М₃₄ М₂₆ М₁₈ М₁₀  М₂      М₆₀ М₅₂ М₄₄ М₃₆ М₂₈ М₂₀ М₁₂ М₄      М₆₂ М₅₄ М₄₆ М₃₈ М₃₀ М₂₂ М₁₄ М₆     

М₆₄ М₅₆ М₄₈ М₄₀ М₃₂ М₂₄ М₁₆ М₈     

М₅₇ М₄₉ М₄₁ М₃₃ М₂₅ М₁₇ М₉ М₁   

М₅₉ М₅₁ М₄₃ М₃₅ М₂₇ М₁₉ М₁₁ М₃  

М₆₁ М₅₃ М₄₅ М₃₇ М₂₉ М₂₁ М₁₃  М₅  

М₆₃ М₅₅ М₄₇ М₃₉ М₃₁ М₂₃ М₁₅ М₇

 

Кері орын алмастыруды  қолданып Y=IP^-1(X)=IP^-1(IP(M)) аламыз және жеңіл тексеруден көз жеткізуге болады, шығыста жоғарыдағыдайға сәйкес, тура биттер тізбектелінеді.

 

Шифрлеу алгоритмінің бөлшектері

3 суретте итерация кезінде қолданылатын алгоритмнің ішкі құрылымы көрсетілген. Әрбір 64 мәннің сол(R) және оң(L) бөліктері тәуелсіз 32-битті өлшемдері ретінде қарастырылады. Кез келген Файстель классикалық шифры сияқты әрбір итерация кезінде орындалатын операциялар келесі формуламен жазуға болады:

L_i=R_i-1,

R_i=L_i-1 +F(R_i-1, K_i).

Кез келген раунд үшін K_i кілті ұзындығы 48 битке тең, ал шығыс элементтерінің R ұзындығы 32 бит. R мәнінің 16 биті қайталануында жатқан кеңейтумен орын ауыстыруы R кіріс мәні кесте көмегімен 48 битке дейін кеңейеді. Алынған 48-битті мән XOR операция көмегімен K_i мен бірге қосылады. Нәтижесінде, ұзындығы 48 битке тең мән 32-битті мәнді генерирлеп ауыстыру функциясына беріледі.

F функциясында S-матрицасының ролі 4 суретте маңызы ашылады. Ауыстыру механизмі сегіз S-матрицасы жиынымен анықталады, оның әрбіреуі кіріске 6 битті мәліметтерді алады және 4-битті нәтижені шығарады. Түрлендіру келесідей ережеге сәйкес жүргізіледі. Бірінші және соңғы биттер кіріс мәндері S-матрицасы үшін 2-битті екілік санды ұсынады, S_і үшін кесте төрт жолмен анықталады да төрт ауыстырудың біреуін береді. Қалған төрт битті баған анықтайды. Баған мен жолдың қиылысында берілген ондық мән 4-биттік көрсетілуде нәтиже болады. Мысалы, егер S_і кірісіне 011001 мәні түссе, онда 01 (ондық 1) жолын және 1100 (ондық 12) бағанасын береді. 1 жол және 12 баған қиылысында 9 мәні орналасқан, сондықтан нәтиже еклік көрсетілуде 1001 түріне ие болады.

1 кесте. DES алгоритмі S-матрицасының  анықталуы.

 

S₁

 

 

 

 

S₂

 

 

 

S₃

 

 

 

 

S₄

 

 

 

 

S₅

 

 

 

 

S₆

 

 

 

 

S₇

 

 

 

S₈

 

 

 

 

S-матрицасының әрбір  жолы кері қайтатын орын алмастыруды  анықтайды. Беріліп отырған алмастыруларды  түсіну үшін 0 жолына S-матрицасы  қойылғанын көруге болады.