Шифр Ель Гамаля

Надійний та зручний для реалізації на персональних комп’ютерах алгоритм цифрового
підпису був розроблений у 1984 році американцем арабського походження Тахером Ель
Гамалем. У 1991 році Національний інститут стандартів (НІСТ) США обґрунтував перед
комісією Конгресу США вибір цього алгоритму як бази для відповідного національного
стандарту. Найменування EGSA має походження від слів El Gamal Signature Algorithm
(алгоритм цифрового підпису Ель Гамаля).
Ідея EGSA базується на тому, що для практичної неможливості фальсифікації ЕЦП може
бути використана практично нерозв’язувана задача дискретного логарифмування.

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

Р = 13, А = 7.
Я підписую своє повідомлення m=1 цифровим підписом, сформованим по алгоритму Ель Гамаля. Обираю собі закритий ключ Х1=3 і формую  відкритий ключ: Y1 = 7^3 mod 13 = 5. Відкритий ключ передаю партнерам.

Потім обираю випадкове секретне число, взаємно просте з Р-1. Нехай k=7. Далі обчислюю число a = A^k mod P = 7^7 mod 13 = 6
Потім за допомоою алгоритму Евкліда знаходжу  b в рівнянні:
m = (X1 * а +k * b) mod (P-1) = 1=3*6+7*1 mod12
Рішенням  буде значення b=1.
Таким чином, пара чисел (6,1) буде цифровим підписом повідомлення  m=1.

При бажанні інший партнер може перевірити цифровий підпис в повідомленні: він отримує мій відкритий ключ та обчислює  с1 і с2 і порівнює їх.
с1=Y1^a * a^b mod P=5^6 * 6^8 mod 13=10,

c2= A^m mod P= 7^2mod 13= 10
Якщо с1 = с2, то цифровий підпис в повідомленні m=1 вірний.

Алгоритм «Луна»

Алгоритм «Луна» (англ. Luhn Algorithm) — алгоритм обчислення контрольної цифри номера пластикових карт відповідно до стандарту ISO / IEC 7812. Алгоритм був розроблений німецьким комп’ютерним фахівцем Гансом Луном в 1954-му році.

Алгоритм «Луна»  використовує просте правило обчислення контрольної суми для перевірки ідентифікаційних номерів, таких як номера пластикових карт. Алгоритм був придуманий для визначення помилок при введенні номера. Алгоритм визначає помилки введення однієї неправильної цифри, а також майже всі перестановки сусідніх цифр, за винятком перестановки 09-90 або зворотної 90-09.

Найбільш поширені застосування для підрахунку контрольної цифри:

— Номери всіх банківських карт.

— Номери деяких дисконтних карт.

— Коди соціального страхування.

— IMEI-коди.

— MEID (модифікований алгоритм).

Алгоритм перевірки контрольної цифри (оригінальний алгоритм, описаний розробником):

Цифри картки нумеруються з кінця

Цифри, що опинилися на непарних місцях, залишаються без змін.

Цифри, що стоять на парних місцях, множаться на 2.

Якщо в результаті такого множення виникає число більше 9, воно замінюється сумою цифр отриманого добутку.

Всі отримані в результаті перетворення цифри сумуються.

Якщо сума кратна 10, то карта валідна. Інакше – карта невалідна

Приклад:

Номер картки:        

6

7

6

2

4

6

6

0

0

2

5

4

9

8

6	7	6	2	4	6	6	0	0	2	5	4	9	8	3	8
16	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1
12	7	12	2	12	6	60	0	0	2	10	4	18	8	6	8
3	7	12	2	12	6	6	0	0	2	1	4	9	8	6	8
3	7	3	2	3	6	6	0	0	2	1	4	9	8	6	8	70

Сума останньої колонки = 70. Отже, карта валідна

Алгоритм RSA

Опис RSA було опубліковано у 1977 році Рональдом Райвестом, Аді Шаміром і Леонардом Адлеманом з Масачусетського Технологічного Інституту (MIT).
Безпека алгоритму RSA побудована на принципі складності факторизації цілих чисел.

Алгоритм використовує два ключі — відкритий (public) і секретний (private), разом відкритий і відповідний йому секретний ключі утворюють пари ключів (keypair). Відкритий ключ не потрібно зберігати в таємниці, він використовується для шифрування даних. Якщо повідомлення було зашифровано відкритим ключем, то розшифрувати його можна тільки відповідним секретним ключем.

Криптостійкість алгоритму RSA ґрунтується на складності розкладання на множники великих чисел, а саме — на винятковій складності завдання визначити секретний ключ на підставі відкритого, так як для цього буде потрібно вирішити задачу про існування дільників цілого числа. Найбільш криптостійкі системи використовують 1024-бітові і великі числа.

Алгоритм складається з наступних кроків:

Крок 1.

Я підготовлюю публічний і приватний ключі.

Для цього обираю p і q. Нехай p=3 і q=11.

Для обчислення n множу p і q. Тому n=33.

Потім обчислюю φ за функцією Ейлера. (p-1) × (q-1)=2*10=20. Тому φ=20.

Далі з вибираю експонетну. Нехай е=3.

Відкритими ключами є {е, n} = {3, 33}. Відкритий ключ я відправляю партнерові.

Потім я маю отримати закритий ключ.  

Для цього знаходжу d з рівності e*d mod φ=1. Підставляю 3*d mod20=1. Тобто 3*d/20=… (остача 1).  Тут d=7.

Пара {d, n} = {7, 33} – закритий ключ. Його потрібно тримати в секреті. Тільки я зможу розшифрувати те, що було зашифровано відкритим ключем.

Крок 2.

Тепер Таня-партнер знає мій відкритий ключ {e, n} = {3, 33} і шифрує повідомлення. Нариклад, повідомлення Р, при Р<n. Нехай P=25.

При цьому, Таня здійснює шифрування за формулою:

Е= Р^еmod n

Е=25³mod33=15625mod33 і це = остачі від ділення 15625 на 33 = 16. Тобто Е=16 Таня відправляє мені.

Крок 3.

Я отримала дані, відправлені партером ( E = 16 ) і маю закритий ключ {d, n} = {7, 33}  і починаю розшифровку за формулою:

Р1=Е^d mod n=16⁷ mod33= 268435456 mod33 і це = остачі від ділення 268435456 на 33. Тобто Р1=25

Порівняння алгоритмів RSA та Деффі – Хеллмана

RSA — криптографічна система з відкритим ключем. RSA став першим алгоритмом такого типу, придатним і для шифрування і для цифрового підпису.  Безпека алгоритму RSA заснована на труднощі вирішення задачі розкладання чисел на прості множники. Основними перевагами RSA є:

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

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

Основні недоліки:

невисока швидкість роботи. АлгоритмRSA працює повільніше симетричного алгоритмуDES.

Алгоритм Діффі-Хеллмана (англ. Diffie-Hellman, DH) — алгоритм, що дозволяє двом сторонам отримати загальний секретний ключ, використовуючи незахищений від прослуховування, але захищений від підміни, канал зв’язку. Цей ключ може бути використаний для шифрування подальшого обміну за допомогою алгоритму симетричного шифрування.

Алгоритм Деффі-Хеллмана генерує секретний ключ для симетричного шифрування (“секретний ключ”).

Алгоритм RSA генерує пару секретний/відкритий ключ для асиметричного шифрування (“відкритий ключ”).

АЛГОРИТМ ДЕФФІ-ХЕЛЛМАНА + шифр ЦЕЗАРЯ

Маючи спільний секретний ключ 13, ми з Танею можемо спілкуватись, використовуючи шифрування за алгоритмом Цезаря, при цьому, не ризикуючи, що хтось  третій зможе дізнатись ключ. Наприклад, ми можемо зашифрувати текст «химери»:

АЛГОРИТМ ДЕФФІ-ХЕЛЛМАНА

Спочатку я і Таня публічно визначаємо параметри генератора g і простого модуля p, які є простими числами.

Потім я вибираю випадкове приватне число – 5.

І вираховую 3⁵mod17=243 mod17=5, тобто, моїм публічним ключем є число 5. Відправляю його Тані.

Потім Таня вибирає своє випадкове приватне число – 4.

І вираховує 3⁴mod17=81mod17=13, тобто публічним числом Тані є число 13. Відправляє його мені.

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

13⁵mod17= 371293mod17=13.

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

5⁴mod17=625mod17=13

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

ПРОСТІ КРИПТОАЛГОРИТМИ

ПРОСТІ КРИПТОАЛГОРИТМИ

Шифр Цезаря — один з найдавніших шифрів, симетричний алгоритм шифрування підстановками. Використовувався римським імператором Юлієм Цезарем для приватного листування. При шифруванні кожен символ замінюється іншим, віддаленим від нього в алфавіті на фіксоване число позицій, наприклад: при зсуві +3, A стало б D, B стало б E і так далі. Шифр Цезаря можна класифікувати як шифр підстановки, при більш вузької класифікації — шифр простої заміни.

Припустимо, що, використовуючи шифр Цезаря, з ключем, який дорівнює 13, необхідно зашифрувати словосполучення "НАДРУКОВАНІ ХИМЕРИ ДУМКУ РОЗІГРІЮТЬ". 

Для цього зрушимо алфавіт так, щоб він починався з тринадцятої букви букви (Й). Отже, беручи вихідний алфавіт АБВГҐДЕЄЖЗИІЇЙКЛМНОПРСТУФХЦЧШЩЬЮЯ, і зміщуючи всі літери вправо на 3, отримуємо відповідність: Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь ЮЯ А Б В Г Ґ Д Е Є Ж З И І Ї, де Н=Щ, А=Й і т. д.

Використовуючи цю схему, відкритий текст "НАДРУКОВАНІ ХИМЕРИ ДУМКУ РОЗІГРІЮТЬ" перетворюється на "ЩЙОЯВЦЬЛЙЩФ ДУШПЯУ ОВШЦВ ЯЮТФМЯФҐБИ". Для того, щоб одержувач повідомлення міг відновити вихідний текст, необхідно повідомити йому, що ключ — 13.

Шифр Віженера — це метод шифрування буквеного тексту, з використанням ключового слова. Квадрат Віженера або таблиця Віженера, може бути використана для зашифровування і розшифровування.

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

Приклад

Текст: Фірчу/к Миро/слава /Ігорі/вна

Ключ: дзвін/д звін /дзвін/дзв

Зашифроване слово: щртдєп уїювуфвйн мїрюшєув

Шифр Вернама (або  схема одноразових блокнотів) — у криптографії, система симетричного шифрування, винайдена в 1917 році співробітниками AT&T Мейджором Джозефом Моборном і Гільбертом Вернамом. Шифр Вернама є єдиною системою шифрування, для якої доведена абсолютна криптографічна стійкість.

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

Приклад

Текст: скарб

Ключ: дзвін

Зашифроване слово: вувюо

Шифрування шрифтом Цезаря слів "НАДРУКОВАНІ ХИМЕРИ ДУМКУ РОЗІГРІЮТЬ"

Слова: НАДРУКОВАНІ ХИМЕРИ ДУМКУ РОЗІГРІЮТЬ
Алфавіт: А Б В Г  Ґ Д  Е Є ЖЗ И І Ї Й К Л М Н О П Р С Т У Ф ХЦ Ч Ш Щ Ь Ю Я.

Зсув на 13 літер: Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ ЬЮЯ А БВ Г Ґ Д Е Є Ж З И І Ї 

Зашифровані слова: ЩЙОЯВЦЬЛЙЩФ ДУШПЯУ ОВШЦВ ЯЮТФМЯФҐБИ