В криптосистемах с открытым ключом процедура шифрования является общедоступной, но из этого совсем не следует, что общедоступной будет и процедура дешифрования.
В классической криптографии ключ К использовался при шифровании и почти во всех случаях при дешифровке. Зная шифрующий ключ К, легко можно получить дешифрующий ключ К1. Процесс получения криптотекста С с открытого текста М с помощью алгоритма Е и используя ключ К запишем в следующем виде: С=ЕК(М). Соответственно, процесс дешифровки выполняется по правилу М=DK1(C), где D — алгоритм дешифровки. Во всех классических криптосистемах дешифрующий ключ легко находится, если известен шифрующий. В криптосистемах же с открытым ключом дешифрующий ключ К1 из ключа К вывести очень непросто — в принципе, практически невозможно.
Система открытого распространения ключей позволяет двум сторонам сформировать совместную часть некоторой распределенной секретной информации. Однако, ни одна из сторон не имеет никакого непосредственного влияния на то, какой окажется эта информация.
Криптосистема RSA
RSA – криптографическая система открытого ключа, обеспечивающая такие механизмы защиты как шифрование и цифровая подпись (аутентификация – установление подлинности).
Алгоритм RSA работает следующим образом:
Пусть p и q - два больших различных простых числа, и пусть n = p*q и e некоторое целое, взаимно простое с (p-1)*(q-1).
Оба соответствующих пространства открытых текстов Mk и зашифрованных сообщений Ck суть Zn - множество неотрицательных целых, меньших n. Если подлинное сообщение окажется слишком длинным, чтобы принадлежать Zn, его необходимо разбить на части и зашифровать, используя режим шифрования со сцеплением блоков.
Соответствующая ключу k функция шифрования Ek: Mk -> Ck определяется как Ek(m) = me mod(n). Для того, чтобы полностью определить естественный алгоритм ее вычисления достаточно записать e и n в открытый справочник. Такая пара называется открытым ключом, который легко вычисляется с помощью личного ключа .
Ek является кандидатом на однонаправленную функцию с потайным ходом, и хотя существует эффективный алгоритм вычисления обратной ей функции Dk, мы не знаем, как получить его эффективно, задаваясь только естественным алгоритмом вычисления Ek (т.е. только для заданных n и e).
Эффективный алгоритм вычисления Dk легко получить, задав дополнительную секретную информацию p и q. С этой целью, используя обобщенные алгоритмы Евклида для нахождения наибольшего общего делителя, чтобы вычислить целое число d, такое что e*d = 1 mod ф(n), где ф(n) = (p-1)*(q-1). По известной теореме Эйлера m(e*d) = m mod(n) для каждого целого числа m и, следовательно, (me) d mod(n) = m, при условии что 0 <= m < n, что обеспечивается, когда m принадлежит Mk.
Функция дешифрования Dk: Ck -> Mk в связи с этим определяется как Dk(c) = md mod(n), и эффективный алгоритм для модульного возведения в степень также может быть использован и для ее вычисления. Тогда каждый пользователь криптосистемы RSA должен раз и навсегда выбрать случайно подходящие целые числа p, q и e и вычислить с их помощью d. После чего он делает свой открытый ключ доступным в пользовательском справочнике, тогда как d сохраняет в секрете. Это дает возможность любому другому пользователю шифровать посылаемые ему сообщения, которые только он и может расшифровать. Для того чтобы эта идея была реализована практически, решающим является удовлетворение требование, чтобы генерация больших случайных простых чисел и вычисление d были легко осуществимы. Функция дешифрования Dk: Ck -> Mk в связи с этим определяется как Dk(c) = md mod(n), и эффективный алгоритм для модульного возведения в степень также может быть использован и для ее вычисления. Суммируя все сказанное, тогда каждый пользователь криптосистемы RSA должен раз и навсегда выбрать случайно подходящие целые числа p, q и e и вычислить с их помощью d. После чего он делает свой открытый ключ доступным в пользовательском справочнике, тогда как d сохраняет в секрете.
В качестве небольшого примера, пусть p = 19 и q = 23, так что n = 437 и ф(n) = 396. Пусть также e = 13, и поэтому d = 61, так как 13*61 = 793 = 2ф(n)+1. Тогда сообщение в открытом текcте m = 123 будет зашифровано как c = 12313 mod(437) = 386. Действительно, 38661 mod(437) = 123.
Если бы существовали эффективные методы разложения на сомножители (факторинга), то, разложив n на сомножители (факторы) p и q, можно было бы получить секретный (private) ключ d. Таким образом надежность криптосистемы RSA основана на трудноразрешимой – практически неразрешимой – задаче разложения n на сомножители (то есть на невозможности факторинга n) так как в настоящее время эффективного способа поиска сомножителей не существует.
Алгоритм шифрования и дешифрования RSA.
1. Выберем два очень больших простых p и q.
2. Определим n=p*q.
3. Выберем большое случайное число, которое назовем e. Это число должно быть взаимно простым с результатом (p-1)*(q-1).
4. Определим такое число d, для которого является истинным соотношение
(e*d) mod((p-1)*(q-1))=1 .
5. Назовем открытым ключом числа e и n, а секретным ключом - числа d,p и q.
После произведенного выбора открытого и секретного ключей по вышеизложенному алгоритму для шифрования данных необходимо выполнить следующие действия:
· разбить шифруемый текст на блоки, каждый из которых может быть представлен в виде числа М(i)= 0,1,...,n-1;
· зашифровать текст, рассматриваемый как последовательность чисел M(i) по формуле:
C(i) = (M(i)e)mod n;
Чтобы расшифровать эти данные, используется секретный ключ {d,n} и выполняются следующие вычисления:
M(i) = (C(i)d) mod n.
В результате получают исходный текст M(i).
0 коммент.:
Отправить комментарий