Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Формалізм

Елементарна криптографія : математичний підхід

Розділ II.

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

1.1. Абетка II. Алфавітом називаємо довільну скінченну множину. Типовими прикладами, які зустрічаються у нашому курсі, є

{а, б, в, г,..., ь, ю, я} - український алфавіт,

{_, а, б, г,..., ь, ю, я} - він же з пропуском між словами,

{_,.,!,?, а, б, г,..., ь, ю, я} - він же з розділовими знаками,

{0, 1}6 - всі 0-1 – послідовності довжини 6,

Z33 = {0,1,2,..., 32} - кільце лишків за модулем 33.

Алфавіти позначатимемо рукописними літерами A, В і т.д. Елементи алфавіту називатимемо символами або буквами, навіть якщо це буде розходитись із звичним вживанням останнього терміну. Наприклад, цифра 1, і число 10 є буквами алфавіту Z33. Слово в алфавіті A — це скінченна послідовність букв цього алфавіту. A* служитиме позначеням для множини всіх слів у алфавіті A. Довжина слова — це кількісі букв у ньому. Зрозуміло, що множина слів у алфавіті A довжини l є нічим іншим як декартовим степенем Al. Довжину слова w позначатимемо як |w|. Для слів v і u через vu позначатимемо результат їх злиття в одне слово, саме в такому порядку. Слово v називатимемо префіксом слова w. У випадку, коли v = w або w = vu для деякого слова и.

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

· Алфавіт А, в якому записуються повідомлення (відкриті тексти}. Повідомлення М є словом в алфавіті А (яке може складатися з багатьох слів у звичному лінгвістичному розумінні), тобто М Є А*. Множина А* називається простором повідомлень або відкритих текстів.

· Алфавіт В, в якому записуються криптотексти. Множина В* називається простором криптотекстів. Часто А = В.

· Простір ключів К, який складається із слів у деякому алфавіті, що називаються ключами.

· Шифруюче відображення Е : КА* В*.

· Дешифруюче відображення D : КВ* А*. Відображення Е і D повинні мати таку властивість:

D(K, Е(К, М)) - М для всіх М А* і К К.. (1)

Фіксація ключа К визначає відображення Ek: А* В* за формулою Ек(М) = Е(К,М) для кожного М А*. Подібним чином задається й відображення Dk: В* А*

Властивість (1) по-іншому можна сформулювати так: для будь-якого К дешифруюче відображення. Dk: В* А* є оберненим зліва до шифруючого відображення Ek: А* В*. З теореми про обернене відображення (див. додаток Б) випливає, що Ek мусить бути ін'єкцією. Цілком зрозуміло, що ця умова рівнозначна принциповій можливості дешифрування. Навпаки, на підставі тієї ж теореми будь-яка родина ін’єктивних відображень {Ек : А* В*} kk може розглядатись як шифруюча в тому плані, що для них існують обернені зліва відображення {Dк : В* А*} kk, які можуть вважатися дешифруючими.

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

Dk(Ek(M)) = Ek(Dk(M)) = М.

Криптосистему називаємо ефективною, якщо шифруюче і дешифруюче відображення

 


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

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

Шифр називається блоковим з періодом l, якщо шифруюче відображення задається спочатку на словах довжини l, тобто маємо Е : K Аl В*, а після цього поширюється на слова довільної довжини наступним чином. Якщо М = M1M2…Mt, де блоки Мі, і t, мають довжину l, то Е(К,М) = E(K,M1)E(K,M2)...E(K,Mt). Якщо ж останній блок Mt має меншу від l довжину, то він доповнюється до повного довільним наперед обумовленим чином.

Часто у блоковому шифрі шифруюче відображення зберігає довжину, тобто є вигляду Е : К Аl Вl. Окрім того множини Аl і Вl можуть містити однакову кількість слів, як це буде, скажімо, в поширеному випадку А = В. Якщо ми маємо відображення саме такого виду і розглядаємо питання, чи можна його використовувати як шифруюче, то в пригоді знову стає теорема про обернене відображення. Згідно з нею досить довести якусь одну з чотирьох умов: 1) ін'єктивність, 2) сюр'єктивність, 3) існування оберненого зліва відображення, 4) існування оберненого справа відображення.

1.2. Дешифрування ітераціями. В цьому пункті ми розглядаємо блоковий шифр із шифруючим відображенням виду Е : К Аl Al (алфавіт криптотекстів збігається з алфавітом повідомлень). Зрозуміло, що для кожного ключа К шифруюче відображення ек є елементом групи Sym Al, де SymX позначає групу перестановок множини X. Принагіднo означимо формально поняття, введене на стор. 40: шифр Е : К Аl Al утворює групу, якщо родина {Ек} kk є в Sym Al підгрупою.

Шифруюче відображення Еk : Аl Al можна застосовувати кілька разів. Відображення Еsk : Аl Al означимо індуктивнo: Е1к = Ek, Еiк = Eк о Еi-1к для і > 1. Еiк будемо називати і-кратною ітерацією або і-тим степенем відображення Eк.

Методом ітерацій суперник може скористатися у разі, коли він має доступ до шифруючого відображення із фіксованим ключем (хоча не знає, який саме ключ К "зашито" в алгоритм). Підслухавши крипто текст С = Ек(М), суперник може спробувати знайти повідомлення М обчислюючи послідовность Е1к(С), E2к(C), Е(С),... доти, поки на якумусь m-му кроці не виявиться, що Еmк(С) = С. Це означає, що повідомлення було отримане на попередньому кроці: М = Еm-1к(С)

Твердження 1.1. Для шифруючого відображення Е : К Аl Al метод ітерацій через деяку кількість кроків приводить до успіху. Точніше, якщо алфавіт складається з п букв, то для будь-якого ключа К існує число m < (пl)! таке, що Еmк(С) = С для всіх САl.

Доведення. В якості m можна взяти порядок відображення Eк як елемента групи SymAl, який за теоремою Лагранжа не перевищує (п')! порядку цієї групи (див. додаток Б). Тоді для будь-якого САl матимемо Еmк(С) = idA’(C) = C.

ВПРАВИ

1.1.Дати формальне означення композиції двох шифруючих відображень Е1 : К1 А* Ь* і Е2 : К2 Ь* С* (повідомлення шифрується спочатку за допомогою Е\, а потім ще раз за допомогою Е2).

1.2.Дати незалежне від теореми Лагранжа доведення того, що метод ітерацій раніше чи пізніше досягає успіху.

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

a)кроків, де е = 2, 71828... — основа натуральних логарифмів.

ь) кроків, де (х) — кількість простих чисел, що не перевищують х (див. пункт IV. 1.3).

1.4. Довести, що для розкриття шифру Віженера над n-символьним алфавітом досить п ітерацій.





Переглядів: 825

<== попередня сторінка | наступна сторінка ==>
Дві пропозиції XX століття | Арифметика

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

  

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.003 сек.