Дискретная математика. Комбинаторика. Ерош И.Л. - 29 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

29
тим, что имеется всего одна благоприятная комбинация, поэтому веро-
ятность распаять разъем правильно, не имея монтажной схемы, равна
P = 1/40320 = 0,0000248. Для решения второй части задачи число
благоприятных комбинаций значительно больше и определяется как
P =
3
8
C
⋅
D
5
= 56 ⋅ 44 = 2464. Поэтому вероятность припаять правильно
ровно 3 провода из 8 равна P = 2464/40320 = 0,061.
2.3. Криптография
При исследовании любых криптографических систем используются
комбинаторные методы. Они позволяют найти количество комбинаций
для расшифровки сообщения и поэтому являются важным инструмен-
том криптоаналитика.
Рассмотрим, например, простейшую классическую криптографичес-
кую систему, называемую системой Цезаря. В этой системе произво-
дится замена букв по определенному правилу. Сначала в первой строке
выписываются подряд все буквы алфавита. Затем формируется ниж-
няя строка, составленная из тех же букв, расположенных в том же по-
рядке, но со сдвигом на s позиций. Для оценки затрат криптоаналитика
по подбору шифра замены требуется вычислить количество вариантов
ключей (т. е. сдвигов). Это число равно количеству букв n в алфавите.
Для латинского алфавита n = 26, для русского алфавита n = 33, поэтому
криптоаналитик должен перебрать соответствующее число разных клю-
чей, т. е. рассмотреть все шифры замены, получаемые всевозможны-
ми сдвигами букв алфавита, т. е. 26 или 33 элемента группы сдвига.
Криптосистема DES оперирует с ключом, состоящими из 56 бит.
Криптоаналитик для вскрытия шифра должен перебрать все 2
56
вари-
анта ключей (если учитывать ключи, состоящие из одних нулей и одних
единиц). Если же имеется дополнительная информация об используе-
мых характеристиках ключей, перебор может быть существенно умень-
шен с помощью комбинаторных методов.
Рюкзачная криптосистема с открытым распределением ключей име-
ет дело с вектором A = (a
1
, a
2
, ..., a
n
). При шифровании сообщений
открыто передаются значения сумм некоторых элементов a
i
, при этом
криптоаналитику часто бывает известно количество элементов и их
сумма (но не известны сами элементы). Для вскрытия шифра криптоа-
налитик должен перебрать число ключей, равное числу сочетаний из n
по k.

Страницы