4 розд моног 2014. Обрунтування та аналіз математичних моделей симетричних блокових перетворень

• Название: Обрунтування та аналіз математичних моделей симетричних блокових перетворень
• Дата: 11.01.2022
• Размер: 1.18 Mb.
• Имя файла: 4 розд моног 2014.docx
• Тип: Обґрунтування; #328434
• страница: 1 из 7

4. Побудування, аналіз та застосування криптосистем типу симетричні блокові перетворення

4.1 Етапи розроблення , класифікація та загальні вимоги до блокових симетричних перетворень

4.2 Обґрунтування та аналіз математичних моделей симетричних блокових перетворень

4.3 Обґрунтування та вибір режимів роботи симетричних блокових перетворень

4.3 Основні методи блокових симетричних перетворень та їх властивості

4.4 Стан стандартизації та уніфікації блокових симетричних перетворень

4.5 Блокові симетричні перетворення на основі ланцюгів Фейстеля

4.6 Блокові симетричні перетворення на основі схеми Лея - Массея

4.7 Блокові симетричні перетворення на основ СПН структур

4.8 Методи криптоаналізу блокових симетричних перетворень

4.9 Дослідження просторової складності блокових симетричних перетворень

4.10 Дослідження просторової складності блокових симетричних перетворень

4.11 Сутність та порівняльний аналіз стандартів блокових симетричних перетворень

4.12 Основні проблемні питання та висновки відносно побудови, удосконалення та застосування блокових симетричних перетворень

Нині практично доведено, що симетричне блокове перетворення (СБП) і на його основі розроблені БСШ є одним із основних криптографічних механізмів забезпечення конфіденційності, цілісності та доступності інформації та інформаційних ресурсів в сучасних інформаційних системах (ІТ), телекомунікаційних системах (ТС) та, в цілому, в інформаційно-телекомунікаційних системах (ІТС). Вони використовуються при реалізації послуг з захисту інформації, як самостійне так і у сукупності із іншими криптографічними механізмами безпеки. Особливо важливим застосуванням БСШ є тоді, коли вимагається середня чи висока швидкодія шифрування чи автентифікації інформації, а також швидкісна реалізації режимів роботи БСШ.

В цьому розділі наводяться теоретичні та практичні результати та пропозиції відносно побудування, аналізу та застосування симетричних блокових перетворень. При викладення результатів будемо посилатись та враховувати уже викладене в підрозділі 1.4 в тому числі що стосується:

• 
  основних понять та визначень відносно вимог до блокового симетричного
  

перетворення;

• 
  загальних вимог до перспективних блокових симетричних перетворень відносно криптографічній стійкості;
  
• 
  спеціальних вимог до перспективного блокового симетричного перетворення;
  

загальної класифікації та рекомендацій відносно вимог до симетричних блокових

перетворень;

• 
  стану стандартизації та уніфікації блокових симетричних перетворень;
  
• 
  оцінки криптографічної стійкості блокових симетричних перетворень.
  

4.1 Етапи розроблення, класифікація та загальні вимоги до блокових симетричних перетворень

Історично криптографічні СБП реалізовувались у вигляді БСШ. Побудування та аналіз БСШ історично розпочинається з розроблення в США алгоритму БСШ DES (Data Encryption Standard) [6,8]. Підґрунтям створення алгоритму DES були роботи авторів [1,2], що були опубліковані на самому початку 70 років у доступному вигляді. Однією із вимог, яка до нього була висунута, це те щоби алгоритм був опублікований та не мав обмежень без ризику відносно його стійкості, тобто неможливості його компрометації за умов його відкритості. В 1977 р. алгоритм БСШ DES був опублікований в якості федерального стандарту США, який вступив у дію в липні того ж року. Основним недоліком алгоритму БСШ DES стала мала довжина секретного ключа – всього 56 бітів. Конструкція алгоритму шифрування DES виявилася настільки вдалою, що продовжила свій розвиток в інших відомих криптографічних алгоритмах – перше за все, ГОСТ 28147–89 [5], FEAL [7], IDEA [25], Skipjack [7], Камелія [ ] і ряді інших менш відомих алгоритмах БСШ, що були розроблені в 80-х та 90-х роках 20 століття

Необхідно відмітити, що до початку 90-х років у закордонному відкритому друку практично не було фундаментальних робіт присвячених БСШ. Друкувались лише дослідження, що стосувалися криптографічного алгоритму DES. Серед них необхідно роботи кінця 90-х років, які стосувались нових ефективних методів криптоаналізу БСШ, перше за все диференційного та лінійного криптоаналізу [30-34]. Тоді склалась ситуація, коли для забезпечення конфіденційності та цілісності несекретної інформації в державних і комерційних установах продовжувалось використання морально та технічно застарілих шифрів. Але швидкий розвиток обчислювальної техніки й безлічі різних, високоефективних методів криптоаналізу БСШ, стали представляти для них потенційні загрози. Крім того, криптографічні алгоритми, що були розробленими, не підтвердили необхідного рівня безпеки, наприклад, Skipjack [7]. Вказане привело до однієї із найбільш важливих подій у сфері прикладної криптографії  – оголошення та проведення міжнародного конкурсу AES (Advanced Encryption Standard) [11 – 12, 14]. В 2001 році на його основі у звуженій версії був прийнятий федеральний стандарт США FIPS-197, який на нинішній час отримав широке застосування в США та у світі [14]. В самих США стандарт дозволений для захисту «цілком таємної» інформації [14].

Зважаючи на позитивний досвід, по аналогії з проектом AES у Європі були розгорнуті та виконані аналогічні проекти (NESSIE) і Японії (CRYPTREC) [44,16,18 21,22]. Відкритий проект NESSIE був початий в 2000 році під егідою Європейської комісії. Завданнями проекту NESSIE був відбір кращих десяти криптографічних примітивів, в тому числі трьох проектів алгоритмів БСШ. Важливими результати досліджень, що отримані за результатами виконання Європейського проекту Nessie в частині БСШ, стало прийняття міжнародного стандарту ISO/IEC 18033-3 [14], а потім і його гармонізація в якості національного ДСТУ ISO/IEC 18033-3 [14].

В Україні нині продовжує використовуватися стандарт БСШ ДСТУ ГОСТ 28147:2009, розроблений у 80-х роках минулого сторіччя [5]. Особливостю алгоритму є використання стандартного довготривалого ключового елемента (ДКЕ), який, як зазначено в стандарті, поставляється в установленому порядку. Дослідження залежності криптографічного стійкості і можливості дешифрування криптограм третьою авторизованої стороною, що поставляє ДКЕ, без знання ключа шифрування, а також формування класу шифрів, що допускають існування такої властивості, стало актуальною науковою та практичною проблемою. Це підтверджується тим, що стандарт ГОСТ 28147:2009 вже виведений з дії в Білорусії [52], а також удосконалений в Російській Федерації (алгоритм «Кузнечик»)[ ]. Також стандарти БСШ, що застосовуються в Україні на сучасних обчислювальних архітектурах, мають істотно меншу продуктивність, ніж діючі закордонні аналоги. В таких умовах застосовувати ДСТУ ГОСТ 28147-89 не тільки в крипто логічному змісті, а і в політичному на має сенсу. Тому актуальним стало вирішення проблеми обґрунтування параметрів і синтезу стійких і продуктивних сучасних БСШ для заміни діючого стандарту.

ЇЇ конкретне вирішення отримано розробкою та введення в дію взаємно пов’язаних Національних стандартів України ДСТУ 7624:2014 “ Інформаційні технології. Криптографічний захист інформації. Алгоритм симетричного блокового перетворення ” та ДСТУ 7564:2014 “ Інформаційні технології. Криптографічний захист інформації. Функція гешування[ ]”.

Необхідно також відмітити, що сучасні БСШ є одним з найбільш поширених криптографічних примітивів. Вони, окрім забезпечення конфіденційності, використовуються також і як конструктивний елемент при побудові функцій гешування (ФГ), кодів автентифікації повідомлень (КАП), генераторів псевдовипадкових послідовностей (ГПВП) тощо. Важливість БСШ підтверджує проведення декількох міжнародних криптографічних конкурсів [11,12,44, 16,22-29], орієнтованих на розробку БСШ. Обґрунтування конструкції раундового відображення БСШ із заданими криптографічними властивостями необхідно також для забезпечення перетворення з необхідною чи зі збільшеною швидкодією. Більше того, ці ж конструкції можуть використовуватися як нелінійне перетворення при синтезі потокових шифрів, ітеративних геш-функцій тощо. Крім того, для блокових алгоритмів необхідна розробка показників ефективності основних високорівневих конструкцій і нових схем генерації циклових ключів для перспективних шифрів. Додатково, при функціонуванні обладнання в середовищах, що не мають повної довіри (засоби автентифікації користувача, модулі доступу до цифрового телебачення, що знаходяться безпосередньо у абонента тощо), можлива реалізація атак для отримання секретного параметра, орієнтованих на властивості математичного перетворення, а також на апаратні засоби криптографічного захисту. Захист від ряду атак такого типу може бути реалізовано як за рахунок удосконалення перетворення, так і при безпосередній розробці засобів криптографічного захисту.

Важливим є той факт, що 30 червня 2006 г. на сайті ДСТЗІ України появилось офіційне оголошення про проведення конкурсу з висунення кандидатів на національний стандарт шифрування. Під час проведення конкурсу фактично було розглянуто чотири (шифри ADE, Калина, Мухомор і Лабіринт) [22-29]. За результатами конкурсу прийнято рішення зупинитися на загальновизнаному світовому стандарті Fips-197 (AES). Національні пропозиції виявилися або занадто близькими по конструкції до світового лідеру, або недостатньо прозорими з точки зору очікуваних показників стійкості в порівнянні з світовим авторитетом.

В цілому відносно проведеного конкурсу можна зробити такі висновки:

• 
  рішення, що були представлені на український конкурс, у порівнянні з шифром Rijndael не мали помітних переваг, або науково методичний апарат, яким володіли розробники, не дозволив їм обгрунтувати суттєві переваги своїх рішень ;
  
• 
  конкурувати з пропозиціями, що пройшли експертизу фахівців світового класу, дуже важке завдання;
  
• 
  оперативно знайти краще рішення в умовах суспільного конкурсу знайти важко.
  

В той же час конкурс не пройшов марно, основними досягненнями конкурсу є певне обґрунтування вимог до перспективних БСШ, а також засвоєння участниками конкурсу науково – методичного аппарату синтезу та аналізу перспективних БСШ. Тобто отримано досвід не тільки відносно розробки сучасних БСШ, але і в освоєнні всього науково-методичного апарату, що застосовується для оцінки та порівняння між собою різних алгоритмів БСШ, виконання перевірки властивостей і показників стійкості алгоритмів шифрування.

Аналіз підтвердив, що основними областями застосування національного стандарту БСШ є такі як[ ]:

• 
  забезпечення конфіденційності інформації та повідомлень на усіх етапах їх життєвого циклу;
  
• 
  забезпечення цілісності інформації та повідомлень на усіх етапах їх життєвого циклу;
  
• 
  шифрування інформації в ІТС, АС, ІС, ТС тощо в різних (десяти) режимах роботи у залежності від вимог що висуваються;
  
• 
  генерація псевдовипадкових послідовностей;
  
• 
  криптографічні протоколи автентифікації, встановлення таємниці та ключів, узгодження таємниці та ключів, розподілу таємниці тощо, коли висуваються складні вимоги до складності (швидкодії);
  
• 
  криптографічні протоколах електронного цифрового підпису тощо.
  

.

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

Симетричні криптографічні перетворення широко застосовуються практично у всіх додатках, що пов’язані з обробкою інформації. Вони реалізуються у вигляді БСШ при його застосуванні в певних режимах роботи. Особливо важливим є їх застосування в ІТС, АС, ІС, ТС при наданні послуг конфіденційності, цілісності, справжності, доступності тощо, коли висуваються складні вимоги відносно криптографічної стійкості та швидкодії. По суті уже практиці підтверджено, що основними якраз і є вимоги відносно захищенності від усіх відомих атак, гарантій відсутності вразливостей, а також забезпечення необхідної, або найвищої за певних умов швидкодії.

Тому вирішення проблеми створення найбільш ефективного стандарту сучасного БСШ, у порівнянні з існуючими БСШ, при застосуванні якого можна було б ефективно реалізувати необхідні, що уже названі вище режими роботи та забезпечити криптографічну стійкість та швидкодію є надзвичайно важливим.

На останок необхідно відмітити про особливості застосування двох термінів – блокового симетричного шифрування (БСШ) та симетричного блокового перетворення (СБП). Перше з них, тобто БСШ виникло історично, коли воно застосовувалось тільки для шифрування інформації. Але згодом на основі БСШ почали реалізовувати різні режими роботи, що названі вище. В специфікації БСШ, що розробляється, обґрунтовується також 10 різних режимів роботи БСШ. Їх у сукупності і будемо називати криптографічними СБП.

В подальшому при викладення результатів будемо посилатись та враховувати уже викладене в підрозділі 1.4.

В подальшому особливу увагу приділимо, на наш погляд перспективному СБП, що нині є національним стандартом України - ДСТУ 7624:2014. Актуальність, важливість та необхідність розробки та прийняття національного стандарту БСШ пов’язане з тим, що симетричне блокове перетворення (СБП) і на його основі розроблений проект стандарту БСШ «Калина-2» є одним із основних криптографічних механізмів забезпечення конфіденційності, цілісності та доступності інформації та ресурсів [6-14]. Симетричні блокові перетворення типу БСШ використовуються при реалізації послуг з захисту інформації, як самостійне так і у сукупності із іншими криптографічними механізмами безпеки. Дуже важливим застосуванням БСШ є тоді, коли вимагається середня чи висока швидкодія шифрування чи автентифікації інформації, а також швидкісна реалізації режимів роботи БСШ. Також важливими доказами застосування БСШ є випробувана часом їх ефективність та можливість застосування в різних, дуже необхідних, режимах роботи.

Необхідно також відмітити, що в Україні продовжує використовуватися стандарт БСШ ДСТУ ГОСТ 28147:2009, який розроблений ще у 80-х роках минулого сторіччя [12]. Особливістю БСШ ДСТУ ГОСТ 28147:2009 (ГОСТ 28147:2009) є використання стандартного довготривалого ключового елемента (ДКЕ), який, як зазначено в стандарті, поставляється в установленому порядку. Наші дослідження залежності криптографічного стійкості і можливості дешифрування криптограм третьою авторизованою стороною, що поставляє ДКЕ, по суті без знання ключа шифрування, а також формування класу шифрів, що допускають існування такої властивості, є критичним для тих хто застосовує такий БСШ. Необхідно відмітити, що вказаний, по суті регіональний шифр ГОСТ 28147:2009 вже виведений з дії в Білорусії [15] і, судячи з результатів наукових конференцій, він планується до заміни і в Російській Федерації у вигляді алгоритму «Кузнечик». Крім того, ДСТУ ГОСТ 28147:2009 (ГОСТ 28147:2009), що застосовується в Україні на сучасних обчислювальних архітектурах, має істотно меншу продуктивність, ніж діючі закордонні аналоги [13,14,17,18,9,11]. Тобто застосування ДСТУ ГОСТ 28147-89 є критичним не тільки в крипто логічному змісті, а і в політичному не має сенсу.

Таким чином, БСШ є одним з найбільш поширених криптографічних примітивів. Окрім забезпечення конфіденційності, БСШ використовуються як конструктивний елемент при побудові функцій гешування (ФГ), кодів автентифікації повідомлень (КАП), генераторів псевдовипадкових послідовностей (ГПВП) тощо.

Зважаючи на уже викладене в підрозділі 1.4, при побудуванні та аналізі СБП необхідно вирішувати такі крипто логічні наукові, системні та практичні завдання.

1. Побудування математичних моделей СБП різних рівнів деталізації.

2. Класифікація крипто аналітичних атак з урахуванням сучасних поглядів, стану, існуючих та проектуємих систем та засобів криптоаналізу.

3. Розроблення методик алгебраїчних та статистичних досліджень перспективних БСП.

4. Розроблення методів алгебраїчних та статистичних досліджень властивостей булевих функцій та S – блоків.

5. Розроблення методів оцінки стійкості СБП до можливих крипто аналітичних атак.

6. Розроблення методів оцінки періодів вихідних послідовностей перспективних СБП.

7. Розроблення методів визначення вироджених, слабких та крипто еквівалентних ключів перспективних СБП.

8. Розроблення методів розрахунку терміну дії ключа, який забезпечує необхідну криптографічну стійкість перспективних СБП в різних режимах його роботи.

9. Розроблення методів оцінки імітостійкості та завадостійкості перспективних СБП в різних режимах його роботи.

10. Розроблення методів методи статистичних досліджень процедури розгортання ключів схеми перспективних СБП.

11. Розроблення методів статистичних досліджень БСШ у відповідних режимах роботи.

В цьому розділі особлива увага звертається на вирішення проблемних задач, що вказані в пунктах 1, 2, 5, 7, 8 та частково в 9,10 та 11. Частина з указаних задач були подані в роботах [ ], їх уточнення та розв’язання наведено в НДР «Алгоритм»[ ].

В подальшому будемо також орієнтуватися та враховувати результат, що викладені в підрозділі 1.4, в тому числі:

• 
  загальні вимоги до перспективних блокових симетричних перетворень відносно криптографічній стійкості (п.1.4.2);
  
• 
  спеціальні вимоги до перспективного блокового симетричного перетворення (п.1.4.3);
  
• 
  загальну класифікацію та рекомендуємі вимоги до симетричних блокових перетворень(п.1.4.4);
  
• 
  методи оцінки криптографічної стійкості блокових симетричних перетворень (п. 14.6).
  

Також в подальшому при побудування СБП за основу приймемо концептуальний підхід чи методологічний принцип, який грунтується на SPN структурі (перш за все Rijndael, FIPS 197, Калина тощо)[ ].

4.2 Обґрунтування та основні положення математичних моделей симетричних блокових перетворень
В підрозділі 4.2 наводяться основні положення в частині математичної моделі СБП «Калина - 2», основні припущення, на яких ґрунтується математична модель СБП та розроблені математичні моделі СБП «Калина - 2» різної степені конкретизації [ ].
4.2.1 Основні положення в частині математичної моделі СБП

При побудуванні та аналізі СБП важливими та очевидно першими по важливості є завдання обґрунтування та вибору методів побудови математичних моделей, а також основні положення алгебраїчної моделі блокового симетричного шифру.

Як слідує із [23-26] математична модель – це система математичних співвідношень – формул, рівнянь, нерівностей тощо, які відображають суттєві властивості об’єкта чи явища. Математична модель дозволяє виявити найбільш характерні ознаки та особливості явища чи зневажити тими, що залишились неврахованими.

При створенні моделі, як правило, необхідно вирішити такі задач:

• 
  виділити припущення, на яких ґрунтується математична модель;
  
• 
  визначити, що необхідно вважати вхідними та вихідними даними;
  
• 
  записати математичні співвідношення, що пов’язують дані виходу з даними входу.
  

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

Процес побудови та вивчення математичних моделей називається математичним моделюванням. Зв'язок математичної моделі з реальністю здійснюється за допомогою ланцюжка гіпотез, ідеалізацій і спрощень. Під математичним моделюванням розуміють процес встановлення відповідності даному реальному об'єкту деякого математичного об'єкта, званого математичної моделлю, і дослідження цієї моделі, що дозволяє отримувати характеристики розглянутого реального об'єкта.

Згідно [26], математична модель – це «еквівалент об'єкта, що відображає в математичній формі найважливіші його властивості – закони, яким він підпорядковується, зв'язки, властиві складовим його частинам, тощо». Вона існує в тріадах «модель – алгоритм – програма». «Створивши тріаду «модель – алгоритм – програма», дослідник отримує в руки універсальний, гнучкий і недорогий інструмент, який спочатку налагоджують та тестують в пробних обчислювальних експериментах. Після того, як адекватність тріади вихідному об'єкту встановлена, з моделлю проводяться різноманітні і детальні дослідження, що дають всі необхідні якісні та кількісні властивості і характеристики об'єкта».

Аналіз показує, що усі існуючі моделі можна поділити на[25-28, 11]:

• 
  дискретні або безперервні;
  
• 
  лінійні або нелінійні моделі;
  
• 
  зосереджені або розподілені системи;
  
• 
  детерміновані або стохастичні;
  
• 
  статичні або динамічні.
  

Можливі змішані типи: в одному відношенні зосереджені (за частиною параметрів), в іншому – розподілені моделі і т.д.

За способом подання об'єкта моделі розрізняються способом представлення об'єкта у вигляді структурних або функціональних моделей. Структурні моделі представляють об'єкт як систему зі своїм улаштуванням і механізмом функціонування. Функціональні моделі не використовують таких подань і відображають тільки поведінку (функціонування ) об'єкта, що розглядається зовні. У їх граничному вираженні вони називаються також моделями «чорного ящика».

Практично завжди при математичному моделюванні спочатку будується особлива ідеальна конструкція, змістовна модель [26], інколи її називають концептуальною моделлю.

Математичне моделювання може здійснюватись засобом застосування комп'ютерної системи моделювання. Для підтримки математичного моделювання розроблено системи комп'ютерної математики , наприклад, Maple, Mathematica, Mathcad, MATLAB, VisSim тощо. Вони дозволяють створювати формальні і блокові моделі як простих, так і складних процесів і пристроїв і легко змінювати параметри моделей в ході моделювання. Блокові моделі представлені блоками (найчастіше графічними ), набір і з'єднання яких задаються діаграмою моделі.

Зважаючи на можливість та необхідність різної деталізації моделі БСШ нижче наводяться:

• 
  спрощена алгебраїчна модель симетричного шифру;
  
• 
  спрощена модель ітеративного( блокового) симетричного шифру;
  
• 
  модель марківського блокового симетричного шифру.
  

4.2.2 Спрощена алгебраїчна модель симетричного шифру

Модель симетричного блокового перетворення може бути подана у спрощеному вигляді, що може бути потрібним при узагальненому аналізі такого перетворення[6, 11, 13, 32]. Розглянемо сутність такої моделі та проведемо узагальнений аналіз.

Нехай X, K, Y – деякі кінцеві множини, які назвемо множиною відкритих текстів, множиною ключів і множиною зашифрованих повідомлень відповідно. Нехай також відносно прямого перетворення X × K множин X і K задана функція

(4.1)

Трійка множин з функцією відображення називається алгебраїчною структурою шифру, якщо виконані дві умови [11, 32]:

а) функція f сюр'єктивна, тобто кожен елемент множини X є прообразом хоча б одного елемента множини Y;

б) для будь-якого  функція ін'єктивна, тобто образи двох різних елементів різні.

Запис f(x,k)=y називається рівнянням шифрування. Мається на увазі, що відкрите повідомлення x зашифровано на ключі k, в результаті чого виходить зашифрований текст y.

Рівнянням розшифрування називають запис виду:

f ^-1(y, k) = x ⇔ f_k^-1(y) = x, (4.2)

тобто мається на увазі, що зашифрований текст y=f(x, k) розшифровується на ключі k і отримують вихідне відкрите повідомлення x.

Добутком шифрів

A₁ = (X₁,K₁,Y₁, f₁) и A₂ = (X₂,K₂,Y₂, f₂), де Y₁⊆ X₂

називають шифр

A = (X₁,K₁×K₂,Y₂,f),

для якого

f (x,(k₁,k₂)) = f (f(x,k₁),k₂), (k₁,k₂) ∈ K₁×K₂.

Дана модель шифру відображає лише деякі функціональні властивості шифрування і розшифрування симетричних шифрів, у яких ключ розшифрування дорівнює або легко обчислюється з ключа зашифрування.

Важливим параметром будь-якого шифру є ключ, що забезпечує вибір одного алгоритму криптографічного перетворення з множини можливих. У сучасній криптографії передбачається, що вся секретність криптографічного алгоритму повинна базуватися на ключі, а не на алгоритмі шифрування (принцип Кірхгофа) [6-9, 28-30].

Далі наведемо спрощену модель ітеративного (блокового симетричного шифру, яка дозволяє врахувати ітеративний характер БСШ.

4.2.3 Спрощена модель ітеративного (блокового) симетричного шифру

Розглянемо частковий випадок СБП у вигляді моделі БСШ.

Нехай функція

E :{0,1}^l×{0,1}^k {0,1}^l

приймає ключ К довжиною k біт і вхідне повідомлення (відкритий текст) M довжиною l біт і повертає зашифрований текст E(M,K) [30, 32]. Для кожного ключа K визначимо функцію

E_K: {0,1}^l×{0,1}^l як E_K(M)= E (M, K) (4.3)

Тоді E – блоковий симетричний шифр, за умови що E_K є перестановкою для будь-якого значення ключа К, а функції E_K, E_K^-1 обчислюються ефективно [6, 32].

В основі більшості сучасних БСШ лежить ітераційна процедура. На рис. 4.1 вона зображена у вигляді циклової (раундової) функції, яка робить БСШ ітеративним.

У загальному вигляді ітераційний БСШ математично представляється наступним чином:

, (4.4)

де  - циклова функція, і – функції початкового і кінцевого забілювання повідомлення відповідно [28]. Також на рис. 4.1 показано схема розгортання ключа (СРК), яка являє собою алгоритм, що генерує циклові ключі (k₁, k₂, ..., k_r+1) для всіх етапів алгоритму шифрування на основі вхідного майстер-ключа (K) [33].

Процедурою змішування ключа блокового симетричного шифру називається алгоритм, який описує кроки введення циклового ключа в алгоритм шифрування [28]. У більшості сучасних блокових симетричних шифрів в якості функції змішування ключа використовується операція виключне АБО (XOR), що обумовлено простотою її реалізації.



Рис. 4.1 - Узагальнена структура ітеративного БСШ.
Аналіз показав, що на рівні узагальненої структури сучасні БСШ повинні, як мінімум, задовольняти таким критеріям [1-13, 16-17]:

а) складність виконання операції за шифрування і розшифрування повинна бути порівнянна з діючими стандартами;

б) відсутність статистичних залежностей між шифротекстом і відкритим повідомленням;

в) відсутність статистичних залежностей між шифротекстом і ключем;

г) бути захищеним від всіх відомих на сьогоднішній день атак.

На сьогоднішній день для реалізації БСШ існує два базових перетворення: блок підстановок (S - блок) і блок перестановок (P- блок) [1-5, 11-13, 16-17].

Показано, що будь-яке двійкове перетворення над двійковим блоком фіксованої довжини, зводиться до S- блоку, але на практиці , в силу складності будови n-розрядного S-блоку при великих n, застосовують більш прості конструкції [11, 31].

Аналіз показав, що S-блок може бути представлений як дешифратор (комбінаційна схема), що перетворює n-розрядне двійкове повідомлення в одно розрядне повідомлення по підставі 2ⁿ, систему комутаторів внутрішніх з'єднань (всього з'єднань 2ⁿ!) і шифратор (комбінаційна схема), що переводить повідомлення з одно розрядного 2ⁿ-ричного в n-розрядне двійкове [34]. Аналіз n-розрядного S-блоку, при великому n вкрай складний, оскільки число можливих значень занадто велике (2ⁿ!). Але S-блок може бути і лінійним перетворенням, однак на практиці використовують нелінійні підстановки, причому меншої розрядності (2⁴, 2⁸), але як частини більш складних систем. При цьому в алгоритмі шифрування основним завданням нелінійних перетворень є перемішування біт [35].

Далі, P-блок змінює положення символів і є лінійним пристроєм [36]. Такий блок може мати дуже велику кількість входів-виходів, проте в силу лінійності систему не можна вважати крипто стійкою. Криптоаналіз відносно ключа для n-розрядного P-блоку проводиться шляхом подачі на вхід n-1 різних повідомлень, кожне з яких складається з n-1 нуля («0») і 1 одиниць («1») [37]. Головним завданням лінійних перетворень є розсіювання бітів даних при шифруванні [37, 38].

На основі наведеної спрощеної моделі можна зробити висновок, що для забезпечення шифрування в ітеративному БСШ необхідно застосовувати як S-блок (блоки) так і перестановки. Тоді застосування S-блока забезпечує перемішування біт, а перестановка Р розсіювання бітів. Тому в ряді випадків побудова БСШ можна звести до обґрунтування та вибирання нелінійних і лінійних елементів S-блоків та Р перестановок.

4.2.4 Спрощена марківська модель БСШ.

Аналіз робіт [ ] , показали, що в якості дещо детальної універсальної моделі БСШ може бути прийнята марківська модель БСШ. Тому розглянемо основні положення концепції та модель марковських БСШ [39].

Як зазначається в [39], теорія марковських шифрів визвала ряд досліджень ітеративних БСШ. Її можна розглядати як перший підхід до розробки БСШ, стійких до диференціального та лінійного криптоаналізу. По суті марківська модель БСШ є найбільш близькою до випадкових шифрів.

Марковський БСШ є ітеративним шифром [39], для якого середня ймовірність поширення ймовірності через один цикл не залежить від входу. Для таких шифрів припущення незалежності циклових підключів дозволяє обчислити середню диференційну ймовірність як добуток ймовірностей індивідуальних циклів. При цьому середня диференціальна ймовірність береться над усіма цикловими підключами, що розглядаються як незалежні значення.

Огляд публікацій відносно марковських шифрів показав, що основоположною публікацією слід вважати спільну роботу Лея, Мессі і Марфу [39] 1991 року. У цій роботі розглядається ітеративний r- цикловий шифр, яки представлений авторами у вигляді рис. 4.2, на рисунку такою наведені необхідні нам позначення.


f

f

f


Z(1) Z(2) Z(r)




f

f

f




Рис.4.2 Шифрування пари відкритих текстів в r-цикловому ітеративному шифрі

В названій роботі наведено таке визначення Марковського шифру.

Визначення 4.1 Ітеративний шифр з циклової функцією є марковським шифром, якщо є групова операція , що визначає диференціал, така, що для всіх значень и умовна ймовірність

(4.5)

є незалежною від , коли підключ являється рівномірно випадковим.

Наведемо також основоположну теорему 4.1, яка пояснює, як вказують автори [39], термінологію  марковський шифр .

Теорема 4.1. Якщо r-цикловий ітеративний шифр є марківським шифром і r циклових ключів є незалежними і рівномірно розподіленими (випадковими), то послідовність різниць є однорідним марківським ланцюгом. Більше того, такий марковський ланцюг є стаціонарним, якщо різниці є рівномірно розподіленими над ненульовими елементами групи. При цьому будемо розглядати БСШ з операцією, що визначає різниці, та розглядається як група, при чому є вхідною різницею, а  по циклові вихідні різниці.

Як приклад, в роботі [39] в якості марковського СШ наводиться шифр DES. Також вказується, що для марковського шифру з незалежними і рівномірно розподіленими (випадковими) цикловими ключами ймовірність r-циклової диференційної характеристики визначається рівнянням Чемпена - Колмогорова :

(4.6)

З цього випливає, що ймовірність r-циклового диференціалу є

(4.7)

В (4.7) суми розглядаються над усіма можливими значеннями різниць між різними елементами, тобто над усіма елементами групи, виключаючи нейтральний елемент e.

Таким чином, в теоремі 4.1 та її інтерпретації говориться про марковські БСШ з незалежними і рівномірно розподіленими (випадковими) цикловими підключами. Також необхідно зазначити, що саме поняття марковського БСШ містить зазначені вище властивості циклових підключів. Тому спеціальне зазначення незалежності та випадковості циклових ключів є, очевидно, зайвим. Тому точніше було б говорити про те, що ітеративний шифр є марковським, якщо циклові ключи є незалежними і рівномірно розподіленими.

Також важливою є гіпотеза про статистичну еквівалентність, що представлену в [ 39 ]. Таку гіпотезу про статистичну еквівалентність можна подати у такому вигляді.

Для (r1) - циклового диференціалу майже для всіх значень циклових ключів _{справедливим є таке:}

(4.8)

Використання вказаної гіпотези дозволяє обґрунтувати умови вразливості ітеративного шифру до атак диференціального криптоаналізу. Показано, що наведена гіпотеза виконується майже для всіх шифрів, які досягли стаціонарного стану.

Для цього також наведемо та проведемо аналіз теорему 4.2 [39].

Теорема 4.2. Для марковського шифру з довжиною блоку m та з незалежними і рівномірно розподіленими цикловими підключами, за умови якщо напів нескінченний марковський ланцюг має «рівномірно-стійкий ймовірнісний» розподіл, тобто існує ймовірностний вектор такий, що для всіх

, (4.9)

якщо рівномірно-стійкий розподіл є рівномірним , і

_(4.10)

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

Відмітимо, що, перша частина твердження цієї теореми потребує уточнення.

В роботі [2], також розглядаються марковські шифри. Розглянемо її результат детальніше.

Нехай згідно [40] R-цикловий шифр визначається аналітично як відображення , для якого цикл r задається функцією ; з цикловим входом, , що є ключем r-того циклу. За такої умови складання з ключем групової операції XOR () над R-цикловий шифр є марківським шифром, якщо і будь-яких справедливо

(4.11)

де X і K незалежні випадкові значення, що рівномірно розподілені над і K множина всіх незалежних ключів відповідно.

Співвідношення (4.9), як відмічається в [40], визначає ймовірність для ключа, який фіксовану вхідну відмінність перетворює в фіксовану вихідну відмінність, що не залежать від циклового входу. Також в [40] зазначається, що SPN шифри з фіксованими S-блоками є марковськими шифрами.

З наведеного можна зробити висновок, що всі підходи до опису марковських шифрів зв'язуються з рівняннями для диференціалів. Це, як показано в [ ], є не зовсім точним. В роботі [ ] наведено більш суворе обґрунтування марковського уточнення ряду принципових моментів, що пов'язані з ними.

Основою для викладення такого підходу є робота [41], що написана ще в 1978 році. У ній викладаються деякі важливі властивості дискретних і одночасно марковських процесів k-того порядку.

В роботі розглядається вибірка процесу , , що задана у вигляді послідовності вибіркових (або середніх за елементарний інтервал дискретності) значень вихідного безперервного процесу , який заданий на деякому скінченному інтервалі часу ( ). Вказується, що найбільш повною статистичною характеристикою цього процесу є багатовимірний закон розподілу ймовірностей сукупності його вибіркових значень. У роботі також наводиться визначається поняття марковського процесу k-того порядку.

Визначення 4.2. Марковським процесом k-того порядку називається процес, умовний закон розподілу ймовірностей вибіркових значень якого для кожного значення вибірки, щодо попередніх значень при будь-якому l > k залежить тільки від k попередніх значень, тобто
. (4.12)
В роботі показано, що марковський і одночасно нормальний процес математично описується стохастичним диференціальним рівнянням відповідного порядку, дискретним аналогом якого є лінійне неоднорідне різницеве рівняння з випадковою правою частиною [42]

, для l > k, , (4.13)

При чому при l ≤ k маємо початкові умови

, . (4.14)

Відмітимо, що згідно [42] в (4.14)  відлік (вибіркове значення) випадкового - корельованого процесу з нульовим математичним очікуванням і фіксованою дисперсією.

Спрощений розгляд проведемо для марковського і процесу першого порядку, тобто при k = 1), для яких
. (4.15 1.1.10)
Із роботи [41] слідує, що найпростіший марковський процес першого порядку описується стохастичним різницевим рівнянням:
, (4.16)

де (  інтервал дискретності, час кореляції процесу). У безперервному часі йому відповідає стохастичне диференційне рівняння першого порядку, що зв'язує поточне значення дискретного процесу з попереднім відліковим значенням .

Тому можна зробити таке узагальнення [ ].

Для марківського процесу першого порядку сусідні відлікові значення процесу пов'язані між собою випадковою компонентою, для Марківського процесу другого порядку три суміжних відлікових значення пов'язані між собою випадкової компонентою, а для марковського процесу k-того порядку вибірка з k+1-го сусідніх відлікових значень процесу пов'язані між собою також випадкової компонентою.

Вказане може бути основою, на якій можна ввести визначення марковських шифрів.

Для цього розглянемо більш детально SPN шифр, представлений на рис. 4.3[45].



Рис. 4.3. SPN БСШ при с N = 16, M = n = 4, и r = 3.

Наведений шифр являє собою r-циклову підстановче - перестановчу схема (SPN) і вимагає r + 1 N-бітних підключів , , . . . , , . Кожен цикл (раунд) складається з трьох шарів. У нього N-бітний вихід є сумою за модулем два з підключем відповідного циклу.

Згідно рис.4.3 блок ділиться на M під блоків розміру n (N = M_n), і кожен підблок є входом в бієктивний n×n блок підстановки (S-блок), що є бієктивним відображенням із {0,1}n в {0,1}ⁿ.

На етапі лінійного перетворення, вихід обробляється N-бітним лінійним перетворенням [11]. Таке лінійне перетворення зазвичай виключається з останнього циклу, так як легко показати, що його включення у перетворення не додає стійкості шифру. Фінальний підключ підсумовується за модулем 2, а на виході r циклу формується шифро текст. Вважається, що ті ж самі лінійні перетворення використовуються в кожному циклі. Якщо це не обумовлено іншого, то ніяких обмежень не встановлено і на вибір S-блоків.

Розшифрування виконується виконанням SPN " перетворення назад, тобто з кінця наперед". При цьому підключ спочатку складається спочатку із зашифрованим текстом, і потім у кожному r циклі (з R аж до 1-го), виконується зворотне лінійне перетворення, що супроводжуване зворотними S-блоками. Результуючий блок також складається по модулю 2 з .

Аналіз показує, що якщо БСШ додавання з цикловим підключем виділити у окреме перетворення, то одно циклове перетворення такого шифру завжди можна представити у вигляді результату виконання над входом в циклову функцію бієктивного перетворення F (проходження через S-блоки і лінійне перетворення), а також подальшого складання результату перетворення з випадковою компонентою, яка визначається цикловим під ключем. В цьому випадку блок даних на виході циклової функції буде мати вигляд:

(4.17 1.1.12)

У результаті ми приходимо до аналогу рівняння (4.16), особливістю якого є те, що в рівнянні (4.17) над цикловим входом виконується перетворення не лінійного типу, як це зроблено в рівнянні (4.16), а нелінійне бієктивне перетворення, яке здійснюється в полі. Ми маємо рівняння, що пов'язує попереднє значення входу за допомогою випадкової компоненти з поточним. Далі, якщо вважати, що ключі для циклів вибираються рівно ймовірно і незалежно, то це рівняння буде марківського процесу

Зважаючи на наведене, а також роботу [ ] можна прийняти таке визначення марківського шифру.

Визначення 4.3. Марковським шифром першого порядку є шифр, для якого співвідношення для виходу циклової функції з її входом для будь-якого значення входу і виходу визначається нелінійним рівнянням (4.17 1.1.12), в якому випадкова компонента в правій частині є ключовим значенням , вибраним незалежно і рівно ймовірно з усієї множини можливих ключів.

По аналогії можна ввести і визначення марковського шифру k-того порядку[ ].

Визначення 4.3. Марковським шифром k-того порядку називається шифр, для якого сусідні значення виходів k циклових функцій і значення входу в першу циклову функцію з цього набору пов'язані між собою нелінійно випадковою компонентою у вигляді нелінійного рівняння, що зв'язує k+1 сусідніх значень на виходах циклових функцій та містить випадкову компоненту.

У визначенні 4.3 на увазі мається рівняння, яке відрізняється нелінійним зв'язком змінних, що входять в нього.

Також необхідно встановити зв'язок наведених визначень з визначеннями, що наведені в [ ].

Так для входу в циклову функцію з , з урахуванням (4.15 ) отримаємо що
. (4.18)

У результаті для різниць (диференціалів) циклового перетворення

, ,

для одного і того ж ключового значення приходимо до рівняння
= = , (4.19 1.1.13)

де  функція циклового перетворення різниць.

Необхідно також відмітити, в [44] марковським названий шифр, у якого рівняння шифрування на одному циклі задовольняє умові: імовірність диференціалу не залежить від вибору відкритих текстів. В даному випадку якщо підключі циклів між собою незалежні, то згідно [45, 11] послідовність різниць після кожного циклу утворює марковський ланцюг, причому подальший стан визначається тільки попереднім.

В цілому на основі численних результатів проведених експериментів нині можна стверджувати, що більшість сучасних шифрів є марковськими, тобто поточне значення шифр тексту є функцією скінченного числа попередніх значень шифр текстів. Для кожного такого шифру існує невелике число початкових циклів, після якого закони розподілу переходів XOR таблиць, тобто диференціалів і зміщень таблиць лінійних апроксимацій шифру приходять до стаціонарного значення. Причому на перших циклах шифрування марковському шифру притаманний перехідний період коли шифр приходить до стаціонарного стану асимптотично.

Таким чином показано, що практично будь-який ітеративний шифр (БСШ) є марківським[ ], в тому числі SPN шифри, при м застосуванні яких в результаті зашифрування формуються марковські процеси першого порядку. Але для БСШ, що побудовані з використанням Фейстель подібних схем формування циклових функцій, процес зашифрування можна описати марковські процесом другого порядку[ ].

Крім того, для кожного ітеративного (марківського) шифру існує певне (невелике) число початкових циклів шифрування, після якого закони розподілу переходів XOR таблиць (диференціалів) і зміщень таблиць лінійних апроксимацій (лінійних корпусів) шифру приходять до стаціонарного значення. Але завжди на перших циклах шифрування для марковському шифру існує перехідний етап, тому такий ітеративний шифр приходить до стаціонарного стану асимптотично[ ].