Невидимая война

Ara (ara@cracklab.ru)

Хакер, номер #085, стр. 085-064-6

К тому же наука не стоит на месте, математики и криптографы постоянно ведут работу по изучению стойкости криптоалгоритмов. Было, к примеру, выявлена некоторая закономерность в распределении простых чисел. Замечено, что простые числа располагаются на числовой оси своего рода скоплениями, что может немного облегчить их поиск. Но пока алгоритм RSA остается одним из самых стойких алгоритмов шифрования.

[что такое RSA]

Немного теории. Алгоритм RSA носит такое название благодаря своим создателям, по первым буквам их фамилий - Rivest, Shamir, Adleman. В настоящее время это один из самых популярных несимметричных криптоалгоритмов. Ключи шифрования вычисляются, как функции двух больших простых чисел, то есть чисел, делящихся только на себя и на единицу. Предполагается, что восстановление исходного текста по шифротексту и закрытому ключу эквивалентно разложению на множители двух больших чисел. Использование достаточно больших чисел делает алгоритм надежным и криптостойким. Формирование открытого и закрытого ключей описывается следующим алгоритмом:

1. Фиксируются два простых числа p и q

2. Вычисляется их произведение n=p*q

3. Выбирается число e, меньшее n, являющееся взаимно простым с числом (p-1)(q-1)

4. По методу Евклида подбираются целые числа d и y, удовлетворяющие уравнению e*d-1=(p-1)(q-1)*y

5. Пара чисел (e,n) - это открытый ключ, которым шифруется текст

6. Число d - закрытый ключ, он храниться в секрете; с его помощью читаются все сообщения.

При шифровании исходный текст рассматривается как числовой ряд, и над каждым его числом совершается операция С(i)=(M[i]^e) mod n.

Более подробно про алгоритм RSA, а также многих других можно прочитать в книге известного специалиста в криптографической науке Брюса Шнайера «Прикладная криптография», переведенной на русский язык.

А мы пока разберем работу алгоритма RSA на очень простом примере. Выберем p=3, q=7 - два взаимно простых числа, правда, маленьких, но это нам нужно только для разбора работы алгоритма. Соответственно, n будет равно 21 (3*7). Установим e=5 - взаимно простое с результатом (3-1)*(7-1)=12. Тогда отыскать несколько пар (d,y) несложно: к примеру, (5,2) или (17,7). Мы для интереса возьмем вторую пару.

Закрытый ключ в этом случае будет числом 17, а открытый - парой чисел (5,21).

Возьмем последовательность M={1,2,3,4,5} и зашифруем ее с помощью открытого ключа:

С(1)=1^5 mod 21 = 1

C(2)=2^5 mod 21 = 11

C(3)=3^5 mod 21 = 12

C(4)=4^5 mod 21 = 16

C(5)=5^5 mod 21 = 17

Получилась последовательность C={1,11,12,16,17}. Это и есть криптотекст. Дешифрование проводится аналогично шифрованию, только при этом используется закрытый ключ. При использовании достаточно больших чисел достигается значительная криптостойкость RSA. Единственный способ взлома этого алгоритма (то есть нахождения закрытого ключа) является так называемая brute-force атака, проще говоря, метод последовательного перебора. Однако сразу стоит заметить, что при достаточно больших (свыше 256 байт) выбранных числах этот перебор может затянуться на долгие-долгие годы.