Лекция дискрет 09
.pdf
Шифр Ришелье (для переписки с королём)
Идея шифра – перемешивание букв исходного текста с использованием нескольких ключей-подстановок
Например, три ключа:
2741635; 15243; 671852493
Эти ключи соответствуют подстановкам
1 |
2 |
3 |
4 |
5 |
6 |
7 |
1 |
2 |
3 |
4 |
5 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
2 |
7 |
4 |
1 |
6 |
3 |
5 |
1 |
5 |
2 |
4 |
3 |
6 |
7 |
1 |
8 |
5 |
2 |
4 |
9 |
3 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
1 |
2 |
3 |
4 |
5 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
2 |
7 |
4 |
1 |
6 |
3 |
5 |
1 |
5 |
2 |
4 |
3 |
6 |
7 |
1 |
8 |
5 |
2 |
4 |
9 |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
Схема шифрования путём перемешивания: первая буква исходного текста идёт во вторую позицию шифрованного, вторая – на место 7, … , седьмая – на 5-ую позицию.
Последующие пять перемещаются с использованием второй подстановки: буква 8 остаётся на месте, девятая уходит в позицию 12 (7+5) и т.д.
Затем применяется третья подстановка, затем вновь первая, за ней – вторая и т.д. до исчерпания шифруемого текста.
Ключи расшифрования – обратные подстановки:
1 |
2 |
3 |
4 |
5 |
6 |
7 |
1 |
2 |
3 |
4 |
5 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
|
|
|
|
|
|
|
|
||||||||||||
4 |
1 |
6 |
3 |
7 |
5 |
2 |
1 |
3 |
5 |
4 |
2 |
3 |
6 |
9 |
7 |
5 |
1 |
2 |
4 |
8 |
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
1 |
2 |
3 |
4 |
5 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
|
|
|
|
||||||||||||||||
2 |
7 |
4 |
1 |
6 |
3 |
5 |
1 |
5 |
2 |
4 |
3 |
6 |
7 |
1 |
8 |
5 |
2 |
4 |
9 |
3 |
|
|
|
|
|
П И С Ь М О О Т П Р А В Л Е Н О В А Ш Е
2 |
7 |
|
4 |
1 |
6 |
3 |
5 |
1 |
5 |
2 |
4 |
3 |
6 |
7 |
1 |
8 |
|
5 |
2 |
4 |
|
9 |
3 |
2 |
|
|
|
|
|
|
|||||||||||||||||||
Ь П О |
С М И |
О П А Р Т Е |
Ш В О В |
Л Н А |
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
1 |
|
6 |
3 |
7 |
5 |
2 |
1 |
3 |
5 |
4 |
2 |
3 |
6 |
9 |
7 |
|
5 |
1 |
2 |
|
4 |
8 |
4 |
|
|
|||||||||||||||||||||||
П И С |
Ь М О |
О Т П Р А В |
Л Е Н О |
В А Ш |
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
1 |
2 |
3 |
4 |
5 |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
4 |
1 |
6 |
3 |
7 |
5 |
2 |
|
1 |
3 |
5 |
4 |
2 |
|
3 |
6 |
9 |
7 |
5 |
1 |
2 |
4 |
8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
Особенность шифра перемешивания: не чувствителен к частотному анализу, поскольку все буквы просто переставляются, сохраняя свои частоты использования.
5) Ещё о группах и полугруппах
Теория групп — это ветвь математики, в которой кто-то делает что-то с чем-то, а затем сравнивает результат с результатом применения той же операции к чему-нибудь ещё или с результатом применения чегонибудь ещё к тому же объекту.
Джеймс Ньюман (США)
6) Другие алгебраические структуры
|
Алгебра [ M; +, ] с одной аддитивной |
||
|
и одной мультипликативной операцией |
||
+ дистрибутивность слева и |
+ алгебра [ M; + ] – абелева |
||
справа операции ( ) |
|||
группа |
|||
|
|
||
относительно операции (+) |
|
||
Кольцо
+ обратный элемент относительно операции ( )
Тело
+ коммутативность операции ( )
Поле
Кольцо квадратных матриц n-ого порядка
[ {Mn}; +, ]
Поле
действительных
чисел
[ R; +, ]
Я приветствую полугруппу, где бы я её ни встретил, а встречается она повсюду. Впрочем, от друзей я слышал, что в математике попадаются объекты, отличные от полугрупп.
Хилле Эйнар (США)
Глава 3. Логические функции
§ 3.1. Основные понятия
Логическая функция – n-арная операция на множестве B = {0, 1}, т.е. функция f: Bn B
Множество всех логических функций - P2
Множество всех логических функций n переменных - P2(n)
f(x1,x2, … ,xn) Каждая xi (i=1…n) принимает два значения – |
|||||||||||||
0 и 1 |
|
|
2n различных наборов значений переменных, |
||||||||||
поэтому возможен полный перебор (пример – f(x1,x2,x3)) |
|||||||||||||
Таблица истинности |
|
Количество различных функций n |
|||||||||||
|
|
|
|
|
|
|
|||||||
x1 |
|
x2 |
x3 |
|
f(x1,x2,x3) |
||||||||
|
|
|
переменных – количество различных |
||||||||||
0 |
|
0 |
0 |
|
0 |
|
векторов значений длиной 2n в |
||||||
0 |
|
0 |
1 |
|
1 |
|
таблице истинности, то есть |
||||||
|
|
|
|
|
|
|
|
|
|
||||
0 |
|
1 |
0 |
|
0 |
|
|
|
|
│P2(n)│ = 22n |
|||
0 |
|
1 |
1 |
|
0 |
|
│P2(1)│ = 4 |
|
|
|
|||
1 |
|
0 |
0 |
|
1 |
|
|
|
|
|
|
φ0 – константа 0 |
|
|
|
|
x |
φ0 |
φ1 |
φ2 |
φ3 |
||||||
|
|
|
|
|
|
|
|||||||
1 |
|
0 |
1 |
|
1 |
|
φ1 |
– тождество |
|||||
|
|
|
0 |
0 |
0 |
1 |
1 |
||||||
1 |
|
1 |
0 |
|
0 |
|
φ2 |
– отрицание (¬) |
|||||
|
|
|
1 |
0 |
1 |
0 |
1 |
||||||
1 |
|
1 |
1 |
|
0 |
|
φ3 – константа 1 |
||||||
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
│P |
(2)│ = 222 = 16 |
|
|
|
|
|
|
|
||
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 |
x2 |
ψ0 |
ψ1 |
ψ2 |
ψ3 |
ψ4 |
ψ5 |
ψ6 |
ψ7 |
|
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
|
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
|
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
x1 |
x2 |
ψ8 |
|
ψ9 |
ψ10 |
ψ11 |
ψ12 |
ψ13 |
ψ14 |
ψ15 |
0 |
0 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
|
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
|
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
|
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|