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

Алгоритм «Луна» (англ. 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

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