s = P(yj = bj) = 1/2 + 2t–1 t.
Посчитав количество уравнений h, в которых Li = 0, мы можем вычислить условную вероятность
p* P zi ui |
h |
p 1 s h sm h |
|
. (*) |
p 1 s h sm h 1 p 1 |
s m h sh |
В было предложено два алгоритма: алгоритм A алгоритм B. В алгоритме A для каждого наблюдаемого символа вычисляется значение p*, а затем l позиций с наибольшими значениями (1–p*) используются для нахождения правильного начального состояния LFSR.
Алгоритм B является итерационным: в каждой итерации производится пересчет условных вероятностей (*) до сходимости, либо выполняется максимальное число итераций.
Данные алгоритмы хорошо работают, если LFSR содержит небольшое количество отводов, а при большом количестве отводов в LFSR эти алгоритмы терпят неудачу. Это происходит потому, что для LFSR с большим количеством отводов каждое уравнение проверки четности дает очень маленькую среднюю поправку и, следовательно, требуется много уравнений для достижения цели. Другими словами, максимальная вероятность корреляции p, которой могут оперировать алгоритмы, намного ниже, если LFSR содержит много отводов. Следовательно, для противостояния вышеописанным атакам, в поточных шифрах необходимо использовать полиномы обратных связей с большим весом.
Данные алгоритмы были улучшены. Были предложены алгоритмы нахождения уравнений проверки четности на основе матричного представления LFSR, линейного кодирования и деления полиномов.
Алгебраическая атака
Впервые алгебраическая атака была предложена в [43_Courtois] и называлась корреляционной атакой высокого порядка. Целью данной атаки является восстановление ключа путем решения системы нелинейных уравнений.
Алгебраическая атака выполняется в несколько этапов:
1.Составить систему нелинейных уравнений из элементов ключевого потока zi и начального состояния s0 LFSR.
2.Подставить имеющиеся биты ключевого потока в составленную систему уравнений.
3.Восстановить ключ, решая полученную систему уравнений.
Для алгебраических атак требуется меньшее количество ключевого потока, чем для корреляционных атак, но при этом они требуют больших временных затрат.
223