Информационная безопасность и защита информации: Конспект лекций. Будко В.Н. - 77 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

S(x) = K
4
<K
4
+ K
3
><K
3
+ K
2
><K
4
+ K
2
+ K
1
><K
3
+ K
1
+ K
0
><K
2
+ K
0
>K
1
K
0
(3)
Тот же самый результат, но заметно проще и обобщённее получим на языке многочленов.
На вход поступает слово (многочлен):
K(x) = K
4
*x
4
+ K
3
*x
3
+ K
2
*x
2
+ K
1
*x
1
+ K
0
, где K
i
= {0, 1}, ‘+’ – сумма по модулю 2.
Это слово умножается на многочлен, единичные биты которого определяются только
теми сигналами с регистра, какие подаются на сумматоры. Так как на первое звено
регистра подаётся старший бит входного слова , то нумеруем сигналы регистра (биты
множителя ) снизу вверх, как показано на рисунке 3.
На сумматоры подаются только биты номер 0, 2, 3. Следовательно , многочлен будет
иметь вид:
g(x) = 1*x
3
+ 1*x
2
+ 0*x + 1 = x
3
+ x
2
+ 1.
Итак:
(K
4
*x
4
+ K
3
*x
3
+ K
2
*x
2
+ K
1
*x
1
+ K
0
)*(x
3
+ x
2
+ 1) = (K
4
*x
7
+ K
3
*x
6
+ K
2
*x
5
+ K
1
*x
4
+ K
0*
x
3
)
+ (K
4
*x
6
+ K
3
*x
5
+ K
2
*x
4
+ K
1
*x
3
+ K
0*
x
2
) + (K
4
*x
4
+ K
3
*x
3
+ K
2
*x
2
+ K
1
*x
1
+ K
0
) = K
4
*x
7
+
(K
3
+ K
4
)*x
6
+ (K
2
+ K
3
)*x
5
+ (K
1
+ K
2
+ K
4
)*x
4
+ (K
0
+ K
1
+ K
3
)*x
3
+ (K
0
+ K
2
)*x
2
+ K
1
*x + K
0
= S(x) (5)
Выражение (5) совпадает с (3).
Итак, вообще: выходное слово есть произведение входного слова (многочлена (4)) и
многочлена x
3
+ x
2
+ 1 = g(x).
S(x) = K(x)*g(x).
Теперь рассмотрим схему на рисунке 4.
В этой схеме многочлен L(x) есть частное от деления многочлена входного слова S(x) на
многочлен g(x) = x
3
+ x
2
+ 1:
L(x) =
S(x)
g(x)
(8).
Это нетрудно увидеть, проведя анализ рисунка 4 подобно анализу рисунка 3. Интереснее
убедиться в следующем. Подадим на вход схемы с рис.4 слово с выхода схемы с рис.3.
тогда подставляя (6) в (8) получим:
L(x) = K(x).
+
+
1
2
3 
S(x) = K4K1K0 (3)
Тот же самый результат, но заметно проще и обобщённее получим на языке многочленов.
На вход поступает слово (многочлен):
K(x) = K4*x4 + K3*x3 + K2*x2 + K1*x1 + K0 , где Ki = {0, 1}, ‘+’ – сумма по модулю 2.
Это слово умножается на многочлен, единичные биты которого определяются только
теми сигналами с регистра, какие подаются на сумматоры. Так как на первое звено
регистра подаётся старший бит входного слова, то нумеруем сигналы регистра (биты
множителя) снизу вверх, как показано на рисунке 3.
На сумматоры подаются только биты номер 0, 2, 3. Следовательно, многочлен будет
иметь вид:
g(x) = 1*x3 + 1*x2 + 0*x + 1 = x3 + x2 + 1.
Итак:
(K4*x4 + K3*x3 + K2*x2 + K1*x1 + K0)*(x3 + x2 + 1) = (K4*x7 + K3*x6 + K2*x5 + K1*x4 + K0* x3)
+ (K4*x6 + K3*x5 + K2*x4 + K1*x3 + K0* x2) + (K4*x4 + K3*x3 + K2*x2 + K1*x1 + K0) = K4*x7 +
(K3 + K4)*x6 + (K2 + K3)*x5 + (K1 + K2 + K4)*x4 + (K0 + K1 + K3)*x3 + (K0 + K2)*x2 + K1*x + K0
= S(x)               (5)
Выражение (5) совпадает с (3).
Итак, вообще: выходное слово есть произведение входного слова (многочлена (4)) и
многочлена x3 + x2 + 1 = g(x).
S(x) = K(x)*g(x).
Теперь рассмотрим схему на рисунке 4.


               +

                          1

               +

                          2



                          3


В этой схеме многочлен L(x) есть частное от деления многочлена входного слова S(x) на
многочлен g(x) = x3 + x2 + 1:
       S(x)
L(x) = g(x) (8).

Это нетрудно увидеть, проведя анализ рисунка 4 подобно анализу рисунка 3. Интереснее
убедиться в следующем. Подадим на вход схемы с рис.4 слово с выхода схемы с рис.3.
тогда подставляя (6) в (8) получим:
L(x) = K(x).

Страницы