Teoria_chisel_i_kriptozashita

Правила зашифрования и расшифрования в системе RSA определим

следующим образом для x X и y Y :
y = E			ko	(x) = xe mod n ;	D	( y) = yd mod n .
					ks
Пусть, в соответствии с определением криптосистемы RSA, n = p q ,
				(e d) modϕ(n) =1,				(5.1)
				ϕ(n) = ( p −1) (q −1) ,
y = E	ko	(x) = xe mod n , D			( y) = yd		mod n = x .	(5.2)
				ks
Для любого целого числа x и простого p по малой теореме Ферма
				x p ≡ x(mod p).				(5.3)
Из (5.3) следует, что x p − x ≡ 0(mod p) , или
			x (x p−1 −1) ≡ 0(mod p).					(5.4)
Если (x, p) = p ,				то p | x , следовательно,			x ≡ 0(mod p).	Отсюда
следует (5.4).		то по малой теореме Ферма x p−1 ≡1(mod p). Отсю-
Если (x, p) =1,

да также следует (5.4).

Из соотношения (5.1) следует e d = k ϕ(n) +1, k > 0 целое. Отсюда и из (5.3) получаем следующую цепочку равенств и сравнений:

yd = (xe )d = xed = xk ϕ(n)+1 = xk ( p−1) (q−1)+1 =
= xk p (q−1) x−k q+k +1 = (x p )k (q−1) x−k q+k +1 ≡	(5.5)
≡ xk (q−1) x−k q+k +1 ≡ x(mod p) .
Таким образом, yd ≡ x(mod p) . Аналогично yd ≡ x(mod q) .	(5.6)

Чтобы доказать сравнение yd ≡ x(mod n) , используем следующую лемму.

Лемма. Пусть a,b,c — натуральные числа, причем (a,b) =1, т.е. a и b –– взаимно простые. Тогда: 1) если b|( a c), то b|c ;

2) если a |c , и b|c , то (a b) |c .

В нашем случае a = p, b = q, ( p, q) =1, c = xe d − x .

p |( xe d − x ), q |( xe d − x ), n = p q |( xe d − x ).

То есть yd ≡ x(mod n) для всех x , включая те, для которых (x, n) ≠1.

Тремя возможными подходами к криптоанализу алгоритма RSA являются следующие:

1)простой перебор, который предполагает проверку всех возможных личных ключей;

41

2)математический анализ. Существует несколько подходов такого рода, но все они, по сути, эквивалентны нахождению множителей произведения двух простых чисел;

3)анализ временных затрат, который опирается на анализ времени выполнения алгоритма расшифрования.

Защита против простого перебора в случае RSA остается той же, что и для других криптосистем, — использование большого пространства клю-

чей. С этой точки зрения, чем больше разрядность е и d, тем надежнее защита. Однако из-за сложности вычислений, как при генерировании ключей, так и при шифровании/расшифровании: чем большим оказывается размер ключа, тем медленнее работает криптосистема.

Математический анализ обеспечивает три различных подхода к криптоанализу RSA:

1)разложение n на два простых его множителя. Это позволит вычислить ϕ(n) = ( p −1)(q −1) , на основании чего можно будет определить d = e−1 modϕ(n);

2)определение непосредственно ϕ(n) без предварительного опре-

деления p и q . Это также позволит определить

d= e−1 modϕ(n);

3)определение непосредственно d без предварительного определения ϕ(n) .

Чтобы избежать выбора значений n, которые могут быть разложены на множители с малыми затратами, предлагается следующие ограничения относительно p и q:

1)значения p и q должны различаться по длине на несколько разрядов;

2)как ( p −1), так и (q −1) должны содержать в своих разложениях достаточно большой простой множитель;

3)НОД ( p −1, q −1) должен быть достаточно малым.

1

Кроме того, доказано, что если e < n и d < n 4 , то d определяется достаточно легко.

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

1)постоянное время возведения в степень. Этого можно добиться увеличением этого времени до определенного уровня, одинакового для всех случаев;

2)случайные задержки;

42

3)маскировка. Умножение шифрованного текста на случайное число перед тем, как выполнять возведение в степень.

В некоторых продуктах RSA Data Security предлагается возможность

использования функции маскировки. В них операция М = Сd mod n с личным ключом выполняется следующим образом:

1)генерируется секретное случайное число r в диапазоне от 0 до n – 1;

2)вычисляется С′ ≡ Сre (mod n) , где е является открытым значением показателя степени;

3)вычисляется М′ ≡ (С′)d (mod n) для обычной реализации RSA;

4)вычисляется М ≡ М′r −1 mod n . В этом сравнении r −1 представ-

ляет собой мультипликативное обратное значение r	mod n . Ре-
зультат будет корректным, если выполнится	равенство

red mod n = r mod n .

При использовании маскировки общая производительность продукта

RSA Data Security снижается на 2...10 %.

6. Методы распределения криптографических ключей

Для распределения ключей используют несколько методов, которые можно сгруппировать в следующие классы [8; 11; 12] :

1)публичное объявление;

2)публично доступный каталог;

3)авторитетный источник открытых ключей;

4)сертификаты открытых ключей.

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

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

Публично доступный каталог. Более высокую степень защиты можно обеспечить с помощью создания и обслуживания некоторого публично доступного динамического каталога открытых ключей. Ответственность за сопровождение и распространение публичного каталога должен нести некоторый надежный центр или организация.

43

Такая схема включает следующие элементы:

1)уполномоченный объект поддерживает каталог с записями, включающими имя и открытый ключ для каждого участника;

2)каждый участник регистрирует свой открытый ключ с помощью объекта, уполномоченного вести каталог. Такая регистрация должна вестись либо при личной явке участника, либо по защищенным коммуникационным каналам;

3)любой участник может заменить существующий ключ новым в любой момент или из-за того, что открытый ключ был где-то уже использован для пересылки достаточно большого объема данных или из-за компрометации ключа;

4)периодически объект, уполномоченный вести каталог, публикует весь каталог или дополнения к нему;

5)участники могут иметь также доступ к каталогу в его электронной версии. Для этого обязательно требуется канал связи между участниками обмена данными и объектом, уполномоченным вести

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

в каталоге.

Авторитетный источник открытых ключей. Эта схема предпола-

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

1)инициатор А посылает сообщение с меткой даты/времени авторитетному источнику открытых ключей с запросом о текущем открытом ключе участника В;

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

—открытый ключ участника В, который участник А может использовать для шифрования сообщений, предназначенных для получателя В;

44

— оригинальный запрос, чтобы сторона А имела возможность сопоставить ответ с ранее отправленным запросом и убедиться, что запрос не был изменен на пути к авторитетному источнику;

— оригинальную метку даты/времени, чтобы отправитель А мог удостовериться, что это сообщение не является одним из старых сообщений от авторитетного источника, содержащим ключ, отличный от текущего открытого ключа адресата В;

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

4)респондент В получает открытый ключ участника А от авторитетного источника точно таким же способом, каким отправитель А получил открытый ключ получателя В;

5)респондент В посылает сообщение инициатору А, шифрованное с помощью ключа В и содержащее оказию отправителя А, а также новую оказию, сгенерированную участником В, что убеждает, что отправителем полученного сообщения был В;

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

Итак, требуется отправить 6 сообщений, однако отсылать первые 4 требуется нечасто, так как обе стороны могут сохранить открытые ключи друг друга для дальнейшего использования, что обычно называют кэшированием. Периодически пользователь должен запрашивать свежие экземпляры открытых ключей своих адресатов, чтобы иметь гарантированную возможность безопасного обмена данными. Авторитетный источник является узким местом системы, поскольку пользователь должен апеллировать к авторитетному источнику при необходимости получить открытый ключ для каждого нового адресата, с которым этот пользователь намерен вести переписку. Каталог имен и открытых ключей, поддерживаемый авторитетным источником, остается уязвимым в отношении несанкционированного вмешательства.

Сертификаты открытых ключей. Сертификаты могут использо-

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

45

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

1)любой участник должен иметь возможность прочитать сертификат, чтобы определить имя и открытый ключ владельца сертификата;

2)любой участник должен иметь возможность проверить, что сертификат исходит из авторитетного источника сертификатов и не является подделкой;

3)только авторитетный источник сертификатов должен иметь воз-

можность создавать и изменять сертификаты.

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

СА = ЕKRавт [T , IDА, KUВ],

где KRавт — личный ключ, используемый авторитетным источником; KUВ — открытый ключ участника В; IDА — идентификатор участника А;

Т — дата/время отправления. Участник А может переслать этот сертификат любому другому участнику, который прочтет и примет сертификат:

DKUавт [СА] = DKUавт [ЕKRавт [Т, IDА, KU А]] = (Т, IDА, KU А) ,

где KUавт — открытый ключ авторитетного источника; KU А — открытый

ключ участника А.

Так как сертификат можно прочитать только с помощью открытого ключа авторитетного источника сертификатов, это дает гарантию того, что

сертификат пришел именно от авторитетного источника. Элементы IDА и KU А сообщают получателю имя и открытый ключ владельца сертифика-

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

В этом смысле ситуация остается рискованной до тех пор, пока возможные системы не будут информированы о том, что старая система уже

46

не действительна. Таким образом, метка даты/времени указывает на длительность срока действия сертификата.

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

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

1) сторона А генерирует пару (открытый/личный) ключей ( KU А, KRА) и передает сообщение стороне В, содержащее KU А и

идентификатор отправителя А IDА ;

2)получатель В генерирует секретный ключ К и передает этот ключ инициатору сообщения А зашифрованным с помощью открытого ключа инициатора А;

3)пользователь А вычисляет DKRА [EKU А [КS ]], чтобы восстановить секретный ключ. Поскольку только пользователь А может расшифровать это сообщение, только два участника обмена А и В будут знать значение КА ;

4)участник А уничтожает ключKRА, а участник В — ключ KU А.

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

Этот протокол уязвим в отношении активных атак. Если нарушитель Е имеет возможность внедрения в канал связи, то он может скомпрометировать связь без того, чтобы быть обнаруженным, следующим образом:

1)участник А генерирует пару открытый/личный ключи ( KU А, KRА) и передает сообщение адресату В, содержащее KU А и идентификатор участника А IDА ;

2)нарушитель Е перехватывает сообщение, создает собственную пару открытый/личный ключи ( KUЕ, KRЕ ) и передает сообщение адресату В, содержащее KUЕ, IDА;

3)В генерирует секретный ключ КS и передает ЕKU Е [КS ];

47

4)нарушитель Е перехватывает это сообщение и узнает КS , вычис-

ляя DKRЕ [EKU Е [КS ]];

5)нарушитель передает участнику А сообщение ЕKU А [КS ].

В результате оба участника А и В будут знать КS , но не будут подозревать, что КS также известен нарушителю Е. Поэтому стороны А и В могут начать обмен сообщениями, используя КS . Нарушитель Е больше не будет активно вмешиваться в канал связи, а просто будет перехватывать сообщения. Зная КS , нарушитель может расшифровать любое сообщение,

а участники А и В не будут подозревать о существовании проблемы. Таким образом, простой протокол оказывается полезным только в случае пассивного перехвата сообщений.

6.1.Распределение секретных ключей

собеспечением конфиденциальности и аутентификации

Схема, представленная на рисунке 3, обеспечивает защиту как от ак-

тивной, так и пассивной атаки.

ЕKU В [N1[IDА]]

					[N [N		]]
Отправитель			Е	KU А		2			Получатель
					1
			ЕKU В [N2 ]
			ЕKU В [ЕKRА [КS ]]

Рис. 3. Распределение секретных ключей с помощью шифрования с открытым ключом

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

1)сторона А использует открытый ключ В для пересылки стороне В шифрованного сообщения, содержащего идентификатор участни-

ка А ( IDА) и оказию ( N1), используемую для идентификации данной транзакции;

2)пользователь В посылает сообщение пользователю А, зашифрованное с помощью KU А, содержащее полученную от него оказию ( N1) и новую оказию ( N2 ), сгенерированную пользователем В.

48

Присутствие N1 в сообщении убеждает участника А в том, что респондентом является сторона В;

3)сторона А возвращает N2 , шифруя сообщение открытым ключом стороны В, гарантируя В, что респондентом является сторона А;

4)участник А выбирает секретный ключ КS и посылает участнику В сообщение М = ЕKUВ [ЕKRА [КS ]]. Шифрование этого сообщения открытым ключом стороны В гарантирует, что только участник В сможет прочитать его, а шифрование личным ключом участника А, — что только участник А мог послать его;

5)сторона В вычисляет DKU А [ЕKRВ [М]], чтобы восстановить сек-

ретный ключ.

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

Гибридная схема. Еще одна схема использования шифрования с открытым ключом при распределении секретных ключей представляет гибридный подход, применяемый на мэйнфреймах фирмы IBM. Эта схема предполагает участие центра распределения ключей (ЦРК), с которым каждый пользователь использует свой главный секретный ключ и распределение секретных сеансовых ключей, шифруемых главным ключом. В основе такого трехуровнего подхода лежит следующая логика:

—скорость выполнения процедуры. Этой логике соответствует мно-

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

—обратная совместимость. Гибридную схему можно легко реализовать в виде расширения уже имеющейся схемы, предполагающей использование ЦРК с минимальными изменениями предусмотренной процедуры и программного обеспечения.

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

49

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

Эффективность алгоритма Диффи — Хеллмана опирается на трудность вычисления дискретных логарифмов.

Обмен ключами по схеме Диффи — Хеллмана происходит следующим образом. В этой схеме имеются два открытых числа : простое число q и целое α , являющееся первообразным корнем q. Предположим, что пользователи А и В намерены обменяться ключами. Пользователь А выбирает

случайное целое число			ХА < q и вычисляет	YА ≡α ХА (mod q) .	Точно
также пользователь В			независимо выбирает	случайное целое	число
Х	В	< q и вычисляет Y	≡α ХВ (mod q) . Каждая сторона сохраняет зна-
		В

чение Х в тайне и делает значение Y свободно доступным другой стороне. Пользователь А вычисляет ключ по формуле К ≡ (YВ)ХА (mod q) , а поль-

зователь В — по формуле К ≡ (YА)ХВ (mod q). По этим двум формулам вычисления дают одинаковые результаты, как следует из вычислений.

К≡ (YВ)ХА (mod q) ≡ (α ХВ mod q)ХА (mod q) ≡

≡(α ХВ )ХА (mod q) ≡α ХВХА (mod q) ≡ (α ХА )ХВ (mod q) ≡

≡(α ХА mod q)ХВ (mod q) ≡ (YА)ХВ (mod q).

Обе стороны обменялись секретными ключами. Поскольку при этом ХА и ХВ были только в личном пользовании и поэтому сохранялись в

тайне, нарушителю придется работать только с q, α, ΥА и ΥВ. Таким образом, нарушителю придется вычислять дискретный логарифм, чтобы определить ключ ХВ = indα,q (YВ) .

После этого он сможет вычислить ключ К точно так же, как это делает пользователь В.

Защищенность обмена ключами по схеме Диффи — Хеллмана опирается на высокую трудность нахождения дискретного логарифма большого простого числа.

Для примера выберем простое число q = 97 с первообразным корнем α = 5. Пользователи А и В выбирают секретные ключи ХА= 36 и ХВ = 58,

соответственно. Каждый вычисляет открытый ключ:

ΥА = 536≡50 (mod 97), ΥB = 558≡44 (mod 97).

После обмена открытыми ключами каждый из них может вычислить общий секретный ключ:

50