Основы криптографии
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
нератором, называется примитивным или базовым, все его кoэффициенты взаимно просты.
Для поля Галуа GF(2n) криптографы любят использовать в качестве модулей трехчлены p(x) = x" + x + 1, так как длинная строка нулей между коэффициентами при x" и x позволяет просто реализовать быстрое умножение по модулю. Полином должен быть примитивным, в противном случае математика не будет работать, x" + x + 1 примитивен для следующих значений n, меньших чем 1000
1, 3, 4, 6, 9, 15, 22, 28, 30,46, 60, 63, 127, 153, 172, 303,471, 532, 865, 900
Существуют аппаратные реализации GF(2127), где px = x121 + x + 1.
Разложение на множители
Разложить число на множители - значит найти его простые сомножители.
= 2*5
= 2*2*3*5
=41*61*101
- 1 =3391*23279*65993*1868569*1066818132868207
Разложение на множители является одной из древнейших проблем теории чисел. Этот процесс несложен, но требует времени. Это пока остается так, но ряд сдвигов в этом искусстве все же произошел. Сегодня самым лучшим алгоритмом является:
Решето числового поля чисел (Number field sieve, NFS).
Решето общего числового поля - это самый быстрый из известных алгоритм для чисел размером 1 10 и более разрядов . В своем первоначальном виде он был непрактичен, но за последние несколько лет он был последовательно улучшен . NFS все еще слишком нов, чтобы бить рекорды разложения на множители, но скоро все перемeнится. Ранняя версия использовалась для разложения на множители девятого числа Ферма: 2512 + 1 .
Другие алгоритмы, вытесненные NFS:
Квадратичное решето. Это самый быстрый из известных и чаще всего использовавшийся алгоритм для чисел, длина которых меньше 1 10 десятичных разрядов. Более быстрая версия этого алгоритма называется множественным полиномиальным квадратичным решетом. Самая быстрая версия называется двойной вариацией множественного полиномиального квадратичного решета с большим простым числом.
Метод эллиптической кривой. Этот метод использовался для поиска не более, чем 43-разрядных множителей.
Проверка делением. Этот самый старый алгоритм разложения на множители состоит из проверки каждого простого числа, меньшего или равного квадратному корню из раскладываемого числа.
В 1970 году большой новостью стало разложение на множители 41-разрядного трудного числа. ("Трудным" является такое число, у которого нет маленьких множителей, и которое не обладает специальной формой, позволяющей упростить процесс.) Десять лет спустя разложение в два раз более длинного числа заняло лишь несколько часов на компьютере Cray .
В 1988 году Карл Померанс (Carl Pomerance), используя обычные СБИС, спроектировал устройство для paзложения на множители . Размер числа, которое можно было разложить, зависел только от размеров устройства, которое так и не было построено.
В 1993 году с помощью квадратичного решета было разложено на множители 120-разрядное трудное число. Раiет, потребовавший 825 mips-лет, был выполнен за три месяца реального времени.
Сегодня для разложения на множители используются компьютерные сети. Для разложения 1 16_разрядного числа в течение нескольких мeсяцев использовалось свободное время массива компьютеров, разбросанных по всему миру, - 400 mips-лет, потребовалось в сумме.
В марте 1994 года с помощью двойной вариации множественного полиномиального QS командой мaтематиков под руководством Ленстры было разложено на множители 129-разрядное (428-битовое) число. Вычисления выполнялись добровольцами в Internet - в течение восьми месяцев трудились 600 человек и 1600 компьютеров, возможно, самый большой в истории многопроцессорный конгломерат. Трудоемкость вычислений была в диапазоне от 4000 до 6000 mips-лет. Компьютеры соединялись по электронной почте, передавая свои результаты в центральное хранилище, где выполнялся окончательный анализ. В этих вычислениях использовaлись QS и теория пятилетней давности, NFS мог бы ускорить выполнение раiетов раз в десять . В cooтветствии с : "Мы делаем вывод, что широко используемые 512-битовые модули RSA могут быть вскрыты организацией, готовой потратить несколько миллионов долларов и подождать несколько месяцев." По оценкам авторов разложение 512-битового числа в 100 раз более трудоемко при использовании той же техники и только в 10 сложнее при использовании NFS и современной техники.
Квадратные корни по модулю n
Если n - произведение двух простых чисел, то возможность вычислить квадратные корни по модулю n вычислительно эквивалентна возможности разложить число n на множители. Другими словами, тот, кто знает простые множители числа n, может легко вычислить квадратные корни любого числа по модулю n, но для любого другого вычисление окажется таким же трудным, как и разложение на простые множители числа п.
Ну вот вроде с математическими основами разобрались. Математика дальше будет нам встречается повсеместно, но базовые знания уже есть..
Собственно говоря уже можно переходить к самим алгоритмам, но кажется я упустил некоторые моменты- а именно XOR, одноразовые блокноты и ключи (нет не от квартиры).
Простое XOR
XOR представляет собой операцию "исключающее или" : '^' в языке С или Q в математической нотации. Это обычная операция над битами :
0 = 0
1 = 1
0 = 1
1 = 1
Также заметим, что:
a a =0
abb=a
Казалось бы, запутанный алгоритм простого XOR по сути является ничем иным, как полиалфавитным шифром Вигенера. Здесь он упоминается только из-за распространенности в коммерческих программных продуктах,