Рефетека.ру / Математика

Реферат: Тест числа на простоту

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


Во многих случаях требуется выяснить, является ли большое число 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, Тест числа на простоту.

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

Берется открытый ключ (e,n) стороны A, вставляется открытый текст L, передается шифрованное сообщение:


Тест числа на простоту


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

Принимается зашифрованное сообщение С, для расшифровки сообщения применяется секретный ключ (d,n):

Тест числа на простоту


Цифровая подпись


Система RSA может использоваться не только для шифрования, но и для цифровой подписи.

Предположим, что абоненту A нужно отправить абоненту B ответ L1, подтверждённый цифровой подписью.

Алгоритм подписи

Взять открытый текст L1, затем создаем цифровую подпись w c помощью секретного ключа (d,n).


Тест числа на простоту


Далее передаем (L1,w), которая состоит из сообщения и подписи.

Алгоритм проверки подлинности подписи

Принять (L1,w), берем открытый ключ (e,n) абонента А, проверяем подлинность подписи


Тест числа на простотуподпись верна


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

Важное свойство цифровой подписи заключается в том, что её может проверить каждый, кто имеет доступ к открытому ключу ее автора. Один из участников обмена сообщениями после проверки подлинности цифровой подписи может передать подписанное сообщение ещё кому-то, кто тоже в состоянии проверить эту подпись.

Заметим, что подписанное сообщение L1 не зашифровано. Оно пересылается в исходном виде и его содержимое не защищено. Путём совместного применения представленных выше схем шифрования и цифровой подписи в системе RSA можно создавать сообщения, которые будут и зашифрованы, и содержать цифровую подпись. Для этого автор сначала должен добавить к сообщению свою цифровую подпись, а затем - зашифровать получившуюся в результате пару (состоящую из самого сообщения и подписи к нему) с помощью открытого ключа принадлежащего получателю. Получатель расшифровывает полученное сообщение с помощью своего секретного ключа. Если проводить аналогию с пересылкой обычных бумажных документов, то этот процесс похож на то, как если бы автор документа поставил под ним свою печать, а затем положил его в бумажный конверт и запечатал, с тем чтобы конверт был распечатан только тем человеком, кому адресовано сообщение.


RSA

Пример

Сначала нужно сгенерировать ключ

Выбираем два простых ключа p=13, q=41

Вычисляем модуль n=p*q = 13*41 =533

Вычисляем функцию Эйлера φ (n) = (p-1) * (q-1) = (13-1) * (41-1) = 480

Выбираем открытый показатель е = 13

Вычисляем секретный показатель d = 37

Открытый ключ (e,n) = (13, 533)

Секретный ключ (d,n) = (37, 533)

Шифрование

Выбираем открытый текст L = 4545

Вычисляем шифротекст G (L) = Le mod n = 99

Расшифрование

Вычисляем исходное сообщение


N (C) = Сd mod n = 4545


Алгоритм Эль-Гамаля


Схема Эль-Гамаля (Elgamal) - криптосистема, предложенная в 1984 году. Схема Эль-Гамаля лежит в основе стандартов электронной цифровой подписи в США и России.

Генерация ключей

Генерируется случайное простое число p длины n.

Выбирается произвольное целое число g, являющееся первообразным корнем по модулю p.

Выбирается случайное число x из интервала (1,p), взаимно простое с p-1.


Вычисляется Тест числа на простоту


Открытым ключом является тройка (p, g, y), закрытым ключом - число x.

Работа в режиме шифрования выглядит следующим образом:

шифруется сообщение М

Выбирается случайное секретное число k, взаимно простое с p − 1.

Вычисляется a = gk (mod p), b = yk M (mod p), где M - исходное сообщение.

Пара чисел (a,b) является шифротекстом.

Длина шифротекста в схеме Эль-Гамаля длиннее исходного сообщения M вдвое.

Расшифрование сообщение осуществляется следующим образом

Зная закрытый ключ x, исходное сообщение можно вычислить из шифротекста (a,b) по формуле:


Тест числа на простоту

Тест числа на простоту и Тест числа на простоту


Режим подписи сообщения


При работе в режиме подписи предполагается наличие фиксированной хеш-функции h, значения которой лежат в интервале (1, p − 1).


Подпись сообщений


Для подписи сообщения M выполняются следующие операции:

Вычисляется дайджест сообщения M: m = h (M).

Выбирается случайное число 1 < k < p − 1 взаимно простое с p-1 и вычисляется Тест числа на простоту.

С помощью расширенного алгоритма Евклида вычисляется число s, удовлетворяющее сравнению:


Тест числа на простоту


Подписью сообщения M является пара (r,s).


Проверка подписи


Зная открытый ключ (p,g,y), подпись (r,s) сообщения M проверяется следующим образом:

Проверяется выполнимость условий: 0 < r < p и 0 < s < p − 1. Если хотя бы одно из них не выполняется, то подпись считается неверной.

Вычисляется дайджест m = h (M).

Подпись считается верной, если выполняется сравнение:


Тест числа на простоту.


DSS (Digital Signature Standard) цифровой подпись

Алгоритм:

выбирается простое число q приблизительно в 160 бит (для этого используются генератор случайных чисел и тест на простату)

выбирается другое простое число р, сравнимое с 1 по модулю q размером приблизительно в 512 бит

выбирается порождающий элемент, для этого вычисляется Тест числа на простоту для случайного целого g0, если g ≠1, то он и будет порождающим элементом

выбирается секретный ключ как случайное целое число х из диапазона 0<x<q. В качестве открытого ключа берется Тест числа на простоту.

Пример. Пусть А хочет подписать сообщение. Сначала А принимает своему ОТ хеш функцию и получает целое число h из диапазона 0<h<q. Затем А выбирает случайное целое k из того же диапазона и вычисляет Тест числа на простоту. Пусть r - наименьший неотрицательный вычет по модулю q последнего выражение. Значит, gk сначала вычисляется по модулю р, а результат приводиться по меньшему простому модулю q. Наконец, А находит такое целое s, что Тест числа на простоту. Пара (r,s) вычетов по модулю q является ее подписью.

Чтобы проверить подпись, получатель В вычисляет Тест числа на простоту и Тест числа на простоту. Потом он вычисляет Тест числа на простоту. Если результат сравним с r по модулю q, то подпись считается подлинной.

Литература


Дж. Андерсон, Дискретная математика и комбинаторика, М.: Вильямс - 2003.

Н. Коблиц, Курс теории чисел и криптографии, М.: научное изд-во ТВП, 2001.

http://ru. wikipedia.org

Рефетека ру refoteka@gmail.com