Подстановки. Анализ системы Вижинера

Под подстановкой множества Ммы подразумеваем взаимно однозначное отображение этого множества на себя:

p: М® М,

т. е. сопоставление p каждому элементу m изМнекоторого образа p(m), причем каждый элемент из Мявляется образом в точности одного элемента. Элемент p(m)обозначают также через p m.

В случае бесконечных множеств Мподстановки называют также преобразованиями, но слово «преобразование» в дальнейшем у нас будет использоваться как синоним слова «отображение».

Если множество Мконечно и его элементы занумерованы числами 0, 1, 2,..., m-1, то каждую подстановку можно полностью описать схемой, в которой под каждым номером k указывается номер p (k)элемента, являющегося прообразом элемента с номером k.

Под произведением p ₁ p₂двух подстановок p₁и p₂ понимается подстановка, которую мы получаем, осуществляя сначала подстановку p₂, а затем применяя к результату подстановку p₁, т. е.

p ₁ p₂ (m) = p ₁( p ₂(m)).

Для подстановок выполняется закон ассоциативности

(p₁p₂) p₃=p₁(p₂ p₂).

Тождественнойили единичной подстановкойявляется такое отображение p₀, которое каждый объект переводит в себя самого:

p₀(m) = m.

Тождественная подстановка обладает свойством единичного элемента группы:

"p₀: pp₀= p.

Обратной подстановкойp^-1 к подстановке p является такая подстановка, которая переводит p(m) ® m:

p^-1p(m)= p₀(m) = m, а также p^-1p=p_0.

Совокупность подстановок произвольного множества М образует группу, так как для нее выполнены аксиомы группы 1—4. Конечное множество Миз п элементов является также симметрической группой.

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

Выполним математический анализ шифра простой замены. Ключом шифра является подстановка π в алфавите Z_m, определяющая правило замены при шифровании буквы х открытого текста, представленной в виде целого числа на букву π(х) шифртекста:

π: х → π(х).

Подстановка π является взаимно однозначным отображением из Z_m на Z_m.

Множество П всех подстановок на Z_m является симметричнойгруппой и обладает следующими свойствами: замкнутость (произведение подстановок π ₁ π ₂ является подстановкой), ассоциативность, существованиеединичного и обратных элементов.

Для многоалфавитной подстановки Е_к ключ подстановки К представляет собой последовательность подстановок из P:

К = {(π ₀, π ₁, …, π _n-1), π _i Î P }, 1£ n < ¥.

Эта подстановкашифрует: п -грамму (х _0, х _1, х _{2, …,} х_n-1) открытого текста в п -грамму (y _0, y _1, y _{2, …,} y_n‑1) шифртекста в соответствии с формулой

y_i = π _i (х_i), 0 £ i < n, п = 1, 2, 3,....

При n ®¥ мы приближаемся к теоретически стойкой одноразовой системе шифрования.

Схема реализации многоалфавитной подстановки Е_к:

х_n-1,…, х ₁, х ₀ y_n-1, …, y ₁ y ₀

ИИ ¾¾¾¾¾→ Е _k ¾¾¾¾¾→ ПИ

k =(π ₀, π ₁, …, π _n-1)

ИК

Отметим характерные особенности подстановки Е _k:

• открытый текст шифруется побуквенно (буква за буквой);

• i -я буква шифртекста является функцией только i -й компоненты π _i ключа k и i -й буквы х_i открытого текста;

Замечание. Криптографическое преобразование Е _k будет одноалфавитнойподстановкой, если значения π _i одинаковы для каждого i =0,1,2,...; иначе оно будет многоалфавитной подстановкой.

Анализ системы Вижинера

Пусть ключевая последовательность системы Вижинера имеет длину r, тогда ключ r -алфавитной подстановки, который является строкой букв или цифр можно представить в виде последовательности подстановок

π =(π ₀, π ₁, …, π _r_-1),

Функция шифрования Вижинера Е_π: х → y преобразует открытый текст х =(х₀ _, х₁ _, х₂ _{, …,} х_n-1) в шифртекст y = (y₀ _, y₁ _, y₂ _{, …,} y_n-1) согласно правилу:

y = (y₀ _, y₁ _, y₂ _{, …,} y_n-1) = (π₀(х₀), π₁(х₁), …, π _n_-1 (х_n_-1)), где π _i =π₍ _i _mod _r ₎.

Криптосистема Хилла

Криптосистема Хилла и её частный случай шифр Плэйфера также относятся к классу шифров, основанных на аналитических преобразованиях шифруемых данных, как и аффинная система шифрования. Они основаны на подстановке не отдельных символов, а n -гpамм (шифр Хилла) или 2-гpамм (шифр Плэйфера). При более высокой криптостойкости они значительно сложнее для реализации и требуют достаточно большого количества ключевой информации.

Алгебраический метод, обобщающий аффинную подстановку Цезаря для шифрования n -грамм, был сформулирован Лестером С. Хиллом.

Шифрование ведется путем выполнения умножения вектора на матрицу. Матрица является ключом шифрования. Открытый текст разбивается на n -граммы – блоки длиной n, равной размерности матрицы, и каждая n -грамма рассматривается как вектор.

Множество целых Z_m, для которого определены операции сложения и умножения по модулю m, является кольцом. Если модуль m является простым числом, то существует обратная величина любого ненулевого элемента из Z_m.

Множество всех n -грамм х = (х _0, х _1, х _{2, …,} х_n-1) с компонентами из кольца Z_m образует векторное пространство Z_m,n над кольцом Z_m. Каждая п -грамма х является вектором. В векторном пространстве Z_m,n для векторов х определены операции сложения и вычитания по модулю п, а также скалярное умножение вектора на элемент x кольца Z_m. Сложение и скалярное умножение являются операциями, удовлетворяющими коммутативному, ассоциативному и дистрибутивному законам.

Базисом для векторного пространства Z_m,n является набор векторов из { х⁽ ⁱ ⁾: 0£ i < L}, которые линейно независимы и порождают Z_m,n. То есть любой вектор х является линейной комбинацией векторов базиса

х =t₀ х⁽ ⁰⁾ + t₁ х⁽ ¹⁾ + … + t_(L-1) х ^(L-1) mod m.

Ключевая матрица Т размером п х п вида Т ={g _i _,j}, i,j = 0, 1, …, n - 1 задает отображение, являющееся линейным преобразованием:

Т: Z_m,n → Z_m,n, Т: х → у; у=Тх,

где .

Это преобразование удовлетворяет условию линейности:

T (t ·x + s ·y)= t Тх + s ·Ту mod m для всех s, t из Z_m и х,у из Z_m,n.

Для дешифрования шифртекста необходимо выполнить обратное преобразование:

х =Т ^-1 у.

Для того, чтобы линейное преобразование Т, заданное своей матрицей, могло быть криптографическим преобразованием, необходимо чтобы оно было обратимым (или невырожденным), то есть должно существовать обратное линейное преобразование

Т ^-1: Z_m,n → Z_m,n: Т Т ^-1 = Т ^-1 Т = I, где I – единичная матрица.

Для этого необходимо, чтобы образы { Tх⁽ ⁱ ⁾: 0£ i < n } векторов базиса { х⁽ ⁱ ⁾: 0£ i < n } пространства n -грамм исходного текста Z_m,n в свою очередь являлись базисом пространства криптограмм Z_m,n.

Известно, что каждый базис для Z_m,n содержит п линейно независимых векторов и любой набор из п линейно независимых векторов, над Z_m,n, является базисом.

Если { х⁽ ⁱ ⁾: 0£ i < n } линейно независимы над Z_m,n, тогда их образы { Tх⁽ ⁱ ⁾: 0£ i < n } линейно независимы над Z_m,n только в том случае, если определитель матрицы det Т не делится на любое простое р, которое делит m.