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

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

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

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

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

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

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

После апробации пособия студентами 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 не делит aa^{p –1} ≡ 1 (modp)