Из этих равенств при некотором



Скачать 169.99 Kb.
Дата15.10.2012
Размер169.99 Kb.
ТипДокументы




и

uuu arara r(modn).

Из этих равенств при некотором q имеем

rrr= a rrr+ nq. (4)

Так как НОД(r,n)=1, i=1,…, (n), то НОД(rrr,n)=1. Поэтому в равенстве (4) q делится на rrr. Отсюда получаем

1= a+nq’.

Полученное равенство эквивалентно утверждению теоремы.

Следствие 4 (Малая теорема Ферма). Если n - простое число, НОД(a,n)= 1, то

a 1(modn).

Следствие 5. Если НОД(a,n) = 1, то

a a(modn).

То есть, при известном значении функции (n) обращение в кольце вычетов сводится к возведению в степень.

В заключение приведем без доказательства полезную теорему [Massey 94].

Теорема 4. (Китайская теорема об остатках).

Пусть Тогда для единственное решение системы .

4.4. Квадратичные вычеты.
Пусть р- простое, а < р, р>2.

Определение 1. а – квадратичный вычет .

Пример 1.
Пусть р = 7, тогда 1, 2, 4 – квадратичные вычеты, а 3, 5, 6 – не квадратичные вычеты:

(mod 7)

Теорема 1. Существует квадратичных вычетов и не квадратичных вычетов в GF(p). У каждого квадратичного вычета существуют два корня такие, что , где называется основным корнем.

Д о к а з а т е л ь с т в о. При следовательно, уравнение = x имеет не менее двух корней. Если , то



Тогда или -(n) или (n). Отсюда имеет ровно два значения корня квадратного или ни одного. Ровно половина ненулевых элементов GF(p) есть квадратичные вычеты.

Теорема 2. Если n = p q, где p, q – простые, то квадратичных вычетов по modn и у каждого квадратичного вычета 4 корня.

Пример 2. n = 35 = 5 7 квадратичных вычетов по
mod 35: 1, 4, 9, 11, 16, 29. Каждый квадратичный вычет имеет ровно 4 корня.

Определение 2. Для целого а и простого p>2 символ Лежандра определяется следующим образом:

L(a, p) = 0, если р/а;

L(a, p) = 1, если а- квадратичный вычет по mod p;

L(a, p) = -1, если а- не квадратичный вычет по mod p.

Теорема 3. L(a, p) = .

Д о к а з а т е л ь с т в о.

  1. .

  2. а- квадратичный вычет, то есть . Тогда по теореме Ферма

.

Таких a ровно . Рассмотрим уравнение

.

Любое а – его корень. Отсюда каждое a является корнем одного из сомножителей в следующем уравнении:

.

Значит, значений квадратичных вычетов а являются корнями уравнения

.

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

.

Если а- не квадратичный вычет, тогда

.

Теорема доказана.

Определение 3. Пусть р- простое, g < p. g называется примитивным элементом мультипликативной группы поля GF(p) (или примитивным элементом по mod p), если 0 < n p-1 a: .

Пример 3. При p = 11, 2 есть примитивный мультипликативной группы GF(11).



Каждое число n(1; 10) может быть представлено в виде .

Для р = 11 числа 2, 6,7,8 являются примитивными элементами мультипликативной группы GF(11). Остальные не являются примитивными элементами.

Замечание. В GF(p) (p-1) примитивных элементов.

Нахождение примитивного элемента, вообще говоря, не является простой задачей. Примитивный элемент находится легко, если известна факторизация р-1. Пусть - простые множители р-1. Для того чтобы проверить, является ли g примитивным элементом по mod p, вычисляется . Если для некоторого i это число равно 1, то g- не примитивный элемент. Если это не выполняется ни для какого , то g- примитивный элемент.

Пример 4. При р = 11 имеем р - 1 = 10 = 2 5. Проверим, что число 2 является примитивным элементом мультипликативной группы GF(11).



следовательно, 2 – примитивный элемент. Проверим 3.



следовательно, 3 не примитивный элемент мультипликативной группы GF(11).
4.5. Факторизация. Логарифмирование в конечных полях.
Факторизация числа означает нахождение его простых множителей.

Пример 1.

10 = 2 5,

60 = 2 2 3 5,

252601 = 41 61 101,

- 1 = 3391 23279 65933 1868569 1066818131868207.

Проблема факторизации – одна из старейших в теории чисел. Сложность самого быстрого алгоритма факторизации [Schn96]:



Пусть (n) – число простых чисел n.

Теорема. (Чебышева о числе простых чисел [Massey 94]).

.

Все современные тесты на простоту основаны на обобщениях теоремы Ферма.

Если имеет порядок N ((modp)) в мультипликативной группе поля GF(p), что предполагает, что - различны, и . Тогда i называется дискретным логарифмом от по основанию и обозначается .



при этом:

  1. вычислять экспоненту легко: требуется не более операций в алгоритме быстрого возведения в степень;

  2. вычисление дискретного логарифма в GF(p) является очень сложной задачей, когда р-1 имеет большой простой множитель.

Для вычисления в GF(p), когда имеет мультипликативный порядок N ((modp)), используют алгоритм Shank [Massey 94]. Выбирается некоторое целое d , где .

Тогда x = Qd + r, 0 r и

.

Далее все вычисления ведутся в GF(p).

  1. Для = 0, 1, … , d-1 вычисляем а = aa и запоминаем - это все логарифмы такие, что

  2. Составляем таблицу (,) для 0 d – таблицу малых логарифмов.

  3. Вычисляем с помощью алгоритма быстрого возведения в степень.

Заметим, что





и, следовательно,

.

  1. Для q = 0, 1, 2, … вычисляем до тех пор, пока не станет равным некоторому в таблице.

  2. Тогда .

Сложность алгоритма имеет порядок операций умножения и память .

Пример 2. Найдем здесь 5- примитивный элемент GF(23), и N = 22 (522 = 1(mod23)) .

  1. d = 5





(2)






1

2

4

5

10

0

2

4

1

3

(3)



(4) y = 13 не принадлежит входу в таблице (q = 0).



Следовательно,

.

= 14

и для его нахождения требуется 5 операций умножения.

Проблема дискретного логарифмирования упрощается, если основание логарифма имеет порядок N и и сводится к дискретному логарифмированию по основанию, имеющему порядок , и дискретному логарифмированию по основанию, имеющему порядок .

Алгоритм [Massey 94] нахождения дискретного логарифма, когда основание логарифма имеет порядок N и приведен ниже. Пусть

.

  1. Вычисляем с помощью алгоритма быстрого возведения в степень.

  2. Вычисляем с помощью алгоритма быстрого возведения в степень.

  3. Находим .

  4. Вычисляем с помощью алгоритма быстрого возведения в степень.

  5. Вычисляем .

  6. Вычисляем с помощью алгоритма быстрого возведения в степень.

  7. Находим .

  8. Получаем x = xN + x.


4.6. Схема RSA.
RSA [Schn 96] используется как для шифрования, так и для подписи.

Выберем p и q – большие простые числа. Пусть модуль n = pq, функция (n) = (p-1)(q-1) – функция Эйлера. Возьмем произвольное
1 е(n) такое, что НОД(е, (n)) = 1. Тогда существует единственное
1 d (n) такое, что ed(mod(n)) = 1.

Система шифрования RSA – это система с открытым ключом, где
е –открытый, а d – секретный ключи. Если 0 x это открытое сообщение, то шифрсообщение получается следующим образом:

С = х(mod n).

Возможность расшифрования следует из следующей теоремы.

Теорема 1. Если p и q – большие простые числа, ed(mod(n)) = 1, то х, 0 x

(х)(modn) = x.

Д о к а з а т е л ь с т в о. Пусть НОД(х, n) =1. Тогда

(х) = х = x .

Поэтому по теореме Эйлера

(х)(modn) = (х( x(modn)))(modn)= (x 1)(modn) = x.

Если НОД(х,n) 1, то или х =0(modn), или НОД(х,n) = p, или НОД(х,n) = q. Если х =0(modn), то х =0(modn). Пусть НОД(х,n) = p. Тогда х = хp, где
(х, n) =1.

х= x= pxpx y(modpq).

Если mp= y(mod(pq)), то mp = pqk + y, следовательно, y = py. Тогда
m y(modq. Следовательно,

x(()) y (modq).

По теореме Ферма z 1 (modq). Поэтому

x= xp(mod(pq)) = y (modn) х(modn),

что и требовалось доказать.

Открытый и шифрованный тексты эффективно вычисляются, если известны е и d при помощи алгоритма быстрого возведения в степень. Если искать секретный ключ d по известному открытому ключу е, то надо
знать (n).

Теорема 2. Вычисление (n) = (p-1)( q-1) эквивалентно (с точностью до алгоритма полиномиальной сложности) факторизации числа n = pq.

Д о к а з а т е л ь с т в о. Пусть известны n и (n). Тогда p и q находятся быстро. Это следует из следующих равенств.

(n) = (p-1)(q-1) = pq-p-q+1 = n-p-q+1.

Отсюда

p+q= n-(n)+1,

pq = n.

По теореме, обратной к теореме Виета, p и q являются корнями квадратного уравнения:

х- (n -(n)+1)x + n = 0.

Вычисление корней – полиномиальный алгоритм. Обратно, если известны p и q, pq = n, то (n) = (p-1)(q-1). Теорема доказана.
Подпись RSA.

Пусть М – сообщение, которое надо подписать. Подпись получается по следующему алгоритму:

С = М(mod n),

тогда (М, С) - сообщение с подписью. Проверка подписи осуществляется следующим образом

С( mod n) = М(mod n) = М’.

Если М = М, то подпись верна.

4.7. Атаки на RSA.


  1. Активная атака с помощью выбранного шифртекста.

Пусть злоумышленник Е перехватывает шифрованное сообщение с от корреспондента А к корреспонденту В. Пусть c = z(modn), где z- открытый текст, е- открытый ключ и , где d- секретный ключ. Е хочет прочитать открытый текст z. Для этого Е выбирает число r, r < n, и вычисляет с помощью открытого ключа



так, что

Пусть Е подписывает у А y с помощью секретного ключа d, т.е.

.

Затем Е вычисляет

.

Таким образом, Е читает z.

  1. Предположим, что Е хочет получить подпись на число N у А, а А никогда не подпишет N. Тогда Е выбирает произвольным образом Х и вычисляет

.

Затем Е вычисляет M = Y N и посылает А на подпись. А подписывает М и возвращает Е число . Е вычисляет



,

что и является подписью N.

  1. Пусть Е хочет подписать у А число . Тогда Е генерирует 2 сообщения и так, что

.

Подписав у А сообщения и , Е затем вычисляет подпись для :



  1. Атака с использованием общего модуля.

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



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

.

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



  1. Атака с малой экспонентой.

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



и пусть - взаимно- простые числа. Следовательно, Мы можем найти из используя обращение китайской теоремы об остатках, а затем найти х путём извлечения кубического корня из .

Похожие:

Из этих равенств при некотором iconЗакрепление составления равенств и выражений
Цели: закрепить знания детей о составлении равенств и выражений; расширить представления детей о космосе
Из этих равенств при некотором iconСказка ключницы Пелагеи
В некотором царстве, в некотором государстве жил-был богатый купец, именитый человек
Из этих равенств при некотором icon«Сказка про Иванушку дурачка и Конька- горбунка»
Сказочница: в некотором царстве, в некотором государстве, сразу как направо пойдешь
Из этих равенств при некотором iconРазнообразие растений
У. Сказки начинаются словами "В некотором царстве, в некотором го- сударстве " Мы знаем, что всё живое делится на царства
Из этих равенств при некотором iconЗнакомство с музыкальными инструментами
Сегодня мы с вами отправимся в сказку. В некотором царстве, в некотором, государстве жили-были музыкальные инструменты. Они были...
Из этих равенств при некотором iconРедьярд Киплинг Откуда у носорога шкура
В некотором царстве, в некотором государстве, на Красном море, у самого берега, стоял Необитаемый остров. На острове жил парс, а...
Из этих равенств при некотором iconНа судьбу не жалуйся, пятерке порадуйся
В некотором сфушном царстве, в некотором сфушном государстве жил был добрый мудрец. И рассказывал он об интересном предмете морфологии...
Из этих равенств при некотором iconЕсли,, то и правило дифференцирования сложной фкп
Заметим, что перечисленные формулы имеют место при предположении существования всех производных, входящих в правые части равенств....
Из этих равенств при некотором iconВ некотором царстве, в некотором государстве жил был помещик, жил и на
Всего у него было довольно: и крестьян, и хлеба, и скота, и земли, и садов. И был тот помещик глупый, читал газету "Весть" и тело...
Из этих равенств при некотором iconЗадача о путешествиях в качестве дальнейшего примера приложения этих идей рассмотрим следующую задачу о путешествиях, которая воз­никает в самых разнообразных прикладных вопросах
В некотором порядке, и задан ряд чисел,где —время, потребное на путешествие из i-го города в j-й
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org