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

Структура высшего очного образования предполагает сочетание различных видов и методов обучения: аудиторные занятия, домашняя и самостоятельная работа студентов, выполнение курсовых работ по специальности, по предметам. Для изучения каждого предмета ГОС ВПО (Государственный образовательный стандарт высшего профессионального образования) по специальности определяет необходимое количество аудиторных занятий каждого вида, а также количество часов, выделенных на самостоятельную работу студентов. В учебном плане специальности «Компьютерная безопасность» Тюменского государственного университета на изучение дисциплины «Криптографические методы защиты информации» отводится 70 часов лекций и 35 часов лабораторных занятий. Объем самостоятельной работы студента по дисциплине криптографические методы защиты информации составляет 82 часа. Методические пособия, указания к выполнению лабораторных и самостоятельных работ, разработанные как дополнение к лекционному материалу, призваны осветить вопросы, встающие перед студентами в процессе выполнения ими самостоятельной работы.Первоначально планировалось включить в пособие 2 раздела - «Вероятностные тесты на простоту» и «Доказуемо просты числа». В данной главе описаны алгоритмы, используя которые можно получить практически любую арифметическую операцию, а именно: сложение, умножения двух чисел (методом Карацубы), возведение в квадрат, вычисление остатка от деления, возведение в степень (дихотомический алгоритм). В данной главе выделены следующие разделы: асимптотический закон распределения простых чисел, тест Ферма на простоту, тест Соловея-Штрассена, тест Миллера-Рабина. Данный тест позволяет эффективно определять, является ли данное число простым, однако, с его помощью нельзя строго доказать составность числа. Так же как и тест Ферма, данный тест позволяет эффективно определять, является ли данное число простым, однако, с его помощью нельзя строго доказать составность числа.Всего разработано три комплекта заданий, соответствующие трем темам: «Операции с большими числами», «Вероятностные тесты на простоту» и «Доказуемо простые числа». Задание к первому разделу - «Операции с большими числами» не разделено на варианты, так как результат данной лабораторной работы подразумевает разработку класса для работы с большими числами, который используется при выполнении лабораторных работ ко второй и третьей главам. Задания к разделу «Операции с большими числами» включают в себя создание класса больших чисел, в котором заданы следующие операции: сложение, вычисление остатка от деления, умножения двух чисел (методом Карацубы), возведение в квадрат, возведение в степень (дихотомический алгоритм). Операция возведения в степень используется при шифровании данных в криптосистемах, основанных на проблеме дискретного логарифмирования, также данная операция используется практически во всех тестах на простоту. Исходя из вышеупомянутых критериев, мы сформулировали задания в порядке возрастания сложности, а именно первой операцией, которую предстоит реализовать студенту, является операция сложения, как уже было описано выше, она является базовой операцией, использующейся при реализации других операций.Тесты представляют собой наборы входных и выходных данных, то есть студент подставляет в реализованный им тест набор входных данных и делает вывод о корректности теста на основе сравнения полученных им выходных данных и данных «эталона». Тесты для самопроверки для раздела «Операции с большими числами» представляет собой две таблицы (в первой таблице длина чисел не превышает 64 бит, во второй длина чисел не превышает 128бит), в столбцы которой занесены числа a и b, название операции и результат. В таблице нами были разработаны наборы входных и выходных данных для следующих арифметических операций: сложение, вычисление остатка от деления, умножение двух чисел, возведение в квадрат, возведение в степень. Числа a и b подаются в программу, реализованную студентом, на вход, а данные в колонках «a b», «a*b», «a mod b», «a2», «ab» это результаты которые должна вернуть программа при данных операциях (т.е. на основе этих данных студент делает вывод о корректности, реализованной им операции). Тесты для самопроверки для раздела «Вероятностные тесты на простоту» представляют собой таблицы, в которых указаны входные данные и реакция теста на эти входные данные (то есть число определяется как простое или как составное).В 2007-2008 учебном году данное методическое пособие впервые было предложено студентам 4 курса специальности «Компьютерная безопасность» групп 347 и 347 Института математики и компьютерных наук Тюменского государственного университета для выполнения лабораторных работ по дисциплине «Криптографические методы защиты информации». Данный эксперимент проходил по следующей схеме: студенту предлагалось выполнить лабораторные работы из методического пособия, после того как он прослушал материал на лекционных занятиях. Во время проведения данного эксперимента, проанализировав первые, полученные нами программн

Содержание

Введение.

Глава 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 г.