ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 05.12.2019
Просмотров: 12431
Скачиваний: 24
111
При этом полагается, что
Функцию Эйлера можно также представить в виде так
и пробегает все значения, участвующие в
разложении на простые сомножители.
Некоторые значения функции
+0 +1 +2 +3 +4 +5 +6 +7 +8 +9
0+
1
1
2
2
4
2
6
4
6
10+
4
10 4
12 6
8
8
16 6
18
20+
8
12 10 22 8
20 12 18 12 28
30+
8
30 16 20 16 24 12 36 18 24
40+
16 40 12 42 20 24 22 46 16 42
50+
20 32 24 52 18 40 24 36 28 58
60+
16 60 30 36 32 48 20 66 32 44
70+
24 70 24 72 36 40 36 60 24 78
80+
32 54 40 82 24 64 42 56 40 88
90+
24 72 44 60 46 72 32 96 42 60
Свойства функции Эйлера
1.
,
если —
простое
число. В
частности, при
имеем
;
2.
. То есть
3.
. Так
4.
5.
, если
, a
Асимптотические соотношения
1.
где — некоторая константа;
112
2.
3.
4.
Тема 2.2. Симметричные методы криптографии.
1. Виды симметричных криптографических систем.
2. Шифры перестановки
2.1. Шифрующие таблицы
2.2. Применение магических квадратов
3. Шифры подстановки (одноалфавитные и многоалфавитные)
4. Гаммирование.
1. Виды симметричных криптографических систем.
Симметричная криптография предполагает шифрование и расшифрование с
использованием одного и того же секретного ключа.
Все многообразие существующих симметричных криптографических
методов можно свести к следующим классам преобразований:
Шифрование заменой (подстановкой)
заключается в том, что символы
шифруемого текста заменяются символами того же или другого алфавита в
соответствии с заранее обусловленной схемой замены.
Шифрование перестановкой
заключается в том, что символы шифруемого
текста переставляются по определенному правилу в пределах некоторого
блока этого текста. При достаточной длине блока, в пределах которого
Симметричные
криптосистемы
Блочные шифры
Перестановки
Гаммирование
Подстановки
113
осуществляется перестановка, и сложном неповторяющемся порядке
перестановки можно достигнуть приемлемой для простых практических
приложений стойкости шифра.
Шифрование гаммированием
заключается в том, что символы шифруемого
текста складываются с символами некоторой случайной последовательности,
именуемой
гаммой шифра.
Стойкость шифрования определяется в основном
длиной (периодом) неповторяющейся части гаммы шифра. Поскольку с
помощью ЭВМ можно генерировать практически бесконечную гамму шифра,
то данный способ является одним из основных для шифрования информации
в автоматизированных системах.
Áëî÷íûå øèôðû
-
п
ðåäñòàâëÿþò ñîáîé ïîñëåäîâàòåëüíîñòü (ñ âîçìîæ íûì ïîâòî-
ðåíèåì è ÷åðåäîâàíèåì) îñíîâíûõ ìåòîäîâ ïðåîáðàçîâàíèÿ, ïðèìåíÿåìóþ ê áëîê ó
(÷àñòè) øèôðóåìîã î òåê ñòà. Íàïðèìåð, ìîæ íî èñïîëüçîâàòü ïðàâèëî óìíîæ åíèÿ
âåê òîðà íà ìàòðèöó, ïðè÷åì óìíîæ àåìàÿ ìàòðèöà ÿâëÿåòñÿ ê ëþ÷îì øèô-
ðîâàíèÿ (ïîýòîìó åå ðàçìåð è ñîäåðæ àíèå äîëæ íû õðàíèòüñÿ â ñåê ðåòå), à
ñèìâîëàìè óìíîæ àåìîã î âåê òîðà ïîñëåäîâàòåëüíî ñëóæ àò ñèìâîëû øèôðóåìîã î
òåê ñòà. Äðóã èì ïðèìåðîì ìîæ åò ñëóæ èòü èñïîëüçîâàíèå òàê íàçûâàåìûõ
îäíîíàïðàâëåííûõ ôóíê öèé äëÿ ïîñòðîåíèÿ ê ðèïòîñèñòåì ñ îòêðûòûì ê ëþ÷îì.
Блочные шифры на практике встречаются чаще, чем “чистые” преобразова-
ния того или иного класса в силу их более высокой криптостойкости. Россий-
ский и американский стандарты шифрования основаны именно на этом
классе шифров.
Процессы шифрования и расшифрования осуществляются в рамках
некоторой криптосистемы. Характерной особенностью симметричной
криптосистемы является применение одного и того же секретного ключа как
при шифровании, так и при расшифровании сообщений.
Если ключ не был скомпрометирован, то при расшифровке автоматически
выполняется аутентификация отправителя, так как только отправитель имеет
ключ, с помощью которого можно зашифровать информацию, и только
получатель имеет ключ, с помощью которого можно расшифровать
информацию. Так как отправитель и получатель - единственные люди,
которые знают этот симметричный ключ, при компрометации ключа будет
скомпрометировано только взаимодействие этих двух пользователей.
114
Проблемой, которая будет актуальна и для других криптосистем, является
вопрос о том, как безопасно распространять симметричные (секретные)
ключи.
Как открытый текст, так и шифртекст образуются из букв, входящих в
конечное множество символов, называемых алфавитом. Примерами
алфавитов являются конечное множество всех заглавных букв, конечное
множество всех заглавных и строчных букв и цифр и т. п. В общем виде
некоторый алфавит £ можно представить так:
Σ = {а
0
, a
1
, а
2
, ..., a
m-1
}
.
При выполнении криптографических преобразований полезно заменить буквы
алфавита целыми числами 0,1,2,3,.... Это позволяет упростить выполнение
необходимых алгебраических манипуляций. Например, можно установить взаимно
однозначное соответствие между русским алфавитом
Σ
РУС
.= {АБВГДЕ... ЮЯ} и множеством целых
Z
32
= {0,1,2,3,..., 31};
между английским алфавитом
Σ
АНГЛ.
= {ABCDEF... YZ} и множеством целых
Z
26
= {0,1.2.3…….. 25}
(см. табл. 2.1 и 2.2).
В дальнейшем будет обычно использоваться алфавит
Z
m
= {0, 1.2.3, ....m-1},
содержащий m "букв" (в виде чисел}.
Замена букв традиционного алфавита числами позволяет более четко
сформулировать
основные
концепции
и
приемы
криптографических
преобразований.
Таблица 2.1
Соответствие между русским алфавитом и множеством целых
Z,, = {0,1.2,3 ............................... 31}
Буква
Число
Буква
Число
буква
ЧИСЛО
Буква
Число
А
0
И
8
Р
16
Ш
24
Б
1
Й
9
С
17
Щ
25
В
2
К
10
Т
18
Ь
26
Г
3
Л
11
У
19
Ы
27
Д
4
М
12
Ф
20
Ъ
28
Е
5
Н
13
X
21
Э
29
Ж
6
О
14
Ц
22
Ю
30
3
7
П
15
Ч
23
Я
31
Таблица 2.2
Соответствие между английским алфавитом и множеством целых
Z
26
= {0, 1, 2, 3
25}
115
Буква
Число
Буква Число
Буква
Число
А
0
J
9
S
18
В
1
К
10
т
19
С
2
L
11
и
20
D
3
М
12
V
21
Е
4
N
13
W
22
F
5
О
14
X
23
G
6
Р
15
Y
24
Н
7
Q
16
Z
25
1
8
R
17
Объединяя по определенному правилу буквы из алфавита Z, можно создать
новые алфавиты:
•
алфавит Σ
2
, содержащий т
2
биграмм a
0
a
0l
a
0
a
1
a
m
_
1
a
m
_
1
;
•
алфавит Σ
3
, содержащий m
3
триграмм a
0
a
0
a
0
a
0
a
0
a
l
a
m
_
1
a
m
_
1
a
m
_
1
В общем случае, объединяя по n букв, получаем алфавит Z
n
. содержащий m
n
n-грамм [95].
Например, английский алфавит
Σ
АНГЛ.
= {ABCDEFGH ... WXYZ}
объемом m =26 букв позволяет сгенерировать посредством операции
конкатенации алфавит из 26
2
=676 биграмм
АА, АВ . XZ, ZZ,
алфавит из 26
3
= 17576 триграмм
ААА.ААВ ZZX.ZZZ и т.д.
Таким образом, текст с n буквами из алфавита Z
m
можно рассматривать как
n-грамму
Х (Хо, X
1
, Х
2
, ..., Хn-1),
где X
i
є Z
m
, 0 < i < n, для некоторого целого n =1, 2, 3
Через
Z
mn
будем обозначать множество n-грамм, образованных из букв
множества Z
m
.
Криптографическое преобразование Е представляет собой совокупность
преобразований
Е = {Е
(n)
: 1 < n < оо},
E
(n)
:Z
min
→Z
m
.
n
.
(2.1)
Преобразование Е
(n)
определяет, как каждая n-грамма открытого текста
х є Z
mn
заменяется п-граммой шифртекста у, т. е.
у = Е
(n)
(х), причем x,y є Z
mn
,
при этом обязательным является требование взаимной однозначности
преобразования Е
(n)
на множестве Z
m
n
.
Криптографическая
система
может
трактоваться
как
семейство
криптографических преобразований
Е = {Е
к
:К є К},
(2.2)
помеченных параметром К, называемым ключом.