RSA
Алгоритм RSA стоит у истоков асимметричной криптографии. Он был предложен тремя исседователями-математиками Рональдом Ривестом (R.Rivest) , Ади Шамиром (A.Shamir) и Леонардом Адльманом (L.Adleman) в 1977-78 годах.
Первым этапом любого асимметричного алгоритма является создание пары ключей: открытого и закрытого и распространение открытого ключа "по всему миру". Для алгоритма RSA этап создания ключей состоит из следующих операций:
Выбираются два простых числа p и q.
Вычисляется их произведение n(=p*q).
Выбирается произвольное число e (e
Методом Евклида решается в целых числах (!) уравнение e*d+(p-1)(q-1)*y=1. Здесь неизвестными являются переменные d и y – метод Евклида как раз и находит множество пар (d,y), каждая из которых является решением уравнения в целых числах.
Два числа (e,n) – публикуются как открытый ключ.
Число d хранится в строжайшем секрете – это и есть закрытый ключ, который позволит читать все послания, зашифрованные с помощью пары чисел (e,n).
Как же производится собственно шифрование с помощью этих чисел:
Отправитель разбивает свое сообщение на блоки, равные k=[log2(n)] бит, где квадратные скобки обозначают, взятие целой части от дробного числа.
Подобный блок, как Вы знаете, может быть интерпретирован как число из диапазона (0;2k-1). Для каждого такого числа (назовем его mi) вычисляется выражение ci=((mi)e)mod n. Блоки ci и есть зашифрованное сообщение Их можно спокойно передавать по открытому каналу, поскольку. Операция возведения в степень по модулю простого числа, является необратимой математической задачей. Обратная ей задача носит название "логарифмирование в конечном поле" и является на несколько порядков более сложной задачей. То есть даже если злоумышленник знает числа e и n, то по ci прочесть исходные сообщения mi он не может никак, кроме как полным перебором mi.
А вот на приемной стороне процесс дешифрования все же возможен, и поможет нам в этом хранимое в секрете число d. Достаточно давно была доказана теорема Эйлера, частный случай которой утверждает, что если число n представимо в виде двух простых чисел p и q, то для любого x имеет место равенство (x(p-1)(q-1))mod n = 1. Для дешифрования RSA-сообщений воспользуемся этой формулой. Возведем обе ее части в степень (-y) : (x(-y)(p-1)(q-1))mod n = 1(-y) = 1. Теперь умножим обе ее части на x : (x(-y)(p-1)(q-1)+1)mod n = 1*x = x.
А теперь вспомним, как мы создавали открытый и закрытый ключи. Мы подбирали с помощью алгоритма Евклида d такое, что e*d+(p-1)(q-1)*y=1, то есть e*d=(-y)(p-1)(q-1)+1. А, следовательно, в последнем выражении предыдущего абзаца мы можем заменить показатель степени на число (e*d). Получаем (xe*d)mod n = x. То есть для того чтобы прочесть сообщение ci=((mi)e)mod n достаточно возвести его в степень d по модулю m : ((ci)d)mod n = ((mi)e*d)mod n = mi.
На самом деле операции возведения в степень больших чисел достаточно трудоемки для современных процессоров, даже если они производятся по оптимизированным по времени алгоритмам. Поэтому обычно весь текст сообщения кодируется обычным блочным шифром (намного более быстрым), но с использованием ключа сеанса, а вот сам ключ сеанса шифруется как раз асимметричным алгоритмом с помощью открытого ключа получателя и помещается в начало файла.
3.1.Технологии цифровых подписей
Как оказалось, теория асимметричного шифрования позволяет очень красиво решать еще одну проблему информационной безопасности – проверку подлинности автора сообщения. Для решения этой проблемы с помощью симметричной криптографии была разработана очень трудоемкая и сложная схема. В то же время с помощью, например, того же алгоритма RSA создать алгоритм проверки подлинности автора и неизменности сообщения чрезвычайно просто.
Предположим, что нам нужно передать какой-либо текст, не обязательно секретный, но важно то, чтобы в него при передаче по незащищенному каналу не были внесены изменения. К таким текстам обычно относятся различные распоряжения, справки, и тому подобная документация, не представляющая секрета. Вычислим от нашего текста какую-либо хеш-функцию – это будет число, которое более или менее уникально характеризует данный текст.
В принципе, можно найти другой текст, который дает то же самое значение хеш-функции, но изменить в нашем тексте десять-двадцать байт так, чтобы текст остался полностью осмысленным, да еще и изменился в выгодную нам сторону (например, уменьшил сумму к оплате в два раза) – чрезвычайно сложно. Именно для устранения этой возможности хеш-функции создают такими же сложными как и криптоалгоритмы – если текст с таким же значением хеш-функции можно будет подобрать только методом полного перебора, а множество значений будет составлять как и для блочных шифров 232–2128 возможных вариантов, то для поиска подобного текста злоумышленнику "потребуются" те же самые миллионы лет.
Таким образом, если мы сможем передать получателю защищенным от изменения методом хеш-сумму от пересылаемого текста, то у него всегда будет возможность самостоятельно вычислить хеш-функцию от текста уже на приемной стороне и сверить ее с присланной нами. Если хотя бы один бит в вычисленной им самостоятельно контрольной сумме текста не совпадет с соответствующим битом в полученном от нас хеш-значении, значит, текст по ходу пересылки подвергся несанкционированному изменению.
Представим теперь готовую к передаче хеш-сумму в виде нескольких k-битных блоков hi, где k – это размер сообщений по алгоритму RSA в предыдущем параграфе. Вычислим над каждым блоком значение si=((hi)d)mod n, где d – это тот самый закрытый ключ отправителя. Теперь сообщение, состоящее из блоков si можно "спокойно" передавать по сети. Никакой опасности по известным hi и si найти Ваш секретный ключ нет – это настолько же сложная задача, как и задача "логарифмирования в конечном поле". А вот любой получатель сообщения может легко прочесть исходное значение hi, выполнив операцию ((si)e)mod n = ((hi)d*e)mod n = hi – Ваш открытый ключ (e,n) есть у всех, а то, что возведение любого числа в степень (e*d) по модулю n дает исходное число, мы доказали в прошлом параграфе. При этом никто другой, кроме Вас, не зная Вашего закрытого ключа d не может, изменив текст, а следовательно, и хеш-сумму, вычислить такие s'i, чтобы при их возведении в степень e получилась хеш-сумма h'i, совпадающая с хеш-суммой фальсифицированного текста.
Таким образом, манипуляции с хеш-суммой текста представляют из себя "асимметричное шифрование наоборот" : при отправке используется закрытый ключ отправителя, а для проверки сообщения – открытый ключ отправителя. Подобная технология получила название "электронная подпись". Информацией, которая уникально идентифицирует отправителя (его виртуальной подписью), является закрытый ключ d. Ни один человек, не владеющий этой информацией, не может создать такую пару (текст,si), что описанный выше алгоритм проверки дал бы положительный результат.
Подобный обмен местами открытого и закрытого ключей для создания из процедуры асимметричного шифрования алгоритма электронной подписи возможен только в тех системах, где выполняется свойство коммутативности ключей. Для других асимметричных систем алгоритм электронной подписи либо значительно отличается от базового, либо вообще не реализуем.
|
