Метод RSA

Метод возведения в степень (метод Эль-Гамаля)

F(x) = x ^m mod n – прямое преобразование.

Эффективного алгоритма для обратной операции – извлечения корня m-ой степени по модулю n для произвольных m и n не найдено. Это проблема дискретного логарифмирования для больших чисел.

Один из методов использует алгоритм извлечения корня при известном разложении числа n на простые множители, это и позволяет отнести функцию F(x) к классу односторонних функций с «потайной лазейкой».

Метод укладки рюкзака(метод Меркле-Холлмана)

Реализацией задачи об укладке рюкзака является криптоалгоритм Меркле-Холлмана.

Пусть задан набор целых положительных чисел А=(а1,а2…аn) и известна некоторая величина Z. Задачей является нахождение таких чисел аi , если это возможно, сумма которых равна числу Z.

В простейшем случае это число Z указывает размер рюкзака , а каждое из чисел аi – размер предмета, который нужно уложить в рюкзак. Задачей является нахождение такого набора предметов, чтобы рюкзак был полностью заполнен.

Пример: Z=3231 и набор из 10 чисел А=(43, 129, 215, 473, 903,302, 561, 1165,697, 1523)

Заметим, что число Z получится при сложении только некоторых чисел аi.

В принципе решение может быть найдено полным перебором подмножеств А и проверкой , какая из ∑ аi равна числу Z. В нашем примере этот перебор состоит из 2¹⁰ комбинаций, включая пустое множество.

Решение Z= 3231= 129 + 473 +909 + 561 + 1165.

z-размер рюкзака, аi- вещи.

Самым популярным из асимметричных является метод RSA основанный на операциях с большими (скажем, 100-значными) простыми числами и их произведениями.

В 1976 году преподаватели Стэнфордского университета, Витфильд Диффи (Whitfield DifFie) и Мартин Хелман (Martin Heliman), предложили систему под названием «шифрование с применением открытого ключа». Этот метод предполагает наличие двух ключей при каждом сеансе кодирования и хорошо отрекомендовал себя даже в незащищенных сетях. Каждый пользователь создает два ключа. Каждый ключ представляет собой произвольный набор цифр объемом в некоторых случаях более чем в 500 цифр. Оба ключа связаны между собой таким образом, что сообщение можно зашифровать с помощью одного ключа и расшифровать с помощью другого, однако расшифровать сообщение с помощью ключа, использовавшегося для его зашифровки, нельзя.

В 1977 году три исследователя из Массачусетсского технологического института (MIT) разработали алгоритм для реализации метода криптографии на основе открытого ключа. Криптосистема получила название RSA, по первым буквам фамилий ее авторов — Рона Ривеста (Ron Rivest), Эйди Шамира (Adi Shamir) и Леонарда Эдлемана (Leonard Adleman) (http://www.rsa.org/).

Исследователи в примере своей первой публикации зашифровали фразу из драмы «Юлий Цезарь» В. Шекспира «ITS ALL GREEK TO ME», она сначала была записана в виде целого числа Х стандартным способом (A=01, B=02,…..Z=26,пробел =00), затем зашифрована

X^e mod m, где m – 129-разрядное целое число, e=9007.

Шифротекст и числа e и m были опубликованы.

Конечно, многие математики пытались найти способ раскрыть алгоритм криптосистемы с открытым ключом с помощью вычислений (часто весьма объемных), однако пока что никому не удалось найти решение этой математической проблемы. Декодирующие программы используют метод «грубой силы», проверяя все возможные комбинации. Теоретически такой подход позволяет добиться успеха, однако необходимый объем вычислений делает такой вариант нереальным при условии, конечно, что открытый ключ имеет достаточную длину.

Лишь в 1994 году через 17 лет фраза была расшифрована, для этого потребовалось 220 дней, были задействованы 600 человек и 1600 компьютеров, соединенных через Интернет.

Этапы реализации алгоритма RSA:

1. Получатель выбирает два очень больших простых числа P и Q и вычисляет два произведения N = PxQ M = (P – 1)x(Q – 1)

2. Затем выбирается случайное число E, взаимно простое с M и вычисляется D, удовлетворяющее условию (ExD = 1) mod M

3. Получатель публикует E и N, как свой открытый ключ, сохраняя D, как секретный ключ.

4. Отправитель сообщение X представляет в виде набора блоков x_i

X = (x₁, x₂, ……x_l), 0 < x_i < M, затем шифрует его с использованием E и N.

5. Каждое x_i возвести в степень E по модулю N, получится шифрованное сообщение: (x₁ ^E mod N), (x₂ ^E mod N),……. (x₁ ^E mod N)

6. Для расшифрования полученного сообщения Получатель, используя свой секретный ключ D, вычисляет для каждого блока (x_i ^ED mod N), т.к. (ExD = 1) mod M, то утверждается x_i ^ED mod N = x_i

Алгоритм RSA может быть использован :

1. как самостоятельное средство шифрования данных в системе с открытым ключом;

2. как средство аутентификации пользователей в системах ЭП;

3. как средство для распределения ключей в составных системах.