Инструменты пользователя

Инструменты сайта


examination:mszki:question28

Экзаменационный вопрос №28

Особенности криптографического алгоритма RSA

Для того чтобы был возможен обмен конфиденциальной информацией между двумя абонентами, ключ должен быть сгенерирован одним из них, а затем каким-либо образом передан другому в конфиденциальном порядке. В общем случае для передачи ключа по каналам связи требуется использование еще одной криптосистемы, для которой вновь возникает проблема распределения ключей и т.д.

Для решения этой и ряда других проблем были предложены криптосистемы с открытым ключом, называемые также асимметричными криптосистемами.

Перед отправкой сообщения адресату исходный текст шифруется открытым (общедоступным) ключом адресата. Алгоритм шифрования построен таким образом, что расшифровывание сообщения возможно только с использованием личного (секретного) ключа адресата.

Впервые модель системы секретной связи с открытым ключом была предложена Диффи и Хеллманом в 1976 году.

Суть этой модели состоит в том, что ключ известен полностью только получателю сообщения и представляет собой тройку чисел k = (е, d, n), где под ключ e служит ключом шифрования, а ключ d — ключом расшифровывания. При этом только d является секретным (личным) ключом. Стойкость системы обеспечивается за счет особых свойств шифр преобразования, которое представляет собой так называемую одностороннюю функцию с лазейкой. Вычисление значения такой функции (от открытого текста и параметра e) должно быть несложным, в то же время ее обращение должно быть вычислительно нереализуемым без знания секретной информации, “лазейки”, связанной с секретным ключом d.

В криптосистеме с открытым ключом сообщение, предназначенное абоненту, зашифровывается отправителем с помощью ключа e и расшифровывается получателем с помощью ключа d. Если шифр преобразование действительно является односторонней функцией, то сам отправитель не в состоянии расшифровать сформированную им криптограмму.

Широко известным примером криптосистемы с открытым ключом является криптосистема RSA, разработанная в 1977 году и получившая название в честь ее создателей: Ривеста, Шамира и Эйдельмана. Стойкость этой системы основывается на сложности обратимости степенной функции в кольце вычетов целых чисел по составному модулю n (при надлежащем выборе модуля). Криптосистема RSA на каждом такте шифрования преобразует двоичный блок открытого текста m длины size(n), рассматриваемый как целое число, в соответствии с формулой: c = me(mod n).

При этом n = pq, где p и q — случайные простые числа большой разрядности, которые уничтожаются после формирования модуля и ключей. Открытый ключ состоит из пары чисел e и n. Под ключ e выбирается как достаточно большое число из диапазона 1 < e < φ(n), с условием: НОД(e, ϕ(n)) = 1, где ϕ(n) — наименьшее общее кратное чисел p–1 и q–1. Далее, решая в целых числах x, y уравнение xe + yφ(n) = 1, полагается d = х, т.е. ed = 1(ϕ(n)). При этом для всех m выполняется соотношение med = m(n), поэтому знание d позволяет расшифровывать криптограммы.

Чтобы гарантировать надежную защиту информации, к системам с открытым ключом предъявляются два следующих требования.

1. Преобразование исходного текста должно исключать его восстановление на основе открытого ключа.

2. Определение закрытого ключа на основе открытого также должно быть вычислительно нереализуемым. При этом желательна точная нижняя оценка сложности (количества операций) раскрытия шифра.

Алгоритмы шифрования с открытым ключом получили широкое распространение в современных информационных системах.

Рассмотрим построение криптосистемы RSA на простом примере.

1. Выберем p = 3 и q = 11.

2. Определим n = 3 • 11 = 33.

3. Найдем ϕ(n) = (p – 1)(q – 1) = 20.

4. Выберем e, взаимно простое с 20, например, e = 7.

5. Выберем число d, удовлетворяющее 7d = 1(mоd 20).

Легко увидеть, что d = 3(mоd 20).

Представим шифруемое сообщение как последовательность целых чисел с помощью соответствия: А = 1, B = 2, С = 3, …, Z = 26. Поскольку size(n) = 6, то наша криптосистема в состоянии зашифровывать буквы латинского алфавита, рассматриваемые как блоки, Опубликуем открытый ключ (e, n) = (7, 33) и предложим прочим участникам системы секретной связи зашифровывать с его помощью сообщения, направляемые в наш адрес. Пусть таким сообщением будет CAB, которое в выбранной нами кодировке принимает вид (3, 1, 2). Отправитель должен зашифровать каждый блок и отправить зашифрованное сообщение в наш адрес:

RSA(C) = RSA(3) = 37 = 2187 = 9(mod 33);

RSA(A) = RSA(1) = 17 = 1(mod 33);

RSA(B) = RSA(1) = 27 = 128 = 29(mod 33).

Получив зашифрованное сообщение (9, 1, 29), мы сможем его расшифровать на основе секретного ключа (d, n) = (3, 33), возводя каждый блок в степень d = 3:

93 = 729 = 3(mоd 33);

13 = 1(mоd 33);

293 = 24389 = 2(mоd 33).

Для нашего примера легко найти секретный ключ перебором. На практике это невозможно, т.к. для использования на практике рекомендуются в настоящее время следующие значения size(n):

1. 512–768 бит — для частных лиц;

2. 1024 бит — для коммерческой информации;

3. 2048 бит — для секретной информации.

examination/mszki/question28.txt · Последние изменения: 2014/01/15 08:20 (внешнее изменение)