 |
Разработка заданий для лабораторных и самостоятельных работ
|
|
|
|
Для закрепления материала лекционных занятий нами были разработаны задания для лабораторных и самостоятельных работ. Всего разработано три комплекта заданий, соответствующие трем темам: «Операции с большими числами», «Вероятностные тесты на простоту» и «Доказуемо простые числа». Предполагается последовательное выполнение этих заданий, в порядке, изложенном в методическом пособии. На изучения каждой из тем, соответствующих разделам пособия, отводится по 2 часа лабораторных занятий и по 2 часа самостоятельной работы. Программная реализация алгоритмов осуществляется студентами в компьютерном классе под руководством преподавателя, отладка программы и оформление результата – в часы, отведенные для самостоятельной работы.
Программные модули разработанные в рамках перечисленных тем, описанные в них классы и функции, используются студентами в дальнейшем курсе предмета «Криптографические методы защиты информации» для выполнения лабораторных работ по реализации и использованию асимметричных алгоритмов шифрования, алгоритмов цифровой подписи, криптографических протоколов, а также для выполнения курсовой работы по предмету.
Задание к первому разделу – «Операции с большими числами» не разделено на варианты, так как результат данной лабораторной работы подразумевает разработку класса для работы с большими числами, который используется при выполнении лабораторных работ ко второй и третьей главам. Выполнение задания к первому разделу, таким образом, является базовым элементом программ, которые разрабатываются студентами в дальнейшем, на протяжении всего курса предмета «КМЗИ».
Задания к разделу «Операции с большими числами» включают в себя создание класса больших чисел, в котором заданы следующие операции: сложение, вычисление остатка от деления, умножения двух чисел (методом Карацубы), возведение в квадрат, возведение в степень (дихотомический алгоритм). Используя данные операции можно получить практически любую арифметическую операцию.
|
|
|
Операция возведения в степень используется при шифровании данных в криптосистемах, основанных на проблеме дискретного логарифмирования, также данная операция используется практически во всех тестах на простоту.
Операции умножения и возведения в квадрат используются при реализации операции возведение в степень и.т.д. Исходя из вышеупомянутых критериев, мы сформулировали задания в порядке возрастания сложности, а именно первой операцией, которую предстоит реализовать студенту, является операция сложения, как уже было описано выше, она является базовой операцией, использующейся при реализации других операций. Далее студенту предстоит реализовать операцию умножения. При реализации данной операции используется операция сложения. Следующим заданием является реализация операции возведения в квадрат, в которой используются реализованные ранние операции сложения и умножения. Наконец, студенту предстоит реализовать операцию возведения в степень, для которой используются все ранее реализованные операции.
Существует большое количество различных вероятностных тестов на простоту. Из большинства тестов было выбрано три «основных», которые и стали предметом изучения в рамках лабораторной работы к главе «Вероятностные тесты на простоту». Данные тесты были выбраны нами исходя из следующего: другие тесты либо гораздо сложнее, либо не имеют принципиальных отличий от выбранных нами тестов. Мы разработали три варианта лабораторной работы, в каждом из вариантов студенту предлагается реализовать один из тестов, в зависимости от варианта, и закрепить свои знания, выполняя задания на использование Асимптотического закона распределения простых чисел. Результат лабораторной работы предлагается оформить в виде таблицы, что позволило бы преподавателю сократить время, затрачиваемое на проверку данной лабораторной работы (это связано с тем, что в данной лабораторной работе используются алгоритмы, компьютерный расчет которых на больших числах занимает достаточно много времени (на персональном компьютере)).
|
|
|
| № | 1 | 2 | … | 10 |
| p | ||||
| n |
Здесь №-номер эксперимента, p- найденное простое число, n- количество перебранных чисел до получения простого.
Также следует отметить, что при заполнении таблицы число n имеет следующий смысл: количество перебранных чисел до получения простого, и если взять среднее значение n по десяти экспериментам, то результат должен получиться достаточно близким к рассчитанному числу ожидаемого количества перебранных чисел до получения простого числа. Если расхождение слишком велико, то можно сделать вывод, что данный вероятностный тест реализован не верно. Результат работы реализованного алгоритма студент может проверить с помощью теста для самопроверки (тесты для самопроверки будут детально рассмотрены в главе 1.5).
В задании к главе «Доказуемо простые числа» студенту предлагается реализовать три теста основанных на трех различных принципах (Данные тесты описаны в разделе 1.3). Исходя из этого, мы выделили три варианта лабораторной работы. В первом и втором варианте лабораторной работы предлагается использовать тесты Миллера и Поклингтона для построения простых чисел, а для третьего варианта предлагается генерировать простые числа при помощи процедуры ГОСТ 34.10-94. Результат лабораторной работы студенту предлагается оформить в виде таблицы, что позволяет преподавателю затрачивать минимум времени на проверку данной работы, а также, при отсутствии времени на проверку работы на занятии, проверить работы во внеурочное время.
| № | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| p | ||||||||||
| Результат проверки вероятностным тестом | ||||||||||
| k |
|
|
|
В данной таблицу в первой строке указывается номер эксперимента. Во второй строке – простое число, получившиеся в ходе эксперимента. В третьей строке – результат проверки этого числа p,реализованного студентом к заданию в главе «Вероятностные тесты на простоту». В четверную строку необходимо внести количество чисел, которые были проверенны детерминистическим тестом и определены как составные, но вероятностным тест определил их, как простые.
Такой способ проверки также позволяет при необходимости студентам выполнять, а преподавателю проверять задания, приведенные в пособии, дистанционно или полностью во время, отведенное для самостоятельной работы (например, в случае болезни студента или при изучении данных тем в рамках других специальностей, где изучение криптографии предусмотрено в качестве спецкурса или темы для самостоятельного изучения). Следует отметить, что компьютерный расчет работы тестов, представленных в данном разделе, на больших числах занимает достаточно много времени (на персональном компьютере)). Студенту предлагается сгенерировать десять простых чисел, алгоритм зависит от выбранного варианта, и затем проверить данные числа одним из вероятностных тестов (реализованным в задании к главе «Вероятностные тесты на простоту»). Каждое число, отвергнутое при проверке детерминистическим тестом, также проверять вероятностными тестами. Данное задание показывает студенту, что некоторое количество простых чисел распознаются детерминистическими тестами как составные.
Итак, в результате выполнения комплекса заданий, предложенных в методическом пособии, студент должен получить следующие знания, умения и навыки:
· навыки реализации и использования класса больших чисел;
· навыки реализации и практического использования вероятностных тесов на простоту;
· знание о практическом применении асимптотического закона распределения;
· умение рассчитывать необходимое количество итераций теста для достижения заданной вероятности ошибки (если студенту представиться возможность, применимо к конкретной задачи, столкнуться с реализацией тестов на простоту, то он самостоятельно сможет рассчитать необходимое количество итераций);
|
|
|
· представление о различии вероятностных и детерминистических тестов на простоту (студент будет иметь четкое представление о том, что при реализации детерминистических тестов он строит число, простота которого не вызывает сомнений);
· знание о надежности тестов, об их быстродействии;
· знаниями о том, что не все числа определенные детерминистическими тестам, как составные на самом деле таковыми являются.
Тесты для самопроверки
Для того чтобы студент мог самостоятельно проверить корректность выполненных им работ, нами были разработаны тесты для самопроверки. Тесты представляют собой наборы входных и выходных данных, то есть студент подставляет в реализованный им тест набор входных данных и делает вывод о корректности теста на основе сравнения полученных им выходных данных и данных «эталона». В пособии тесты выделены в отдельную главу, которая располагается после заданий к главам.
Тесты для самопроверки для раздела «Операции с большими числами» представляет собой две таблицы (в первой таблице длина чисел не превышает 64 бит, во второй длина чисел не превышает 128бит), в столбцы которой занесены числа a и b, название операции и результат.
В таблице нами были разработаны наборы входных и выходных данных для следующих арифметических операций: сложение, вычисление остатка от деления, умножение двух чисел, возведение в квадрат, возведение в степень. Студенту следует проверять реализованные им арифметические операции в следующем порядке:
1. сложение, так как это базовая операция, использующаяся при реализации всех остальных;
2. умножение, так как при реализации данной операции используется только сложение, то для студента не составит труда найти ошибку в алгоритме, зная, что операция сложения работает верно;
3. вычисление остатка от деления, так как при реализации данной операции используется битовый сдвиг, сложение и вычитание;
4. возведение в квадрат, так как при реализации данной операции используются операции сложения и умножения;
5. возведение в степень следует проверять последним, так как при реализации данной операции используются почти все предыдущие проверяемые операции.
Пример тестовых данных приведен в следующей таблице.
| a | b | a+b | a*b | a mod b | a2 | ab |
| 0 51 | 0 7 | 0 58 | 0 357 | 0 2 | 0 2601 | 0 897410677851 |
| 0 78 | 0 5 | 0 83 | 0 390 | 0 3 | 0 6084 | 0 2887174368 |
| 0 36 | 0 4 | 0 40 | 0 144 | 0 0 | 0 1296 | 0 1679616 |
| 0 21 | 0 10 | 0 31 | 0 210 | 0 1 | 0 441 | 0 16679880978201 |
| 0 5 | 0 12 | 0 18 | 0 60 | 0 5 | 0 25 | 0 244140625 |
|
|
|
Числа a и b подаются в программу, реализованную студентом, на вход, а данные в колонках «a+b», «a*b», «a mod b», «a2», «ab» это результаты которые должна вернуть программа при данных операциях (т.е. на основе этих данных студент делает вывод о корректности, реализованной им операции). Следует отметить, что в таблице числа записаны «0 210» это следует понимать как старшую и младшую часть числа.
Также следует реализованные операции проверять сначала на данных из таблицы с малыми значениями (64 бита), при успешном результате следует проверить на данных из второй таблицы(128 бит).
Тесты для самопроверки для раздела «Вероятностные тесты на простоту» представляют собой таблицы, в которых указаны входные данные и реакция теста на эти входные данные (то есть число определяется как простое или как составное). Перед тем как использовать таблицы по назначению, следует установить количество итераций теста равным одному. Также следует отметить, что проверяемое число следует проверять тестом не менее десяти раз и результат проверки сверять с данными из таблицы. Это обусловлено тем, что данные тесты всегда простое число принимает за простое, но каждый тест может принять составное число за простое (при использовании некоторых случайных оснований чисел). Поэтому если мы будем проверять составные числа тестом, то иногда результат будет «простое» но чаще «составное». Стоит отметить, что для теста Ферма существует класс чисел Кармайкла, которые являются составными, но всегда принимаются за «простые». Такие числа также внесены в таблицу для самопроверки.
| Числа для проверки | Результат теста | |
| Простые числа | 0 8363 0 1657 0 9781 | Всегда «простое» |
| Числа Кармайкла | 0 1105 0 2465 | Для теста Ферма -Всегда «простое», для тестов Миллера-Рабина и Соловея-Штрассена- чаще «составное»,чем «простое» |
| Составные, нечетные, не Кармайкла | 0 625 0 791 0 3871 | Чаще «составное»,чем «простое» |
Всего в пособии насчитывается 30 наборов.
Тесты для самопроверки для раздела «Доказуемо простые числа» представляют собой таблицы, в которых указаны входные данные и реакция теста на эти входные данные. Для тестов Миллера и Поклингтона проверка проводиться в два этапа первый этап заключается в проверке данных тестов таблицей составных чисел, второй проверкой таблицей ориентированной на каждый из тестов. (Стоит отметить, что перед проверкой следует установить значение параметра надежности равным единицы).
Таблица составных чисел:
| Числа для проверки (p) | Разложение p-1 | Разложение F | R | Результат теста |
| 0 335 0 437 0 657 0 779 | 2*167 22*109 24*41 2*389 | 167 109 41 389 | 2 4 16 2 | Всегда отвергаются |
Тест Миллера:
| Простое число p | Разложение (p-1) | Вероятность ошибки (вероятность того, что число будет принято за составное) |
| 13 | 22*3 | 0,66666 |
| 29 | 2*2*7 | 0,57142 |
| 61 | 2*2*3*5 | 0,73333 |
| 97 | 25*3 | 0,66666 |
Тест Поклингтона:
| Простое число p | Разложение F | R | Вероятность ошибки (вероятность того, что число будет принято за составное) |
| 13 | 2*2 | 3 | 0,5 |
| 29 | 7 | 4 | 0,14285 |
| 61 | 3*5 | 4 | 0,46666 |
| 97 | 3*22 | 8 | 0,66666 |
| 157 | 13 | 8 | 0,125 |
Всего в пособии более 30 тестовых примеров на каждый из тестов.
Для процедуры генерации чисел заданной длинны ГОСТ 31.10-94 предусмотрена отдельная таблица, в которой входными данными являются числа q и t а результатом является построенное число p (Стоит отметить, что перед проверкой следует установить значение параметра ξ равным 0).
Процедура генерации чисел заданной длинны ГОСТ 31.10-94:
| q | t | Построенное число p |
| 3 | 4 | 13 |
| 5 | 6 | 41 |
| 7 | 5 | 29 |
| 5 | 5 | 31 |
| 11 | 7 | 67 |
| 11 | 8 | 199 |
| 13 | 7 | 79 |
Всего в пособии насчитывается 20 наборов.
|
|
|
