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

Таблиця 1.9

Блок S6

Таблиця 1.10

Блок S7

Таблиця 1.11

Блок S8

4. Вихід С = С1 С2 … С8 перемішується фіксованою підстановкою Р2.

Таблиця 1.12

Підстановка Р2.

Розклад ключів.

1. У 64-бітовому ключі К усуваються біти 8, 16..., 64. Біти, що залишилися, перемішуються підстановкою Р3.

Таблиця 1.13

Підстановка Р3

Вихід Р3(К) представляється у вигляді Р3(К) = С0D0, де С0 - ліва половина D0 - права.

2. Чергове значення СіDі обчислюється по схемі

Сi = Li(Сi-1), Di = Li(Di-1),

де Li - циклічне зрушення вліво на одну позицію, якщо i = 1, 2, 9, 16. У решті випадків Li - зрушення вліво на дві позиції.

3. На цьому етапі вихід перемішується підстановкою Р4.

Таблиця 1.14

Підстановка Р4

Дешифрування DES.

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

DES дозволяє використовувати для шифрування або дешифрування блоку одну і ту ж функцію. Єдина відмінність полягає в тому, що ключі повинні використовуватися в зворотному порядку. Тобто, якщо на етапах шифрування використовувалися ключі К1, К2, К3, ..., K16, то ключами дешифрування будуть K16, K15, K14, ..., К1. Алгоритм, який створює ключ для кожного етапу, також циклічний. Ключ зрушується направо, а число позицій зрушення рівне 0, 1,2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1.

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

Система RSA використовується як для шифрування, так і для підпису.

Вона базується на односторонній функції з «лазівкою» (trapdoor function).

Ця система базується на наступних двох фактах з теорії чисел:

1) задача перевірки числа на простоту є порівняно легким;

2) задача розкладання чисел виду п = pq (р і q - прості числа) на множники є дуже важкою, якщо ми знаємо тільки п, а р і q - великі числа (це так зване завдання факторизації).

Виберемо p і q - великі прості числа. Хай модуль n = pq, функція (n) = (p-1)(q-1) - функція Ейлера. Візьмемо довільне 1 е(n) таке, що
НОД(е, (n)) = 1. Тоді існує єдине 1 d (n) таке, що

ed(mod(n)) = 1. (1.1)

Система шифрування RSA - це система з відкритим ключем, де
е - відкритий, а d - секретний ключі, п - відоме. Якщо 0 x<n - це відкрите повідомлення, то криптограма отримується таким чином:

С = х(mod n).

Сторона, що отримала зашифроване повідомлення обчислює

х' = Сd (mod n), причому х' = х.

Доказ:

х' = Сd (mod n) = хed (mod n)

Рівність (1.2.1) означає, що для деякого k

ed = k(n) + 1.

Звідси і iз теореми Ейлера слідує

x' = xkц(n) + 1 (mod n) = x.

Те, що і потрібно було довести.

Розглянемо властивості системи RSA

1) Система шифрує і дешифрує інформацію коректно;

2) Зловмисник, що перехоплює всі повідомлення і що знає всю відкриту інформацію, не зможе знайти початкове повідомлення при великих р і q. Це пояснюється тим, що зловмисник знає тільки відкриті параметри n і e. Для того, щоб знайти d, він повинен знати значення (n) = (p - l)(q - 1), а для цього, у свою чергу, йому потрібно знати p і q. Взагалі кажучи, він може знайти p і q, розклавши n на множники, проте це важке завдання.

Одностороння функція у = xе (mod n), що використовується в системі RSA, володіє так званою «лазівкою», що дозволяє легко обчислити зворотну функцію х = (mod n), якщо відоме розкладання n на прості множники. (Дійсно, легко обчислити (n) = (p - 1)(q - 1), а потім d = e-1 (mod (n))) Якщо р і q невідомі, то обчислення значення зворотної функції практично неможливе, а знайти p і q по n дуже важко, тобто знання p і q - це «лазівка» або «потайний хід»). Такі односторонні функції з лазівкою знаходять застосування і в інших розділах криптографії.

Відзначимо, що для схеми RSA важливо, щоб кожен абонент вибирав власну пару простих чисел p і q, тобто всі модулі n для кожного учасника повинні бути різні (інакше один абонент міг би читати зашифровані повідомлення, призначені для іншого абонента). Проте цього не вимагається від другого відкритого параметра е. Параметр е може бути однаковим у всіх абонентів. Часто рекомендується вибирати е = 3 . Тоді шифрування виконується максимально швидко, всього за два множення.

Підпис RSA.

Хай М - повідомлення, яке треба підписати. Підпис отримується за наступним алгоритмом:

С = М(mod n),

тоді (М, С) - повідомлення з підписом. Перевірка підпису здійснюється таким чином

С( mod n) = М(mod n) = М'.

Якщо М = М', то підпис вірний.

1.3. Методика визначення стійкості криптосистем

Є декілька різних критеріїв, які можна було б використовувати для оцінки якості пропонованої секретної системи. Розглянемо найбільш важливі з цих критеріїв.

1. Кількість секретності.

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

2. Об'єм ключа.

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

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

4. Розростання числа помилок.

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

5. Збільшення об'єму повідомлення.

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

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

Питання про теоретичну стійкість шифрів вперше було сформульоване Клодом Шенноном: «Наскільки надійна криптосистема, якщо криптоаналітик супротивника має в своєму розпорядженні необмежений час і всі необхідні засоби для аналізу криптограм?». З цим питанням тісно зв'язане наступне питання: «Чи існують шифри, які не міг би розкрити криптоаналітик, що має в своєму розпорядженні скільки завгодно велику криптограму і необмежені обчислювальні ресурси?».

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

Рисх(а) = Рисх/ш(а/у) (1.2)

за умови, що Ру(у)>0, де

Рисх(а) - розподіл імовірності на множині відкритих текстів;

Рисх/ш(а/у) - сумісний розподіл імовірності на множині пар відкритих і шифрованих текстів;

Ру(у) - розподіл імовірності на множині шифрованих текстів.

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

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

Системний підхід.

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

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

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

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

Однією з основних характеристик практичної стійкості шифру Е є середня трудомісткість ТЕ дешифрування, яка визначається виразом

ТЕ =Т(). (1.3)

При цьому важливо відзначити наступне:

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

Якщо надійність алгоритму дешифрування мала, то з погляду криптографа він є безпечним, а з погляду криптоаналітика неефективним. Таким чином, при отриманні оцінки (1.3.2) величини ТЕ доцільно розглядати лише ті алгоритми дешифрування, надійність яких достатньо велика. При цьому для визначення «найкращого» алгоритму дешифрування системи Е можна використовувати різні критерії залежно від конкретних умов завдання. Наприклад, можна вважати «найкращим» алгоритм дешифрування , для якого найменше значення приймає величина T()/(). Цю величину можна інтерпретувати як середні трудовитрати, необхідні для успішного дешифрування шифрсистеми.

2. Складність дешифрування залежить від кількісних і якісних характеристик криптограм, які має в своєму розпорядженні криптоаналітик. Кількісні характеристики визначаються числом перехоплених криптограм і їх довжинами. Якісні характеристики пов'язані з достовірністю перехоплених криптограм (наявність спотворень, пропусків і т. д.).

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

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

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

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

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

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

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

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

Асимптотичний аналіз стійкості.

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

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

Оцінка кількості необхідного шифрматериалу.

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

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

Як приклад такого шифру розглянемо шифр Діффі. У цьому шифрі рандомізатором є масив з 2n випадкових двійкових послідовностей, занумерованих елементами множини Vn. Ключем є п-мірний двійковий вектор. При шифруванні з використанням ключа k двійкова послідовність відкритого тексту складається побітово з послідовністю рандомізатора, що має номер k. Таким чином, для дешифрування повідомлення супротивнику необхідно досліджувати порядка 2п біт.

Вартісний підхід.

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

1.4. Криптопротоколи, їх класифікація, особливості використання

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

Властивості криптопротоколів:

- кожен учасник протоколу повинен знати протокол і послідовність дій, що становлять його;

- кожен учасник протоколу повинен погодитися слідувати протоколу;

- протокол повинен бути несуперечливим, кожна дія повинна бути визначена так, щоб не було можливості нерозуміння;

- ?протокол повинен бути повним, кожній можливі ситуації повинна відповідати певна дія.

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

В крипптопротоколах використовується загальне правило: «Неможливо зробити або дізнатися більше, ніж це визначене в протоколі».

Умови криптографічного завдання визначають особливості відповідного протоколу.

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

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

Але при реалізації цих протоколів існують деякі труднощі:

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

- Комп'ютерна мережа повинна забезпечити підтримку посередника.

- Існує затримка, що властива всім протоколам із посередником.

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

- Через те, що в мережі всі повинні довіряти посереднику, він є слабким місцем мережі при спроби злому.

Існують і протоколи з арбітром, де під арбітром розуміється посередник особливого типа: він не обов'язково бере участь у виконанні кожного етапу протоколу, він запрошується тільки для перевірки коректності виконання протоколу.

Найпривабливіший різновид протоколів - самодостатні протоколи, конструкція яких забезпечує контроль за вірним виконанням протоколу. Для виконання цього протоколу не потрібен ані посередник, ані арбітр, що вирішує спори. Сама побудова протоколу забезпечує відсутність спорів. Якщо одна із сторін намагатиметься зшахраювати, шахрайство буде миттєво виявлено іншою стороною, і протокол припинить виконуватись.

В ідеальному випадку будь-який протокол повинен бути самодостатнім, але, на великий жаль, не існує самодостатніх протоколів для кожної ситуації.

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

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

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

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

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

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

1. Відправник і адресат домовляються про використовувану симетричну криптосистему, тобто про сімейство відображень Е = , k К, де К - простір ключів.

2. Відправник і адресат домовляються про секретний ключ зв'язку k, тобто про використовуване відображення ЕЕк.

3. Відправник шифрує відкритий текст X за допомогою відображення Ек, тобто створює криптограму Y = Ек (Х).

4. Криптограма Y передається по лінії зв'язку адресату.

5. Адресат розшифровує криптограму Y, використовуючи той же
ключ k і відображення Ек-1, зворотне до відображення Ек, і читає повідомлення X:

Х = Ек-1(Y).

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

Крок 2 протоколу реалізується або за допомогою посередника, третьої сторони, яку можна умовно назвати центром генерації і розподілу ключів (ЦГРК), або функції ЦГРК покладаються на абонентів. У першому випадку криптографічний протокол зв'язку шифру називають трибічним, а в другому випадку - двостороннім.

Захищений

канал зв'язку

Х k k Х

Лінія зв'язку

Х

k

Рис. 1.4

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

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

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

Пасивний супротивник (криптоаналітик), бажаючи дістати доступ до повідомлення X, контролює лінію зв'язку на кроці 4 протоколу. Не втручаючись в реалізацію протоколу, він перехоплює криптограму Y з метою розкриття шифру.

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

1) криптоаналітик контролює лінію зв'язку;

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

3) криптоаналітику невідомий ключ k, тобто невідомо відображення Ек, яке використане для отримання криптограми Y.

У цих умовах криптоаналітик намагається вирішити наступні завдання, які називаються завданнями дешифрування:

1. Визначити відкритий текст X і використаний ключ k по перехопленій криптограмі Y, тобто побудувати алгоритм дешифрування такий, що

( Y) = (Х, k).

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

(Х, Y) = к.

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

3. Визначити використовуваний ключ k по спеціально підібраному відкритому тексту X і по відповідному шифрованому тексту Y, тобто побудувати алгоритм дешифрування Х такий, що

Х(Y) = к.

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

Дешифрувальні задачі першого типу відрізняються вищою обчислювальною складністю в порівнянні із задачами другого і третього типу. Найменшу обчислювальну складність мають задачі тестування.

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

Розглянутий протокол має на увазі взаємну довіру відправника, адресата і третьої сторони в особі ЦГРК. Це є слабкістю даного протоколу, оскільки не завжди можна виключити взаємний обман дійових осіб протоколу. Втім, абсолютних гарантій бездоганності того або іншого протоколу не існує, оскільки виконання будь-якого протоколу зв'язане за участю людей і залежить, зокрема, від надійності дійових осіб протоколу.

Таким чином, по організації секретного зв'язку з використанням симетричної криптосистеми можна зробити наступні висновки:

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

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

3. Якщо допустити, що кожна пара користувачів мережі зв'язку
застосовує окремий ключ, то число необхідних ключів дорівнює
п(п-1)/2 для п користувачів. Це означає, що при великому п генерація, зберігання і розподіл ключів стає трудомісткою проблемою.

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

1. Відправник і адресат домовляються про використовувану асиметричну криптосистему.

2. Адресат посилає відправнику відкритий ключ k.

3. Відправник шифрує відкритий текст X за допомогою відкритого
ключа k, тобто створює криптограму Y = Еk(X).

4. Криптограма Y передається по лінії зв'язку адресату.

5. Адресат розшифровує криптограму Y, використовуючи закритий ключ z, і читає повідомлення X:

X = Еz(X).

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

Гідністю протоколу є те, що він не вимагає розподілу секретних ключів. У мережі зв'язку нерідко відкриті ключі всіх користувачів поміщаються в загальнодоступну базу даних, а закриті ключі зберігаються у користувачів. Це спрощує протокол, оскільки відправник сам виконує крок 2 протоколи, не чекаючи дії адресата. Адресат не бере участь в протоколі до тих пір, поки не збереться прочитати відкрите повідомлення.

Висновки

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

На практиці алгоритми з відкритим ключем не замінюють симетричних алгоритмів. Як правило, вони використовуються для шифрування не самих повідомлень, а ключів або деяких інших «допоміжних» інформаційних блоків відносно невеликої довжини. Це викликано наступними обставинами:

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

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

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

Розділ 2. Моделі елементів захищених систем

2.1. Поняття стійкості шифрсистеми

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

Щоб конкретизувати наші міркування, розглянемо «ігрову атаку», яка розігрується між Зловмисником і законним Учасником сеансу зв'язку. Ця гра дозволить продемонструвати обчислювальні аспекти, пов'язані з поняттям стійкості.

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

Ігрова атака описується наступним протоколом .

Попередні умови:

а) Зловмисник і законний Учасник діють в заданій криптосистемі, що складається з алгоритму шифрування , простору початкових повідомлень М і простору зашифрованих текстів С;

б) законний Учасник володіє фіксованим ключем шифрування k.

1. Зловмисник підбирає різні повідомлення m0, m1 М і посилає їх учаснику. Повідомлення m0, m1 називаються підібраним початковим текстом (chosen plaintext messages). Зловмисник поки знаходиться на етапі пошуку ("find-stage") повідомлень m0, m1. Зрозуміло, він готує їх так, щоб легко розпізнати результат їх шифрування.

2. Якщо ці повідомлення мають різну довжину, Учасник доповнює коротше з них, щоб їх довжини стали однаковими. Наприклад, для доповнення повідомлень він може використовувати фіктивний рядок 0d, де d - різниця між довжинами повідомлень. Учасник підкидає ідеальну монету b{0,1} і виконує наступну операцію шифрування

с* =

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

3. Одержавши зашифрований текст с*, Зловмисник повинен вгадати результат підкидання монети, надіславши учаснику 0 або 1. Тепер Зловмисник знаходиться на етапі осмисленого вгадування ("guess-stage" for an educated guess), намагаючись вгадати результат жеребкування, проведеного учасником. Відповіді, що відрізняються від 0 і 1, не допускаються.

У цій грі учасник пропонує зловмиснику відповісти на наступне питання. Результатом якого з експериментів k(m0) чи k(m1) є оклик с*?

Вважатимемо, що Зловмисник застосовує імовірнісний поліноміальний алгоритм розпізнавання. Позначимо через Adv перевагу Зловмисника, з яким він може розпізнавати відмінність між зашифрованими текстами. Вона дорівнює різниці між ймовірностями, з якими Зловмисник може розпізнати експерименти k(m0) чи k(m1).

Adv = | Prob[0 Зловмисник(с* = k(m0))] - Prob[0 Зловмисник(с* = =k(m1))]|. (2.1)

Імовірнісний простір повинен містити випадковий вибір, зроблений Учасником і Зловмисником, а також внутрішню випадкову операцію алгоритму шифрування. Відзначимо, що відповідь Зловмисника залежить не тільки від зашифрованого тексту оклику с*, але і від двох підібраних початкових повідомлень (m0, m1). Тільки тому його відповідь можна вважати результатом «осмисленого вгадування» («educated guess»).

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

Adv = |Prob[0 Зловмисник(с* = k(m0))] -

- Prob[0 Зловмисник(с*=k(m1))]|. (2.2)

Згідно з правилами гри Зловмиснику не дозволяється давати відповіді, які відрізняються від 0 та 1, тому неправильна відповідь є подією, додатковою по відношенню до правильної відповіді. З цього випливає наступна формула

Adv = |Prob[0 Зловмисник(с* = k(m0))] -

- (1 - Prob[0 Зловмисник(с*=k(m0))] )|.

Тобто

Prob[0 Зловмисник(с* = k(m0))] = Adv. (2.3)

Формула (2.3) часто застосовується для виразу переваги алгоритму при вгадуванні результатів підкидання ідеальної монети. Отже, якщо Adv = 0, то випадкова відповідь Зловмисника має такий самий розподіл, як і результати підкидання ідеальної монети. Проте слід враховувати, що перевага завжди більше нуля. Очевидно, що формула (2.1.3) також справедлива, якщо в результатах жеребкування всі нулі замінити одиницями.

З формули (2.3) виходить, що перевага Зловмисника ніколи не перевищує , оскільки імовірність завжди лежить в інтервалі [0,1]. Дійсно, якщо Учасник шифрує обидва початкові тексти з імовірністю , перевагу Adv, що задана формулою (2.1), є різниця імовірності сумісних подій і ніколи не перевищує . Можна відмітити, що формула (2.1.3) виглядає так, ніби Учасник підкидає несиметричну монету, наприклад, Учасник з імовірністю шифрує повідомлення m0 і з імовірністю - повідомлення m1.

Досліджувана криптосистема стійка по відношенню до ігрової атаки, якщо експеримент k(m0) не можливо відрізнити від експерименту k(m1). Це означає, що при будь-якій значущій перевазі Adv не повинно існувати жодного поліноміального алгоритму розпізнавання. Інакше кажучи, перевага, з якою Зловмисник може розрізняти результати шифрування, повинна бути дуже малою величиною в порівнянні з параметром безпеки схеми шифрування, яким, як правило, є довжина ключа шифрування. Можна вважати, що перевага будь-якого поліноміального алгоритму розпізнавання, що вживається Зловмисником, задається функцією, що повільно росте, залежною від об'єму обчислювальних ресурсів. Тут термін «повільно росте» означає, що, навіть якщо Зловмисник різко збільшить об'єм своїх обчислювальних ресурсів, перевага збільшиться украй трохи.

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

2.2. Стійкість криптографічних протоколів

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

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

- некоректна логіка роботи криптопротокола;

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

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

Проблеми, що відносяться до другої категорії, найбільш поширені. На практиці саме по цих «больових крапках» звичайно проводяться атаки на криптопротоколи. Активний порушник може робити вплив на функціонування криптопротоколу шляхом наступних атак:

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

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

- підміна сторони інформаційного обміну. В процесі встановлення сеансу зв'язку між легальними користувачами зловмисник у разі подібної атаки намагається видати себе за одного з них або ініціювати від імені легального користувача встановлення зв'язку;

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

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

Як приклад успішної атаки такого типу розглянемо криптопротокол розподілу секретних сеансових ключів між двома учасниками інформаційного обміну. Авторами цього методу є Нідхем і Шредер. Уразливість цього криптопротоколуа вперше була виявлена Денінгом і Сакко. Кожен учасник даного протоколу повинен розділити знання свого секретного ключа з сервером аутентифікації. Протокол складається з наступних кроків:

1. А > S: А, В, Na. Учасник А посилає запит серверу S, в якому він указує, що необхідно встановити сеанс зв'язку з учасником В. У даному запиті присутні наступні значення:

- А і В - імена або ідентифікатори учасників;

- N - унікальне для даного сеансу число; використовується для запобігання повторним передачам шляхом включення його в подальші повідомлення.

2. S > A: { Na, В, Кab, { Кab, А}Kbs}Kas.Сервер відповідає повідомленням, зашифрованим на секретному ключі сервер-учасник А (Кas), в якому знаходиться сеансовий ключ (Кab), а також ще одна копія цього ключа, зашифрованого на секретному ключі сервер-учасник В (Кbs).

3. А > B: { Кab, А}Кbs Учасник В розшифровує дане повідомлення, оскільки йому відомий ключ Кbs; в результаті він одержує ключ Кab.

4. B > A: {Nb}Kab. Дане повідомлення учасник В посилає для того, щоб переконатися, що А володіє ключем Кab, і показати учаснику А своє знання Кab.

5. А > B: {Nb - 1} Кab. Учасник А доводить своє володіння ключем Кab, і на цьому протокол закінчує свою роботу, в результаті учасники А і В одержують загальний секретний сеансовий ключ Кab.

Уразливість даного криптопротокола полягає в тому, що якщо сеансовий ключ К1ab із попередньої сесії був скомпрометований, то зловмисник (позначимо його через З), що дістав можливість контролю мережевого трафіку на кроці 3 нової (нескомпрометованої) сесії, перехоплює повідомлення (А > В: { Кab, A}Kbs) і замість нього посилає повідомлення (З > В: { К1ab, A}Кbs). Учасник B відповідає повідомленням (B > A: {Nb}К1ab), вважаючи, що А бажає встановити з ним нову сесію з ключем К1ab. З, одержуючи дане повідомлення, розшифровує його і відправляє В повідомлення (З > В: {Nb - 1}К1ab). Таким чином, З встановлює сесію з В від імені А.

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

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

Для прикладу проведемо доказ стійкості криптопротокола «уявний покер». Для початку необхідно розглянути сам протокол.

Для того, щоб зіграти в покер, гравці А і Б спочатку повинні чесно роздати карти. Слово «чесно» означає, що при роздачі карт А і Б повинні дотримуватися чотирьох правил.

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

2. А і Б повинні знати карти, якими вони володіють, а інші гравці не повинні знати, які карти знаходяться на руках їх партнерів.

3. А і Б повинні підозрюватися в шахрайстві і порушенні правил протоколу.

4. А і Б повинні мати можливість перевіряти, чи чесно була зіграна попередня гра.

Ідея, що лежить в основі уявного покеру, полягає в застосуванні шифру, що володіє властивістю комутативності. Застосовуючи такий шифр, А і Б можуть двічі шифрувати повідомлення, використовуючи свої секретні ключі, і повинні двічі розшифровувати його. Хай

С = ЕХ( М) і М = DX(C)

означають алгоритми шифрування і розшифрування, що виконуються користувачем X. Комутативна властивість шифру полягає в тому, що для будь-якого повідомлення М виконуються наступні рівняння.

М = DA(DB(EA(EB(M)))) = DB(DA(EB(EA(M)))). (2.4)

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

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

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

Попередні умови:

А і Б погодили комутативний шифр, що володіє властивістю (2.4), і згенерували свої секретні ключі шифрування. Колода складається з трьох карт: М1, М2 і М3.

Мета:

Чесна роздача по одній карті кожному гравцю за правилами 1 - 4 .

1. А шифрує три карти таким чином: Сі = ЕА( М), де і = 1,2,3. Він посилає Б ці три зашифровані тексти у випадковому порядку. (Передача зашифрованих текстів у випадковому порядку еквівалентна перетасовуванню колоди.)

2. Б випадковим чином витягує один із зашифрованих текстів. Позначимо його через С. Потім він двічі шифрує його як СС = ЕВ( С), випадковим чином витягує інший текст, позначений як С , і посилає зашифровані тексти СС і С А. ( Символи СС позначають карту, що належить Б , а символ С - карту, видану А. Зашифрована карта, що залишилася, ігнорується.)

3. А розшифровує тексти СС і С. Результат розшифрування тексту С позначає його карту, а розшифрування тексту СС, що позначається як С , - карту Б. Текст С повертається Б.

4. Б розшифровує текст С і узнає свою карту.

Аналіз стійкості.

Після виконання протоколу складається наступна ситуація.

* Оскільки на першому кроці А тасує колоду, обидва гравці з однаковою імовірністю одержують одну з карт, що належать множині {M1, M2, M3}. Потрібно звернути увагу на те, що А прагне добре перетасувати колоду, щоб Б не одержав переваги. Отже, перша умова чесної роздачі виконана.

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

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

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

Хай N - загальний модуль в криптосистемі RSA. А і Б знають розкладання числа N на множники. Позначимо через (еА, dA) показники ступенів, використані при шифруванні і розшифруванні А, а через (еВ, dВ) - показники, що вживаються Б. Знання розкладання числа N на прості множники дозволяє А (Б) знайти число еА по заданому числу dA (число еВ - по заданому числу dВ) за допомогою порівняння

еХ dХ = 1(mod (N)) (2.5)

де символ X позначає гравця А або В, (N) - функція Ейлера. Для користувача X одержуємо наступні формули.

ЕХ( М)=( mod N),

DХ( М)= ( mod N).

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

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

2.3. Математичні моделі елементів криптографічних систем

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

Моделі джерел відкритих текстів.

Детерміновані моделі.

Кожне джерело відкритого тексту (ДВП) характеризується:

1. одним або декількома мовами спілкування;

2. набором алфавітів, що використовуються;

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

4. частотними характеристиками повідомлень.

ДВП породжує тексти у відповідності з правилами граматики деякої мови, що знаходить відображення і в статистичних характеристиках повідомлень. Наприклад у текстах на англійській мові за літерою q завжди йде літера r, в російських текстах літери ь і ъ ніколи не слідують за голосними буквами. Взагалі кожну мову і кожне ДВП можна характеризувати розбиттям множини усіх k-грам, k = 2, 3,…, на допустимі (що зустрічаються в яких-небудь текстах) і недозволені (що не зустрічаються в жодних текстах).

Розбиття множини усіх k-грам на допустимі та недозволені визначає детерміновану модель ДВП. В такій моделі відкритий текст розглядається як послідовність букв деякого алфавіту, що не містить недозволених k-грам. Можна помітити, що розподіл k-грам на допустимі і недозволені умовне, причина чому динамічність мови, її здатність до розвитку. Крім того, вказаний розподіл може мати індивідуальні особливості для кожного ДВП.

Імовірнісні моделі.

В імовірнісних моделях ДВП розглядається як джерело випадкових послідовностей.

Хай джерело генерує в алфавіті Zm текст кінцевої або нескінченної довжини. При цьому можна вважати, що джерело генерує кінцеву або нескінченну послідовність випадкових змінних х0, х1, …, хn-1, що приймають значення в Zm. Імовірність випадкового повідомлення (а0, а1,…, аn-1) визначається як імовірність такої послідовності подій:

Р(а0, а1,…, аn-1)= Р х0 = а0, х1 = а1,…, х n-1 = аn-1.

Множина випадкових повідомлень утворює імовірнісний простір, якщо виконані умови:

1) Р(а0, а1,…, аn-1)0 для будь-якого випадкового повідомлення

(а0, а1,…,аn-1);

2) = 1;

3) Для будь-якого повідомлення (ао, а1, …,аn-1) і будь-якого s > n

Р(ао, а1, …,аn-1) = ,

тобто імовірність будь-якого випадкового повідомлення довжини n є сума імовірностей усіх продовжень цього повідомлення до довжини s.

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

Розглянемо таку імовірнісну модель ДВП, як стаціонарне джерело незалежних символів алфавіту.

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

Р(а0, а1,…, аn-1) =

де для всіх i0,1,…, n-1 і будь-якого aZm

Pxi = a>0; = 1.

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

Приведемо списки букв високої частоти використання для деяких європейських мов (табл. 2.3.1).

Таблица 2.1 Частота букв в різних мовах

Страницы: 1, 2, 3, 4