66909

ПРИКЛАДНА КРИПТОЛОГІЯ

Лекция

Информатика, кибернетика и программирование

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

Украинкский

2014-09-01

305.66 KB

27 чел.

ПРИКЛАДНА КРИПТОЛОГІЯ

ЛЕКЦІЯ №4(2.1)

тема лекції

« ОСНОВНІ ТЕОРЕТИЧНІ ПОЛОЖЕННЯ СТІЙКОСТІ  СИМЕТРИЧНИХ КРИПТО СИСТЕМ»

Навчальні питання

4.1 Структурні схеми та моделі захищених інформаційної та інформаційно – телекомунікаційної систем

4.2  Вступ в теорію криптографічної стійкості

4.3  Умови та приклади реалізації криптосистем  з безумовним  рівнем стійкості

4.4 Умови реалізації обчислювальної та ймовірної  стійкості крипто перетворень

Додаток А Приклади розв’язку задач

1. Горбенко І.Д., Горбенко Ю.І. Прикладна криптологія. Монографія. Харків, ХНУРЕ,  Форт, 2012 р.,  1 видання, 868 с.

2. Горбенко І.Д., Горбенко Ю.І. Прикладна криптологія. Підручник. Харків, ХНУРЕ,  Форт, 2012 р.,  2  видання, 878 с.

3. Горбенко І.Д., Горбенко Ю.І. Прикладна криптологія. Електронний конспект лекцій. Харків, ХНУРЕ, 2012 р.

4. Горбенко І. Д. Гриненко Т. О. Захист інформації в інформаційно-телекомунікаційних системах: Навч. посібник. Ч.1. Криптографічний захист інформації - Харків: ХНУРЕ, 2004 - 368 с.

4.1 Структурні схеми та моделі захищених інформаційної та інформаційно – телекомунікаційної систем

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

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

 4.1.1 Структурна схема організації захищеного зв’язку.

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

На рис. 2.1 наведена спрощена структурна схема ІТС.

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

ДІ1

ДІ2

Арбітр

Порушник

(криптоаналітична система)

ОІ1

ОІ2

І Т С

1

2

3

4

5

6

7

                              Рисю2.1  Спрощена структурна схема ІТС.

Згідно схеми ІТС будемо розглядати  4 типи об’єктів[ 12, 13 ]:

1) джерела інформації (ДІ) та одержувачі інформації (ОІ( у загальному випадку користувачі));

2) інформаційно-телекомунікаційна система (ІТС);

3) сукупність порушників або зловмисників (крипто аналітична система);

4) арбітр, задача якого полягає в аналізі суперечок та підготовці матеріалів для їх  розгляду.

Порушник (Зловмисник)  у відповідності до моделі, що наведена в 2.2,  навмисно чи не навмисно реалізує погрози з метою нанесення втрат системі та або власникам , а також  користувачам.

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

- порушення конфіденційності;

- порушення цілісності;

- порушення доступності;

- порушення  неспростовності та спостережливості;

- порушення справжності (автентичності).

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

4.1.2 Структурні схеми захищеного зв’язку  в ІТС.

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

Будемо вважати, що на виході джерел інформації (у користувачів) повідомлення  Mi появляються з апріорною ймовірності  із множини nM

                                                        Р(Mi), i=1, nM   

і відомими кількість інформації, що міститься в кожному із повідомлень

                                                       ,                                                  (2.1)

а також  ентропія джерела повідомлень

                                                       ,                                    (2.2).

тобто  середня кількість інформації в повідомленні.

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

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

 

СА1

СА2

КЗ

КЗ

Рисунок  2.2 – Структурна схема захищеної ІТС

На рис. 2.2 використані такі позначення (скорочення) :

  1.  К1 та К2 - користувачі( джерела, одержувачі повідомлень) ;  
  2.  СА1, СА2 – системи (засоби автентифікації);
  3.  Ш1, Ш2 – шифратори(системи чи засоби зашифрування та  розшифрування) інформації;
  4.  КЗ1  та  КЗ2– ключові засоби( засоби зберігання та введення ключів);
  5.   Джерело ключів, що забезпечує управління ключами;
  6.  КРА (ЗЛ) – крипто аналітична система(порушник, зловмисник);
  7.  ТС(НІ, БД) – телекомунікаційна система(носій інформації, база даних).
  8.  А – арбітр, що розглядає та готую матеріали відносно суперечок між користувачами.

В наведеній ІТС КРА(ЗЛ) мають повний доступ до повідомлень, що передаються в ІТС з використанням каналів ТС. Тому для надання користувачам базових послуг здійснюється ряд криптографічних перетворень.

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

                                  ,   (2.3)

де:

          Fa  - криптографічне  перетворення  автентифікації;

          - таємний(особистий)  ключ автентифікації;

           - параметри криптографічного перетворення.

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

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

                                     (2.4)

Де:

          Fзш  - криптографічне  перетворення  зашифрування;

          - ключ зашифрування захищеного повідомлення ;

           - параметри криптографічного перетворення зашифрування;

         Сі –  зашифроване повідомлення (криптограма).

По суті шифратор  Ш1 є джерелом криптограм. Для конкретно вибраного шифру можна визначити безумовну апріорну статистику появи на виході шифратора криптограм  

                                Р(Сi), i=1, nС

із повної множини  nС .Також можна говорити і про ентропію джерела криптограм  H( Ci).

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

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

На приймальній стороні при розшифруванні виконуються зворотні криптографічні перетворення  - розшифрування     Fрш  та автентифікації( перевірки цілісності та справжності). Спочатку виконується розшифровування криптограми  Сі*

                               ,    (2.5)

         де:

         Fрш  - криптографічне  перетворення  роз шифрування;

          - ключ розшифрування криптограмм  Сі*

           - параметри криптографічного перетворення розшифрування;

           –  розшифроване захищене повідомлення.

Далі повідомлення перевіряється в системі автентифікації  CA2  на цілісність та справжність  засобом виконання зворотного  криптографічного перетворення    автентифікації

                                                       (2.6)

де:

          F зa  - зворотне криптографічне  перетворення  автентифікації;

          - таємний (відкритий )  ключ перевірки автентичності (автентифікації);

           - параметри зворотного  криптографічного  перетворення  автентифікації.

            - розшифроване та перевірене на цілісність і справжність повідомлення( можливо з помилками і тому з великою ймовірністю буде відкинутим).

Таким чином, прямі  перетворення (2.3) та (2.4),  а також зворотні (2.5)  і ( .6)  є  криптографічними,  тобто здійснюються за допомогою ключових даних (ключів).

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

Елементами системи управління ключами є джерело ключів  ДК та ключові засоби КЗ.

4.1.3 Особливості застосування криптографічного захисту  в ІС.

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

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

                

   Рис.2.3 Структурна схема захищеної  ізольованої ІС.

Відмінність інформаційного захищеного обміну, що наведено на рис. 2.3 від 2.2 в тому що при необхідності криптограми зчитуються з носія і користувач, по суті К1, виконує звороті перетворення , як це виконувалось користувачем К2 згідно рис. 2.2. Після розшифрування  та перевірки на автентичність (цілісність, справжність)  повідомлення (інформація)  Мi  відновлюється у відкритому вигляді.

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

                            

                          4.2  Вступ в теорію криптографічної стійкості

   В розділах 7 та 8 достатньо детально викладаються питання крипто аналізу відносно симетричних та асиметричних крипто перетворень. В цьому розділі ми наведемо тільки початкові формалізовані відомості відносно оцінки криптографічної стійкості криптографічних перетворень, що будемо використано при викладенні теоретичних та практичних питань криптографії в 2 – 4 розділах. Розпочнемо розгляд для випадків, коли в ІС чи ІТС потрібно забезпечити конфіденційність , ґрунтуючись на положення теорії Кл. Шеннона.  

 

   4.2.1  Ймовірнісні -   інформаційні моделі ІС та ІТС.

 В ІС та ІТС , структурні схеми яких наведені  на рис. 2.2 та 2.3, порушник (крипто аналітик) може ставити такі задачі:  

1) визначити яке повідомлення Мi  міститься в криптограмі C i;

2) визначити, який  K j ключ чи пара довгострокового  Kд j та сеансового ключів  Kс   j, були використані при шифруванні інформації.

При проведенні  крипто аналізу будемо вважати, що крипто аналітик знає все про ІС чи ІТС  - апріорну статистику появи повідомлень та криптограм, режими роботи, загальні характеристики тощо.  Він знаходиться в апріорній невизначеності тільки відносно таємного ключа Kj чи таємних ключів (Kд j ,  Kс ), що застосовуються.

В найбільш простому випадку для знаходження повідомлення  крипто аналітик може вирішувати задачу побудови апостеріорного ряду[1 ]    

     

                  ,                                       (2.7)

В випадку (2.7) необхідно побудувати апостеріорний ряд розміром  nm  * nc, що у більшості практичних випадків із – за великого розміру задачі, зробити неможливо.

Апріорну невизначеність крипто аналітика відносно повідомлення Мі, яке  міститься в криптограмі Сі можна задати через умовну ентропію    H(M/C) . Як показано в [ 1, 11,13 ]  таку ентропію можна обчислити як:

 

                              (2.8)

В результаті виконання крипто аналізу невизначеність крипто аналітика  H( M/C) зменшується, тобто   крипто аналітик отримує в результаті крипто аналізу  від джерела інформації  кількість інформації яку можна оцінити як

                                         (2.9)

Важливими є граничні оцінки :

  1.  якщо H( M/C) =0  то ;                                                                 (2.10)
  2.  якщо то  .                                                                 (2.11)

В реальних ситуаціях апостеріорна ентропія визначається  як

                                                                                             ( 2.12)

Зрозуміло, що у випадку ( 2.10)  крипто аналітик успішно вирішує  задачу крипто аналізу, а у випадку ( 2.11) не має такої можливості, оскільки він не отримав ніякої інформації відносно джерела інформації.

При вирішенні другої задачі , тобто спробі визначити, який  Kj ключ чи пара  ключів

( Kд j,   Kс j), були використані при шифруванні інформації, необхідно вибрати та використати ряд показників джерела ключів.

4.2.2 Основні показники оцінки  якості шифрів

Не претендуючи на повноту, виберемо в якості основних показників такі  як:
- розмір простору ключів
N k ,  тобто число ключів що можуть застосовуватись;

- ентропія джерела ключів  H(К)  ;

- безпечний час ( математичне сподівання часу визначення ключа) ;

- потужність крипто аналітичної системи  γ;

-  ймовірність успішного вирішення задачі крипто аналізу Р у ; 

- відстань єдності шифру l0 .

Інші показники  та критерії будуть вводитись та застосовуватись в міру необхідності.

Ентропію джерела ключів будемо визначати як

                         ,    (2.13)

де Р(Кi) - імовірність появи Кi  ключа в системі.

Безпечний час tб будемо визначати як математичне сподівання часу розкриття криптосистеми, наприклад знаходження таємного ключа,  із використанням конкретного методу:

                                ,                                                             (2.14)

де:

  1.  N г – кількість групових операцій, які повинен виконати (розглянути) крипто аналітик;
  2.  γ – потужність крипто аналітичної системи (варіантів за секунду - в/c);
  3.  К – кількість секунд у році – приблизно 3.15  107(с/рік)
  4.  Р у  ймовірність успішного розкриття ;
  5.  l0- відстань єдності шифру.

Більш детально відстань єдності буде розглянута нижче.

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

    

                          (   N k , H(К) , , γ, Р у, l0 )                                                          (2.15)                                                 

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

4.2.3  Класифікація криптосистем по стійкості.

На наш погляд, в  залежності від складності задачі крипто аналізу, шифри по криптографічній стійкості можна поділити на чотири такі класи:

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

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

3) ймовірно стійкі, доведення стійкості відносно яких зводиться до вирішення математичної або математичних задач, складність вирішення яких не доведена ;

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

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

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

                                                                                                               (2.16)         

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

                                                                                                                  (2.17)

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

                                       

                                                                                                                  (2.18)   

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

                                                                                                                   (2.19)     

На наш погляд,  запропонована класифікація дозволяє практично оцінити та порівняти криптосистеми та крипто перетворення.

4.3   Умови та приклади реалізації криптосистем  з безумовним  рівнем стійкості

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

Розгляд та умови реалізації розпочнемо криптосистем розпочнемо у відповідності з рівнями гарантій стійкості.

4.3.1 Умови реалізації безумовно стійких криптосистем.

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

Теорема 2.5.1  Необхідною і достатньою умовами забезпечення безумовної стійкості є:

,     (2.20)   

тобто імовірність появи Сj криптограми на виході шифратора не повинно залежати від того, яке Мі повідомлення з’явилось на виході джерела повідомлення. Інакше, ймовірність появлення криптограми повинно бути однаковою для всіх ключів і для всіх повідомлень. Це означає, що будь-яке повідомлення може зашифровуватись  в будь-яку криптограму з однаковою ймовірністю.

Доведення. Визначимо апостеріорну імовірність ,  яку  може обчислити порушник (крипто аналітик), знаючи апріорні ймовірності  ,   та , використовуючи  відому теорему теорії ймовірності та математичної статистики, в нашому випадку співвідношення (2.7)

                                          .    (2.21)

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

                                               ,                                        (2.22)

Дійсно, в цьому випадку згідно (2.11)

                                                                                                              (2.23).  

Підставивши (2.22) в (2.23) отримаємо що

                                                                     (2.24)

Теорему доведено для загальних умов.

4.3. 2 Приклади реалізації безумовно стійкої криптосистеми.

Криптографічні системи для яких виконується ця умова і є безумовно стійкими[1, 2,11,13]. Прикладом реалізації такої системи є система Вернама.  У цій системі здійснюється потокове шифрування, тобто символи криптограми в шифраторі зашифруються за правилом:

                                                      ,                                       (2.25)

де Мi – i-й символ повідомлення , , а Кі – і-й символ ключа, Сі - i-й символ криптограми, m – розмір алфавіту, що використовується.

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

                                                        .                                                   (2.26)

Розшифрування в системі Вернама здійснюється згідно з правилом

                                            .   (2.27)

Аналіз (2.25) і (2.27) показує, що для зашифрування і розшифрування потрібно використовувати однакову випадкову послідовність (ключ).

Можна показати, що для системи, яка розглядається, умовна ентропія [7]:

                                             ,  (2.28)

де l – довжина криптограми, d – надмірність алфавіту повідомлень.

Визначимо умову, при якій реалізується безумовна стійкість, тобто знайдемо число символів криптограми, при якому не можна здійснити крипто аналіз.

Задача крипто аналізу може бути розв’язана, коли:

                                                    .

Тоді із (2.28) випливає, що

                                                    .                          (2.29 )

Розв’язавши рівняння (2.29) отримаємо, що відстань єдності l0 визначається як

                                                     .     (2.30)

Фізично параметр l0 означає мінімальну кількість символів криптограми при правильному отриманні яких можна сподіватися на успішний крипто аналіз. Якщо l<l0, то система безумовно стійка. Це друга умова реалізації безумовно стійкої системи.

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

                                               .    (2.31)

Найкращий випадок, якщо .

Використовуючи функції ненадійності Шеннона [7]:

                                             ,    (2.32)

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

   Для деякого класу лінійних (групових) шифрів, у яких використовуються природні мови (російська, англійська, С++, графіка)  Кл. Шеннон отримав розв’язок рівняння (2.28),  якщо

                                           

                                               ,

                                      ,  (2.33)

                                                         (2.34)

і апостеріорна ентропія визначається через умовну апостеріорну імовірність ,

то

,              (2.35)

,              (2.36)

.

Далі можна розрахувати за (2.35), знаючи статистики Р(Сj) і .

Надмірність d визначається залежністю символів мови між собою та різними ймовірностями появи їх в тексті. Вона може бути визначена, як

                                           ,                                               (2.37)

де Н0(М) – ентропія мови, де всі символи порівняно ймовірні і незалежні.

Якщо

                         ,        (2.38)

то

                             ,                    (2.39)

тому

                            .                         (2.40)

Використовуючи рівняння (2.34), маємо для мови з m алфавітом

                                      .                                                               (2.41)

Для двійкового алфавіту (m=2)

                                     .                                                                      (2.42)

4.4 Умови реалізації обчислювальної та ймовірної  стійкості крипто перетворень

4.4.1 Умови здійснення крипто аналізу

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

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

Нагадаємо, що завданням крипто аналізу є відновлення відкритого тексту без знання ключа або частини ключа, а також визначення самого  ключа. Кожну спробу здійснення крипто аналізу називають атакою.

Фундаментальне припущення відносно крипто аналізу вперше було висловлено ще в 19 столітті датчанином А. Керкхоффсом, яке полягає в тому,  що таємність інформації( повідомлення ), що зашифровується в повній мірі повинна залежати тільки  від ключа. Інакше, стійкість криптограми ґрунтується на конфіденційності ключа. При цьому Керкхоффс виходив із допущення, що крипто аналітик має всю необхідну інформацію відносно опису криптографічної системи та засобів її реалізації. Якраз в цих умовах повинне забезпечуватись задекларований рівень криптографічно стійкості.  Якщо крипто аналітик не в змозі здійснити успішно крипто аналіз в умовах повних знань,  то  зрозуміло, що  в умовах апріорної невизначеності тим паче він не зможе успішно здійснити атаку.

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

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

Задано:

                    С1 = Е к( М1), С2 = Е к( М2), …, Сi = Е к( Мi).                                           (2.55)

Необхідно визначити : повідомлення  М1, М2….., Мi , а краще ключ К, а значить алгоритм визначення

                     Мi+1   із  Сi+1 = Е к( Мi+1).                                                                            (2.56)

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

Задано:   

                        М1, С1 = Е к( М1);  М2, С2 = Е к( М2); …, Мi , Сi = Е к( Мi).                     (2.57)

Необхідно визначити : ключ К чи алгоритм визначення  

                         Мi+1   із  Сi+1 = Е к( Мi+1)                                                                            (2.58)

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

Задано:  

                           М1, С1 = Е к( М1);  М2, С2 = Е к( М2); …, Мi , Сi = Е к( Мi),                     (2.59)

причому крипто аналітик може вибирати  М1,, . М2, …, Мi .

Необхідно визначити : ключ К чи алгоритм визначення

                             Мi+1   із  Сi+1 = Е к( Мi+1)                                                                            (2.60).

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

Задано:  

                               М1, С1 = Е к( М1);  М2, С2 = Е к( М2); …, Мi , Сi = Е к( Мi),                   (2.61)

причому крипто аналітик може вибирати  М1,, . М2, …, Мi .

Мається доступ до  М1, С1 = Е к( М1); На основі отриманих даних вибирається  М2, С2 = Е к( М2); …,  На основі отриманих даних вибирається  Мi , Сi = Е к( Мi).

Необхідно визначити  ключ К чи алгоритм визначення

                                 Мi+1   із  Сi+1 = Е к( Мi+1)                                                                         (2.62).

5)Атака на основі підібраного  шифро тексу. При здійсненні цієї атаки крипто аналітик може вибирати  шифро тексти Сi = Е к( Мi) та використовуючи засіб з введеним в нього ключем К,  розшифровувати вибрані шифро тексти, тобто отримувати Мi . Особливість цієї атаки в тому, що крипто аналітик  має засіб розшифрування з введеним в нього ключем, але ключ йому не доступний ніяким чином. Визначений ключ ( ключі) крипто аналітик може використати для дешифрування інших шифро текстів, які отримані з застосуванням  цього ключа( цих ключів). В даному випадку атака проводиться таким чином.

Задано:  

С1, М1 = D к( C1);  C2, M 2 = D к( C2); …, Ci , Mi = D к( Мi),                                                   (2.63)

причому крипто аналітик може вибирати  D 1, . D2, …, D i .

Необхідно визначити : ключ К, що міститься  в засобі в недоступній формі.

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

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

7) Грабіжницький  «аналіз». В цьому випадку ключ( ключі) отримуються на основі використання агентури, шантажу власників ключів, їх підкупу, застосування торту тощо. Враховуючи велику обчислювальну складність атак 1) -6) метод грабіжницького аналізу найбільш ефективний та  реальний.

4.4.2 Визначення обчислювально стійкої криптосистеми та умови реалізації

 Згідно ( 2.17) під обчислювально стійкими  криптосистеми (шифрами)  будемо вважати такі, відносно яких складність крипто аналізу   носить  експоненційний характер   і  значення безпечного часу на багато більше часу цінності інформації, тобто  

                                                                                                                  

В ряді випадків обчислювально стійкі криптосистеми( шифри) називають шифрами з гарантованою крипто стійкістю. Прикладами таких шифрів є блокові та потокові симетричні шифри. Розглянемо умови реалізації обчислювально стійкої криптосистеми на прикладі застосування симетричних шифрів.  У обчислювально  стійких криптосистемах замість ключової послідовності К i, що використовується в безумовно стійких шифрах, використовують спеціальним чином генеровану гаму шифрування  Гi. Правило зашифрування  зводиться ло складання символів повідомлення та гами зашифрування за певним модулем m та має вигляд

                                                                  (2.64)

                                               ,                                (2.65)

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

Розшифровування шифротексту   здійснюється за правилом

                                                          (2.66)

Основними умовами забезпечення обчислювальної стійкі  є такі [ 2, 4 - 7 ].

  1.  Гама   повинна генеруватись спеціальними засобами – генераторами гами .
  2.  Символи гами повинні генеруватись випадково, рівно ймовірно, незалежно та одно рідно.
  3.  Період повторення гами  повинен бути не менше допустимої величини lд, тобто

                                                        (2.67)

  1.  Закон формування гами повинен забезпечувати „ секретність ” гами, тобто непередбачуваність .  Цю вимогу можна звести до вимоги, що складність обернення рівняння (2.65), тобто знаходження  ключа

                                                       (2.68)

повинна носити експоненційний характер.

Відмітимо Що в  якості показника оцінки складності гами можна використовувати поняття її структурної  скритності, наприклад у вигляді

                                      ,                                                                            (2.69)

де   l н число символів гами, які потрібно знати для розкриття тих що залишились, тобто  lп -    lн.  При цьому найкращою  буде гама ,  для  якої , а значить на основі (2.69) Sc 1.

  1.  Відновлюваність гами в просторі та часі, тобто наявності можливості генерувати ідентичні гами на різних станціях та в різний час.
  2.  Забезпечення допустимого рівня появи колізій, тобто ідентичних відрізків гами.
  3.  Допустима складність (швидкодія) генерування гами в просторі  та часі тощо

Необхідно відмітити, що у більшості  випадків здійснюють двійкове шифрування, тобто за модулем 2. За даних умов правила шифрування (2.64) та (2.65) мають такий вигляд

                                               ,                    (2.70)

                                                .                     (2.71)

Для оцінки  стійкості обчислювально стійкої криптосистеми можна використовувати  показники, що введені в ( 2.4.2)  кортеж параметрів (2.15) -  (   N k , H(К) , , γ, Р у, l0 )                                                          

4.4.3  Визначення та умови реалізації ймовірно стійкої криптосистеми (шифру)

            

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

                                                                                                                          (2.72)

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

                                                                                                                     (2.73)

В асиметричні криптосистемі один  із ключів асиметричної пари є таємним(особистим), а інший відкритим.

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

  1.  Шифрування( зашифрування,  розшифрування )  здійснюється на основі асиметричного алгоритму  та використання   асиметричної пари ключів.
  2.  Асиметрична пара ключів складається, як мінімум, з особистого  К о, ( таємного) та відкритого   Кв ключів.
  3.   Направлене зашифрування  здійснюється з використанням відкритого ключа  Кв.
  4.  Розшифрування використовується з використанням особистого ключа.
  5.  Особистий та відкритий ключі є взаємозалежними і існують алгоритми визначення одного із ключів по відомому іншому.
  6.  При реалізації асиметричного шифрування повинні застосовуватись загальні параметри криптографічних перетворень , але такі що складність відомих атак повинна мати не нижче за суб експоненційну.
  7.   Асиметричне криптографічне перетворення повинне дозволяти реалізацію моделі взаємної недовіри  та взаємного захисту.
  8.  Асиметрична ключова пара, як правило, повинна генеруватись власником цієї пари ключів.
  9.  Усі алгоритми та засоби криптографічних перетворень повинні забезпечувати цілісність та справжність загальних параметрів та ключів.

Інформаційні структури , що використовують асиметричні крипто перетворення  отримали назву інфраструктур відкритого ключа[ 5,6,12, 31]. Вони мають достатньо значиму історію розроблення, створення та розвитку. Перші роботи в цьому напрямку стали актуальними після винаходу асиметричних криптографічних перетворень. Розроблено  значне число асиметричних криптографічних систем. Їх принциповою особливістю є те, що при виконанні криптографічних перетворень в них використовується одна або декілька асиметричних пар ключів[4 – 6, 11- 13]. Нині також розглядаються ряд перспективних напрямів, що пов’язані перш за все із застосуванням криптографічних перетворень на ідентифікаторах зі спарюванням точок еліптичних кривих і на гіпереліптичних кривих. Можливість та умови застосування вказаних перетворень вивчені теоретично, створені та випробовуються дослідні версії, розроблено рекомендації та обговорюється необхідність створення регіональних і міжнародних стандартів. Буквально в 2010 році  значну дорогу пробили собі криптографічні перетворення типу шифрування , що ґрунтуються на перетвореннях в урізаних кільцях поліномів, які знайшли своє закріплення в стандарті ANSI США Х 9.98 [163 - 167]. У таблиці 1   наведено основні асиметричні крипто перетворення, що застосовуються або можуть застосовуватись для таких криптографічних перетворень як направлене шифрування, як (електронний) цифровий підпис, узгодження ключів тощо .  Як випливає з таблиці 2.2, в якості (сертифіката) відкритого ключа направленого шифрування  в RSA системі використовується відкритий Ei ключ із* асиметричної пари ключа (Di, Ei), а в якості особистого   ( таємного ) ключ  Di.

Для асиметричного криптографічного перетворення в полі Галуа як (сертифікат) відкритого ключа направленого шифрування  використовується елемент поля Yi, а як особистий ключ – ціле число Хi. 

                               Таблиця 2.2

Асиметричні криптографічні перетворення для ЕЦП

Параметри перетворення /

Вид перетворення

Особи

стий ключ

Відкритий ключ (сертифікат)

Асиметрична пара (ключ)

Загальні параметри

Сертифікати

Складність крипто

аналізу

Перетворення в кільці (RSA)

Di

Ei

(Ei, Di)

N = PQ

Ei

Субекспоненційна

Перетворення в полі Галуа F(P) (DSA)

Хi

Yi=

gXi(mod P)

(Xi, Yi)

P, q, g

Yi

Субекспоненційна

Перетворення в групі точок еліптичних кривих Е(F(q))

di

Qi=

diG(modq)

(di, Qi)

a, b, G, n, f(x)(P), h

Qi

Експоненційна

Перетворення в гіпереліптичних кривих

Сi

D2= ciD1

(ci, D2)

f(x), g(x), q, D1, g, J

D2

Експоненційна

Перетворення зі спарюванням точок еліптичних кривих

Di  =

s QiD

QiD = H1(ID)

(diD, QiD)

G1, G2, e, H1, P, H2, H3,

F2m, Pp

QiD

Міжекспоненційна – субекспоненційна

Для асиметричного криптографічного перетворення в групі точок еліптичних кривих як сертифікат відкритого ключа направленого шифрування  використовується точка еліптичної кривої Qi, а як особистий ключ електронного цифрового підпису – ціле число di. При застосуванні криптографічного перетворення на гіпереліптичних кривих як сертифікат відкритого ключа використовується якобіан D2, а як особистий ключ – якобіан D1. При застосуванні криптографічного перетворення зі спарюванням точок еліптичних кривих як сертифікат відкритого ключа направленого шифрування  використовується  ключ QiD, а як особистий ключ – diD.

Особливий інтерес нині мають ІВК, що ґрунтуються на криптографічних перетвореннях в кільці урізаних поліномів[165 ]. Основною перевагою цього алгоритму є те, що він працює набагато швидше звичайних алгоритмів направленого шифрування з відкритим ключем, наприклад таких як RSA. Перевага у швидкості є особливо великою в генерації ключів, яке найчастіше є найбільш важливою частиною у криптографії з відкритим ключем.

Детально класифікація та математичні моделі асиметричних крипто перетворень, що подані в таблиці наведені в 3 розділі монографії.

Додаток А

4.3.3 Приклади розв’язку задач оцінки стійкості

Приклад 1. Знайти l0 для безумовно стійкого шифру. В результаті маємо

.

Враховуючи, що

та ,

маємо

                                ,                                  (2.43)

коли та

                                                                                           (2.44)

коли .

Таким чином, для безумовно стійкої системи l0 не менше довжини повідомлення, і не менше довжини ключа, оскільки d<1. Тому для успішного крипто аналізу крипто аналітик повинен отримати не менш ніж lк символів, тобто весь ключ.

Можна показати, що іншою умовою забезпечення безумовної стійкості є:

.

Покладемо, що , тоді

                  ,                                                   (2.45)

                  ,                                                 (2.46)

де Nk – кількість ключів, NM – кількість повідомлень.

Імовірності появи Кі ключа і Мі повідомлення є

,

,

тому

,

,

.                                           (2.47)

В результаті отримаємо

      .                                                           (2.48)

  Приклад 2. Знайти l0 для реального повідомлення (мова українська), за умови, що джерело ключів містить:

, d=0,4.

В результаті маємо

,

біт.

Приклад 3. Знайти l0 для безумовно стійкого шифру. В результаті маємо

.

Враховуючи, що

                                           та ,

маємо

                                           ,     (2.49)

коли та

                                                                                                             (2.50)

коли .

Таким чином, для безумовно стійкої системи l0 не менше довжини повідомлення, і не менше довжини ключа, оскільки d<1. Тому для успішного крипто аналізу крипто аналітик повинен отримати не менш ніж символів, тобто весь ключ.

Можна показати, що іншою умовою забезпечення безумовної стійкості є:

.

Покладемо, що , тоді

                                         ,                                                   (2.51)

                                         ,                                                  (2.52)

   де Nk – кількість ключів, NM – кількість повідомлень.

Імовірності появи Кі ключа і Мі повідомлення є

                                        ,

                                         ,

тому

                                       ,

                                       ,

                            .                                           (2.53)

В результаті отримаємо

                                             .                                                     (2.54)

Приклад 4. Визначити кількість символів ключа (обсяг ключів), які потрібно розіслати користувачам  К1 і К2, зв'язаних між собою каналом зі швидкістю V=2Мг біт/с, якщо вони працюють протягом року безупинно, а на носій інформації записується 5*109 бітів.

Довжина повідомлення

.

Число дисків, на які можна записати 5*109 інформації

.

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

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


 

А также другие работы, которые могут Вас заинтересовать

63644. СОВРЕМЕННАЯ ЗАПАДНАЯ ФИЛОСОФИЯ 241.5 KB
  Далее вспомним Юма утверждавшего что действительность для человека поток его ощущений; кантовскую критику разума по которой мы видим не то что есть а только то что можем видеть в силу своего устройства; странное положение Фихте весь мир это Я преломляющее реальность...
63645. Русская философия. Конец ХVIII – начало ХIХ веков 165 KB
  Одна из основных проблем его философии концепция бытия и человека в нем. Таким образом Чаадаев по существу утверждает иррациональность бытия человека. К философии истории тесно примыкает концепция человека. Однако раздвоенность природы человека обусловила трагизм его положения.
63646. Evolution of views on the role of state in the market economy 144.5 KB
  Became a base for development of now industrialized countries, played a key role in mixed economy formation. Appeared in the wake of Great Depression in the USA. State should actively interfere in the economy because free market does not posses mechanisms to help the economy struggle out from crisis.
63647. Теоретические проблемы периодизации развития Российского государства 82.1 KB
  С момента своего возникновения и до конца XIX века ведущую роль в системе политической власти играл класс феодалов основной собственник земли с постепенно закрепленными на ней крестьянами. Этот период делят на следующие этапы: а Раннефеодальное государство с VIII до середины XV века.
63649. УПРАВЛİННЯ ФİНАНСОВИМИ РИЗИКАМИ 420.02 KB
  Ризики у фінансово-господарській діяльності суб’єктів господарювання Ефективне забезпечення моделі управління фінансовими ризиками передбачає зокрема вирішення таких проблемних питань: аналіз умов виникнення і формування комерційних ризиків...
63652. ГОСУДАРСТВЕННЫЙ И МУНИЦИПАЛЬНЫЙ КРЕДИТ 53 KB
  Государственный и муниципальный кредит – это совокупность экономических отношений между государствами в лице его органов власти и управления, с одной стороны, и физическими и юридическими лицами - с другой, при которых государство выступает в качестве заемщика, кредитора и гаранта.