Криптография
При исследовании любых криптографических систем используются комбинаторные методы. Они позволяют найти количество комбинаций для расшифровки сообщения и поэтому являются важным инструментом криптоаиалитика.
Рассмотрим, например, простейшую классическую криптографическую систему, называемую системой Цезаря. В этой системе производится замена букв по определенному правилу. Сначала в первой строке выписываются подряд все буквы алфавита. Затем формируется нижняя строка, составленная из тех же букв, расположенных в том же порядке, но со сдвигом на s позиций. Для оценки затрат криптоаиалитика по подбору шифра замены требуется вычислить количество вариантов ключей (т. е. сдвигов). Это число равно количеству букв n в алфавите. Для латинского алфавита n = 26, для русского алфавита n = 33, поэтому криптоаналитик должен перебрать соответствующее число разных ключей, т. е. рассмотреть все шифры замены, получаемые всевозможными сдвигами букв алфавита, т. е. 26 или 33 элемента группы сдвига.
Криптосистема DES оперирует с ключом, состоящими из 56 бит. Криптоаналитик для вскрытия шифра должен перебрать все варианта ключей (если учитывать ключи, состоящие из одних нулей и одних единиц). Если же имеется дополнительная информация об используемых характеристиках ключей, перебор может быть существенно уменьшен с помощью комбинаторных методов.
Рюкзачная криптосистема с открытым распределением ключей имеет дело с вектором
А = При шифровании сообщений открыто передаются, значения сумм некоторых элементов ai, при этом криптоаналитику часто бывает известно количество элементов и их сумма (но не известны сами элементы). Для вскрытия шифра криптоаналитик должен перебрать число ключей, равное числу сочетаний из n по k.
