Розробка імовірнісної моделі криптографічних протоколів (стр. 10 из 19)
Для прикладу проведемо доказ стійкості криптопротокола «уявний покер». Для початку необхідно розглянути сам протокол.
Для того, щоб зіграти в покер, гравці А і Б спочатку повинні чесно роздати карти. Слово «чесно» означає, що при роздачі карт А і Б повинні дотримуватися чотирьох правил.
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 j(N)) (2.5)
де символ X позначає гравця А або В, j(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-грам. Задаючи певний імовірнісний розподіл на множині відкритих текстів, задається відповідна модель ДВП.
Розглянемо таку імовірнісну модель ДВП, як стаціонарне джерело незалежних символів алфавіту.
У цій моделі передбачається, що імовірність повідомлень повністю визначається імовірністю використання окремих букв алфавіту у випадковому тексті: