XI Международная студенческая научная конференция Студенческий научный форум - 2019
Генерация и исследование псевдослучайных последовательностей. Реорганизация потоков шифрования данных
КомментарииПолная версия работы доступна во вкладке "Файлы работы" в формате PDF
Генератор псевдослучайных последовательностей - алгоритм порождающий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению[1].
Строго говоря, эти генераторы не являются криптографическими, поскольку их выход предсказуем, но при соблюдении определенных условий случайная последовательность бит на их выходе выглядит случайно, т.е. удовлетворяет статистическим тестам на случайность. Федеральный американский стандарт FIPS 140-1 определяет четыре статистических теста на случайность: блочный тест, тест длин серий, монобитный тест и тест серий. Сначала задаются границы для удовлетворенных значений статистических параметров для этих тестов. После битовая последовательность, получаемая из генератора, длиной 2000 бит, поддается каждому из четырех приведенных тестов. Считается, что генератор не прошел весь комплекс проверок, если один из тестов не пройден.
Монобитный тест. Состоит в подсчете количества нулей и единиц на отрезке последовательности определенной длины.
Блочный тест. Последовательность разбивается на блоки длиной m бит. Тест основан на том, что в идеальной случайной последовательности вероятность всех блоков одинакова.
Тест длин серий. Определяет число вхождений серий одинаковых битов различной длины. Алгоритм вычисления длины битовых блоков основан на том, что число 2n-1 содержит n единичных битов.
Тест серий. Находятся все серии битов – непрерывные последовательности одинаковых битов – и их распределение сравнивается с ожидаемым распределением таких серий для случайной последовательности. Длина последовательности 100 и более бит[2].
Для примера будет осуществлена программная реализация регистра сдвига с линейной обратной связью (РСЛОС) и потокового шифра на его основе. Основная последовательность РСЛОС будет задаваться полиномом .
Для начала был записан произвольный код в текстовый файл ish.txt и сохранен. После был создан текстпрограммы с РСЛОС:
function[seq c]=LFSR(s,t)
n=length(s);
c(1,:)=s;
m=length(t);
for k=1:2^n-2;
b(1)=xor(s(t(1)), s(t(2)));
if m>2;
for i=1:m-2;
b(i+1)=xor(s(t(i+2)), b(i));
end
end
j=1:n-1;
s(n+1-j)=s(n-j);
s(1)=b(m-1);
c(k+1,:)=s;
end
seq=c(:,n)';
end
Текст программы шифрования:
clear
clc
s=textread('ish.txt','%c')
s=s';
s=str2double(s)
t=[20 3];
[seq c] =LFSR(s,t)
res = fopen('res.txt', 'w');
string=[seq{:}]
fwrite(res, string);
fclose(res);
В итоге результат выполненной работы был записан в новый текстовый файл res.txt :
Рисунок 1 ─ Результат
Использованные источники:
Коробейников А. Г, Ю.А.Гатчин. Математические основы криптологии. Учебное пособие. СПб: СПб ГУ ИТМО, 2004. – 106 с, илл.
М. А. Иванов, И. В. Чугунков. Глава 4. Методика оценки качества генераторов ПСП. // Теория, применение и оценка качества генераторов псевдослучайных последовательностей. — М.: КУДИЦ-ОБРАЗ, 2003 — 240 с. ISBN 5-93378-056-1