- •1. Розділ 1 " Прикладна криптологія "
- •Основні поняття криптології. Шифрування та кодування. Стеганографія та криптографія. Алгоритми та протоколи.
- •Шифрування методом Цезаря. Зламування методу Цезаря.
- •Криптостійкість шифрів
- •Шифрування методом простої підстановки. Статистичні властивості мови. Зламування методу простої підстановки.
- •Поліалфавітні шифри (Гронсфельда, Тритеніуса, Віженера). Зламування методу Віженера.
- •Криптостійкість ключів.
- •Перестановочні шифри. Статистичні властивості криптограм перестановок.
- •Методи генерації псевдовипадкових послідовностей.
- •Симетричні шифри. Блочні та потокові шифри. Режими роботи блочних шифрів.
- •Стандарт шифрування dеs.
- •Стандарт шифрування rc5.
- •Характеристики
- •Шифрування
- •Дешифрування
- •Створення підключів
- •Стандарт шифрування idea.
- •Стандарт шифрування aes.
- •Криптоаналіз блочних та потокових шифрів.
- •Асиметрична криптографія.
- •Метод Райвеста-Шамира-Адлемана (rsа).
- •Перевірка чисел на взаємну простоту (розширений алгоритм Евкліда). Теореми Міллера-Рабіна та Ферма.
- •Зламування криптограм rsа.
- •Дискретне логарифмування.
- •Метод ель-Гамаля. Розшифровування криптограм ель-Гамаля.
- •Автентифікація користувача. Цифровий підпис. Стандарт dsa.
- •Шифрування з використанням еліптичних кривих.
- •Забезпечення цілісності інформації. Алгоритми хешування. Стандарт md5.
- •Забезпечення цілісності інформації. Алгоритми хешування. Стандарт sha-1.
- •Забезпечення цілісності інформації. Алгоритми хешування. Стандарт ripemd-160.
- •Реализация ripemd-160
- •Автентифікація користувача. Коди автентичності повідомлень.
- •Управління ключами. Обмін ключами по схемі Діффі-Хеллмана.
Дискретне логарифмування.
Стійкість широко розповсюджених у даний час схем ЕЦП (електронний цифровий підпис) заснована на складності рішення приватної завдання дискретного логарифмування в простому полі GF (p). Завдання це формулюється наступним чином:
• задані прості числа p, q і натуральне число g <p порядку q, тобто
gq 1 (modp);
• знаючи значення y = gx (mod p), необхідно знайти x Z.
В даний час найбільш швидким алгоритмом рішення загальної задачі дискретного логарифмування (при довільному виборі g) є алгоритм узагальненого решета числового поля, обчислювальна складність якого оцінюється як
O(exp((c+O(1))(ln (p))1/3(ln (ln (p)))2/3 операцій в полі GF(p), де c (64/9)1/3.
Методами рішення приватної завдання дискретного логарифмування є також -метод и -метод Полларда і деякі близькі методи, що вимагають для її вирішення виконання порядку
q/4 операцій множення в полі GF (p). (1.2)
«При 1024-бітовому p і 256-бітовому q ми отримуємо приблизно 1.3E +26 для методу решета числового поля і 3.0E +38 для - і - методів Полларда».
Національні стандарти DigitalSignatureStandard (прийнятий NIST в 1991 р. з наступними змінами в 1993, 1996 р.), російський стандарт цифрового підпису ГОСТ Р 34.10-94 реалізовують ЕЦП в простому полі.
Прогрес в галузі вирішення задачі дискретного логарифмування привів до того, що стала можлива реальна компрометація схем ЕЦП, заснованих на складності обчислень у мультиплікативної групи поля, з боку порушника, який володіє досить невисокими обчислювальними і фінансовими ресурсами. Тому на рубежі XX і XXI століття в багатьох країнах світу стали використовуватися схеми формування ЕЦП, засновані на складності розв'язання задачі дискретного логарифмування в групі точок еліптичної кривої. Це завдання формулюється наступним чином:
• задана еліптична крива E над полем GF (p), де p - просте число;
• обрана точка G, що має простий порядок q в групі точок кривої E;
• знаючи точку kG необхідно відновити натуральне число k.
Алгоритми створення і перевірки ЕЦП, що базуються на математичному апараті еліптичних кривих, є стійкішими в порівнянні зі схемами, що базуються на складнощі вирішення задачі дискретного логарифмування в простому полі.
В даний час найбільш швидкими алгоритмами розв'язання задачі дискретного логарифмування в групі точок еліптичної кривої при правильному виборі параметрів вважаються - метод і - метод Полларда і близькі їм методи. Їх складність оцінюється формулою (1.2) і, таким чином, числом близько 1038 операцій додавання точок кривої.
Метод ель-Гамаля. Розшифровування криптограм ель-Гамаля.
Алгоритм Ель-Гамаля може використовуватися для формування електронного підпису або для шифрування даних. Він базується на трудності обчислення дискретного логарифма. Для генерації пари ключів спочатку береться просте число p і два випадкових числа g і x, кожне з яких менше p. Потім обчислюється: y = gx mod p
Загальнодоступними ключами є y, g і p, а секретним ключем є х. Для підпису повідомлення M вибирається випадкове число k, яке є простим по відношенню до p-1. Після цього обчислюється a= gk mod p.
Далі з рівняння M = (xa + kb) mod (p-1) знаходимо b. Електронним підписом для повідомлення M буде служити пара a і b. Випадкове число k слід зберігати в секреті. Для верифікації підпису необхідно перевірити рівність:
yaab mod p = gM mod p.
Пара a і b представляють собою зашифрований текст. Слід зауважити, що зашифрований текст має розмір у два рази більше вихідного. Для дешифрування виробляється обчислення:
M = b/ax mod p
Проблема дискретного логарифма полягає в тому, що, знаючи підставу степені і отриманий після зведення результат по модулю простого числа, неможливо за поліноміальний час визначити, в яку саме степінь було зведено основу. У схемі Ель Гамаля потенційний зловмисник може отримати значення a, р, (aхmodp) і (ауmodp). Однак через складності визначення чисел х і у "в чистому вигляді" у нього не виявляється можливості обчислити значення
k= (aхуmodp), яке йому так необхідно для прочитання шифровки.
Щодо числа р криптоаналіз висуває таку вимогу. Число (р-1) має містити в розкладанні на множники великий простий дільник. У деяких протоколах з участю схеми Ель Гамаля р вибирається як (qх2+1), де q-просте число (число р в цьому випадку називається простим). При виборі хіуполучателем і відправником відповідно, природно, має виконуватися вимога до їх інформаційної ємності. Для генерації цих чисел повинен використовуватися або ГВЧ-генератор "дійсно" випадкових чисел (не ГПСЧ), або криптостійкий генератор псевдовипадкових чисел (КПТСЧ). В іншому випадку зловмисник просто визначить х або у повним перебором.
Всі користувачі інформаційного простору можуть використовувати одну і ту ж пару підстави кінцевого поля р і породжує елемента а - це дозволяє не включати ці параметри у відкритий ключ, а також використовувати передобчислювання (кешування) для значного прискорення алгоритму. Однак для кожного повідомлення повинно використовуватися нове значення у, в іншому випадку з'являється можливість по одному відомому повідомленню прочитати всі інші.
За криптостійкість у схемі Ель Гамаля 512-бітове число р прирівнюється до 56-бітного симетричного ключа, про який вже склалося однозначну думку. Тому на практиці застосовуються р довжиною в 768, 1024 і 1536 біт.