Введение
Основная идея поточного шифрования состоит в том, что каждый из последовательных знаков открытого текста подвергается своему преобразованию. В идеале разные знаки открытого текста подвергаются разным преобразованиям, т.о. преобразование, которому подвергаются знаки открытого текста, должно изменяться с каждым следующим моментом времени. Реализуется эта идея следующим образом. Некоторым образом получается последовательность знаков k1, k2, … , называемая ключевым потоком (keystream) или бегущим ключом (running key, RK). Затем каждый знак xi открытого текста подвергается обратимому преобразованию, зависящему от ki – соответствующего знака ключевого потока. Хотя подавляющее большинство существующих шифров с секретным ключом с определенностью могут быть отнесены или к поточным или к блочным шифрам, теоретически граница между этими классами остается довольно размытой. Так, например, допускается использование алгоритмов блочного шифрования в режиме поточного шифрования (например, режимы CBF и OFB для алгоритма DES или режим гаммирования для алгоритма ГОСТ 28147-89). Как крайний случай любой блочный шифр можно рассматривать как подстановочный поточный шифр, использующий знаки алфавита большой мощности. Например, алгоритмы DES и ГОСТ 28147-89 – подстановочные шифры над алфавитом мощности 264 1,8·1019. Кроме того, известны поточные шифры, построенные на основе криптографических алгоритмов с открытым ключом.
Поточные шифры могут быть очень быстрыми в работе, в общем случае они намного быстрее блочных шифров. Поскольку шифрующая последовательность часто может генерироваться независимо от открытого текста или шифртекста, такие генераторы имеют преимущество в том, что шифрпоследовательность может вырабатываться до процесса шифрования или расшифрования, на который остается лишь единственная легкая операция наложения.
Рисунок 2. Первый регистр
Рисунок 1. Общая схема
Алгоритм основан на операции исключающего или. Разберем его на рисунке 1 – общей схеме и рисунке 2, в котором изображен первый регистр.
Мы применим нашу операцию в отношении нулевого, первого и последнего битов. Затем, сдвигаем все биты на один разряд вправо и полученный в предыдущем действии бит вставим в нулевой в регистре. Таким образом, выдвинутый бит из регистра будет являться выходным т. е в формуле (1) – это «a1».
Рисунок 3. Второй регистр
Аналогично работают схемы на рисунке 3, в котором выходным битом будет являться «а2» и рисунке 4 – «а3».
Затем исходя из формулы (1) мы выбираем бит какого из регистров включать в последовательность.
 (1)
В результате так образуется последовательность из битов «а», которая будет накладываться на открытый текст.
Рисунок 4. Общая блок-схема
Б
лок-схемы
Рисунок 5. Блок-схема алгоритма Берлекэмпа-Месси
Инструкция по работе программы
При запуске программы автоматически генерируется последовательность из 1000 элементов. На экране вы видите массив битов и вычисленную линейную сложность (62). Также выводит количество нулей и единиц, их максимальные длины и частоту появления этих длин.
Рисунок 6. Результат из последовательности.
Р
езультат работы
Рисунок 7. Линейная сложность, максимальные длины и частоты
Реализованная программа работает как мы и предполагали и генерирует последовательность из битов. Вычисленная программно линейная сложность (62) практически совпадает с вычисленной вручную равной 63. |
Скачать 204.89 Kb.