Спосіб криптографічного перетворення l-бітових вхідних блоків цифрових даних в l-бітові вихідні блоки

1 Спосіб криптографічного перетворення Lбітових вхідних блоків цифрових даних в L-бітові ВИХІДНІ блоки, який полягає в розбитті блоку даних на N > 2 підблоки, почерговому перетворенні підблоків шляхом формування принаймні одного бінарного вектора за значенням підблоку і зміни підблоку з використанням бінарного вектора, який відрізняється тим, що формування бінарного вектора на наступному кроці перетворення підблоку здійснюють залежно від структури бінарного вектора на попередньому кроці перетворення підблоку 2 Спосіб за п 1, який відрізняється тим, що формують два бінарні вектори і один з них перетворюють за допомогою операції циклічного зсуву на число бітів, що дорівнює значенню другого бінарного вектора 3 Спосіб за п 1, який відрізняється тим, що зміну одного з підблоків здійснюють шляхом виконання над ним операції циклічного зсуву на число бітів, що дорівнює поточному значенню бінарного вектора 4 Спосіб за п 1, який відрізняється тим, що при перетворенні підблоків використовують таблиці підстановок, число яких Т > 2, при цьому за бінарним вектором вираховують номер (v) таблиці і підблок змінюють за допомогою операції підстановки, що задається v-тою таблицею О (О Винахід відноситься до галузі електрозв'язку і обчислювальної техніки, а саме до галузі криптографічних способів та пристроїв для шифрування повідомлень (інформації) В описі способу, що заявляється, використовуються такі терміни секретний ключ - це бінарна інформація, яка відома тільки законному користувачу, криптографічне перетворення - це перетворення цифрової інформації, яке забезпечує вплив одного біта початкових даних на багато бітів вихідних даних, наприклад, з метою захисту інформації від несанкціонованого читання, формування цифрового підпису, виробляння коду виявлення модифікацій, важливими видами криптографічних перетворень є одностороннє перетворення, хеширування і шифрування, хеширування інформації - це спосіб формування так званого хеш-коду, розмір якого є фіксованим (звичайно 128 бітів) для повідомлень будьякого розміру, широко застосовуються способи хеширування, які базуються на ітеративних хешфункціях із застосуванням блочних механізмів криптографічного перетворення інформації [див Lai X, Massey J L Hash Functions Based on Block Ciphers/Workshop on Theory and Applications of Cryptographic Techniques EUROCRYPT'92 Hungary, May 24 - 28, 1992 Proceedings P 53 - 66 ], шифрування - це процес перетворення інформації, який залежить від секретного ключа і який перетворює початковий текст в шифртекст, який являє собою псевдовипадкову ПОСЛІДОВНІСТЬ знаків, з якої отримання інформації без знання секретного ключа є практично неможливим, ю ю 55496 дешифрування - це процес, зворотний процетільки від його початкового значення, прикладом дурі шифрування, дешифрування забезпечує відодномісних операцій є операції циклічного зсуву, новлювання інформації за криптограмою за умови двомісна операція - це операція, яка виконузнання шифрключа, ється над двома операндами, результат виконаншифр - це сукупність елементарних кроків пеня деякої даної двомісної операції залежить від ретворення вхідних даних з використанням секрезначення кожного операнда, прикладом двомісних тного ключа, шифр може бути реалізований у виоперацій є операції складання, віднімання, многляді програми для комп'ютера або у вигляді ження та ш окремого пристрою, ВІДОМІ способи блочного шифрування даних, див наприклад стандарт США DES [ National Buбінарний вектор - це деяка ПОСЛІДОВНІСТЬ нуreau of Standards Data Encryption Standard Federal льових і одиничних бітів, наприклад 101101011, Information Processing Standards Publication 46 конкретна структура бінарного вектора може бути January 1977 ] В цьому способі шифрування блоінтерпретована як бінарне число, якщо вважати, ків даних виконують шляхом формування секретщо позиція кожного біта відповідає бінарному розного ключа, розбиття блока даних, який перетворяду, тобто бінарному вектору може відповідати рюється, на два підблоки L і R і зміни їх по черзі числове значення, яке визначається однозначно шляхом виконання операції порозрядного скластруктурою бінарного вектора, дання за модулем два над підблоком L і бінарним криптоаналіз - метод обчислювання секретновектором, який формується як вихідне значення го ключа для отримання несанкціонованого достудеякої функції F від значення підблока R Після пу до зашифрованої інформації або розробка мецього блоки переставляються місцями Функція F в тоду, який забезпечує доступ до зашифрованої цьому способі реалізується шляхом виконання інформації без обчислення секретного ключа, операцій перестановки і підстановки, які виконуодностороннє перетворення - це таке переються над підблоком R Цьому способу властива творення L-бітового вхідного блока даних в Lвисока швидкість перетворень при втіленні у вибітовий вихідний блок даних, яке дозволяє легко гляді спеціалізованих електронних схем обчислити вихідний блок за вхідним блоком, а обчислення вхідного блока, який би перетворювався Однак відомий спосіб використовує секретний у випадково вибраний вихідний блок, є практично ключ малого розміру (56 бітів), що робить його нездійсненим завданням, вразливим до криптоаналізу шляхом підбору ключа Останнє пов'язано з високою потужністю суодностороння функція - це функція, значення часних комп'ютерів масового використання якої легко обчислюється за даним аргументом, однак обчислення аргументу за даним значенням Найближчим за своєю технічною суттю до функції є важким завданням, односторонні функції способу криптографічного перетворення L-бітових реалізуються як ПОСЛІДОВНІСТЬ процедур одностовхідних блоків цифрових даних в L-бітові ВИХІДНІ роннього перетворення деякого вхідного блока блоки, що заявляється, є спосіб, описаний в праці [ (аргументу), вихідне значення якого приймається Kalmski В S , Robshaw M J В Fast Block Cipher за значення функції, Proposal/ Fast Software Encryption Proceedings of the Cambridge Security Workshop, Lecture Notes in криптостійкість - це міра надійності захисту Computer Science v 809, Sprmger-Verlag, 1994, pp зашифрованої інформації і являє собою трудоміс26 - 39, див також В Schneier, "Applied Cryptograткість, що вимірюється КІЛЬКІСТЮ елементарних phy", Second Eddition, John Wiley & Sons, Inc , New операцій, які необхідно виконати для відновлення York, 1966, pp 342 - 344] Цей спосіб включає фоінформації за криптограмою за умови знання алрмування секретного ключа, розбиття вхідного горитму перетворення, але без знання секретного 1024-байтового блока даних на 32-бітові підблоки ключа, в разі односторонніх перетворень під крипВо, В-і, В>2 В255 і почергового перетворення підблоТОСТІЙКІСТЮ розуміється складність обчислення ків Секретний ключ формується у вигляді таблиці вхідного значення блока за його вихідним значенперестановки і упорядкованої ПОСЛІДОВНОСТІ ІЗ ням, 2048 підключів Qo, Qi, Q2 Q2047, кожний з яких операції циклічного зсуву, що залежать від пемає довжину 32 біти Шифрування блока даних ретворюваних підблоків або від бінарного вектора, виконується у вигляді чотирьох раундів перетво- це операції циклічного зсуву на число бітів, яке рення Один раунд шифрування полягає в наступзадається значенням підблока або значенням біному Згідно З таблицею перетворення, яка заданарного вектора, операції циклічного зсуву ліворуч ється секретним ключем, виконується (праворуч) позначаються знаком " « "), перестановка підблоків даних Потім по черзі пенаприклад, запис Ві 2 , подібні (схожі) операції є бається 32-бітовий бінарний вектор V за значенням зовими для шифру RC5 [ R Rivest, The RC5 Enпідблоків Bh, Bk, В,, де h, і, j , k є різними номерами, cryption Algorithm, Fast Software Encryption, Second згідно з аналітичним виразом V=Bh + F(Bh, Bk, В,) + International Workshop Proceedings (Leuven, BelQq, де знаком "+" позначена операція складання за gium, December 14 - 16, 1994), Lecture Notes in модулем 2 32 , q - номер поточного підключа Computer Science, v 1008, Sprmger-Verlag, 1995, pp 86-96], Номери h, і, j , k обирають в залежності від ноодномісна операція - це операція, яка виконується над одним операндом (блоком даних або бінарним вектором), значення підблока після виконання деякої даної одномісної операції залежить меру раунда шифрування і номеру кроку перетворення підблока Сформований бінарний вектор використовується під час перетворення підблока В, таким чином Виконується операція порозрядно 55496 поточне значення бінарного вектор через значення бінарного вектора на попередніх кроках перетворення Новим є також те, що формують два бінарні вектори і один з них перетворюють за допомогою операції циклічного зсуву на КІЛЬКІСТЬ біт, яка дорівнює значенню другого бінарного вектора Завдяки такому вирішенню забезпечується додаткове підвищення криптостійкості перетворення блоків інформації довжиною І_=512, 1024, 2048, 4096 і 8192 бітів, оскільки операції циклічного зсуву такого типу є нелінійними і задають більш складну функцію формування бінарного вектору Новим також є те, що змінювання одного з підблоків здійснюють шляхом виконання над ним операції циклічного зсуву на КІЛЬКІСТЬ біт, яка доріСпосіб забезпечує високу криптостійкість завнює поточному значенню бінарного вектора вдяки великій довжині блока даних і використанню Завдяки такому рішенню забезпечується довеликої КІЛЬКОСТІ операцій перетворення, які придаткове підвищення криптостійкості перетворення, падають на один підблок оскільки операції циклічного зсуву такого типу є Однак цей спосіб має недоліки, а саме під час нелінійними і виконуються безпосередньо над підпрограмної реалізації він не забезпечує високої блоками, які перетворюються швидкості криптографічного перетворення даних, Новим є також те, що під час перетворення яка є необхідною для побудови програмних систем підблоків використовують таблиці підстановок, захисту комп'ютерної інформації, що працюють в КІЛЬКІСТЬ яких Т>2, при цьому за бінарним вектомасштабі реального часу Наприклад, для мікрором обчислюють номер (v) таблиці і підблок зміпроцесора Pentium/200 швидкість шифрування не нюють за допомогою операції підстановки, яка перевищує 6 Мбітів/с Цей недолік пов'язаний з задається v-тою таблицею тим, що для забезпечення СТІЙКОСТІ ДО диференційного криптоаналізу потрібно виконувати велику Завдяки такому вирішенню забезпечується КІЛЬКІСТЬ операцій перетворення, які припадають додаткове підвищення криптостійкості перетвона один біт вхідних даних рення блоків інформації довжиною І_=64 і 128 бітів, оскільки операції підстановки є нелінійними і ефеВ основу винаходу поставлена задача розроктивні для реалізації при порівняно малому розмірі бити спосіб криптографічного перетворення Lблока інформації, який перетворюється Викорисбітових вхідних блоків цифрових даних в L-бітові тання заздалегідь не визначених операцій підстаВИХІДНІ блоки, в якому перетворення вхідних даних новки є способом досягнення високої криптостійздійснювалося б таким чином, щоб забезпечувакості до найбільш сильних методів криптоаналізу, лося зменшення КІЛЬКОСТІ операцій перетворення, зокрема до диференційного криптоаналізу, який які припадають на один біт вхідних даних, при одописано, наприклад, в праці [Biham E , Shamir A ночасному забезпеченні високої СТІЙКОСТІ ДО ДИDifferential Cryptanalysis of DES-hke Cryptosystems/ ференційного криптоаналізу, завдяки чому підвиJournal of Cryptology, v 4, n 1, 1991, pp 3-721] щується швидкість шифрування Нижче суть винаходу, який заявляється, більш Поставлена задача вирішується тим, що в докладно роз'яснюється прикладами його здійсспособі криптографічного перетворення L-бітових нення з посиланням на креслення, що додаються вхідних блоків цифрових даних в L-бітові ВИХІДНІ блоки, який полягає в розподілі блока даних на N > Скорочений опис креслень 2 підблоків, почерговому перетворенні підблоків На фіг 1 наведена узагальнена схема криптошляхом формування принаймні одного бінарного графічного перетворення згідно зі способом, який вектора за значенням підблока і змінюванні підзаявляється блока з використанням бінарного вектора, згідно з На фіг 2 наведена схема шифрування ВІДПОВІвинаходом формування бінарного вектора на наДНО до прикладу 2 ступному кроці перетворення підблока здійснюють На фіг 3 наведена схема одностороннього пезалежно від структури бінарного вектора на поперетворення ВІДПОВІДНО до прикладу З редньому кроці перетворення підблока Кращі варіанти здійснення винаходу Винахід пояснюється узагальненою схемою Завдяки такому вирішенню забезпечується криптографічного перетворення блоків даних на краще розсіювання впливу бітів вхідного блока основі способу, що заявляється, яка показана на даних на біти вихідного блока, завдяки чому зафіг 1, безпечується висока СТІЙКІСТЬ до диференційного ДЄ В - бЛОК, ЯКИЙ ПереТВОрЮЄТЬСЯ, Ь-і, І32, Ьп криптоаналізу одночасно із зменшенням КІЛЬКОСТІ - підблоки, які перетворюються, F - операційний операцій перетворення, які виконуються, що і забезпечує підвищення швидкості криптографічного блок, який здійснює зміну підблоків, f - операційперетворення Краще розсіювання забезпечується ний блок, який здійснює формування бінарного за рахунок того, що біти підблоків, які перетворені вектора, Vo - початкове значення бінарного вектона попередніх кроках перетворення впливають на ра Вхідний L-бітовий блок цифрових даних, де Lхід перетворення поточного блока подвійним чиКІЛЬКІСТЬ бінарних розрядів в блоці, розбивається ном (1) безпосередньо впливаючи на поточне на N>2 підблоків, кожний з яких має розмір L/N значення бінарного вектора і (2) впливаючи на бітів Суцільна ЛІНІЯ відповідає передаванню підго складання за модулем 2 над підблоком В, і V і значення яке отримується після виконання цієї операції присвоюється підблока В, Це записуєтьсяу вигляді співвідношення B|^B|®V, де знак ' V означає операцію присвоювання і знак "Ф" означає операцію порозрядного складання за модулем 2 Після ЦЬОГО аналогічно виконується перетворення іншого підблока і т д , поки не будуть перетворені всі підблоки Кожний новий крок формування 32бітового бінарного вектора виконується незалежно від значення бінарного вектора, який був сформований на попередньому кроці В одному раунді шифрування індекс і приймає за деякою черговістю 256 різних значень, що відповідають всім номерам підблоків (від 0 ДО 255) 8 В третьому випадку це може бути, наприклад, перетворення, що задається виразом В ^ В Ф Qv, де Qv - підключ з номером v, який обчислюється за значенням бінарного вектора v = V 11 mod 2 Останнє співвідношення задає вибір номера рівного значенню 11 молодших розрядів бінарного вектора Важливим поодиноким випадком другого варіанту використання бінарного вектора в перетвореннях підблока є виконання операції підстановки над підблоком, яка залежить від бінарного вектора Такий тип підстановок може бути використаний при задаванні великої КІЛЬКОСТІ різних таблиць підстановок, кожній з яких присвоєно порядковий номер, і для виконання операції підстановки над підблоком використовують таблицю, номер якої вибирають залежно від значення V, наприклад, якщо використовують 32 таблиці підстановки, номер таблиці можна обчислювати за формулою v = V mod 2 5 Рація вибору таблиці підстановки, яка використовується для виконання операції підстановки над підблоком на поточному кроці, за спеціально формованим бінарнним вектором полягає в тому, щоб зробити не визначеним наперед вибір таблиці підстановки для кожного кроку перетворення підблоків, що підвищує СТІЙКІСТЬ криптографічного перетворення 55496 блоків, які перетворюються, пунктирна - передаванню бінарного вектора Підблоки по черзі перетворюються шляхом їх зміни за допомогою операційного блока F, який використовує в перетвореннях значення бінарного вектора, що обумовлює залежність вихідного значення підблока, який перетворюється, від значення бінарного вектора Операційний блок f для виконання перетворення бінарного вектора використовує значення підблока, перетвореного на попередньому кроці, тобто операційний блок f формує бінарний вектор за структурою одного з підблоків, які перетворюються, і за значенням бінарного вектора, яке він мав на попередньому кроці перетворення підблока з використанням бінарного вектора Це обумовлює залежність значення бінарного вектора від даних, які перетворюються Виконання процедур перетворення, які задаються функцією F, над підблоком будемо називати одним кроком змінювання підблока Виконання процедур перетворення, що задаються функцією f, над бінарним вектором будемо називати кроком формування бінарного вектора Крок перетворення підблока включає крок формування бінарного вектора і крок змінювання підблока Кроки перетворення виконуються послідовно над усіма підблоками, після чого здійснюється перестановка підблоків В окремих випадках реалізації способу, що заявляється, перестановка блоків може не використовуватися Виконання N кроків змінювання підблока, N кроків формування бінарного вектора і перестановка підблоків, що показані на фіг 1, складають один раунд перетворення Значення бінарного вектора після N-ro кроку формування бінарного вектора править за початкове значення бінарного коду для наступного раунда перетворення при побудові односторонніх функцій перетворення L-бітових блоків цифрових даних При побудові шифрів початкове значення бінарного вектора для кожного раунда формується в залежності від секретного ключа КІЛЬКІСТЬ раундів перетворення може бути заданим в залежності від конкретних варіантів побудови операційних блоків F і f Важливим в наведеній схемі є те, що бінарний вектор формують залежно від його структури на попередньому кроці перетворення підблока з використанням бінарного вектора Під перетворенням підблока з використанням бінарного вектора розуміють (1) виконання двомісної операції, операндами якої є підблок і бінарний вектор, або (2) виконання над підблоком одномісної операції (наприклад, підстановки чи перестановки бітів) , модифікацію якої вибирають залежно від значення бінарного вектора, або (3) виконання двомісної операції, що виконується над підблоком і підключем, номер якого залежить від значення бінарного вектора Наприклад, в першому випадку це може бути перетворення 32 - бітового бідблока В, коли даному підблоку присвоюють значення рівне результату складання за модулем 2 3 2 підблока В і бінарного вектора V B^B+V В другому випадку це може бути операція циклічного зсуву ліворуч, що виконується над підблоком В на число розрядів рівне значенню бінарного вектора, яку аналітично виражають співвідношенням Під формуванням бінарного вектора ми розуміємо запис, наприклад, в реєстр чи комірку пам'яті обчислювального пристрою деякої ПОСЛІДОВНОСТІ одиничних чи нульових бітів Під формуванням бінарного вектора залежно від його структури на попередньому кроці перетворення підблока з використанням бінарного коду ми розуміємо задания залежності поточного значення бінарного вектора, що формується, від значення, яке бінарний вектор мав на попередньому корці використання при перетворенні підблока даних Наприклад, скажімо, блок В був перетворений з використанням значення бінарного вектора V Перед використанням бінарного вектора на деякому іншому кроці перетворення, наприклад підблока В,, бінарний вектор може формуватися у ВІДПОВІДНОСТІ З виразом V ^V+Qt,, де b=Bimod 2 11 - номер підключа, який обчислюється в залежності від значення підблока Можливість технічної реалізації способу, що заявляється, пояснюється конкретними прикладами його здійснювання Приклад 1 Цей приклад є варіантом способу, що заявляється, який виконує шифрування блоків даних по 512-байт (4096 бітів) Використання такого розміру вхідних блоків обумовлене тим, що в комп'ютерних системах цей розмір блоків є стандартним При використанні блочних шифрів, які обробляють блоки такого розміру, зберігається можливість довільного доступу до даних, які зберігаються на вбудованому магнітному ноем в зашифрованому вигляді В цьому прикладі використовується 8192байтовий секретний ключ у вигляді сукупності з 2048 пронумерованих 32-бітових ПІДКЛЮЧІВ {Qv}, де v = 0, 1, 2, , 2047 Секретний ключ формують, наприклад, шляхом його копіювання з магнітного носія в оперативну пам'ять комп'ютера Криптографічне перетворення за прикладом 1 описується 55496 таким алгоритмом Алгоритм 1 Шифрування 4096-бітових блоків ВХІД 4096-бітовий блок, виконаний у вигляді сукупності 128 32-бітових підблоків {В-і, В2 В us,} 1 Встановити номер блока, що обробляється, і = 1 і початкове значення бінарних векторів V-i, V2, V31 v Vi< Q1, V2< Q 2l V3 » 22, де "-" означає операцію віднімання за модулем 2 3 2 6 Сформувати бінарний вектор v за структурою бінарного вектора V3 v ^ v Ф (V3 mod 211) 7 Сформувати бінарний вектор V1 V-i^Vi + Qv 8 Перетворити підблок Ві Ві [ (Ві < « V2) Ф V3 ] + V! 9 Сформувати бінарний вектор V1 V-i^- Ві 10 Перетворити підблок Ві Ві