|
U={a, 1, 0},
V={b, 0, 1},
T={U[1]modV[1], U[2]-[U[1]/V[1]]*V[2], U[3]-[U[1]/V[1]]*V[3]}.
Если в результате первого значения множеству T равно на «1» T[1]=1 тогда, d=T[3].
Если, T[1]1 тогда, переходят V на U и T на V, продолжается до T[1]=1.
Например, (d*8)mod23=1; a=23, b=8;
U={23, 1, 0},
V={8, 0, 1},
T={23mod8, 1-[23/8]*0, 0-[23/8]*1}={7, 1, -2}
T[1]1, тогда продолжаем следующей выражений
U=V={8, 0, 1},
V=T={7, 1, -2},
T={U[1]modV[1], U[2]-[U[1]/V[1]]*V[2], U[3]-[U[1]/V[1]]*V[3]}.
T={8mod7, 0-[8/7]*1, 1-[8/7]*(-2)}={1, -1, 3}. T[1]=1 тогда, d=T[3]=3.
Доказательство: (3*8)mod23=1. (d*8)mod23=1
Задание
1.
|
a=3; b=-4;
c=5; n=8;
|
a=-45;
n=7;
|
n=17;
e=2;
|
2.
|
a=6; b=-7;
c=8; n=8;
|
a=-54;
n=8;
|
n=19;
e=4;
|
3.
|
a=12; b=-21;
c=13; n=8;
|
a=-5;
n=60;
|
n=17;
e=3;
|
4.
|
a=14; b=-12;
c=13; n=8;
|
a=-55;
n=21;
|
n=23;
e=4;
|
5.
|
a=15; b=-16;
c=17; n=8;
|
a=-56;
n=50;
|
n=23;
e=6;
|
6.
|
a=51; b=-21;
c=12; n=8;
|
a=-52;
n=105;
|
n=23;
e=12;
|
7.
|
a=51; b=-10;
c=53; n=8;
|
a=-55;
n=4;
|
n=23;
e=2;
|
8.
|
a=89; b=-10;
c=56; n=8;
|
a=-63;
n=6;
|
n=29;
e=6;
|
9.
|
a=11; b=-12;
c=13; n=8;
|
a=-36;
n=89;
|
n=29;
e=5;
|
Практическая работа №2
Тема. Анализ паролей на основе однозначной подстановки
Симметричные криптосистемы (также симметричное шифрование, симметричные шифры) (англ. symmetric-key algorithm) — способ шифрования, в котором для шифрования и расшифровывания применяется один и тот же криптографический ключ.
Классическими примерами таких алгоритмов являются симметричные криптографические алгоритмы, перечисленные ниже:
Простая перестановка
Одиночная перестановка по ключу
Двойная перестановка
Перестановка "Магический квадрат"
В простых шифрах, к которым относятся шифры перестановки, используются таблицы, которые дают простые шифрующие процедуры перестановки букв в сообщении. Ключом в них служат размер таблицы, фраза, задающая перестановку или специальная особенность таблиц. Перестановка без ключа — один из самых примитивных методов шифрования.
Например, сообщение «НЕЯСНОЕ СТАНОВИТСЯ ЕЩЕ БОЛЕЕ НЕПОНЯТНЫМ» записывается в таблицу по столбцам. Пример для таблицы из 5 строк и 7 столбцов приведен на рис 1.1.
н
|
о
|
Н
| с |
Б
|
Н
|
я
|
Е
|
Е
|
0
|
я
|
0
|
Е
|
т
|
Я
|
С
|
В
|
Е
|
Л
|
П
|
н
|
С
|
т
|
и
|
Щ
|
Е
|
0
|
ы
|
Н
|
А
|
т
|
Е
|
Е
|
Н
|
м
|
Рис. 1.1. Таблица шифрования методом «перестановка без ключа»
После того, как открытый текст записан колонками, для образования шифровки он считывается по строкам. Если его записывать группами по 5 букв, то получится: НОНСБ НЯЕЕО ЯОЕТЯ СВЕЛП НСТИЩ ЕОЫНА ТЕЕНМ. Для использования этого шифра отправителю и получателю нужно договориться об общем ключе в виде размера таблицы. Объединение букв в группы не входит в ключ шифра и используется лишь для удобства записи не смыслового текста.
Более практический метод шифрования, называемый одиночной перестановкой по ключу, очень похож на предыдущий. Он отличается лишь тем, что колонки таблицы переставляются по ключевому слову, фразе или набору чисел длиной в строку таблицы. Используя в виде ключа слово ЛУНАТИК, получим следующие таблицы ( Рис. 2).
Л
|
У
|
Н
|
А
|
Т
|
И
|
К
|
4
|
7
|
5
|
1
|
6
|
2
|
3
|
Н
|
0
|
Н
|
С
|
Б
|
Н
|
я
|
Е
|
Е
|
0
|
Я
|
0
|
Е
|
т
|
Я
|
С
|
В
|
Е
|
Л
|
П
|
н
|
С
|
Т
|
И
|
Щ
|
Е
|
0
|
ы
|
Н
|
А
|
Т
|
Е
|
Е
|
Н
|
м
|
|
А
|
и
|
К
|
л
|
Н
|
Т
|
У
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
С
|
Н
|
я
|
Н
|
Н
|
Б
|
0
|
Я
|
Е
|
т
|
Е
|
0
|
0
|
Е
|
Е
|
П
|
н
|
Я
|
В
|
Л
|
С
|
Щ
|
0
|
ы
|
С
|
и
|
Е
|
Т
|
Е
|
Н
|
м
|
Н
|
т
|
Е
|
А
|
|
До перестановки
|
После перестановки
|
Рис. 1.2. Таблицы шифрования
Шифр подстановки — это метод шифрования, в котором элементы исходного открытого текста заменяются зашифрованным текстом в соответствии с некоторым правилом. Элементами текста могут быть отдельные символы (самый распространённый случай), пары букв, тройки букв, комбинирование этих случаев и так далее. В классической криптографии различают четыре типа шифра подстановки:
Одно алфавитный шифр подстановки (шифр простой замены) — шифр, при котором каждый символ открытого текста заменяется на некоторый, фиксированный при данном ключе символ того же алфавита.
Однозвучный шифр подстановки похож на одноалфавитный за исключением того, что символ открытого текста может быть заменен одним из нескольких возможных символов.
Полиграммный шифр подстановки заменяет не один символ, а целую группу. Примеры: шифр Плейфера, шифр Хилла.
Полиалфавитный шифр подстановки состоит из нескольких шифров простой замены. Примеры: шифр Виженера, шифр Бофора, одноразовый блокнот.
Шифр Цезаря — один из древнейших шифров. При шифровании каждая буква заменяется другой, отстоящей от ней в алфавите на фиксированное число позиций. Шифр назван в честь римского императора Гая Юлия Цезаря, использовавшего его для секретной переписки. Естественным развитием шифра Цезаря стал шифр Виженера. Шифрование с использованием ключа k = 4:
Исходный алфавит: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Алфавит замены: E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
Рис.1.3. Шифр Цезаря
Задание: Разработать программы классических криптоалгоритмов подстановки и перестановки для защиты текстовой информации.
Практическая работа №3
Тема. Программирование классических шифров
Шифр Цезаря — один из древнейших шифров. При шифровании каждый символ заменяется другим, отстоящим от него в алфавите на фиксированное число позиций. Шифр Цезаря можно классифицировать как шифр подстановки, при более узкой классификации — шифр простой замены.
Шифр назван в честь римского императора Гая Юлия Цезаря, использовавшего его для секретной переписки. Естественным развитием шифра Цезаря стал шифр Виженера. С точки зрения современного криптоанализа, шифр Цезаря не имеет приемлемой стойкости.
Рис.1.1. Шифр Цезаря со сдвигом на 3
Алфавит:
Пример:
Ответ: «Пхнфчузхещнд»
Если сопоставить каждому символу алфавита его порядковый номер (нумеруя с 0), то шифрование и дешифрование можно выразить формулами модульной арифметики:
y=(x+k) mod n
x=(y-k+n) mod n,
где x — символ открытого текста,
y — символ шифрованного текста,
n — мощность алфавита,
k — ключ.
Квадрат Полибия
Шаг 1: Формирование таблицы шифрования
К каждому языку отдельно составляется таблица шифрования с одинаковым (не обязательно) количеством пронумерованных строк и столбцов, параметры которой зависят от его мощности (количества букв в алфавите). Берутся два целых числа, произведение которых ближе всего к количеству букв в языке — получаем нужное число строк и столбцов. Затем вписываем в таблицу все буквы алфавита подряд — по одной на каждую клетку. При нехватке клеток можно вписать в одну две буквы (редко употребляющиеся или схожие по употреблению).
Латинский алфавит
В современном латинском алфавите 26 букв, следовательно таблица должна состоять из 5 строк и 5 столбцов, так как 25=5*5 наиболее близкое к 26 число. При этом буквы I, J не различаются (J отождествляется с буквой I), так как не хватает 1 ячейки:
|
1
|
2
|
3
|
4
|
5
|
1
|
A
|
B
|
C
|
D
|
E
|
2
|
F
|
G
|
H
|
I/J
|
K
|
3
|
L
|
M
|
N
|
O
|
P
|
4
|
Q
|
R
|
S
|
T
|
U
|
5
|
V
|
W
|
X
|
Y
|
Z
|
Русский алфавит
Идею формирования таблицы шифрования проиллюстрируем для русского языка. Число букв в русском алфавите отличается от числа букв в греческом алфавите, поэтому размер таблицы выбран другой (квадрат 6*6=36, поскольку 36 наиболее близкое число к 33)
Do'stlaringiz bilan baham: |
