Система Райвеста, Шаміра, Адлемана

RSA — криптографічна система з відкритим ключем.

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

RSA став першим алгоритмом такого типу, придатним і для шифрування і для цифрового підпису. Алгоритм використовується у великій кількості криптографічних застосунків.

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

Припустимо, Боб хоче послати Алісі повідомлення (для прикладу повідомленням будуть цілі числа)

Алгоритм шифрування: 1. Взяти відкритий ключ (e, n) Аліси 2. Взяти відкритий текст m 3. Зашифрувати повідомлення з використанням відкритого ключа Аліси: c = E(m) = m^e mod n

Алгоритм дешифрування: 1. Взяти зашифроване повідомлення C 2. Взяти свій закритий ключ (d, n) 3. Використати закритий ключ для розшифрування повідомлення: m = D(c) = c^d mod n

RSA може використовуватися не тільки для шифрування, але й для цифрового підпису.

Система RSA використовується для захисту програмного забезпечення й у схемах цифрового підпису. Також вона використовується у відкритій системі шифрування PGP.

Класичні шифри

Шифр частоколу

Шифр ADFGVX

У роки І-ої світової війни з'явились системи, чи не найвідомішим представником яких є шифр ADFGVX, що застосовувався німецькою армією. ADFGVX є композицією двох шифрів — підстновки і перестановки. Наприклад повідомлення: DОN'TPUTITOFFTILLTOMORROW

Проміжний криптотекст: FXADFAXGVAGXXGGFXGADAVAVXGGFFFFFXG ADDAADVXVXADFD (шифрування лівим малюнком)

Шифр Цезаря

Це один з найбільш древніх відомих шифрів, яким, як можна припустити виходячи з його назви, користувався римський імператор Юлій Цезар. Суть шифру полягає в заміні кожної букви на букву, віддалену від її в алфавіті на 3 позиції вправо. Подібні шифри, засновані на заміні одних букв іншими, називаються підстановочні. Моноалфавитні шифри (до яких відноситься і шифр Цезаря) – це різновид символів шифрів, в якій кожній букві нешифрованих тексту завжди відповідає одна і та ж буква в зашифрованому тексті.

Наприклад текст «ATTACK» після шифрування вийде «DWWDFN»

Шифр Віженера

Шифр Віженера – шифр названий на честь Віженера, який у якості ключа використовує слово. Якщо пронумерувати літери алфавіту від 0 до 32 (а → 0, б → 1, в → 2, ...), то шифрування Віженера можна представити формулою Ci = (Pi + Kj) mod 33, де Kj - j-та літера ключового слова.

Табличне представлення:

• • • • • • • • • • • • • • • • • • • • • • • •

• • • • • • • • • • • • • • • • • • • • • • • •

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

Наприклад, відкритий текст: «поліалфавітнийшифр»

Ключ: «ключключключключкл»

Шифротекст: «аайдйщтцлхіучцхґдв».

Бінарний метод піднесення до степеня за модулем числа n

.

Система Діффі-Хелмана

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

Спочатку генеруються два великих простих числа n і q. Ці два числа не обов'язково зберігати в секреті. Далі один з партнерів P1 генерує випадкове число x і посилає іншому учаснику майбутніх обмінів P2 значення A = q^x mod n

Після отримання А партнер P2 генерує випадкове число y і посилає P2 обчислене значення B = q^y mod n

Партнер P1, отримавши В, обчислює K_x = B^x mod n, а партнер P2 обчислює K_y = A^y mod n. Алгоритм гарантує, що числа K_y і K_x рівні і можуть бути використані в якості секретного ключа для шифрування. Адже навіть перехопивши числа Аі В, важко обчислитиK_x абоK_y.