№1 - Основные понятия и термины алгебраической криптографии

Шифрование – преобразование текста с целью скрыть его содержание от несанкционированного прочтения.

Криптография – наука составления шифров и шифропротоколов.

Криптоанализ – наука о методах и способах вскрытия шифров.

Криптосистемой (системой шифрования) называют известный способ шифрования, обладающий сменными элементами – ключами.

Обычно рассматривают ключ шифрования и ключ дешифрования. Если их необходимо хранить в секрете, то система называется симметричной, или системой с секретными ключами.

Если ключ шифрования открыт, то есть не является секретным, то такие системы называются асимметричными, или системами с открытым ключом.

Шифрируемый текст называется исходным текстом. Результат шифрования называется шифртекстом.

Система шифрования включает в себя в качестве основного элемента функцию шифрования. Функция шифрования преобразует исходный текст в шифровку. Эта функция зависит от ключа шифрования.

Основное правило шифрования

Исходный текст должен однозначно восстанавливаться по шифртексту, то есть функция должна быть обратимой.

Криптостойкость – способность криптосистемы производить шифровки, трудные для несанкционированного прочтения (взлома)

Стойкие системы таковы, что нахождение обратной к функции шифрования в общем случае трудная задача. Однако при знании соотвествующего секрета – ключа дешифрования – это нахождение эффективно выполним

Определение. Односторонней функцией $y = f(x)$ будем называть такую функцию, для которой вычисление $y$ по $x$ осуществляется достаточно просто, а нахождение $y$ по $x$ – трудная задача.

Для  шифрования используют одностороние функции $y = f(x)$ с секретом.

1) для $f$ существует $f^{-1}$
2) $f^{-1}$ можно найти эффективно, зная секрет

В современной криптографии используемая киберсистема считается открытой, то есть метод шифрования не является секретным. При этом её криптостойкость определяется не только качесвтом криптосистемы, но и надежностью используемых ключей.

Алфавит

Мы рассматриваем тексты, которые записываются в виде конечных последовательностей знаков соотсвтеующего алфавита.

Алфавит может иметь обычный смысл: 33 буквы от А до Я или 26 букв от А до Z

Определение. Алфавитом будем называть совокупность знаков, среди которых могут встречаться обычные буквы, цифры, знаки препинания, специальные знаки, обозначающие пробелы, и другие.

Иногда вместо алфавита используется термины знаковая система.

Текстом будем называть упорядоченный набор  знаков.

Имеется ещё одно понятие -  единницы текста. Самая простая единица текста  - знак. В качестве единицы текста можно считать, например, пары знаков – диграфы или тройки – триграфы.

При $k \geq 2$ последний $k$-граф текста может оказаться неполным, тогда его пополняют знаками выбраннрого вида.

Кроме этого, тексты часто разбивают на блоки. Блок – это некоторая конечная последовательность единиц текста. Обычна длина блока фиксирована. Одним из самых простых способов шифрования является простая замена. 

В криптографии, как правило, работают с оцифрованными текстами. Единицы текста заменяют на числа различной природы. Это могут быть обычные целые числа, элементы колец вычетов, конечных полей и т.д.

Оцифровка текста не является шифрованием. Исходный текст в его записи в данном алфавите должен однозначно восстанавливаться по своему оцифрованному виду.

Введем алфавит:

Текст $a\&21\_\&$ оцифровывается ккак 015473. Допустим теперь, что в алфавите мы в качестве единицы текста выберем диграфы. Паре $\alpha ,2 \iff 2 \text{ } 5$ отвечается запись числа $(2,5)$. В 8-ричной системе исчисления : $(2,5)_{8} = 5 + 2 * 8 = 21$. Всевозмодных пар $8^2 = 64$. Все они нумируются двузначными числами в 8-ричных системе исчиления от $(0,0)_{8} = 0$ до
$(7,7)_{8}=7+7*8=7+56=63$

Если мы рассмотрим $k$-граф $(a_{k-1},a_{k-2},\dots,a_{0})$, то ему можно сопоставить число
$$(a_{k-1},a_{k-2},\dots,a_{0})_{8}=$$
$$=a_{0}+a_{1}*8+\dots+a_{k-2}*8^{k-2}+a_{k-1}*8^{k-1}$$

Для русского алфавита удобно выбрать нумерацию 33-ричной системе
$\text{ГОД } \iff 3,15,4$

Три графу поставим в соответствие число $(3,15,4)_{33}=4+15*33+3*33^2=3766$

Обозначим $m \in \{0,1\}^*$ означает $m$-бинарная последовательность (последовательность нулей и единиц).

При использовании бинарных последовательностей удобно, чтобы алфавит содержал $2^k$ знаков.

Пример:

Платформой называется система, используемая для записи текста. Это может быть совокупность бинарных последовательностей, колец вычетов, конченое поле и т.д.

Иногда платформы исходного и зашифрованного текста разные.

Мы будем заниматься алгебраической криптографией, где она, как правило, в качестве платформы выбирает абстраткную группу.