Лекция: Эта система эквивалентна системе

pq=N, p+q=N — j(N)+1.

Значит p, q корни квадратичного трехчлена

x2 -( N — j(N)+1)x + N.

Они могут быть вычислены по формулам:

Напомним основные моменты функционирования системы открытого шифрования RSA. Открытый ключ системы RSA есть пара <N,e>, где N = pq, а 1<e<j(N) такое натуральное число, что НОД(e,j(N))=1. Секретный ключ системы RSA есть пара чисел <N,d>, где 1<d<j(N) такое натуральное число, что выполняется (3).

Для шифрования открытый текст m (последовательность бит) представляется в виде последовательности блоков m1, m2,…, mt длины l, таким образом, чтобы каждый блок представлялся вычетом из (ℤ/N)*. Отсюда следует, что длина блока l не должна превосходить двоичной длины числа N. С другой стороны, как известно, число l не должно быть малым. Соответствующий m шифртекст c есть последовательность вычетов из (ℤ/N)* c1, c2,…, ct, где ci º mie(mod N), которая затем преобразуется в последовательность бит.

Таким образом, шифрование заключается в вычислении значений однонаправленной функции f(x) по формуле (1). Для расшифрования надо найти соответствующие обратные значения по формуле (2), то есть mi º cid(mod N).

Напомним также, что систему RSA можно использовать для подписи открытого сообщения m. Пусть c = H(m) хэш-значение открытого сообщения m, причем cÎ(ℤ/N)*. Тогда подпись под сообщением m можно вычислить, использовав секретный ключ <N,d> в системе RSA. Таким образом, m, m1 подписанное сообщение m, где m1ºcd(modN). Для проверки подписи надо использовать открытый ключ <N,e> системы RSA. То есть проверить выполнение сравнения m1e ºc(mod N). Если оно выполнено, то подпись принимается, в противном случае она отвергается.

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

Мультипликативность функции шифрования.Функции шифрования и расшифрования в системе RSA обладают свойством мультипликативности. То есть шифртекст cºme(mod N), где m=m1m2(mod N), есть произведение шифртекстов, соответствующих открытым текстам m1, m2

c º c1c2(mod N), где ci º mie(mod N),

при 1£ i£ 2.

Атака на подпись. Пусть противник создал сообщение mÎ(ℤ/N)* и хочет, чтобы Алиса подписала m с помощью своего секретного ключа <N,d>. Однако Алиса отказывается поставить подпись именно под этим сообщением. Тогда противник может замаскировать сообщение m следующим образом. Он выбирает случайный вычет rÎ(ℤ/N)*,
вычисляет º mre(mod N), где <N,e> открытый ключ Алисы. Сообщение представляется на подпись. Алиса подписывает это сообщение, то есть вычисляет. Таким образом ,c подписанное сообщение. Далее противник вычисляет

c1 º cr-1 º md(mod N)

и формирует подписанное Алисой сообщение m,c1. Хотя внешне эта угроза кажется надуманной, она реальна, если Алиса не ограничивает множество сообщений, которые она может подписать. Ограничить это множество можно по крайней мере двумя способами.

· Алиса вычисляет подпись c под сообщением mÎ(ℤ/N)* по формуле c º H(m)d(mod N), где H: (ℤ/N)* ® (ℤ/N)* функция, которая не сохраняет мультипликативность.

· Алиса может подписывать только те сообщения, которые обладают определенной структурой. Тогда сообщение º mre такой структурой, вероятно, обладать не будет.

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

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

Тогда, в силу обобщённой теоремы Евклида, существуют такие числа r и s, что

.

Пусть r отрицательно (отрицательно должно быть либо r, либо s). Тогда можно вычислить, используя алгоритм Евклида, а затем вычислить сообщение m

Атака на открытый текст для ключей с малой экспонентой и различными модулями. Метод Хаштада. Пусть е мало, например, е=3 и е используется для зашифрования одного и того же текста m по различным модулям. Соответствующие шифртексты имеют вид

(*)

Пусть – взаимно-простые числа. Тогда Мы можем найти из используя обращение китайской теоремы об остатках можно вычислить вычет y mod(N1N2N3) таким образом, что y º yi(mod Ni). Тогда из (*) легко получить yºm mod( ), а затем можно найти m путём извлечения кубического корня из .

Метод Хаштада допускает обобщение. Например, метод работает, когда ei=e, 1£i £r, где r³e. Здесь в качестве надо взять N1N2 … Nr.

Один из вариантов защиты от рассмотренного метода является внесение зависимости сообщения от номера абонента, которому передается сообщение m. Для передачи сообщения m i–ому абоненту передается сообщение

mi º i2t+m(mod Ni).

Атака на сеть абонентов, которые используют систему RSA с фиксированным модулем N.Пусть имеется сеть абонентов, которые используют систему RSA с фиксированным модулем N. То есть открытый ключ i–го абонента равен <N,ei>. Тогда i–ый абонент, исходя из своего секретного ключа <N,di>, может, как было показано выше, найти факторизацию N. Тогда он найдет секретные ключи всех других абонентов и сможет читать зашифрованную информацию, направленную в их адрес.

С другой стороны, система с общим модулем имеет еще одну слабость. Пусть одно сообщение mÎ(ℤ/N)* направляется в зашифрованном виде в два адреса. Таким образом

Пусть также НОД(ei,ej)=1. Тогда существуют целые числа r, s, для которых eir+ejs=1 и сообщение m можно найти по формуле

m º circjs (mod N).

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

ТЕОРЕМА Копперсмита. Пусть N целое число и f(x)Îℤ[x] многочлен со старшим коэффициентом 1 степени d. Пусть натуральное число при некотором фиксированном e,. Тогда имеется алгоритм вычисления всех целых x0, |x0|<X, для которых f(x0) º 0 (mod N). Сложность алгоритма полиномиальная от log2N.

 

В более общей формулировки теоремы звучит таким образом, что корень x0многочлена f(x) (mod N) такой, что может быть вычислен за время полиномиальное от 1/e, log2N, d.

Отметим, что если старший ненулевой по mod N коэффициент a многочлена f(x) из формулировки теоремы не равен 1 то обычно предлагаются следующие варианты сведения задачи определения x0. Если НОД(a,N)=1, то умножив многочлен на a–1(mod N), получают многочлен, удовлетворяющий условию теоремы. Если НОД(a,N)¹1, то раскладывают N на множители.

Атака на RSA с маленькой экспонентой шифрования при передаче связанных сообщений. Основная идея. Предположим, что имеется два сообщения m1,m2Î(ℤ/N)*, связанных соотношением

m2=sm1+r(mod N). (**)

Пусть эти сообщения зашифрованы с помощью RSA с открытым ключом <N,3>

с1 ºm13(mod N), с2 ºm23(mod N).

Тогда располагая c1,c2,s,r,N, противник может вычислить m1 по формуле

m1 º º (mod N),

если Î(ℤ/N)*. Аналогичная формула имеет место для открытого ключа <N,5> и сообщений m1,m2, связанных так, что m2ºm1+1(mod N). Пусть с1 º m,
с2 º m (mod N). Тогда

Однако, при больших e аналогичные формулы являются чрезвычайно сложными. Поэтому поступают следующим образом. Пусть сообщения m1,m2 связаны соотношением (**) и с1ºm (mod N), с2 º m (mod N). Тогда m1 есть общий корень по mod N двух многочленов

xe-c1, (sx+r)e-c2

Применим к этим многочленам алгоритм Евклида. Обычно алгоритм Евклида применяется над полем. В этом случае каждый шаг алгоритма может быть реализован, т.к. ненулевой элемент поля обратим в этом поле. В кольце ℤ/N имеются необратимые ненулевые элементы. Отсюда следует, что можно выполнить шаг алгоритма Евклида для многочленов над ℤ/N или факторизовать N. Сложность применения алгоритма Евклида к многочленам xe-c1, (sx+r)e-c2 равна O(e2) операций по mod N. Имеется асимптотически быстрый алгоритм Евклида, сложность которого не более O(e1+e) операций по mod N.
В результате применения алгоритма Евклида к указанным многочленам получим

Îℤ/N[x].

Если deg g(x)=1, то общий корень этих многочленов легко находится во многих практических системах, используется значение e=216+1. Таким образом, изложенный здесь метод вычисления m1 является эффективным для таких систем.

Обобщения.

1.Пусть вместо (**) выполняется соотношение

m2 º p(m1) (mod N),

где p(х) многочлен из ℤ/N[x] степени d. Пусть также m1, m2 зашифрованы с помощью открытого ключа <N,e>. Тогда m1 – общий корень многочленов xe-c1 и p(x)e-c2 по mod N.

2. Пусть сообщения m1,m2Îℤ/N* связаны ещё более сложным соотношением

p(m1 ,m2) º 0 (mod N),

где p(x,y) – многочлен из ℤ/N[x,y] степени d. Отсюда получается система трёх полиномиальных уравнений от двух неизвестных:

p(m1 ,m2) º 0 (mod N),

m -с1º 0 (mod N), (***)

m -с2º 0 (mod N).

3. Очевидным обобщением системы (***) является следующая система уравнений

…..

относительно сообщений m1, m2, .., mkÎ(ℤ/N)*. Пусть. Известно, что сложность вычисления открытых сообщений m1, m2, .., mk оценивается величиной

операций в ℤ/N.

Маленькая экспонента расшифрования в системе RSA. Для уменьшения времени расшифрования выбирают небольшое значение экспоненты расшифрования d(modj(N)), затем вычисляют экспоненту зашифрования из сравнения edº1(modj(N)). Обычно ускорение процесса расшифрования необходимо там, где RSA используется для идентификации или цифровой подписи. Так, например, рядовой пользователь располагает электронной карточкой, то есть маломощным компьютером, который не способен быстро выполнить большой объем вычислений. Например, возвести число в большую степень по modN. Как будет показано, при маленьких d система RSA оказывается нестойкой, так как в этом случае модуль N может быть факторизован.

Атака на RSA с экспонентой расшифрования..Пусть N=pq, где p, q такие простые числа, что q<p<2q и k таково, что

ed=1+kj(N), 0<e<j(N), 0 < d <

Известно, что факторизация такого числа N возможна за число шагов алгоритма Евклида, примененного к паре целых чисел e и N. Следовательно, при указанных параметрах для шифра RSA существует эффективный алгоритм дешифрования.

Алгоритм факторизации N основан на следующей теореме Хинчина (1978): всякая несократимая рациональная дробь a/b, удовлетворяющая неравенству

,

есть подходящая дробь числа a.

Атака на RSA с экспонентой расшифрования d = O(N0,292). Пусть N=pq, где p, q простые числа равные по порядку величине. Экспонента расшифрования d удовлетворяет неравенству

d < Nd, 0 < d < 1.

Значение e удовлетворяет e » N или e существенно меньше N.

При указанных параметрах для шифра RSA существует эффективный алгоритм дешифрования, основанный на факторизации N.

Атака на RSA с использованием частичной информации о простых числах p,q. Пусть N=pq модуль в системе RSA, двоичная длина которого равна n. Двоичная длина простых сомножителей p,q равна приблизительно. Пусть заданы дополнительно старших (младших) разрядов числа p или q. В этом случае известен эффективный алгоритм факторизации числа N.

Атака на RSA с использованием частичной информации о секретной экспоненте расшифрования.Пусть <N, d> и <N, e> – секретный и открытый ключ в системе RSA, где двоичная длина N равна n бит, а двоичная длина p, q равна приблизительно бит. Известно, что, зная младших разрядов d, можно вычислить значение d за равное e применений алгоритма из предыдущего пункта.

Атака на RSA при небольшой экспоненте шифрования е.Известен эффективный алгоритм вычисления половины старших разрядов d при небольшой экспоненте шифрования е.

Атака на RSA с помощью временного анализа.Предположим, что имеется возможность измерять время возведения m в секретную степень d. Рассмотрим процесс возведения в степень бинарным методом. Пусть есть двоичное разложение числа d. Положим z = m и c = 1. Для i=0,1,..,n выполним одну итерацию алгоритма возведения, которая состоит из двух шагов:

1) если di =1, то, 2) z z2 (mod N). В итоге. Очевидно, что время выполнения одной итерации существенно зависит от значения di. Оно, конечно, зависит еще и от значения m. Поэтому, фиксируя время выполнения одной итерации для набора случайных чисел mj, 1 £ j £ t, можно определить среднее время ее выполнения. Это дает возможность точно определить di. Детали этого метода изложены в статье [Kocher, 1996]. Похожим методом можно вычислить di по потребляемой мощности. Это в принципе можно сделать, если возведение производит электронная карта.

Китайская теорема об остатках.Некоторые реализации RSA используют китайскую теорему об остатках для ускорения вычисления. Пусть

и .

Тогда вычислив сначала

и

можно найти с по формуле

,

где и. Этот способ примерно в 4 раза быстрее, чем вычисление с по обычной формуле. Однако такое использование китайской теоремы может быть опасным. Предположим, что в компьютере, который производит это вычисление, произошел сбой. Например, при копировании содержимого регистра один бит был скопирован неправильно. Тогда подпись с под сообщением m (если вычисляется подпись) оказывается неверной. Располагая этой неверной подписью, противник находит разложение N. Действительно, пусть при вычислении число cp оказалось вычисленным неверно. Таким образом, пусть неверное значение, в то время как cq было вычислено правильно. Результирующий вычет равен. Тот факт, что подпись неверна, проверить легко, критерием является

≢ .

В этом случае противник вычисляет

.

Метод вскрытия стандарта PKCS1. Пусть двоичная длина модуля N в системе RSA равна n бит. Пусть m сообщение двоичной длины l<n бит. Перед шифрованием естественно дополнить сообщение m до сообщения длины n строкой случайных бит. Это делается для рандомизации получаемого в итоге блока шифртекста. Например, в одной из ранних версий PKCS1 (Public Key Cryptographic Standard 1) используется такой подход. После дополнения сообщение выглядит следующим образом

 

случайные биты m

 

Такое сообщение шифруется с помощью RSA. Начальный блок сообщения имеет длину 16 и содержит 02, то есть равен (0,0,..,0,1,0), что указывает на наличие далее строки случайных бит. При получении, сообщение расшифровывается. Проверяется наличие начального блока из 16-ти бит равного 02, удаляются случайные биты и т.д. Однако некоторые реализации построены таким образом, что не обнаружив в начальных 16-ти битах расшифрованного сообщения стандартного 02, компьютер выдает сообщение об ошибке. То есть отправитель сообщения получает сообщение об ошибке. В статье [8] показано как это приводит к вскрытию сообщения m.

Пусть противник перехватывает шифртекст с, зашифрованный на открытом ключе Алисы <N, e> и ей предназначенный. Противник выбирает случайное r Îℤ/N, вычисляет и передает Алисе. Программа, которая работает на компьютере Алисы, пытается расшифровать. Компьютер возвращает сообщение об ошибке или не делает этого. В последнем случае противник делает вывод, что первые 16 бит расшифрованного сообщения составляют 02. Несколько таких успешных попыток достаточно для дешифрования с.

 

Литература

 

1. Bellar M. Rogoway P. Optimal asymmetric encryption. Eurocrypt’94, LNCS 950, 1995. – 92-111.

2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.

3. Coppersmith D. Solving linear equations over GF(2) via a block Wiedemann algorithm. Math. Comp. – 1996

4. M. Tatebayashi, N. Matsuzakai, D. B. Newman, Key distribution protocol for digital mobile communication systems, Crypto’89, LNCS vol.435, Springer, 1990, 324-333.

5. M. K. Franklin, M. K. Reiter, Verifiable signature sharing, Eurocrypt’95, LNCS vol. 921, Springer, 1995, 50-63.

6. Хинчин А.Я. Цепные дроби. – М.: Наука, 1978.

7. Kocher P. Timing attacks on implementations of Diffe-Hellman, RSA, DSS, and other systems. Proceedings of Crypto'96. Lecture notes in computer science N 1109. – 1996. – c. 104-113.

8. D. Bleichenbacher, Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS#1, Crypto’98, LNCS vol. 1462, Springer,1998,1-12.

 

 


Глава 45.

еще рефераты
Еще работы по информатике