Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
і юточные системы шифрования
Пусть ?{,...,?т— базис поля 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),...) ,