№3 - Элементы шифрования. Шифры замены, перестановки и Вернама. Гаммирование

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

Определение. Хеш функцией $h$ называется функция, переводящая произвольную бинарную последовательность в последовательность определенной длины.

В криптографии хещ-функции используются для образования дайджестов $h(m)$ для сообщений $m$, создания образов некоторых данных для их безопастного хранения и ч.т.д

Обратимость кольца см в вопросе 2

Подставляя значения предыдущих остатков получим:
$$d=r_{s-1}-(r_{s-r}-r_{s-1}t_{s})t_{s+1}=$$
$$r_{s-1}(1+t_{s}t_{s+1})-r_{s-2}t_{s+1}=\dots$$
$$\dots kl+nt$$
Если $d=1$, то это означает, что $1=kl+nt$ или $kl=1-nt\implies kl=1(\text{mod }n)$
$l=k^{-1}$, т.е. элемент $k$ обратим.
Мы доказали, что если $\text{НОД }(k,n)=1$, то $\exists k^{-1}$

Шифр Вернама и гаммирование

Шифр Вернама работает с исходным текстом, представленным в виде бинарной последоватльности $m=m_{1}m_{2}\dots m_{e}$.
В качестве ключа используется бинарная последовательность $k=k_{1}k_{2}\dots k_{e}$ той же самой длины (или большей).

Шифрованный текст представляется в виде бинарной последовательности $c=c_{1}c_{2}\dots c_{e}$ той же самой длины. Процесс шифрования определяется операцией побитного сложения по $\text{mod 2}$:
$$c_{i}=m_{i} \oplus K_{i}, \text{ }i=1,2,\dots,l$$
Эиа операция называется $XOR$.

Более общим является шифрование методом гаммировния $\text{mod n}$. Обычно в качестве $n$ выбирают мощность алфавита, буквы которого занумерованы вычетами $0,\dots,n-1$.
Исходный текст $m=m_{1}m_{2}\dots m_{e}$ представлен вычетами $m_{i} (\text{mod }n),i=1,2,\dots,l$. Ключ также представляет собой последовательность вычетов по $\text{mod }n$ той же (или большей длины):
$$K=K_{1}K_{2},\dots K_{e}$$
Шифрование результатом которого является последовательность $c=c_{1}c_{2},\dots,c_{e}$ вычестов $\text{mod }n$, осуществлеяется по правилу:

$$c_{i}=m_{i}+k_{i} (\text{mod }n),i=1,2,\dots l \ \ (1)$$
Ясно, что дешифрирование шифрованного текста $c$ осуществляется по формуле:
$$m_{i}=c_{i}-k_{i}(\text{mod }n),i=1,2,\dots,l$$
В случае с $n=2$ получится $m_{i}=c_{i}+k_{i}$

Если ключ $K$ представляет собой случайную последовательность и используется один раз, то говорят о шифровании методом одноразового блокнота. Такое шифрование является абсолюнто надежным. Таким образом, из текста $m$ можно получать подходящим выбором ключа любой текст той же самой длины.

Любая частичная дешифровка текста (определение части ключа) не помогает при расшифровке остального текста (определению остатка ключа).

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

Гаммированием называется метод шифрования, который определяется формулой (1), но при этом ключ $K$ генерируется. Ключ $K$ называется гаммой.

К ключу $K$ предъявляются следующее требование: Последовательность, играющая роль ключа должна быть псевдослучайной.