Шифры замены (подстановки)

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

Простейшим из шифров замены является одноалфавитная подстановка, называемая также шифром простой замены. Ключом такого шифра является взаимно однозначное отображение (подстановка) F алфавита открытого текста (X) в алфавит шифртекста (Y): F: X↔Y. Зафиксируем нумерацию символов в алфавитах X и Y: X = {x1, x2, … xn}, Y = {y1, y2, … yn}. Тогда отображение F фактически задается перестановкой p порядка n = |X| = |Y|: при шифровании символ xi открытого текста заменяется на символ yp(i) шифртекста. Эта перестановка может быть задана либо таблицей, либо с помощью формулы. При задании с помощью формулы значение p(i) представляется в виде выражения, зависящего от i.

Типичным примером шифра замены является шифр Цезаря. Этот шифр реализует следующее преобразование текста, записанного с помощью латинского алфавита: каждая буква открытого текста заменяется буквой, стоящей на три позиции позже нее в алфавите (при этом алфавит считается записанным по кругу, то есть после буквы 'z' идет буква 'a'). Например, открытый текст "secret" будет преобразован в "vhfuhw". Ключ для шифра Цезаря можно задать в виде следующей таблицы (см. рис. 2.3). В первой строке записаны буквы открытого текста, во второй – соответствующие им буквы шифртекста.


 

 

a b c d e f g h i j k l m n o p q r s t u v w x y z
d e f g h i j k l m n o p q r s t u v w x y z a b c
Рис. 2.3. Таблица замен шифра Цезаря.

 

Шифр Цезаря можно описать и в виде формулы. Для этого пронумеруем буквы латинского алфавита числами от 0 до 25: a = 0, b = 1, …, z = 25. Тогда правило замены можно описать следующим образом: буква с номером i заменяется на букву с номером i+3 (mod 26), где операция "mod 26" означает вычисление остатка от деления на 26.

Разумеется, возможен обобщенный вариант шифра Цезаря, при котором буква с номером i заменяется на букву с номером i+k (mod 26). В этом случае ключом шифра является число k.

Еще больше обобщив этот метод, мы придем к семейству аффинных шифров. Для алфавита из n символов {a1, a2, …, an} аффинным шифром называется процедура, заменяющая входной символ ai на символ aj, где j = k⋅i+l (mod n). Для того чтобы имелась возможность расшифрования числа n и k должны быть взаимно простыми, то есть НОД(n, k) = 1.

Шифры простой замены в настоящее время не используются, поскольку их стойкость невелика. Методы взлома таких шифров основаны на анализе частотности отдельных символов и их комбинаций. Дело в том, что в любом языке различные буквы и комбинации из двух, трех или большего количества букв имеют характерные частоты повторений в текстах. Например, в текстах на русском языке чаще всего встречается буква 'О', затем, в порядке убывания частоты, идут буквы 'Е' (считая, что 'Е' и 'Ё' – одна и та же буква), 'А', 'И', 'Т' и т.д. Для английского языка аналогичная последовательность самых частых букв: 'E', 'T', 'A', 'I', 'N'. Самым частым символом в текстах является, однако, не буква, а символ пробела.

Ясно, что при использовании шифра простой замены частота повторений зашифрованных символов в шифртексте совпадает с частотой повторений соответствующих исходных символов в открытом тексте. Это позволяет достаточно легко вскрыть такой шифр. Более тонкие характеристики (учет сочетаемости различных букв) позволяют даже автоматизировать процесс взлома.

Для того чтобы увеличить стойкость шифров замены, применяют многоалфавитную подстановку, называемую также шифром сложной замены. Процедура шифрования для многоалфавитной замены включает набор подстановок {p1, p2,…, pm} и функцию-распределительY(k,i), задающую последовательность применения подстановок pi. При шифровании i-го символа открытого текста применяется подстановка с номером Y(k,i), где k — ключ шифрования.

Частным случаем многоалфавитной замены является шифр Виженера. Формально этот шифр можно описать следующим образом. В качестве ключа шифрования выберем набор из m целых чисел: k = (k1, k2, …, km). Процедуру преобразования открытого текста t = (t1, t2, …) в шифртекст c = (c1, c2, …) построим на основе обобщенного шифра Цезаря: c1 = t1 + k1 (mod 26),
c2 = t2 + k2 (mod 26), и т.д. Когда будут использованы все m компонент ключа k, для шифрования (m+1)-й буквы снова возьмем k1, и т.д. Фактически, в качестве ключа шифрования используется гамма шифра – бесконечная последовательность, образованная периодическим повторением исходного набора: k1,k2,…,km, k1,k2,…,km, k1,k2,…

Взломать шифр многоалфавитной замены немного сложнее, чем шифры простой замены, но тоже достаточно легко. Такой шифр на самом деле представляет собой одновременное применение m шифров простой замены (обобщенный шифр Цезаря), причем часть исходного текста, состоящая из букв ti, tm+i, t2m+i, … шифруются с использованием "ключа" ki (i=1, …,m).

Если известен период гаммы (т.е. число m), то к каждой такой части можно применить любой из методов взлома шифров простой замены. Если период гаммы не известен, то задача усложняется. Но и для этих случаев разработаны эффективные методы взлома. Эти методы позволяют с достаточной вероятностью определить период гаммы, после чего задача сводится к взлому шифра гаммирования с известным периодом.

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

Простейшим вариантом гомофонического шифра является следующий. Предположим, что нам известны частоты вхождений символов в открытый текст. Пусть fi — частота появления i–го символа в открытом текста (i — номер буквы в алфавите). Каждой букве ti исходного алфавита (т.е. алфавита, с помощью которого записывается открытое сообщение) сопоставим подмножество Fi, содержащее fi символов выходного алфавита (т.е. алфавита, с помощью которого записывается шифртекст), причем никакие два подмножества Fi и Fj не пересекаются. При шифровании будем заменять каждое вхождение символа ti на случайный символ из множества Fi. Ясно, что средняя частота появления в шифртексте любого из символов выходного алфавита одинакова, что существенно затрудняет криптоанализ.

Шифры гаммирования

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

Суть метода гаммирования заключается в следующем. С помощью секретного ключа k генерируется последовательность символов

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

В качестве обратимой операции обычно используется либо сложение по модулю количества букв в алфавите n: либо, при представлении символов открытого текста в виде двоичного кода, операция поразрядного суммирования по модулю два (XOR): .

Расшифрование осуществляется применением к символам шифртекста и гаммы обратной операции: , или (операция XOR является обратной к самой себе).

Стойкость систем шифрования, основанных на гаммировании, зависит от характеристик гаммы – ее длины и равномерности распределения вероятностей появления знаков гаммы.

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

1) все символы гаммы полностью случайны и появляются в гамме с равными вероятностями;

2) длина гаммы равна длине открытого текста или превышает ее;

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

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

Обычно гамма либо получается периодическим повторением ключевой последовательности фиксированного размера, либо генерируется по некоторому правилу. Для генерации гаммы удобно использовать генераторы псевдослучайных чисел (ПСЧ). Наиболее известными генераторами ПСП являются линейный конгруэнтный генератор и генератор линейный рекуррентный последовательности.

Линейный конгруэнтный генератор задается рекуррентной формулой: gi = a×gi–1 + b (mod m), где gi – i-й член последовательности псевдослучайных чисел; a, b, m и g0 – ключевые параметры. Данная последовательность состоит из целых чисел от 0 до m – 1, и если элементы gi и gj совпадут, то последующие участки последовательности также совпадут: gi+1 = gj+1, gi+2 = gj+2, и т.д. Поэтому последовательность {gi} является периодической, и ее период не превышает m. Для того чтобы период последовательности псевдослучайных чисел, сгенерированной по указанной рекуррентной формуле, был максимальным (равным m), параметры данной формулы должны удовлетворять следующим условиям:

· b и m —взаимно простые числа;

· a – 1 делится на любой простой делитель числа m;

· a – 1 кратно 4, если m кратно 4.

Линейная рекуррентная последовательность задается следующей формулой:

, i = 0,1…,

где Å – операция вычисления суммы по модулю 2, – состояние j-го бита последовательности, – коэффициент обратной связи, , коэффициенты .

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

Последовательности такого вида легко реализуются программными или аппаратными средствами. Основу этой реализации составляет регистр сдвига с линейной обратной связью (РСЛОС).

РСЛОС представляет собой простое в реализации, недорогое устройство, способное формировать последовательности и обеспечить такие требования как:

· большой размер ансамбля последовательностей, формируемых на одной алгоритмической основе;

· оптимальность корреляционных функций в ансамбле;

· сбалансированность структуры;

· максимальность периода для данной длины регистра сдвига.

Обобщенная схема РСЛОС приведена на рис. 2.4.

 

Рис. 2.4. Обобщенный вид регистра сдвига с линейной обратной связью.

 

Сдвиговый регистр представляет собой последовательность битов. Количество битов определяется длиной регистра. Если длина равна n битам, то регистр называется n-битовым регистром сдвига. Всякий раз, когда в выходную последовательность нужно извлечь бит, все биты регистра сдвига сдвигаются вправо на 1 позицию. Новый крайний левый бит является функцией всех остальных битов регистра. Выдвинутый из регистра бит является очередным элементом последовательности. Периодом регистра сдвига называется длина получаемой последовательности до начала ее повторения.

Обратная связь представляет собой просто операцию XOR над битами регистра, для которых значения коэффициентов обратной связи равно 1. Перечень этих битов называется отводной последовательностью.

Любой n-битовый РСЛОС может находиться в одном из 2n–1 внутренних состояний. Это означает, что теоретически такой регистр может генерировать псевдослучайную последовательность с периодом 2n–1 битов. (Число внутренних состояний и максимальный период равны 2n–1, потому что заполнение РСЛОС нулями, приведет к тому, что сдвиговый регистр будет выдавать бесконечную последовательность нулей, что абсолютно бесполезно.) Только при определенных отводных последовательностях РСЛОС циклически пройдет через все 2n–1 внутренних состояний, такие РСЛОС являются регистрами с максимальным периодом. Получившийся результат называется М – последовательностью.

Для того, чтобы конкретный n-битовый РСЛОС имел максимальный период 2n–1, двоичный полином f(x) = hnxn + hn–1xn–1 + … + h1x + 1, образованный из отводной последовательности и константы 1, должен быть примитивным. Полином f(x) степени n называется примитивным, если его нельзя представить в виде произведения двух полиномов с меньшими степенями (свойство неприводимости) и, если x является генератором всех ненулевых полиномов со степенями не выше n, умножение которых осуществляется по модулю f(x).

В общем случае не существует эффективного способа генерировать примитивные полиномы данной степени. Проще всего выбирать полином случайным образом и проверять, не является ли он примитивным. Это чем-то похоже на проверку, не является ли простым случайно выбранное число. В настоящее время составлены таблицы примитивных полиномов, которыми можно воспользоваться при разработке конкретных РСЛОС.

В качестве примера рассмотрим РСЛОС максимального периода с полином обратной связи f(x) = x4 + x +1. На рис. 2.5 приведена его структурная схема.

Если начальное состояние этого РСЛОС – [0, 0, 0, 0], выходная последовательность также будет нулевой. В табл. 2.1 показано содержимое битов регистра a0, a1, a2, a3, в конце каждого такта t работы регистра при начальном состоянии [0, 1, 1, 0].

 

Рис. 2.5. РСЛОС с полином обратной связи f(x) = x4 + x +1.

 

Таблица 2.1

Пример 16-и тактов работы РСЛОС с полином обратной связи f(x) = x4 + x +1

t a0 a1 a2 a3   t a0 a1 a2 a3
 
 
 
 
 
 
 
 

 

При таком начальном заполнении РСЛОС выходная последовательность представляет собой 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, ¼ и является периодической с периодом 24–1= 15.

Ключевыми параметрами РСЛОС являются его отводная последовательность и начальное состояние регистра сдвига. Таким образом, для использования РСЛОС в потоковых шифрах, и при шифровании, и при расшифровании, обратную связь необходимо сконфигурировать на определенную отводную последовательность, а регистр инициализировать одним и тем же значением.