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


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


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


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


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


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


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


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


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


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



Контакти
 


Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция






Формалізм

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

Розділ 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-символьним алфавітом досить п ітерацій.





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

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

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

 

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


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