Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Криптографическая защита информации.rtf
Скачиваний:
3
Добавлен:
01.07.2025
Размер:
18 Мб
Скачать
☆

Построчное вращение матрицы

В ходе данной операции каждая строка матрицы данных, кроме первой, вращается (циклически сдвигается) влево на определенное число позиций, зависящее от номера строки и от размера блока данных:

, 1£i£4, 1£j£n.

Первая строка всегда остается на месте: С1 = 0, для нее приведенная выше формула существенно упрощается: z1j = y1j. Ниже в таблице приведены величины сдвига для строк матрицы со второй по четвертую в зависимости от числа столбцов n в матрице:

n

4

6

8

C2

1

1

1

C3

2

2

3

C4

3

3

4

Умножение на постоянную матрицу

Н а этом шаге матрица данных слева умножается на постоянную матрицу-циркулянт M:

X = M´X,

При выполнении матричного умножения операции сложения и умножения элементов обеих матриц выполняются в конечном поле GF(28). Матрица M является циркулянтом: каждая ее строка получается циклическим сдвигом предыдущей строки вправо на один элемент. Элементы матрицы выбраны таким образом, чтобы свести к минимуму трудоемкость операции умножения: в ней присутствуют лишь небольшие по значению числа 01, 02 и 03, половина элементов - единичные, т.е. реального умножения выполнять для них не требуется. Этим самым обеспечивается высокая эффективность возможных реализаций этой операции.

Следует добавить, что операция умножения в конечном поле GF(28) является достаточно трудоемкой в программной реализации и никаким образом не сводится к обычному арифметическому умножению. Если умножение двоичных чисел реализуется сдвигами и обычным арифметическим суммированием, то умножение полиномов над полем GF(2) - теми же сдвигами и побитовым суммированием по модулю 2. Однако в шифре Rijndael одним из множителей всегда является константа и размер операндов невелик - один байт. Это позволяет реализовать умножение на константу в поле GF(28) как замену, что существенно повышает эффективность программной реализации. Для каждого множителя-константы при этом требуется свой отдельный узел замен. Напротив, наиболее эффективной аппаратной реализацией этой операции является реализация в виде серии сдвигов и побитовых сложений по модулю два в соответствие с ее непосредственным определением.

Дешифрация

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

1. Ключевые элементы используются в порядке, обратном тому, в котором они используются при шифровании. Кроме того, все ключевые элементы, кроме первого и последнего, должны быть умножены слева на матрицу, обратную матрице M. Таким образом, если при шифровании используется следующая последовательность ключевых элементов

k1, k2, k3, ... , kR, kR+1,

то при дешифрации должна быть использована следующая последовательность элементов:

kR+1, M -1 kR, ... , M -1 k3, M -1 k2, k1.

2. На шаге побайтовой замены используется узел замен S-1 обратный тому, что применяется в процедуре шифрования S. Это означает, что каково бы ни было байтовое значение b, всегда справедливо следующее соотношение:

S -1[S[b]] = b.

Указанный узел замен S-1 представлен в следующей таблице:

x0

x1

x2

x3

x4

x5

x6

x7

x8

x9

xA

xB

xC

xD

xE

xF

0x

52

09

6a

d5

30

36

a5

38

bf

40

a3

9e

81

f3

d7

fb

1x

7c

e3

39

82

9b

2f

ff

87

34

8e

43

44

c4

de

e9

cb

2x

54

7b

94

32

a6

c2

23

3d

ee

4c

95

0b

42

fa

c3

4e

3x

08

2e

a1

66

28

d9

24

b2

76

5b

a2

49

6d

8b

d1

25

4x

72

f8

f6

64

86

68

98

16

d4

a4

5c

cc

5d

65

b6

92

5x

6c

70

48

50

fd

ed

b9

da

5e

15

46

57

a7

8d

9d

84

6x

90

d8

ab

00

8c

bc

d3

0a

f7

e4

58

05

b8

b3

45

06

7x

d0

2c

1e

8f

ca

3f

0f

02

c1

af

bd

03

01

13

8a

6b

8x

3a

91

11

41

4f

67

dc

ea

97

f2

cf

ce

f0

b4

e6

73

9x

96

ac

74

22

e7

ad

35

85

e2

f9

37

e8

1c

75

df

6e

Ax

47

f1

1a

71

1d

29

c5

89

6f

b7

62

0e

aa

18

be

1b

Bx

fc

56

3e

4b

c6

d2

79

20

9a

db

c0

fe

78

cd

5a

f4

Cx

1f

dd

a8

33

88

07

c7

31

b1

12

10

59

27

80

ec

5f

Dx

60

51

7f

a9

19

b5

4a

0d

2d

e5

7a

9f

93

c9

9c

ef

Ex

a0

e0

3b

4d

ae

2a

f5

b0

c8

eb

bb

3c

83

53

99

61

Fx

17

2b

04

7e

ba

77

d6

26

e1

69

14

63

55

21

0c

7d

3. На шаге построчного вращения матрицы данных осуществляется циклический сдвиг строк на то же самое количество элементов, что и при шифровании, но в обратную сторону - вправо. Либо, в силу свойств операции циклического сдвига, можно осуществить вращение строк матрицы в ту же сторону, что и при шифровании, т.е. влево, но на другое количество элементов, вычисляемое по следующей формуле:

Сi' = n - Ci, 2£i£4.

Константы циклического сдвига влево строк матрицы в процедуре дешифрования в зависимости от числа столбцов матрицы данных приведены в следующей ниже таблице:

n

4

6

8

C2’

3

5

7

C3’

2

4

5

C4’

1

3

4

На шаге умножения слева на постоянную матрицу используется матрица M -1, обратная используемой при шифровании матрице M:

Следует отметить, что умножение в конечном поле GF(28) на элементы матрицы M -1 с точки зрения вычислительных затрат является более трудоемкой операцией, чем умножение на элементы матрицы M. Кроме того, в обратной матрице присутствуют четыре различных элемента, тогда как в исходной - только три, что позволяло "сэкономить" одно умножение из четырех. Все сказанное приводит к тому, что при непосредственной реализации умножения в поле GF(28) модули дешифрования получаются заметно менее быстродействующими, чем модули шифрования. Однако, эта особенность не является настолько существенной, как может показаться на первый взгляд. Во-первых, в большинстве практических режимов использования шифра применяется только прямое преобразование (шифрование) - подобная ситуация имеет место при шифровании с использованием потоковых режимов (в том числе и при дешифрации), при выработке имитовставки (кода аутентификации), при выработке хэш-функции и при выработке массивов псевдослучайных данных. Во вторых, если умножение на константу в поле GF(28) реализовать как замену, различия в трудоемкости нивелируются.