Разработка и исследование криптоалгоритма на основе использования скремблера

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

Скремблеры

Суть скремблирования заключается в побитном изменении проходящего через систему потока данных. Практически единственной операцией, используемой в скремблерах является XOR – "побитное исключающее ИЛИ". Параллельно прохождению информационного потока в скремблере по определенному правилу генерируется поток бит – кодирующий поток. Как прямое, так и обратное шифрование осуществляется наложением по XOR кодирующей последовательности на исходную.

Генерация кодирующей последовательности бит производится циклически из небольшого начального объема информации – ключа по следующему алгоритму. Из текущего набора бит выбираются значения определенных разрядов и складываются по XOR между собой. Все разряды сдвигаются на 1 бит, а только что полученное значение ("0" или "1") помещается в освободившийся самый младший разряд. Значение, находившееся в самом старшем разряде до сдвига, добавляется в кодирующую последовательность, становясь очередным ее битом (см. рис.1).

Рис.1.

Из теории передачи данных криптография заимствовала для записи подобных схем двоичную систему записи. По ней изображенный на рисунке скремблер записывается комбинацией "10011₂" – единицы соответствуют разрядам, с которых снимаются биты для формирования обратной связи.

Рассмотрим пример кодирования информационной последовательности 010111₂ скремблером 101₂ с начальным ключом 110₂.

скремблер код.бит инф.бит рез-т

1 1 0 _

\ \ \_

1 1 1 _ \_

\ \ \_ 0 XOR 0 = 0

0 1 1 _ \_

\ \ \_ 1 XOR 1 = 0

1 0 1 \_

\ \ 1 XOR 0 = 1

и т.д.

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

Декодирование заскремблированных последовательностей происходит по той же самой схеме, что и кодирование. Именно для этого в алгоритмах применяется результирующее кодирование по "исключающему ИЛИ" – схема, однозначно восстановимая при раскодировании без каких-либо дополнительных вычислительных затрат.

Генераторы последовательностей наибольшей длины

В математике доказывается (в терминах применительно к скремблированию), что для скремблера любой разрядности N всегда существует такой выбор охватываемых обратной связью разрядов, что генерируемая ими последовательность бит будет иметь период, равный 2N-1 битам.

Так, например, в 8-битном скремблере, при охвате 0-го, 1-го, 6-го и 7-го разрядов действительно за время генерации 255 бит последовательно проходят все числа от 1 до 255, не повторяясь ни разу.

ПНД неразрывно связаны с математической теорией неприводимых полиномов. Оказывается, достаточно чтобы полином степени N не был представим по модулю 2 в виде произведения никаких других полиномов, для того, чтобы скремблер, построенный на его основе, создавал ПНД.

Например, единственным неприводимым полиномом степени 3 является x3+x+1, в двоичном виде он записывается как 1011₂ (единицы соответствуют присутствующим разрядам).

Скремблеры на основе неприводимых полиномов образуются отбрасыванием самого старшего разряда (он всегда присутствует, а следовательно, несет информацию только о степени полинома), так на основе указанного полинома, мы можем создать скремблер 011₂ с периодом зацикливания 7(=2³-1).

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

Задание на лабораторную работу

Написать программу на C#, выполняющую:

1. 
   Ввод строки текста с клавиатуры
   
2. 
   Кодирование этой строки последовательным применением скремблера к каждому биту каждого ее символа. В качестве скремблера взять двоичный эквивалент числа (17), в качестве начального значения ключа – число (118).
   
3. 
   Печать закодированной строки (в символьном или двоичном представлении)
   
4. 
   Определить период повторения последовательности, генерируемой заданным скремблером для нескольких начальных значений ключа, выбранных случайным образом в диапазоне (0 – 255).
   
5. 
   Выбрать начальное значение с максимальным периодом повторения и выполнить кодирование и декодирование строки повторным применением скремблера.
   
6. 
   По варианту задания, выданному преподавателем, построить генератор ПНД и выполнить кодирование и декодирование той же самой исходной строки применением скремблера, реализующего данный генератор.
   

Вариант: G₁(x⁸) x⁸+x⁴+x³+x+1

7. 
   Печать раскодированной строки (по желанию – сравнение с исходной строкой и печать сообщения корректности кодирования и декодирования)
   

Таблица 2. Неприводимые и примитивные полиномы. (В круглых скобках показаны неприводимые, но не примитивные полиномы).

N Полиномы (в шестнадцатеричном формате)

1 3 2

2 7

3 B D

4 13 19 (1F)

5 25 29 2F 37 3B 3D

6 43 (45) 49 57 5B 61 6D 73

7 83 87 91 9D A7 AB B9 BF Cl CB

D3 D4 E5 EF Fl F7 FD

8 (11B) 11D 12B 12D (139) (13F) 14D 15F 163 165

169 171 (177) (17B) 187 (18B) (19F) (1A3) 1A9 (1B1)

(1BD) 1CF (1D7) (1DB) 1E7 (1F3) 1F5 (1F9)

Пример: Второй непримитивный полином степени 8 - (139) в шестнадцатеричном виде. Целое шестнадцатеричное число эквивалентно 1 0011 1001 в двоичном виде (обратите внимание, что мы должны сохранить только 9 битов). Соответствующий полином - x⁸ + x⁵ + x⁴ + x³ + 1.