Несимметричность в реализации алгоритма шифрации данных предполагает то, что для зашифровки и расшифровки нужны разные ключи. Это свойство криптоалгоритмов находит самое различное применение в построении безопасности информационных систем. В первую очередь получили распространение системы с открытым ключом, в которых используются два варианта ключей: первый ключ - открытый, используемый для шифрации, второй - закрытый, известный только получателю сообщения и используемый для расшифровки сообщения.
Первый и наиболее известный несимметричный криптоалгоритм, одна из первых систем с открытым ключом, был создан Ривестом, Шамиром и Алдеманом. Эти американские математики во время совместных исследований в Массачусетском технологическом институте в 1977 году разработали систему RSA, опубликованную в 1978 году. Название алгоритма взято по первым буквам фамилий авторов (Rivest, Shamir и Aldeman в английском варианте).
Приведу описание протокола RSA:
1) Выбираются два простых числа, P и Q, величина которых определяет стойкость к вскрытию и размер шифруемого сообщения, и вычисляется два произведения N=PxQ и M=(P-1)x(Q-1).
2) После этого первый участник A системы выбирает случайное целое число D, взаимно простое с M. Взаимно простое означает то, что наибольший общий делитель этих двух чисел должен быть равен 1. Вычисляется число E, удовлетворяющее условию modM(DE)=1, где - взятие остатка при делении.
3) Затем первый участник A публикует D и N для получателей своих сообщений как свои открытые ключи шифрования, сохраняя как закрытый ключ.
4) Потом первый участник A формирует S - сообщение с применением свертки S=sum(0,n)an-ixbi-1, где n - количество символов в шифруемом сообщении, a и i - номер символа и его позиция, b - размер множества используемых символов.
Для пояснений приведу пример. Сформируем свертку из букв, составляющих название алгоритма RSA. Размер множества возьмем 32 символа (необходимо 5 бит для представления всего используемого в примере множества символов). Номера символов возьмем по порядку следования в английском алфавите, соответственно у букв номера будут A=1, R=18, S=19. Слову RSA будет соответствовать следующее число S=((1x32)+19)x32+18=1650. Это похоже на то, как формируются числа в позиционной системе исчисления, с тем отличием, что вместо основания 10 взято 32 и вместо цифр использованы порядковые номера символов в множестве. Длина сообщения равна значению выражаемого им целого числа и должна лежать в интервале (1,N).
5) Окончательную зашифровку участник A производит возведением S в степень E по модулю N: S'=modN(SD).
6) Дешифрование сообщения второй участник B производит возведением S' в степень E по модулю N, т.е. S=modN(S'E).
Криптостойкость системы RSA основана на том, что не может быть просто вычислено без знания простых сомножителей P и Q, а нахождение этих сомножителей из N считается трудно разрешимой задачей. На самом деле поиск больших простых чисел, используемых для формирования ключей, весьма непростая задача и на практике идут к различным упрощениям для формирования ключей. Первоначально авторы RSA для обеспечения криптостойкости предлагали выбирать простые числа P и Q случайно, по 50 десятичных знаков каждое. Но вскоре уже число из 155 десятичных цифр было разложено на простые сомножители за 6 недель математиками Ленстра из фирмы Bellcore и Манасси из фирмы DEC. Для этого они соединили 1000 ЭВМ, находившихся в разных странах мира. Последние исследования для построения ключей рекомендуют числа из 250-300 десятичных знаков. Для шифрования по системе RSA приходится возводить огромные числа в большие степени, отсюда у алгоритма крайне низкое быстродействие, что является его существенным недостатком и сужает область применения.
Более эффективную несимметричную систему шифрования с открытым ключом предложил ЭльГамаль в 1985 году. Протокол строится на основе возведения в степень по модулю большого простого числа. Для этого задается большое простое число . Как и в предыдущем примере, сообщение формируется с помощью свертки и представляет собой целое число не большее . Приведу протокол шифросистемы в варианте, предложенном Шамиром:
1) Участникам системы A и B известно только число P.
2) Первый участник A генерирует случайное число X из интервала (1,P).
3) Второй участник B генерирует случайное число из того же интервала (1,P).
4) Участник А шифрует сообщение ключом X: S1=modP(SX) и посылает участнику В.
5) Участник В шифрует его своим ключом Y: S2=modP(S1Y) и посылает S2 к А.
6) Участник А убирает свой ключ из шифровки S3=modP(S2-X) и пересылает к участнику В.
7) Получатель В окончательно расшифровывает сообщение S=modP(S3-Y).
В протоколе ЭльГамаля большая степень защиты, чем при использовании протокола RSA, достигается с таким же по размеру числом N. Это позволяет на порядок увеличить скорость работы алгоритма без потери криптостойкости. Стойкость системы ЭльГамаля основана на том, что легко вычислить степень целого числа, но трудно решить задачу дискретного логарифмирования, т.е. найти показатель степени, в который нужно возвести заданное число, для получения другого заданного целого числа.
В системе, построенной по протоколу RSA, зашифровать сообщение может любой, зная открытые ключи, а восстановить - только адресат с закрытым ключом. Другими словами, можно зашифровать сообщение и осуществить broadcasting (широковещательную рассылку сообщения) с уверенностью в том, что прочтет сообщение только санкционированное лицо. К примеру, раскидать сообщение по гостевым книгам нескольких веб-сайтов, отправить на электронный почтовый ящик общего пользования и тому подобное. Другое свойство протокола RSA получается, если поменять местами числа E и D. Получится, что зашифровать может один, а уже расшифровать сможет любой получатель. На этом свойстве формируется так называемая "цифровая подпись". Отправитель посылает шифрованное сообщение вместе с "цифровой подписью" L, которую вычисляют из уравнения S=modN(LE). Цифровая подпись определяет авторство сообщения, что получило широкое распространение в первую очередь в деловой и банковской сферах.
В протоколах RSA и ЭльГамаля для формирования шифрованного сообщения применяется свертка. Свертка имеет интересное свойство. Оно состоит в том, что шифрованное сообщение зависит как от ключа, так и от одного или более предшествующих символов открытого текста. Другими словами, в текст нельзя внести изменения, не зная ключа. На этом построено формирование "цифровой печати", которая удостоверяет отсутствие несанкционированных изменений в сообщении. В деловых приложениях понятия "цифровой печати" и "подписи" часто смешивается в один термин - "цифровая подпись". Свертки применяются также для контроля отсутствия ошибок в сообщении. Если, к примеру, исказить один бит в шифровке, то произойдет так называемое "размножение ошибок" и при расшифровке текст сообщения будет нечитаемым. Это одновременно сильное и слабое свойство подобных систем. Кстати, в комбинированных системах из шифров замены и перестановки также может наблюдаться размножение ошибок. Алгоритмы CRC для контроля целостности кода построены на этом же принципе сверток.
Несимметричные алгоритмы с открытыми ключами при прочих недостатках имеют весьма низкое быстродействие, по сравнению с симметричными протоколами DES или IDEA. Поэтому с начала восьмидесятых годов стали строить так называемые гибридные системы. В них протоколы шифрования с открытым ключом используются для передачи ключей и генерации цифровой подписи, а основная информация для передачи защищается симметричными алгоритмами типа DES.
Black Prince,
Werebad@bigfoot.com
Версия для печати
