Разработка методического пособия на тему "Генерация простых чисел"

Содержание

Введение.

Глава 1. Структура и содержание учебно-методического пособия.

1.1. Теоретическое наполнение раздела «Операции с большими числами»

1.2. Теоретическое наполнение раздела «Вероятностные тесты на простоту»

1.3. Теоретическое наполнение раздела «Доказуемо простые числа»

1.4. Разработка заданий для лабораторных и самостоятельных работ

1.5. Тесты для самопроверки

Глава 2. Апробация методического пособия.

2.1 Апробация в Тюменском государственном университете

2.2 Апробация в Тюменской государственной академии экономики, управления и права

Заключение

Список литературы

Приложение 1

Введение

Актуальность. Структура высшего очного образования предполагает сочетание различных видов и методов обучения: аудиторные занятия, домашняя и самостоятельная работа студентов, выполнение курсовых работ по специальности, по предметам. Аудиторные занятия, в свою очередь, делятся на лекционные, практические, лабораторные и семинарские занятия. Для изучения каждого предмета ГОС ВПО (Государственный образовательный стандарт высшего профессионального образования) по специальности определяет необходимое количество аудиторных занятий каждого вида, а также количество часов, выделенных на самостоятельную работу студентов.

В учебном плане специальности «Компьютерная безопасность» Тюменского государственного университета на изучение дисциплины «Криптографические методы защиты информации» отводится 70 часов лекций и 35 часов лабораторных занятий. Объем самостоятельной работы студента по дисциплине криптографические методы защиты информации составляет 82 часа. На изучение других предметов криптографической направленности – «Теоретико-числовые методы в криптографии» и «Криптографические протоколы» - также отведено в сумме 70 часов лекционных 35 часов практических занятий. В целом, на изучение криптографии в Тюменском государственном университете отводится 210 часов аудиторной нагрузки. Таким образом, криптография как общепрофессиональная и специальная дисциплина является одной из центральных в учебном процессе на специальности «Компьютерная безопасность».

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

Методическое обеспечение учебного процесса является одной из важнейших составляющих учебного процесса, особенно в части самостоятельной работы студентов. Связь между преподавателем и студентом не должна обрываться в тот момент, когда студент покидает аудиторию. Методические пособия, указания к выполнению лабораторных и самостоятельных работ, разработанные как дополнение к лекционному материалу, призваны осветить вопросы, встающие перед студентами в процессе выполнения ими самостоятельной работы. Материал, даваемый на лекции, как правило, носит общий характер, и из-за временных ограничений, а также различий в уровне подготовки студентов, различной мотивации к изучению предмета, интересу к различным разделам и аспектам данной дисциплины. В методическом пособии есть возможность рассмотреть каждое направление, каждый алгоритм более подробно, остановиться на вопросах его практической реализации, оговорить моменты, очевидные для одних студентов, но, возможно, представляющие существенные затруднения для других. Важным моментом является возможность рассмотреть в методическом пособии темы, не относящиеся непосредственно к изучаемой дисциплине, но использующиеся при ее освоении. Например, в разработанное пособие вошел раздел «Операции с большими числами», в котором не описано никаких криптографических алгоритмов, однако весьма полезный для студента.

Тематика генерации больших простых чисел, избранная для разработанного методического пособия, является ключевой для изучения криптографических методов защиты информации. Почти каждый криптографический алгоритм с открытым ключом требует генерации простого числа размером не менее 512 бит. В процессе использования таких алгоритмов приходится многократно создавать такие числа, причем некоторые алгоритмы требуют простые числа специального вида. Например, алгоритм цифровой подписи (ЦП) стандарта ГОСТ Р 34.11-94 требует генерации двух простых чисел p и q таких, что q является делителем числа (p-1). Таким образом, прежде чем приступать к реализации алгоритмов с открытым ключом, студент должен освоить тему генерации больших простых чисел.

На данный момент существует несколько алгоритмов получения простого числа. В справочной литературе, в том числе такой популярной как [9], рассмотренные алгоритмы приведены без математического обоснования, что в свою очередь не позволяет изучить материал в полном объеме. Для получения наиболее полных знаний следует пользоваться учебной литературой. Большинство изданий учебной литературы содержит не только описание самих алгоритмов, а также их математические обоснования, примеры и.т.п.

На данный момент среди учебной литературы достаточно слабо представлена тема генерации больших простых чисел. Большинство авторов в своих работах не освещают данную тему в полном объеме, а именно [1] осветил данную тему не в полном объеме, в работе присутствуют описание алгоритмов и оценки их сложности и надежности. [3] осветил данную тему не в полном объеме, в работе присутствуют описание алгоритмов их математическое обоснование и примеры, отсутствуют оценки сложности и надежности алгоритмов. [5] осветили тему не в полном объеме: в работе отсутствует математическое обоснование алгоритмов и их оценки сложности и надежности. [12] осветили данную тему достаточно полно, в работе присутствует описание алгоритмов их исчерпывающее математическое обоснование, присутствуют оценки сложности и надежности, примеры.

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

Целью данной работы является:

Разработать методическое пособие на тему «Генерация простых чисел» для специальности «Компьютерная безопасность» Тюменского государственного университета, включающее в себя теоретический материал, задания к практическим работам, указания к их выполнению и материалы для проверки качества выполненных заданий.

Для достижения данной цели пришлось решить следующие задачи:

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

2. Определить структуру и содержание методического пособия.

3. Оформить теоретический материал согласно структуре

4. Составить задания к лабораторным работам по теме к каждому из разделов.

5. Составить задания для самопроверки для каждой из глав пособия.

6. Апробировать составленное методическое пособие с целью улучшения подачи материала.

Апробация работы:

В 2007-2008 учебном году данное методическое пособие впервые было предложено студентам 4 курса специальности «Компьютерная безопасность» групп 347 и 347 Института математики и компьютерных наук Тюменского государственного университета для выполнения лабораторных работ по дисциплине «Криптографические методы защиты информации».

В сентябре - декабре 2008 года по материалу разработанного методического пособия в рамках преддипломной практики в Тюменской государственной академии мировой экономики, управления и права со студентами специальности «Прикладная информатика» были проведены практические занятия по дисциплине «Информационная безопасность» в объеме 10 часов аудиторных занятий и 12 часов самостоятельной работы студентов.

Данное методическое пособие включено в план издания учебно-методической литературы кафедры Информационной безопасности Тюменского государственного университета на 2009 г.

Глава 1. Структура и содержание учебно-методического пособия

Первоначально планировалось включить в пособие 2 раздела – «Вероятностные тесты на простоту» и «Доказуемо просты числа». Это обусловлено тем, что разные криптосистемы используют разные типы простых чисел. Существует 2 основных подхода к генерации простых чисел: методы, генерирующие число, являющееся простым с высокой степенью вероятности (т.н. probability methods) и методы, генерирующие числа, являющиеся доказуемо простыми (т.н. provability methods).

В каждом разделе были приведены несколько тестов на простоту.

После апробации пособия студентами 4 курса специальности «Компьютерная безопасность» групп 347 и 347 Института математики и компьютерных наук Тюменского государственного университета выяснилось, что многие студенты затрудняются самостоятельно описать класс больших чисел, поэтому было решено ввести в курс «криптографические методы защиты информации» дополнительную тему «Операции с большими числами» и провести по ней лабораторное занятие, а также включить данную тему в методическое пособие.

В каждом разделе выделены теоретическая часть, задания для самостоятельной работы, также было решено включить во второй и третий раздел тестовые данные для программ, разработанных студентами, чтобы каждый студент имел возможность самостоятельно проверить корректность работы своей программы. Упрощенно, тестовые данные представляют собой данные на вход программы и данные, которые должны быть получены на выходе. Также к каждой паре «вход-выход» приложено предположительное определение ошибки алгоритма в случае несовпадения полученного результата с ожидаемым. Более подробно эти тестовые данные описаны в разделе 1.6.

1.1.     Теоретическое наполнение раздела «Операции с большими числами»

Большинство современных алгоритмов такие как ГОСТ Р34.11-94, ГОСТ Р 34.11-2001, DSA и EСDSA накладывают условия на длину простого числа, например в ГОСТ Р 34.11-2001 длина простого числа должна быть больше 255 бит, а по стандарту DSA 512≤|p|≤1024. Для реализации данных алгоритмов необходимо умение работать с «большими» числами, а именно знать, как они представляются в памяти компьютера, и выполнять над ними арифметические операции.

Все алгоритмы, описанные в первой части пособия, приведены для случая, когда на основе класса 64-битных целых чисел описывается класс 128-битных целых. Пользуясь принципами, описанными для этого случая, студенту предоставляется самостоятельно построить класс 256- или 512-, 1024-битных целых чисел.

В данной главе описаны алгоритмы, используя которые можно получить практически любую арифметическую операцию, а именно: сложение, умножения двух чисел (методом Карацубы), возведение в квадрат, вычисление остатка от деления, возведение в степень (дихотомический алгоритм). Все операции над большими числами описаны через следующие стандартные операции над 64-битными целыми числами: сложение, вычитание, вычисление остатка от деления, возведение в квадрат, возведение в n-ю степень.

Операция сложения – это первая операция, описываемая в пособии, поэтому она рассмотрена наиболее подробно. Предлагается метод с использованием стандартной операции сложения 64-битных чисел. Результат сложения двух n-битных чисел предлагается помещать в 2n-битное число с тем, чтобы при выполнении криптографических преобразований промежуточный результат не выходил за размеры класса.

Вычисление остатка от деления. В пособии предлагается метод Барретта. В данном методе используются стандартные 64-битные операции сложение, умножение, вычитание, возведение в n-ю степень, вычисление остатка от деления.

Умножение 2х чисел. В пособии предлагается метод Карацубы. В данном методе используются стандартные 64-битные операции сложение, умножение, вычитание, возведение в n-ю степень, вычисление остатка от деления. Данный метод дает преимущество в скорости вычисления, так как позволяет сократить количество операций умножения с 4 до 3 по сравнению с традиционным подходом. Наряду с методом Карацубы, описывается метод умножения «столбиком» (традиционный подход) и производится сравнение этих двух методов.

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

Возведение в степень. В пособии предлагается дихотомический алгоритм. Рассматриваются два варианта этого метода – «слева направо» и «справа налево». В данном алгоритме используются операции умножения и возведения в квадрат для 256-, 512- или 1024-битных целых чисел.

Изложение каждого из методов сопровождается примерами.

1.2. Теоретическое наполнение раздела «Вероятностные тесты на простоту»

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

В данной главе выделены следующие разделы: асимптотический закон распределения простых чисел, тест Ферма на простоту, тест Соловея-Штрассена, тест Миллера-Рабина.

Асимптотический закон распределения простых чисел. Данный раздел был включен во 2-ю главу для того, чтобы дать студенту представление об эффективности случайного поиска простых чисел, поскольку именно случайный поиск простых чисел используется в алгоритмах построения с использованием вероятностных тестов на простоту.

Вводится теоретико-числовая функция π(x) – количество простых чисел, меньших x. В пособии приводится собственно теорема (асимптотический закон), которая определяет предельные характеристики распределения простых чисел среди целых положительных чисел, а также теорема Чебышева, определяющая границы интервала, на котором расположено π(x) для различных x.

Для иллюстрации использования приведенных теорем рассмотрен пример. В примере для множества целых положительных 32-битных чисел (таких, что старший бит равен 1) с использованием асимптотического закона вычислена вероятность того, что наугад выбранное из этого множества число окажется простым. Такая вероятность приняла следующее значение:

p»

Если сузить поиск до нечетных чисел, то вероятность возрастет в 2 раза и составит p».

После чего в методическом пособии сделан обоснованный вывод о том, что случайный поиск простых чисел целесообразен.

Тест Ферма. В данном разделе рассмотрен алгоритм теста Ферма на простоту. Данный тест позволяет эффективно определять, является ли данное число простым, однако, с его помощью нельзя строго доказать составность числа.

В основе теста Ферма лежит теорема Ферма. Ее формулировка приведена в тексте пособия (без доказательства)

Теорема Ферма (малая)

Если р – простое, и p не делит a  a^p–1 ≡ 1 (mod p)

Таким образом, если n-простое число, то для любого основания a будет выполняться сравнение a^n–1 ≡ 1 (mod n). Если n – составное число, то такое сравнение будет выполняться лишь для некоторых a в силу случайного совпадения. На этом факте основан тест Ферма, который проверяет данное сравнение для случайным образом выбранных оснований a.

Также в пособии отмечено тот факт что, для данного теста существуют такие составные числа, для которых сравнение a^n–1 ≡ 1 (mod n) выполняются при любом основании a. Поэтому, каково бы ни было значение параметра надежности (то есть количество перебранных оснований a), тест Ферма будет принимать такое составное число за простое. Такие числа называются числами Кармайкла.

Следует отметить, что вид чисел Кармайкла определяется теоремой Кармайкла.

Теорема Кармайкла:

n – число Кармайкла 1) n свободно от квадратов (т.е. n = p₁∙p₂∙…∙p_k);

2) (p_i – 1)\(n – 1), i = 1,…,k ;

3) k .

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

Для данного теста приводится оценка вероятности ошибки, равная ε^t, где ε , где - функция Эйлера, n - испытуемое число , t - параметр надежности.

 - функция Эйлера, где n — натуральное число, равна количеству натуральных чисел, не больших n и взаимно простых с ним.

Если тест показал, что испытуемое число является простым, то подразумевается, что данное число является простым с вероятностью 1- ε^t.

В случае составного испытуемого числа, имеющего только большие делители, ε, то есть существуют числа, для которых вероятность ошибки при проверке их на простоту тестом Ферма близка к 1.

В качестве примера иллюстрирующего работу теста были приведены расчеты, в качестве испытуемого числа было выбрано простое число 43, параметр надежности был выбран равный 2, основания, по которым проводилась проверка, были равны 35 и 13. При этом сравнение * выполнилось по основанию 35 и по основанию 13. Тест, таким образом, выдал ответ «43 – простое число».

Тест Соловея-Штрассена. В данном разделе рассмотрен алгоритм теста на простоту Соловея-Штрассена. Так же как и тест Ферма, данный тест позволяет эффективно определять, является ли данное число простым, однако, с его помощью нельзя строго доказать составность числа.

Этот тест основан на различии между символами Якоби и Лежандра.

Символом Лежандра называется символ  , где p – простое число, Q(p) – множество квадратичных вычетов по модулю p,  – множество квадратичных не вычетов по модулю p , а называется числителем, р – знаменателем символа Лежандра.

Символ Якоби определяется равенством:, где n – составное число, каноническое разложение которого есть . Знаменатель символа Лежандра – простое число, а символа Якоби – составное.

Свойства символа Лежандра и символа Якоби совпадают, за исключением критерия Эйлера. Критерий Эйлера выполняется для символа Лежандра, и не выполняется для символа Якоби.

Критерий Эйлера: Для символа Лежандра

Алгоритм вычисления этих двух символов одинаков, так как он основан на использовании свойств символов Якоби и Лежандра.

В алгоритме теста встречается вычисление символа Якоби (). В пособии приведен алгоритм вычисления данного символа, без свойств, на которых основано вычисление данного символа. Студенту разъясняется роль данного символа в алгоритме.

Для данного теста приводится оценка вероятности ошибки, равная ε^t, где t – число итераций теста, параметр надежности, а  < .

Из данной оценки надежности теста сделан вывод о том, что оценка надежности для теста Соловея–Штрассена гораздо лучше, чем для теста Ферма, даже в том случае, когда φ(n) ненамного меньше n. Если на одной итерации вероятность ошибочного решения теста не превышает ½, то уже на двух итерациях – ¼, на трех – 1/8, и т. д. Уже на 14 итерациях вероятность ошибочного решения на превышает 0, 0001.

Также студенту представлен пример, иллюстрирующий вычисление символа Якоби . В заключении данного раздела студенту представлен пример работы алгоритма со следующими параметрами: испытуемое (простое) число равно 43, параметр надежности равен 2.

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

Данный тест основан на теореме ферма, которая гласит если n – простое число, то для любого a: 0<a<n выполняется a^n—1≡1(mod n).

В пособии приведена оценка вероятности ошибки ε ≤ , то есть верхняя граница ошибки на одной итерации для теста Миллера-Рабина в 2 раза меньше аналогичной для теста Соловея-Штрассена и в 4 раза – для теста Ферма. Если на одной итерации вероятность ошибочного решения в тесте не превышает ¼, то на двух итерациях – 1/16, на трех – 1/64. Для того, чтобы вероятность ошибки не превышала 0, 0001, требуется всего 7 итераций, что в 2 раза меньше, чем для теста Соловея-Штрассена. На практике рекомендуется использовать не менее пяти итераций теста, что обеспечивает вероятность вынесения ошибочного решении не более 0,001.

Студенту разъяснятся метод построения последовательности b₀, b₁,…,b_s , а именно то, что каждый последующий член данной последовательности является квадратом предыдущего по модулю n, а последний член есть ни что иное как a^n—1 mod n. То есть на одном из шагов теста строиться последовательность квадратов по модулю n.

В качестве примера, иллюстрирующего работу теста, были приведены расчеты. В качестве испытуемого числа было выбрано составное число 65, параметр надежности был выбран равный 5.

1.3. Теоретическое наполнение раздела «Доказуемо простые числа»

В данном разделе рассмотрены алгоритмы которые позволяют строить числа, простота которых не вызывает сомнений, а именно тест Миллера на простоту, тест основанный на теореме Поклингтона, Процедура генерации простых чисел заданной длины ГОСТ Р 34.10-94. Последний алгоритм используется в отечественном стандарте шифрования ГОСТ Р 34.10-94.

Данная тема редко и недостаточно полно затрагивается в учебно-методической литературе, несмотря на достаточно большую ее практическую значимость.

Подход к получению доказуемо простых чисел отличается от подхода, рассмотренного ранее. Для построения таких чисел не используется случайный поиск. С использованием таблицы простых чисел небольшого размера, построенной заранее, строится число m (равное произведению нескольких простых чисел либо произведению простых чисел и случайного числа), затем число n=2m+1 проверяется на простоту одним из нижеприведенных тестов.

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

Теорема Сэлфриджа.

Пусть n—1=. n – простое,   a: 1) a^n—1≡1(mod n);

2) 1(mod n).

Данная теорема приведена в пособии без доказательства.

Теорема Сэлфриджа дает удобный критерий для доказательства простоты числа. На основании этой теоремы построен алгоритм Миллера проверки чисел на простоту, который требуют полной факторизации числа n—1.

Алгоритм построения простого числа с помощью теста Миллера следующий:

1. Строится таблица малых простых чисел q_i (или используется готовая таблица);

2. Строится число m=(где q_i—случайные простые числа из таблицы, α_i – случайные целые числа), размер которого на 1 бит меньше требуемого размера для простого числа;