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

---

---

Обратная таблица подстановок
SboxD = {
0x52, 0x09, 0x6A, 0xD5, 0x30, 0x36, 0xA5, 0x38, 0xBF, 0x40, 0xA3,
0x9E, 0x81, 0xF3, 0xD7, 0xFB,
0x7C, 0xE3, 0x39, 0x82, 0x9B, 0x2F, 0xFF, 0x87, 0x34, 0x8E, 0x43,
0x44, 0xC4, 0xDE, 0xE9, 0xCB,
0x54, 0x7B, 0x94, 0x32, 0xA6, 0xC2, 0x23, 0x3D, 0xEE, 0x4C, 0x95,
0x0B, 0x42, 0xFA, 0xC3, 0x4E,
0x08, 0x2E, 0xA1, 0x66, 0x28, 0xD9, 0x24, 0xB2, 0x76, 0x5B, 0xA2,
0x49, 0x6D, 0x8B, 0xD1,0x25,
0x72, 0xF8, 0xF6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xD4, 0xA4, 0x5C,
0xCC, 0x5D, 0x65, 0xB6,0x92,
0x6C, 0x70, 0x48, 0x50, 0xFD, 0xED, 0xB9, 0xDA, 0x5E, 0x15, 0x46,
0x57, 0xA7, 0x8D, 0x9D, 0x84,
0x90, 0xD8, 0xAB, 0x00, 0x8C, 0xBC, 0xD3, 0x0A, 0xF7, 0xE4, 0x58,
0x05, 0xB8, 0xB3, 0x45,0x06,
0xD0, 0x2C, 0x1E, 0x8F, 0xCA, 0x3F, 0x0F, 0x02, 0xC1, 0xAF, 0xBD,
0x03, 0x01, 0x13, 0x8A, 0x6B,
0x3A, 0x91, 0x11, 0x41, 0x4F, 0x67, 0xDC, 0xEA, 0x97, 0xF2, 0xCF,
0xCE, 0xF0, 0xB4, 0xE6, 0x73,
0x96, 0xAC, 0x74, 0x22, 0xE7, 0xAD, 0x35, 0x85, 0xE2, 0xF9, 0x37,
0xE8, 0x1C, 0x75, 0xDF, 0x6E,

---

---

39
Иногда b называют вычетом a по модулю m , a – конгруэнтным
b по модулю m. Операция c mod t означает остаток от деления c на t и называется приведением по модулю.
Числа, сравнимые по модулю, образуют класс вычетов по модулю
m. Все числа из одного и того же класса имеют один и тот же остаток r от деления на m. Любое число a из класса вычетов называется вычетом по модулю m.
Полная система вычетов – это совокупность вычетов, взятых по одному из каждого класса вычетов.
Приведённая система вычетов по модулю m – это совокупность всех вычетов из полной системы, взаимно простых с модулем m.
Теоремы Ферма и Эйлера
Функция Эйлера
φ(m)– это количество положительных целых чисел, которые меньше m и взаимно простые с m.
Например, φ(10)=4, т.к. числа 2, 4, 6 и 8 имеют общий с 10 делитель 2, число 5 имеет общий с 10 делитель 5, а числа 1, 3, 7 и 9 – не имеют общих делителей с 10 (кроме 1) и, следовательно, являются взаимно простыми с числом 10.
Если p – простое, то φ (p)=p-1
Если p ,q – простые, то
φ (n)= φ (p⋅q)= φ (p) ⋅ φ (q)=(p-1) ⋅ (q-1)
φ (n)= φ (p
α
⋅q
β
)=
φ (p
α
)
⋅ φ (qβ)=(p-1) ⋅p
α-1
⋅ (q-1) ⋅q
β-1
Теорема Эйлера: Для любых взаимно простых чисел a и m справедливо a
φ
(n)
≡ 1 (mod m).
Следствие из теоремы Эйлера: a
φ(m)+1
≡ a (mod m)
Теорема Ферма: Если p– простое число, a– положительное целое число, которое не делится на p, то a p-1
≡ 1 (mod p ).

40
Тест Ферма
Из малой теоремы Ферма следует, что, если для нечетного n существует такое целое a , что 1<=a<=n, НОД (a,n)=1и
)
(mod
1 1
p
a
n


, то число n вероятно простое.
Входные данные: нечетное число n≥5;
Выходные данные: "число n составное", " число n вероятно простое".
1.
Выбирается случайное целое число a, 2<=a<=n-2.
2.
Вычисляется
)
mod
(
1
n
a
r
n


3.
При r=1 тест дает ответ, что "число n вероятно простое".
Иначе " число n составное ".
Существенным недостатком данного теста является наличие чисел
Кармайкла. Это нечетные составные числа, для которых сравнение из формулы выполняются при любом a.
Тест Рабина-Миллера
Тест Рабина-Миллера чаще всего используется для проверки числа на простоту.
Входные данные: нечетное число n>=5;
Выходные данные: "число n составное", "число n вероятно простое ".
1.
Представить n-1 в виде n-1=2
s
, число r - нечетное.
2.
Выбирается случайное целое число a, 2<=a<=n-2.
3.
Вычислить
)
(mod n
a
y
r

4.
При
1

y
и
1


n
y
выполнить следующие действия:
4.1 Пусть j=1 4.2 Если j<=s-1 и y≠n-1

---