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

Надійний та зручний для реалізації на персональних комп’ютерах алгоритм цифрового
підпису був розроблений у 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 літер: Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ ЬЮЯ А БВ Г Ґ Д Е Є Ж З И І Ї 

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

Шифрування шрифтом Цезаря ПРІЗВИЩА ІМ'Я ПО-БОТЬКОВІ

ПІБ: Фірчук Мирослава Ігорівна

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

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

Зашивроване ПІБ: ГФЯЕВЦ ШУЯЬАЧЙЛЙ ФМЬЯФЛЩЙ

Криптографія: загальні визначення, Класифікація

Криптографія – це практика і вивчення методів безпечного спілкування в присутності третіх осіб (так званих противників). У більш загальному понятті, мова йде про побудову та аналізу протоколів, які дозволяють подолати вплив противників і які пов’язані з різними аспектами в області інформаційної безпеки, таких як конфіденційність даних, цілісність даних, аутентифікації і безвідмовності. Сучасна криптографія перетинає дисципліни математики, інформатики та електротехніки. Застосування криптографії включають наступне: банківські карти, комп’ютерні паролі і електронну комерцію, та інше.
В криптографичній термінології вихідне повідомлення називають відкритим текстом (plaintext або cleartext). Зміна вихідного тексту так, щоб скрити від інших його склад, називають шифруванням (encryption). Зашифроване повідомлення називають шифротекстом (ciphertext). Процес, при якому із шифротексту видаляється відкритий текст називають дешифруванням (decryption). Переажно в процесі шифрування і дешифрування використовується деякий ключ (key) і алгоритм забезпечує, що дешифрування можна зробити лише знаючи ключ.
Криптографія – це наука про те, як забезпечити секретність повідомлення. Криптоаналіз – це наука про те, як відкрити шифроване повідомлення, так як відкрити текст не знаючи ключ. Криптографією займаються криптографи, а криптоаналізом займаються криптоаналітики.

Асиметричні алгоритми шифрування – алгоритми шифрування, які використовують різні ключі для шифрування та розшифрування даних. Головне досягнення асиметричного шифрування в тому , що воно дозволяє людям, що не мають існуючої домовленості про безпеку, обмінюватися секретними повідомленнями. Необхідність відправникові й одержувачеві погоджувати таємний ключ по спеціальному захищеному каналі цілком відпала. Процедура шифрування обрана так, що вона необоротна навіть по відомому ключу шифрування. Тобто, знаючи ключ шифрування й зашифрований текст, неможливо відновити вихідне повідомлення – прочитати його можна тільки за допомогою другого ключа – ключа дешифрування. А раз так, то ключ шифрування для відправлення листів якій-небудь особі можна взагалі не приховувати – знаючи його однаково неможливо прочитати зашифроване повідомлення. Тому, ключ шифрування називають в асиметричних системах “відкритим ключем”, а от ключ дешифрування одержувачеві повідомлень необхідно тримати в секреті – він називається “закритим ключем”. Алгоритми шифрування й дешифрування створюються так, щоб знаючи відкритий ключ, неможливо було обчислити закритий ключ.
Симетричні алгоритми шифрування – спосіб шифрування, в якому для шифрування і дешифрування застосовується один і той же криптографічний ключ. До винаходу схеми асиметричного шифрування єдиним існуючим способом було симетричне шифрування. Ключ алгоритму повинен зберігатися в секреті обома сторонами. Алгоритми шифрування і дешифрування даних широко застосовуються в комп’ютерній техніці в системах приховування конфіденційної і комерційної інформації від не коректного використання сторонніми особами. Головним принципом у них є умова, що та приймає заздалегідь знають алгоритм шифрування, а також ключ до повідомлення, без яких інформація є всього лише набір символів, що не мають сенсу. Симетричні криптоалгоритми виконують перетворення невеликого (1 біт або 32-128 біт) блоку даних в залежності від ключа таким чином, що прочитати оригінал повідомлення можна тільки знаючи цей секретний ключ.

Асиметричні криптоалгоритми: Криптосистема з відкритим ключем;
Для шифрування повідомлення використовується відкритий ключ, а при дешифруванні – закритий. Тобто, знаючи ключ шифрування й зашифрований текст, неможливо відновити вихідне повідомлення;
При порушенні конфіденційності k-ої робочої станції зловмисник довідається тільки “закритий” ключ k : це дозволяє йому читати всі повідомлення, що приходять абонентові k, але не дозволяє видавати себе за нього при відправленні листів;
В асиметричних системах кількість існуючих ключів пов’язане з кількістю абонентів лінійно (у системі з N користувачів використовуються 2*N ключів).
Симетричні криптоалгоритми: Криптосистема з секретним ключем;
Секретний ключ використовується і для шифрування, і для дешифрування. Тобто, знаючи ключ шифрування й зашифрований текст, ви зможете дешифрувати повідомлення;
При порушенні конфіденційності якої-небудь робочої станції зловмисник одержує доступ до всіх ключів цього користувача й може відправляти, нібито від його імені, повідомлення всім абонентам, з якими “жертва” вела переписку;
В симетричних системах число ключів зростає квадратично із збільшенням числа користувачів.

Існують кілька способів, згідно з якими можуть бути класифіковані всі криптографічні системи. Часто за основу приймається наступна класифікація:
1. Криптосистеми обмеженого використання.
2. Криптосистеми загального використання;
- з секретним ключем;
- з відкритим ключем.