The OpenNET Project / Index page

[ новости /+++ | форум | теги | ]



"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Версия для распечатки Пред. тема | След. тема
Форум Разговоры, обсуждение новостей
Исходное сообщение [ Отслеживать ]
Присылайте удачные настройки в раздел примеров файлов конфигурации на WIKI.opennet.ru.
. "Для ядра Linux 3.13 представлены патчи с улучшением генераци..." +/
Сообщение от pavlinux (ok), 19-Ноя-13, 22:38 
> Не факт. Я, конечно, ихсходников не читал, но предпологаю, что там вычисления
> по-модулю.  Кстати, если не лень, то можешь попробовать на множители
> пораскладывать. В каком многочлене будет выше наименьшая  степень множителя, тот
> сложнее анализировать. Если есть кто более сведующий в теории чисел,  
> то поправьте, если я ошибся.

Ну там примерно так объясняется


3.1.1 Analysis Without Input

When the input is set to zero, the mixing function is equivalent to an LFSR over GF(2^32) with
feedback polynomial Q(X) = α^3*(P(X) − 1) + 1, where α is the primitive element of GF(2^32)
corresponding to X defined by the CRC-32-IEEE 802.3 polynomial, and P(X) depends on the
size of the pool:

     input pool: P(X) = X^128 + X^103 + X^76 + X^51 + X^25 + X + 1
     output pool: P(X) = X^32 + X^26 + X^20 + X^14 + X^7 + X + 1.

The multiplication by α^3 is done by a lookup table, called twist-table in the source code.
The actual system slightly differs from what is stated in the comments of the source code.
First, the design of the mixing function is claimed to rely on a Twisted Generalized Feedback
Shift Register (TGFSR) as defined in [MK92]. However, TGFSRs are LFSRs on binary words
with a trinomial feedback polynomial whereas the mixing function uses a heptanomial. The
case of general polynomials on finite fields is treated in standard literature, such as [LN97].
Moreover, the maximal period, that is the primitivity of the feedback polynomial, seems to
have been ill understood, as the comments mention the primitivity for polynomials on GF(2),
whereas the primitivity must be checked on GF(232). This confusion is also repeated in [GPR06,
Definition 2.2].

Finally, the polynomial Q(X) = α^3*(P(X) − 1) + 1 is not primitive over GF(2^32), nor is it
even irreducible. Thus, the resulting LFSR does not achieve maximal period. The period is less
than 2^(92∗32) − 1, rather than the maximal value of 2^(128∗32) − 1, for the input pool,
and less than 2^(26∗32)−1 instead of 2^32∗32 − 1 for the output pool.

We do not believe these reduced periods can lead to practical attacks. However, Q(X) can be
made irreducible by changing just one feedback position:

   input pool: P(X) = X^128 + X^104 + X^76 + X^51 + X^25 + X + 1
   output pool: P(X) = X^32 + X^26 + X^19 + X^14 + X^7 + X + 1.

These modified polynomials have periods of (2^128∗32−1)/3 and (2^32∗32−1)/3, respectively.
A primitive polynomial can be easily achieved by using (α^i)*(P(X)−1)+1 with gcd(i,2^32−1) = 1,
for example for i = 1,2,4,7, . . ., and an adequate polynomial P(X). This would change the size
of the twist-table to 2^i elements. For instance, α^2*(X^32+X^26+X^23+X^14+X^7+X)+1 is primitive.
All these computations can be made using computational algebra systems like magma [BCP97].

Хотя в последнем примере, при 3-м члене 23-степень.

Ответить | Правка | Наверх | Cообщить модератору

Оглавление
Для ядра Linux 3.13 представлены патчи с улучшением генераци..., opennews, 19-Ноя-13, 11:53  [смотреть все]
Форумы | Темы | Пред. тема | След. тема



Партнёры:
PostgresPro
Inferno Solutions
Hosting by Hoster.ru
Хостинг:

Закладки на сайте
Проследить за страницей
Created 1996-2024 by Maxim Chirkov
Добавить, Поддержать, Вебмастеру