 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Задача дискретного логарифмування формулюється в такий спосіб
Для відомих цілих 
знайти ціле число 
, таке, що
.
Алгоритм обчислення дискретного логарифма за прийнятний час поки не знайдена, тому модульна експонента вважається односпрямованою функцією.
За сучасними оцінками теорії чисел при досить великих цілих числах A 2664 й N 2664 рішення задачі дискретного логарифмування (знаходження показника ступеня для відомого 
) потребує близько 1026 операцій, тобто ця задача має в 103 разів більшу обчислювальну складність, ніж задача розкладання на множники. Різниця в оцінках складності задач зростає при збільшенні довжини чисел.
Відзначимо, що поки не вдалося довести, що не існує ефективного алгоритму обчислення дискретного логарифма за прийнятний час. Виходячи з цього, модульна експонента віднесена до односпрямованих функцій умовно, що однак не заважає з успіхом застосовувати її на практиці.
Другим важливим класом функцій, що використовуються при побудові криптосистем з відкритим ключем, є односпрямовані функції з "потаємним ходом".
Функція 
належить до класу односпрямованих функцій з "потаємним ходом" у тому випадку, якщо вона є односпрямованою й, крім того, можливо ефективне обчислення зворотної функції, якщо відомо "потаємний хід" (таємне число, рядок або інша інформація, що асоціюється з даною функцією).
Як приклад односпрямованої функції з "потаємним ходом" можна вказати модульну експоненту з фіксованими модулем і показником ступеня, що використовується в криптосистемі RSA. Змінна основа модульної експоненти використовується для вказівки числового значення повідомлення М або криптограми С.
7. Требования, предъявляемые к ассиметрическим криптосистемам
Асиметричні алгоритми шифрування— алгоритми шифрування, які використовують різні
ключі для шифрування та дешифрування даних.
· RSA — криптографічна система з відкритим ключем. RSA став першим алгоритмом такого
типу, придатним і для шифрування, і для цифрового підпису. Алгоритм використовується у великій
кількості криптографічних додатків
1. Обирається два числа: p та q - прості числа
2. Вираховується добуток n=p*q - модуль
3. Вираховується значення функції Ейлера від n:
4. Обирається число e: (1 < e < φ(n)), взаємно просте зі значенням φ(n)
5. Вираховується число d, обернене до числа e за mod φ(n), тобто:
,
k -ціле число 6. Відкритий ключ RSA: P=(e, n)
7. Секретний ключ RSA: S=(d, n)
Асиметричны системи були винайдені, щоб:
1)Не передавати ключ
2)Для генерації ЕЦП
Характерні риси:
- відкритий ключ К та зашифрований С можуть передаватись по незахищеним каналам.
- алгоритми шифрування та дешифрування є вдкритими
- захищеність інформації заснована на захищеності таємного ключа.
Вимоги:
Обчислення KA і KВ yf стороні одержувача повинно бути простим
Знаючи відкритий ключ можна легко обчислити і повідомлення можна легко знайти криптограму С
Одержувач знаючи криптограму і закритий ключ може легко відновити повідомлення М.
Зловмисник знаючи KA на мрже обчислити KВ
Ключі можуть викор. В будь-якому порядку
Приклад: RSA, Асиметр. Схема Ель-Гамаля.
8. Шифр RSA
Послідовність дій користувача В і користувача А:
1. Користувач В вибирає два довільних великих простих числа Р і Q;
2. Користувач В обчислює значення модуля N:
.
3. Користувач В обчислює функцію Ейлера (8):
.
4. Користувач В випадково вибирає значення відкритого ключа КA з урахуванням виконання умов:
, 
.
5. Користувач В обчислює значення секретного ключа КB, використовуючи розширений алгоритм Евкліда при розв’язуванні порівняння
.
6. Користувач В пересилає користувачеві А пару чисел
(N, КA) незахищеним каналом.
Якщо користувач А хоче передати користувачеві В повідомлення М, він виконує такі кроки:
- користувач А розбиває вихідний відкритий текст М на блоки, кожний з яких може бути поданий у вигляді числа
Мi= 0,1,2,..., N -1;
- користувач А шифрує текст, поданий у вигляді послідовності чисел Мi, за формулою
;
- користувач А відправляє криптограму
C 1, С 2, С 3,..., Ci,... користувачеві В;
- користувач В розшифровує прийняту криптограму
C 1, С 2, С 3,..., Ci,...,
використовуючи секретний ключ КB, за формулою
.
У результаті буде отримана послідовність чисел Mi, яка являє собою вихідне повідомлення М. Щоб алгоритм RSA мав практичну цінність, необхідно мати можливість без істотних витрат генерувати великі прості числа, уміти оперативно обчислювати значення ключів
КA і КB.
ПРИКЛАД
Необхідно зашифрувати повідомлення “КНИГА”, яке складається з символів українського алфавіту, за допомогою алгоритму RSA.
Виконаємо зашифрування відкритого тексту.
Дії користувача В.
Для простоти обчислень будуть використовуватися невеликі числа. На практиці застосовуються дуже великі числа.
Нехай Р = 3 і Q =11, тоді N =33. Обчислимо значення функції Ейлера для N=33, отримаємо:
.
Виберемо у якості відкритого ключа КA =3 і перевіримо виконання умов (3), (4):
.
Обчислюємо значення секретного ключа КB відповідно до формули (5)
.
Розв’язуючи вищевказане порівняння, одержуємо КB =7, тому що
.
Передаємо користувачеві А пару чисел (N =33, KA =3).
Дії користувача А.
Повідомлення, яке буде шифруватися і складається з символів українського алфавіту, представляється як послідовність цілих чисел у діапазоні 0...32. Кожному символу відповідає ціле число. Таким чином, відкритий текст «КНИГА» буде послідовністю чисел
М ={14, 17, 10, 3, 0}.
Виконаємо зашифрування тексту, представленого у вигляді послідовності чисел M, використовуючи ключ К A = 3 і N = 33, за формулою
.
В результаті отримаємо:
Відправляємо користувачеві В криптограму C ={5, 29, 10, 27, 0}.
Виконаємо розшифрування шифртексту.
Дії користувача В.
Розшифруємо прийняту криптограму C, використовуючи секретний ключ К B=7, за формулою
.
У результаті одержуємо:
Таким чином, відновлене вихідне повідомлення
М ={14, 17, 10, 3, 0}відповідає символьному повідомленню "КНИГА".
9. Шифр Полига –Хеллмана
Схема шифрования Полига - Хеллмана сходна со схемой шифрования RSA. Она представляет собой несимметричный алгоритм, поскольку используются различные ключи для шифрования и расшифрования. В то же время эту схему нельзя отнести к классу криптосистем с открытым ключом, так как ключи шифрования и расшифрования легко выводятся один из другого. Оба ключа (шифрования и расшифрования) нужно держать в секрете.
Аналогично схеме RSA криптограмма С и открытый текст Р определяются из соотношений
С = Рe mod n,
Р = Сd mod n,
где e*d 1 (по модулю некоторого составного числа).
В отличие от алгоритма RSA в этой схеме число n не определяется через два больших простых числа; число n должно оставаться частью секретного ключа. Если кто-либо узнает значения е и n, он сможет вычислить значение d.
Не зная значений е или d, противник будет вынужцен вычислять значение
е = log P С (mod n).
Известно, что это является трудной задачей. Схема шифрования Полига - Хеллмана запатентована в США и Канаде.
10. Ассиметрическая криптоситема Рабина
Криптосистема Рабина – криптографический алгоритм с открытым ключом. Ее безопасность, как и у RSA, связана с трудностью разложения на множители.
Безопасность схемы Рабина опирается на сложность поиска квадратных корней по модулю составного числа. Сложность этого алгоритма аналогична проблеме разложения на множители.
Главным неудобством практического применения криптосистемы Рабина является то, что при расшифровке текста получается четыре различных сообщения. И нужно применить дополнительные усилия для нахождения истинного исходного текста.
Генерация ключа
Как любая асимметричная криптосистема, система Рабина использует и открытый и закрытый ключи. Открытый ключ необходим для шифрования документов и может быть опубликован для всеобщего обозрения. Закрытый ключ должен быть известен только получателям зашифрованных сообщений.
Процесс генерации ключей следующий:
Выбираются два больших простых числа p и q, которые удовлетворяют условию 
Такой специальный вид простых чисел сильно ускоряет процедуру извлечения корней по модулю р и q.
Тогда 
n - открытый ключ. Числа p и q - закрытый ключ.
Для шифрования сообщения необходим открытый ключ n. Чтобы расшифровать зашифрованный текст нужны p и q.
Рассмотрим простой пример. Пусть p = 7 и q = 11, тогда n = 77. Открытый ключ, 77, публикуется для всеобщего обозрения, с помощью его шифруются сообщения. Закрытые ключи, 7 и 11, остаются известы только владельцу, и с помощью их расшифровываются сообщения. Такой выбор ключей – хорошо подходит для примера. Но плохой для практического использования, т.к. разложение на множители 77 тривиально.
Шифрование
Для шифрования используется только открытый ключ n. С помощью его исходный текст преобразовывается в зашифрованный. Для шифрования сообщения m нужно просто вычислить:
Таким образом, шифрование состоит из операции умножения по модулю N, что обеспечивает более высокую скорость шифрования, чем в RSA, даже если в последней выбирают небольшую шифрующую экспоненту.
В нашем примере. Пусть исходным текстом является m = 20. Тогда зашифрованным текстом будет:
Расшифрование
Расшифрование в этом алгоритме более сложное. Для него нужен закрытый ключ p и q. Процесс выглядит следующим образом:
Сначала, используя алгоритм Эвклида, из уравнения 
находим числа yp и yq.
Далее, используя китайскую теорему об остатках, можно вычислить числа
Один из этих корней r, -r, s, -s является истинным открытым текстом m.
Вернемся в нашему примеру: В результате расшифровки получаем: 
Видим, что один из корней является исходным текстом m.
11. Ассиметрическая криптосистема Эль Гамаля
Схема Эль-Гамаля — криптосистема с открытым ключом,основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи.
Генерация ключей:
- Генерируется случайное простое число Р длины битов n.
- Выбирается произвольное целое число G, являющееся первообразным корнем по модулю P.
- Выбирается случайное целое число KB (секретный ключ) такое, что 1 < KB < P.
- Вычисляется открытый ключ 
.
Шифрование:
- Имеем сообщение M.
- Выбирается сессионный ключ — случайное целое число K, такое, что 
- Вычисляются числа 
- Пара чисел (a,b) является шифротекстом.
Расшифрование:
Зная закрытый ключ KB, исходное сообщение можно вычислить из шифротекста (a,b) по формуле:
12. Хэш-функции
Хеширование — преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки, а их результаты называют хешем, хеш-кодом или дайджестом сообщения.
Хеширование применяется для сравнения данных: если у двух массивов хеш-коды разные, массивы гарантированно различаются; если одинаковые — массивы, скорее всего, одинаковы.
Классы хеш-функций:
- бесключевые хеш-функции (хеш-функции на вход которых подается только сообщение) – к ним относятся коды обнаружения изменений сообщения (MDC-код, modification detection code).
- ключевые хеш-функции (хеш-функции на вход которых подается сообщение и секретный ключ) – к ним MAC-коды.
Бесключевые хеш-функции делятся на:
- Односторонняя хеш-функция
- Свободная от столкновения хеш-функция
Классификация хеш-функций по используемым внутренним преобразованиям:
- на основе какой-либо трудновычисляемой математической задачи;
- на основе алгоритмов блочного шифрования;
- разработанные с нуля.
13. Требования, предъявляемые к хеш-функциям
функції хешування полягає в тому, щоб одержати «дактилоскопічну» характеристику відкритого тексту М. Для цього функція хешування повинна мати такі властивості:
1) бути прийнятною до блоку будь-якої довжини;
2) на виході давати значення фіксованої довжини;
3) дайджест h=Н(x) повинен обчислюватися легко для будь-якого заданого значення x, а алгоритм обчислення повинен бути практичним з погляду як апаратної, так і програмної реалізації;
4) для будь-якого даного дайджесту h практично неможливо обчислити x, для якого H(x)=h. Таку властивість називають однобічністю;
5) для будь-якого блоку x практично неможливо обчислити y¹x, для якого H(x)=H(y). Таку властивість називають слабкою опірністю колізіям;
6) практично неможливо обчислити будь-яку пару різних x та y, для яких 
. Таку властивість називають сильною опірністю колізіям.
Те що далі по цьому питанні не важливо.Просто якощо комусь потрібно більш детельне пояснення.
Необхідно зазаначити, що властивості 1-3 описують вимоги, що забезпечують можливість практичного застосування функції хешування для аутентифікації повідомлень. Властивість 4 забезпечує однобічність: легко одержати код на основі наявного повідомлення, але практично неможливо відтворити повідомлення. Це важливо, коли алгоритм аутентифікації припускає використання таємного значення S. Саме значення S не посилається, але якщо хеш-функція не є однобічною, зловмисник може легко визначити таємне значення, досить спостерігати або перехоплювати потік даних, щоб одержати повідомлення М та дайджест 
. Потім зловмисник розгляне функцію, зворотну функції хешування та одержить 
. Тепер, коли зловмисник має 
та 
легко відновити таємне значення S.
Властивість 5 гарантує, що не вдасться знайти інше повідомлення, що дає в результаті хешування те саме значення, що й дане повідомлення. Це запобігає можливості фальсифікації повідомлень у тому випадку, коли виконується шифрування хеш-кода (у способах застосування хеш-кода 2 і 3. У такій ситуації зловмисник може прочитати повідомлення та обчислити відповідний хеш-код. Однак, він не має таємного ключа, а тому не може змінити повідомлення так, щоб цього не було виявлено. Якщо ця властивість не виконана, зловмисник може діяти в такий спосіб: спочатку перехоплюється повідомлення разом із приєднаним до нього дайджестом, потім обчислюється нешифрований хеш-код повідомлення і нарешті створюється альтернативне повідомлення з тим самим хеш-кодом.
Властивість 6 гарантує захист від атак на основі парадокса задачі про дні народження.
14. Хеш-функция SHA-1
Поиск по сайту: