1976 рік вважається роком народження несиметричної криптографії. Цього року американськими математиками Вайтфілдом Діффі, Мартіном Хеллманом і Ральфом Меркле була представлена ідеологія криптосистеми з відкритим ключем.

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

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

В теперішній час в несиметричній криптографії найбільше поширення набули системи RSA, Ель-Гамаля і Ель-Гамаля на еліптичних кривих.

Схема RSA

RSA – криптографічна система відкритого ключа, що забезпечує такі механізми захисту як шифрування і цифровий підпис. Криптосистема RSA розроблена в 1977 році і названа на честь її розробників Ronald Rivest, Adi Shamir і Leonard Adleman.

Алгоритм RSA працює таким чином: беруться два досить великих простих числа p і q та обчислюється їх добуток n = p*q; n називається модулем.

Потім вибирається число e, що задовольняє умові 1< e < (p - 1)*(q - 1) і що не має загальних дільників окрім 1 (взаємно просте) з числом (p - 1)*(q - 1).

Потім обчислюється число d таким чином, що (e*d - 1) ділиться на (p - 1)*(q – 1),  де

e – відкритий (public) показник,

d – секретний (private) показник.

Пара (n; e) є відкритим (public) ключем, а (n; d). – особистим (private) ключем.

Дільники p і q можна або знищити, або зберегти разом з особистим (private) ключем.

Якби існували ефективні методи розкладання на співмножники (факторизація), то, розклавши n на співмножники p та q, можна було б отримати секретний (private) ключ d. Таким чином, надійність криптосистеми RSA заснована на важко вирішуваному завданні розкладання n на співмножники (тобто на неможливості факторизації n) оскільки в даний час ефективного способу пошуку співмножників не існує.

Нижче описується використання системи RSA для шифрування інформації (відзначимо, що створення цифрових підписів на основі RSA трохи відрізняється - практичне використання; про створення цифрових підписів на основі RSA можна прочитати на сторінці «Цифровий підпис» поточного розділу).

Припустимо, Кореспондент 1 хоче послати Кореспондентові 2 повідомлення M. Для цього Кореспондент 1 створює зашифрований текст З, підносячи повідомлення M до ступеня e і умножаючи на модуль n: C = M**e* (mod n), де e та n – відкритий (public) ключ Кореспондента 2. Потім Кореспондент 1 посилає С (зашифрований текст) Кореспондентові 2. Щоб розшифрувати отриманий текст, Кореспондент 2 підносить отриманий зашифрований текст C до ступеня d і умножає на модуль n: M = c**d*(mod n); залежність між e та d гарантує, що Кореспондент 2 обчислить M вірно. Оскільки лише Кореспондент 2 знає d, то лише він має можливість розшифрувати отримане повідомлення.

Схема Ель- Гамаля

Схема Ель-Гамаля, запропонована в 1985 р., може бути використана як для шифрування, так і для цифрового підпису. Безпека схеми Ель-Гамаля обумовлена складністю обчислення дискретного логарифма в кінцевому полі.

Для того, щоб згенерувати ключову пару (відкритий ключ і особистий ключ), спочатку вибирають деяке велике просте число Р і велике ціле число G, причому G < Р. Числа Р і G можуть бути поширені серед групи користувачів.

Потім вибирають випадкове ціле число X, причому Х<Р. Число Х є секретним ключем і повинно зберігатися в секреті.

Далі обчислюють Y = GX mod P. Число Y є відкритим ключем.

Для того, щоб зашифрувати повідомлення М, вибирають випадкове ціле число К, 1<К<Р -1, таке, що числа К та (Р-1) є взаємно простими.

Потім обчислюють числа

a = G^{K (}mod P),

b = Y^K М (mod P).

Пара чисел (а,b) є шифртекстом. Відмітимо, що довжина шифртекста вдвічі більше довжини вихідного відкритого тексту М.

Для того, щоб розшифрувати шифртекст (а, b), обчислюють

М = b / a^X (mod Р). (*)

Оскільки

b / a^X = Y^K M / a^X = G^KX M / G^KX =M (mod P),

тому співвідношення (*) справедливе.

У реальних схемах шифрування необхідно використовувати як модуль Р велике ціле просте число, яке має у двійковому вигляді довжину 512 - 1024 біти.