Методические указания и варианты заданий к выполнению лабораторных работ по дисциплине «Информационная безопасность в сетях» (стр. 4 из 7)
Function NOD(A as integer, B as integer) as integer
if (A mod B)=0 then
NOD=B
Else
NOD=NOD(B, A mod B)
End if
End
КОНТРОЛЬНЫЕ ВОПРОСЫ
1. Что вычисляет алгоритм Евклида?
2. Сколько строчек вычислений необходимо произвести в алгоритме Евклида?
3. Как производится заполнение столбцов x и y в расширенном алгоритме Евклида?
4. Какая алгоритмически сложная задача лежит в основе метода RSA?
5. Что такое простое число? Какие методы проверки простоты числа вы знаете?
6. Как генерируется параметры метода RSA?
7. Какие параметры в RSA вычисляются с помощью алгоритма Евклида?
8. Как производится процедура шифрования/расшифровки в методе RSA?
9. Какой длины должны быть простые числа p и q в методе RSA, чтобы обеспечить необходимый уровень надежности?
10. Каким образом, зная значение функции Эйлера и открытый ключ е, можно рассчитать закрытый параметр d?
11. Дайте определение односторонней функции.
12. Сколько итераций потребуется сделать в методе Полларда, если N ≈100 млн (108)?
Лабораторная работа №2
Шифрование текстовых файлов на основе линейных
сдвиговых регистров с обратной связью.
Цель работы: Изучить принципы работы линейного сдвигового регистра с обратной связью (ЛРОС) и организацию шифрования на их основе
Задание на лабораторную работу:
1. Изучить теоретический материал по принципам построения и работы ОРОС,
2. Разработать программу на языке VBA в Excel, моделирующую работу ЛРОС,
3. Выполнить шифрование/ расшифровку произвольного файла с использованием этой программы. Для шифрования выбрать неприводимый многочлен степени не ниже 16. Шифрование выполнять побитно над словами длины 2 байта.
4. Ответить на контрольные вопросы в конце задания.
Теоретический материал.
Последовательности, генерируемые с помощью сдвиговых регистров, широко используются как в теории кодирования, так и в криптографии. Теория таких регистров разработана достаточно давно еще в доэлектронное время, в период военной криптографии.
Сдвиговый регистр с обратной связью состоит из двух частей: сдвигового регистра и функции обратной связи. Сдвиговый регистр представляет собой последовательность битов фиксированной длины. Число битов называется длиной сдвигового регистра. Функция обратной связи является булевой функцией из множества L-мерных векторов с координатами из множества {0, 1} в множество {0, 1}, L – длина сдвигового регистра. В начальный момент работы сдвиговый регистр заполняется некоторым начальным значением. На каждом последующем шаге вычисляется значение
, где xi – значение ячейки с номером si, содержимое регистра сдвигается вправо, а в освободившееся место помещается значение y. 
Выходом регистра обычно бывает младший разряд s0. Иногда в качестве выхода берут все слово, помещающееся в регистре. Последовательность таких слов является периодичной. Периодом сдвигового регистра называется длины последовательности регистровых слов до начала ее повторения. Очевидно, что количество различных слов для регистра длины L равно
, поэтому период любой последовательности регистровых слов не может превышать .Простейшим видом сдвигового регистра с обратной связью является линейный сдвиговый регистр с обратной связью (linear feedback shift register LFSR). Функция
обратной связи является в этом случае просто суммой по модулю 2 нескольких фиксированных разрядов 
.Пример. Рассмотрим линейный сдвиговый регистр R длины L=4 и функцией обратной связи
(отвод от первого и четвертого вывода). 
Пусть исходное значение регистра равно <1,1,1,1>, тогда этот регистр будет порождать следующую последовательность
В этом примере период последовательности значений регистра равен
. Это максимально возможное значение, т.к. слово, состоящее из одних нулей не может быть никогда достигнуто из ненулевой конфигурации (докажите это!).Последовательность максимальной длины
называется M-последовательностью. Не всякий регистр LFSR может обладать такой последовательностью. Проблема определения по заданному регистру LFSR, будет ли он обладать M-последовательностью, является нетривиальной. Для ее решения сопоставим произвольному регистру LFSR длины L следующий многочлен 
(*), где коэффициент 
принимает значение 1 или 0 в зависимости от того, присутствует ли соответствующее слагаемое 
в функции обратной связи. Например, регистру LFSR в рассмотренном выше примере соответствует многочлен 
.Теорема. Произвольный LFSR регистр обладает M-последовательностью тогда и только тогда, когда соответствующий многочлен
является неприводимым (неразложимым) над полем F2={0, 1}.Пример приводимого многочлена можно взять из всем известной формулы сокращенного умножения
. Поскольку, все значения берутся по модулю 2, то в вычисляя значения многочленов надо помнить, что 
а 
.В общем случае, нет простого способа генерировать многочлены заданной степени по модулю 2, однако можно легко проверить, является ли заданный многочлен приводимым или нет над заданным конечным полем. Для этого используется алгоритм Берлекампа (Berlekamp) (см. Лидл, Нидеррайтер[7], т.1, гл.3.). В следующем разделе мы рассмотрим упрощенную ыерсию алгоритма Берленкамфа.
Неприводимые многочлены в конечном поле K.
В этом разделе мы научимся определять для заданного многочлена
с коэффициентами из конечного поля P={0, 1, 2, ... q - 1}, является ли этот многочлен неприводимым в поле P. Неприводимые многочлены используются для построения линейных сдвиговых регистров с обратной связью (см. раздел 3.1.6). Наш алгоритм основывается на следующей теореме.Теорема. Пусть F – конечное поле, состоящее из q элементов. Тогда для любого натурального
многочлен 
является произведением всех неприводимых над полем F многочленов степени k.Из этой теоремы сразу следует, что для произвольного многочлена
является произведением всех линейных сомножителей 
, 
является произведением всех квадратичных сомножителей и т.д. Поэтому, если 
=1 для 
, то является неприводимым многочленом. Наибольший общий делитель двух многочленов находят с помощью алгоритма Евклида, используя соотношение 
, где 
- остаток от деления 
на 
.