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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


Реферат Алгоритм Миллера-Рабина и малая теорема Ферма. Псевдопростые числа, тест на простоту. Криптографический алгоритм шифрования с открытым ключом и цифровой подписью. Создание открытого и секретного ключей. Режим подписи сообщения и способы ее проверки.

Информация:

Тип работы: Реферат. Предмет: Математика. Добавлен: 12.12.2009. Сдан: 2009. Уникальность по antiplagiat.ru: --.

Описание (план):


9

Тема: Алгоритм Миллера-Рабина и малая теорема Ферма

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

Тест на простоту представляет собой критерий того, что число n не является простым. Если n "проходит" этот тест, то оно, возможно, простое число. Если оно "проходит" целый набор тестов на простоту, то весьма вероятно, что оно действительно является простым. С другой стороны, если n не проходит хотя бы одного теста на простоту, то оно совершенно определенно является составным. Однако при этом остается нерешенной трудная задача нахождения простых делителей числа n (задача факторизации). В общем случае для разложения на множители большого числа, о котором известно, что оно составное (поскольку оно не прошло теста на простоту), требуется порядка величины. Надежность криптосистемы RSA основывается на том предположении, что значительно легче найти два чрезвычайно больших простых числа n и q, чем, зная n=p*q, но не p или q, найти делители числа n.

Псевдопростые числа

Пусть n - большое нечетное число, и мы хотим определить является ли n простым.

Теорема (Ферма). Если n - простое число, то согласно малой теореме Ферма для любого такого b, что НОД (b, n) =1,. (1)

Если n - не простое число, то (1) тоже может выполняться (хотя это маловероятно).

Определение. Если n - нечетное составное число, b - целое число, НОД (n, b) =1, и (1) выполняется, то n называется псевдопростым числом по основанию b.

Другими словами, "псевдопростое" число - это число n, которое "претендует" быть простым, проходя тест (1).

Пример 1. число n = 91 - псевдопростое по основанию b = 3, так как . Однако, 91 не есть псевдопростое число по основанию 2, так как . Если бы мы еще не знали, что 91 составное число, то

соотношение доказало бы нам это.

Сильно псевдопростое число. Рассмотрим теперь еще один вид критериев простоты, который в определенном смысле даже лучше теста Соловея - Штрассена, основанного на определении псевдо простаты по Эйлеру. Это тест Миллера-Рабина, основанный на вводимом ниже понятии "сильно псевдо простаты". Предположим, что n - большое нечетное натуральное число и . Пусть, далее, n - псевдопростое по основанию b, т.е. . Идея критерия сильной псевдо простаты такова. Пусть , t - нечетно. Если последовательно вычислять , то при простом n первым элементом, отличным от 1, должен быть элемент

1, так как при простом n единственными решениями сравнения являются +1 и-1. практически действии выполняются "в обратном направлении". Полагаем , t - нечетно. Вычисляем по модулю n. Если , возводим в квадрат по модулю n, получаем , затем вновь возводим в квадрат и т.д. до тех пор, пока не получим 1: . Тогда, если n - простое, предыдущим числом должно быть - 1, в противном случае мы получаем доказательство того, что n составное.

Определение. Пусть n - нечетное составное число и n-1=2st, t - нечетно. Пусть . Если n и b удовлетворяют одному из условий:

1) ;

2) существует такое r, , что

(2)

то n называет сильно псевдопростым по основанию b.

Тест Миллера-Рабина. Предположим, что мы хотим определить, является большое натуральное число n простым или составным. Представим n-1 в виде , t нечетно, и выберем случайное целое число b, 0<b<n. Сначала вычисляем по модулю n. Если получается , то заключением, что n прошло тест (2) при данном b, и производим новый случайный выбор b. В противном случае возводим в квадрат по модулю n, результат вновь возводим в квадрат по модулю n и продолжаем так до тех пор, пока не получим - 1. Если это происходить, то мы считаем, что n прошло тест. Если же это не происходить, т.е. если мы получаем , в то время как , то n не проходить тест, и это доказывает, что n - составное число. Если мы k раз случайно выбирали разные основания b и n каждый раз проходило соответствующий тест, то число n имеет не более шанса быть составным.

Применение этих теорем можно увидеть в следующих алгоритмах:

Алгоритм RSA

RSA (от фамилий криптографов Rivest, Shamir и Adleman) криптографический алгоритм шифрования с открытым ключом и цифровой подписью.

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

Если х известно, то f (x) вычислить относительно просто

Если известно y = f (x), то для x нет простого пути вычисления

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

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

В криптографической системе с открытым ключом у каждого абонента есть открытый ключом (public key) и секретный ключом (secret key). Каждый ключ часть информации. В криптографической системе RSA каждый ключ состоит из пары целых чисел. Каждый абонент набирает свой открытый и секретный ключ самостоятельно. Секретные ключи секретны, открытые ключи можно сообщать. Открытый и секретный ключи каждого абонента обмена сообщениями взаимно обратные.

Алгоритм создания открытого и секретного ключей

Выбираются два случайных простых числа p и q заданного размера (например, 512 битов каждое).

Вычисляется их произведение n = pq

Вычисляется значение функции Эйлера от числа n:

Выбирается целое число e, взаимно простое со значением функции . e - простые числа, содержащие небольшое количество единичных битов в двоичной записи. Например, простые числа Ферма 17, 257, 65537.

Вычисляется число d, мультипликативно обратное к числу e по модулю , т. е число, удовлетворяющее сравнению:

;

то есть , где k любое натуральное число (0, 1, 2…).

Пара G = (e,n) публикуется в качестве открытого ключа RSA (RSA public key).

Пара N = (d,n) играет роль секретного ключа RSA (RSA secret key) и держится в секрете.

Число n называется модулем, а числа e и d - открытой и секретной экспонентами, соответственно.

Допустим абонент В хочет послать сообщение абоненту В по коммутационному каналу.

Сообщением являются целые числа лежащие от 0 до n-1, .

Алгоритм шифрования:

Берется открытый ключ ( и т.д.................


Перейти к полному тексту работы



Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.