1.КРИПТОГРАФИЧЕСКИЕ СИСТЕМЫ, ОСНОВАННЫЕ НА МЕТОДЕ ПОДСТАНОВКИ
Криптографические системы, основанные на методе подстановки, разделяются на
четыре основных класса:
1) monoalphabetic;
2) homophonic;
3) polyalphabetic;
4) polygram.
В системах класса monoalphabetic символ исходного текста заменяется другим
символом таким образом, что между ними существует однозначное соответствие. То
есть каждый символ исходного текста однозначно заменяется его подстановкой.
Криптографическим ключем такой системы является таблица соответствия исходного
алфавита алфавиту подстановки. Например, для английского алфавита существует 26!
= 4*1026 различных криптографических систем первого класса. Наиболее простые
системы данного класса предполагают аналитическое описание подстановок. Так,
простейший шифратор, основанный на принципе подстановки, сдвигает каждую букву
английского алфавита на k позиций, где k является ключом шифра. В так называемом
алгоритме Цезаря i-я буква алфавита заменяется (i+k)-й буквой по модулю 26. Юлий
Цезарь использовал подобную систему для k=3. Аналитически криптосистема Цезаря
описывается выражением
Ek(i) = (i+k) mod 26. (1.1)
Например, в соответствии с приведенным выражением буква A исходного английского
алфавита, имеющая номер i=0, заменяется буквой D, имеющей номер (i+k) mod 26 =
(0+3) mod 26 = 3, а буква z (i=25) заменяется буквой C, имеющей номер (i+k) mod
26 = (25+3) mod 26 = 2. Следующий пример иллюстрирует алгоритм шифрования
Цезаря:
Исходный текст :CRYPTOGRAPHYANDDATASECURITY.
Шифротекст :FUBSWRJUDSKBDQSGDWDVHFXULWB.
Алгоритм дешифрования имеет вид
Dk(i) = (i+26-k) mod 26. (1.2)
Существуют более сложные методы подстановки. Шифраторы, основанные на умножении
номера каждого символа исходного текста на значение ключа k, описываются
следующим отношением:
Ek(i) = (i*k) mod n, (1.3)
где i - номер символа исходного текста, n - количество символов в исходном
алфавите (n=26 для английского алфавита и n=256 для ASCII-кодов), k - ключ, n и
k должны быть взаимно простыми.
Шифраторы, основанные на сдвиге и умножении, описываются выражением
Ek(i) = (i*k1+k0) mod n. (1.4)
Любой шифратор класса monoalphabetic может быть представлен в виде
полиномиального преобразования порядка t:
Ek(i) = (k0 + k1*i + k2*i2 +...+ kt-1*it-1 + kt*it) mod n. (1.5)
Алгоритм Цезаря является полиномиальным преобразованием нулевого порядка.
В криптографических системах класса homophonic имеется несколько вариантов
замены исходного символа. Например, буква A может быть заменена цифрами 24, 35,
37, а буква B - цифрами 41, 17, 76. Тогда слово ABBA может быть зашифровано как
(37, 17, 76, 24), или (35, 41, 76, 37) и т. д. Подобные системы характеризуются
значительно большей криптографической стойкостью, чем системы класса homophonic.
Криптографические системы класса polyalphabetic основаны на использовании
нескольких различных ключей . Большинство шифраторов подобного типа являются
периодическими с периодом P. Исходный текст вида
X = x1 x2 x3 x4 ... xp xp+1 ... x2p ...
шифруется с помощью ключей k1, k2, ..., kp:
Ek(X)= Ek1(x1) Ek2(x2) ... Ekp(xp) Ek1(xp+1) ... Ekp(x2p) (1.6)
Для p=1 будем иметь шифр класса monoalphabetic.
Один из таких алгоритмов был предложен в XVI веке французом Вигеном (Vigenere).
В данном случае ключ K представляется последовательностью
K = k1 k2 ... kp,
где ki (1