Класична задача криптографії

Сентябрь 7, 2022

Главная
Алгебра
Класична задача криптографії

Содержание

2. Класична задача криптографії М – відкритий текст С – криптотекст К – ключ. Е – алгоритм
3. Запис криптографічних перетворень С = Ек(М) - криптотекст С є результатом застосування алгоритму Е до відкритого
4. Криптологія: Криптографія Криптоаналіз
5. Криптоаналітичний принцип Керкгоффса: Аналізуючи надійність шифру, ми зобов'язані виходити із припущення, що суперник: здатен підслухати С
6. Стійкість Спроба зламу шифра – атака на шифр. Здатність шифра витримувати атаки - стійкість.
7. Брутальна атака Для знаходження М суперник може скористатися методом повного перебору. Суперник може перебирати всі можливі
8. Атака лише із криптотекстом. Суперник знає лише криптотекст ЕК(М). Варіант - крім ЕК(М) відома ще певна
9. Атака з відомим відкритим текстом. Крім ЕK(М) суперник знає як додаткові криптотексти ЕK(М1),..., ЕK(МІ), так і
10. Атака з вибраним відкритим текстом. Суперник має доступ до "шифруючого устаткування" і спроможний отримати криптотексти ЕK(М1),.
11. Атака з вибраним криптотекстом. Суперник має доступ до "дешифруючого устаткування" і спроможний отримати відкриті тексти DK(M1),.
12. Стійкість/вразливість Якщо атака певного виду призводить до розкриття шифру, то шифр є вразливим до неї, якщо
13. Особливості шифрів заміни Загальна кількість можливостей розмістити букви у всіх n позиціях дорівнює добутку n *
14. Шифр зсуву Шифр зсуву є звуженням загального шифру заміни на сукупність лише n ключів, у яких
15. Вразливість шифрів заміни Шифри заміни стійкий до брутальної атаки (n! ключів) на відміну від підмножини шифрів
16. Частотний аналіз У досить довгих текстах кожна буква зустрічається із приблизно однаковою частотою, залежною від самої
17. Частоти літер української мови
18. Графік частот вживання літер
19. Додаткові методи частотного аналізу Якщо при шифруванні не ігноруються пропуски між словами, то найпоширенішим символ у
20. Приклад частотного аналізу Розшифрувати криптотекст, отриманий шифром зсуву, причому пропуски та розділові знаки ігнорувались Пцпспофнпмплпибгпефрптмбвмєоп
21. Гомофонний шифр заміни К. Ф. Гауса Кожна буква відкритого тексту замінюється не єдиним символом як у
22. Поліграмні шифри. Послідовність кількох букв тексту називається поліграмою. Послідовність із двох букв називається біграмою (іноді диграфом),
23. Playfair, 4-и квадрати Розглянемо біграмний шифр, що застосовується до текстів латинкою. Ключем є чотири квадрати розміру
24. Поліалфавітні шифри. Поліалфавітними називають шифри заміни, в яких позиція букви у відкритому тексті впливає на те,
25. Шифр Віженера. Для букв х та у цього алфавіту означимо їх суму х + у як
26. Таблиця кодування для Віженера
27. Розшифрувати КЛЮЧ ЛАОЇЮЦРФШАОЇЩЦАІҐНЗЯМАОЇНЦА
28. при використанні шифру Віженера однаковим буквам у відкритому тексті можуть відповідати різні букви у криптотексті. За
29. Шифр з автоключем Віженера- Кардано. Криптотекст отримують сумуванням відкритого тексту із послідовністю букв такої ж довжини.
30. Завдання 1 Завдання 1.1. Користуючись шифром зсуву на 2 позиції, зашифрувати повідомлення рятуйтесь. 1.2 Розшифрувати криптотекст
31. а) Зашифрувати слово cryptography за допомогою шифру заміни з ключем abcdefghijklm nopqrstuvwxyz badcfehgjilkn mporqtsvuxwzy b) Дешифрувати
33. Скачать презентацию

Слайд 2

Класична задача криптографії
М – відкритий текст
С – криптотекст
К – ключ.

Е – алгоритм шифрування
D – алгоритм дешифрування

Слайд 3

Запис криптографічних перетворень
С = Ек(М) - криптотекст С є результатом застосування

алгоритму Е до відкритого тексту М та ключа К
М = Dк(С) відкритий текст М отримується із С та K за допомогою алгоритму D.

Слайд 4

Криптологія:
Криптографія
Криптоаналіз

Слайд 5

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

суперник:
здатен підслухати С
знає алгоритми Е і D
ключ К йому невідомий.

Слайд 6

Стійкість
Спроба зламу шифра – атака на шифр.
Здатність шифра витримувати атаки

- стійкість.

Слайд 7

Брутальна атака
Для знаходження М суперник може скористатися методом повного перебору.
Суперник

може перебирати всі можливі ключі К і обчислювати DK(С) доти, доки не натрапить на осмислений текст, який вірогідно і буде шуканим.

Слайд 8

Атака лише із криптотекстом.
Суперник знає лише криптотекст ЕК(М).
Варіант - крім

ЕК(М) відома ще певна кількість криптотекстів ЕK(М1),.. .,ЕK(МІ), зашифрованих з використанням одного й того ж ключа.

Слайд 9

Атака з відомим відкритим текстом.
Крім ЕK(М) суперник знає як додаткові криптотексти

ЕK(М1),..., ЕK(МІ), так і відповідні їм відкриті тексти М1,..., MI (які, скажімо, пересилалися раніше і з тих чи інших причин вже не є таємними).

Слайд 10

Атака з вибраним відкритим текстом.
Суперник має доступ до "шифруючого устаткування" і

спроможний отримати криптотексти
ЕK(М1),. .., ЕK(МІ)
для вибраних на власний розсуд відкритих текстів М1, . . ., МI (ця атака відповідає мінімальним можливостям суперника у випадку криптосистем з відкритим ключем).

Слайд 11

Атака з вибраним криптотекстом.
Суперник має доступ до "дешифруючого устаткування" і спроможний

отримати відкриті тексти DK(M1),. . ., DK(M I) для вибраних на власний розсуд криптотекстів С1,..., СІ
(однак, як і у випадку попередньої атаки, неспроможний отримати безпосередньо таємний ключ).

Слайд 12

Стійкість/вразливість
Якщо атака певного виду призводить до розкриття шифру, то шифр є

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

Слайд 13

Особливості шифрів заміни
Загальна кількість можливостей розмістити букви у всіх n позиціях

дорівнює добутку n * n-1 *n-2 *...*2. Таким чином, загальна кількість ключів є n!.
Серед цієї загальної кількості деякі ключі є непридатними для вжитку, як от тривіальний ключ, у якому нижній рядок збігається з верхнім.

Слайд 14

Шифр зсуву
Шифр зсуву є звуженням загального шифру заміни на сукупність лише

n ключів, у яких нижній рядок є циклічним зсувом верхнього рядка.
Ключ такого гатунку повністю визначається довжиною зсуву s.
Можна вважати, що 0 ≤ s

Слайд 15

Вразливість шифрів заміни
Шифри заміни стійкий до брутальної атаки (n! ключів) на

відміну від підмножини шифрів зсуву (n-1 ключів)
Але вони вразливі до частотного аналізу

Слайд 16

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

частотою, залежною від самої букви та незалежною від конкретного тексту та ключа.
купила мама коника
частота букви «а» = 4/18 = 0,22
частота пропуску = 2/18 = 0,11

Слайд 17

Частоти літер української мови

Слайд 18

Графік частот вживання літер

Слайд 19

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

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

Слайд 20

Приклад частотного аналізу
Розшифрувати криптотекст, отриманий шифром зсуву, причому пропуски та розділові

знаки ігнорувались
Пцпспофнпмплпибгпефрптмбвмєоп

Слайд 21

Гомофонний шифр заміни
К. Ф. Гауса
Кожна буква відкритого тексту замінюється не єдиним

символом як у шифрі простої заміни, а будь-яким символом із декількох можливих.
Наприклад:
«а» замінюється будь-яким із чисел 10,17,23,46,55,
«б» — будь-якого із 12,71.
Кількість варіантів для кожної букви пропорційна її частоті в мові.
Гомофонний шифр піддається ретельнішому і трудомісткішому різновиду частотного аналізу, який окрім частот окремих символів враховує також частоти пар символів. Подібний аналіз дозволяє ламати ще один клас шифрів заміни, про що йдеться у наступному пункті.

Слайд 22

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

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

Слайд 23

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

чотири квадрати розміру 5 на 5
підрахунок частот окремих букв алфавіту нічого не дає.
Однак для l = 2 з успіхом застосовується аналіз частот біграм.

Слайд 24

Поліалфавітні шифри.
Поліалфавітними називають шифри заміни, в яких позиція букви у відкритому

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

Слайд 25

Шифр Віженера.
Для букв х та у цього алфавіту означимо їх суму

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

Слайд 26

Таблиця кодування для Віженера

Слайд 27

Розшифрувати
КЛЮЧ
ЛАОЇЮЦРФШАОЇЩЦАІҐНЗЯМАОЇНЦА

Слайд 28

при використанні шифру Віженера однаковим буквам у відкритому тексті можуть відповідати

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

Слайд 29

Шифр з автоключем Віженера- Кардано.
Криптотекст отримують сумуванням відкритого тексту із послідовністю

букв такої ж довжини. Однак тепер цю послідовність формують хитріше — спершу записують ключ, а справа до нього дописують початковий відрізок самого відкритого тексту:
КЛЮЧ
ЛАОЇОЩЗЛЮЩЗЛЩЩТВДЙЙТХРЮУДЩТ

Слайд 30

Завдання 1
Завдання
1.1. Користуючись шифром зсуву на 2 позиції, зашифрувати повідомлення
рятуйтесь.
1.2 Розшифрувати

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

Слайд 31

а) Зашифрувати слово cryptography за допомогою шифру заміни з ключем
abcdefghijklm nopqrstuvwxyz

badcfehgjilkn mporqtsvuxwzy
b) Дешифрувати криптотекст vnjufqtjsz, отриманий за використанням того ж ключа.
Порахувати частоти всіх символів у тексті мамаимилаираму.
В потоці зашифрованих донесень від інформатора домінує буква н. Припустивши, що використовується шифр зсуву і пропуски між словами ігноруються, знайти за допомогою частотного аналізу ключ і розшифрувати повідомлення
опдрснкнмярстомзйнлопнвнкнчдмннкдкшйяспдсшнвн.
а) Використовуючи шифр чотирьох квадратів із пункту з ключем як на малюнку, зашифрувати слово university.
b) Дешифрувати криптотекст sknromra, отриманий за допомогою того ж шифру з тим же ключем.
а) Зашифрувати повідомлення білі мухи налетіли, використавши шифр Віженера з ключем зима.
b) Розшифрувати криптотекст ьччжпчьишисаеяйпявааьяч, отриманий за допомогою шифру Віженера з тим же ключем.
Показати, що шифр зсуву є частковим випадком шифру Віженера. Який ключ у шифрі Віженера над українським алфавітом слід взяти, щоб отримати шифр Цезаря?

Класична задача криптографії

Содержание

Класична задача криптографії М – відкритий текстС – криптотекстК – ключ.

Запис криптографічних перетвореньС = Ек(М) - криптотекст С є результатом застосування

Криптологія:КриптографіяКриптоаналіз

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

СтійкістьСпроба зламу шифра – атака на шифр. Здатність шифра витримувати атаки

Брутальна атакаДля знаходження М суперник може скористатися методом повного перебору. Суперник

Атака лише із криптотекстом.Суперник знає лише криптотекст ЕК(М). Варіант - крім

Атака з відомим відкритим текстом.Крім ЕK(М) суперник знає як додаткові криптотексти

Атака з вибраним відкритим текстом.Суперник має доступ до "шифруючого устаткування" і

Атака з вибраним криптотекстом.Суперник має доступ до "дешифруючого устаткування" і спроможний

Стійкість/вразливістьЯкщо атака певного виду призводить до розкриття шифру, то шифр є

Особливості шифрів заміниЗагальна кількість можливостей розмістити букви у всіх n позиціях

Шифр зсувуШифр зсуву є звуженням загального шифру заміни на сукупність лише

Вразливість шифрів заміниШифри заміни стійкий до брутальної атаки (n! ключів) на

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