Файл: Ббк 32. 81я7 И74 Составители ст преп. С. И. Жданова ст преп. С. Н. Рога и 74 информационная безопасность методические указания к выполнению лабораторных работ и ргз для студентов очной формы обучения направлений бакалавриата.pdf

41 4.2.1 Положить y=y
2
(mod n)
4.2.2 При y=1 результат: " число n составное "
4.2.3 Увеличить j на 1 4.3 При
1


n
y
результат: " число n составное ".
5.
Результат: " число n вероятно простое ".
В результате выполнения теста для простого числа n единственными решениями сравнения
)
(mod
1 2
n
y

являются
)
(mod
1
n
y


Вероятность ошибки теста Рабина - Миллера составляет не более
1/4. Для уменьшения вероятности ошибки тест необходимо повторить не менее t раз. Вероятность ошибки в этом случае будет равняться
(1/4)
t
Детерминированные алгоритмы проверки на простоту
Детерминированный алгоритм, проверяющий простоту чисел, принимает целое число и выдает на выходе признак: это число —
простое число или составной объект.
Алгоритм теории делимости
Испытание на делимость - самое простое детерминированное испытание. В его основе лежит использование в качестве делителей всех чисел меньших, чем
n
. Если любое из этих чисел делит n, то
n - составное число.

42
Сложность побитового испытания делимостью
Пусть дано число n. Разрядность числа - 200 бит. Вычислим количество разрядных операций, необходимых для выполнения алгоритма -
2 2
b
n
=2 100
Если алгоритм имеет скорость 2 30 операций в секунду, то необходимо 2 70
секунд для проведения испытаний.
AKS-алгоритм
В 2002 году летом индийские математики Аграавал, Саксен и
Кайал нашли полиномиальный детерминированный алгоритм проверки числа на простоту. Основная идея, на которой основан это алгоритм такова: n- простое число тогда и только тогда, когда:
HOД (a,n)=1, (x-a)
n
≡(x-a)
n
(mod n)
Алгоритм AKS (псевдокод)
if (n is has the form a b
with b > 1) then output COMPOSITE r := 2 while (r < n) { if (gcd(n,r) is not 1) then output COMPOSITE if (r is prime greater than 2) then { let q be the largest factor of r-1 if (q > 4sqrt(r)log n) and (n
(r-1)/q is not 1 (mod r)) then break
} r := r+1
} for a = 1 to 2sqrt(r)log n {

43 if ( (x-a)
n is not (x n
-a) (mod x r
-1,n) ) then output COMPOSITE
} output PRIME;
Алгоритм AKS и его модификации на практике пока не могут конкурировать по удобству использования и времени выполнения с другими алгоритмами.
Реализацию алгоритма AKS можно посмотреть по приведенной ниже ссылке:
http://yves.gallot.pagesperso-orange.fr/src/
Алгоритм генерации простого числа
1.
Сгенерировать случайное n-битное число p.
2.
Установить его старший и младший биты равными 1. Старший бит будет гарантировать требуемую длину искомого числа, а младший бит – обеспечивать его нечётность.
3.
Убедиться, что p не делится на небольшие простые числа: 3, 5,
7, 11 и т.д. Наиболее эффективна проверка на делимость на все простые числа, меньшие 500.
4.
Выполнить тест Рабина-Миллера минимум 5 раз.
Если p не прошло хотя бы одну проверку в пунктах 3 или 4, то оно не является простым.
Проверка, что случайное нечётное p не делится на 3, 5 и 7, отсекает
54 % нечётных чисел. Проверка делимости на все простые числа, меньшие 256, отсекает 80 % составных нечётных чисел.
Даже если составное число «просочилось» через этот алгоритм, это будет сразу же замечено, т.к. шифрование и дешифрование не будут работать.

44
Содержание работы
Реализовать приложение, позволяющее выполнять следующие действия:
1.
Реализовать подпрограмму для проверки чисел на простоту, используя изученные вероятностные методы.
Программа должна отражать затраченное время на проверку чисел на простоты.
В тесте Ферма предусмотреть вывод сообщения о введении числа
Кармайкла, если такое число подается на проверку.
В тесте Рабина-Миллера пользователь должен иметь возможность самостоятельно задавать количество проверок.
2.
Реализовать подпрограмму для проверки чисел на простоту, используя предложенный детерминированный алгоритм( алгоритм теории делимости).
Программа должна отражать затраченное время на проверку чисел на простоты.
3.
С помощью алгоритма генерации простого числа получить большое простое число (в данной лабораторной работе под большими числами будем понимать числа, превышающие 2 64
).
Пользователь вводит количество проверок в тесте на простоту и длину числа в битах.
Контрольные вопросы
1.
Для чего нужно большое простое число?
2.
Как проверить, является число простым или нет?
3.
Как сгенерировать большое простое число?

45 4.
Приведите пример алгоритма эффективной реализации возведения целого числа в целую степень по модулю n.
5.
Что такое псевдопростые числа? Как они влияют на результат работы алгоритмов проверки на простоту.
6.
Что такое числа Кармайкла? Перечислите числа Кармайкла в диапазоне от 1 до 100000.

46
Лабораторная работа №5
АЛГОРИТМ ОБМЕНА КЛЮЧАМИ
ДИФФИ-ХЕЛЛМАНА
Цель работы: изучить и реализовать на практике алгоритм обмена ключами Диффи-Хеллмана.
Краткие теоретические сведения
Криптографический протокол – это набор формализованных правил, описывающий последовательность действий, исполняемые двумя и более лицами, для решения задачи защиты информации с использованием криптографии.
Одна из основных проблем криптографии – передача сообщения по незащищенному каналу связи. При симметричном шифровании ключи шифрования ценны также как и само передаваемое сообщение.
Отсюда следует проблема распределения ключей. Надежность любой симметричной криптографической системы во многом зависит от выбранной схемы распределения ключей.
Первообразные корни
Класс [a], где (a,n)=1 называется первообразным корнем по модулю
n, если показатель числа a по модулю n равен
φ(n) значению функции Эйлера.
Известно, что любой показатель k числа a по модулю n делит
φ(n). Из этого факта вытекает способ нахождения первообразных корней. Представим φ(n) в виде:
m
k
m
k
k
p
p
p
n



)
(
2 1
2 1

, где
p
i
- простые делители. Тогда, чтобы k было первообразным корнем числа n, нужно, чтобы:

47 1) число k было взаимно простым с числом n ;
2)
i
n
k
i
p
n


)
(mod
1
)
(

Построение первообразного корня по модулю n
В силу теоремы Эйлера для любых взаимно простых a и n выполняется соотношение:
),
(mod
1
)
(
n
a
n


где

)
(n

обозначает функцию Эйлера, значение которой равно количеству положительных целых значений, меньших n и взаимно простых с n .
Для простого числа n выполняется:
1
)
(


n
n

Если предположить, что два числа p и q – простые, тогда для n=
p
α
⋅q
β
функция Эйлера будет иметь вид:
)
1
(
)
1
(
)
(
)
(
)
(
)
(
1 1






















q
q
p
p
q
p
q
p
n
Говорят, что число a, взаимно простое с модулем n, принадлежит
показателю m , если m – такое наименьшее натуральное число, что выполняется сравнение:
)
(mod
1
n
a
m

Если a и n – взаимно простые, то существует, по крайней мере, одно число m =
)
(n

, удовлетворяющее условию
)
(mod
1
n
a
m

Если некоторая последовательность имеет длину ϕ(n), тогда целое число a генерирует своими степенями множество всех ненулевых вычетов по модулю n. Такое целое число называют Для числа n количество

первообразных корней по модулю n равно
))
1
(
(

n


Пример. Пусть n = 41 . Имеем c= φ (41)= 40=2 3
⋅5 . Итак, первообразный корень не должен удовлетворять двум сравнениям: a
8
≡1(mod 41), a
20
≡1(mod 41).

48
Испытываем числа 2, 3, 4, … : 2 8
≡ 10, 2 20
≡ 1 , 3 8
≡ 1, 3 20
≡ 40 , 4 8
≡
18, 4 20
≡ 1 ,5 8
≡ 18, 5 20
≡ 1 , 6 8
≡ 10, 6 20
≡40. Отсюда видно, что 6 – наименьший первообразный корень по модулю 41.
Распределение секретных ключей. Схема обмена
ключами Диффи-Хеллмана
Цель схемы Диффи-Хелмана – обеспечение двум пользователям защищенную возможность обмена секретным ключом. Алгоритм основан на трудности вычислений дискретных логарифмов.
Безопасность обмена ключами в алгоритме Диффи-Хеллмана вытекает из того факта, что, хотя относительно легко вычислить экспоненты по модулю простого числа, но очень трудно вычислить дискретные логарифмы. Для больших простых чисел задача считается неразрешимой.
Предположим, что двум абонентам необходимо провести конфиденциальную переписку, а в их распоряжении нет первоначально оговоренного секретного ключа. Однако между ними существует канал, защищённый от модификации, т.е. данные, передаваемые по нему, могут быть прослушаны, но не изменены
(такие условия имеют место довольно часто). В этом случае две стороны могут создать одинаковый секретный ключ, ни разу не передав его по сети, по следующему алгоритму (см. рисунок 5).
Обмен ключами по схеме Диффи-Хеллмана

49
Алгоритм заключается в следующем:
Задаются глобальные открытые элементы:

n– случайное большое простое число;

g– первообразный корень n.
Вычисляется ключ пользователем A:

выбирается большое секретное число X
A
(X
A

вычисление открытого значения Y
A
: Y
A
= g
X
A mod n;
Вычисляется ключ пользователем B:

Выбирается большое секретное число X
B
(X
B

Вычисление открытого значения Y
B
: Y
B
= g
X
B
mod n;
Вычисляется секретный ключ пользователем A: K=Y
B
X
A
mod n;
Вычисляется секретный ключ пользователем B: K=Y
A
X
B
mod n.
Данный алгоритм надежно работает только на каналах, защищенных от модификации.
С принципом работы алгоритма Диффи-Хелмана можно познакомиться в следующем видео: https://habrahabr.ru/post/151599/.
Содержание работы
Реализовать приложение, позволяющее выполнять следующие действия:
1.
Изучить схему обмена ключами Диффи-Хелмана.
2.
Реализовать подпрограмму, определяющую для заданного числа первые 100 первообразных корней, отображая при этом суммарное время, затраченное на их поиск. Число может задаваться десятеричной, шестнадцатеричной и двоичной формах.
3.
Вручную для первых 5 полученных числовых значений привести доказательство, что они действительно являются первообразными корнями заданного числа n.

50 4.
Реализовать подпрограмму, моделирующую обмен ключами между абонентами по схеме Диффи-Хеллмана. Программа должна получать большие простые числа X
A
, X
B
и n случайным образом с помощью алгоритма генерации простого числа, а также предоставлять пользователю возможность задавать их.
Контрольные вопросы
1.
Что такое первообразный корень по модулю n.
2.
Для числа n=54 найти первообразные корни.
3.
Опишите алгоритм эффективной реализации возведения целого числа в целую степень по модулю n.
4.
Опишите схему обмена ключами Диффи-Хелмана.
5.
В чем заключается криптографическая стойкость алгоритма обмена ключами Диффи-Хелмана.
6.
Доказать, что в схеме Диффи-Хелмана K
a
=K
b

51
Лабораторная работа №6
РЕАЛИЗАЦИЯ КОМБИНИРОВАННЫХ
АЛГОРИТМОВ ШИФРОВАНИЯ ДАННЫХ
Цель работы: изучить принцип работы ассиметричных алгоритмов. Разработать приложение, совмещающее в себе достоинства симметричных и ассиметричных алгоритмов шифрования.
Краткие теоретические сведения
При всех своих достоинствах симметричные алгоритмы обладают существенными недостатками. Во-первых, при симметричном шифровании необходимо, чтобы приемник и передатчик сообщения имели общий
ключ, который каким-то образом должен быть им заранее передан. Один из основоположников шифрования с открытым ключом У. Диффи, заметил, что данное требование отрицает всю суть криптографии, а именно возможность поддерживать всеобщую секретность при коммуникациях.
Во-вторых, все участники обмена данными должны быть убеждены, что электронное сообщение было послано конкретным участником. Это более сильное требование, чем
аутентификация.
Диффи и Хеллман достигли значительных результатов, предложив способ решения обеих задач, который радикально отличается от всех предыдущих подходов к шифрованию.
Ключ, используемый в симметричном шифровании, будем называть секретным ключом. Два ключа, используемые при шифровании с открытым ключом, будем называть открытым ключом и закрытым ключом. Закрытый ключ держится в секрете, создается

52 локально каждым пользователем, открытый ключ – общеизвестен.
Закрытый ключ обозначается KR, открытый ключ -KU.
Диффи и Хеллман описывают требования, которым должен удовлетворять алгоритм шифрования с открытым ключом.
1)
Создавать пару (открытый ключ KU, закрытый ключ KR).
2)
Имея открытый ключ и незашифрованное сообщение М, создать соответствующее зашифрованное сообщение:
3)
С = Е
KU
[М]
4)
Дешифровать сообщение, используя закрытый ключ:
5)
М = D
KR
[C] = D
KR
[E
KU
[M]]
6)
Невозможно, зная открытый ключ KU, определить закрытый ключ KR.
7)
Невозможно, зная открытый ключ KU и зашифрованное сообщение С, восстановить исходное сообщение М.
8)
Можно добавить шестое требование, хотя оно не выполняется для всех алгоритмов с открытым ключом:
9)
Шифрующие и дешифрующие функции могут применяться в любом порядке:
10) М = Е
KU
[D
KR
[M]]
Односторонней функциейназывается такая функция, у которой каждый аргумент имеет единственное обратное значение, при этом вычислить саму функцию легко, а вычислить обратную функцию трудно.
Обычно "легко" означает, что проблема может быть решена за полиномиальное время от длины входа. Таким образом, если длина
входа имеет n битов, то время вычисления функции пропорционально
n
a
, где а - фиксированная константа. Таким образом, говорят, что
алгоритм принадлежит классу полиномиальных алгоритмов Р. Термин