Алгоритъмът GOST 28147 89 е. Вътрешен стандарт за криптиране на данни

Популярно известният термин „производителност на процесора“ е обективен, изчислен параметър, който се измерва във флопс. Повечето хора обаче го измерват в гигахерци, наивно вярвайки, че те са едно и също нещо. Никой не знае термина „производителност на кода“ и веднага ще обясня защо.

Причината е, че съвсем наскоро го измислих и все още не съм казал на никого за него. Въпреки това, производителността на кода, както и производителността на процесора, има обективни характеристики, които могат да бъдат измерени. Тази статия е специално за производителността на кода, изпълняван от ядрото на процесора.

Как се измерва производителността на кода? Тъй като аз бях първият, който говори за това, по право на откривателя ще го измервам в RTT единици;).

Сега сериозно. В съвременните процесори основните трансформации са операции с 32-битови числа, всичко останало като цяло е екзотика. Затова ще вземем предвид основното - операции с 32-битови числа. Колко 32-битови операции мислите, че едно съвременно процесорно ядро ​​може да изпълнява едновременно?

Ученикът ще отговори – една, учителят му ще се замисли и ще каже, че са четири, професионалистът – че досега има само дванадесет операции.

И така, програмен код, който зарежда всички изпълнителни единици на процесора едновременно през цялото време на изпълнение на кода, ще има производителност от 12 RTT. Максимално! Честно казано, никога преди не съм писал такъв код, но в тази статия ще се опитам да положа усилия.

Ще докажа, че е възможен код с едновременно изпълнение на дванадесет 32-битови операции

Програмният код, който използва един задвижващ механизъм в ядрото на процесора, естествено ще има производителност от 1 RTT. Програмите, генерирани от езикови компилатори на високо ниво и интерпретатори на виртуални машини, могат да се похвалят с такава производителност на кода. Не е необходимо да се предполага, че индикаторът за натоварване на процесора, който може да се види в диспечера на задачите на ОС, може да служи като обективен критерий за ефективността на кода. Натоварването на ядрото на процесора може да бъде 100%, но програмният код ще използва една изпълнителна единица в него (производителност 1 RTT). В този случай при 100% натоварване ядрото на процесора ще работи на 1/12 от максималната си производителност. С други думи, когато Windows Task Manager показва максималното натоварване на процесора, действителната му производителност може да варира от 1 до 12 RTT. Ако видите 100% натоварване на което и да е процесорно ядро ​​в прозореца за производителност, погрешно е да се приеме, че всички изпълнителни механизми работят в това ядро, изобщо не!

Единственият критерий за индиректна оценка на работата на процесорното ядро ​​при максимална производителност може да бъде неговата консумация на енергия и, като следствие, шумът на охладителя. Сега, ако охладителят е шумен, тогава да, натоварването е достигнало максимума. Време е обаче да приключим с общите концепции и да преминем към суровата практика.

Традиционно изпълнение на GOST 28147-89

Не съм професионалист в областта на информационната сигурност, но все пак съм запознат с темата за криптирането. Бях вдъхновен да изучавам криптиране на симетричен поток специално от разговори с професионален криптограф, когото дълбоко уважавам. И след като взех тази тема, се опитах да го направя добре, и не само добре, но и бързо, изпълнявайки максимален брой операции за единица време. С други думи, бях изправен пред задачата да напиша програмен код с максимална RTT стойност.

Криптографската трансформация в съответствие с GOST 28147-89 се използва за поточно криптиране на информация в комуникационни канали и на дискови устройства.

В момента софтуерната реализация на този GOST на RON на централния процесор се използва широко. В известните методи за прилагане на GOST цялата секретна информация (ключове за криптиране, заместващи блокове) се намира в RAM. Това намалява надеждността на криптирането, тъй като наличието на RAM dump може напълно да разкрие всички тайни елементи на крипто-трансформацията. В допълнение, методът има ограничения в производителността поради местоположението на основните обекти за крипто преобразуване в OP и непълното зареждане на изпълнителните блокове на ALU. Съвременните процесори, прилагащи крипто процедурата по добре познат метод, могат да осигурят скорости на криптиране от 40–60 мегабайта в секунда. И ако наистина го разберем до края, причината за ниската производителност и слабата сигурност на крипто конвертирането е софтуерната реализация на блока за заместване. За неговото описание в GOST вижте фиг. 1.

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

За софтуерната реализация на блока за заместване се използват специални таблици в RAM, изготвени на етапа на инициализация на криптофункцията. Тези таблици комбинират заместващите възли на съседни тетради в 8 × 8-битови байтови таблици, като по този начин поставят четири 256-байтови таблици в RAM.

При по-напреднали реализации тези таблици са с размер 1024 байта (256 думи от четири байта). Това беше направено, за да се приложи в таблиците допълнително циклично изместване с 11 позиции на 32-битовата дума, получена в резултат на заместване (следващата операция на алгоритъма за преобразуване съгласно GOST). Пример за изпълнение на GOST с помощта на този метод е показано в Приложение 1 (на диск).

Информацията на блока за заместване е таен компонент на криптофункцията (както е формулирано в GOST, вижте фиг. 2).

Поставянето на тези таблици с ключовете на блока за заместване в OP противоречи на изискванията на GOST (клауза 1.7), тъй като секретната информация става достъпна за програми на трети страни, работещи на изчислителната инсталация. FSB, който също сертифицира софтуерни реализации на криптиране според GOST, гледа на това нарушение, меко казано, снизходително. Ако, за да постави ключове в OP, FSB все още изисква „смокиново листо“ - маскиране на ключовете с помощта на операцията XOR, тогава нищо не се изисква за заместващи блокове в OP; те се съхраняват в ясна форма.

Накратко, FSB позволява такива софтуерни реализации на криптопроцедури да преминат, въпреки очевидното намаляване на сигурността на такова решение и пряко нарушение на собствените му изисквания съгласно GOST (клауза 1.7). И това въпреки добре познатите методи за разбиване на шифри чрез вземане на дъмп на паметта...

Ще се върнем към въпроса за съхраняването на ключове и заместващи блокове във вътрешните регистри на процесора малко по-късно (има красиво и бързо решение), но засега ще съхраняваме само ключове за криптиране в MMX регистри, това е по-надеждно.

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

Многопоточно изпълнение на GOST 28147-89

Единственият начин да се ускорят крипто процедурите в известния алгоритъм е въвеждането на многопоточност. Смисълът на тази промяна в изпълнението на алгоритъма е да се изчислят няколко блока данни паралелно.

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

Съществува обаче и друга възможност за паралелна обработка на данни на едно процесорно ядро. Нека обясня тази неочевидна идея.

Съвременните процесори включват поне две и дори три до шест аритметично-логически единици. Тези ALU (FPU, адресни аритметични единици и т.н.) могат да работят независимо една от друга; единственото условие за тяхната паралелна работа е софтуерните обекти, върху които работят, да са несвързани. С други думи, в инструкциите, които едновременно изпълняват ALU, адресите на паметта и номерата на регистрите трябва да са различни. Или не трябва да се извършват записи в споделени регистри и адреси на паметта, достъпни от различни изпълнителни модули на процесора.

Работното натоварване на всички ALU се контролира от специален хардуерен модул вътре в ядрото на процесора - планировчикът, който сканира изпълнимия код напред, до дълбочина от 32–64 байта. Ако планировчикът открие инструкции, които могат да бъдат изпълнени на ALU без конфликти, тогава той ги изпълнява едновременно на различни устройства за изпълнение. В този случай броячът на изпълнените команди показва изпълняващата се команда (има няколко от тях в такава схема), след което всички команди вече са изпълнени.

Повечето програмни последователности, генерирани автоматично (от компилатори), не могат да заредят всички ALU и FPU, разположени в ядрото на процесора. В този случай хардуерът на процесора е неактивен, което значително намалява неговата резултатна производителност. Разработчиците на процесори разбират това и въвеждат режими за увеличаване на честотата на ядрото, когато хардуерът не се използва напълно. Това е и това, за което са предназначени системите за хипертрейдинг и аз ще използвам тази система, за да „натисна“ кода до максимум в бъдеще.

Компилаторите, дори най-оптимизираните, и още повече двигателите на виртуалните машини, не могат да генерират оптимизиран код по отношение на производителността. Само програмист с инженерни познания може да напише такъв оптимизиран код, а инструментът за писането му е изключително асемблер.

Типична илюстрация на възможността за изпълнение на няколко независими програмни нишки на едно процесорно ядро ​​е реализацията на GOST, изпълнена в две нишки на едно процесорно ядро. Идеята на кода е проста: има два блока данни за криптиране/декриптиране, но едно процесорно ядро, което ще извърши преобразуването. Възможно е да се извърши преобразуването на тези два блока данни последователно и това се прави и до днес. В този случай времето, необходимо за извършване на трансформациите, се удвоява.

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

На фигурата горният пример показва обичайния ред на обработка на два независими блока от данни. Първо се обработва първият блок, след което процесорът продължава да обработва втория блок. Естествено, полученото време е равно на два пъти времето, необходимо за обработка на един блок, а изпълнителните механизми на процесорното ядро ​​не са напълно заредени.

Следното е пример за вплитане на команди от различни нишки за обработка. В този случай командите, свързани с различни блокове данни, се преплитат. Планировчикът избира инструкции, които са независими една от друга, и ги предава за изпълнение на ALU1 и ALU2. Групирането на команди на първата и втората нишки на тези ALU се извършва автоматично, тъй като работният алгоритъм на планировчика включва групиране на команди, свързани с общи данни на едно и също изпълнително устройство.

За да може такъв програмен код да работи без прекъсване на ALU, е необходимо всяка програмна нишка да работи със собствен набор от регистри. Кешът в тази схема се превръща в тясно място (има само два изходни порта за данни), така че съхраняваме ключовете в MMX регистри. Тъй като в този случай заместващите (и изместващите) възли в паметта се четат само, те могат да бъдат общи и за двете програмни нишки.

Това, разбира се, е много опростено обяснение на принципа на паралелно изпълнение на програмни нишки на едно ядро; в действителност всичко е много по-сложно. На практика трябва да вземете под внимание конвейерната архитектура на изпълнителните механизми, ограниченията за едновременен достъп до кеша и блока на регистъра RON, наличието на адресни аритметични възли, комутатори и много други... Така че това е тема за професионалисти, които се броят на пръстите... на едната ръка.

Методът за паралелно криптиране се прилага ефективно само за режим на работа на 64-битов процесор, тъй като в този режим има достатъчен брой RON (до 16 броя!). Пример за изпълнение на GOST с помощта на този метод е показан в Приложение 2 (на диск).

Ясно е, че това изпълнение на GOST има кодова производителност от 2 RTT кода. Сега нека видим как това се отразява на времето за изпълнение.

Цикълът на криптиране за една нишка (Приложение 1) е 352 тактови цикъла и през това време се изчисляват 8 байта данни; за двупоточна реализация на GOST (Приложение 2) са необходими 416 процесорни цикъла, но се изчисляват 16 байта. Така получената скорост на преобразуване се увеличава от 80 на 144 мегабайта за 3,6 GHz процесор.

Получава се интересна картина: кодът съдържа точно два пъти повече команди и се изпълнява само 15% по-дълго, но мисля, че читателите вече са разбрали причината за това явление...

Теоретично кодът от втория пример трябва да се изпълни в същия брой цикли като кода от първия пример, но възелът на планировчика е разработен от инженери на Intel, но те също са хора и всички сме далеч от съвършенството. Така че е възможно да се оцени ефективността на тяхното създаване. Този код също ще работи на AMD процесор и можете да сравните техните резултати.

Ако някой не вярва на думата ми, тогава за такива невярващи на диска са включени тестови програми с броячи на часовници. Програмите са в изходен код, разбира се на асемблер, така че има възможност да проверите думите ми и в същото време да видите някои от триковете на професионалното кодиране.

Използване на SSE регистри и AVX команди на съвременни процесори за прилагане на GOST 28147-89

Съвременните процесори на архитектурата x86/64 включват набор от SSE регистри с размер 16 байта и специализирани FPU (поне два) за извършване на различни операции върху тези регистри. Възможно е да се внедри GOST на това оборудване и в този случай заместващите възли могат да бъдат поставени не под формата на таблици в RAM, а директно в специални SSE регистри.

Един SSE регистър може да побере две таблици от 16 реда наведнъж. По този начин четири SSE регистъра ще поемат напълно всички заместващи таблици. Единственото условие за такова поставяне е изискването за преплитане, според което тетрадите от един и същи байт трябва да бъдат поставени в различни SSE регистри. Освен това е препоръчително да поставите ниските и високите тетради на входните байтове съответно в ниските и високите тетради на байтовете на SSE регистрите.

Тези изисквания се определят чрез оптимизация за съществуващия набор от AVX команди. По този начин всеки байт от регистъра SSE ще съдържа две тетради, съответстващи на различни байтове от входния регистър на блока за заместване, докато позицията на байта в регистъра за SSE уникално съответства на индекса в таблицата за заместване на блока за заместване.

Диаграма на едно от възможните разполагания на заместващи възли в регистрите на SSE е показана на фиг. 4.

Поставянето на секретна информация на заместващи възли в SSE регистрите повишава сигурността на крипто процедурата, но пълното изолиране на тази секретна информация е възможно, ако са изпълнени следните условия:

• Ядрото на процесора се превключва в режим на хост на хипервайзор и блокът за прекъсване (APIC) е принудително деактивиран в него. В този случай ядрото на процесора е напълно изолирано от операционната система и приложенията, работещи в изчислителната инсталация.
• Регистрите на SSE се зареждат и изчислителното ядро ​​се изолира преди стартирането на операционната система; оптимално е тези процедури да се изпълняват от надеждния модул за зареждане (TLM).
• Програмите за криптопроцедури в съответствие с GOST се намират в непроменяема област на паметта на изчислителната инсталация (или BIOS, или във флаш паметта на MDZ).

Спазването на тези изисквания ще осигури пълна изолация и неизменност на програмния код на криптопроцедурите и използваната в тях секретна информация.

За ефективно вземане на проби от tetrad SSE регистри се използват многовходните байтови превключватели, включени в блоковете FPU. Тези превключватели позволяват прехвърляне от всеки байт източник към всеки байт местоназначение, като се използват индекси, разположени в специален индексен регистър на SSE. Освен това прехвърлянето се извършва паралелно за всичките 16 байта на регистъра на приемника на SSE.

Имайки заместващи възли за съхранение на SSE регистри и многовходов превключвател в FPU блокове, е възможно да се организира следната трансформация в заместващия блок (фиг. 5).

В тази схема входният регистър във всяка тетрада определя адреса за съответния превключвател, който предава информация от устройствата на заместващите възли към изходния регистър чрез шината за данни. Тази схема може да бъде организирана по три начина:

• Създайте подходящ дизайн на чип, но това е фантастично за нас.
• Препрограмирането на микрокода и създаването на собствена процесорна команда за прилагане на тази функция на съществуващи процесори вече не е фантазия, но, за съжаление, е нереалистично в настоящите условия.
• Напишете програма, като използвате официални AVX команди. Опцията може да не е много ефективна, но може да се приложи „тук и сега“. Това е, което ще направим по-нататък.

Работата на комутаторите се управлява от специална триадресна команда AVX VPSHUFB. Първият му операнд е приемникът на информация от превключвателите, вторият е източникът, към който са свързани входовете на превключвателите. Третият операнд е контролен регистър за превключватели, всеки байт от който е свързан със съответния превключвател; стойността в него указва номера на посоката, от която превключвателят чете информация. За описание на тази команда от официалната документация на Intel вижте фиг. 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 не е очевидно. Следователно времето за изпълнение на стандартните процедури беше измерено чрез метода на директна замяна в съответствие с GOST за четири и осем нишки.

За четири нишки е получена скорост на изпълнение от 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 разширение, и в този допълнителен набор от инструкции има такива, които значително опростяват изпълнението на GOST алгоритъм.

Това се отнася до командите за логическо пакетно изместване на байта и пакетно циклично изместване на двойни думи. В примерите, дадени в Приложения 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 реда). Така че GOST се оказва по-ефективен, когато се прилага на x86/64 архитектура, кой би си помислил...

Това е, ако говорим за постигнатото ниво на скорост на криптиране. И ако имаме предвид теоретичните усъвършенствания в областта на повишаването на ефективността на кода, тогава най-вероятно никой не се нуждае от това. На практика няма специалисти на ниво 3–6 RTT, компилаторите обикновено генерират код на ниво 1–2.5 RTT и по-голямата част от програмистите не знаят асемблер и дори да знаят правописа му, те не разбират дизайна на модерен процесор. И без това знание няма значение дали е асемблер или някакъв вид SI-sharp.

Но не всичко е толкова тъжно: най-важното след седмица безсънни нощи е нов алгоритъм за прилагане на GOST, който би било грях да не се патентова. А заявките за патенти (общо три) вече са готови и подадени, така че, господа бизнесмени, редете се - жените и децата получават отстъпка.

). В същото време в руските медии и блогове на руски потребители нараства броят на бележките за този алгоритъм: както отразяващи резултатите от атаки срещу руския стандарт с различна степен на надеждност, така и съдържащи мнения относно неговите оперативни характеристики. Авторите (и съответно читателите) на тези бележки често остават с впечатлението, че местният алгоритъм за криптиране е остарял, бавен и има уязвимости, които го правят значително по-податлив на атаки, отколкото чуждестранните алгоритми за криптиране с подобна дължина на ключа. С тази поредица от бележки бихме искали да ви разкажем в достъпна форма за текущото състояние на нещата с руския стандарт. Първата част ще обхване всички атаки срещу GOST 28147-89, известни на международната криптографска общност и текущите оценки на неговата сила. В бъдещи публикации ще разгледаме по-отблизо свойствата на стандарта от гледна точка на възможността за изграждане на ефективни реализации.

Никола Куртоа - "великият и ужасен"

Нека започнем с разказ за дейността на Никола Куртоа, който е автор на цяла поредица от произведения, посветени на руския стандарт за блоково криптиране ().

През октомври 2010 г. започна процесът на разглеждане на включването на алгоритъма GOST 28147-89 в международния стандарт ISO/IEC 18033-3. Още през май 2011 г. в електронния архив на ePrint се появи статия на известния криптограф Никола Куртоа, белязана от много двусмислено отношение към него от световната криптографска общност. Публикациите на Куртоа са тъжен пример за манипулация на понятия, която не разкрива нови свойства на въпросния обект, а с претенция за сензация провокира разпространението на погрешни мнения за действителните му свойства в некомпетентна среда.

Алгебричен метод

Разсъжденията на Куртоа са изградени около два класа методи за криптоанализ: алгебрични методи и диференциални. Нека разгледаме първия клас методи.

По опростен начин методът на алгебричния криптоанализ може да се опише като съставяне и решаване на голяма система от уравнения, всяко от чиито решения съответства на целта на криптоаналитика (например, ако една система е съставена с помощта на една двойка на обикновен текст и шифрован текст, тогава всички решения на тази система съответстват на ключовете, при които този обикновен текст се преобразува в този е шифрован). Тоест, в случай на проблема с криптоанализа на блоков шифър, същността на алгебричния метод на криптоанализа е, че ключът се намира в резултат на решаване на система от полиномиални уравнения. Основната трудност е да можете да създадете възможно най-проста система, като вземете предвид характеристиките на конкретен шифър, така че процесът на решаването му да отнеме възможно най-малко време. Тук ключова роля играят особеностите на всеки конкретен анализиран шифър.

Алгебричният метод, използван от Куртоа, може да бъде описан накратко по следния начин. На първия етап се използват такива свойства на GOST 28147-89 като наличието на фиксирана точка за част от трансформацията на криптиране, както и така наречената точка на отражение. Благодарение на тези свойства се избират няколко двойки от достатъчно голям брой двойки обикновен текст-шифрован текст, което позволява да се разглеждат трансформации не на 32, а само на 8 кръга. Вторият етап е, че въз основа на резултатите от 8 кръгови трансформации, получени на първия етап, се конструира система от нелинейни уравнения, в която ключовите битове са неизвестни. След това тази система се решава (това звучи просто, но в действителност е най-отнемащата време част от метода, тъй като системата се състои от нелинейни уравнения).

Както беше отбелязано по-горе, никъде в работата няма подробно описание и анализ на сложността на втория и основен етап на определяне на ключа. Именно сложността на втория етап определя сложността на целия метод като цяло. Вместо това авторът предоставя прословутите „факти“, на базата на които прави оценки за интензивността на труда. Твърди се, че тези „факти“ се основават на експериментални резултати. Анализът на „фактите“ от работата на Куртоа като цяло е даден в работата на местни автори. Авторите на тази работа отбелязват, че много от „фактите“ на Куртоа, представени без никакви доказателства, се оказват неверни по време на експериментално тестване. Авторите на статията отидоха по-далеч и, следвайки Куртоа, извършиха анализ на сложността на втория етап, използвайки добре обосновани алгоритми и оценки. Получените оценки на сложността показват пълната неприложимост на представената атака. В допълнение към местните автори, големите проблеми, които има Куртоа с оценките и обосновката на неговите методи, също бяха отбелязани, например, в работата.

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

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

Общият метод на диференциалния криптоанализ се основава на използването на свойствата на нелинейните преобразувания, използвани в криптографските примитиви, свързани с влиянието на стойността на ключа върху зависимостите между разликите между двойки входни и двойки изходни стойности на тези преобразувания . Нека опишем основната идея на диференциалния метод за криптографски анализ на блоков шифър. Обикновено блоковите шифри трансформират входните данни на етапи, като използват редица така наречени кръгли трансформации, като всяка кръгла трансформация не използва целия ключ, а само част от него. Нека разгледаме леко „пресечен“ шифър, който се различава от оригиналния по това, че няма последния кръг. Нека приемем, че е било възможно да се установи, че криптирането на два открити текста, които се различават в някои фиксирани позиции, използвайки такъв „пресечен“ шифър, най-вероятно ще доведе до шифровани текстове, които също се различават в някои фиксирани позиции. Това свойство показва, че „скъсеният“ шифър най-вероятно оставя зависимост между някои открити текстове и резултатите от тяхното криптиране. За да възстановим част от ключа, използвайки този очевиден недостатък, е необходимо да можем да шифроваме предварително избрани обикновени текстове на ключа, който искаме да възстановим (т.нар. „атака с избран обикновен текст“). В началото на процедурата за „отваряне на ключ“ произволно се генерират няколко двойки открити текстове, които се различават по същите фиксирани позиции. Всички текстове са криптирани с помощта на „пълен“ шифър. Получените двойки шифрован текст се използват за възстановяване на тези ключови битове, които са били използвани в последната кръгова трансформация, както следва. Използвайки произволно избрана стойност на желаните ключови битове, към всички шифровани текстове се прилага трансформация, обратна на последната кръгова трансформация. Всъщност, ако сме познали желаната стойност на ключовите битове, ще получим резултата от „пресечен“ шифър, а ако не сме познали, всъщност ще „криптираме данните още повече“, което само ще намали зависимост между блоковете, отбелязани по-горе (разликата е в някои фиксирани позиции). С други думи, ако сред резултатите от такава „допълнителна обработка“ на шифровани текстове имаше доста двойки, които се различават в известните ни фиксирани позиции, това означава, че сме познали необходимите ключови битове. В противен случай ще има значително по-малко такива двойки. Тъй като във всеки кръг се използва само част от ключа, търсените битове (т.е. ключовите битове, използвани в последния кръг) не са толкова много, колкото битовете в пълния ключ и могат просто да бъдат итерирани чрез повтаряне на стъпките по-горе . В този случай определено ще се натъкнем на правилния смисъл някой ден.

От горното описание следва, че най-важното нещо в метода на диференциалния анализ са номерата на тези позиции в откритите и шифрованите текстове, разликите в които играят ключова роля при възстановяването на ключовите битове. Фундаменталното присъствие на тези позиции, както и наборът от техните номера, пряко зависи от свойствата на онези нелинейни трансформации, които се използват във всеки блоков шифър (обикновено цялата „нелинейност“ е концентрирана в така наречените S-кутии или заместващи възли).

Куртоа използва леко модифицирана версия на диференциалния метод. Нека веднага да отбележим, че Куртоа прави своя анализ за S-кутии, които са различни от сегашните и от предложените в ISO. Работата предоставя диференциални характеристики (тези числа, в които блоковете трябва да се различават) за малък брой кръгове. Обосновката за разширяване на характеристиките за повече рундове, както обикновено, се основава на „факти“. Куртоа изразява, отново, с нищо друго освен авторитета си, неподкрепено предположение, че промяната на S-кутиите няма да повлияе на устойчивостта на GOST 28147-89 срещу неговата атака (докато по неизвестни причини S-кутиите от 1-вия работен проект на допълнението към стандарта ISO/IEC 18033-3 не е взето предвид). Анализът, извършен от авторите на статията, показва, че дори ако вземем на вяра необоснованите „факти“ на Куртоа и анализираме GOST 28147-89 с други S-блокове, атаката отново се оказва не по-добра от пълно търсене.

Подробен анализ на произведенията на Куртоа с подробно обосноваване на неоснователността на всички твърдения за намаляване на устойчивостта на руския стандарт е извършен в произведенията [,].

В същото време дори самият Куртоа признава абсолютната липса на точност в изчисленията! Следващият слайд е взет от презентацията на Куртоа в секцията за кратки съобщения на FSE 2012.

Трябва да се отбележи, че работата на Куртоа също е многократно критикувана от чуждестранни изследователи. Например, работата му по изграждането на атаки срещу алгоритъма за блоково криптиране AES, използвайки метода XSL, съдържаше същите фундаментални недостатъци като работата по анализа на руския стандарт: повечето от оценките на трудоемкостта се появяват в текста напълно необосновани и необосновани - подробно критиката може да се намери например в работата. В допълнение, самият Куртоа признава широко разпространени откази да публикува работата си на големи конференции по криптография и в утвърдени рецензирани списания, което често му оставя само възможността да говори в секцията с кратки съобщения. Например, можете да прочетете за това в раздел 3 на работата. Ето някои цитати от самия Куртоа, свързани с работата му:

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

Така професионалната част от международната криптографска общност гледа на качеството на работата на Куртоа с не по-малко съмнение, отколкото, да речем, твърденията на някои руски специалисти за способността им да разбият AES за 2100, които не са потвърдени от никакви последователни изчисления, или последно „доказателство“ за хипотеза от две страници за неравенството на класовете на сложност 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 кръга на криптиране по GOST 28147-89 чрез Swap - операцията за размяна на половини от 64-байтова дума. Ако откритият текст е включен в този набор, резултатът от пълното 32-кръгово преобразуване на GOST 28147-89 съвпада с резултата от 16-кръговото, което авторът на атаката използва. В случая на метода DDS, това е множеството от x, така че F 8 (x) = x (фиксирана точка на трансформацията F 8). За всеки обикновен текст от този набор трансформацията GOST 28147-89 работи точно както последните 8 кръга, което опростява анализа.

Сложността на атаката Isobe е 2224 операции за криптиране, DDS атаката е 2192. Въпреки това, всички въпроси за това дали Isobe и DDS атаките въвеждат нови ограничения върху условията за използване на нашия алгоритъм се отстраняват чрез оценка на изискванията за обема на материала, необходим за извършване на всяка от атаките: методът Isobe изисква 2 32 двойки обикновен текст и шифрован текст, а за метода DDS - 2 64. Обработката на такива обеми от материал без промяна на ключа е a priori неприемлива за всеки блоков шифър с дължина на блока 64: върху материал от том 2 32, като се вземе предвид проблемът с рождените дни (вижте например ), вероятността за поява на повтарящи се блокове е близо до 1/2, което ще осигури на атакуващия възможност да направи определени заключения относно откритите текстове от шифрованите текстове, без да определя ключа. Наличието на 2 64 двойки обикновени и криптирани текстове, получени на един ключ, всъщност позволява на врага да извършва операции по криптиране и декриптиране, без изобщо да знае този ключ. Това се дължи на чисто комбинаторно свойство: врагът в този случай разполага с цялата таблица за преобразуване на криптиране. Тази ситуация е абсолютно неприемлива при никакви разумни условия на работа. Например в CryptoPro CSP има техническо ограничение за обема на криптирания материал (без преобразуване на ключ) от 4 MB (вижте). По този начин строгата забрана за използване на ключ върху материал с такъв обем е присъща на всеки блоков шифър с дължина на блока 64 бита и следователно Isobe и DDS атаките по никакъв начин не стесняват обхвата на използване на алгоритъма GOST 28147-89 при запазване на максималната възможна сила от 2256.

Разбира се, трябва да се отбележи, че изследователите (Isobe и Dinur-Dankelman-Shamir) са показали, че някои свойства на алгоритъма GOST 28147-89 позволяват да се намерят пътища за анализ, които не са взети предвид от създателите на алгоритъма. Простата форма на графика на ключовете, която значително опростява задачата за конструиране на ефективни реализации, също така позволява някои редки случаи на ключове и обикновени текстове да конструират по-прости описания на трансформациите, произведени от алгоритъма.

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

Имайте предвид, че известна небрежност в оценките на средната интензивност на труда присъства и в работата на Dinur, Dunkelman и Shamir. По този начин, когато се конструира атака, не се обръща дължимото внимание на следната точка: за значителна част от ключовете наборът от открити текстове x, така че F 8 (x) = x, е празен: може просто да няма фиксирани точки за 8 кръга на трансформация. Наличието на фиксирани точки също зависи от избора на заместващи възли. По този начин атаката е приложима само за определени заместващи възли и ключове.

Заслужава да се спомене още една работа с атака срещу GOST 28147-89. През февруари 2012 г. в електронния архив ePrint на международната криптографска асоциация се появи актуализирана версия на статията (от ноември 2011 г.), която съдържаше нова атака срещу GOST 28147-89. Характеристиките на представената атака са следните: обемът на материала е 2 32 (като Isobe), а трудоемкостта е 2 192 (като DDS). По този начин тази атака подобри DDS атаката за времеви запис по отношение на обема на материала от 2 64 на 2 32. Отделно отбелязваме, че авторите честно представиха всички изчисления с обосновка за сложността и обема на материала. След 9 месеца беше открита фундаментална грешка в горните изчисления и от ноември 2012 г. актуализираната версия на статията в електронния архив вече не съдържа никакви резултати по отношение на домашния алгоритъм.

Атаки, предполагащи, че нападателят знае "нещо" за ключовете

Нека накрая да отбележим, че в литературата има и редица произведения (вижте например и ), посветени на атаките срещу GOST 28147-89 в така наречения модел на свързания ключ. Този модел основно съдържа предположението, че атакуващият може да получи достъп за анализ не само до двойки отворени текстове и криптирани с желания ключ, но също и до двойки отворени и криптирани текстове, получени с помощта на (също неизвестни) ключове, които се различават от желания по познат нормален начин (например във фиксирани битови позиции). В този модел наистина е възможно да се получат интересни резултати относно GOST 28147-89, но в този модел е възможно да се получат не по-малко силни резултати относно, например, стандарта AES, който е най-широко използван в съвременните обществени мрежи ( вижте например). Имайте предвид, че условията за извършване на този тип атака възникват при използване на шифър в определен протокол. Трябва да се отбележи, че резултатите от този вид, въпреки че представляват несъмнен академичен интерес от гледна точка на изучаване на свойствата на криптографските трансформации, всъщност не са приложими за практиката. Например, всички инструменти за защита на криптографска информация, сертифицирани от FSB на Русия, отговарят на най-строгите изисквания за схеми за генериране на ключове за криптиране (вижте например). Както е посочено в резултатите от анализа, ако има 18 асоциирани ключа и 2 10 двойки блокове с обикновен текст и шифрован текст, сложността на пълното отваряне на частния ключ, с вероятност за успех 1-10 -4, всъщност е 2 26 . Въпреки това, ако гореспоменатите изисквания за разработване на ключов материал са изпълнени, вероятността за намиране на такива ключове е 2 -4352, тоест 24096 пъти по-малко, отколкото ако просто се опитате да отгатнете секретния ключ при първия опит.

Работите, свързани с модела със свързани ключове, включват и работа, която през 2010 г. предизвика много шум в руските електронни издания, които не страдат от навика внимателно да проверяват материала в надпреварата за сензации. Резултатите, представени в него, не бяха подкрепени от никаква строга обосновка, но съдържаха гръмки изявления за възможността за хакване на държавния стандарт на Руската федерация на слаб лаптоп за няколко секунди - като цяло статията беше написана в най-добрите традиции на Никола Куртоа. Но въпреки абсолютно очевидната неоснователност на статията за читателя, който е повече или по-малко запознат с основните принципи на научните публикации, именно за да успокои руската общественост след работата, Рудски написа подробен и задълбочен текст, съдържащ изчерпателен анализ на този недостатък. Статията със самообясняващо се заглавие „За нулевата практическа значимост на работата „Атака за възстановяване на ключ върху пълен GOST блоков шифър с нулево време и памет““ дава обосновка, че средната сложност на дадения метод е не по-малка от сложността на цялостно търсене.

Сух остатък: какво е трайност на практика?

В заключение представяме таблица, съдържаща данни за всички резултати от строго описани и обосновани атаки срещу GOST 28147-89, известни на международната криптографска общност. Имайте предвид, че сложността е дадена в операциите за криптиране на алгоритъма GOST 28147-89, а паметта и материалът са посочени в блокове на алгоритъма (64 бита = 8 байта).

Атака	Интензивност на труда	памет	Необходим материал
Изобе	2 224	2 64	2 32
Динур-Данкелман-Шамир, FP, 2DMitM	2 192	2 36	2 64
Dinur-Dankelman-Shamir, FP, ниска памет	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

Въпреки доста широкомащабния цикъл на изследване в областта на устойчивостта на алгоритъма GOST 28147-89, в момента не е известна нито една атака, условията за изпълнението на която биха били постижими със съпътстващите оперативни изисквания за дължина на блока от 64 бита. Ограниченията за обема на материала, който може да бъде обработен на един ключ, произтичащи от параметрите на шифъра (дължина на битовете на ключа, дължина на битовете на блока) са значително по-строги от минималния обем, необходим за извършване на всяка известна атака. Следователно, когато отговаря на съществуващите оперативни изисквания, нито един от методите за криптоанализ, предложени към днешна дата GOST 28147-89, не позволява определяне на ключ с трудоемкост, по-малка от изчерпателното търсене.

GOST 28147-89 алгоритъм за криптиране, неговото използване и софтуерна реализация за компютри на платформата Intel x86.

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

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

Термини и обозначения.

Описание на стандарта за криптиране на Руската федерация се съдържа в много интересен документ, озаглавен „Алгоритъм за криптографско преобразуване GOST 28147-89“. Фактът, че в името му вместо термина „криптиране“ фигурира по-общо понятие „ криптографско преобразуване ”, не е никак случайно. В допълнение към няколко тясно свързани процедури за криптиране, документът описва един алгоритъм за генериране имитации на вложки . Последното не е нищо повече от криптографска контролна комбинация, тоест код, генериран от оригиналните данни с помощта на таен ключ за целите на имитационна защита , или защита на данните от неоторизирани промени.

На различни стъпки на GOST алгоритмите, данните, с които работят, се интерпретират и използват по различни начини. В някои случаи елементите от данни се третират като масиви от независими битове, в други случаи като цяло число без знак, в трети като структуриран сложен елемент, състоящ се от няколко по-прости елемента. Следователно, за да се избегне объркване, е важно да се съгласите относно използваната нотация.

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

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

В алгоритъма елемент от данни може да се интерпретира като масив от отделни битове, в който случай битовете се обозначават със същата буква като масива, но във версия с малки букви, както е показано в следния пример:

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

По този начин, ако сте забелязали, е приет така нареченият GOST. “little-endian” номериране на цифри, т.е. В рамките на многобитовите думи с данни отделните битове и групите от битове с по-нисък номер са по-малко значими. Това е директно посочено в параграф 1.3 от стандарта: „При добавяне и циклично преместване на двоични вектори най-значимите битове се считат за битове на устройства с големи числа.“ Освен това клаузите на стандарта 1.4, 2.1.1 и други изискват започване на запълване на регистрите за съхранение на виртуалното криптиращо устройство с данни от най-ниските, т.е. по-малко значими категории. Точно същият ред на номериране е възприет в микропроцесорната архитектура Intel x86, поради което при внедряването на шифър в софтуера на тази архитектура не са необходими допълнителни пермутации на битове в думите с данни.

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

Логиката на конструиране на шифър и структурата на ключовата информация на GOST.

Ако внимателно проучите оригиналния GOST 28147–89, ще забележите, че той съдържа описание на алгоритмите на няколко нива. На самия връх има практични алгоритми, предназначени за криптиране на масиви от данни и разработване на имитативни вложки за тях. Всички те се основават на три алгоритъма от ниско ниво, наречени в текста на GOST цикли . Тези основни алгоритми са посочени в тази статия като основни цикли за да ги разграничим от всички останали цикли. Те имат следните имена и символи, като последните са дадени в скоби и тяхното значение ще бъде обяснено по-късно:

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

От своя страна, всеки от основните цикли е многократно повторение на една единствена процедура, призована за определеност по-нататък в тази работа основната стъпка на крипто конвертирането .

По този начин, за да разберете GOST, трябва да разберете следните три неща:

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

Преди да преминем към изучаването на тези въпроси, трябва да говорим за ключовата информация, използвана от алгоритмите на GOST. В съответствие с принципа на Кирхоф, на който отговарят всички съвременни шифри, известни на широката публика, именно неговата секретност осигурява тайната на криптираното съобщение. В GOST ключовата информация се състои от две структури от данни. Освен действителното ключ , необходими за всички шифри, той също съдържа таблица за заместване . По-долу са основните характеристики на ключовите структури на GOST.

Основната стъпка на крипто конвертирането.

Основната стъпка на крипто преобразуване е по същество изявление, което уточнява преобразуването на 64-битов блок от данни. Допълнителен параметър на този оператор е 32-битов блок, който се използва като ключов елемент. Диаграмата на основния алгоритъм на стъпки е показана на фигура 1.

Фигура 1. Схема на основната стъпка на криптопреобразуване на алгоритъма GOST 28147-89.

По-долу са дадени обяснения на алгоритъма на основните стъпки:

Стъпка 0

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

Етап 1

Допълване с ключ. Долната половина на преобразувания блок се добавя по модул 2 32 с ключовия елемент, използван в стъпката, резултатът се прехвърля към следващата стъпка;

Стъпка 2

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

След това стойността на всеки от осемте блока се заменя с нова, която се избира от таблицата за заместване, както следва: стойност на блок S iпромени в S i-ти елемент по ред (номериране от нула) аз-този заместващ възел (т.е. аз-ти ред от таблицата за заместване, номериране също от нулата). С други думи, елемент от таблицата за заместване с номер на ред, равен на номера на блока, който се замества, и номер на колона, равен на стойността на блока, който се замества като 4-битово неотрицателно цяло число, се избира като заместител за стойността на блока. Това прави размера на заместващата таблица ясен: броят на редовете в нея е равен на броя на 4-битовите елементи в 32-битов блок данни, тоест осем, а броят на колоните е равен на броя на различни стойности на 4-битов блок от данни, за който е известно, че е 2 4, шестнадесет.

Стъпка 3

Завъртете 11 бита наляво. Резултатът от предишната стъпка се измества циклично с 11 бита към най-значимите битове и се предава на следващата стъпка. В диаграмата на алгоритъма символът показва функцията за циклично изместване на своя аргумент с 11 бита наляво, т.е. към по-високите чинове.

Стъпка 4

Побитово събиране: Стойността, получена в стъпка 3, се добавя побитово по модул 2, като горната половина на блока се преобразува.

Стъпка 5

Преместване по веригата: долната част на конвертирания блок се измества на мястото на по-стария и резултатът от предишната стъпка се поставя на негово място.

Стъпка 6

Получената стойност на конвертирания блок се връща като резултат от изпълнението на алгоритъма на основната стъпка на крипто преобразуване.

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

Както беше отбелязано в началото на тази статия, GOST принадлежи към класа на блоковите шифри, тоест единицата за обработка на информация в него е блок от данни. Следователно е съвсем логично да се очаква, че той ще дефинира алгоритми за криптографски трансформации, тоест за криптиране, декриптиране и „отчитане“ на контролна комбинация от един блок от данни. Тези алгоритми се наричат основни цикли GOST, който подчертава тяхното фундаментално значение за изграждането на този шифър.

Основните цикли са изградени от основни стъпки криптографска трансформация, обсъдена в предишния раздел. По време на основната стъпка се използва само един 32-битов ключов елемент, докато GOST ключът съдържа осем такива елемента. Следователно, за да може ключът да се използва напълно, всеки от основните цикли трябва многократно да изпълнява основната стъпка с различните й елементи. В същото време изглежда съвсем естествено във всеки основен цикъл всички ключови елементи да се използват еднакъв брой пъти; от съображения за сила на шифъра този брой трябва да бъде повече от един.

Всички предположения, направени по-горе, базирани просто на здравия разум, се оказаха верни. Основните цикли се състоят от многократно изпълнение основна стъпка използвайки различни ключови елементи и се различават един от друг само по броя на повторенията на стъпките и реда, в който се използват ключовите елементи. По-долу е тази поръчка за различни цикли.

Цикъл на криптиране 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 .

Фигура 2b. Схема на цикъла на дешифриране 32-P

Производствен цикъл на имитация на вложка 16-Z:

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

Фигура 2c. Схема на производствения цикъл на имитация на вложка 16-Z.

Всеки от циклите има собствено буквено-цифрово обозначение, съответстващо на шаблона „ n-X", където първият елемент от обозначението ( н), определя броя на повторенията на основната стъпка в цикъла, а вторият елемент за обозначаване ( х), буква, определя реда на криптиране („Z“) или декриптиране („P“) при използването на ключови елементи. Тази поръчка се нуждае от допълнително обяснение:

Цикълът на дешифриране трябва да бъде обратен на цикъла на криптиране, т.е. последователното прилагане на тези два цикъла към произволен блок трябва в крайна сметка да доведе до оригиналния блок, което се отразява в следната връзка: ° С 32-Р ( ° С 32-З ( T))= Т, Където T– произволен 64-битов блок от данни, ° СХ ( T) – резултатът от изпълнението на цикъла хнад блока с данни T. За да се изпълни това условие за алгоритми, подобни на GOST, е необходимо и достатъчно редът на използване на ключовите елементи от съответните цикли да е взаимно обратен. Лесно е да се провери валидността на писменото условие за разглеждания случай чрез сравняване на горните последователности за цикли 32-З и 32-Р. Едно интересно следствие следва от горното: свойството на един цикъл да е обратен на друг цикъл е реципрочно, т.е. цикълът 32-Z е обратен на цикъла 32-P. С други думи, криптирането на блок от данни може теоретично да се извърши с помощта на цикъл на декриптиране, в който случай декриптирането на блок от данни трябва да се извърши чрез цикъл на криптиране. От двата взаимно обратни цикъла, единият може да се използва за криптиране, тогава вторият трябва да се използва за декриптиране на данни, но стандартът GOST 28147-89 присвоява роли на цикли и не дава на потребителя право на избор по този въпрос .

Цикълът за създаване на имитативна вложка е наполовина по-дълъг от циклите на криптиране, редът на използване на ключови елементи в него е същият като в първите 16 стъпки на цикъла на криптиране, което е лесно да се провери, като се вземат предвид горните последователности, следователно този ред в обозначението на цикъла е кодиран със същата буква "Z".

Схеми на основни цикли са показани на фигури 2a-c. Всеки от тях приема като аргумент и връща като резултат 64-битов блок от данни, посочени в диаграмите н. Стъпка на символа ( н,х) обозначава изпълнението на основната стъпка на крипто-трансформация за блок от данни низползване на ключов елемент х. Има още една разлика между изчислителните цикли на криптиране и имитативно вмъкване, която не е спомената по-горе: в края на основните цикли на криптиране високите и ниските части на резултатния блок се разменят, това е необходимо за тяхната взаимна обратимост.

Основни режими на криптиране.

GOST 28147-89 предоставя следните три режима на криптиране на данни:

• проста подмяна,
• игри,
• игри с обратна връзка,

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

Във всеки от тези режими данните се обработват в блокове от 64 бита, на които масивът се разделя и се подлага на криптографска трансформация, поради което GOST се отнася до блокови шифри. Въпреки това, в два гама режима е възможно да се обработи непълен блок от данни с размер под 8 байта, което е от съществено значение при криптиране на масиви от данни с произволен размер, който може да не е кратен на 8 байта.

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

TО, T w – масиви от отворени и съответно криптирани данни;

, – аз- последователни 64-битови блокове съответно отворени и криптирани данни: , , последният блок може да е непълен: ;

н– брой 64-битови блокове в масива от данни;

° С X – функция за преобразуване на 64-битов блок от данни с помощта на алгоритъм с основен цикъл „X“.

Сега ще опишем основните режими на криптиране:

Лесна подмяна.

Шифроването в този режим се състои от прилагане на цикъл 32-З към блокове с отворени данни, декриптиране - цикъл 32-Р към блокове с криптирани данни. Това е най-простият от режимите; 64-битовите блокове от данни се обработват независимо един от друг. Схемите на алгоритмите за криптиране и декриптиране в режим на проста замяна са показани съответно на фигури 3a и b; те са тривиални и не се нуждаят от коментари.

рисуване. 3а. Алгоритъм за криптиране на данни в режим на проста замяна

рисуване. 3б. Алгоритъм за дешифриране на данни в режим на проста замяна

Размерът на масива от отворени или криптирани данни, подлежащ на съответно криптиране или декриптиране, трябва да бъде кратен на 64 бита: | T о |=| T w |=64· н , след извършване на операцията размерът на получения масив от данни не се променя.

Режимът на просто заместващо криптиране има следните характеристики:

• Тъй като блоковете с данни са криптирани независимо един от друг и тяхната позиция в масива от данни, криптирането на два идентични блока с обикновен текст води до идентични блокове с шифрован текст и обратно. Отбелязаното свойство ще позволи на криптоаналитика да направи заключение за идентичността на оригиналните блокове данни, ако срещне идентични блокове в криптирания масив от данни, което е неприемливо за сериозен шифър.
• Ако дължината на криптирания масив от данни не е кратна на 8 байта или 64 бита, възниква проблемът как и как да се допълни последният непълен блок от данни на масива до пълните 64 бита. Тази задача не е толкова проста, колкото изглежда на пръв поглед. Очевидни решения като „допълване на непълен блок с нула битове“ или, по-общо, „допълване на непълен блок с фиксирана комбинация от нула и един бит“ могат, при определени условия, да дадат на криптоаналитика възможността да използва методи на груба сила, за да определи съдържанието на този много непълен блок и този факт означава намаляване на шифъра за сигурност. В допълнение, дължината на шифрования текст ще се промени, увеличавайки се до най-близкото цяло число, кратно на 64 бита, което често е нежелателно.

На пръв поглед горните функции правят почти невъзможно използването на режима на проста замяна, тъй като той може да се използва само за криптиране на масиви от данни с размер, кратен на 64 бита, и не съдържа повтарящи се 64-битови блокове. Изглежда, че за всякакви реални данни е невъзможно да се гарантира изпълнението на тези условия. Това е почти вярно, но има едно много важно изключение: не забравяйте, че размерът на ключа е 32 байта, а размерът на таблицата за заместване е 64 байта. В допълнение, наличието на повтарящи се 8-байтови блокове в ключ или таблица за заместване ще покаже тяхното много лошо качество, така че такова повторение не може да съществува в реални ключови елементи. По този начин открихме, че режимът на проста замяна е доста подходящ за криптиране на ключова информация, особено след като другите режими са по-малко удобни за тази цел, тъй като изискват допълнителен синхронизиращ елемент от данни - съобщение за синхронизиране (вижте следващия раздел). Нашето предположение е правилно; GOST предписва използването на прост режим на замяна изключително за криптиране на ключови данни.

Гумиране.

Как можете да се отървете от недостатъците на режима на проста подмяна? За да направите това, е необходимо да се направи възможно криптирането на блокове с размер по-малък от 64 бита и да се гарантира, че блокът с шифрован текст зависи от неговия номер, с други думи, произволно процес на криптиране. В GOST това се постига по два различни начина в два режима на криптиране, осигуряващи хазартни игри . Гумиране - това е налагането (премахването) на криптографска скала върху отворени (криптирани) данни, тоест последователност от елементи на данни, генерирани с помощта на някакъв криптографски алгоритъм за получаване на криптирани (отворени) данни. За да се приложи гама по време на криптиране и да се премахне по време на декриптиране, трябва да се използват взаимно обратни двоични операции, например събиране и изваждане по модул 2 64 за 64-битови блокове от данни. В GOST за тази цел се използва операцията на побитово добавяне по модул 2, тъй като тя е обратна на себе си и освен това е най-просто реализирана в хардуера. Гама решава и двата споменати проблема: първо, всички гама елементи са различни за реални криптирани масиви и следователно резултатът от криптирането дори на два идентични блока в един масив от данни ще бъде различен. Второ, въпреки че гама елементите се генерират на равни части от 64 бита, може да се използва част от такъв блок с размер, равен на размера на криптирания блок.

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

RGPG, използван за генериране на скалата, е повтаряща се функция: – елементи от повтарящата се последователност, f– трансформационна функция. Следователно неизбежно възниква въпросът за неговата инициализация, тоест за елемента , Всъщност този елемент от данни е параметър на алгоритъма за гама режими, в диаграмите той се обозначава като С, и се нарича в криптографията синхронизиране изпращане , а в нашия ГОСТ – първоначално запълване един от регистрите на енкодера. По определени причини разработчиците на GOST решиха да използват не съобщението за синхронизиране директно за инициализиране на RGFC, а резултата от неговото преобразуване според цикъла 32-Z: . Последователността от елементи, генерирани от RGHR, зависи изцяло от нейното първоначално запълване, тоест елементите на тази последователност са функция на техния брой и първоначалното запълване на RGHR: където f i(х)=f(f i –1 (х)), f 0 (х)=х. Като се вземе предвид трансформацията с помощта на простия алгоритъм за заместване, се добавя и зависимост от ключа:

Където Г i– аз-ти елемент от скалата, К- ключ.

По този начин последователността от гама елементи, които трябва да се използват в гама режим, се определя еднозначно от ключовите данни и съобщението за синхронизиране. Естествено, за да бъде процедурата за криптиране обратима, трябва да се използва едно и също съобщение за синхронизиране в процесите на криптиране и декриптиране. От изискването за уникалност на гамата, неспазването на което води до катастрофално намаляване на силата на шифъра, следва, че за да се криптират два различни масива от данни на един и същи ключ, е необходимо да се осигури използването на различни съобщения за синхронизация. Това води до необходимостта от съхраняване или предаване на съобщението за синхронизация по комуникационните канали заедно с криптираните данни, въпреки че в някои специални случаи то може да бъде предварително определено или изчислено по специален начин, ако се изключи криптиране на два масива с един и същи ключ.

Сега нека разгледаме по-отблизо RGPC, използван в GOST за генериране на елементи на гамата. На първо място, трябва да се отбележи, че не се изисква да се предоставят никакви статистически характеристики на генерираната последователност от числа. RGHR е проектиран от разработчиците на GOST въз основа на необходимостта да се изпълнят следните условия:

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

Въз основа на изброените принципи, създателите на GOST проектират много успешен RGHR, който има следните характеристики:

Където ° С 0 =1010101 16 ;

Където ° С 1 =1010104 16 ;

Долният индекс в число показва неговата бройна система, така че константите, използвани в тази стъпка, се записват в шестнадесетичен формат.

Вторият израз се нуждае от коментари, тъй като текстът на GOST съдържа нещо друго: , със същата стойност на константата ° С 1 . Но по-нататък в текста на стандарта е даден коментар, че се оказва, че при операцията за вземане на остатъка по модул 2 32 –1 тамне се разбира по същия начин, както в математиката. Разликата е, че според GOST (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

Дефинира входните данни за основната стъпка на криптовалута:

• T o(w) – масив от отворени (криптирани) данни с произволен размер, подложени на процедура за криптиране (декриптиране), по време на която масивът се конвертира на 64-битови части;
• С – съобщение за синхронизиране , 64-битов елемент от данни, необходим за инициализиране на гама генератора;

Етап 1

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

Стъпка 2

Една стъпка от операцията на RGPC, прилагаща неговия повтарящ се алгоритъм. По време на тази стъпка най-големият ( С 1) и младши ( С 0) части от последователността от данни се генерират независимо една от друга;

Стъпка 3

Гумиране. Следващият 64-битов елемент, генериран от RGPC, се подлага на процедура за криптиране с помощта на цикъл 32-3, резултатът се използва като гама елемент за криптиране (декриптиране) на следващия блок от отворени (криптирани) данни със същия размер.

Стъпка 4

Резултатът от алгоритъма е криптиран (декриптиран) масив от данни.

Следните са характеристиките на гама като режим на криптиране:

1. Идентични блокове в отворен масив от данни ще дадат различни блокове с шифрован текст, когато бъдат криптирани, което ще направи възможно скриването на факта на тяхната идентичност.
2. Тъй като гама наслагването се извършва побитово, криптирането на частичен блок от данни се постига лесно чрез криптиране на битовете на този частичен блок чрез използване на съответните битове на гама блока. По този начин, за криптиране на непълен блок от 1 бит, според стандарта, трябва да се използва най-младшият бит от гама блока.
3. Съобщението за синхронизиране, използвано за криптиране, трябва по някакъв начин да бъде предадено за използване при декриптиране. Това може да се постигне по следните начини:

• съхранява или предава съобщение за синхронизиране заедно с криптиран масив от данни, което ще доведе до увеличаване на размера на масива от данни, когато е криптиран с размера на съобщението за синхронизиране, тоест с 8 байта;
• използвайте предварително определена стойност на съобщението за синхронизация или го генерирайте синхронно от източника и приемника по определен закон, в този случай няма промяна в размера на предавания или съхранен масив от данни;

И двата метода се допълват взаимно и в онези редки случаи, когато първият, най-често срещаният не работи, може да се използва вторият, по-екзотичен. Вторият метод има много по-малко приложение, тъй като е възможно да се направи предварително зададено съобщение за синхронизиране само ако не повече от един масив от данни е криптиран върху даден набор от ключова информация, което не се случва много често. Също така не винаги е възможно да се генерира синхронизиращо съобщение синхронно при източника и получателя на масив от данни, тъй като изисква стриктна връзка с нещо в системата. По този начин една привидно здрава идея да се използва номерът на предаденото съобщение като съобщение за синхронизация в система за предаване на криптирани съобщения не е подходяща, тъй като съобщението може да бъде загубено и да не достигне до получателя, в който случай системите за криптиране на източника и приемникът ще се десинхронизира. Следователно в разглеждания случай няма алтернатива на предаването на съобщението за синхронизиране заедно с шифрованото съобщение.

От друга страна може да се даде обратен пример. Да кажем, че криптирането на данни се използва за защита на информацията на диска и се изпълнява на ниско ниво; за да се осигури независим достъп, данните се криптират по сектори. В този случай е невъзможно да се съхрани съобщението за синхронизиране заедно с криптираните данни, тъй като размерът на сектора не може да бъде променен, но може да бъде изчислен като някаква функция на номера на четящата глава на диска, номера на пистата (цилиндъра) и номера на сектора на пистата. В този случай съобщението за синхронизация е обвързано с позицията на сектора на диска, което е малко вероятно да се промени без преформатиране на диска, тоест без унищожаване на данните в него.

Гама режимът има още една интересна функция. В този режим битовете на масива от данни се криптират независимо един от друг. Така всеки бит от шифрования текст зависи от съответния бит от открития текст и, разбира се, от поредния номер на бита в масива: . Това означава, че промяната на бит за шифрован текст на противоположната стойност ще доведе до подобна промяна на противоположната стойност на бит на обикновен текст:

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

Това свойство дава на атакуващия възможност, чрез въздействие върху битовете на шифрования текст, да направи предсказуеми и дори целенасочени промени в съответния открит текст, получен след дешифриране, без да притежава секретния ключ. Това илюстрира добре известния факт в криптологията, че тайната и автентичността са различни свойства криптографски системи . С други думи, свойствата на криптосистемата да осигурява защита срещу неоторизиран достъп до съдържанието на съобщение и срещу неоторизирани промени в съобщение са независими и могат да се припокриват само в определени случаи. Това означава, че има криптографски алгоритми, които осигуряват определена секретност на криптираните данни и в същото време не предпазват от промени по никакъв начин, и обратното, гарантирайки автентичността на данните и по никакъв начин не ограничавайки възможността за запознаване с тях. Поради тази причина разглежданото свойство на гама режима не трябва да се счита за негов недостатък.

Гама с обратна връзка.

Този режим е много подобен на гама режима и се различава от него само по начина, по който се генерират гама елементите - следващият гама елемент се генерира в резултат на трансформацията от 32-3 цикъла на предишния блок от криптирани данни и за криптиране първият блок от масива от данни, гама елементът се генерира в резултат на същия цикъл на синхронизация на трансформацията. Това постига блокова верига - всеки блок с шифрован текст в този режим зависи от съответния и всички предишни блокове с обикновен текст. Следователно този режим понякога се нарича игри с блокиращи блокове . Фактът, че блоковете са свързани, няма ефект върху силата на шифъра.

Диаграмата на алгоритмите за криптиране и декриптиране в гама режим с обратна връзка е показана на фигура 5 и поради своята простота не се нуждае от коментари.

Фигура 5. Алгоритъм за криптиране (декриптиране) на данни в гама режим с обратна връзка.

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

гумиране;

Гама с обратна връзка;

Ако в редовния гама режим промените в определени битове от шифротекста засягат само съответните битове от открития текст, то в гама режима с обратна връзка картината е малко по-сложна. Както може да се види от съответното уравнение, когато се декриптира блок от данни в гама-режим със затворен контур, блокът с отворени данни зависи от съответните и предишните криптирани блокове от данни. Следователно, ако въведете изкривявания в криптиран блок, тогава след декриптиране ще бъдат изкривени два блока с отворени данни - съответният и този след него, като изкривяванията в първия случай ще бъдат от същото естество като в гама режим , а във втория случай - както при лесната замяна. С други думи, в съответния блок с отворени данни същите битове ще бъдат повредени, както в блока с криптирани данни, а в следващия блок с отворени данни всички битове са независими един от друг с вероятност 1 / 2 ще променят стойностите си.

Разработване на симулирана вложка за масива от данни.

В предишните раздели обсъдихме влиянието на повредата на криптирани данни върху съответните обикновени данни. Установихме, че при декриптиране в режим проста замяна съответният блок от отворени данни се оказва изкривен по непредсказуем начин, а при декриптиране на блок в режим гама промените са предвидими. В гама режим със затворен контур два блока се изкривяват, единият по предвидим начин, а другият по непредсказуем начин. Означава ли това, че от гледна точка на защита срещу налагане на фалшиви данни гама режимът е лош, а гама режимите проста замяна и обратна връзка са добри? - В никакъв случай. Когато се анализира тази ситуация, е необходимо да се вземе предвид, че непредсказуемите промени в дешифриран блок от данни могат да бъдат открити само ако същите тези данни са излишни и колкото по-голяма е степента на излишък, толкова по-вероятно е откриването на изкривяване. Много голям излишък възниква, например, за текстове на естествени и изкуствени езици, в този случай фактът на изкривяване се открива почти неизбежно. Въпреки това, в други случаи, например, когато компресираните цифровизирани звукови изображения са изкривени, ние просто ще получим различно изображение, което ухото ни може да възприеме. Изкривяването в този случай ще остане неоткрито, освен ако, разбира се, няма предварителна информация за естеството на звука. Изводът тук е следният: тъй като способността на някои режими на криптиране да откриват изкривявания, въведени в криптираните данни, зависи значително от наличието и степента на излишък на криптираните данни, тази способност не е присъщо свойство на съответните режими и не може да се счита за тяхното предимство.

За да се реши проблемът с откриването на изкривявания в криптиран масив от данни с дадена вероятност, GOST предвижда допълнителен режим на криптографска трансформация - разработването на имитативно вмъкване. Имитационна вложка е контролна комбинация, която зависи от отворени данни и секретна информация за ключ. Целта на използването на имитативно вмъкване е да се открият всички случайни или умишлени промени в информационния масив. Проблемът, описан в предишния параграф, може да бъде успешно решен чрез добавяне на имитативни вмъквания към криптираните данни. За потенциален нападател следните две задачи са почти невъзможни за решаване, ако той няма ключа:

• изчисляване на имитативно вмъкване за даден отворен масив от информация;
• избор на отворени данни за дадена симулационна вложка;

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

Фигура 6. Алгоритъм за разработване на симулирана вложка за масив от данни.

Част от блока, получен на изхода, се приема като симулирано вмъкване, обикновено неговите 32 най-малко значими бита. При избора на размера на фалшивата вложка трябва да се има предвид, че вероятността за успешно налагане на фалшиви данни е равна на 2 –| аз | на опит за селекция, ако нападателят няма на разположение по-ефективен метод за селекция от обикновеното отгатване. Когато използвате 32-битово симулирано вмъкване, тази вероятност е равна на

Обсъждане на GOST криптографски алгоритми.

Криптографска сила на GOST.

При избора на криптографски алгоритъм за използване в конкретна разработка, един от определящите фактори е неговата сила, тоест устойчивостта на опитите на противника да го разкрие. Въпросът за силата на шифъра, при по-внимателно разглеждане, се свежда до два взаимосвързани въпроса:

• Възможно ли е изобщо да се разбие този шифър?
• ако е така, колко трудно е да се направи на практика;

Шифрове, които изобщо не могат да бъдат разбити, се наричат ​​абсолютно или теоретично силни. Съществуването на такива шифри е доказано от теоремата на Шанън, но цената на тази сила е необходимостта да се използва ключ за криптиране на всяко съобщение, който не е по-малък по размер от самото съобщение. Във всички случаи, с изключение на редица специални, тази цена е прекомерна, така че на практика се използват предимно шифри, които не са абсолютно сигурни. По този начин най-често срещаните схеми за криптиране могат да бъдат разбити за крайно време или по-точно за краен брой стъпки, всяка от които е някаква операция върху числа. За тях най-важното понятие е практическата постоянство, което изразява практическата трудност на тяхното откритие. Количествена мярка за тази трудност може да бъде броят на елементарните аритметични и логически операции, които трябва да бъдат извършени, за да се отвори шифърът, тоест, за да се определи съответният открит текст за даден шифрован текст с вероятност не по-малка от дадена стойност. В същото време, в допълнение към декриптирания масив от данни, криптоаналитикът може да има блокове от отворени данни и съответните криптирани данни или дори способността да получи съответните криптирани данни за всякакви отворени данни, които избере - в зависимост от изброените и много други неуточнени условия се разграничават отделни видове криптоанализ.

Всички съвременни криптосистеми са изградени на принципа на Кирхоф, тоест тайната на криптираните съобщения се определя от тайната на ключа. Това означава, че дори ако самият алгоритъм за криптиране е известен на криптоаналитика, той все пак не може да дешифрира съобщението, ако не разполага с подходящия ключ. Един шифър се счита за добре проектиран, ако няма начин да бъде разбит по-ефективно от груба сила върху цялото ключово пространство, т.е. над всички възможни ключови стойности. GOST вероятно отговаря на този принцип - през годините на интензивни изследвания не е предложен нито един ефективен метод за неговия криптоанализ. По отношение на силата, той е с много порядъци по-добър от предишния американски стандарт за криптиране, DES.

GOST използва 256-битов ключ и обемът на ключовото пространство е 2256. Нито едно от електронните устройства, които съществуват в момента или се очаква да бъдат внедрени в близко бъдеще, не може да се използва за вземане на ключ за време, по-малко от много стотици години. Тази стойност се превърна в де факто стандарт за размера на ключа за симетрични криптографски алгоритми в наши дни, а новият стандарт за криптиране на САЩ също я поддържа. Бившият американски стандарт, DES, с неговия реален размер на ключа от 56 бита и обем на ключовото пространство от само 2 56 вече не е достатъчно стабилен в светлината на възможностите на съвременните изчислителни инструменти. Това беше демонстрирано в края на 90-те години чрез няколко успешни груби опити за разбиване на DES. В допълнение, DES беше податлив на специални техники за криптоанализ като диференциален и линеен. В това отношение DES може да представлява по-скоро изследователски или научен, отколкото практически интерес. През 1998 г. неговата криптографска слабост беше официално призната - Националният институт по стандарти на САЩ препоръча използването на тройно DES криптиране. И в края на 2001 г. беше официално одобрен нов американски стандарт за криптиране, AES, изграден на различни принципи и лишен от недостатъците на своя предшественик.

Бележки за архитектурата на GOST.

Добре известно е, че вътрешният стандарт за криптиране е представител на цяло семейство шифри, изградени на същите принципи. Най-известният му „роднина“ е бившият американски стандарт за криптиране, алгоритъмът DES. Всички тези шифри, като GOST, съдържат алгоритми на три нива. В основата винаги има определена „основна стъпка“, въз основа на която по подобен начин се изграждат „основни цикли“ и на тяхна основа се изграждат практически процедури за криптиране и разработване на имитативни вложки. По този начин спецификата на всеки един от шифрите от това семейство се състои именно в неговата основна стъпка или по-скоро дори в нейната част. Въпреки че архитектурата на класическите блокови шифри, към които се отнася GOST, е далеч извън обхвата на тази статия, все пак си струва да кажете няколко думи за нея.

Алгоритмите за „основните стъпки на крипто-трансформация“ за шифри като GOST са изградени по идентичен начин и тази архитектура се нарича балансирана мрежа на Feistel (балансирана мрежа на Feistel) след името на лицето, което първо го е предложило. Схема за преобразуване на данни в един цикъл или, както обикновено се нарича, кръгъл , е показано на фигура 7.

Фигура 7. Съдържание на основната стъпка на крипто-трансформация за блокови шифри, подобни на GOST.

На входа на основното стъпало се подава блок с равен размер, горната и долната половина на който се обработват отделно една от друга. По време на преобразуването долната половина на блока се поставя на мястото на по-старата половина, а по-старата половина се комбинира с помощта на побитовата операция изключителен или ” с резултат от изчисляване на определена функция, на мястото на най-младата. Тази функция приема като аргумент долната половина на блока и ключовия информационен елемент ( х), е съдържателната част на шифъра и се нарича функция за криптиране . По различни причини се оказа изгодно да се раздели криптираният блок на две части с еднакъв размер: | н 1 |=|н 2 | – този факт е отразен от думата „балансирана” в името на архитектурата. Криптирането на небалансирани мрежи обаче също се използва от време на време, макар и не толкова често, колкото балансираните. В допълнение, съображенията за сила на шифъра изискват размерът на ключовия елемент да не бъде по-малък от размера на половината блок: в GOST и трите размера са равни на 32 бита .

Ако приложим горното към диаграмата на основната стъпка на алгоритъма GOST, ще стане очевидно, че блокове 1,2,3 на алгоритъма (виж Фиг. 1) определят изчисляването на неговата функция за криптиране, а блокове 4 и 5 задайте формирането на изходния блок на основната стъпка въз основа на съдържанието на входния блок и стойностите на функцията за криптиране. Повече подробности за архитектурите на съвременните блокови шифри с таен ключ могат да бъдат намерени в класически произведения или в адаптирана форма в моите произведения.

В предишния раздел вече сравнихме DES и GOST по отношение на издръжливостта, сега ще ги сравним по отношение на функционалното съдържание и лекотата на изпълнение. В циклите на криптиране на GOST основната стъпка се повтаря 32 пъти, за DES тази стойност е 16. Въпреки това, самата функция за криптиране на GOST е много по-проста от подобна DES функция, която съдържа много нередовни битови пермутации. Тези операции са изключително неефективни при съвременните неспециализирани процесори. GOST не съдържа такива операции, така че е много по-удобно за внедряване на софтуер.

Нито едно от приложенията на DES за платформата Intel x86, разгледани от автора, не достига дори половината от производителността на изпълнението на GOST, предложено в тази статия, въпреки двойно по-краткия цикъл. Всичко по-горе показва, че разработчиците на GOST са взели предвид както положителните, така и отрицателните аспекти на DES, а също така са оценили по-реалистично настоящите и бъдещите възможности на криптоанализа. Въпреки това, приемането на DES като основа при сравняване на производителността на внедряванията на шифри вече не е от значение. Новият американски стандарт за криптиране се справя много по-добре с ефективност - със същия размер на ключа като GOST (256 бита), AES работи с около 14% по-бързо - това е в сравнение с броя на „елементарните операции“. В допълнение, GOST практически не може да бъде успореден, докато AES има много повече възможности в това отношение. При някои архитектури това предимство на AES може да е по-малко, при други може да е по-голямо. И така, на процесор Intel Pentium достига 28%. Подробности можете да намерите в.

Изисквания за качество на ключовата информация и източници на ключове.

Не всички ключове и таблици за подмяна осигуряват максимална сила на шифъра. Всеки алгоритъм за криптиране има свои собствени критерии за оценка на ключовата информация. Така за алгоритъма DES е известно, че има т.нар. слаби ключове ", когато се използва, връзката между отворени и криптирани данни не се маскира достатъчно и шифърът се разбива относително лесно.

Ако изчерпателен отговор на въпроса за критериите за качество на GOST ключовете и таблиците за подмяна може да бъде получен навсякъде, това може да бъде само от разработчиците на алгоритъма. Съответните данни не бяха публикувани в публичната преса. Въпреки това, според установената процедура, за криптиране на класифицирана информация трябва да се използват ключови данни, получени от оторизирана организация. Косвено това може да показва наличието на методи за проверка на ключови данни за въшки. Ако наличието на слаби ключове в GOST е спорен въпрос, тогава наличието на слаби резервни единици е извън съмнение. Очевидно „тривиалната“ таблица за заместване, според която всяка стойност се заменя сама по себе си, е толкова слаба, че при нейното използване шифърът може да бъде просто разбит, независимо какъв е ключът.

Както беше отбелязано по-горе, критерии за оценка на ключова информация не са налични, но все пак могат да се направят някои общи съображения за тях.

Ключ

Ключът трябва да бъде масив от статистически независими битове, които с еднаква вероятност приемат стойностите 0 и 1. Не може да се изключи напълно, че някои специфични ключови стойности може да се окажат „слаби“, т.е. шифърът може да не осигури определеното ниво на сила, ако се използва. Въпреки това, вероятно, делът на такива стойности в общата маса на всички възможни ключове е пренебрежимо малък. Поне интензивното изследване на шифъра все още не е разкрило нито един такъв ключ за никоя от известните (т.е. предложени от FAPSI) таблици за заместване. Следователно ключовете, генерирани с помощта на някакъв сензор за наистина произволни числа, ще бъдат с високо качество с вероятност, която се различава от единица с пренебрежимо малка сума. Ако ключовете се генерират с помощта на генератор на псевдослучайни числа, тогава използваният генератор трябва да осигурява горните статистически характеристики и освен това да има висока криптографска сила - не по-малка от тази на самия GOST. С други думи, задачата за определяне на липсващите членове на последователността от елементи, генерирани от генератора, не трябва да бъде по-проста от задачата за разбиване на шифъра. Освен това могат да се използват различни статистически критерии за отхвърляне на ключове с лоши статистически характеристики. На практика обикновено са достатъчни два критерия: за проверка на равновероятното разпределение на ключовите битове между стойности 0 и 1 обикновено се използва тестът на Пиърсън (хи квадрат), а за проверка на независимостта на ключовите битове се използва тестът за изпълнение . Можете да прочетете за споменатите критерии в учебници или справочници по математическа статистика.

Най-добрият подход за генериране на ключове би бил използването на хардуерни сензори със среден клас, но това не винаги е приемливо по икономически причини. При генериране на малък масив от ключова информация, разумна алтернатива на използването на такъв сензор е широко разпространеният в практиката метод на „електронна рулетка“, когато следващата генерирана порция произволни битове зависи от момента, в който операторът натиска бутон определен клавиш на клавиатурата на компютъра. В тази схема източникът на произволни данни е компютърният потребител или по-точно времевите характеристики на неговата реакция. В този случай само няколко бита произволни данни могат да бъдат генерирани на натискане на клавиш, така че общата скорост на генериране на ключова информация е ниска - до няколко бита в секунда. Очевидно този подход не е подходящ за получаване на големи масиви от ключове.

В случай, че е необходимо да се генерира голям масив от ключова информация, използването на различни софтуерни сензори за псевдослучайни числа е възможно и широко разпространено. Тъй като такъв сензор изисква високи нива на криптографска сила, естествено е да използваме гама генератора на самия шифър като него - ние просто „нарязваме“ генерираната от шифъра гама на „парчета“ с необходимия размер, за GOST - 32 байтове. Разбира се, за този подход ще ни е необходим „главен ключ“, който можем да получим с помощта на описания по-горе метод на електронна рулетка и с негова помощ, използвайки шифър в режим на гама генератор, получаваме масив от ключова информация с размер Имаме нужда от. Така че тези два метода за генериране на ключове – „ръчно“ и „алгоритмично“ – работят в тандем, като се допълват взаимно. Схемите за генериране на ключове в „нискобюджетните“ системи за криптографска защита на информация почти винаги са изградени на този принцип.

Таблица за заместване

Таблицата за замяна е дългосрочен ключов елемент, тоест тя е валидна за много по-дълъг период от един ключ. Предполага се, че е общ за всички криптиращи възли в една и съща система за криптографска защита. Дори ако поверителността на таблицата за заместване е нарушена, силата на шифъра остава изключително висока и не намалява под допустимата граница. Следователно няма особена нужда таблицата да се пази в тайна и в повечето търговски приложения на GOST това се прави. От друга страна, заместващата таблица е критичен елемент за осигуряване на силата на целия шифър. Избирането на грешна таблица може да доведе до лесно разбиване на шифъра от известни техники за криптоанализ. Критериите за разработване на резервни единици са строго пазена тайна и FAPSI едва ли ще ги сподели с обществеността в близко обозримо бъдеще. В крайна сметка, определянето дали дадена таблица за заместване е добра или лоша изисква огромно количество работа - много хиляди човешки и машинни часове. Веднъж избрана и използвана, дадена таблица трябва да бъде заменена, ако и само ако шифърът, който я използва, се е оказал уязвим за един или друг тип криптоанализ. Следователно най-добрият избор за средния потребител на шифър би бил да вземе една от няколко таблици, които са станали публични. Например от стандарта за хеш функцията, известна още като функцията на „централното банкиране“; информация за тези таблици може да се намери в откритата преса и дори в Интернет, ако търсите достатъчно.

За тези, които не са свикнали да поемат по лесния път, по-долу е дадена обща схема за получаване на висококачествени таблици:

1. Използвайки една или друга техника, вие разработвате набор от осем заместващи единици с гарантирани характеристики на нелинейност. Има няколко такива техники, една от тях е използването на така наречените бент функции.
2. Вие проверявате изпълнението на най-простите „критерии за качество“ - например тези, публикувани за възли за подмяна на DES. Ето още няколко общи съображения в това отношение: Всеки заместващ възел може да бъде описан от четири логически функции от четири логически аргумента. Ако тези функции са записани в минимална форма(т.е. с минималната възможна дължина на израза) няма да бъде достатъчно сложен, такъв заместващ възел се отхвърля. Освен това отделните функции в рамките на цялата таблица за заместване трябва да са достатъчно различни една от друга. На този етап се елиминират много маси с очевидно ниско качество.
3. За шифър с таблици по ваш избор, изградете различни кръгли модели, съответстващи на различни видове криптоанализ, и измерете съответните характеристики на „профила“. Така че, за линеен криптоанализ, изградете линеен статистически аналог на кръга на криптиране и изчислете характеристиката на „профила“ - индикатор за нелинейност. Ако е недостатъчно, заместващата таблица се отхвърля.
4. Накрая, използвайки резултатите от предходния параграф, вие подлагате шифъра с избраната от вас таблица на интензивно изследване - опит за криптоанализ с всички известни методи. Този етап е най-трудният и отнема много време. Но ако е направен висококачествено, тогава с голяма степен на вероятност може да се твърди, че шифърът с избраните от вас таблици няма да бъде разбит от простосмъртните и е възможно да бъде твърде труден за интелигентността услуги.

Можете обаче да го направите много по-просто. Работата е там, че колкото повече кръгове има в един шифър, толкова по-малко влияние имат характеристиките на силата на един рунд върху силата на целия шифър. GOST има до 32 кръга - повече, отколкото в почти всички шифри с подобна архитектура. Следователно за повечето битови и търговски приложения е достатъчно да се получат заместващи възли като независими произволни пермутации на числа от 0 до 15. Това може да се приложи на практика, например чрез разбъркване на тесте от шестнадесет карти, на всяка от които е присвоена една от стойностите на посочения диапазон.

По отношение на таблицата за заместване трябва да се отбележи още един интересен факт. За обратимостта на циклите на криптиране "32-З" и "32-Р" не се изисква заместващите възли да бъдат пермутации на числа от 0 до 15. Всичко работи, дори ако заместващият възел има дублиращи се елементи и заместващият определен от такъв възел, е необратим, но в този случай силата на шифъра е намалена. Защо това е точно така не се обсъжда в тази статия, но не е трудно да се провери самият факт. За да направите това, достатъчно е първо да се опитате да шифровате и след това да дешифрирате блок от данни, като използвате такава „непълна“ заместваща таблица, чиито възли съдържат дублирани стойности.

Вариации по темата на GOST

Много често за използване в криптографска система за защита на данните се изисква алгоритъм с по-бърза скорост на внедряване от GOST и не се изисква такава висока криптографска сила. Типичен пример за такива задачи са различни видове електронни борсови системи за търговия, които управляват търговски сесии в реално време. Тук използваните алгоритми за криптиране са необходими, за да направят невъзможно дешифрирането на оперативните данни на системата по време на сесията (данни за подадени поръчки, сключени транзакции и др.), след изтичането й тези данни, като правило, вече не са безполезен за нападателите. С други думи, изисква се гарантирана издръжливост от само няколко часа - това е типичната продължителност на търговска сесия. Ясно е, че използването на пълноценен GOST в тази ситуация би било стрелба по врабчета с оръдие.

Какво да направите в този и подобни случаи, за да увеличите скоростта на криптиране? Отговорът е на повърхността - използвайте модификация на шифъра с по-малко основни стъпки (кръгове) в основните цикли. Колкото пъти намалим броя на кръговете на криптиране, производителността се увеличава със същата сума. Тази промяна може да се постигне по два начина - чрез намаляване на дължината на ключа и намаляване на броя на "циклите на преглед" на ключа. Спомнете си, че броят на основните стъпки в основните цикли на криптиране е н=n·m, Където н– брой 32-битови елементи в ключа, м– брой цикли на използване на ключови елементи, в стандарта н=8, м=4. Можете да намалите който и да е от тези числа, но най-простият вариант е да намалите дължината на ключа, без това да повлияе на начина, по който се използва.

Ясно е, че цената за ускоряване на работата ще бъде намаляване на силата на шифъра. Основната трудност е, че е доста трудно да се оцени повече или по-малко точно степента на това намаление. Очевидно единственият възможен начин да направите това е да проведете пълномащабно проучване на варианти на шифър с намалени цикли на криптографско преобразуване. Ясно е, че, първо, това изисква използването на класифицирана информация, която е собственост само на разработчиците на GOST, и, второ, това е много трудоемко. Затова сега ще се опитаме да дадем много, много груба оценка, базирана само на общи модели.

Що се отнася до устойчивостта на шифъра към кракване чрез „обширни“ методи, тоест към атака с „груба сила“, тук всичко е повече или по-малко ясно: ключ от 64 бита е някъде на ръба да бъде достъпен за този тип на атака, шифър с ключ от 96 бита или по-висок (не забравяйте, че ключът трябва да съдържа цяло число от 32-битови елементи) е доста устойчив на него. Наистина, преди няколко години предишният американски стандарт за криптиране, DES, беше многократно хакнат чрез груба сила - първо беше хакнат от компютърна мрежа, организирана на базата на глобалния интернет, а след това от специализирана мрежа, т.е. компютър, създаден специално за тази цел. Да приемем, че стандартната версия на GOST, когато се внедрява в софтуера на съвременните процесори, работи четири пъти по-бързо от DES. Тогава 8-кръговият „намален GOST“ ще работи 16 пъти по-бързо от DES. Нека приемем също, че във времето след хакването на DES изчислителната производителност се е увеличила четирикратно според закона на Мур. В резултат на това получаваме, че сега проверката на един 64-битов ключ за „намаления GOST“ с осем цикъла е 64 пъти по-бърза от проверката на един DES ключ наведнъж. По този начин предимството на тази версия на GOST пред DES по отношение на сложността на атака с груба сила се намалява от 2 64–56 = 2 8 = 256 на 256 / 64 = 4 пъти. Съгласете се, това е много илюзорна разлика, почти нищо.

Много по-трудно е да се оцени устойчивостта на отслабените модификации на GOST към „интензивните“ методи на криптоанализ. Но и тук може да се проследи една обща закономерност. Факт е, че характеристиките на „профила“ на много от най-мощните видове криптоанализ днес зависят експоненциално от броя на кръговете на криптиране. Така че за линеен криптоанализ (LCA) това ще бъде характеристика на линейност Л :

Където ° С и са константи, R е броят кръгове. Подобна връзка съществува за диференциалния криптоанализ. В техния „физически смисъл“ всички характеристики от този вид са вероятности. Обикновено количеството първоначални данни, необходими за криптоанализа, и тяхната сложност са обратно пропорционални на тези характеристики. От това следва, че тези показатели за интензивност на труда нарастват експоненциално с броя на основните стъпки на криптиране. Следователно, когато броят на кръговете се намали няколко пъти, сложността на най-известните видове анализи ще се промени като, много приблизително и грубо, коренът на тази степен от първоначалното количество. Това е много голям спад в издръжливостта.

От друга страна, GOST е проектиран с голяма граница на безопасност и днес е устойчив на всички известни видове криптоанализ, включително диференциален и линеен. По отношение на LCA това означава, че за успешното му внедряване са необходими повече двойки „отворен блок - криптиран блок“, отколкото „съществува в природата“, тоест повече от 2 64 . Като се вземе предвид горното, това означава, че за успешен LCA на 16-кръгов GOST ще са необходими поне блокове или 2 35 байта или 32 GB данни, а за 8-кръг - поне блокове или 2 19 байта или 0,5 MB.

Изводите от всичко по-горе са дадени в следващата таблица, която обобщава характеристиките на намалените версии на GOST.

Брой кръгове	Размер на ключа, битове	Индекс на ефективност	Вероятни характеристики на шифъра (много груба оценка)
24	192	1,33	Устойчив на повечето известни видове CA или на ръба на устойчивостта. Практическата реализация на КА е невъзможна поради високите изисквания към изходните данни и трудоемкостта.
16	128	2	Теоретично той е нестабилен за някои видове криптоанализ, но практическото им прилагане в повечето случаи е трудно поради високите изисквания към изходните данни и интензивността на труда.
12	95	2,67	Той не е устойчив на някои известни видове криптоанализ, но е подходящ за осигуряване на секретност на малки количества данни (до десетки или стотици килобайти) за кратък период от време.
8	64	4	Не е устойчив на някои известни видове криптоанализ, но е подходящ за осигуряване на секретност на малки количества данни (до десетки килобайта) за кратък период от време.

Последните две опции, с 12 и 8 кръга, са в състояние да осигурят много, много ограничена времева защита. Използването им е оправдано само при задачи, при които се изисква само краткотрайна секретност на защитените данни от порядъка на няколко часа. Възможна област на приложение на тези слаби варианти на шифър е да блокира UDP трафик от електронни системи за борсова търговия. В този случай всеки пакет данни (дейтаграма, средното „D“ от съкращението UDP) се криптира с помощта на отделен 64-битов ключ, а самият ключ се криптира с помощта на сесиен ключ (ключ, чийто обхват е една комуникационна сесия между два компютъра) и се предава заедно с данните.

Преди да завърша с намалените версии на GOST, ще кажа, че всички горни съображения са силно спекулативни. Стандартът осигурява издръжливост само за един, 32-заряден вариант. И никой не може да ви даде гаранции, че устойчивостта на кракване на намалените версии на шифъра ще се промени по начина, посочен по-горе. Ако все пак решите да ги използвате в своите разработки, не забравяйте, че сте стъпили на много нестабилна почва, която всеки момент може да се изплъзне изпод краката ви. Тъй като скоростта на криптиране е критичен проблем за вас, може би трябва да обмислите използването на по-бърз шифър или по-мощен компютър? Друго съображение, поради което си струва да се направи това, е, че отслабените версии на GOST ще бъдат най-чувствителни към качеството на използваните резервни единици.

Разглежданият въпрос има и обратна страна. Ами ако скоростта на криптиране не е критична, но изискванията за сила са много строги? Устойчивостта на GOST може да се повиши по два начина - нека ги наречем "обширен" и "интензивен". Първият от тях не е нищо повече от просто увеличаване на броя на кръговете за криптиране. Не ми е съвсем ясно защо това всъщност може да е необходимо, тъй като вътрешният стандарт вече осигурява необходимата издръжливост и без това. Ако обаче страдате от параноя повече от необходимото ниво (и всички „защитници на информация“ са просто длъжни да страдат от това, това е условие за професионална годност, единственият въпрос е тежестта на случая :), това ще помогне успокояваш се донякъде. Ако не сте сигурни за този шифър на KGB или таблицата за заместване, която използвате, просто удвоете, учетворете и т.н. брой рундове – изберете кратността въз основа на тежестта на вашия случай. Този подход ви позволява наистина да увеличите силата на шифъра - ако по-рано криптоанализът беше просто невъзможен, сега е невъзможен на квадрат!

По-сложен и интересен въпрос е дали е възможно да се увеличи силата на шифъра, без да се променя броят и структурата на основните стъпки на криптиране. Изненадващо отговорът на това е положителен, въпреки че отново стъпваме върху разклатената почва на спекулациите. Факт е, че в GOST, на основната стъпка на преобразуване, се предполага, че се заменят 4 с 4 бита, но на практика (ще говорим за това по-късно) всички софтуерни реализации извършват замяната байт по байт, т.е. 8 на 8 бита - това се прави от съображения за ефективност. Ако незабавно проектираме такъв заместител като 8-битов, значително ще подобрим производителността на един кръг. Първо, характеристиката на „дифузия“ или индикаторът „лавин“ ще се увеличи - един бит от изходните данни и/или ключ ще повлияе на по-голям брой битове от резултата. Второ, за по-големи заместващи възли могат да се получат по-ниски диференциални и линейни характеристики, като по този начин се намалява податливостта на шифъра към подобни видове криптоанализ. Това е особено вярно за намалените GOST цикли, а за 8 и 12-кръгли варианти такава стъпка е просто необходима. Това донякъде ще компенсира загубата на издръжливост в тях от намаляването на броя на патроните. Това, което затруднява използването на тази техника, е, че ще трябва сами да проектирате такива „уголемени“ резервни единици. А също и фактът, че по-големите единици обикновено са много по-трудни за конструиране от по-малките.

Нестандартно използване на стандарта.

Разбира се, основната цел на криптографските алгоритми GOST е криптирането и защитата на данните. Но те могат да намерят и други приложения, свързани, естествено, с информационната сигурност. Нека поговорим накратко за тях:

1. За криптиране в гама режим GOST предвижда разработването на криптографска гама - последователност от битове с добри статистически характеристики и висока криптографска сила. След това тази гама се използва за модифициране на отворени данни, което води до криптирани данни. Това обаче не е единственото възможно приложение на криптографската гама. Факт е, че алгоритъмът за неговото генериране е генератор на псевдослучайни числа (PRNG) с отлични характеристики. Разбира се, използването на такъв PRNG, където се изискват само статистическите характеристики на генерираната последователност, но не е необходима криптографска сила, не е много разумно - за тези случаи има много по-ефективни генератори. Но за различни приложения, свързани с информационната сигурност, такъв източник ще бъде много полезен:

• Както беше отбелязано по-горе, гама може да се използва като „суров материал“ за генериране на ключове. За да направите това, просто трябва да получите гама сегмент с необходимата дължина - 32 байта. По този начин могат да се правят ключове според нуждите и няма да е необходимо да се съхраняват - ако такъв ключ отново е необходим, ще бъде доста лесно да се генерира отново. Просто трябва да запомните на какъв ключ е бил първоначално генериран, какво съобщение за синхронизация е използвано и с кой байт от генерираната гама е започнал ключът. Цялата информация с изключение на използвания ключ е некласифицирана. Този подход ще улесни управлението на доста сложна и разклонена ключова система, като се използва само един „главен ключ“.
• Подобно на предишния, гамата може да се използва като първоначална „суровина“ за генериране на пароли. Тук може да възникне въпросът защо изобщо е необходимо да ги генерираме, не е ли по-лесно просто да ги измислим според нуждите? Неуспехът на този подход беше ясно демонстриран от поредица от инциденти в компютърните мрежи, най-големият от които беше ежедневната парализа на Интернет през ноември 1988 г., причинена от червея Morris. Един от начините, по които злонамерена програма прониква в компютър, е чрез отгатване на пароли: програмата се опитва да влезе в системата, като последователно опитва пароли от своя вътрешен списък от няколкостотин и в значителна част от случаите успява. Човешкото въображение за измисляне на пароли се оказа много бедно. Ето защо в онези организации, където на сигурността се обръща нужното внимание, паролите се генерират и разпространяват на потребителите от системния администратор по сигурността. Генерирането на пароли е малко по-сложно от генерирането на ключове, тъй като в този случай „суровата“ двоична гама трябва да бъде преобразувана в символна форма, а не просто „нарязана“ на парчета. Освен това може да се наложи отделните стойности да бъдат отхвърлени, за да се гарантира, че всички буквени знаци са еднакво вероятно да се появят в паролата.
• Друг начин за използване на криптографската гама е гарантираното изтриване на данни на магнитни носители. Факт е, че дори когато информацията се презаписва върху магнитен носител, остават следи от предишни данни, които могат да бъдат възстановени чрез подходящо изследване. За да се унищожат тези следи, такова презаписване трябва да се извършва многократно. Оказа се, че ще е необходимо да се презаписва информация върху носителя по-малко пъти, ако подобна процедура използва случайни или псевдослучайни данни, които ще останат неизвестни за експертите, опитващи се да възстановят изтритата информация. Гама шифърът ще бъде полезен тук.

2. Не само криптографската гама, но и самата криптографска трансформация може да се използва за нужди, които не са пряко свързани с криптирането:

• Знаем, че една от тези опции за използване на GOST е разработването на симулирани вложки за масиви от данни. Въпреки това, на базата на всеки блоков шифър, включително GOST, е доста лесно да се изгради схема за изчисляване на еднопосочна хеш функция, наричана още в литературата MDC, което в различни източници означава промяна на кода за откриване / манипулация (Ммодификация/ Манипулация детекция ° Сода) или дайджест на съобщението (Месе д igest ° Сода). Първото декодиране се появи в литературата много по-рано, второто, по-кратко, мисля, беше измислено от онези, които не успяха да си спомнят първото :), - беше шега. MDC може да се използва директно в системи за защита от имитация като аналог на вмъкване на имитация, което обаче не зависи от секретния ключ. В допълнение, MDC се използва широко в схемите за електронен цифров подпис (EDS), тъй като повечето от тези схеми са проектирани по такъв начин, че да е удобно да се подпише блок от данни с фиксиран размер. Както знаете, на базата на обсъждания стандарт GOST 28147-89 е изграден стандартът на Руската федерация за изчисляване на еднопосочната хеш функция GOST R34.11-94.
• По-малко известно е, че на базата на всеки блоков шифър, включително GOST, може да се изгради напълно функционална схема за цифров подпис, със секретен ключ за подпис и отворена комбинация за проверка. Поради редица причини тази схема не е получила широко практическо разпространение, но в някои случаи все още може да се счита за много привлекателна алтернатива на „математическите“ схеми за цифров подпис, които в момента са доминиращи в света.

Литература

Системи за обработка на информация. Криптографска защита. Алгоритъм за криптографска трансформация GOST 28147-89. състояние Ком. СССР според стандартите, М., 1989. ftp://ftp.wtc-ural.ru/pub/ru.crypt/GOST-28147
Шанън Клод. Математическа теория на тайните системи. В сборника „Трудове по теория на информацията и кибернетика”, М., IL, 1963, стр. 333-369. http://www.enlight.ru/crypto/articles/shannon/shann__i.htm
Обявяване на одобрение на Федерален стандарт за обработка на информация (FIPS) 197, Advanced Encryption Standard (AES), Федерален регистър том. 66, бр. 235 / четвъртък, 6 декември 2001 г. / Известия, стр. 63369–63371. http://csrc.nist.gov/encryption/aes/
Файстел Хорст. Криптография и компютърна сигурност. Превод на А. Винокуров по изданието Horst Feistel. Криптография и компютърна поверителност, Scientific American, май 1973 г., том. 228, бр. 5, стр. 15-23. http://www.enlight.ru/crypto/articles/feistel/feist_i.htm
Шнайер Брус. Приложна криптография. 2-ро изд. Протоколи, алгоритми и изходни текстове на езика C., М., “Триумф”, 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
Винокуров Андрей, Применко Едуард. Текст на доклада „За софтуерното внедряване на стандарти за криптиране в Руската федерация и САЩ“, конференция по информатизация, Москва, МИФИ, 28-29 януари 2001 г. Публикувано в сборник от конференции.
Информационни технологии. Криптографска защита на информацията. Хеш функция GOST R34.11-94, Държавен стандарт на Руската федерация, М., 1994 г.

Алгоритъмът, определен от GOST 28147-89, има дължина на ключа за криптиране от 256 бита. Той криптира информацията в блокове от 64 бита (такива алгоритми се наричат ​​блокови алгоритми), които след това се разделят на два подблока от 32 бита (N1 и N2) (Фигура 1). Подблок N1 се обработва по определен начин, след което неговата стойност се добавя със стойността на подблок N2 (добавянето се извършва по модул 2, т.е. прилага се логическата операция XOR - „изключително или“), след което подблоковете се разменят . Тази трансформация се извършва определен брой пъти („ръндове“): 16 или 32, в зависимост от режима на работа на алгоритъма. Във всеки кръг се извършват две операции.

Фигура 1. Схема на алгоритъма GOST 28147-89.

Първият е ключът. Съдържанието на подблок N1 се добавя по модул 2 с 32-битовата част на ключа Kx. Пълният ключ за криптиране е представен като конкатенация от 32-битови подключове: K0, K1, K2, K3, K4, K5, K6, K7. По време на процеса на криптиране се използва един от тези подключове в зависимост от кръглото число и режима на работа на алгоритъма.

Втората операция е подмяна на маса. След ключа подблок N1 се разделя на 8 части от 4 бита, стойността на всяка от които се заменя в съответствие с таблицата за заместване за тази част от подблока. След това подблокът се завърта побитово наляво с 11 бита.

Заместванията на таблици (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 a 4, 1 a 11, 2 a 2 ...).

Алгоритъмът, определен от GOST 28147-89, осигурява четири режима на работа: проста замяна, гама, гама с обратна връзка и генериране на имитационни прикачени файлове. Те използват същата трансформация на криптиране, описана по-горе, но тъй като целта на режимите е различна, тази трансформация се извършва по различен начин във всеки от тях.

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

K0, K1, K2, K3, K4, K5, K6, K7, K0, K1 и т.н. - в кръгове от 1 до 24;

K7, K6, K5, K4, K3, K2, K1, K0 - в кръгове от 25 до 32.

Дешифрирането в този режим се извършва по абсолютно същия начин, но с малко по-различна последователност от използване на подключове:

K0, K1, K2, K3, K4, K5, K6, K7 - в кръгове от 1 до 8;

K7, K6, K5, K4, K3, K2, K1, K0, K7, K6 и т.н. - в кръгове от 9 до 32.

Всички блокове са криптирани независимо един от друг, т.е. резултатът от криптирането на всеки блок зависи само от неговото съдържание (съответния блок от оригиналния текст). Ако има няколко идентични блока от оригинален (обикновен) текст, съответните блокове от шифрован текст също ще бъдат идентични, което предоставя допълнителна полезна информация за криптоаналитик, който се опитва да разбие шифъра. Следователно този режим се използва главно за криптиране на самите ключове за криптиране (много често се прилагат многоключови схеми, при които по редица причини ключовете се криптират един върху друг). Други два режима на работа са предназначени за криптиране на самата информация - гама и гама с обратна връзка.

В гама режим всеки блок с обикновен текст се добавя бит по бит модул 2 към 64-битов шифър гама блок. Шифрова гама е специална последователност, която се получава в резултат на определени операции с регистри N1 и N2.

• 1. Първоначалното им попълване се записва в регистрите N1 и N2 - 64-битова стойност, наречена синхронизиращо съобщение.
• 2. Съдържанието на регистрите N1 и N2 (в този случай съобщения за синхронизиране) се криптира в режим на проста замяна.
• 3. Съдържанието на регистър N1 се сумира по модул (232 - 1) с константата C1 = 224 + 216 + 28 + 24 и резултатът от събирането се записва в регистър N1.
• 4. Съдържанието на регистър N2 се събира по модул 232 с константата C2 = 224 + 216 + 28 + 1 и резултатът от събирането се записва в регистър N2.
• 5. Съдържанието на регистрите N1 и N2 се извежда като 64-битов гама блок на шифъра (в този случай N1 и N2 образуват първия гама блок).

Ако е необходим следващ гама блок (т.е. криптирането или декриптирането трябва да продължи), се връща към стъпка 2.

За декриптиране гамата се генерира по подобен начин и след това шифрованият текст и гама битовете отново се подлагат на XOR. Тъй като тази операция е обратима, при правилно развита скала се получава оригиналният текст (табл. 1).

Маса 1.Криптиране и декриптиране в гама режим

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

В повечето реализации на алгоритъма GOST 28147-89 съобщението за синхронизиране не е тайно, но има системи, при които съобщението за синхронизиране е същият таен елемент като ключа за шифроване. За такива системи ефективната дължина на ключа на алгоритъма (256 бита) се увеличава с още 64 бита от секретното съобщение за синхронизация, което също може да се счита за ключов елемент.

В гама режим със затворен цикъл, за запълване на регистри N1 и N2, като се започне от 2-ри блок, не се използва предишният гама блок, а резултатът от криптирането на предишния блок с обикновен текст (Фигура 2). Първият блок в този режим се генерира напълно подобно на предишния.

Фигура 2. Генериране на шифрова гама в гама-режим със затворен контур.

При разглеждането на начина на генериране на имитационни префикси е необходимо да се дефинира понятието субект на генериране. Префиксът е криптографска контролна сума, изчислена с помощта на ключ за криптиране и предназначена да провери целостта на съобщенията. При генериране на префикс за имитация се извършват следните операции: първият 64-битов блок от информационния масив, за който се изчислява префиксът за имитация, се записва в регистрите N1 и N2 и се криптира в режим на намалена проста замяна ( изпълняват се първите 16 кръга от 32). Полученият резултат се сумира по модул 2 със следващия блок информация и резултатът се съхранява в N1 и N2.

Цикълът се повтаря до последния блок информация. Полученото 64-битово съдържание на регистрите N1 и N2 или част от тях в резултат на тези трансформации се нарича имитационен префикс. Размерът на имитационния префикс се избира въз основа на необходимата надеждност на съобщенията: с дължината на имитационния префикс r бита, вероятността промяната в съобщението да остане незабелязана е равна на 2-r. Най-често a Използва се 32-битов имитационен префикс, т.е. половината от съдържанието на регистрите. Това е достатъчно, тъй като, както всяка контролна сума, имитационният прикачен файл е предназначен предимно за защита срещу случайно изкривяване на информацията. За защита срещу умишлена промяна на данните се използват други криптографски методи - предимно електронен цифров подпис.

При обмен на информация имитационният префикс служи като вид допълнително средство за контрол. Изчислява се за обикновен текст, когато всяка информация е криптирана и се изпраща заедно с шифрования текст. След декриптирането се изчислява нова стойност на префикса за имитация и се сравнява с изпратената. Ако стойностите не съвпадат, това означава, че шифрованият текст е бил повреден по време на предаване или са използвани неправилни ключове по време на дешифрирането. Префиксът за имитация е особено полезен за проверка на правилното декриптиране на ключова информация при използване на схеми с много ключове.

Алгоритъмът GOST 28147-89 се счита за много силен алгоритъм - в момента не са предложени по-ефективни методи за неговото разкриване от метода на „груба сила“, споменат по-горе. Високата му сигурност се постига преди всичко благодарение на голямата дължина на ключа – 256 бита. Когато използвате тайно синхронизиращо съобщение, ефективната дължина на ключа се увеличава до 320 бита, а шифроването на заместващата таблица добавя допълнителни битове. В допълнение, криптографската сила зависи от броя на кръговете на трансформация, които съгласно GOST 28147-89 трябва да бъдат 32 (пълният ефект на дисперсия на входните данни се постига след 8 кръга).

Предимствата на GOST 28147-89 са наличието на защита срещу налагане на неверни данни (генериране на имитации) и един и същ цикъл на криптиране във всичките четири алгоритъма на GOST.

„Докато си жив, не умирай, гледай този свят.
Мнозина тук имат мъртва душа – мъртви са вътрешно.
Но те вървят и се смеят, без да знаят, че ги няма,
Не бързай със своя смъртен час“, каза ми тя.

Ария, "Там горе"

1. Въведение

1. Въведение в блоковите шифри

2.1 Фейстел мрежи.
2.2 Блоков шифър GOST 28147-89

1. Теоретичен минимум

3.1 Ключова информация
3.2 Основна стъпка на криптовалута

3.3 Основни цикли:“ 32-Z” , “ 32-P” .

1. Практикувайте

4.1 Изпълнение на основната стъпка на крипто конвертиране
4.2 Увеличаване на скоростта на алгоритъма
5.
6. Списък на използваната литература
7. Благодарности

Въведение.

Този документ е моят опит да опиша метод за проста замяна на алгоритъма за криптиране GOST 28147-89 с най-простия, но въпреки това технически компетентен език. Читателят ще каже мнението си за това колко добре съм успял, след като прочете първите шест точки.

За да бъде работата ми по-полезна, препоръчвам да се въоръжите с произведенията на авторите, посочени в списъка на използваната литература. Препоръчва се и калкулатор, за да има функция за изчисляване на операцията XOR, защото четенето на статията предполага, че читателят възнамерява да проучи този алгоритъм за криптиране. Въпреки че е подходяща и като справочно ръководство, написах тази статия специално като обучителна.

Въведение в блоковите шифри.

Преди да започнем да разглеждаме алгоритъма, трябва да се запознаем с историята на създаването на този вид шифри. Алгоритъмът принадлежи към категорията на блоковите шифри, в чиято архитектура информацията е разделена на краен брой блокове, окончателният естествено може да не е пълен. Процесът на криптиране се извършва точно върху пълни блокове, които формират шифрограмата. Последният блок, ако е непълен, се допълва с нещо (ще говоря за нюансите на неговото завършване по-долу) и се криптира по същия начин като пълните блокове. Под шифрограма имам предвид резултата от функцията за криптиране, действаща върху определено количество данни, които потребителят е изпратил за криптиране. С други думи, шифрограмата е крайният резултат от криптирането.

Историята на развитието на блоковите шифри е свързана с началото на 70-те години, когато компанията IBM, осъзнавайки необходимостта от защита на информацията при предаване на данни по компютърни комуникационни канали, започва да прилага своя собствена научноизследователска програма, посветена на защитата на информацията в електронните мрежи, включително криптография.

Група от изследователи и разработчици от IBM, които започнаха да изследват системи за криптиране със симетрична ключова схема, бяха ръководени от Dr. Хорст Файстел.

2.1 Мрежи на Фейстел

Архитектурата на новия метод за криптиране, предложен от Feistel в класическата литература, се нарича „Feistel Architecture“, но в момента в руската и чуждестранната литература се използва по-утвърден термин - „Feistel network“ или Feistel`s NetWork. Впоследствие шифърът "Луцифер" е изграден с помощта на тази архитектура - която по-късно е публикувана и предизвиква нова вълна от интерес към криптографията като цяло.

Идеята на мрежовата архитектура на Feistel е следната: входният информационен поток е разделен на блокове с размер n бита, където n е четно число. Всеки блок се разделя на две части - L и R, след което тези части се подават в итеративен блоков шифър, в който резултатът от j-тия етап се определя от резултата от предходния етап j-1! Това може да се илюстрира с пример:

Ориз. 1

Където функция A е основното действие на блоков шифър. Това може да бъде просто действие, като например операцията XOR, или може да има по-сложна форма и да бъде последователност от няколко прости действия - добавяне по модул, ляво изместване, замяна на елемент и т.н., заедно тези прости действия образуват така наречената основна стъпка на крипто преобразуване.

Трябва да се отбележи, че ключовите елементи на работата на функцията са предоставянето на ключови елементи и операцията XOR и колко добре са обмислени тези операции показва криптографската сила на шифъра като цяло.

За да бъде напълно ясна идеята за мрежите на Feistel, нека разгледаме най-простия случай, изобразен в ориз. 1, където във функция A – ще се появят операциите “mod 2” (“xor”), но това най-простиятслучай, в по-сериозна ситуация, например укриване на информация от национално значение, функция А може да бъде по-сложна (доколкото видях, функция А наистина може да бъде много сложна):

Първоначални данни:

L=1110b, R=0101, K=1111b

Вземете кода за криптиране

1. (R + K) mod 2 4 = Smod, Smod = 0100b
2. (Smod + L) mod 2 = Sxor, Sxor = 1010b
3. L=R, R=Sxor

L=0101b, R=1010b

Нека обясним нашите действия:

1. Тази операция е добавяне на мод 2 4. На практика подобна операция се свежда до просто събиране, при което трябва да съберем две числа и да игнорираме пренасянето в 5-та цифра. Тъй като, ако поставим експонента над цифрите на двоичното представяне на число, ще има степен четири над петата цифра, нека да разгледаме фигурата по-долу, която показва действията на нашата операция:

Ориз. 2

Тук посочих със стрелка експонентите, както можете да видите, резултатът трябваше да бъде 10100, но тъй като операцията mod 2 4 игнорира пренасянето, получаваме 0100.

1. Тази операция се нарича mod 2 в литературата и се изпълнява на асемблер чрез командата XOR. Но по-правилното му име е mod 2 1. Без тази уникална операция едва ли е възможно да се изгради бърз, лесен за изпълнение алгоритъм за криптиране и в същото време той да бъде доста устойчив на криптиране. Уникалността на тази операция се състои в това, че тя е противоположна на себе си! Например, ако числото A е XORED с числото B, резултатът е B. В бъдеще е достатъчно да XOR числата B и C едно с друго, за да получите предишната стойност на A!

В тази операция получихме 1010 с числата 1110 и 0100, за да върнем 1110 обратно, достатъчно е да сложим XOR числата 0100 и 1010 едно с друго! Можете да прочетете повече за тази операция в статията, прикачена към уебсайта. www.wasm.ru, « Основно ръководство заАлгоритми за откриване на CRC_error» авторът, който Рос Н. Уилямс. В тази работа има точка - „ 5. Двоична аритметика без пренасяне" Именно в тази статия е описана операцията. xor!Възкликвам, защото в тази статия тази операция е така описана, че читателят не само разбира как работи тази операция, той дори я започва виж, чуй и усети!

1. Това действие е необходимо, така че при дешифриране на шифрограмата да могат да се получат оригиналните стойности.

2.2 Блоков шифър GOST 28147-89

Алгоритъмът за криптиране GOST 28147-89 принадлежи към категорията на блоковите шифри, работещи в съответствие с архитектурата на балансирани мрежи на Feistel, където две части от избрания блок информация са с еднакъв размер. Алгоритъмът е разработен в недрата на осми отдел на КГБ, сега трансформиран във FAPSI, и е създаден като стандарт за криптиране на Руската федерация през 1989 г. по време на СССР.

За да работи този алгоритъм, е необходимо информацията да се раздели на блокове с размер 64 бита. Генерирайте или въведете в системата за криптиране следната ключова информация: ключ и таблица за заместване. Изборът на ключ и заместваща таблица при криптиране трябва да се вземе много сериозно, т.к Това е основата за сигурността на вашата информация. За информация относно изискванията, наложени на ключа и таблицата за подмяна, вижте параграфа „Изисквания за ключова информация“.

Когато разглеждаме метода, няма да се фокусираме върху това, защото тази статия, както казах по-горе, е написана с цел да научи читателя как да криптира данни, като използва метода за просто заместване на даден алгоритъм за криптиране, но определено ще засегнем този въпрос в края на статията.

Теоретичен минимум.

3.1 Ключова информация

Както казах по-горе, следните участват активно в криптирането на данни:

3.1.1. Ключът е поредица от осем елемента, всеки с размер 32 бита. По-нататък ще го обозначаваме със символа K, а елементите, от които се състои са k1, k2, k3, k4, k5, k6, k7, k8.

3.1.2 Таблица за заместване – матрица от осем реда и шестнадесет колони, наричана по-нататък Hij. Всеки елемент в пресечната точка на ред i и колона j заема 4 бита.

Основното действие в процеса на криптиране е основната стъпка на крипто конвертирането. Това не е нищо повече от действие за криптиране на данни с помощта на определен алгоритъм, само че разработчиците въведоха много тромаво име :).

Преди да започне криптирането, блокът се разделя на две части L и R, по 32 бита всяка. Те избират ключов елемент и едва след това подават тези две части на блока, ключовия елемент и заместващата таблица във функцията на основната стъпка. Резултатът от основната стъпка е една итерация на основния цикъл, която ще бъде обсъдена в следващия параграф. Основната стъпка се състои от следното:

1. Допълнителната част на блока R се сумира с ключовия елемент K mod 2 32. Описах подобна операция по-горе, тук същото нещо, само показателят не е „4“, а „32“ - резултатът от тази операция ще бъде допълнително обозначен със Smod.
2. Разделяме предварително получения резултат Smod на четирибитови елементи s7, s6, s5, s4, s3, s2, s1, s0 и го подаваме във функцията за заместване. Заместването става по следния начин: изберете елемента Smod - s i , започнете отначало с най-ниския елемент и го заменете със стойността от таблицата за заместване за i - реда и колоната, посочени от стойността на елемента s i . Отиваме на s i +1 елемент и продължаваме по същия начин и продължаваме, докато заменим стойността на последния елемент Smod - резултатът от тази операция ще бъде означен като Ssimple.
3. При тази операция стойността на Ssimple се измества циклично наляво с 11 бита и получаваме Srol.
4. Избираме втората част на блок L и добавяме mod 2 със Srol, като резултат имаме Sxor.
5. На този етап частта L на блока става равна на стойността на частта R, а частта R от своя страна се инициализира от резултата на Sxor и това е краят на основната стъпкова функция!

3.3 Основни цикли: “32-Z”, “32-R”.

За да се шифрова информацията, тя трябва да бъде разделена на блокове с размер 64 бита; естествено, последният блок може да бъде по-малък от 64 бита. Този факт е ахилесовата пета на този метод на „проста подмяна“. Тъй като добавянето му към 64 бита е много важна задача за увеличаване на криптографската сила на шифърграмата, това чувствително място, ако присъства в масива от информация, може и да не е (например файл с размер 512 байта !), трябва да се третират с голяма отговорност!

След като сте разделили информацията на блокове, трябва да разделите ключа на елементи:

K = k1,k2,k3,k4,k5,k6,k7,k8

Самото криптиране се състои в използването на така наречените основни цикли. Които от своя страна включват n-тия брой основни стъпки за преобразуване на крипто.

Основните цикли са, как да го кажа, маркирани: n – m. Където n е броят на основните стъпки на крипто конвертиране в основния цикъл, а m е „типът“ на основния цикъл, т.е. За какво говорим, "Z" криптиране или "R" криптиране на данни.

Основният цикъл на криптиране 32-3 се състои от 32 основни стъпки на крипто-трансформация. Функцията, която изпълнява стъпковите действия, се доставя с блок N и ключов елемент K, където първата стъпка се случва с k1, втората над получения резултат с елемент k2 и т.н. по следната схема:

k1,k2,k3,k4,k5,k6,k7,k8,k1,k2,k3,k4,k5,k6,k7,k8,k1,k2,k3,k4,k5,k6,k7,k8k8,k7, k6,k5,k4,k3,k2,k1

Процесът на дешифриране за 32-P се извършва по подобен начин, но ключовите елементи се доставят в обратен ред:

k1,k2,k3,k4,k5,k6,k7,k8,k8,k7,k6,k5,k4,k3,k2,k1,k8,k7,k6,k5,k4,k3,k2,k1,k8, k7,k6,k5,k4,k3,k2,k1

Практикувайте.

След като се запознахме с теорията как да криптираме информация, дойде време да видим как криптирането се случва на практика.

Първоначални данни:

Нека вземем блока информация N = 0102030405060708h, тук частите L и R са равни:

L = 01020304h, R =05060708h, вземете ключа:

К = ' като28 zw37 q839 7342ui23 8e2t wqm2 ewp1’ (това са ASCII кодове, за да видите шестнадесетичното представяне, можете да отворите този файл в режим на преглед в Total Commander, като натиснете „ F3"и след това ключът" 3 "). В този ключ стойностите на елемента ще бъдат:

k1 = 'as28', k2 = 'zw37', k3 = 'q839', k4 = '7342'

k5 = 'ui23', k6 = '8e2t', k7 = 'wqm2', k8 = 'ewp1'

Нека вземем и следната таблица за заместване:

Ориз. 3

Тук редовете са номерирани от 0 до 7, колоните от 0 до F.

Внимание:Цялата информация, включително ключа с таблицата за заместване, се приема като пример за разглеждане на алгоритъма!

С помощта на „Входни данни“ е необходимо да се получи резултатът от основната стъпка на криптопреобразуване.

1. Избираме частта R = 05060708h и ключовия елемент k1 = ‘as28’, в шестнадесетична форма ключовият елемент ще изглежда така: 61733238h. Сега изпълняваме операцията за сумиране mod 2 32:

Ориз. 4

Както можете да видите на фигурата, нямахме прехвърляне към 33 бита, маркирани в червено и с показател „ 32 " И ако имахме други стойности за R и ключовия елемент, това можеше да се случи и тогава щяхме да го игнорираме и в бъдеще щяхме да използваме само битовете, маркирани в жълто.

Изпълнявам тази операция с помощта на командата асемблер добавете:

; eax = R, ebx = 'as28'

Резултатът от тази операция е Smod = 66793940h

1. Сега това е най-сложната операция, но ако се вгледате по-отблизо, вече не е толкова страшно, колкото изглежда в началото. Нека си представим Smod в следната форма:

ФИГУРАТА НЕ Е ЗАПАЗЕНА

Ориз. 5

Опитах се да визуализирам Smod елементите на фигурата, но все пак ще обясня:

s0 = 0, s1 = 4, s2 = 9 и т.н.

Сега, започвайки от най-ниския елемент s0, правим замяната. Запомняне на точката " 3.2 Основна стъпка на криптовалута» i – ред, s i – колона, потърсете стойността в нулевия ред и нулевата колона:

Фиг.6

Така че текущата стойност на Smod не е 6679394 0 ч, 6679394 5 ч.

Нека започнем да заместваме s1, т.е. четири. Използване на първия ред и четвъртата колона (s1= 4!). Да погледнем снимката:

Ориз. 7

Сега стойността е Smod, а не 667939 4 5ч, 667939 2 5ч. Предполагам, че алгоритъмът за заместване вече е ясен за читателя и мога да кажа, че след това крайният резултат на Ssimple ще има следната стойност - 11e10325h.

Ще говоря за това как това може да се реализира най-лесно под формата на команди на асемблер по-късно в следващия параграф, след като говоря за разширената таблица.

1. Трябва да изместим получената Ssimple стойност с 11 бита наляво.

Ориз. 8

Както можете да видите, това действие е доста просто и се изпълнява с една команда на асемблерния език - роли резултатът от тази операция Srol е 0819288Fh.

1. Сега всичко, което остава, е да XOR частта L от нашия информационен блок със стойност Srol. Взимам калкулатор от w2k sp4 и получавам Sxor = 091b2b8bh.
2. Това действие е окончателно и ние просто присвояваме, почистваме R, стойността на част L и инициализираме част L със стойността на Sxor.

Краен резултат:

L = 091b2b8bh, R = 01020304h

4.2 Увеличете скоростта на алгоритъма

Сега нека поговорим за оптимизиране на алгоритъма за скорост. Когато изпълнявате всеки проект, трябва да имате предвид, че програма, която работи с регистри по-често, отколкото с памет, работи най-бързо и тук тази преценка също е много важна, т.к. над един блок информация има до 32 криптиращи действия!

Когато внедрих алгоритъма за криптиране в моята програма, направих следното:

1. Избрах част от блока L в регистъра eax и R в регистъра edx.
2. Регистърът esi беше инициализиран с адреса на разширения ключ, повече за това по-долу.
3. На регистъра ebx беше присвоена стойността на адреса на разширената заместваща таблица, повече за това по-долу
4. Предава информацията от точки 1,2,3 към функцията на основния цикъл 32 - Z или 32 - R, в зависимост от ситуацията.

Ако погледнете диаграмата на доставките на ключовите елементи в параграф „ Основни цикли: “32-Z”, “32-R”", тогава нашият ключ за основния цикъл 32 - Z може да бъде представен по следния начин:

K 32-Z =

"as28", "zw37", "q839", "7342", "ui23", "8e2t", "wqm2", "ewp1",

"as28", "zw37", "q839", "7342", "ui23", "8e2t", "wqm2", "ewp1",

"ewp1", "wqm2", "8e2t", "ui23", "7342", "q839", "zw37", "as28"

Тези. от началото има k1, k2, k3, k4, k5, k6, k7, k8 - ‘ as28', 'zw37', 'q839', '7342', 'ui23', '8д2T', 'wqm2', 'ewp1'Тази последователност се повтаря три пъти. След това елементите вървят в обратен ред, т.е.: k8,k7,k6,k5,k4,k3,k2,k1 - 'ewp1', 'wqm2', '8e2t', 'ui23', '7342', 'q839', 'zw37', 'as28'.

Предварително подредих елементите в масива в реда, в който трябва да бъдат въведени в 32 - Z. По този начин увеличих паметта, необходима за ход, но се спасих от някои мисловни процеси, които не ми бяха необходими, и увеличих скоростта на алгоритъм, за чрез намаляване на времето за достъп до паметта! Тук описах само ключа за 32 - Z, за цикъл 32 - P направих същото, но използвах различна схема за захранване на елементи, която също описах в параграф „ Основни цикли: “32-З”, “32-Р”».

Време е да опиша изпълнението на функцията за замяна, както обещах по-горе. Не можах да го опиша по-рано, защото... това налага въвеждането на ново понятие – разширена заместваща таблица. Не мога да ти обясня какво е. Вместо това ще ви го покажа и вие можете сами да формулирате какво представлява - разширена заместваща таблица?

Така че, за да разберем какво е разширена заместваща таблица, имаме нужда от заместваща таблица; например ще взема тази, показана на фиг. 3.

Например трябваше да заменим номера 66793940h. Ще го представя в следния вид:

ФИГУРАТА НЕ Е ЗАПАЗЕНА

Ориз. 9

Сега, ако вземем елементите s1, s0, т.е. нисък байт, тогава резултатът от функцията за замяна ще бъде равен на 25h! След като прочетох статията на Андрей Винокуров, която цитирах в параграф „ Списък на използваната литература", вие наистина ще откриете, че ако вземете два низа, можете да получите масив, което ви позволява бързо да намерите заместващи елементи с помощта на команда на асемблер xlat.Казват, че има друг по-бърз начин, но Андрей Винокуров прекара около четири години в проучване на бързи алгоритми за прилагане на GOST! Мисля, че няма нужда да преоткриваме колелото, когато то вече съществува.

И така, относно масива:

Нека вземем първите два реда, нула и първи, и да създадем масив от 256 байта. Сега наблюдаваме една особеност: ако трябва да преобразуваме 00h, тогава резултатът ще бъде 75h (разчитаме на фиг. 3) - поставяме тази стойност в масива при отместване 00h. Взимаме стойността 01h, резултатът от заместващата функция 79h, поставяме я в масива при отместване 01 и така нататък до 0FFh, което ще ни даде 0FCh, което поставяме в масива при отместване 0FFh. Така че получихме разширена таблица със замествания за първата група редове: първи и нула. Но все още има три групи: втора страница 2, страница 3, трета страница 4, страница 5, четвърта страница 6, страница 7. С тези три групи се справяме по същия начин, както с първата. Резултатът е разширена таблица за заместване!

Сега можете да приложите алгоритъм, който ще извърши замяната. За да направим това, ние вземаме изходните кодове, които Андрей Винокуров публикува на страницата си, вижте „ Библиография».

lea ebx,extended_table_simple

mov eax, [поставете номера за замяна]

add ebx,100h ;прескочи до следващите два възела

sub ebx,300h ; така че в бъдеще ebx ще сочи към таблицата

Сега има още една функция: с предишните действия ние не само заменихме, но и изместихме числото 8 бита наляво! Всичко, което трябва да направим, е да преместим числото с още 3 бита наляво:

и получаваме резултата от операцията rol eax,11!

Не мога да добавя нищо повече относно оптимизацията, единственото нещо, което мога да подчертая, е това, което казах по-горе - използвайте регистри по-често, отколкото достъп до памет. Мисля, че тези думи са само за начинаещи; опитните разбират това прекрасно и без моите думи :).

Изисквания за ключова информация.

Както е посочено в статията на Андрей Винокуров, ключът се избира по два критерия:

— критерий за равновероятното разпределение на битовете между стойностите 1 и 0. Обикновено критерият на Пиърсън („хи-квадрат“) се използва като критерий за равновероятното разпределение на битовете.

Това означава, че ключът по принцип може да бъде произволно число. Тоест, когато се формира следващият бит от ключа, вероятността той да се инициализира до единица или нула е 50/50!

Моля, имайте предвид, че ключът се състои от осем елемента, всеки от които е 32 бита, така че общо има 32 * 8 = 256 бита в ключа и броят на възможните ключове е 2256! Това не ви ли учудва? 🙂

- сериен критерий.

Ако погледнем нашия ключ, който предоставих в параграф „ 4.1 Изпълнение на основната стъпка на крипто конвертиране", тогава ще забележите, че следната нотация е вярна:

Ориз. 10

В една фраза стойността на k 1 не трябва да се повтаря в k 2 или в друг ключов елемент.

Тоест ключът, който избрахме да разглеждаме като алгоритъм за криптиране, напълно отговаря на двата критерия по-горе.

Сега относно избора на заместваща маса:

Сега нека поговорим за това как да изберем правилната таблица за заместване. Основното изискване за избор на заместващи таблици е феноменът на „неповторение“ на елементи, всеки от които е с размер 4 бита. Както вече видяхте по-горе, всеки ред от таблицата за заместване се състои от стойностите 0h, 1h, 2h, 3h, ..., 0fh. Така че основното изискване гласи, че всеки ред съдържа стойностите 0h, 1h, 2h, ..., 0fh и всяка такава стойност в едно копие. Например последователността:

1 2 3 4 5 6 7 8 9 А Б В Г Д Е

Напълно отговаря на това изискване, но все пак! Не се препоръчва да изберете такава последователност като низ. Защото, ако подадете стойност към входа на функция, която разчита на такъв низ, тогава ще получите същата стойност като изхода! не ми вярваш След това вземете числото 332DA43Fh и осем такива реда като таблица на заместванията. Извършете операцията по подмяна и ви уверявам, че резултатът, който ще получите, е 332DA43Fh! Тоест, същото като това, което сте подали като вход за операцията! Но това не е признак на добри маниери при криптиране и беше ли така? 🙂

Това беше едно изискване, следващият критерий казва, че - всеки бит от изходния блок трябва да бъде статистически независим от всеки бит от входния блок!

Как изглежда това по-просто? И ето как например избрахме елемента s0 = 0Fh, 01111b от горното число. Вероятността сега да заменим първия бит с единица или нула е 0,5! Вероятността за замяна на втория, третия и четвъртия бит, всеки бит, който разглеждаме отделно, с единици или нули също е 0, 5. При избора на s1 = 0Eh, вероятността да заменим нулевия бит, а това е „0“, с нула или едно твърде равно на – 0,5! По този начин, според този критерий, няма модел между замяната на нулеви битове на елементите s0, s1! Да, можете да замените единици, но можете също да замените нули. 🙂

За да оцените таблицата според този критерий, можете да изградите таблица с корелационни коефициенти, изчислени по формулата:

— ако p = 1, тогава стойността на бит j на изхода е равна на стойността на бит i на входа за всяка комбинация от битове на входа;

— ако p = -1, тогава стойността на бит j на изхода винаги е обратна на входния бит i;

— ако p = 0, тогава изходният бит j с еднаква вероятност приема стойностите 0 и 1 за всяка фиксирана стойност на входния бит i.

Да вземем пример с един ред:

д	б	4	1	3	Е	5	9	0	А	д	7	6	8	2	° С

Нека го разделим на „компоненти“:

Нека изчислим един коефициент, използвайки формулата, дадена по-горе. За да бъде по-лесно да разберете как се прави това, ще обясня по-подробно:

— вземаме 0-ия бит от 0-то число (0) на входа и 0-ия бит от 0-то число на изхода (1) и изпълняваме операцията 0 XOR 1 = 1.

— вземаме 0-тия бит от 1-вото число (1) на входа и 0-ия бит от 1-вото число на изхода (1) и изпълняваме операцията 1 XOR 1 = 0.

— вземаме 0-тия бит от 2-рото число (0) на входа и 0-ия бит от 2-рото число на изхода (0) и изпълняваме операцията 0 XOR 0 = 0.

— вземаме 0-ия бит от 3-то число (1) на входа и 0-ия бит от 3-то число на изхода (1) и изпълняваме операцията 1 XOR 1 = 0.

След извършване на последователни операции XOR в тази последователност, ние преброяваме броя на всички ненулеви стойности, получаваме стойността 6. Следователно P 00 = 1-(6/2 4-1) = 0,25. И така, оказа се, че стойността на бит 0 на изхода е равна на стойността на бит 0 на входа в 4 случая от 16;

Финална таблица с коефициенти:

Таблицата с коефициенти ще бъде както следва (който не е твърде мързелив, може да преизчисли)

	Вход
Изход		0	1	2	3
	0	-0,25	0,00	0,00	0,00
	1	0,00	1,00	0,00	0,00
	2	0,00	0,00	1,00	0,00
	3	0,00	0,00	0,00	-0,50

Е, в тази таблица нещата са още по-лоши - битове 1 и 2 от групата остават непроменени! Криптоаналитикът има какво да се обърне 🙂 Като се вземат предвид всички тези изисквания, чрез просто грубо търсене бяха открити таблици за пермутация, съответстващи на определената теория (към днешна дата - 1276 комбинации). Ето някои от тях:

09 0D 03 0E-06 02 05 08-0A 07 00 04-0C 01 0F 0B

00 05 0A 07-03 08 0F 0C-0E 0B 04 09-0D 06 01 02

06 0B 0F 00-0C 01 02 0D-08 07 09 04-05 0A 03 0E

04 0E 00 09-0B 01 0F 06-03 0D 07 0A-0C 02 08 05

04 02 08 0E-05 0F 03 09-0B 01 0D 07-0A 0C 06 00

07 03 09 0C-08 00 06 0F-0E 04 01 0A-0D 0B 02 05

06 0F 03 08-0D 04 0A 01-09 02 05 0C-00 0B 0E 07

0C 06 08 01-03 09 07 0E-0B 05 0F 02-04 0A 00 0D

04 0B 09 06-0E 01 00 0F-0A 05 03 0C-0D 02 07 08

00 0E 0F 01-07 08 09 06-04 0B 0A 05-03 0D 0C 02

0F 09 01 07-04 0A 08 06-0E 00 02 0C-05 03 0B 0D

0A 03 04 01-05 0C 0B 0E-08 06 0F 0D-07 09 00 02

0B 06 0F 01-04 0A 08 05-00 0D 0C 02-07 09 03 0E

0C 03 02 08-0D 06 0B 05-07 09 04 0F-0A 00 01 0E

02 0B 0F 04-09 00 06 0D-05 0E 01 08-0C 07 0A 03

Списък на използваната литература.

1. Статия от Андрей Винокуров:

GOST 28147-89 алгоритъм за криптиране, неговото използване и прилагане

за компютри на платформата Intel x86.

(може да се намери на: http://www.enlight.ru/crypto/frame.htm).

Ето изходните кодове за прилагане на алгоритъма за криптиране.

1. Статия от Хорст Файстел:

Криптография и компютърна сигурност.

(може да се намери на същия адрес като предишната статия)

1. Рос Н. Уилямс:

Основно ръководство за CRC алгоритми за откриване на грешки

Публикувано на уебсайта www.wasm.ru.

Благодарности

Бих искал да изразя своята благодарност на всички посетители на форума www.wasm.ru. Но специално бих искал да благодаря на ChS, който в момента е известен като SteelRat, той ми помогна да разбера неща, които вероятно никога не бих разбрал, както и помощ при написването на параграфа: „ Изисквания за ключова информация“, основната част от този параграф е написана от него. Също така съм дълбоко благодарен на служителя на KSTU. А.Н. Туполев Аникин Игор Вячеславович и би било грях да не споменем Крис Касперски за това, което е, и Володя / wasm.ru за неговите инструкции. О, и аз го получавам от него :). Също така искам да спомена Sega-Zero / Callipso, че ми навяха някаква математическа джунгла.

Това е може би всичко, което бих искал да ви кажа.

Ще бъда благодарен за критика или въпроси, свързани с тази статия или просто съвет. Моите данни за контакт: [имейл защитен], ICQ – 337310594.

С най-добри пожелания, Evil`s Interrupt.

P.S.: Не съм се опитвал да надмина никого с тази статия. Написано е с намерението да улесни изучаването на GOST и ако имате затруднения, това не означава, че аз съм виновен за това. Бъдете разумни и търпеливи, всичко най-хубаво на вас!