Научная литература
booksshare.net -> Добавить материал -> Криптография -> Алферов А.П. -> "Основы криптографии Учебное пособие" -> 67

Основы криптографии Учебное пособие - Алферов А.П.

Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии Учебное пособие — М.: Гелиос АРВ, 2002. — 480 c.
ISBN 5-85438-025-0
Скачать (прямая ссылка): osnovikriptografii2005.djvu
Предыдущая << 1 .. 61 62 63 64 65 66 < 67 > 68 69 70 71 72 73 .. 126 >> Следующая

і юточные системы шифрования

Пусть ?{,...,?т— базис поля Q, рассматриваемого как

векторное пространство над полем P. Тогда последняя система эквивалентна следующей системе линейных уравнений от т переменных над полем P :

т

Z AW *

xS-trq (Oj-Ss) = OCj,

‘ S=1

J = 1, к.

Покажем, что ранг этой системы линейных уравнений равен к. Предположим, что между строками матрицы системы существует нетривиальное линейное соотношение с коэффициентами С|,...,с*.:

Yct 'trf (Qt -?s) = ^ S = I,т. t=і

Тогда для любого значения s = I5 m выполняется соотношение

‘rf (es-Ycf0t) = °-

t=I

к

Обозначим Z = ^jct-Bt . Тогда для любого набора t=\

получаем равенство

259
Глава 9

т т

trq O-JX'^) = 0’

5=1

Qm

из которого следует, что tr?j (z • х) = 0 для любого X є P .

Согласно лемме 1, полученное равенство возможно только в случае, когда z = 0, что, в силу неприводимости многочлена F(x) и условия к <т, означает, что C1 =... = Ck = 0.

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

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

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

260
I юточные системы шифрования

§ 9.5. Алгоритм Берлекемпа — Месси

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

Любая периодическая последовательность может рассматриваться как линейная рекуррентная последовательность Поэтому для любой периодической последовательности существует некоторый линейный регистр сдвига, который Є€ гчрабатывает. Если элементы, образующие период последовательности, выбираются случайно, то степень минимального многочлена такой последовательности близка к величине ес периода. Поэтому линейная сложность может рассматриваться как характеристика сложности аналитического строенш псевдослучайной последовательности. Низкую линейнук сложность имеют слабые в криптографическом отношение последовательности. Вместе с тем высокая линейная сложность не гарантирует отсутствия других недостатков. Напри мер, для генерации последовательности, период которой име ет вид (О,О,...,ОД), требуется линейный регистр, длина которого совпадает с длиной периода этой последовательности однако ясно, что считать эту последовательность случайно? нельзя.

Эффективным методом нахождения линейного регистр* сдвига минимальной длины, генерирующего заданную после довательность, является алгоритм Берлекемпа — Месси. При ведем модификацию этого алгоритма, предложенную А. А. Нечаевым [Киг95].

Пусть P — некоторое поле, е — единица поля P . Обо

значим через и (о,/-і)=(и(0),...,1/(/-1)) начальный отрезої

26
Гпава 9

произвольной последовательности и элементов поля P. Будем говорить, что многочлен

W-I

G(Jt) = хт - Ybj •xJ є Р[х]

J=О

вырабатывает отрезок u{o,l — l), если

т-1 __________

u(i + m)= Y,b j •«(/ + У), і = OJ - т-\,

J=о

то есть если данный отрезок последовательности является отрезком некоторой линейной рекуррентной последовательности с характеристическим многочленом G(x) .

Алгоритм Берлекемпа — Месси строит многочлен G(x)

наименьшей степени, вырабатывающий отрезок w(o,/-l). Приведем одну из многочисленных модификаций алгоритма со сложностью, оцениваемой величиной 6т2(1 + о(1)) операций поля P.

Определим операцию умножения последовательности на

п

многочлен. Для произвольного многочлена Н(х) = Hj • Xj

J=О

и последовательности v положим Н{х)-у = W9 где HO = ?bj-v(i + J), і> 0.

J=0

Будем говорить, что многочлен G(x) степени т вырабатывает 1>т знаков последовательности и, если выполняется равенство

262
I Юточные системы шифрования

G(x)-u = V = (0,...,0, v(l -m),...) ,
Предыдущая << 1 .. 61 62 63 64 65 66 < 67 > 68 69 70 71 72 73 .. 126 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed