Методи сучасної криптографії:Іспит

Матеріал з USIC Wiki

Перейти до: навігація, пошук

Ця стаття відноситься до групи довідкових статей для студентів ФІН.

Портал:Інформаційні науки

Методи сучасної криптографії

Зміст

1 Припущення сучасної криптографії. Відмінності та переваги систем з симетричним ключем та відкритим ключем.
- 1.1 Криптографія з відкритим ключем
  - 1.1.1 Недоліки та переваги
- 1.2 Відмінності та переваги систем з симетричним ключем та відкритим ключем
2 Класичні криптосистеми (Шифр Цезаря, шифри простої заміни, шифри перестановки)
3 Афінні шифри. Криптоаналіз афінних шифрів на прикладі шифру Віжинера
4 Припущення сучасної криптографії. Умова абсолютної надійності шифру. Шифр одноразового блокноту.
5 Відмінності та переваги систем з симетричним ключем та відкритим ключем.
6 Основні цілі криптографії. Властивості, які вимагаються від електронного підпису.
7 Симетричні шифри: формалізація. Історичні приклади. Режими роботи симетричних шифрів.
8 Алгоритм Евкліда та його варіації. Застосування до знаходження оберненого елементу в Z_n^* та розв'язання діафантових рівнянь.
9 Кільце лишків. Теореми Ферма та Ойлера.
10 Функція Ойлера φ(n). Алгоритм ефективного обчислення a^b mod n.
11 Прості числа. Тестування та породження.
12 Криптосистеми з відкритим ключем
13 Система Ель-Гамаля
- 13.1 Генерування ключів
- 13.2 Шифрування
- 13.3 Розшифрування
14 Протокол Діффі-Хелмана
15 Система RSA
- 15.1 Генерування public та secret ключів
- 15.2 Шифрування/розшифрування
- 15.3 Цифровий підпис
16 Цифрові підписи. Вимоги до підписів. Система підпису Ель-Гамаля.
17 Цифрові підписи на основі системи RSA. Стандарт DSS та алгоритм DSA.
18 Симетричні криптосистеми. Принципи побудови сучасних блокових шифраторів на прикладі AES (деталі опустити)
19 Первісні корені. Визначення, тестування, породження
20 Протокол Діффі-Хелмана. Атака "людина всередині"
21 Хеш-функції. Основні означення, вимоги до хеш-функції. Застосування хеш-функції до перевірки цілісності та для аутентифікації.
22 Еліптичні криві над R, Q. Група точок та кривих
23 Еліптичні криві над полями F_p, p -просте число. Група точок на цих кривих
24 Скінченні поля GF(2ⁿ). Підрахунок кількості точок на еліптичних кривих
25 Протокол розподілу ключів Діффі-Хелмана на еліптичній кривій та система шифруванні Мессі-Омури
26 Система Ель-Гамаля на еліптичних кривих. Протокол MQV
27 Цифровий підпис на еліптичні кривій (ДСТУ 4145-2002)
28 Інфраструктура відкритого ключа (PKI): сертифікати, центри сертифікації тощо

Припущення сучасної криптографії. Відмінності та переваги систем з симетричним ключем та відкритим ключем.

Вимоги до безпеки інформації:

конфіденційність
цілісність
аутентифікація
контроль доступу
мітка часу
підпис
неспростовність (неможливість відмови від дії)

Криптографія

Вивчення математичних технік, пов'язаних із такими аспектами безпеки інформації:

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

Характеристики алгоритмів:

1. Рівень безпеки

2. Функціональність

3. Методи використання

4. Продуктивність

5. Легкість реалізації

Криптографія з відкритим ключем

$\{ E_e, e \in K \}$ , $D_d, d \in K$

Відкритий ключ: неможливо за реальний час за ключем e відновити ключ d.

Недоліки та переваги

переваги звичайних симетричних шифрів

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

недоліки симетричних шифрів

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

недоліки симетричних шифрів

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

переваги асиметричних шифрів

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

недоліки асиметричних шифрів

швидкодія на порядки менша, ніж в симетричних
великі типові розміри ключів
не доведено безпечність

Відмінності та переваги систем з симетричним ключем та відкритим ключем

Криптографія з відкритим ключем

В схемі з відкритим ключем є два ключі - відкритий public і секретний secret, обрані таким чином, що їх

послідовне застосування до масиву даних лишає цей масив без змін.

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

секретного ключа практично нездійсненна - нерозв'язною є задача вирахування секретного ключа за відкритим

ключем.

Переваги криптографії з відкритим ключем:

спрощений механізм обміну ключами. При здійсненні комунікації по каналу зв'язку передаэться тыльки

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

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

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

блоці тієї ж довжини.

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

значно розширились (цифровий підпис, ліцензування, нотаризація, схеми голосування, електронні гроші)

Криптографія з симетричним ключем

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

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

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

Приклади методу:

метод одноразового блокноту
DES (Data Encryption Standard)

Характеристики симетричних шифрів

1. Взаємно однозначне відображення

2. Компроміс між швидкістю та ефективністю

3. Розсіювання

4. Перемішування

5. високочастотний ступінь нелінійності

6. Кореляційний імунітет

7 відсутність особливостей шифрування

8. ітеративність

Класичні криптосистеми (Шифр Цезаря, шифри простої заміни, шифри перестановки)

Афінні шифри. Криптоаналіз афінних шифрів на прикладі шифру Віжинера

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

Відмінності та переваги систем з симетричним ключем та відкритим ключем.

Основні цілі криптографії. Властивості, які вимагаються від електронного підпису.

Забезпечення конфіденційності даних (униможливлення несанкціонованого доступу до даних).

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

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

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

Основний спосіб вирішення - використання цифрового підпису.

Цифровий підпис має мати такі властивості:

1. Должна быть возможность проверить автора, дату и время создания подписи.

2. Должна быть возможность аутентифицировать содержимое во время создания подписи.

3. Подпись должна быть проверяема третьей стороной для разрешения споров.

Таким чином, функція цифрового підпису включає в себе функцію аутентифікації

На основі цих властивостей можна сформулювати наступні вимоги до цифрового підпису:

1. Подпись должна быть битовым образцом, который зависит от подписываемого сообщения.

2. Подпись должна использовать некоторую уникальную информацию отправителя для предотвращения подделки или отказа.

3. Создавать цифровую подпись должно быть относительно легко.

4. Должно быть вычислительно невозможно подделать цифровую подпись как созданием нового сообщения для существующей цифровой подписи, так и созданием ложной цифровой подписи для некоторого сообщения.

5. Цифровая подпись должна быть достаточно компактной и не занимать много памяти.

Симетричні шифри: формалізація. Історичні приклади. Режими роботи симетричних шифрів.

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

Алгоритм Евкліда та його варіації. Застосування до знаходження оберненого елементу в Z_n^* та розв'язання діафантових рівнянь.

Кільце лишків. Теореми Ферма та Ойлера.

Функція Ойлера φ(n). Алгоритм ефективного обчислення a^b mod n.

Прості числа. Тестування та породження.

Криптосистеми з відкритим ключем

${E_e, e \in K}, {D_d, d \in K}$

Відкритий ключ: неможливо за реальний час за ключем e відновити ключ d

Переваги звичайних симетричних шифрів:

переваги звичайних симетричних шифрів:

ефективність (швидкість шифрування та дешифрування)

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

Недоліки симетричних шифрів:

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

Переваги асиметричних шифрів:

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

Недоліки симетричних шифрів:

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

Система Ель-Гамаля

Генерування ключів

Вибираютьp- просте (p-1 має містити простий дільник q > 2¹⁶⁰)
Вибирають 1<q<p-1

Бажано q - первісний корінь

Вибирають випадкове a від 2 до p-2

$h \equiv q^a \mod p$

Відкритий ключ: (p, q, h)
Закритий ключ: (a)

Шифрування

Повідомлення M б'ється на блоки по m

$m \in Z_p^*$

вибираємо випадкове число 1 ≤ r ≤ p-1
c=(c₁, c₂)

$c_1 \equiv q^r \mod p$

$c_2 \equiv m h^r \mod p$

Розшифрування

$D(C) \equiv c_2(c_1^a)^{-1} \mod p$

$(c_1^a)^{-1} = (q^{r-a})^{-1} = (h^r)^{-1} \mod p$

r має бути унікальним для кожного блоку

Протокол Діффі-Хелмана

Узгодження ключа

Дві сторони: Аліса та Боб

1. Сторона А: p - просте, q. Пара (p,q) передається Б

2. Сторона А генерує випадкове число k_a, 2 ≤ k_a ≤ p-2

Б генерує k_b: 2 ≤ k_b ≤ p-2

3. Сторона А: y_a=q^k_a mod p. Передає y_a стороні Б

4. Сторона Б: y_b=q^k_b mod p. Передає y_b стороні A

5. Сторона А: k=y_b^k_a mod p = q^k_ak_b mod p

6. Сторона Б: k=y_a^k_b mod p = q^k_bk_a mod p

Система RSA

Генерування public та secret ключів

1. Обирається два числа: p та q - прості числа

2. Вираховується добуток n=p*q - модуль

3. Вираховується значення функції Ейлера від n:

$\phi(n)=(p-1) \cdot (q-1) = n \cdot (1-\frac{1}{p})(1-\frac{1}{q})$

4. Обирається число e: (1 < e < φ(n)), взаємно просте зі значенням φ(n)

5. Вираховується число d, обернене до числа e за mod φ(n), тобто:

$d \cdot e \equiv 1 \mod \phi (n)$

$d \cdot e \equiv 1 + k \cdot \phi(n)$ , k -ціле число

6. Відкритий ключ RSA: P=(e, n)

7. Секретний ключ RSA: S=(d, n)

Шифрування/розшифрування

Алгоритм шифрування стороною B

B посилає повідомлення до А

береться відкритий ключ (e, n) сторони А
взяти відкритий текст M
передати повідомлення: P_A(M)=M^e mod n

Алгоритм дешифрування стороною А

прийняти повідомлення C
Застосувати секретний ключ (d, n) - закритий ключ ((e, n) - відкритий ключ)

S_A(C)= C^d mod n

Цифровий підпис

RSA може використовуватися не тільки для шифрування, але й для цифрового підпису. Підпис $s\,$ повідомлення $m\,$ обчислюється з використанням секретного ключа за формулою:

$s=m^d\bmod\ n\,$

Для перевірки правильності підпису потрібно переконатися, що виконується рівність

$m=s^e\bmod\ n\,$

Цифрові підписи. Вимоги до підписів. Система підпису Ель-Гамаля.

Цифрові підписи на основі системи RSA. Стандарт DSS та алгоритм DSA.

Симетричні криптосистеми. Принципи побудови сучасних блокових шифраторів на прикладі AES (деталі опустити)

Первісні корені. Визначення, тестування, породження

Первісний корінь за модулем $m$ ― ціле число $g$ таке, що

$g^{\phi(m)} \equiv 1 \mod m$

і

$g^{\ell} \not\equiv 1 \mod m$ при $1\le\ell\le\phi(m)-1,$

де $φ(m)$ ― функція Ейлера. Іншими словами, первісний корінь - це породжуючий елемент мультиплікативної групи. кільця лишків за модулем $m$ .

Для первісного кореня $g$ його степені $g 0 = 1, g,..., g φ(m) - 1$ непорівнювані між собою за модулем $m$ і породжують приведену систему лишків за модулем $m$ . Тому для кожного числа $a$ , взаємно простого з $m$ , знайдеться показник $\ell$ ( $0\le\ell\le\phi(m)-1$ ) такий, що

$g^{\ell} \equiv a \pmod m.$

Таке число $\ell$ називається індексом числа a за основою g.

Первісні корені існують не для всіх модулів, а тільки для модулів $m$ виду

m = 2,4, p a,2 p a,

де $p > 2$ ― просте число. Тільки в цих випадках мультиплікативна група кільця лишків за модулем $m$ є циклічною групою порядку $φ(m)$ .

Протокол Діффі-Хелмана. Атака "людина всередині"

Хеш-функції. Основні означення, вимоги до хеш-функції. Застосування хеш-функції до перевірки цілісності та для аутентифікації.

Еліптичні криві над R, Q. Група точок та кривих

Еліптичні криві над полями F_p, p -просте число. Група точок на цих кривих

Скінченні поля GF(2ⁿ). Підрахунок кількості точок на еліптичних кривих

Протокол розподілу ключів Діффі-Хелмана на еліптичній кривій та система шифруванні Мессі-Омури

Система Ель-Гамаля на еліптичних кривих. Протокол MQV

Цифровий підпис на еліптичні кривій (ДСТУ 4145-2002)

Інфраструктура відкритого ключа (PKI): сертифікати, центри сертифікації тощо

PKI, як і простий сервер-депозитарій, має базу даних для збереження сертифікатів, але, у той же час, надає сервіси і протоколи по керуванню відкритими ключами. У них входять можливості випуску (видання), відкликання (анулювання) і системи довіри сертифікатів. Головною же особливістю PKI є наявність компонентів, відомих як Центр сертифікації (Certification Authority, CA) і Центр реєстрації (Registration Authority, RA). Центр сертифікації (ЦС) видає цифрові сертифікати і підписує їх своїм закритим ключем. Через важливість своєї ролі, ЦС є головним компонентом інфраструктури PKI. Використовуючи відкритий ключ ЦС, будь-який користувач, що бажає перевірити дійсність конкретного сертифіката, звіряє підпис Центра сертифікації і, отже, засвідчується в цілісності інформації, що утримується в сертифікаті, і, що більш важливо, у взаємозв’язку зведень сертифіката і відкритого ключа.

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

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

Формат сертифікатів Цифровий сертифікат - це набір ідентифікуючих зведень , зв'язаних з відкритим ключем і підписаних довіреною третьою особою , щоб довести їхня дійсність і взаємозв'язку. Сертифікат може бути представлений безліччю різних форматів. PGP підтримує два формати сертифікатів:

• Сертифікати OpenPGP (частіше називані просто ключами PGP) • Сертифікати X.509

Формат сертифікату PGP Сертифікат PGP містить :

• Відкритий ключ власника сертифіката - відкрита частина ключової пари і її алгоритм: RSA v4, RSA Legacy v3, DH або DSA. • Зведення про власника сертифіката - інформація, що ідентифікує особистість користувача: його ім'я, адреса електронної пошти, номер ICQ, фотографія і т.д. • ЕЦП власника сертифіката - підпис ключової пари, зв'язаної із сертифікатом (т.зв. автопідпис). • Період дії сертифіката - дата початку дії сертифіката і дата закінчення його дії; указує на те, коли сертифікат стане недійсним (аналогічно терміну дії прав водія). Якщо ключова пара містить додаткові підключи шифрування, то тут буде зазначений період дії кожного з них . • Кращий алгоритм шифрування - указує на те, зашифровану яким алгоритмом інформацію воліє одержувати власник сертифіката. Підтримуються наступні: CAST, AES, IDEA, Triple-DES і Twofish.

Ви можете представити сертифікат PGP у виді відкритого ключа з однієї або декількома прив'язаними до нього "бирками" (мал. 9). На цих "бирках" зазначена інформація, що ідентифікує власника ключа, а також підпис цього ключа, що підтверджує, що ключ і ідентифікаційні зведення взаємозалежні. (Цей вид підпису називається автопідписом (self-signature); її містить кожен PGP-сертифікат.)

Унікальний аспект формату сертифікатів PGP у тім , що кожен сертифікат може містити безліч підписів. Будь-яка людина може підписати ідентифікаційно-ключову пару, щоб завірити, покладаючись на своє особисте переконання, що відкритий ключ належить саме зазначеному в ID користувачеві. Якщо пошук на суспільних серверах-депозитаріях, то можете знайти деякі ключі, як, наприклад, що належить авторові PGP Філу Ціммерману, що містять величезну кількість підписів.

Деякі PGP-сертифікати складаються з відкритого ключа з декількома "бірками", кожна з яких містить власні зведення , що ідентифікують власника ключа (наприклад, ім'я власника і його робітник e-mail, прізвисько власника і його домашній e-mail, фотографія власника - усі на одному сертифікаті). Список підписів на кожній з "бірок" може бути різним ; підпису вказують на вірогідність визначеної "бірки" і її приналежність відкритому ключеві, а не на те, що всі "бірки" достовірні. (Врахуйте, що "вірогідність" залежить від встоновленого неї : підпису - це думки, і різні люди приділяють різний ступінь уваги перевірці дійсності перед підписанням ключа.)