Популарно познатиот термин „перформанси на процесорот“ е објективен, пресметан параметар кој се мери во флопови. Сепак, повеќето луѓе го мерат во гигахерци, наивно верувајќи дека тие се иста работа. Никој не го знае терминот „изведба на код“, и веднаш ќе објаснам зошто.

Причината е што неодамна го смислив и сè уште никому не сум кажал за тоа. Сепак, перформансите на кодот, како и перформансите на процесорот, имаат објективни карактеристики што може да се измерат. Оваа статија е конкретно за перформансите на кодот извршен од јадрото на процесорот.

Како се мери перформансите на кодот? Бидејќи јас бев првиот што зборував за ова, по право на откривачот ќе го измерам во RTT единици;).

Сега сериозно. Во современите процесори, главните трансформации се операциите на 32-битни броеви; сè друго е, во голема мера, егзотично. Затоа, ќе ја земеме предвид главната работа - операции со 32-битни броеви. Колку 32-битни операции мислите дека едно модерно процесорско јадро може да изврши истовремено?

Ученикот ќе одговори - еден, неговиот учител ќе помисли и ќе каже дека се четири, стручниот - дека досега има само дванаесет операции.

Значи, програмскиот код што ги вчитува сите единици за извршување на процесорот истовремено во текот на целото време на извршување на кодот ќе има перформанси од 12 RTT. Максимално! Да бидам искрен, никогаш досега не сум напишал таков код, но во оваа статија ќе се обидам да се потрудам.

Ќе докажам дека кодот со истовремено извршување на дванаесет 32-битни операции е возможен

Програмскиот код што користи еден активирач во јадрото на процесорот природно ќе има перформанси од 1 RTT. Програмите генерирани од јазични компајлери на високо ниво и толкувачи на виртуелни машини можат да се пофалат со такви перформанси на кодот. Нема потреба да се претпоставува дека индикаторот за оптоварување на процесорот, кој може да се види во менаџерот на задачи на ОС, може да послужи како објективен критериум за ефикасноста на кодот. Оптоварувањето на јадрото на процесорот може да биде 100%, но програмскиот код ќе користи една извршна единица во него (изведба 1 RTT). Во овој случај, при 100% оптоварување, јадрото на процесорот ќе работи со 1/12 од неговите максимални перформанси. Со други зборови, кога Управникот со задачи на Windows го покажува максималното оптоварување на процесорот, неговите реални перформанси може да варираат од 1 до 12 RTT. Ако видите 100% оптоварување на кое било јадро на процесорот во прозорецот за перформанси, погрешно е да се претпостави дека сите актуатори работат во ова јадро, воопшто не!

Единствениот критериум за индиректно оценување на работата на јадрото на процесорот при максимални перформанси може да биде неговата потрошувачка на енергија и, како последица на тоа, бучавата на ладилникот. Сега, ако ладилникот е бучен, тогаш да, товарот отиде до максимум. Сепак, време е да завршиме со општите концепти и да продолжиме со суровата практика.

Традиционална имплементација на ГОСТ 28147-89

Не сум професионалец во областа на информациската безбедност, но сепак сум запознаен со темата за шифрирање. Бев инспириран да проучувам шифрирање на симетрични текови конкретно од разговори со професионален криптограф кого длабоко го почитувам. И, откако ја зафатив оваа тема, се обидов да го направам тоа добро, и не само добро, туку и брзо, извршувајќи го максималниот број операции по единица време. Со други зборови, се соочив со задача да напишам програмски код со максимална вредност на RTT.

Криптографската трансформација во согласност со ГОСТ 28147-89 се користи за шифрирање на информации во каналите за комуникација и на дисковите.

Во моментов, широко се користи софтверската имплементација на овој ГОСТ на RON на централниот процесор. Во познати методи за спроведување на ГОСТ, сите тајни информации (клучеви за шифрирање, блокови за замена) се наоѓаат во RAM меморијата. Ова ја намалува веродостојноста на шифрирањето, бидејќи со депонијата на RAM меморијата може целосно да се откријат сите тајни елементи на крипто-трансформацијата. Покрај тоа, методот има ограничувања во изведбата поради локацијата на главните објекти за конверзија на крипто во ОП и нецелосното вчитување на извршните единици на ALU. Современите процесори, спроведувајќи ја крипто процедурата користејќи добро познат метод, можат да обезбедат брзина на шифрирање од 40-60 мегабајти во секунда. И ако навистина го разбереме до крај, причината за ниските перформанси и слабата безбедност на конверзијата на крипто е софтверската имплементација на блокот за замена. За неговиот опис во ГОСТ, видете на Сл. 1.

Според клаузулата 1.2 од ГОСТ, овој блок имплементира тетрадни (четири бита) пермутации во 32-битен збор, но архитектурата на процесорот x86/64 и неговиот инструкциски систем не се способни ефикасно да манипулираат со тетради.

За софтверска имплементација на блокот за замена, се користат специјални табели во RAM меморија, подготвени во фазата на иницијализација на криптофункцијата. Овие табели ги комбинираат заменските јазли на соседните тетради во табели од 8 × 8-битни бајти, со што се ставаат четири табели од 256 бајти во RAM меморијата.

Во понапредните имплементации, овие табели се со големина од 1024 бајти (256 зборови од четири бајти). Ова беше направено со цел да се имплементира во табелите дополнително циклично поместување за 11 позиции на 32-битниот збор добиен како резултат на замена (следната операција на алгоритмот за конверзија според ГОСТ). Пример за имплементација на ГОСТ со користење на овој метод е прикажан во Додаток 1 (на диск).

Информациите за блокот за замена се тајна компонента на криптофункцијата (како што е формулирана во ГОСТ, видете Сл. 2).

Поставувањето на овие табели со клучевите на блокот за замена во ОП е во спротивност со барањата на ГОСТ (клаузула 1.7), бидејќи тајните информации стануваат достапни за програмите од трети лица што работат на компјутерската инсталација. ФСБ, кој исто така потврдува софтверски имплементации на шифрирање според ГОСТ, гледа на ова прекршување, благо речено, снисходливо. Ако, за да ги постави клучевите во ОП, FSB сè уште бара „смоквин лист“ - маскирање на клучевите со помош на операцијата XOR, тогаш ништо не е потребно за блокови за замена во ОП; тие се складираат во јасна форма.

Накратко, ФСБ дозволува такви софтверски имплементации на криптопроцедури да поминат, и покрај очигледното намалување на безбедноста на таквото решение и директно кршење на сопствените барања според ГОСТ (клаузула 1.7). И ова и покрај добро познатите методи за кршење на шифрите со земање мемориски депонија...

Ќе се вратиме на прашањето за складирање на клучеви и блокови за замена во внатрешните регистри на процесорот малку подоцна (има убаво и брзо решение), но засега ќе ги складираме клучевите за шифрирање само во регистрите MMX, ова е посигурно.

Но, доволно од текстовите, она што е важно за темата што се разгледува е дека овој програмски код има изведба од 1 RTT. Сега да напишеме код со перформанси на 2 RTT.

Повеќенаменска имплементација на ГОСТ 28147-89

Единствениот начин да се забрзаат крипто процедурите во познатиот алгоритам е да се воведе мултинишка. Поентата на оваа промена во имплементацијата на алгоритмот е да се пресметаат неколку блокови податоци паралелно.

Повеќето програмери под паралелна обработка подразбираат исклучиво работа на неколку процесорски јадра, синхронизирани преку прекини и семафори во меморијата.

Сепак, постои уште една опција за паралелна обработка на податоци на едно процесорско јадро. Дозволете ми да ја објаснам оваа неочигледна идеја.

Современите процесори вклучуваат најмалку две, па дури и три до шест аритметичко-логички единици. Овие ALU (FPU, адресни аритметички единици и така натаму) можат да работат независно еден од друг; единствениот услов за нивно паралелно функционирање е софтверските објекти на кои работат да бидат разделени. Со други зборови, во инструкциите кои истовремено извршуваат ALU, мемориските адреси и броевите на регистарот мора да бидат различни. Или, не треба да се врши запишување на споделени регистри и мемориски адреси до кои пристапуваат различни единици за извршување на процесорот.

Обемот на работа на сите ALU е контролиран од специјална хардверска единица во јадрото на процесорот - распоредувачот, кој го скенира извршниот код напред, до длабочина од 32-64 бајти. Ако распоредувачот открие инструкции што може да се извршуваат на ALU без конфликти, тогаш ги извршува истовремено на различни уреди за извршување. Во овој случај, бројачот на извршени команди ја означува командата за извршување (има неколку од нив во таква шема), по што сите команди се веќе извршени.

Повеќето програмски секвенци генерирани автоматски (од компајлери) не можат да ги вчитаат сите ALU и FPU лоцирани во јадрото на процесорот. Во овој случај, хардверот на процесорот е неактивен, што значително ги намалува неговите резултатски перформанси. Програмерите на процесори го разбираат ова и воведуваат режими за зголемување на основната фреквенција кога хардверот не е целосно искористен. Ова е исто така она за што се дизајнирани системите за хипертргување и јас ќе го користам овој систем за да го „притиснам“ кодот до максимум во иднина.

Компајлерите, дури и најоптимизираните, а уште повеќе моторите на виртуелната машина, не можат да генерираат оптимизиран код во однос на перформансите. Ваков оптимизиран код може да напише само програмер со инженерско знаење, а алатката за негово пишување е исклучиво асемблер.

Типична илустрација за можноста за извршување на неколку независни програмски нишки на едно процесорско јадро е имплементацијата на ГОСТ, извршена во две нишки на едно процесорско јадро. Идејата за кодот е едноставна: има два блока на податоци за шифрирање/дешифрирање, но едно процесорско јадро кое ќе ја изврши конверзијата. Можно е да се изврши конверзијата на овие два податочни блока последователно, и тоа е направено до ден-денес. Во овој случај, времето потребно за завршување на трансформациите се удвојува.

Но, можете да го направите тоа поинаку: алтернативни команди поврзани со обработката на различни блокови на податоци. Овие опции се претставени графички на Сл. 3.

На сликата, горниот пример го покажува вообичаениот редослед на обработка на два независни блока на податоци. Првиот блок се обработува прво, а потоа процесорот продолжува да го обработува вториот блок. Секако, добиеното време е еднакво на двојно повеќе од времето потребно за обработка на еден блок, а актуаторите на јадрото на процесорот не се целосно вчитани.

Следното е пример за преплетување на команди од различни нишки за обработка. Во овој случај, командите поврзани со различни блокови на податоци се испреплетени. Распоредувачот избира инструкции кои се независни една од друга и ги пренесува за извршување на ALU1 и ALU2. Групирањето на командите на првата и втората нишка на овие ALU се врши автоматски, бидејќи алгоритмот за работа на распоредувачот вклучува групација на команди поврзани со заеднички податоци на истиот извршен уред.

За да може таквиот програмски код да работи без прекин на ALU, неопходно е секоја програмска нишка да работи со свој сет на регистри. Кешот во оваа шема станува тесно грло (има само две излезни порти за податоци), така што ги складираме клучевите во MMX регистрите. Бидејќи во овој случај јазлите за замена (и поместување) во меморијата само се читаат, тие можат да бидат заеднички за двете програмски нишки.

Ова, се разбира, е многу поедноставено објаснување на принципот на паралелно извршување на програмските нишки на едно јадро; во реалноста, сè е многу покомплицирано. Во пракса, треба да ја земете предвид цевководната архитектура на актуаторите, ограничувањата за истовремен пристап до кешот и блокот на регистарот RON, присуството на адресни аритметички јазли, прекинувачи и многу повеќе... Значи, ова е тема за професионалци, кој може да се изброи на прсти... од едната рака.

Методот на паралелно шифрирање ефективно се спроведува само за 64-битен режим на работа на процесорот, бидејќи во овој режим има доволен број RON (дури 16 парчиња!). Пример за имплементација на ГОСТ со користење на овој метод е прикажан во Додаток 2 (на диск).

Јасно е дека оваа имплементација на ГОСТ има изведба на код од 2 RTT кодови. Сега да видиме како ова влијае на времето на извршување.

Циклусот на шифрирање за еден поток (Додаток 1) е 352 тактни циклуси и за ова време се пресметуваат 8 бајти податоци; за имплементација со две нишки на ГОСТ (Додаток 2) потребни се 416 процесорски циклуси, но се пресметуваат 16 бајти. Така, добиената брзина на конверзија се зголемува од 80 на 144 мегабајти за процесор од 3,6 GHz.

Се појавува интересна слика: кодот содржи точно двојно повеќе команди, а извршува само 15% подолго, но мислам дека читателите веќе ја разбрале причината за овој феномен...

Теоретски, кодот од вториот пример треба да се изврши во ист број циклуси на такт како и кодот од првиот пример, но јазолот за распоредувач е развиен од инженери на Интел, но тие се исто така луѓе, и сите сме далеку од совршени. Значи, можно е да се оцени ефективноста на нивното создавање. Овој код ќе работи и на AMD процесор и можете да ги споредите нивните резултати.

Ако некој не го прифати мојот збор за тоа, тогаш за таквите неверници, на дискот се вклучени програми за тестирање со бројачи на часовници. Програмите се во изворен код, се разбира во асемблер, па има можност да си ги проверам зборовите, а воедно да погледнете некои од триковите на професионалното кодирање.

Користење на SSE регистри и AVX команди на современи процесори за имплементација на ГОСТ 28147-89

Современите процесори на архитектурата x86/64 вклучуваат збир на SSE регистри со големина од 16 бајти и специјализирани FPU (најмалку два) за извршување на различни операции на овие регистри. Можно е да се имплементира ГОСТ на оваа опрема, и во овој случај, јазлите за замена може да се постават не во форма на табели во RAM меморијата, туку директно на посветени регистри на SSE.

Еден регистар на SSE може да собере две табели од 16 редови одеднаш. Така, четири регистри за SSE целосно ќе ги сместат сите табели за замена. Единствениот услов за такво поставување е условот за испреплетување, според кој тетрадите од ист бајт мора да се стават во различни регистри на SSE. Дополнително, препорачливо е да се постават ниските и високите тетради на влезните бајти, соодветно, во ниските и високите тетради на бајтите на регистрите SSE.

Овие барања се одредуваат со оптимизација за постојниот сет на команди AVX. Така, секој бајт од регистарот SSE ќе содржи две тетради што одговараат на различни бајти на влезниот регистар на блокот за замена, додека позицијата на бајтот во регистарот SSE единствено одговара на индексот во табелата за замена на блокот за замена.

На сл. 4.

Поставувањето тајни информации за заменските јазли на регистрите на SSE ја зголемува безбедноста на крипто-процедурата, но целосна изолација на овие тајни информации е можна доколку се исполнети следните услови:

• Јадрото на процесорот е префрлено во режим на домаќин на хипервизор, а блокот за прекини (APIC) е присилно оневозможен во него. Во овој случај, јадрото на процесорот е целосно изолирано од ОС и апликациите што работат на компјутерската инсталација.
• SSE регистрите се вчитуваат и компјутерското јадро е изолирано пред да започне оперативниот систем; оптимално е да се извршат овие постапки од доверливиот модул за подигање (TLM).
• Програмите за криптопроцедури во согласност со ГОСТ се наоѓаат во непроменлива мемориска област на компјутерската инсталација (било BIOS или во флеш меморија на MDZ).

Усогласеноста со овие барања ќе обезбеди целосна изолација и непроменливост на програмскиот код на криптопроцедурите и тајните информации што се користат во нив.

За ефикасно земање примероци од тетрадни SSE регистри, се користат преклопниците со повеќе влезни бајти вклучени во блоковите на FPU. Овие прекинувачи овозможуваат пренос од кој било извор бајт до кој било дестиниран бајт, користејќи индекси лоцирани во посебен регистар на индекси SSE. Покрај тоа, преносот се врши паралелно за сите 16 бајти од регистарот на приемници SSE.

Имајќи јазли за замена за складирање на SSE регистрите и повеќевлезен прекинувач во блоковите FPU, можно е да се организира следната трансформација во блокот за замена (сл. 5).

Во оваа шема, влезниот регистар во секоја тетрада ја одредува адресата за соодветниот прекинувач, кој пренесува информации од дисковите на замените јазли до излезниот регистар преку податочната магистрала. Оваа шема може да се организира на три начини:

• Направете соодветен дизајн на чип, но ова е фантастично за нас.
• Репрограмирањето на микрокодот и создавањето сопствена команда на процесорот за имплементирање на оваа функција на постоечки процесори повеќе не е фантазија, но, за жал, е нереално во сегашните услови.
• Напишете програма користејќи официјални команди AVX. Опцијата можеби не е многу ефикасна, но може да се имплементира „овде и сега“. Така, тоа е она што ќе го направиме следно.

Работата на прекинувачите се контролира со специјална команда со три адреси AVX VPSHUFB. Неговиот прв операнд е примачот на информации од прекинувачите, вториот е изворот на кој се поврзани влезовите на прекинувачите. Третиот операнд е контролен регистар за прекинувачи, чиј секој бајт е поврзан со соодветен прекинувач; вредноста во неа го одредува бројот на насоката од која прекинувачот чита информации. За опис на оваа команда од официјалната документација на Интел, видете на Сл. 5. На сл. Слика 6 покажува дијаграм за тоа како функционира оваа команда - прикажани се само половина од SSE регистрите, за втората половина сè е слично.

Прекинувачот ги користи само најниските четири бита за да ја одреди насоката на комутацијата, последниот бит во секој бајт се користи за да го принуди соодветниот бајт на примачот на нула, но оваа функција на прекинувачот сè уште не е барана во нашиот случај.

Напишана е програма за земање примероци на тетради преку прекинувачи на FPU, но јас дури и не ја ставив во апликацијата - тоа е премногу патетично. Да се ​​има 128-битен регистар и да се користат само 32 бита во него е непрофесионално.

Како што велат, „Нашата целна линија е хоризонтот“, па истиснете го, истиснете го... ќе го притиснеме и ќе го ставиме во вреќи!

Ова не е игра со зборови, туку сурова реалност на FPU - SSE регистрите можат да се поделат на еднакви делови и истите трансформации да се извршат на овие делови со една команда. За да може процесорот да го разбере ова, постои магична буква „P“ - пакет што се става пред командата мнемоника, и не помалку магични букви „Q“, „D“, „W“, „B“, кои се ставаат на крајот и се декларираат На кои делови се поделени SSE регистрите во оваа команда?

Ние сме заинтересирани за сериски режим со SSE регистар поделен на четири 32-битни блокови; Соодветно на тоа, сите команди ќе бидат со префикс „P“, а на крајот со симболот „D“. Ова овозможува да се обработат четири 32-битни блокови паралелно со една процесорска команда, односно да се пресметаат четири блокови на податоци паралелно.

Програмата што го имплементира овој метод е достапна во Додаток 3, со сите објаснувања таму.

Сепак, притиснете толку многу! Современите процесори имаат најмалку два FPU, а може да се користат две независни инструкциски нишки за целосно да се вчитаат. Ако правилно ги менувате командите од независни нишки, можете целосно да ги вчитате двете FPU единици со работа и да добиете осум паралелни обработени текови на податоци одеднаш. Ваква програма е напишана, а може да се погледне во Додаток 4, но треба внимателно да ја гледате - може да полудите. Ова е она што се нарекува „шифрата не е за секого...“.

Прашање за цената

Употребата на SSE регистри за складирање на јазли за замена е разбирлива - обезбедува одредена гаранција за изолација на тајните информации, но значењето на пресметувањето на самата криптофункција на FPU не е очигледно. Затоа, времето на извршување на стандардните процедури беше мерено со методот на директна замена во согласност со ГОСТ за четири и осум нишки.

За четири нишки, добиена е брзина на извршување од 472 процесорски циклуси. Така, за процесор со фреквенција од 3,6 GHz, една нишка се пресметува со брзина од 59 мегабајти во секунда, а четири нишки, соодветно, со брзина од 236 мегабајти во секунда.

За осум нишки, добиена е брзина на извршување од 580 процесорски циклуси. Така, за процесор од 3,6 GHz, една нишка се брои со 49 мегабајти во секунда, а осум нишки со 392 мегабајти во секунда.

Како што читателот може да види, кодот во примерот #3 има перформанси од 4 RTT, а кодот во примерот #4 има перформанси од 8 RTT. Во овие примери на SSE регистрите, шаблоните се исти како кога се користи RON, само распоредувачот ја намалил својата ефикасност. Во моментов обезбедува зголемување на времетраењето за 20%, додека ја удвојува должината на кодот.

Покрај тоа, овие резултати се добиени со користење на универзални AVX команди достапни и во Intel и во AMD процесорите. Ако оптимизирате за AMD процесор, резултатот ќе биде многу подобар. Звучи спротивно на трендот, но сепак е вистина, а еве зошто: AMD процесорите имаат дополнителен сет на инструкции, таканаречената XOP екстензија, а во овој дополнителен сет инструкции има и такви кои значително ја поедноставуваат имплементацијата на Алгоритам ГОСТ.

Ова се однесува на командите за логичко поместување на бајт и рафално циклично поместување на двојни зборови. Во примерите дадени во Прилозите 3 и 4, се користат низи од универзални команди кои ја спроведуваат потребната трансформација: во првиот случај, една „дополнителна“ команда, а во другиот случај, четири дополнителни команди одеднаш. Значи, постојат резерви за оптимизација, и тоа значителни.

Кога станува збор за понатамошна оптимизација, вреди да се запамети присуството на 256-битни регистри (регистри YMM), со кои теоретски можете да ја удвоите брзината на пресметките. Но, засега ова е само перспектива; во моментот, процесорите многу забавуваат при извршувањето на 256-битни инструкции (FPU-ите имаат ширина на патеката од 128 бита). Експериментите покажаа дека на современите процесори, броењето 16 нишки на регистрите на YMM не дава никаква корист. Но, ова е само за сега; на новите модели на процесор, перформансите на 256-битни инструкции несомнено ќе се зголемат, а потоа употребата на 16 паралелни нишки ќе стане препорачлива и ќе доведе до уште поголемо зголемување на брзината на крипто процедурата .

Теоретски, може да сметате на брзина од 600–700 мегабајти во секунда ако процесорот има два FPU со ширина на работна патека од 256 бита секој. Во овој случај, можеме да зборуваме за пишување код со ефикасност од 16 RTT, и ова не е фантазија, туку блиска иднина.

Мешан режим

Повторно се поставува прашањето за бројот на регистри; нема доволно од нив за промовирање на таков алгоритам. Но, режимот на хипертргување ќе ни помогне. Јадрото на процесорот има втор сет на регистри достапни во режим на логички процесор. Затоа, ќе го извршиме истиот код на два логички процесори одеднаш. Во овој режим, се разбира, нема да имаме повеќе актуатори, но поради алтернација можеме да добиеме целосно оптоварување на сите актуатори.

Овде не можете да сметате на зголемување од 50%, тесно грло е кеш меморијата каде што се чуваат технолошките маски, но сепак можете да добиете зголемување од 100 дополнителни мегабајти. Оваа опција не е прикажана во додатоците (макроата се слични на оние што се користат во кодот 8 RTT), но е достапна во програмските датотеки. Значи, ако некој не верува во можноста за шифрирање со брзина од 500 мегабајти во секунда на едно процесорско јадро, нека работи тест датотеки. Има и текстови со коментари за никој да не помисли дека лажам.

Овој фокус е возможен само на процесорите на Intel; AMD има само две FPU единици на два процесорски модули (аналогно на режимот на хипертргување). Но, има уште четири ALU кои би било грев да не се користат.

Може да ги ставите модулите на процесорот Bulldozer во режим сличен на режимот на хипертргување, но да ја извршите конверзијата во RON на различни модули во една нишка, и на SSE регистрите во друга нишка и да ги добиете истите 12 RTT. Не ја тестирав оваа опција, но мислам дека 12 RTT код ќе работи поефикасно на AMD. Заинтересираните можат да го пробаат; програмите за тестирање може лесно да се прилагодат да работат на „Булдожери“.

На кого му треба?

Сериозно прашање, но со едноставен одговор - ова им треба на сите. Наскоро сите ќе бидеме закачени на облаците, таму ќе складираме и податоци и програми, а таму, ох, колку сакаме да создадеме свое, приватно катче. За да го направите ова, ќе мора да го шифрирате сообраќајот, а брзината на конверзија на крипто ќе биде главниот одлучувачки фактор за удобна работа во облакот. Нашиот избор на алгоритам за шифрирање е мал - или GOST или AES.

Згора на тоа, доволно чудно, алгоритмот за шифрирање AES вграден во процесорите се покажува многу побавен; тестовите покажуваат брзини од 100-150 мегабајти во секунда, а тоа е со хардверска имплементација на алгоритмот! Проблемот лежи во броењето со една нишка и блокот за замена, кој работи на бајти (табела од 256 редови). Значи, ГОСТ излегува дека е поефективен кога е имплементиран на архитектурата x86/64, кој би помислил...

Ова е ако зборуваме за постигнатото ниво на брзина на шифрирање. И ако ги имаме на ум теоретските усовршувања во областа на зголемување на ефикасноста на кодот, тогаш најверојатно никому не му треба ова. Практично нема специјалисти на ниво 3-6 RTT, компајлерите генерално генерираат код на ниво од 1-2,5 RTT, а мнозинството програмери не знаат асемблер, па дури и да го знаат неговиот правопис, тие не го разбираат дизајнот на модерен процесор. И без ова знаење, не е важно дали е асемблер или некој вид SI-sharp.

Но, не е сè толку тажно: крајната линија по една недела непроспиени ноќи е нов алгоритам за спроведување на ГОСТ, што би било грев да не се патентира. А пријавите за патенти (вкупно три) се веќе завршени и поднесени, па, господа, бизнисмени, редете се - жените и децата добиваат попуст.

). Во исто време, во руските медиуми и блогови на руски корисници, расте бројот на белешки за овој алгоритам: и ги покриваат резултатите од нападите врз рускиот стандард со различен степен на доверливост и содржат мислења за неговите оперативни карактеристики. Авторите (и, следствено, читателите) на овие белешки често добиваат впечаток дека домашниот алгоритам за шифрирање е застарен, бавен и има пропусти што го прават значително поподложен на напади од странските алгоритми за шифрирање со слична должина на клучот. Со оваа серија белешки би сакале да ви кажеме во достапна форма за моменталната состојба со рускиот стандард. Првиот дел ќе ги опфати сите напади на ГОСТ 28147-89 познати на меѓународната криптографска заедница и тековните проценки на неговата сила. Во идните публикации, ќе ги разгледаме и својствата на стандардот од гледна точка на способноста да се градат ефективни имплементации.

Никола Куртоа - „големиот и страшниот“

Да почнеме со приказна за активностите на Николас Куртоа, кој е автор на цела серија дела посветени на рускиот стандард за шифрирање блокови ().

Во октомври 2010 година започна процесот на разгледување на вклучувањето на алгоритмот ГОСТ 28147-89 во меѓународниот стандард ISO/IEC 18033-3. Веќе во мај 2011 година, на електронската архива ePrint се појави напис од познатиот криптограф Николас Куртоа, обележан со многу двосмислен однос кон него од светската криптографска заедница. Публикациите на Куртоа се тажен пример за манипулација со концептите, кои не откриваат никакви нови својства на предметниот објект, но со тврдење за сензација предизвикуваат ширење на погрешни мислења за неговите вистински својства во некомпетентна средина.

Алгебарски метод

Расудувањето на Куртоа е изградено околу две класи методи на криптоанализа: алгебарски методи и диференцијални. Ајде да ја разгледаме првата класа на методи.

На поедноставен начин, методот на алгебарска криптанализа може да се опише како компилација и решение на голем систем на равенки, чиишто решенија одговараат на целта на криптоаналитичарот (на пример, ако системот се составува со користење на еден пар на обичен текст и шифриран текст, тогаш сите решенија на овој систем одговараат на клучевите на кои овој обичен текст се претвора во овој е шифриран). Односно, во случајот со проблемот на криптоанализа на блок шифра, суштината на алгебарскиот метод на криптоанализа е дека клучот е пронајден како резултат на решавање на систем на полиномни равенки. Главната тешкотија е да може да се создаде што е можно поедноставен систем, земајќи ги предвид карактеристиките на одредена шифра, така што процесот на негово решавање трае што е можно помалку време. Овде клучната улога ја играат карактеристиките на секоја специфична шифра што се анализира.

Алгебарскиот метод што го користел Куртоа може накратко да се опише на следниов начин. Во првата фаза, таквите својства на ГОСТ 28147-89 се користат како постоење на фиксна точка за дел од трансформацијата на шифрирањето, како и таканаречена точка на рефлексија. Благодарение на овие својства, неколку парови се избрани од доволно голем број парови обичен текст-шифриран текст, што овозможуваат да се земат предвид трансформациите не на 32, туку само на 8 круга. Втората фаза е дека, врз основа на резултатите од 8 тркалезни трансформации добиени во првата фаза, се конструира систем на нелинеарни равенки, во кои клучните битови се непознати. Следно, овој систем е решен (ова звучи едноставно, но во реалноста е најодземниот дел од методот, бидејќи системот се состои од нелинеарни равенки).

Како што е наведено погоре, никаде во делото нема детален опис и анализа на сложеноста на втората и главна фаза на одредување на клучот. Комплексноста на втората фаза е таа што ја одредува сложеноста на целиот метод како целина. Наместо тоа, авторот ги дава озлогласените „факти“ врз основа на кои прави проценки за интензитетот на трудот. Се вели дека овие „факти“ се засноваат на експериментални резултати. Анализата на „фактите“ од работата на Куртоа во целина е дадена во делата на домашните автори. Авторите на ова дело забележуваат дека многу од „фактите“ на Куртоа презентирани без никакви докази биле откриени дека се лажни за време на експерименталното тестирање. Авторите на статијата отидоа подалеку и, следејќи го Куртоа, направија анализа на сложеноста на втората фаза користејќи добро основани алгоритми и проценки. Добиените проценки за сложеност ја покажуваат целосната неприменливост на презентираниот напад. Покрај домашните автори, во делото беа забележани и големите проблеми што ги има Куртоа со оценките и оправданоста на неговите методи, на пример.

Диференцијален метод

Да го разгледаме вториот метод на Куртоа, кој се заснова на диференцијална криптоанализа.

Општиот метод на диференцијална криптоанализа се заснова на искористување на својствата на нелинеарните пресликувања што се користат во криптографските примитиви, поврзани со влијанието на клучната вредност врз зависностите помеѓу разликите помеѓу паровите влезни и паровите излезни вредности на овие пресликувања. . Дозволете ни да ја опишеме главната идеја за диференцијалниот метод на криптографска анализа на блок шифра. Вообичаено, блок-шифрите ги трансформираат влезните податоци во фази користејќи голем број таканаречени тркалезни трансформации, а секоја тркалезна трансформација не го користи целиот клуч, туку само дел од него. Да разгледаме малку „отсечена“ шифра, која се разликува од оригиналната по тоа што го нема последниот круг. Да претпоставиме дека е можно да се утврди дека шифрирањето на два обични текстови кои се разликуваат во некои фиксни позиции со користење на таква „скратена“ шифра најверојатно ќе резултира со шифрирани текстови кои исто така се разликуваат во некои фиксни позиции. Ова својство покажува дека „скратената“ шифра најверојатно остава зависност помеѓу некои обични текстови и резултатите од нивното шифрирање. За да се врати дел од клучот користејќи ја оваа очигледна маана, неопходно е да можеме да ги криптираме претходно избраните обични текстови на клучот што сакаме да го вратиме (т.н. „избран напад на обичен текст“). На почетокот на постапката за „отварање на клучот“, случајно се генерираат голем број на парови обични текстови, кои се разликуваат во истите фиксни позиции. Сите текстови се шифрирани со помош на „целосна“ шифра. Добиените парови на шифриран текст се користат за враќање на оние клучни битови што беа користени во последната рунда трансформација, како што следува. Користејќи некоја случајно избрана вредност на саканите битови на копчињата, на сите шифрирани текстови се применува трансформација инверзна на трансформацијата на последниот круг. Всушност, ако ја погодиме саканата вредност на клучните битови, ќе го добиеме резултатот на „скратена“ шифра, а ако не погодивме, всушност ќе ги „шифрираме податоците уште повеќе“, што само ќе го намали зависност помеѓу блоковите наведени погоре (разликата е во некои фиксни позиции). Со други зборови, ако меѓу резултатите од таквата „дополнителна обработка“ на шифрирани текстови имало доста парови кои се разликуваат во фиксните позиции што ни се познати, тогаш тоа значи дека сме ги погодиле потребните клучни битови. Во спротивно, ќе има значително помалку такви парови. Бидејќи само дел од клучот се користи во секој круг, пребаруваните битови (т.е. клучните битови користени во последниот круг) не се толку бројни како битовите во целосниот клуч и едноставно може да се повторат со повторување на чекорите погоре. . Во овој случај, еден ден дефинитивно ќе се сопнеме на правилното значење.

Од горенаведениот опис произлегува дека најважното нешто во методот на диференцијална анализа се бројките на токму тие позиции во обичните и шифрираните текстови, разликите во кои играат клучна улога во враќањето на клучните битови. Основното присуство на овие позиции, како и множеството на нивните броеви, директно зависи од својствата на оние нелинеарни трансформации што се користат во која било блок шифра (обично целата „нелинеарност“ е концентрирана во т.н. S-кутии или јазли за замена).

Куртоа користи малку изменета верзија на диференцијалниот метод. Веднаш да забележиме дека Куртоа ја прави својата анализа за S-кутии кои се разликуваат од сегашните и од оние предложени во ISO. Работата обезбедува диференцијални карактеристики (оние броеви во кои блоковите треба да се разликуваат) за мал број кругови. Оправдувањето за проширување на карактеристиките за повеќе кругови, како и обично, се заснова на „факти“. Куртоа изразува, повторно, со ништо друго освен неговиот авторитет, неподдржана претпоставка дека менувањето на S-кутиите нема да влијае на отпорот на ГОСТ 28147-89 против неговиот напад (додека од непознати причини, S-кутиите од 1-виот работен нацрт на не беше земено предвид додавањето на стандардот ISO/IEC 18033-3). Анализата спроведена од авторите на статијата покажува дека дури и ако ги земеме неоснованите „факти“ на Куртоа за верата и го анализираме ГОСТ 28147-89 со други S-блокови, нападот повторно се покажува дека не е подобар од целосно пребарување.

Детална анализа на делата на Куртоа со детално потврдување на неоснованоста на сите изјави за намалување на отпорноста на рускиот стандард беше извршена во делата [,].

Во исто време, дури и самиот Куртоа ја признава апсолутната непрецизност во пресметките! Следниот слајд е преземен од презентацијата на Куртоа во делот за кратки известувања за FSE 2012 година.

Треба да се напомене дека работата на Куртоа, исто така, постојано беше критикувана од странски истражувачи. На пример, неговата работа за конструирање напади на алгоритам за шифрирање блок AES со помош на методот XSL ги содржеше истите фундаментални недостатоци како и работата на анализата на рускиот стандард: повеќето проценки за интензитетот на трудот се појавуваат во текстот целосно неосновани и неосновани - детално критиката може да се најде, на пример, во работата. Дополнително, самиот Куртоа признава широко распространето одбивање да ја објави својата работа на големи конференции за криптографија и во етаблирани списанија со рецензија, честопати оставајќи му само можност да зборува во делот за кратки огласи. На пример, можете да прочитате за ова во делот 3 од делото. Еве неколку цитати од самиот Куртоа во врска со неговата работа:

• „Мислам дека публиката на Asiacrypt нема да почувствува дека е интересно“. Рецензент на Asiacrypt 2011 година.
• „… има голем, голем, голем проблем: овој напад, кој е главниот придонес на трудот, веќе е објавен на FSE’11 (тоа беше дури и најдобриот труд),…“. Рецензент за Crypto 2011.

Така, професионалниот дел од меѓународната криптографска заедница го гледа квалитетот на работата на Куртоа со не помалку сомневање од, да речеме, изјавите на некои руски специјалисти за нивната способност да пробијат AES за 2.100, кои не се потврдени со никакви конзистентни пресметки, или најнов „доказ“ за хипотеза на две страници за нееднаквоста на класите на сложеност P и NP.

Напади на Исобе и Динур-Данкелман-Шамир

Општата идеја за нападите Isobe () и Dinur-Dankelman-Shamir (во натамошниот текст: DDS напад) () е да се конструира за одреден (зависен од клучот) тесен сет на обични текстови еквивалентна трансформација на оваа група, која има структура поедноставна од самата трансформација на шифрирање. Во случајот на методот Isobe, ова е множество од 64-битни блокови x така што F 8 -1 (Swap(F 8 (z))) = z, каде z = F 16 (x), преку F 8 ( x) и F 16 ( x) ги означуваат првите 8 и првите 16 круга на шифрирање ГОСТ 28147-89, соодветно, преку Swap - операција на замена на половини од збор од 64 бајти. Ако обичниот текст е вклучен во овој сет, резултатот од целосната трансформација од 32 круга на ГОСТ 28147-89 се совпаѓа со резултатот од 16-круг, што е она што го користи авторот на нападот. Во случајот на методот DDS, ова е множество од x така што F 8 (x) = x (фиксна точка на трансформацијата F 8). За кој било обичен текст од овој сет, трансформацијата ГОСТ 28147-89 функционира исто како и последните 8 круга, што ја поедноставува анализата.

Комплексноста на нападот Isobe е 2.224 операции за шифрирање, нападот DDS е 2.192. Сепак, сите прашања за тоа дали нападите Isobe и DDS воведуваат нови ограничувања на условите за користење на нашиот алгоритам се отстранети со проценка на барањата за обемот на материјалот потребен за извршување на секој од нападите: методот Isobe бара 2 32 пара обичен текст. и шифриран текст, а за методот DDS - 2 64. Обработката на такви количини на материјал без промена на клучот е априори неприфатлива за која било блок шифра со должина на блок од 64: на материјал од волумен 2 32, земајќи го предвид проблемот со родендени (види, на пример, ), веројатноста за појава на повторените блокови е блиску до 1/2, што ќе обезбеди напаѓачот да може да извлече одредени заклучоци за обичните текстови од шифрираните текстови без да го одреди клучот. Присуството на 2 64 пара обични и шифрирани текстови добиени на еден клуч всушност му овозможува на непријателот да изврши операции за шифрирање и дешифрирање без воопшто да го знае овој клуч. Ова се должи на чисто комбинаторно својство: непријателот во овој случај ја има целата табела за конверзија на шифрирање. Оваа ситуација е апсолутно неприфатлива под какви било разумни услови за работа. На пример, во CryptoPro CSP постои техничко ограничување на обемот на шифриран материјал (без конверзија на клучот) од 4 MB (види). Така, строга забрана за користење клуч на материјал со таков волумен е вродена во која било блок шифра со должина на блок од 64 бита, и затоа нападите Isobe и DDS на никаков начин не го стеснуваат опсегот на употреба на алгоритмот ГОСТ 28147-89 притоа задржувајќи ја максималната можна јачина од 2.256.

Се разбира, треба да се забележи дека истражувачите (Изобе и Динур-Данкелман-Шамир) покажаа дека некои својства на алгоритмот ГОСТ 28147-89 овозможуваат да се пронајдат патеки за анализа што не биле земени предвид од креаторите на алгоритмот. Едноставната форма на распоредот на копчињата, која значително ја поедноставува задачата за конструирање ефективни имплементации, исто така дозволува некои ретки случаи на клучеви и обични текстови да конструираат поедноставни описи на трансформациите произведени од алгоритмот.

Работата покажува дека ова негативно својство на алгоритмот може лесно да се елиминира со целосно зачувување на оперативните карактеристики, но, за жал, тоа е составен дел на алгоритмот во неговата најчесто користена форма.

Забележете дека одредена небрежност во проценките на просечниот интензитет на трудот е присутна и во работата на Динур, Данкелман и Шамир. Така, кога се конструира напад, не се посветува должно внимание на следната точка: за значителен дел од клучевите, множеството од обични текстови x, така што F 8 (x) = x, е празно: едноставно може да нема фиксни точки за 8 рунди на трансформација. Постоењето на фиксни точки зависи и од изборот на јазли за замена. Така, нападот е применлив само за одредени замени јазли и клучеви.

Исто така, вреди да се спомене уште една работа со напад на ГОСТ 28147-89. Во февруари 2012 година, ажурирана верзија на статијата (од ноември 2011 година) се појави на електронската архива ePrint на меѓународната криптографска асоцијација, која содржеше нов напад на ГОСТ 28147-89. Карактеристиките на презентираниот напад се следните: волуменот на материјалот е 2 32 (како Isobe), а интензитетот на трудот е 2 192 (како DDS). Така, овој напад го подобри временскиот рекорден напад DDS во однос на волуменот на материјалот од 2 64 на 2 32. Одделно забележуваме дека авторите искрено ги презентирале сите пресметки со оправдување за сложеноста и обемот на материјалот. По 9 месеци, беше пронајдена фундаментална грешка во горенаведените пресметки, а од ноември 2012 година, ажурираната верзија на написот во електронската архива повеќе не содржи никакви резултати во однос на домашниот алгоритам.

Напаѓаат под претпоставка дека напаѓачот знае „нешто“ за клучевите

Конечно, забележуваме дека во литературата има и голем број дела (види, на пример, и ) посветени на нападите на ГОСТ 28147-89 во таканаречениот модел на поврзан клуч. Овој модел во основа ја содржи претпоставката дека напаѓачот може да добие пристап за анализа не само до парови отворени текстови и шифрирани со помош на саканиот клуч, туку и до парови отворени и шифрирани текстови добиени со помош на (исто така непознати) клучеви кои се разликуваат од саканиот по познат редовен начин (на пример, во фиксни битови позиции). Во овој модел, навистина е можно да се добијат интересни резултати за ГОСТ 28147-89, но во овој модел е можно да се добијат не помалку силни резултати за, на пример, стандардот AES, кој е најшироко користен во современите јавни мрежи ( види, на пример,). Забележете дека условите за извршување на овој тип на напад се јавуваат кога се користи шифра во одреден протокол. Треба да се забележи дека резултатите од овој вид, иако се од несомнен академски интерес од гледна точка на проучување на својствата на криптографските трансформации, всушност не се релевантни за практиката. На пример, сите алатки за заштита на криптографски информации сертифицирани од FSB на Русија ги исполнуваат најстрогите барања за шеми за генерирање на клучеви за шифрирање (види, на пример,). Како што е наведено во резултатите од анализата, ако има 18 поврзани клучеви и 2 10 пара блокови обичен текст и шифриран текст, сложеноста на целосно отворање на приватниот клуч, со веројатност за успех од 1-10 -4, всушност е 2 26 . Меѓутоа, ако горенаведените барања за развој на клучниот материјал се исполнети, веројатноста за наоѓање такви клучеви е 2 -4352, односно 24096 пати помала отколку ако едноставно се обидете да го погодите тајниот клуч при првиот обид.

Делата поврзани со моделот со поврзани клучеви вклучуваат и работа, која во 2010 година предизвика голема врева во руските електронски публикации, кои не страдаат од навиката внимателно да го проверуваат материјалот во трката за сензации. Резултатите презентирани во него не беа поддржани со никакво ригорозно оправдување, но содржеа гласни изјави за можноста да се хакира државниот стандард на Руската Федерација на слаб лаптоп за неколку секунди - генерално, написот е напишан во најдобрите традиции на Николас Куртоа. Но, и покрај апсолутно очигледната неоснованост на статијата за читателот кој е повеќе или помалку запознаен со основните принципи на научните публикации, токму за да ја увери руската јавност по работата Рудски напиша детален и темелен текст кој содржи сеопфатна анализа. на овој недостаток. Написот со самообјаснив наслов „За нултата практично значење на работата „Напад за обновување на клучот на целосна блок-шифра ГОСТ со нула време и меморија““ дава оправдување дека просечната сложеност на методот наведен не е помала од сложеноста. на целосно пребарување.

Сув остаток: што е издржливост во пракса?

Како заклучок, презентираме табела која содржи податоци за сите резултати од строго опишани и оправдани напади на ГОСТ 28147-89 познати на меѓународната криптографска заедница. Забележете дека сложеноста е дадена во операциите за шифрирање на алгоритмот ГОСТ 28147-89, а меморијата и материјалот се означени во алгоритамски блокови (64 бита = 8 бајти).

Напад	Интензитетот на трудот	Меморија	Потребен материјал
Изобе	2 224	2 64	2 32
Динур-Данкелман-Шамир, FP, 2DMitM	2 192	2 36	2 64
Динур-Данкелман-Шамир, ФП, ниска меморија	2 204	2 19	2 64
	2 224	2 36	2 32
Динур-Данкелман-Шамир, Рефлексија, 2DMitM	2 236	2 19	2 32
Целосно пребарување	2 256	1	4
Број на наносекунди од создавањето на универзумот	2 89

И покрај прилично обемниот циклус на истражување на полето на отпорност на алгоритмот ГОСТ 28147-89, во моментот не е познат ниту еден напад, чиишто услови за спроведување би биле остварливи со придружните оперативни барања за должина на блок од 64 бита. Ограничувањата на волуменот на материјалот што може да се обработи на едно копче што произлегува од параметрите на шифрата (должина на битот на клучот, должина на битот на блокот) се значително построги од минималниот волумен потребен за извршување на кој било моментално познат напад. Следствено, при исполнување на постојните оперативни барања, ниту еден од методите за криптоанализа предложени до датумот ГОСТ 28147-89 не дозволува одредување клуч со интензитет на труд помал од исцрпното пребарување.

Кај нас е воспоставен унифициран алгоритам за криптографско претставување на податоци за системи за обработка на информации во компјутерски мрежи, поединечни компјутерски системи и компјутери, кој е определен ГОСТ 28147-89.

Овој алгоритам за конверзија на криптографски податоци е 64-битен блок алгоритам со 256-битен клуч, дизајниран за имплементација на хардвер и софтвер, ги исполнува криптографските барања и не наметнува ограничувања за степенот на тајност на заштитените информации.

Кога се опишува алгоритмот, се користи следната нотација:

L и R - секвенци на битови;
LR е конкатенација на низите L и R, во кои битови од низата R следат битови од низата L;
(+) - модуло за собирање битови 2 (операција „ексклузивна ИЛИ“);
[+] - собирање на 32-битни броеви модуло 2 32;
(+) - собирање на 32-битни броеви модуло 2 32 -1.

Броевите се сумираат според следново правило:

A [+] B = A + B ако A + B< 2 32 ,
A [+] B = A + B - 2 32 ако A + B >= 2 32 . A (+) B = A + B ако A + B< 2^32 - 1, A {+} B = A + B - (2^32 - 1), если A + B >= 2^32 - 1.

Алгоритмот обезбедува четири режими на работа:

Во секој случај, 256-битен клуч K се користи за шифрирање на податоците, кои се претставени како осум 32-битни подклучеви K i:

K = K 7 K 6 K 5 K 4 K 3 K 2 K 1 K 0.

Дешифрирањето се врши со користење на истиот клуч како и шифрирањето, но процесот е обратен од процесот на шифрирање на податоците.

Лесен режим на замена

Првиот и најлесниот режим е замена. Податоците што треба да се шифрираат се поделени на 64-битни блокови. Постапката за шифрирање за блок од отворени податоци T 0 вклучува 32 циклуси (j=1...32).

Блокот T 0 е поделен на две секвенци од 32 бита: B(0)A(0), каде што B(0) се леви или битови од висок ред, A(0) се битови од десниот или низок ред.

Овие секвенци се внесуваат во погоните N 1 и N 2 пред почетокот на првиот циклус на шифрирање.

Првиот циклус (j=1) од процедурата за шифрирање за 64-битен блок на податоци е опишан со следните формули:

Овде i го означува бројот на повторување (i = 1, 2,..., 32).

Функцијата f се нарекува функција за шифрирање. Неговиот аргумент е збирот, модуло 2, од 32 броеви A(i), добиени на претходниот чекор на повторување, и клучниот број X(j) (димензијата на секој од овие броеви е 32 цифри).

Функцијата за шифрирање вклучува две операции на добиената 32-битна сума. Првата операција се нарекува замена K. Блокот за замена K се состои од 8 јазли за замена K(1) ... K(8) со меморија од по 64 бита. 32-битниот вектор кој пристигнува до блокот за замена е поделен на 8 секвенцијални 4-битни вектори, од кои секој се претвора во 4-битен вектор од соодветниот јазол за замена, што е табела од 16 цели броеви во опсегот 0. .15.

Влезниот вектор ја одредува адресата на редот во табелата, број од кој е излезниот вектор. 4-битните излезни вектори потоа секвенцијално се спојуваат во 32-битен вектор. Табелата за блокови за замена K содржи клучни елементи кои се заеднички за компјутерската мрежа и ретко се менуваат.

Втората операција е циклично поместување налево од 32-битниот вектор добиен како резултат на замена на K. 64-битниот блок од шифрирани податоци T sh е претставен како T sh = A (32) B (32).

Останатите блокови на отворени податоци во режим на едноставна замена се шифрираат на ист начин.

Ве молиме имајте предвид дека режимот за едноставна замена може да се користи за шифрирање податоци само во ограничени случаи. Овие случаи вклучуваат генерирање клуч и негово шифрирање со обезбедување имитациона заштита (заштита од наметнување лажни податоци) за пренос преку комуникациски канали или складирање во компјутерска меморија.

Гама режим

Отворените податоци, поделени на 64-битни блокови T(i) (i=1, 2,..., m, каде што m се определува со волуменот на шифрирани податоци), се шифрираат во режимот гама со битско собирање модуло 2 со гама шифрата Гш, која се произведува во блокови од 64 бита, односно Гш = (Г(1),Г(2),...,Г(i),...,Г(m)).

Равенката за шифрирање на податоците во гама режим може да се претстави на следниов начин:

Ш(i) = A (Y(i-1) [+] C2, Z(i-1) (+) C1) (+) T(i) = Г(i) (+) T(i) .
Тука Ш(i) е 64-битен блок од шифриран текст,
А - функција за шифрирање во режим на едноставна замена (аргументите на оваа функција се два 32-битни броеви),
C1 и C2 се константи наведени во ГОСТ 28147-89,
Y(i) и Z(i) се величини кои се одредуваат итеративно додека гамата се формира на следниов начин:
(Y(0), Z(0)) = A(S), каде што S е 64-битна бинарна секвенца (синхронизирана порака);
(Y(i), Z(i)) = (Y(i-1) [+] C2, Z(i-1) (+) C1) за i = 1, 2,...,m.

Дешифрирањето на податоците е можно само во присуство на порака за синхронизација, која не е таен елемент на шифрата и може да се складира во компјутерската меморија или да се пренесе преку комуникациски канали заедно со шифрирани податоци.

Гама режим со повратни информации

Мод играње игрисо повратни информации е многу сличен на гама режимот. Како и во гама режимот, отворените податоци, поделени на 64-битни блокови T(i) (i=1, 2,..., m, каде што m се определува со волуменот на шифрирани податоци), се шифрираат со модуло за собирање битови 2 со гама шифра Г sh, која се произведува во блокови од 64 бита:

G w = (G(1),G(2),...,G(i),...,G(m)).

Бројот на бинарни цифри во блокот T(m) може да биде помал од 64, додека делот од опсегот на шифрите што не се користи за шифрирање од блокот G(m) е отфрлен.

Равенката за шифрирање на податоците во гама режим на затворена јамка може да се претстави на следниов начин:

Тука Ш(i) е 64-битен блок од шифриран текст,
А - функција за шифрирање во режим на едноставна замена. Функцискиот аргумент на првиот чекор од итеративниот алгоритам е 64-битна порака за синхронизација, а во сите наредни чекори тој е претходниот блок од шифрирани податоци Ш(i-1).

Развој на имитациски инсерти

Процес на производство имитовские униформа за кој било од режимите на шифрирање податоци.

Вметнувањето на имитација е блок од p битови (имитационо вметнување Ir), кој се генерира или пред да се шифрира целата порака, или паралелно со шифрирањето блок-по-блок. Првите блокови од отворени податоци кои учествуваат во генерирањето на имитативната влошка може да содржат информации за услугата (на пример, дел за адреса, време, порака за синхронизација) и не се шифрирани. Вредноста на параметарот p (бројот на бинарни битови во симулацискиот инсерт) се одредува со криптографски барања, земајќи го предвид фактот дека веројатноста за наметнување лажни пречки е еднаква на 1/2^p.

За да се добие симулирано вметнување, отворените податоци се претставени во форма на 64-битни блокови T(i) (i = 1, 2,..., m, каде што m се определува со обемот на шифрирани податоци). Првиот блок од обични податоци T(1) претрпува трансформација што одговара на првите 16 циклуси на алгоритмот за шифрирање во режим на едноставна замена. Покрај тоа, клучот што се користи за шифрирање на податоците се користи како клуч за генерирање на имитативната влошка.

64-битниот број добиен по 16 циклуси на работа се сумира модуло 2 со вториот блок од отворени податоци T(2). Резултатот од сумирањето повторно е подложен на трансформација што одговара на првите 16 циклуси на алгоритмот за шифрирање во режим на едноставна замена. Добиениот 64-битен број се сумира модуло 2 со третиот блок од отворени податоци T(3), итн. Последниот блок T(m), доколку е потребно, дополнет до целосен 64-битен блок со нули, се сумира модуло 2 со резултатот од работата на чекор m-1, по што се шифрира во режим на едноставна замена во текот на првиот 16 циклуси на алгоритмот. Од добиениот 64-битен број, се избира сегмент Ir со должина p битови.

Имитативното вметнување Ir се пренесува преку канал за комуникација или во компјутерската меморија по шифрираните податоци. Примените шифрирани податоци се дешифрираат, а од примените блокови отворени податоци T(i) се генерира симулирана вметнување Ir, која потоа се споредува со симулирана вметнување Ir добиена од каналот за комуникација или од компјутерската меморија. вметнувањата не се совпаѓаат, сите дешифрирани податоци се сметаат за лажни.

Алгоритам за шифрирање ГОСТ 28147-89, негова употреба и имплементација на софтвер за компјутери на платформата Intel x86.

Андреј Винокуров

Опис на алгоритмот.

Услови и ознаки.

Опис на стандардот за шифрирање на Руската Федерација е содржан во многу интересен документ насловен „Алгоритам за криптографска конверзија ГОСТ 28147-89“. Фактот што во неговото име наместо поимот „енкрипција“ се појавува поопшт концепт „ криптографска конверзија “, воопшто не е случајно. Во прилог на неколку тесно поврзани процедури за шифрирање, документот опишува еден алгоритам за генерирање имитации инсерти . Последново не е ништо повеќе од криптографска контролна комбинација, односно код генериран од оригиналните податоци со помош на таен клуч за целите на заштита од имитација , или заштита на податоците од неовластени промени.

Во различни чекори на ГОСТ алгоритмите, податоците на кои работат се толкуваат и користат на различни начини. Во некои случаи, податочните елементи се третираат како низи од независни битови, во други случаи како неозначен цел број, во други како структуриран комплексен елемент кој се состои од неколку поедноставни елементи. Затоа, за да се избегне забуна, важно е да се договориме за употребената нотација.

Елементите на податоци во овој напис се означени со големи букви со курзив стил (на пример, X). Преку | X| ја означува големината на податочниот елемент Xво битови. Така, ако го толкуваме податочниот елемент XКако ненегативен цел број, можеме да ја напишеме следната неравенка:.

Ако податочниот елемент се состои од неколку помали елементи, тогаш овој факт се означува на следниов начин: X=(X 0 ,X 1 ,…,X n –1)=X 0 ||X 1 ||…||X n-1. Процесот на комбинирање на неколку податочни елементи во еден се нарекува конкатенација податоци и се означува со симболот „||“. Природно, следнава врска мора да биде задоволена за големини на податочните елементи: | X|=|X 0 |+|X 1 |+…+|X n-1 |. Кога се специфицираат сложени податочни елементи и операцијата за конкатенација, составните податочни елементи се наведени по растечки редослед на приоритет. Со други зборови, ако композитниот елемент и сите негови податочни елементи ги толкуваме како неозначени цели броеви, тогаш можеме да ја напишеме следната еднаквост:

Во алгоритмот, податочниот елемент може да се толкува како низа од поединечни битови, во тој случај битовите се означени со истата буква како и низата, но во мала верзија, како што е прикажано во следниот пример:

X=(x 0 ,x 1 ,…,x n –1)=x 0 +2 1 · x 1 +…+2 n-1 · x n –1 .

Така, ако забележавте, усвоен е таканаречениот ГОСТ. „малку-ендијанско“ нумерирање на цифри, т.е. Во рамките на повеќебитните податочни зборови, поединечните битови и групите на битови со помал број се помалку значајни. Ова е директно наведено во став 1.3 од стандардот: „При додавање и циклично поместување бинарни вектори, најзначајните битови се сметаат за битови на погони со голем број“. Понатаму, клаузулите од стандардот 1.4, 2.1.1 и други бараат започнување со пополнување на регистрите за складирање на виртуелниот уред за шифрирање со податоци од најниските, т.е. помалку значајни категории. Точно истиот редослед на нумерирање е усвоен во архитектурата на микропроцесорот Intel x86, поради што при имплементирање на шифра во софтверот на оваа архитектура, не се потребни дополнителни пермутации на битови во зборовите на податоци.

Ако некоја операција која има логично значење се изврши на податочни елементи, тогаш се претпоставува дека оваа операција се изведува на соодветните битови од елементите. Со други зборови А Б=(а 0 б 0 ,а 1 б 1 ,…,a n –1 b n–1), каде n=|А|=|Б|, а симболот „ ” означува произволна бинарна логичка операција; по правило, тоа значи операција ексклузивни или , што е исто така операција на модуло за сумирање 2:

Логиката на конструирање на шифра и структурата на клучните информации ГОСТ.

Ако внимателно го проучите оригиналниот ГОСТ 28147–89, ќе забележите дека содржи опис на алгоритми на неколку нивоа. На самиот врв има практични алгоритми дизајнирани да ги шифрираат низите на податоци и да развијат имитативни инсерти за нив. Сите тие се засноваат на три алгоритми на ниско ниво, наречени во текстот на ГОСТ циклуси . Овие основни алгоритми се наведени во овој напис како основни циклуси да ги разликува од сите други циклуси. Ги имаат следните имиња и симболи, вторите се дадени во загради и нивното значење ќе биде објаснето подоцна:

• циклус на шифрирање (32-З);
• циклус на декрипција (32-P);
• циклус на производство на имитациски влошка (16-Z).

За возврат, секој од основните циклуси е повеќекратно повторување на една единствена постапка, повикана на дефинитност понатаму во оваа работа главниот чекор на конверзија на крипто .

Така, за да го разберете ГОСТ, треба да ги разберете следните три работи:

• што се случи основен чекор крипто конверзии;
• како се формираат основните циклуси од основните чекори;
• од три основни циклуси се собираат сите практични GOST алгоритми.

Пред да продолжиме да ги проучуваме овие прашања, треба да зборуваме за клучните информации што ги користат алгоритмите на ГОСТ. Во согласност со принципот на Кирхоф, кој го задоволуваат сите модерни шифри познати на пошироката јавност, нејзината тајност е таа што ја обезбедува тајноста на шифрираната порака. Во ГОСТ, клучните информации се состојат од две структури на податоци. Покрај вистинските клуч , неопходен за сите шифри, содржи и табела за замена . Подолу се дадени главните карактеристики на клучните структури на ГОСТ.

Главниот чекор на конверзија на крипто.

Основниот чекор на конверзија на крипто е во суштина изјава која ја одредува конверзијата на 64-битен блок на податоци. Дополнителен параметар на овој оператор е 32-битен блок, кој се користи како клучен елемент. Дијаграмот на алгоритмот на главниот чекор е прикажан на Слика 1.

Слика 1. Шема на главниот чекор на крипто-конверзија на алгоритмот ГОСТ 28147-89.

Подолу се објаснувања за главниот алгоритам за чекори:

Чекор 0

• Н– конвертиран 64-битен податочен блок, за време на извршувањето на неговиот мал чекор ( Н 1) и постар ( Н 2) деловите се третираат како посебни 32-битни неозначени цели броеви. Така, можеме да пишуваме N=(Н 1 ,Н 2).
• X– 32-битен клучен елемент;

Чекор 1

Додаток со клуч. На долната половина на конвертираниот блок се додава модуло 2 32 со клучниот елемент што се користи на чекорот, резултатот се пренесува на следниот чекор;

Чекор 2

Замена на блок. 32-битната вредност добиена во претходниот чекор се толкува како низа од осум 4-битни кодни блокови: S=(С 0 , С 1 , С 2 , С 3 , С 4 , С 5 , С 6 , С 7), и С 0 ги содржи 4-те најмлади, и С 7 – 4 најзначајни битови С.

Следно, вредноста на секој од осумте блокови се заменува со нова, која се избира од табелата за замена на следниов начин: вредност на блокот С исе менува на С и-ти елемент по редослед (нумерирање од нула) јас- тој јазол за замена (т.е. јас-та линија од табелата за замена, нумерирање исто така од нула). Со други зборови, елемент од табелата за замена со број на ред еднаков на бројот на блокот што се заменува и број на колона еднаков на вредноста на блокот што се заменува како 4-битен ненегативен цел број е избран како замена. за вредноста на блокот. Ова ја прави јасна големината на табелата за замена: бројот на редови во него е еднаков на бројот на 4-битни елементи во 32-битен податочен блок, односно осум, а бројот на колони е еднаков на бројот на различни вредности на 4-битен податочен блок, за кој се знае дека е 2 4, шеснаесет.

Чекор 3

Завртете 11 бита налево. Резултатот од претходниот чекор се поместува циклично за 11 бита кон најзначајните битови и се пренесува на следниот чекор. Во алгоритамскиот дијаграм, симболот ја означува функцијата на циклично поместување на неговиот аргумент 11 бита налево, т.е. кон повисоките чинови.

Чекор 4

Собирање на битови: Вредноста добиена во чекор 3 се додава битови модуло 2 со конвертирање на повисоката половина од блокот.

Чекор 5

Поместување по должината на ланецот: долниот дел од конвертираниот блок се префрла на местото на постариот, а резултатот од претходниот чекор се става на негово место.

Чекор 6

Добиената вредност на конвертираниот блок се враќа како резултат на извршувањето на алгоритмот на главниот чекор на конверзија на крипто.

Основни циклуси на криптографски трансформации.

Како што беше забележано на почетокот на овој напис, ГОСТ припаѓа на класата на блок шифри, односно единицата за обработка на информации во него е блок на податоци. Затоа, сосема е логично да се очекува дека ќе дефинира алгоритми за криптографски трансформации, односно за шифрирање, дешифрирање и „сметководство“ за контролна комбинација на еден блок податоци. Овие алгоритми се нарекуваат основни циклуси ГОСТ, кој ја нагласува нивната фундаментална важност за изградбата на оваа шифра.

Основните јамки се изградени од главните чекори криптографска трансформација дискутирана во претходниот дел. За време на главниот чекор, се користи само еден 32-битен клучен елемент, додека клучот ГОСТ содржи осум такви елементи. Затоа, за да може клучот целосно да се користи, секоја од основните јамки мора постојано да го извршува главниот чекор со неговите различни елементи. Во исто време, се чини сосема природно дека во секој основен циклус сите клучни елементи треба да се користат ист број пати; поради јачината на шифрата, овој број треба да биде повеќе од еден.

Сите претпоставки направени погоре, базирани едноставно на здрав разум, се покажаа како точни. Основните јамки се состојат од повторено извршување главен чекор користејќи различни клучни елементи и се разликуваат едни од други само по бројот на повторувања на чекорите и редоследот по кој се користат клучните елементи. Подолу е оваа нарачка за различни циклуси.

Циклус на шифрирање 32-Z:

К 0 ,К 1 ,К 2 ,К 3 ,К 4 ,К 5 ,К 6 ,К 7 ,К 0 ,К 1 ,К 2 ,К 3 ,К 4 ,К 5 ,К 6 ,К 7 ,К 0 ,К 1 ,К 2 ,К 3 ,К 4 ,К 5 ,К 6 ,К 7 ,К 7 ,К 6 ,К 5 ,К 4 ,К 3 ,К 2 ,К 1 ,К 0 .

Слика 2а. Шема на циклус на шифрирање 32-З

Циклус на дешифрирање 32-P:

К 0 ,К 1 ,К 2 ,К 3 ,К 4 ,К 5 ,К 6 ,К 7 ,К 7 ,К 6 ,К 5 ,К 4 ,К 3 ,К 2 ,К 1 ,К 0 ,К 7 ,К 6 ,К 5 ,К 4 ,К 3 ,К 2 ,К 1 ,К 0 ,К 7 ,К 6 ,К 5 ,К 4 ,К 3 ,К 2 ,К 1 ,К 0 .

Слика 2б. Шема на циклусот на декрипција 32-P

Циклус на производство на имитациона влошка 16-Z:

К 0 ,К 1 ,К 2 ,К 3 ,К 4 ,К 5 ,К 6 ,К 7 ,К 0 ,К 1 ,К 2 ,К 3 ,К 4 ,К 5 ,К 6 ,К 7 .

Слика 2в. Шема на производствен циклус на имитациона влошка 16-Z.

Секој од циклусите има своја алфанумеричка ознака што одговара на шемата " n-X", каде што првиот елемент на ознаката ( n), го одредува бројот на повторувања на главниот чекор во циклусот и вториот елемент за означување ( X), буква, го одредува редоследот на шифрирање („Z“) или дешифрирање („P“) при употребата на клучните елементи. Оваа наредба бара дополнително објаснување:

Циклусот на дешифрирање мора да биде инверзен на циклусот на шифрирање, односно, последователната примена на овие два циклуса на произволен блок мора на крајот да го даде оригиналниот блок, што се рефлектира во следнава врска: В 32-Р ( В 32-З ( Т))=Т, Каде Т- произволен 64-битен блок на податоци, В X( Т) – резултат од извршувањето на јамката Xнад податочниот блок Т. За да се исполни овој услов за алгоритми слични на ГОСТ, потребно е и доволно редоследот на употреба на клучните елементи според соодветните циклуси да биде взаемно обратен. Лесно е да се потврди валидноста на писмената состојба за предметот што се разгледува со споредување на горенаведените секвенци за циклусите 32-З и 32-Р. Една интересна последица следи од горенаведеното: својството на циклусот да биде инверзен во однос на друг циклус е реципрочно, односно, циклусот 32-Z е инверзен на циклусот 32-P. Со други зборови, шифрирањето на блок од податоци теоретски може да се изврши со користење на циклус на дешифрирање, во тој случај дешифрирањето на блок од податоци мора да се изврши со циклус на шифрирање. Од двата меѓусебно инверзни циклуси, кој било може да се користи за шифрирање, а потоа вториот мора да се користи за дешифрирање податоци, меѓутоа, стандардот ГОСТ 28147-89 доделува улоги на циклуси и не му дава на корисникот право да избира во ова прашање .

Циклусот за производство на имитативен инсерт е половина од долгите циклуси на шифрирање, редоследот на користење на клучните елементи во него е ист како во првите 16 чекори од циклусот на шифрирање, што е лесно да се потврди со разгледување на горенаведените секвенци, затоа овој редослед во означувањето на циклусот е кодиран со истата буква „Z“.

Шемите на основните циклуси се прикажани на сликите 2а-в. Секој од нив зема како аргумент и како резултат враќа 64-битен блок на податоци, наведен во дијаграмите Н. Симбол чекор( Н,X) го означува извршувањето на главниот чекор на крипто-трансформација за блок на податоци Нкористејќи клучен елемент X. Постои уште една разлика помеѓу циклусите за пресметување на шифрирање и имитативни вметнувања, кои не се споменати погоре: на крајот од основните циклуси на шифрирање, високите и ниските делови од резултатот блок се заменуваат, тоа е неопходно за нивната меѓусебна реверзибилност.

Основни режими на шифрирање.

ГОСТ 28147-89 ги обезбедува следните три начини на шифрирање на податоци:

• едноставна замена,
• играње игри,
• играње со повратни информации,

и еден дополнителен режим за генерирање на имитирани влошки.

Во кој било од овие режими, податоците се обработуваат во блокови од 64 бита, на кои низата е поделена и подложена на криптографска трансформација, поради што ГОСТ се однесува на блок шифри. Меѓутоа, во два гама режими е можно да се обработи нецелосен блок податоци со големина помала од 8 бајти, што е од суштинско значење кога се шифрираат низи на податоци со произволна големина, што не може да биде повеќекратно од 8 бајти.

Пред да преминете на дискусија за специфични алгоритми за криптографска трансформација, неопходно е да се разјасни ознаката што се користи во дијаграмите во следните делови:

ТО, Т w – низи од отворени и шифрирани податоци, соодветно;

, – јас- секвенцијални 64-битни блокови на отворени и шифрирани податоци, соодветно: , , последниот блок може да биде нецелосен: ;

n– број на 64-битни блокови во податочната низа;

В X – функција за конвертирање на 64-битен податочен блок користејќи го основниот циклус „X“ алгоритам.

Сега ќе ги опишеме главните начини на шифрирање:

Лесна замена.

Шифрирањето во овој режим се состои од примена на циклус 32-З на блокови од отворени податоци, дешифрирање - циклус 32-Р на блокови од шифрирани податоци. Ова е наједноставниот од режимите; 64-битните податочни блокови се обработуваат независно еден од друг. Шемите на алгоритми за шифрирање и дешифрирање во режим на едноставна замена се прикажани на сликите 3а и б, соодветно; тие се тривијални и не бараат коментари.

Цртеж. 3а. Алгоритам за шифрирање на податоци во режим на едноставна замена

Цртеж. 3б. Алгоритам за дешифрирање податоци во режим на едноставна замена

Големината на низата отворени или шифрирани податоци, кои се предмет на шифрирање или дешифрирање, соодветно, мора да биде повеќекратно од 64 бита: | Т o |=| Т w |=64· n , по извршувањето на операцијата, големината на добиената низа на податоци не се менува.

Едноставниот режим на шифрирање за замена ги има следниве карактеристики:

• Бидејќи податочните блокови се шифрираат независно еден од друг и нивната позиција во низата со податоци, шифрирањето на два идентични блока со обичен текст резултира со идентични блокови на шифриран текст и обратно. Забележаното својство ќе му овозможи на криптоаналитичарот да донесе заклучок за идентитетот на оригиналните блокови на податоци доколку наиде на идентични блокови во шифрираната низа на податоци, што е неприфатливо за сериозна шифра.
• Ако должината на шифрираната низа на податоци не е повеќекратна од 8 бајти или 64 бита, се јавува проблемот како и како да се дополни последниот нецелосен податочен блок од низата до целосните 64 бита. Оваа задача не е толку едноставна како што изгледа на прв поглед. Очигледни решенија како „дополнување на нецелосен блок со нула битови“ или, поопшто, „дополнување на нецелосен блок со фиксна комбинација од нула и еден битови“ може, под одредени услови, да му дадат на криптоаналитичарот можност да користи методи на брутална сила за да утврди содржината на овој многу нецелосен блок, а овој факт значи намалување на безбедносната шифра. Дополнително, должината на шифрениот текст ќе се промени, зголемувајќи се до најблискиот цел број повеќекратен од 64 бита, што често е непожелно.

На прв поглед, горенаведените карактеристики го прават речиси невозможно користењето на режимот за едноставна замена, бидејќи може да се користи само за шифрирање низи на податоци со големина која е повеќекратна од 64 бита и не содржи повторливи 64-битни блокови. Се чини дека за какви било реални податоци е невозможно да се гарантира исполнување на овие услови. Ова е речиси точно, но има еден многу важен исклучок: запомнете дека големината на клучот е 32 бајти, а големината на табелата за замена е 64 бајти. Покрај тоа, присуството на повторени блокови од 8 бајти во табела за клуч или замена ќе укаже на нивниот многу лош квалитет, така што таквото повторување не може да постои во вистински клучни елементи. Така, откривме дека режимот за едноставна замена е сосема погоден за шифрирање на клучните информации, особено затоа што другите режими се помалку погодни за оваа намена, бидејќи бараат дополнителен елемент за синхронизирање на податоци - порака за синхронизација (видете го следниот дел). Нашата претпоставка е точна; ГОСТ пропишува употреба на едноставен режим за замена исклучиво за шифрирање на клучните податоци.

Гумање.

Како можете да се ослободите од недостатоците на режимот за едноставна замена? За да го направите ова, неопходно е да се овозможи шифрирање на блокови со големина помала од 64 бита и да се осигура дека блокот на шифриран текст зависи од неговиот број, со други зборови, рандомизираат процес на шифрирање. Во ГОСТ ова се постигнува на два различни начини во два режима на шифрирање, обезбедувајќи играње игри . Гумање - ова е наметнување (отстранување) на криптографска скала на отворени (шифрирани) податоци, односно низа од податочни елементи генерирани со помош на некој криптографски алгоритам за да се добијат шифрирани (отворени) податоци. За да се примени гама за време на шифрирањето и да се отстрани за време на дешифрирањето, мора да се користат взаемно инверзни бинарни операции, на пример, модул за собирање и одземање 2 64 за 64-битни податочни блокови. Во ГОСТ, за таа цел, се користи операцијата на модулот за собирање битови 2, бидејќи тој е обратен од себе и, згора на тоа, наједноставно се имплементира во хардверот. Гама ги решава двата споменати проблеми: прво, сите гама елементи се различни за вистински шифрирани низи и, според тоа, резултатот од шифрирање дури и два идентични блока во една низа на податоци ќе биде различен. Второ, иако гама елементите се генерираат во еднакви делови од 64 бита, може да се користи дел од таков блок со големина еднаква на големината на шифрираниот блок.

Сега да преминеме директно на описот на гама режимот. Гамата за овој режим се добива на следниов начин: со помош на некој алгоритамски генератор на повторливи секвенци на броеви (RNGN), се генерираат 64-битни блокови на податоци, кои потоа се конвертираат со помош на циклусот 32-3, односно шифрирани во едноставна режим на замена, што резултира со гама блокови. Поради фактот што апликацијата и отстранувањето на гама се изведуваат со користење на истата ексклузивна битна или операција, алгоритмите за шифрирање и дешифрирање во гама режим се идентични, нивната општа шема е прикажана на Слика 4.

RGPG што се користи за генерирање на скалата е рекурентна функција: – елементи од повторливата низа, ѓ– функција на трансформација. Следствено, неизбежно се поставува прашањето за неговата иницијализација, односно за елементот.Всушност, овој податочен елемент е алгоритамски параметар за гама режими, во дијаграмите е означен како С, и се нарекува во криптографијата синхронизирај испрати , и во нашиот ГОСТ – почетно полнење еден од регистрите на енкодерот. Од одредени причини, програмерите на ГОСТ одлучија да не ја користат пораката за синхронизација директно за иницијализирање на RGFC, туку резултатот од неговата конверзија според циклусот 32-Z: . Редоследот на елементите генерирани од RGHR целосно зависи од неговото почетно полнење, односно елементите на оваа низа се функција од нивниот број и почетното полнење на RGHR: каде f i(X)=ѓ(f i –1 (X)), ѓ 0 (X)=X. Земајќи ја предвид трансформацијата со користење на едноставниот алгоритам за замена, се додава и зависност од клучот:

Каде Г i– јас-ти елемент на вагата, К- клуч.

Така, низата гама елементи што ќе се користат во гама-режимот е уникатно одредена од клучните податоци и пораката за синхронизација. Секако, за постапката за шифрирање да биде реверзибилна, истата порака за синхронизација мора да се користи во процесите на шифрирање и дешифрирање. Од барањето за уникатност на гамата, неуспехот да се усогласи со што доведува до катастрофално намалување на јачината на шифрата, произлегува дека за да се шифрираат две различни низи податоци на истиот клуч, неопходно е да се обезбеди употреба на различни пораки за синхронизација. Ова доведува до потреба да се складира или пренесе пораката за синхронизација долж комуникациските канали заедно со шифрираните податоци, иако во некои посебни случаи тоа може да се предодреди или пресмета на посебен начин ако е исклучено шифрирањето на две низи со ист клуч.

Сега да го разгледаме подетално RGPC што се користи во ГОСТ за генерирање на гама елементи. Пред сè, треба да се забележи дека не е потребно да се обезбедат никакви статистички карактеристики на генерираната низа од броеви. RGHR е дизајниран од програмерите на ГОСТ врз основа на потребата да се исполнат следниве услови:

• периодот на повторување на низата броеви генерирана од RGPC не треба да се разликува многу (во проценти) од максималната можна вредност за дадена големина на блок од 2 64;
• соседните вредности произведени од RGPG мора да се разликуваат едни од други во секој бајт, инаку задачата на криптоаналитичарот ќе биде поедноставена;
• RGPC треба да биде прилично лесен за имплементација и во хардвер и софтвер на најчестите типови на процесори, од кои повеќето се знае дека се 32-битни.

Врз основа на наведените принципи, креаторите на ГОСТ дизајнираа многу успешен RGHR, кој ги има следните карактеристики:

Каде В 0 =1010101 16 ;

Каде В 1 =1010104 16 ;

Подлогата во бројот го означува неговиот броен систем, така што константите што се користат во овој чекор се напишани во хексадецимално.

Вториот израз има потреба од коментари, бидејќи текстот на ГОСТ содржи нешто друго: , со иста вредност на константата В 1 . Но понатаму во текстот на стандардот е даден коментар дека, се испоставува, под операцијата за преземање на остатокот од модулот 2 32 –1 тамуне се сфаќа на ист начин како во математиката. Разликата е во тоа што според ГОСТ (2 32 -1) мод(2 32 –1)=(2 32 –1), а не 0. Всушност, ова ја поедноставува имплементацијата на формулата, а математички точниот израз за неа е даден погоре.

• периодот на повторување на низата за долниот дел е 2 32, за постариот дел 2 32 -1, за целата низа периодот е 2 32 (2 32 -1), доказот за овој факт е многу едноставен, дознајте го себе си. Првата од двете формули се имплементира во една команда, втората, и покрај нејзината очигледна незгодност, во две команди на сите модерни 32-битни процесори - првата команда го изведува вообичаениот модуло за додавање 2 32 со складирање на битот за носење, а втората командата го додава битот за носење на добиеното значење.

Дијаграмот за алгоритам за шифрирање во гама режим е прикажан на Слика 4; подолу се објаснувања за шемата:

Слика 4. Алгоритам за шифрирање (дешифрирање) на податоци во гама режим.

Чекор 0

Ги дефинира влезните податоци за главниот чекор на конверзија на крипто:

• Т o(w) – низа од отворени (шифрирани) податоци со произволна големина, подложени на процедура за шифрирање (декрипција), во текот на постапката, низата се конвертира во 64-битни делови;
• С – синхронизирај порака , 64-битен податочен елемент потребен за иницијализирање на генераторот на гама;

Чекор 1

Почетната трансформација на пораката за синхронизација, извршена за нејзино „рандомизирање“, односно елиминирање на статистичките обрасци присутни во неа, резултатот се користи како почетно пополнување на RGPC;

Чекор 2

Еден чекор од операцијата RGPC, имплементирање на неговиот рекурентен алгоритам. За време на овој чекор, најстариот ( С 1) и помлад ( С 0) делови од секвенцата на податоци се генерираат независно еден од друг;

Чекор 3

Гумање. Следниот 64-битен елемент генериран од RGPC е подложен на процедура за шифрирање користејќи циклус 32-3, резултатот се користи како гама-елемент за шифрирање (дешифрирање) на следниот блок отворени (шифрирани) податоци со иста големина.

Чекор 4

Резултатот од алгоритмот е шифрирана (декриптирана) низа на податоци.

Следниве се карактеристиките на гама како режим за шифрирање:

1. Идентичните блокови во низата со отворени податоци ќе дадат различни блокови на шифриран текст кога се шифрираат, што ќе овозможи да се сокрие фактот за нивниот идентитет.
2. Бидејќи гама преклопувањето се изведува битови, шифрирањето на делумен блок од податоци лесно се постигнува со шифрирање на битови од тој делумен блок со користење на соодветните битови од гама блокот. Така, за шифрирање на нецелосен блок од 1 бит, според стандардот, треба да се користи најмалку значајниот бит од гама блокот.
3. Пораката за синхронизација што се користи за шифрирање мора некако да се пренесе за употреба при дешифрирање. Ова може да се постигне на следниве начини:

• складирајте или пренесете порака за синхронизација заедно со шифрирана низа на податоци, што ќе доведе до зголемување на големината на низата со податоци кога е шифрирана според големината на пораката за синхронизација, односно за 8 бајти;
• користете однапред одредена вредност на пораката за синхронизација или генерирајте ја синхроно од изворот и примачот според одреден закон, во овој случај нема промена во големината на пренесената или складираната низа на податоци;

И двата методи се надополнуваат, а во оние ретки случаи кога првиот, најчестиот не функционира, може да се користи вториот, поегзотичниот. Вториот метод има многу помала примена, бидејќи е можно да се направи порака за синхронизација однапред одредена само ако не е шифрирана повеќе од една низа на податоци на даден сет на клучни информации, што не се случува многу често. Исто така, не е секогаш можно синхроно да се генерира порака за синхронизација на изворот и примачот на низата на податоци, бидејќи бара строга врска со нешто во системот. Така, навидум здравата идеја да се користи бројот на пренесената порака како порака за синхронизација во систем за пренос на шифрирани пораки не е соодветна, бидејќи пораката може да се изгуби и да не стигне до примачот, во тој случај системите за шифрирање на изворот а приемникот ќе стане десинхронизиран. Затоа, во разгледуваниот случај, нема алтернатива за пренос на пораката за синхронизација заедно со шифрираната порака.

Од друга страна, може да се даде спротивен пример. Да речеме дека шифрирањето на податоците се користи за заштита на информациите на дискот и се спроведува на ниско ниво; за да се обезбеди независен пристап, податоците се шифрираат по сектори. Во овој случај, невозможно е да се складира пораката за синхронизација заедно со шифрираните податоци, бидејќи големината на секторот не може да се промени, но може да се пресмета како некоја функција на бројот на главата за читање на дискот, бројот на песната (цилиндарот) и бројот на секторот на патеката. Во овој случај, пораката за синхронизација е врзана за позицијата на секторот на дискот, што е малку веројатно да се промени без реформатирање на дискот, односно без уништување на податоците на него.

Гама режимот има уште една интересна карактеристика. Во овој режим, битовите од податочната низа се шифрираат независно еден од друг. Така, секој бит од шифрениот текст зависи од соодветниот бит на обичниот текст и, се разбира, од секвенцискиот број на битот во низата: . Ова имплицира дека менувањето на бит за шифриран текст во спротивна вредност ќе резултира со слична промена на спротивната вредност на битот за обичен текст:

каде што означува превртена во однос на тбитна вредност().

Ова својство му дава можност на напаѓачот, со влијание на битовите на шифрениот текст, да направи предвидливи, па дури и насочени промени на соодветниот обичен текст добиен по дешифрирањето, без да го поседува тајниот клуч. Ова го илустрира добро познатиот факт во криптологијата дека тајноста и автентичноста се различни својства криптографски системи . Со други зборови, својствата на криптосистемот за обезбедување заштита од неовластен пристап до содржината на пораката и од неовластени промени на пораката се независни и може да се преклопуваат само во одредени случаи. Тоа значи дека постојат криптографски алгоритми кои обезбедуваат одредена тајност на шифрирани податоци и во исто време не заштитуваат од промени на кој било начин, и обратно, обезбедувајќи ја автентичноста на податоците и во никој случај не ја ограничуваат можноста за запознавање со нив. Поради оваа причина, разгледуваното својство на гама режимот не треба да се смета како негов недостаток.

Гама со повратни информации.

Овој режим е многу сличен на режимот гама и се разликува од него само по начинот на кој се генерираат гама-елементите - следниот гама-елемент се генерира како резултат на трансформација од 32-3 циклуси на претходниот блок на шифрирани податоци и за шифрирање првиот блок од низата податоци, гама-елементот се генерира како резултат на истиот циклус на синхронизација на трансформацијата. Со ова се постигнува синџир на блокови - секој блок на шифриран текст во овој режим зависи од соодветните и од сите претходни блокови на обичен текст. Затоа, овој режим понекогаш се нарекува играње со испреплетени блокови . Фактот дека блоковите се поврзани нема влијание врз јачината на шифрата.

Дијаграмот на алгоритмите за шифрирање и дешифрирање во гама режимот со повратни информации е прикажан на слика 5 и поради неговата едноставност не бара никакви коментари.

Слика 5. Алгоритам за шифрирање (дешифрирање) на податоци во гама режим со повратна информација.

Гама шифрирањето со затворена јамка ги има истите карактеристики како и обичното шифрирање на гама, освен ефектот на оштетување на шифрениот текст на соодветниот обичен текст. За споредба, да ги запишеме функциите за дешифрирање блок за двата споменати режими:

Гумање;

Гама со повратни информации;

Ако во редовниот гама режим, промените во одредени битови од шифрениот текст влијаат само на соодветните битови од обичниот текст, тогаш во режимот на повратна гама сликата е нешто покомплицирана. Како што може да се види од соодветната равенка, при дешифрирање на податочен блок во гама режим на затворена јамка, блокот со отворени податоци зависи од соодветните и претходните шифрирани блокови на податоци. Затоа, ако воведете изобличувања во шифриран блок, тогаш по дешифрирањето два блока отворени податоци ќе бидат искривени - соодветниот и оној што следи, а изобличувањата во првиот случај ќе бидат од иста природа како во режимот гама , а во вториот случај - како во лесната замена. Со други зборови, во соодветниот блок на отворени податоци истите битови ќе бидат оштетени како и во блокот на шифрирани податоци, а во следниот блок на отворени податоци сите битови се независни еден од друг со веројатност 1 / 2 ќе ги промени нивните вредности.

Развој на симулиран инсерт за податочната низа.

Во претходните делови, разговаравме за влијанието на корупцијата на шифрираните податоци врз соодветните обични податоци. Утврдивме дека при дешифрирање во режим на едноставна замена, соодветниот блок на отворени податоци се покажува како искривен на непредвидлив начин, а при дешифрирање блок во режимот гама, промените се предвидливи. Во гама режимот со затворена јамка, два блока се искривуваат, едниот на предвидлив начин, а другиот на непредвидлив начин. Дали ова значи дека од гледна точка на заштита од наметнување лажни податоци, гама режимот е лош, а едноставните замени и гама режимите за повратни информации се добри? - Во никој случај. Кога се анализира оваа ситуација, неопходно е да се земе предвид дека непредвидливите промени во дешифрираниот блок на податоци може да се откријат само ако истите тие податоци се вишок, и колку е поголем степенот на вишок, толку е поголема веројатноста за откривање на изобличување. Се јавува многу голем вишок, на пример, за текстови на природни и вештачки јазици, во овој случај фактот на искривување се открива речиси неизбежно. Меѓутоа, во други случаи, на пример, кога компресираните дигитализирани звучни слики се искривени, едноставно ќе добиеме поинаква слика што нашето уво може да ја воочи. Искривувањето во овој случај ќе остане неоткриено, освен ако, се разбира, нема априори информации за природата на звукот. Заклучокот овде е следниов: бидејќи способноста на некои режими на шифрирање да детектираат изобличувања воведени во шифрирани податоци значително се потпира на присуството и степенот на вишок на шифрираните податоци, оваа способност не е вродена сопственост на соодветните режими и не може да се смета како нивната предност.

За да се реши проблемот со откривање на изобличувања во шифрирана низа на податоци со дадена веројатност, ГОСТ предвидува дополнителен начин на криптографска трансформација - развој на имитативно вметнување. Вметнувањето за имитација е контролна комбинација која зависи од отворените податоци и тајните клучни информации. Целта на користењето на имитативно вметнување е да се детектираат сите случајни или намерни промени во информациската низа. Проблемот опишан во претходниот пасус може успешно да се реши со додавање имитативни инсерти на шифрираните податоци. За потенцијален напаѓач, следните две задачи се речиси невозможни да се решат ако го нема клучот:

• пресметка на имитативно вметнување за дадена отворена низа на информации;
• избор на отворени податоци за даден симулациски инсерт;

Дијаграмот на алгоритмот за развој на симулиран инсерт е прикажан на слика 6.

Слика 6. Алгоритам за развој на симулиран инсерт за податочна низа.

Дел од блокот примен на излезот се зема како симулирано вметнување, обично неговите 32 најмалку значајни бита. При изборот на големината на лажен инсерт, мора да се земе предвид дека веројатноста за успешно наметнување на лажни податоци е еднаква на 2 –| Јас | по обид за избор, доколку напаѓачот нема на располагање поефективен метод за селекција од едноставното погодување. Кога се користи 32-битен симулиран инсерт, оваа веројатност е еднаква на

Дискусија за криптографските алгоритми ГОСТ.

Криптографска сила на ГОСТ.

При изборот на криптографски алгоритам за употреба во одреден развој, еден од одлучувачките фактори е неговата сила, односно отпорот на обидите на противникот да го открие. Прашањето за јачината на шифрата, по поблиско испитување, се сведува на две меѓусебно поврзани прашања:

• Дали е можно воопшто да се пробие оваа шифра?
• ако е така, колку е тешко да се направи практично;

Шифрите кои воопшто не можат да се скршат се нарекуваат апсолутно или теоретски силни. Постоењето на такви шифри е докажано со теоремата на Шенон, но цената на оваа сила е потребата да се користи клуч за шифрирање на секоја порака што не е помала по големина од самата порака. Во сите случаи, со исклучок на голем број специјални, оваа цена е преголема, па затоа во пракса главно се користат шифри кои не се апсолутно сигурни. Така, најчестите шеми за шифрирање може да се скршат во одредено време, или, поточно, во конечен број чекори, од кои секоја е некоја операција на броеви. За нив најважен концепт е практичната упорност, што ја изразува практичната тешкотија на нивното откривање. Квантитативна мерка за оваа тешкотија може да биде бројот на елементарни аритметички и логички операции што мора да се извршат за да се отвори шифрата, односно за да се одреди соодветниот обичен текст за даден шифриран текст со веројатност не помала од дадена вредност. Во исто време, покрај низата со дешифрирани податоци, криптоаналитичарот може да има блокови од отворени податоци и соодветни шифрирани податоци, па дури и можност да добие соодветни шифрирани податоци за сите отворени податоци што ќе ги избере - во зависност од наведените и многу други неодредени услови, се разликуваат посебни видови криптоанализа.

Сите модерни криптосистеми се изградени на принципот Кирхоф, односно тајноста на шифрираните пораки се определува со тајноста на клучот. Ова значи дека дури и ако самиот алгоритам за шифрирање му е познат на криптоаналитичарот, тој, сепак, не може да ја дешифрира пораката ако го нема соодветниот клуч. Шифрата се смета за добро дизајнирана ако не постои начин да се скрши поефикасно отколку со брутална сила над целиот клучен простор, т.е. над сите можни клучни вредности. ГОСТ веројатно одговара на овој принцип - со текот на годините на интензивно истражување, не е предложен ниту еден ефективен метод за нејзина криптоанализа. Во однос на јачината, таа е многу посилна од претходниот американски стандард за шифрирање, DES.

ГОСТ користи 256-битен клуч и јачината на просторот за копчиња е 2.256. Ниту еден од електронските уреди кои моментално постојат или се очекува да бидат имплементирани во блиска иднина не може да се користи за да се земе клучот за време помалку од многу стотици години. Оваа вредност стана де факто стандард за големина на клучот за симетрични криптографски алгоритми овие денови, а новиот американски стандард за шифрирање исто така го поддржува. Поранешниот американски стандард, DES, со неговата вистинска големина на клучот од 56 бита и обемот на просторот за клучеви од само 2 56 повеќе не е доволно стабилен во светлината на можностите на современите компјутерски алатки. Ова беше докажано во доцните 90-ти со неколку успешни обиди за брутална сила да се скрши DES. Покрај тоа, DES беше подложен на специјални техники за криптоанализа како што се диференцијални и линеарни. Во овој поглед, DES може да биде од истражувачки или научен интерес, а не од практичен интерес. Во 1998 година, нејзината криптографска слабост беше официјално препознаена - Националниот институт за стандарди на САД препорача употреба на тројно шифрирање DES. И на крајот на 2001 година, новиот американски стандард за шифрирање, AES, беше официјално одобрен, изграден на различни принципи и ослободен од недостатоците на неговиот претходник.

Белешки за архитектурата ГОСТ.

Добро е познато дека домашниот стандард за шифрирање е претставник на целото семејство на шифри изградени на истите принципи. Нејзиниот најпознат „роднина“ е поранешниот американски стандард за шифрирање, алгоритамот DES. Сите овие шифри, како ГОСТ, содржат алгоритми на три нивоа. Во основата секогаш постои одреден „основен чекор“, врз основа на кој на сличен начин се градат „основните циклуси“ и врз нивна основа се градат практични процедури за шифрирање и развој на имитативни инсерти. Така, специфичноста на секоја од шифрите на ова семејство лежи токму во нејзиниот главен чекор, поточно дури и во неговиот дел. Иако архитектурата на класичните блок шифри, на кои се однесува ГОСТ, лежи многу подалеку од опсегот на овој напис, сепак вреди да се каже неколку зборови за тоа.

Алгоритмите за „главните чекори на крипто-трансформација“ за шифри како ГОСТ се изградени на идентичен начин, и оваа архитектура се нарекува избалансирана мрежа на Фејстел (балансирана мрежа на Фејстел) по името на лицето кое прв го предложило. Шема за конверзија на податоци на еден циклус, или, како што обично се нарекува, круг , е прикажано на слика 7.

Слика 7. Содржина на главниот чекор на крипто-трансформација за блок шифри слични на ГОСТ.

Блок со рамномерна големина се доставува до влезот на главниот чекор, чии повисоки и долни половини се обработуваат одделно една од друга. За време на конверзијата, долната половина од блокот се поставува на местото на постарата половина, а постарата половина, комбинирана со помош на операцијата на битови ексклузивни или ” со резултат од пресметување на одредена функција, на местото на најмладата. Оваа функција ја зема како аргумент ниската половина од блокот и клучниот информативен елемент ( X), е содржински дел од шифрата и се нарекува функција за шифрирање . Од различни причини, се покажа дека е поволно да се подели шифрираниот блок на два дела со еднаква големина: | Н 1 |=|Н 2 | – овој факт се рефлектира со зборот „балансирано“ во името на архитектурата. Меѓутоа, одвреме-навреме се користат и шифрирање на небалансирани мрежи, иако не толку често како избалансираните. Покрај тоа, размислувањата за јачината на шифрата бараат големината на клучниот елемент да не биде помала од големината на половина блок: во ГОСТ, сите три големини се еднакви на 32 бита .

Ако го примениме горенаведеното на дијаграмот на главниот чекор на алгоритмот ГОСТ, ќе стане очигледно дека блоковите 1,2,3 од алгоритмот (види слика 1) ја одредуваат пресметката на неговата функција за шифрирање, а блоковите 4 и 5 наведете го формирањето на излезниот блок на главниот чекор врз основа на содржината на влезниот блок и вредностите на функцијата за шифрирање. Повеќе детали за архитектурите на модерните блок шифри со таен клуч може да се најдат во класичните дела или, во адаптирана форма, во моите дела.

Во претходниот дел, веќе ги споредивме DES и GOST во однос на издржливоста, сега ќе ги споредиме во однос на функционалната содржина и леснотијата на имплементација. Во циклусите на шифрирање GOST, главниот чекор се повторува 32 пати, за DES оваа вредност е 16. Сепак, самата функција за шифрирање GOST е многу поедноставна од сличната функција DES, која содржи многу неправилни битови пермутации. Овие операции се крајно неефикасни кај современите неспецијализирани процесори. ГОСТ не содржи такви операции, па затоа е многу поудобно за имплементација на софтвер.

Ниту една од имплементациите на DES за платформата Intel x86 прегледана од авторот не достигнува ни половина од перформансите на имплементацијата на ГОСТ предложена во овој напис, и покрај двојно пократкиот циклус. Сето горенаведено покажува дека програмерите на ГОСТ ги земале предвид и позитивните и негативните аспекти на DES, а исто така пореално ги процениле сегашните и идните можности на криптоанализата. Сепак, земањето на DES како основа кога се споредуваат перформансите на имплементации на шифри веќе не е релевантно. Новиот американски стандард за шифрирање работи многу подобро со ефикасност - со иста големина на клучот како GOST (256 бита), AES работи околу 14% побрзо - ова е споредено во однос на бројот на „елементарни операции“. Покрај тоа, ГОСТ практично не може да се паралелизира, додека AES има многу повеќе можности во овој поглед. Кај некои архитектури оваа предност на AES може да биде помала, кај други може да биде поголема. Значи, на процесор Intel Pentium достигнува 28%. Детали може да се најдат во.

Барања за квалитетот на клучните информации и извори на клучеви.

Не сите клучеви и табели за замена обезбедуваат максимална јачина на шифрата. Секој алгоритам за шифрирање има свои критериуми за оценување на клучните информации. Така, за DES алгоритмот се знае дека постојат т.н. слаби клучеви “, кога се користи, врската помеѓу отворените и шифрираните податоци не е доволно маскирана, а шифрата релативно лесно се крши.

Ако сеопфатен одговор на прашањето за критериумите за квалитет на клучевите ГОСТ и табелите за замена може да се добие воопшто насекаде, тој може да биде само од развивачите на алгоритмот. Релевантните податоци не беа објавени во отворениот печат. Меѓутоа, според утврдената процедура, за шифрирање на класифицирани информации, мора да се користат клучни податоци добиени од овластена организација. Индиректно, ова може да укаже на присуство на методи за проверка на клучните податоци за вошки. Ако присуството на слаби клучеви во ГОСТ е дискутабилно прашање, тогаш присуството на слаби заменски единици е несомнено. Очигледно, „тривијалната“ табела за замена, според која секоја вредност се заменува сама по себе, е толку слаба што при нејзиното користење, шифрата може да се пробие едноставно, без разлика кој е клучот.

Како што е наведено погоре, критериумите за проценка на клучните информации не се достапни, но сепак може да се направат некои општи размислувања за нив.

Клуч

Клучот мора да биде низа од статистички независни битови кои ги земаат вредностите 0 и 1 со еднаква веројатност. Не може целосно да се исклучи дека некои специфични клучни вредности може да се покажат како „слаби“, т.е. шифрата може да не го обезбеди одреденото ниво на јачина доколку се користи. Сепак, веројатно, уделот на таквите вредности во вкупната маса на сите можни клучеви е занемарливо мал. Барем, интензивното истражување на шифрата сè уште не открило ниту еден таков клуч за која било од познатите (т.е., предложени од FAPSI) табели за замена. Затоа, клучевите генерирани со помош на некој навистина случаен сензор за броеви ќе бидат со висок квалитет со веројатност што се разликува од единството за занемарливо мала количина. Ако клучевите се генерираат со помош на генератор на псевдо-случајни броеви, тогаш користениот генератор мора да ги обезбеди горенаведените статистички карактеристики и, покрај тоа, да има висока криптографска сила - не помала од онаа на самиот ГОСТ. Со други зборови, задачата за одредување на исчезнатите членови на низата елементи генерирани од генераторот не треба да биде поедноставна од задачата за разбивање на шифрата. Дополнително, може да се користат различни статистички критериуми за отфрлање на клучеви со лоши статистички карактеристики. Во пракса, обично се доволни два критериуми: за проверка на рамномерната распределба на клучните битови помеѓу вредностите 0 и 1, обично се користи Пирсон тест (чи квадрат) и за проверка на независноста на клучните битови, се користи тестот за извршување. . За споменатите критериуми можете да прочитате во учебници или референтни книги за математичка статистика.

Најдобар пристап за генерирање клучеви би бил користењето хардверски сензори од среден опсег, но тоа не е секогаш прифатливо од економски причини. Кога се генерира мала низа клучни информации, разумна алтернатива за користење на таков сензор е методот „електронски рулет“, кој е широко користен во пракса, кога следниот генериран дел од случајни битови зависи од моментот во кој операторот ќе притисне одредено копче на тастатурата на компјутерот. Во оваа шема, изворот на случајни податоци е корисникот на компјутерот, или поточно, временските карактеристики на неговата реакција. Во овој случај, само неколку битови случајни податоци може да се генерираат по притискање на тастатурата, така што вкупната брзина на генерирање клучни информации е мала - до неколку бита во секунда. Очигледно, овој пристап не е погоден за добивање големи низи клучеви.

Во случај кога е неопходно да се генерира голема низа клучни информации, употребата на разни софтверски сензори за псевдо-случајни броеви е можна и многу распространета. Бидејќи таков сензор бара високи нивоа на криптографска сила, природно е да се користи гама генератор на самата шифра - едноставно ја „сечеме“ гамата генерирана од шифрата на „парчиња“ со потребната големина, за ГОСТ - 32 бајти. Се разбира, за овој пристап ќе ни треба „главен клуч“, кој можеме да го добиеме со користење на методот на електронски рулет опишан погоре, и со негова помош, користејќи шифра во режим на гама генератор, добиваме низа клучни информации со големина ни треба. Така, овие два методи за генерирање клучеви - „рачни“ и „алгоритамски“ - работат во тандем, надополнувајќи се еден со друг. Шемите за генерирање клучни во „нискобуџетните“ системи за криптографска заштита на информации речиси секогаш се изградени на овој принцип.

Табела за замена

Табелата за замена е долгорочен клучен елемент, односно важи многу подолг период од еден клуч. Се претпоставува дека е заедничко за сите јазли за шифрирање во рамките на истиот систем за криптографска заштита. Дури и ако е нарушена доверливоста на табелата за замена, јачината на шифрата останува исклучително висока и не се намалува под дозволената граница. Затоа, нема посебна потреба да се чува табелата во тајност, а во повеќето комерцијални апликации на ГОСТ тоа е направено. Од друга страна, табелата за замена е критичен елемент за обезбедување на јачината на целата шифра. Изборот на погрешна табела може да доведе до тоа шифрата да биде лесно скршена со познати техники за криптоанализа. Критериумите за развој на заменските единици се строго чувана тајна и FAPSI веројатно нема да ги сподели со јавноста во блиска догледна иднина. На крајот на краиштата, за да се каже дали дадената табела за замена е добра или лоша бара огромна количина на работа - многу илјадници работни часови и машински часови. Откако ќе се избере и употреби, табелата мора да се замени ако и само ако шифрата што ја користи се покажа дека е ранлива на еден или друг вид криптоанализа. Затоа, најдобриот избор за просечниот корисник на шифри би бил да земе една од неколкуте табели што станаа јавни. На пример, од стандардот за функцијата хаш, позната и како функцијата „централно банкарство“; информациите за овие табели може да се најдат во отворениот печат, па дури и на Интернет, ако погледнете доволно добро.

За оние кои не се навикнати да одат по лесен пат, подолу е општа шема за добивање висококвалитетни табели:

1. Користејќи една или друга техника, развивате сет од осум заменски единици со загарантирани карактеристики на нелинеарност. Постојат неколку такви техники, една од нив е употребата на таканаречените свиткани функции.
2. Го проверувате исполнувањето на наједноставните „критериуми за квалитет“ - на пример, оние објавени за јазлите за замена на DES. Еве уште неколку општи размислувања во овој поглед: Секој јазол за замена може да се опише со четири логички функции од четири логички аргументи. Ако овие функции се напишани во минимална форма(т.е., со минимална можна должина на изразување) нема да биде доволно сложено, таков јазол за замена се отфрла. Покрај тоа, поединечните функции во целата табела за замена мора да бидат доволно различни една од друга. Во оваа фаза, многу очигледно неквалитетни табели се елиминирани.
3. За шифра со табели по ваш избор, изградете различни кружни модели што одговараат на различни типови на криптоанализа и измерете ги соодветните карактеристики на „профилот“. Значи, за линеарна криптоанализа, изградете линеарен статистички аналог на кругот за шифрирање и пресметајте ја карактеристиката „профил“ - индикатор за нелинеарност. Доколку е недоволна, табелата за замена се отфрла.
4. Конечно, користејќи ги резултатите од претходниот пасус, ја подложувате шифрата со табелата што сте ја одбрале на интензивно истражување - обид за криптоанализа користејќи ги сите познати методи. Оваа фаза е најтешка и одзема многу време. Но, ако е направено со висок квалитет, тогаш со висок степен на веројатност може да се каже дека шифрата со табелите што сте ги избрале нема да биде пробиена од обични смртници и, можно е, ќе биде премногу тешка за интелигенцијата. услуги.

Сепак, можете да го направите многу поедноставно. Работата е во тоа што колку повеќе кругови има во шифрата, толку помалку влијание имаат карактеристиките на јачината на еден круг врз јачината на целата шифра. ГОСТ има дури 32 круга - повеќе отколку во скоро сите шифри со слична архитектура. Затоа, за повеќето домашни и комерцијални апликации доволно е да се добијат јазли за замена како независни случајни пермутации на броеви од 0 до 15. Ова може практично да се спроведе, на пример, со мешање на шпил од шеснаесет карти, од кои на секоја и е доделена една од вредностите на наведениот опсег.

Во однос на табелата за замени, треба да се забележи уште еден интересен факт. За реверзибилност на циклусите на шифрирање „32-З“ и „32-Р“, не е потребно јазлите за замена да бидат пермутации на броеви од 0 до 15. Сè работи дури и ако јазолот за замена има дупликат елементи, а замената определен со таков јазол, е неповратен, но во овој случај јачината на шифрата е намалена. Зошто е тоа токму така, не се дискутира во овој напис, но не е тешко да се потврди самиот факт. За да го направите ова, доволно е прво да се обидете да шифрирате, а потоа да дешифрирате блок податоци користејќи таква „нецелосна“ табела за замена, чии јазли содржат дупликат вредности.

Варијации на тема ГОСТ

Многу често, за употреба во систем за заштита на криптографски податоци, потребен е алгоритам со поголема брзина на имплементација од ГОСТ, а не е потребна таква висока криптографска сила. Типичен пример за такви задачи се различните видови електронски системи за тргување со акции кои управуваат со трговските сесии во реално време. Овде, користените алгоритми за шифрирање се потребни за да оневозможат дешифрирање на оперативните податоци на системот за време на сесијата (податоци за доставени нарачки, склучени трансакции итн.), По неговото истекување, овие податоци, по правило, повеќе не се бескорисни за напаѓачите. Со други зборови, потребна е гарантирана издржливост од само неколку часа - ова е типичното времетраење на трговската сесија. Јасно е дека користењето на полноправно ГОСТ во оваа ситуација би било гаѓање врапчиња со топ.

Што да направите во овој и слични случаи за да се зголеми брзината на шифрирање? Одговорот лежи на површината - користете модификација на шифрата со помалку главни чекори (кругови) во основните циклуси. Кога го намалуваме бројот на кругови за шифрирање, перформансите се зголемуваат за иста количина. Оваа промена може да се постигне на два начина - со намалување на должината на клучот и намалување на бројот на „циклуси на преглед“ на клучот. Потсетиме дека бројот на основни чекори во основните циклуси на шифрирање е Н=n·m, Каде n– број на 32-битни елементи во клучот, м– број на циклуси на употреба на клучните елементи, во стандардот n=8, м=4. Можете да намалите кој било од овие бројки, но наједноставната опција е да ја намалите должината на клучот без да влијаете на начинот на кој се користи.

Јасно е дека цената за забрзување на работата ќе биде намалување на јачината на шифрата. Главната тешкотија е што е доста тешко повеќе или помалку точно да се процени големината на ова намалување. Очигледно, единствениот можен начин да се направи ова е да се спроведе целосна студија за варијанти на шифри со намалени криптографски циклуси на конверзија. Јасно е дека, прво, ова бара употреба на класифицирани информации, кои се во сопственост само на програмерите на ГОСТ, и, второ, тоа е многу трудоинтензивно. Затоа, сега ќе се обидеме да дадеме многу, многу груба проценка, базирана само на општи обрасци.

Што се однесува до отпорноста на шифрата на пукање со „обемни“ методи, односно на напад со „брутална сила“, сè е повеќе или помалку јасно овде: клучот од 64 бита е некаде на работ да биде достапен за овој тип. на напад, шифра со клуч од 96 бита или повисок ( запомнете дека клучот мора да содржи цел број од 32-битни елементи) е доста отпорен на него. Навистина, пред неколку години, претходниот американски стандард за шифрирање, DES, беше постојано хакиран со методи на брутална сила - прво беше хакиран од компјутерска мрежа организирана врз основа на глобалниот интернет, а потоа од специјализирана мрежа, т.е. компјутер дизајниран специјално за оваа намена. Да претпоставиме дека стандардната верзија на ГОСТ, кога се имплементира во софтвер на современи процесори, работи четири пати побрзо од DES. Тогаш 8-кружниот „намален ГОСТ“ ќе работи 16 пати побрзо од DES. Ајде, исто така, да претпоставиме дека во времето по хакирањето на DES, перформансите на компјутерите се четирикратно зголемени според законот на Мур. Како резултат на тоа, добиваме дека сега проверката на еден 64-битен клуч за „намален ГОСТ“ со осум циклуси е 64 пати побрзо од проверката на едно копче DES одеднаш. Така, предноста на оваа верзија на ГОСТ во однос на DES во однос на сложеноста на нападот со брутална сила е намалена од 2 64–56 = 2 8 = 256 на 256 / 64 = 4 пати. Се согласувам, ова е многу илузорна разлика, речиси ништо.

Многу е потешко да се процени отпорноста на ослабените модификации на ГОСТ на „интензивните“ методи на криптоанализа. Меѓутоа, и овде може да се следи општ модел. Факт е дека карактеристиките на „профилот“ на многу од најмоќните типови на криптоанализа денес зависат експоненцијално од бројот на кругови на шифрирање. Значи, за линеарна криптоанализа (LCA) ова ќе биде карактеристика на линеарност Л :

Каде В и се константи, R е бројот на кругови. Слична врска постои и за диференцијалната криптоанализа. Во нивното „физичко значење“, сите карактеристики од овој вид се веројатности. Вообичаено, количината на почетни податоци потребни за криптоанализа и нејзината сложеност се обратно пропорционални на таквите карактеристики. Следи дека овие показатели за интензитетот на трудот растат експоненцијално со бројот на основни чекори за шифрирање. Затоа, кога бројот на кругови ќе се намали неколку пати, сложеноста на најпознатите типови на анализа ќе се промени како, многу приближно и грубо, коренот на оваа моќност од првобитната количина. Ова е многу голем пад на издржливоста.

Од друга страна, ГОСТ беше дизајниран со голема маргина на безбедност и денес е отпорен на сите познати типови на криптоанализа, вклучувајќи диференцијална и линеарна. Во однос на LCA, тоа значи дека за негова успешна имплементација, потребни се повеќе парови „отворен блок-шифриран блок“ отколку „постои во природата“, односно повеќе од 2 64 . Имајќи го предвид горенаведеното, ова значи дека за успешна LCA на GOST од 16 круга, ќе бидат потребни најмалку блокови или 2 35 бајти или 32 GB податоци, а за 8-круг, најмалку блокови или 2 19 бајти или 0,5 MB.

Заклучоците од сето погоре се дадени во следната табела, која ги сумира карактеристиките на намалените верзии на ГОСТ.

Број на кругови	Големина на клучот, битови	Индекс на перформанси	Веројатни карактеристики на шифрата (многу груба проценка)
24	192	1,33	Отпорен на повеќето познати типови на CA, или на работ на отпор. Практичната имплементација на CA е невозможна поради високите барања за првичните податоци и интензитетот на трудот.
16	128	2	Теоретски, тој е нестабилен за некои видови криптоанализа, но нивната практична имплементација во повеќето случаи е тешка поради високите барања за изворните податоци и интензитетот на трудот.
12	95	2,67	Не е отпорен на некои познати типови на криптоанализа, но е погоден за обезбедување тајност на мали количини на податоци (до десетици или стотици килобајти) за краток временски период.
8	64	4	Не е отпорен на некои познати типови на криптоанализа, но е погоден за обезбедување тајност на мали количини на податоци (до десетици килобајти) за краток временски период.

Последните две опции, со 12 и 8 круга, се способни да обезбедат многу, многу ограничена временска заштита. Нивната употреба е оправдана само во задачи каде што е потребна само краткорочна тајност на заштитените податоци, од редот на неколку часа. Можна област на примена за овие слаби варијанти на шифри е блокирање на UDP сообраќајот од електронските системи за тргување на размена. Во овој случај, секој податочен пакет (податок, средното „D“ од кратенката UDP) се шифрира со помош на посебен 64-битен клуч, а самиот клуч е шифриран со помош на клуч за сесија (клуч чиј опсег е една комуникациска сесија помеѓу два компјутери) и се пренесува заедно со податоци.

Пред да завршам со намалените верзии на ГОСТ, ќе кажам дека сите горенаведени размислувања се многу шпекулативни. Стандардот обезбедува издржливост само за една варијанта со 32 круга. И никој не може да ви даде гаранции дека отпорноста на намалените верзии на шифрата на пукање ќе се промени на начин наведен погоре. Ако сепак одлучите да ги искористите во вашите случувања, запомнете дека сте стапнале на многу растреперено тло, кое во секој момент може да ви се лизне од под нозете. Бидејќи брзината на шифрирање е критично прашање за вас, можеби треба да размислите да користите побрза шифра или помоќен компјутер? Друго размислување зошто вреди да се направи ова е дека ослабените верзии на ГОСТ ќе бидат најчувствителни на квалитетот на користените единици за замена.

Прашањето што се разгледува има и негативна страна. Што ако брзината на шифрирање не е критична, но барањата за јачина се многу строги? Отпорот на ГОСТ може да се зголеми на два начина - да ги наречеме „обемни“ и „интензивни“. Првиот од нив не е ништо повеќе од едноставно зголемување на бројот на кругови за шифрирање. Не ми е сосема јасно зошто тоа всушност може да биде потребно, бидејќи домашниот стандард веќе ја обезбедува потребната издржливост без ова. Меѓутоа, ако страдате од параноја повеќе од потребното ниво (и сите „бранители на информации“ се едноставно обврзани да страдаат од тоа, ова е услов за професионална соодветност, единственото прашање е сериозноста на случајот:), ова ќе помогне се смируваш малку. Ако не сте сигурни за оваа шифра на КГБ или за табелата за замена што ја користите, едноставно удвои, четирикратно, итн. број на кругови - изберете го мноштвото врз основа на тежината на вашиот случај. Овој пристап ви овозможува навистина да ја зголемите јачината на шифрата - ако порано криптоанализата беше едноставно невозможна, сега е невозможна на квадрат!

Посложено и интересно прашање е дали е можно да се зголеми јачината на шифрата без промена на бројот и структурата на главните чекори за шифрирање. Изненадувачки, одговорот на ова е позитивен, иако повторно газиме на треперливиот терен на шпекулации. Факт е дека во ГОСТ, на главниот чекор на конверзија, треба да се замени 4 на 4 бита, но во пракса (за ова ќе зборуваме подоцна) сите софтверски имплементации ја вршат замената бајт по бајт, т.е. 8 на 8 бита - ова е направено од причини за ефикасност. Ако веднаш дизајнираме таква замена како 8-битна, значително ќе ги подобриме перформансите на еден круг. Прво, карактеристиката „дифузија“ или индикаторот „лавина“ ќе се зголеми - еден бит од изворните податоци и/или клучот ќе влијае на поголем број битови од резултатот. Второ, за поголеми јазли за замена, може да се добијат пониски диференцијални и линеарни карактеристики, со што се намалува подложноста на шифрата на слични типови на криптоанализа. Ова е особено точно за намалени циклуси на ГОСТ, а за опции од 8 и 12 круга, таков чекор е едноставно неопходен. Ова донекаде ќе го компензира губењето на издржливоста кај нив од намалувањето на бројот на кругови. Она што го отежнува користењето на оваа техника е тоа што ќе треба сами да дизајнирате такви „зголемени“ единици за замена. И, исто така, фактот дека поголемите единици генерално се многу потешки за изградба од помалите.

Нестандардна употреба на стандардот.

Се разбира, главната цел на криптографските алгоритми ГОСТ е шифрирање и заштита на податоците. Сепак, тие можат да најдат и други апликации поврзани, природно, со безбедноста на информациите. Ајде накратко да зборуваме за нив:

1. За шифрирање во гама режим, ГОСТ предвидува развој на криптографска гама - низа битови со добри статистички карактеристики и висока криптографска сила. Оваа гама потоа се користи за менување на отворените податоци, што резултира со шифрирани податоци. Сепак, ова не е единствената можна примена на криптографската гама. Факт е дека алгоритмот за неговото генерирање е генератор на псевдо-случајна секвенца на броеви (PRNG) со одлични карактеристики. Се разбира, користењето на таков PRNG каде што се потребни само статистичките карактеристики на генерираната низа, но не е потребна криптографска сила, не е многу разумно - за овие случаи има многу поефикасни генератори. Но, за различни апликации поврзани со безбедноста на информациите, таков извор ќе биде многу корисен:

• Како што е наведено погоре, гамата може да се користи како „суровина“ за генерирање клучеви. За да го направите ова, само треба да добиете гама сегмент со потребната должина - 32 бајти. На овој начин, клучевите може да се направат по потреба и нема да треба да се складираат - доколку повторно е потребен таков клуч, ќе биде прилично лесно повторно да се генерира. Треба само да запомните на кој клуч е првично генериран, каква порака за синхронизација била користена и со кој бајт од генерираната гама започнал клучот. Сите информации освен употребениот клуч се некласифицирани. Овој пристап ќе го олесни контролирањето на прилично сложен и разгранет клучен систем користејќи само еден „главен клуч“.
• Слично на претходната, гамата може да се користи како почетна „суровина“ за генерирање лозинки. Овде може да се појави прашањето: зошто е потребно воопшто да се генерираат? Зар не е полесно едноставно да се измислуваат по потреба? Неуспехот на овој пристап беше јасно покажан со серија инциденти во компјутерските мрежи, од кои најголемиот беше секојдневната парализа на Интернетот во ноември 1988 година, предизвикана од црвот Морис. Еден од начините на кои злонамерната програма навлезе во компјутерот беше со погодување лозинки: програмата се обидуваше да влезе во системот со секвенцијално испробување на лозинки од нејзината внатрешна листа од неколку стотици, и во значителен дел од случаите успеваше. Човечката имагинација за измислување лозинки се покажа како многу лоша. Тоа е причината зошто во оние организации каде што на безбедноста се посветува соодветно внимание, лозинките се генерираат и се дистрибуираат до корисниците од страна на администраторот за безбедност на системот. Генерирањето лозинки е малку покомплицирано од генерирањето клучеви, бидејќи во овој случај „суровата“ бинарна гама мора да се претвори во симболична форма, а не едноставно да се „сече“ на парчиња. Дополнително, поединечните вредности можеби ќе треба да се отфрлат за да се осигура дека сите азбучни знаци подеднакво веројатно ќе се појават во лозинката.
• Друг начин за користење на криптографската гама е гарантирано бришење на податоците на магнетните медиуми. Факт е дека дури и кога информациите се препишуваат на магнетен медиум, остануваат траги од претходните податоци, кои можат да се вратат со соодветно испитување. За да се уништат овие траги, таквото препишување мора да се врши многу пати. Се покажа дека би било потребно помалку пати да се препишуваат информации на медиумите доколку во таквата постапка се користат случајни или псевдо-случајни податоци кои би останале непознати за експертите кои се обидуваат да ги вратат избришаните информации. Гама шифрата ќе ни се најде овде.

2. Не само криптографската гама, туку и самата криптографска трансформација може да се користи за потреби кои не се директно поврзани со шифрирањето:

• Знаеме дека една од овие опции за користење на ГОСТ е развојот на симулирани инсерти за низи на податоци. Сепак, врз основа на која било блок шифра, вклучително и ГОСТ, прилично е лесно да се конструира шема за пресметување на еднонасочна хаш-функција, исто така наречена во литературата MDC, која во различни извори се залага за промена на кодот за откривање / манипулација (Ммодификација/ Манипулација Делекцијата Вода) или дигест на порака (Месеј Дигестирам Вода). Првото декодирање се појави во литературата многу порано, второто, пократко, мислам, го измислија оние кои не можеа да се сетат на првото :), - тоа беше шега. MDC може директно да се користи во системите за заштита од имитација како аналог на имитациско вметнување, што, сепак, не зависи од тајниот клуч. Покрај тоа, MDC е широко користен во шемите за електронски дигитален потпис (EDS), бидејќи повеќето од таквите шеми се дизајнирани на таков начин што е погодно да се потпише податочен блок со фиксна големина. Како што знаете, врз основа на дискутираниот стандард ГОСТ 28147-89, беше изграден стандардот на Руската Федерација за пресметување на еднонасочната хаш функција ГОСТ Р34.11-94.
• Помалку е познато дека врз основа на која било блок шифра, вклучително и ГОСТ, може да се изгради целосно функционална шема за дигитален потпис, со таен клуч за потпис и отворена комбинација за верификација. Поради повеќе причини, оваа шема не доби широка практична дистрибуција, но во некои случаи сè уште може да се смета како многу атрактивна алтернатива на „математичките“ шеми за дигитални потписи кои моментално доминираат во светот.

Литература

Системи за обработка на информации. Криптографска заштита. Алгоритам за криптографска трансформација ГОСТ 28147-89. држава Com. СССР според стандардите, М., 1989. ftp://ftp.wtc-ural.ru/pub/ru.crypt/GOST-28147
Шенон Клод. Математичка теорија на тајни системи. Во збирката „Дела за теорија на информации и кибернетика“, М., ИЛ, 1963, стр. 333-369. http://www.enlight.ru/crypto/articles/shannon/shann__i.htm
Објавување одобрување на Федералниот стандард за обработка на информации (FIPS) 197, Напреден стандард за шифрирање (AES), Федерален регистар Vol. 66, бр. 235 / четврток, 6 декември 2001 година / Известувања, стр. 63369–63371. http://csrc.nist.gov/encryption/aes/
Фејстел Хорст. Криптографија и компјутерска безбедност. Превод на А. Винокуров според публикацијата Хорст Фајстел. Криптографија и компјутерска приватност, Scientific American, мај 1973 година, кн. 228, бр. 5, стр. 15-23. http://www.enlight.ru/crypto/articles/feistel/feist_i.htm
Шнајер Брус. Применета криптографија. 2. ед. Протоколи, алгоритми и изворни текстови на јазик Ц., М., „Триумф“, 2002 година http://www.ssl.stu.neva.ru/psw/crypto/appl_rus/appl_cryp.htm
Менезес Алфред, ван Оршот Пол, Ванстон Скот. Прирачник за применета криптографија. ttp://www.cacr.math.uwaterloo.ca/hac/
Винокуров Андреј. Како функционира блок шифрата? Ракопис. http://www.enlight.ru/crypto/articles/vinokurov/blcyph_i.htm
Винокуров Андреј. Прашања за криптографија за електронското списание iNFUSED BYTES онлајн. http://www.enlight.ru/crypto/articles/ib/ib.htm
Винокуров Андреј, Применко Едуард. Текст на извештајот „За софтверска имплементација на стандарди за шифрирање во Руската Федерација и САД“, конференција за информатизација, Москва, MEPhI, 28-29 јануари 2001 година. Објавено во зборникот на конференцијата.
Информациска технологија. Заштита на криптографски информации. Хеш функција ГОСТ Р34.11-94, Државен стандард на Руската Федерација, М., 1994 година.

Овој алгоритам е задолжителен за употреба како алгоритам за шифрирање во владините организации на Руската Федерација и голем број комерцијални.

Опис на алгоритмот

Дијаграмот на алгоритмот е прикажан на сл. 3.1. Како што можете да видите, дизајнот на овој алгоритам е прилично едноставен, што јасно ја поедноставува неговата софтверска или хардверска имплементација.

Алгоритмот ГОСТ 28147-89 шифрира информации во блокови од 64 бита, кои се поделени на два подблока од 32 бита (N1 и N2). Подблокот N1 се обработува на одреден начин, по што се собира неговата вредност

со вредност на потблок N2 (додавањето се врши модуло 2), потоа се заменуваат потблоковите. Оваа трансформација се изведува во одреден број кругови: 16 или 32, во зависност од режимот на работа на алгоритмот (опишан подолу). Во секој круг се вршат следните операции:

1. Апликација за клуч. Содржината на подблокот /VI се додава модуло 2 32 со дел од копчето Kx.

Клучот за шифрирање на алгоритмот GOST 28147-89 има димензија од 256 бита, а Kx е неговиот 32-битен дел, односно 256-битниот клуч за шифрирање е претставен како конкатенација на 32-битни подклучеви (сл. 3.2):

Shch ATI, AG2, Yu, AG4, K5, Kb, K7.

За време на процесот на шифрирање, се користи еден од овие подклучеви, во зависност од кружниот број и режимот на работа на алгоритмот.

Ориз. 3.1. Алгоритамски дијаграм ГОСТ 28147-

Ориз. 3.2. Клуч за шифрирање на алгоритмот ГОСТ 28147-89

2. Замена на маса. По клучувањето, потблокот /VI е поделен на 8 делови од 4 бита, од кои вредноста на секој поединечно се заменува во согласност со табелата за замена за овој дел од подблокот. Замените на табелите (Substitution box, S-box) често се користат во современите алгоритми за шифрирање, па затоа вреди да се разгледаат подетално.

Замената на табелата се користи на овој начин: блок од податоци со одредена големина (во овој случај, 4-битен) се доставува до влезот, чиј нумерички приказ го одредува бројот на излезната вредност. На пример, имаме S-кутија од следнава форма:

4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1.

Нека дојде 4-битниот блок „0100“ на влезот, односно вредноста 4. Според табелата, излезната вредност ќе биде еднаква на 15, т.е. „1111“ (0 се заменува со 4, 1 со 11, вредноста на 2 останува непроменета, итн.).

Како што можете да видите, дизајнот на алгоритмот е многу едноставен, што значи дека најголемиот товар за шифрирање на податоците паѓа на табелите за замена. За жал, алгоритмот има својство дека има „слаби“ табели за замена, со кои алгоритмот може да се реши со криптоаналитички методи. Слабите вклучуваат, на пример, табела во која излезот е еднаков на влезот:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.

3. Битно циклично поместување налево за 11 бита.

Алгоритамски режими на работа

Алгоритмот ГОСТ 28147-89 има 4 режими на работа:

□ едноставен режим на замена;

□ гама режим;

P гама режим со повратни информации;

□ начин на развој на имитирани прилози.

Овие режими се малку различни од општоприфатените (опишани во Дел 1.4), па затоа вреди да се разгледаат подетално.

Овие режими имаат различни цели, но ја користат истата трансформација на шифрирање опишана погоре.

Лесен режим на замена

Во режимот на едноставна замена, секој 64-битен блок на информации е едноставно шифриран со користење на 32 круга опишани погоре. 32-битните потклучеви се користат во следнава низа:

□ KO, Kl, K2, KZ, K4, K5, KB, AG7, KO, ATI итн. - во рунди од 1 до 24;

□ К1, Кб, К5, К4, КЗ, К2, К\, КО - во рунди од 25 до 32.

Дешифрирањето во режим на едноставна замена се изведува на ист начин, но со малку поинаква низа на користење на подклучеви:

□ KO, K\, K2, KZ, K4, K5, Kb, KP - во рунди од 1 до 8;

□ КП, Кб, К5, К4, КЗ, К2, К\, КО, К1, Кб итн - во рунди од 9 до 32.

Слично на стандардниот режим на ЕЦБ, поради посебното шифрирање на блоковите, режимот за едноставна замена строго не се препорачува за шифрирање на самите податоци; треба да се користи само за шифрирање на други клучеви за шифрирање во шеми со повеќе клучеви.

Гама режим

Во гама режимот (сл. 3.3), секој блок од обичен текст се додава малку по малку модуло 2 на 64-битен шифриран гама блок. Гама шифрата е посебна секвенца која се генерира со помош на трансформациите опишани погоре како што следува:

1. Нивното почетно полнење е запишано во регистрите N1 и N2 - 64-битна вредност наречена „синхронизирана порака“ (пораката за синхронизација е практично аналог на векторот за иницијализација во режимите CBC, CFB и OFB).

2. Содржината на регистрите /VI и N2 (во овој случај, пораките за синхронизација) се шифрираат во режим на едноставна замена.

3. Содржината на N1 се додава модуло (2 32 – 1) со константа CI = 2 24 + 2 16 + 2 8 + 4, резултатот од собирањето се запишува во регистарот /VI.

4. Содржината на N2 се додава модуло 2 со константата C2 = 2 24 + 2 16 + 2 8 +1, резултатот од собирањето се запишува во регистарот N2.

5. Содржината на регистрите /VI и N2 се емитува како 64-битен шифра гама блок (т.е., во овој случај, /VI и N2 го формираат првиот гама блок).

6. Ако е потребен следниот гама блок (т.е. треба да се направи дополнително шифрирање или дешифрирање), вратете се на чекор 2.

За дешифрирање, гамата се генерира на сличен начин, а потоа шифрениот текст и гама битовите повторно се XOR.

За да се генерира истиот опсег на шифри, корисникот што го дешифрира криптограмот мора да го има истиот клуч и истата вредност на пораката за синхронизација што се користеле при шифрирањето на информациите. Во спротивно, нема да може да се добие оригиналниот текст од шифрираниот.

Во повеќето имплементации на алгоритмот ГОСТ 28147-89, пораката за синхронизација не е таен елемент, сепак, пораката за синхронизација може да биде тајна како и клучот за шифрирање. Во овој случај, можеме да сметаме дека ефективната должина на клучот на алгоритмот (256 бита) се зголемува за уште 64 бита од пораката за синхронизација, што може да се смета како дополнителен клучен елемент.

Гама режим со повратни информации

Во режимот гама со повратни информации, резултатот од шифрирањето на претходниот блок од обичен текст се користи за пополнување на регистрите /VI и L/2, почнувајќи од вториот блок, не претходниот гама-блок, туку резултатот од шифрирањето на претходниот блок од обичен текст. (Сл. 3.4). Првиот блок во овој режим се генерира целосно слично на претходниот.

Ориз. 3.4. Генерирање на шифрирана гама во гама режим со повратни информации

Режим на производство на прицврстување имитација

Префиксот е криптографска контролна сума пресметана со помош на клуч за шифрирање и дизајнирана да го потврди интегритетот на пораките. За да се пресмета, постои посебен режим на алгоритмот ГОСТ 28147-89.

Генерирањето на имитациски префикс се врши на следниов начин:

1. Првиот 64-битен блок на информации за кој се пресметува префиксот за имитација се запишува во регистрите N1 и N2 и се шифрира во намален режим на едноставна замена, во кој се изведуваат првите 16 круга од 32.

2. Добиениот резултат е сумиран модуло 2 со следниот блок на информации, зачувувајќи го резултатот во N1 и N2.

3. M и N2 се шифрираат повторно во скратениот режим на едноставна замена, итн. до последниот блок на информации.

Префиксот за имитација се смета за 64-битна добиена содржина на регистрите N1 и N2 или дел од нив. Најчесто се користи 32-битен имитативен префикс, односно половина од содржината на регистрите. Ова е доволно, бидејќи, како и секоја контролна сума, додатокот за имитација е наменет, пред сè, да заштити од случајно искривување на информациите. За заштита од намерна промена на податоците, се користат други криптографски методи - првенствено електронски дигитален потпис (види Дел 1.1).

Префиксот за имитација се користи на следниов начин:

1. При шифрирање на која било информација, префиксот за имитација на обичен текст се пресметува и се испраќа заедно со шифрениот текст.

2. По дешифрирањето, префиксот за имитација повторно се пресметува и се споредува со испратениот.

3. Ако пресметаните и испратените имитациски префикси не се совпаѓаат, текстот на шифрата бил искривен за време на преносот или биле користени неточни клучеви за време на дешифрирањето.

Префиксот за имитација е особено корисен за проверка на правилното дешифрирање на клучните информации при користење на шеми со повеќе клучеви.

Префиксот за имитација е некој аналог на кодот за автентикација на пораката MAC, пресметан во режимот CBC; Разликата е во тоа што при пресметување на префиксот за имитација не се користи пораката за синхронизација, додека при пресметување на MAC се користи векторот за иницијализација.

Јачина на криптографски алгоритам

Во 1994 година, описот на алгоритмот ГОСТ 28147-89 беше преведен на англиски и објавен; по ова почнаа да се појавуваат резултатите од нејзината анализа, спроведена од странски специјалисти; сепак, не беа пронајдени напади кои се приближуваат до изводливоста подолго време.

□ голема должина на клучот - 256 бита; заедно со пораката за тајна синхронизација, ефективната должина на клучот се зголемува на 320 бита;

□ 32 рунди трансформации; веќе по 8 круга се постигнува целосниот ефект на дисперзија на влезните податоци: менувањето на еден бит од блокот на обичен текст ќе влијае на сите битови од блокот за шифриран текст и обратно, односно има повеќекратна маргина на јачина.

Ајде да ги разгледаме резултатите од криптоанализата на алгоритмот ГОСТ 28147-89.

Анализа на табели за замена

Бидејќи табелите за замена не се предвидени во стандардот, голем број дела (на пример, во) сугерираат дека „надлежна организација“ може да издаде и „добри“ и „лоши“ табели за замена. Сепак, познатиот експерт Брус Шнајер таквите претпоставки ги нарекува „гласини“. Јасно е дека криптографската сила на алгоритмот во голема мера зависи од својствата на користените табели за замена; соодветно, постојат слаби табели за замена (види пример погоре), чија употреба може да го поедностави нападот на алгоритмот. Сепак, можноста за користење на различни табели за замена изгледа како многу достојна идеја, во корист на која може да се наведат следните два факти од историјата на стандардот за шифрирање DES (за детали, видете Дел 3.15):

□ нападите кои користат и линеарна и диференцијална криптоанализа на алгоритмот DES користат специфични карактеристики на табелите за замена; кога користите други табели, криптоанализата ќе мора да започне одново;

□ направени се обиди да се зајакне DES против линеарна и диференцијална криптоанализа со користење на поцврсти табели за замена; таквите табели, кои се навистина поцврсти, беа предложени, на пример, во алгоритмот s 5 DES; но, за жал, беше невозможно да се замени DES со s 5 DES, бидејќи табелите за замена се строго дефинирани во стандардот, и соодветно на тоа, имплементациите на алгоритмот веројатно не ја поддржуваат можноста за промена на табелите на други.

Голем број на дела (на пример, и ) погрешно заклучуваат дека тајните табели за замена на алгоритмот ГОСТ 28147-89 можат да бидат дел од клучот и да ја зголемат неговата ефективна должина (што не е значајно, бидејќи алгоритмот има многу голема 256 -бит клуч). Сепак, работата докажува дека тајните за замена на тајните можат да се пресметаат со помош на следниот напад, кој може практично да се користи:

1. Се поставува копчето нула и се врши пребарување на „нула вектор“, односно вредноста z = /(0), каде што /() е тркалезната функција на алгоритмот. Оваа фаза трае околу 2 операции за шифрирање.

2. Користејќи го нултиот вектор, се пресметуваат вредностите на табелите за замена, што трае не повеќе од 2 11 операции.

Модификации на алгоритам и нивна анализа

Работата спроведе криптоанализа на модификациите на алгоритмот ГОСТ 28147-89:

□ GOST-H алгоритам, во кој, во однос на оригиналниот алгоритам, редоследот на користење на подклучеви е променет, имено во кругови од 25 до 32 подклучеви се користат по директен редослед, односно потполно ист како во претходните кругови на алгоритмот;

□ 20-круг GOST® алгоритам, во кој круг користи XOR наместо модуло-2 додавање за преклопување на клучот.

Врз основа на резултатите од анализата, заклучено е дека GOST-H и GOST© се послаби од оригиналниот GOST 28147-89 алгоритам, бидејќи и двата имаат класи на слаби клучеви. Вреди да се напомене дека во однос на криптоанализата GOST©, делото од збор до збор го повторува делот посветен на криптоанализата на алгоритмот ГОСТ 28147-89, добро познато дело објавено во 2000 година (без никакви референци за оригиналот). Ова ја доведува во прашање професионалноста на авторите на делото и другите негови резултати.

Во работата беше предложена многу интересна модификација на алгоритмот: табелите S\…Ss мора да бидат нужно различни; во секој круг од алгоритмот тие мора да се преуредуваат според одреден закон. Оваа пермутација може да зависи од клучот за шифрирање, или може да биде и тајна (т.е. да биде дел од поголем клуч за криптирање од оригиналниот 256-битен клуч). И двете од овие опции, според нивните автори, значително ја зголемуваат отпорноста на алгоритмот против линеарната и диференцијалната криптоанализа.

И уште една модификација поврзана со табелите за замена е дадена во работата, која анализира еден од можните методи за пресметување на табелите за замена врз основа на клучот за шифрирање. Авторите на делото заклучија дека таквата зависност го ослабува алгоритмот, бидејќи доведува до присуство на слаби клучеви и до некои потенцијални ранливости на алгоритмот.

Целосна кружна анализа на алгоритам

Исто така, има напади на целосниот круг ГОСТ 28147-89 без никакви измени. Едно од првите јавни дела за анализирање на алгоритмот, добро познато дело, е посветено на напади кои ги искористуваат слабостите во процедурата за проширување на клучот на голем број добро познати алгоритми за шифрирање. Особено, целосниот алгоритам ГОСТ 28147-89 може да се прекине со помош на диференцијална криптоанализа на поврзаните клучеви, но само ако се користат слаби табели за замена. Верзијата од 24 круга на алгоритмот (во која недостасуваат првите 8 рунди) се отвора на сличен начин со сите табели за замена, но силните табели за замена (на пример, дадената) го прават таквиот напад целосно непрактичен.

Ростовцев и Е. наоѓање на неговиот екстрем кој одговара на вистинската клучна вредност. Тие, исто така, пронајдоа голема класа слаби клучеви на алгоритмот ГОСТ 28147-89, кои овозможуваат отворање на алгоритмот користејќи само 4 избрани обични текстови и соодветните шифрирани текстови со прилично мала сложеност. Криптанализата на алгоритмот се продолжува во работата.

Во 2004 година, група специјалисти од Кореја предложија напад кој, користејќи диференцијална криптоанализа на поврзани клучеви, може да добие 12 бита од тајниот клуч со веројатност од 91,7%. Нападот бара 2 35 избрани обични текстови и 2 36 операции за шифрирање. Како што можете да видите, овој напад е практично бескорисен за всушност да се прекрши алгоритмот.