Схемы с элементами памяти

Дополнительные возможности для усложнения ЛРП открывает использование в криптографических алгоритмах элементов памяти.

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

Пусть имеются три последовательности и массив памяти. Будем записывать элементы первой последовательности в память по адресам, которые определяются элементами второй последовательности. Элементы выходной последовательности получаются при считывании значений, хранящихся в массиве памяти, в соответствии с элементами третьей последовательности. Таким образом, первая последовательность определяет, какие знаки заносятся в память, вторая последовательность управляет процессом записи этих элементов в память, а третья – процессом считывания из памяти элементов выходной последовательности.

Рассмотрим частный случай, когда процессами записи и считывания управляет одна и та же последовательность.

Пусть и и v – последовательности над полем Р, а вы­ходная последовательность у вырабатывается с использова­нием q ячеек памяти R₀,...,R_q–1. Если R_j(i)–заполнение j-й ячейки памяти перед началом i-го такта работы схемы, то преобразование информации в i-м такте описывается фор­мулами

y(i)=R_v(i)(i),

если j ¹ v(i),

если j = v(i).

Таким образом, последовательность v определяет адреса, по которым в память записываются элементы последовательности и.

Рассмотрим вопрос о периодах выходных последовательностей генератора Макларена-Марсальи указанного типа.

Пусть последовательность и имеет период t, а адресная последовательность v принимает значения 0,1,...,q-1 и имеет период t. Начальное заполнение памяти R₀(0),...,R_q–1(0) выбирается произвольно.

Пусть i₀ – такое наименьшее натуральное число, что для любого kÎ{0,1,..., q–1} существует i Î{0,1,..., i₀} такое, что v(i)=k. Другими словами, через i₀ тактов работы схемы память будет заполнена только элементами последовательности и.

Теорема 6. Пусть t – период последовательности и, t – период последовательности v, причем (t,t)=1, t >t. Тогда для значения периода Т выходной последовательности у выполняется равенство Т=ts, где s=t/d и d£ е^q/e.