ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 18.01.2025
Просмотров: 721
Скачиваний: 2
Алгоритм rsa
Алгоритм RSA стоит у истоков асимметричной криптографии. Он был предложен тремя исседователями-математиками Рональдом Ривестом (R.Rivest) , Ади Шамиром (A.Shamir) и Леонардом Адльманом (L.Adleman) в 1977-78 годах.
Первым этапом любого асимметричного алгоритма является создание пары ключей : открытого и закрытого и распространение открытого ключа "по всему миру". Для алгоритма RSA этап создания ключей состоит из следующих операций :
Выбираются два простых (!) числа p и q
Вычисляется их произведение n(=p*q)
Выбирается произвольное число e (e<n), такое, что НОД(e,(p-1)(q-1))=1, то есть e должно быть взаимно простым с числом (p-1)(q-1).
Методом Евклида решается в целых числах (!) уравнение 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.
На самом деле операции возведения в степень больших чисел достаточно трудоемки для современных процессоров, даже если они производятся по оптимизированным по времени алгоритмам. Поэтому обычно весь текст сообщения кодируется обычным блочным шифром (намного более быстрым), но с использованием ключа сеанса, а вот сам ключ сеанса шифруется как раз асимметричным алгоритмом с помощью открытого ключа получателя и помещается в начало файла.
Технологии цифровых подписей
Как оказалось, теория асимметричного шифрования позволяет очень красиво решать еще одну проблему информационной безопасности – проверку подлинности автора сообщения. Для решения этой проблемы с помощью симметричной криптографии была разработана очень трудоемкая и сложная схема. В то же время с помощью, например, того же алгоритма 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), что описанный выше алгоритм проверки дал бы положительный результат.
Подобный обмен местами открытого и закрытого ключей для создания из процедуры асимметричного шифрования алгоритма электронной подписи возможен только в тех системах, где выполняется свойство коммутативности ключей. Для других асимметричных систем алгоритм электронной подписи либо значительно отличается от базового, либо вообще не реализуем.
Механизм распространения открытых ключей
Казалось бы, асимметричные криптосистемы лишены одного из самых главных недостатков симметричных алгоритмов – необходимости предварительного обмена сторонами секретным ключом по защищенной схеме (например, из рук в руки или с помощью поверенного курьера). Вроде бы достаточно "раструбить" по всему свету о своем открытом ключе, и вот готова надежная линия передачи сообщений.
Но оказывается не все так просто : предположим я Ваш потенциальный собеседник. Для того чтобы отправить зашифрованное сообщение, я должен узнать Ваш открытый ключ. Если Вы не приносили мне его лично на дискете, значит я его просто взял из информационной сети. А теперь главный вопрос : где доказательство, что данный набор байт является именно Вашим открытым ключом? Ведь злоумышленник может сгенерировать произвольную пару (закрытый ключ, открытый ключ), затем активно распространять или пассивно подменять при запросе Ваш открытый ключ созданным им. В этом случае при отправке сообщения 1) я зашифрую его тем ключом, который думаю, что является Вашим, 2) злоумышленник, перехватив сообщение дешифрует его парным закрытым ключом, прочтет и более того : 3) может переслать дальше, зашифровав действительно уже Вашим открытым ключом. Точно так же, но по инверсной схеме, он может подменить и мою электронную подпись под моим письмом.
Таким образом, если между отправителем и получателем нет конфиденциальной схемы передачи асимметричных ключей, то возникает серьезная опасность появления злоумышленника-посредника. Но асимметричная криптография нашла изящный способ очень значительного снижения риска подобной атаки. Если задуматься, то неправильно говорить, что между Вами и Вашим собеседником нет гарантированной линии связи. Несомненно у Вас найдется трое-четверо надежных знакомых в столице или за рубежом, у них в свою очередь также найдется множество знакомых во многих точках страны и мира. В конце концов, Вы пользуетесь программным обеспечением фирм, если не центры, то хотя бы филиалы которых находятся в той стране или в том городе, куда Вы хотите отправить письмо. Проблема только в том, что начиная, со второго от Вас звена ни Вы не знаете человека, ни он Вас, и вероятность того, что он, или более того, крупная компания, будут что-либо делать ради Вас, очень мала.
Но в принципе, если множество единомышленников объединятся с целью создать надежную сеть распространения ключей, то это будет им вполне под силам. А сама асимметричная криптография поможет им в этом следующим образом : на самом деле никуда ходить с дискетой, получив просьбу от своего знакомого передать открытый ключ мистера V.M.B. мистеру R.H.J., не нужно. Ведь Вы общаетесь с Вашим знакомым, значит, у Вас есть его открытый ключ, полученный каким-либо надежным способом. А следовательно, он может Вам прислать этот открытый ключ мистера V.M.B., подписав сообщение своей электронной подписью. А от Вас в свою очередь требуется всего лишь отправить этот ключ дальше по цепочке в направлении мистера R.H.J., подписав уже своей электронной подписью. Таким образом, минуя несколько переподписываний, открытый ключ дойдет от места отправления к месту требования по надежному пути. В принципе от Вас даже может не требоваться никаких действий – просто поставьте на Вашей ЭВМ специальный сервер распространения ключей, и он все только что описанные действия будет выполнять автоматически.