Блочный шифр Skipjack

Размещено на http://allbest.ru

Министерство образования и науки Кыргызской Республики

Министерство образования и науки РФ

Государственное образовательное учреждение высшего профессионального образования

Кыргызско-Российский Славянский университет

Естественно-технический факультет

Кафедра прикладной математики и информатики

РЕФЕРАТ

по кодирование и защита информации

на тему: Блочный шифр Skipjack

Выполнил: Маннанов М.С

Проверила: Красниченко Л.С

Бишкек-2020



План

Введение

История Skipjack

Описание

Криптоанализ

Алгоритм шифрования Skipjack

Дешифрование

Программная реализация

Литература



Введение

Skipjack -- блочный шифр, разработанный Агентством национальной безопасности США.

Изначально этот шифр был предназначен для использования в чипе Clipper.

Впоследствии алгоритм был рассекречен и теперь предоставляет уникальный взгляд правительственных спецслужб на проекты шифров.



История Skipjack

Skipjack был предложен как закрытый алгоритм шифрования, финансируемый правительством США. Шифр был предназначен для использования в чипе Clipper, встроенном в защищённое оборудование. Skipjack использовался только для шифрования, депонирование ключа в уполномоченные органы -- наиболее обсуждаемый аспект использования шифра -- достигалось за счёт отдельного механизма, называемого Law Enforcement Access Field (LEAF).

Изначально проект был засекречен и по этой причине был расценен с огромным подозрением в обществе криптографии. Шифр был опубликован 24 июня 1998 года.

Для повышения общественного доверия были призваны несколько академических исследователей (не из правительства), чтобы оценить алгоритм.

Исследователи не нашли проблем ни с алгоритмом непосредственно, ни с процессом оценки. Более того, их отчёт пролил некоторый свет на историю и развитие Skipjack:

Skipjack -- один из семейства шифров, разработанных в 1980 г. как часть набора алгоритмов «Type I» Агентства Национальной Безопасности США SKIPJACK был разработан с применением элементов и методов с более чем 40-летней историей.

Многие из методов связаны с работами, которые были оценены некоторыми из наиболее опытных и известных экспертов в мире комбинаторики и абстрактной алгебры. Примерная дата задумки SKIPJACK -- около 1980, а его первичная реализация -- 1987.



Описание

Skipjack использовал 80-битовый ключ для шифрования/дешифрования 64-битовых блоков данных. Это несбалансированная Сеть Фейстеля с 32 раундами.

Алгоритм был специально разработан, чтобы занять место DES.

Криптоанализ

Эли Бихам и Ади Шамир произвели криптографическую атаку против 16 из 32 раундов в течение одного дня после рассекречивания алгоритма.

Вместе с Алексом Бирюковым они, используя невозможный дифференциальный криптоанализ, всего в течение нескольких месяцев раскрыли 31 из 32 его раундов.

Позже были опубликованы статьи атакующие 28 раундов шифра с использованием усеченных дифференциалов.

В 2002 году Рафаэлем Фаном была опубликована статья, анализирующая возможные атаки на полные 32 раунда.

Позднее, в 2009 году, в статье, соавтором которой тоже являлся Фан, указано, что на тот момент не существовало атаки на полный алгоритм шифра Skipjack.

Алгоритм шифрования Skipjack

Данный алгоритм шифрования - блочный. В его работе используется 10-байтный ключ шифрования и входной блок символов размером 8 байт. В процессе шифрования данные разбиваются на 4 слова(по 2 байта каждое).

Слова обозначаются w₁, w₂, w_3, w₄(w₁ - старшие 2 байта входного блока).

Далее выполняются 32 раунда преобразования слов одной из функций - A или B[1].

Приведем пошаговое описание алгоритма функции A и обобщенные правила преобразований в функциях A и B.

Рисунок 1. Функция A

Пошаговое описание алгоритма функции A:

1. Выполнить операцию G над w₁.

2. Применить операцию XOR к результату предыдущего шага и значению w₄.

3. Присвоить w₁ результат применения операции XOR к результату шага 2 и текущему значению счетчика.

4. Присвоить w₄ текущее значение w₃.

5. Присвоить w₃ текущее значение w₂.

6. Присвоить w₂ результат, полученный на шаге 1.

7. Увеличить значение счётчика на 1.

Рисунок 2. Функция B.



Обобщенные правила преобразований функции A:

w₁^k+1=G^k(w₁^k)+w₄^k+счетчик^k

w₂^k+1= G^k(w₁^k)

w₃^k+1= w₂^k

w₄^k+1=w₃^k

Обобщенные правила преобразований функции B:

w₁^k+1= w₄^k

w₂^k+1= G^k(w₁^k)

w₃^k+1= w₁^k+w₂^k+счетчик^k

w₄^k+1=w₃^k

Здесь и далее k - номер раунда алгоритма.

Операция G представляет собой четырехраундовую сеть Фейстеля[1]:

Рисунок 3. Функция G.

Здесь cv_4k+n= K(4*k+n (mod 10)). K - ключ шифрования.

F - замещение входящего байта согласно F-таблице. В ней номер строки - старшие 4 бита входного байта(индексация начинается с нуля), номер столбца - младшие 4 бита.

Таблица 1.

F-таблица

A3

D7

09

83

F8

48

F6

F4

B3

21

15

78

99

B1

AF

F9

E7

2D

4D

8A

CE

4C

CA

2E

52

95

D9

1E

4E

38

44

28

0A

DF

02

A0

17

F1

60

68

12

B7

7A

C3

E9

FA

3D

53

96

84

6B

BA

F2

63

9A

19

7C

AE

E5

F5

F7

16

6A

A2

39

B6

7B

0F

C1

93

81

1B

EE

B4

1A

EA

D0

91

2F

B8

55

B9

DA

85

3F

41

BF

E0

5A

58

80

5F

66

0B

D8

90

35

D5

C0

A7

33

06

65

69

45

00

94

56

6D

98

9B

76

97

FC

B2

C2

B0

FE

DB

20

E1

EB

D6

E4

DD

47

4A

1D

42

ED

9E

6E

49

3C

CD

43

27

D2

07

D4

DE

C7

67

18

89

CB

30

1F

8D

C6

8F

AA

C8

74

DC

C9

5D

5C

31

A4

70

88

61

2C

9F

0D

2B

87

50

82

54

64

26

7D

03

40

34

4B

1C

73

D1

C4

FD

3B

CC

FB

7F

AB

E6

3E

5B

A5

AD

04

23

9C

14

51

22

F0

29

79

71

7E

FF

8C

0E

E2

0C

EF

BC

72

75

6F

37

A1

EC

D3

8E

62

8B

86

10

E8

08

77

11

BE

92

4F

24

C5

32

36

9D

CF

F3

A6

BB

AC

5E

6C

A9

13

57

25

B5

E3

BD

A8

3A

01

05

59

2A

46

На вход подаются , 1<=i<=4, счетчик устанавливается в 1, k=0. Для шифрования сообщения 8 раз выполняется операция A, затем - 8 раз B, 8 раз - A и 8 раз B. шифрование программный ключ криптоанализ

После каждого выполнения функции A или B счётчик увеличивается на 1. На выходе имеем , 1<=i<=4, k =32.

Дешифрование

Дешифрование осуществляется применением в обратном порядке функций, обратных к A и B, значение счётчика на первом шаге устанавливается в 32.

Обобщенные правила преобразований функции A^-1:

w₁^k-1=[G^k-1]^-1(w₂^k)

w₂^k-1= w₃^k

w₃^k-1= w₄^k

w₄^k-1=w₁^k+w₂^k+счетчик^k-1

Обобщенные правила преобразований функции B^-1:

w₁^k-1= [G^k-1]^-1(w₂^k)

w₂^k-1= [G^k-1]^-1(w₂^k) +w₃^k+счетчик^k-1

w₃^k-1= w₄^k

w₄^k-1=w₁^k

Рисунок 4. Функция G^-1.

На вход подаются , 1<=i<=4, счетчик устанавливается в 32, k=0. Сначала 8 раз выполняется операция B^-1, затем - 8 раз A^-1, 8 раз - B^-1 и 8 раз A^-1. После каждого выполнения функции A^-1 или B^-1 счётчик уменьшается на 1. На выходе имеем , 1<=i<=4, k =0.

Программная реализация

В ходе работы алгоритм был реализован в виде программного продукта, позволяющего шифровать и дешифровать исходный текст по введенному ключу.

1/// skipjack.cpp - modified by Wei Dai from Paulo Barreto's skipjack32.c,

2/// which is public domain according to his web site.

3

4 #include "pch.h"

5

6 #ifndef CRYPTOPP_IMPORTS

7

8 #include "skipjack.h"

9

10 /*

11 * Optimized implementation of SKIPJACK algorithm

12 *

13 * originally written by Panu Rissanen <bande@lut.fi> 1998.06.24

14 * optimized by Mark Tillotson <markt@chaos.org.uk> 1998.06.25

15 * optimized by Paulo Barreto <pbarreto@nw.com.br> 1998.06.30

16 */

17

18 NAMESPACE_BEGIN(CryptoPP)

19

20 /**

21 * The F-table byte permutation (see description of the G-box permutation)

22 */

23 const byte SKIPJACK::Base::fTable[256] = {

24

0xa3,0xd7,0x09,0x83,0xf8,0x48,0xf6,0xf4,0xb3,0x21,0x15,0x78,0x99,0xb1,0xaf,0xf9,

25 0xe7,0x2d,0x4d,0x8a,0xce,0x4c,0xca,0x2e,0x52,0x95,0xd9,0x1e,0x4e,0x38,0x44,0x28,

26 0x0a,0xdf,0x02,0xa0,0x17,0xf1,0x60,0x68,0x12,0xb7,0x7a,0xc3,0xe9,0xfa,0x3d,0x53,

27 0x96,0x84,0x6b,0xba,0xf2,0x63,0x9a,0x19,0x7c,0xae,0xe5,0xf5,0xf7,0x16,0x6a,0xa2,

28 0x39,0xb6,0x7b,0x0f,0xc1,0x93,0x81,0x1b,0xee,0xb4,0x1a,0xea,0xd0,0x91,0x2f,0xb8,

29 0x55,0xb9,0xda,0x85,0x3f,0x41,0xbf,0xe0,0x5a,0x58,0x80,0x5f,0x66,0x0b,0xd8,0x90,

30 0x35,0xd5,0xc0,0xa7,0x33,0x06,0x65,0x69,0x45,0x00,0x94,0x56,0x6d,0x98,0x9b,0x76,

31 0x97,0xfc,0xb2,0xc2,0xb0,0xfe,0xdb,0x20,0xe1,0xeb,0xd6,0xe4,0xdd,0x47,0x4a,0x1d,

32 0x42,0xed,0x9e,0x6e,0x49,0x3c,0xcd,0x43,0x27,0xd2,0x07,0xd4,0xde,0xc7,0x67,0x18,

33 0x89,0xcb,0x30,0x1f,0x8d,0xc6,0x8f,0xaa,0xc8,0x74,0xdc,0xc9,0x5d,0x5c,0x31,0xa4,

34 0x70,0x88,0x61,0x2c,0x9f,0x0d,0x2b,0x87,0x50,0x82,0x54,0x64,0x26,0x7d,0x03,0x40,

35 0x34,0x4b,0x1c,0x73,0xd1,0xc4,0xfd,0x3b,0xcc,0xfb,0x7f,0xab,0xe6,0x3e,0x5b,0xa5,

36 0xad,0x04,0x23,0x9c,0x14,0x51,0x22,0xf0,0x29,0x79,0x71,0x7e,0xff,0x8c,0x0e,0xe2,

37 0x0c,0xef,0xbc,0x72,0x75,0x6f,0x37,0xa1,0xec,0xd3,0x8e,0x62,0x8b,0x86,0x10,0xe8,

38 0x08,0x77,0x11,0xbe,0x92,0x4f,0x24,0xc5,0x32,0x36,0x9d,0xcf,0xf3,0xa6,0xbb,0xac,

39 0x5e,0x6c,0xa9,0x13,0x57,0x25,0xb5,0xe3,0xbd,0xa8,0x3a,0x01,0x05,0x59,0x2a,0x46

40 };

41

42 /**

43 * The key-dependent permutation G on V^16 is a four-round Feistel network.

44 * The round function is a fixed byte-substitution table (permutation on V^8),

45 * the F-table. Each round of G incorporates a single byte from the key.

46 */

47 #define g(tab, w, i, j, k, l) \

48 { \

49 w ^= (word)tab[i*256 + (w & 0xff)] << 8; \

50 w ^= (word)tab[j*256 + (w >> 8)]; \

51 w ^= (word)tab[k*256 + (w & 0xff)] << 8; \

52 w ^= (word)tab[l*256 + (w >> 8)]; \

53 }

54

55 #define g0(tab, w) g(tab, w, 0, 1, 2, 3)

56 #define g1(tab, w) g(tab, w, 4, 5, 6, 7)

57 #define g2(tab, w) g(tab, w, 8, 9, 0, 1)

58 #define g3(tab, w) g(tab, w, 2, 3, 4, 5)

59 #define g4(tab, w) g(tab, w, 6, 7, 8, 9)

60

61 /**

62 * The inverse of the G permutation.

63 */

64 #define h(tab, w, i, j, k, l) \

65 { \

66 w ^= (word)tab[l*256 + (w >> 8)]; \

67 w ^= (word)tab[k*256 + (w & 0xff)] << 8; \

68 w ^= (word)tab[j*256 + (w >> 8)]; \

69 w ^= (word)tab[i*256 + (w & 0xff)] << 8; \

70 }

71

72 #define h0(tab, w) h(tab, w, 0, 1, 2, 3)

73 #define h1(tab, w) h(tab, w, 4, 5, 6, 7)

74 #define h2(tab, w) h(tab, w, 8, 9, 0, 1)

75 #define h3(tab, w) h(tab, w, 2, 3, 4, 5)

76 #define h4(tab, w) h(tab, w, 6, 7, 8, 9)

77

78 /**

79 * Preprocess a user key into a table to save an XOR at each F-table access.

80 */

81 void SKIPJACK::Base::UncheckedSetKey(const byte *key, unsigned int length, const NameValuePairs &)

82 {

83 AssertValidKeyLength(length);

84

85 /* tab[i][c] = fTable[c ^ key[i]] */

86 int i;

87 for (i = 0; i < 10; i++) {

88 byte *t = tab+i*256, k = key[9-i];

89 int c;

90 for (c = 0; c < 256; c++) {

91 t[c] = fTable[c ^ k];

92 }

93 }

94 }

95

96 typedef BlockGetAndPut<word16, LittleEndian> Block;

97

98 /**

99 * Encrypt a single block of data.

100 */

101 void SKIPJACK::Enc::ProcessAndXorBlock(const byte *inBlock, const byte *xorBlock, byte *outBlock) const

102 {

103 word16 w1, w2, w3, w4;

104 Block::Get(inBlock)(w4)(w3)(w2)(w1);

105

106 /* stepping rule A: */

107 g0(tab, w1); w4 ^= w1 ^ 1;

108 g1(tab, w4); w3 ^= w4 ^ 2;

109 g2(tab, w3); w2 ^= w3 ^ 3;

110 g3(tab, w2); w1 ^= w2 ^ 4;

111 g4(tab, w1); w4 ^= w1 ^ 5;

112 g0(tab, w4); w3 ^= w4 ^ 6;

113 g1(tab, w3); w2 ^= w3 ^ 7;

114 g2(tab, w2); w1 ^= w2 ^ 8;

115

116 /* stepping rule B: */

117 w2 ^= w1 ^ 9; g3(tab, w1);

118 w1 ^= w4 ^ 10; g4(tab, w4);

119 w4 ^= w3 ^ 11; g0(tab, w3);

120 w3 ^= w2 ^ 12; g1(tab, w2);

121 w2 ^= w1 ^ 13; g2(tab, w1);

122 w1 ^= w4 ^ 14; g3(tab, w4);

123 w4 ^= w3 ^ 15; g4(tab, w3);

124 w3 ^= w2 ^ 16; g0(tab, w2);

125

126 /* stepping rule A: */

127 g1(tab, w1); w4 ^= w1 ^ 17;

128 g2(tab, w4); w3 ^= w4 ^ 18;

129 g3(tab, w3); w2 ^= w3 ^ 19;

130 g4(tab, w2); w1 ^= w2 ^ 20;

131 g0(tab, w1); w4 ^= w1 ^ 21;

132 g1(tab, w4); w3 ^= w4 ^ 22;

133 g2(tab, w3); w2 ^= w3 ^ 23;

134 g3(tab, w2); w1 ^= w2 ^ 24;

135

136 /* stepping rule B: */

137 w2 ^= w1 ^ 25; g4(tab, w1);

138 w1 ^= w4 ^ 26; g0(tab, w4);

139 w4 ^= w3 ^ 27; g1(tab, w3);

140 w3 ^= w2 ^ 28; g2(tab, w2);

141 w2 ^= w1 ^ 29; g3(tab, w1);

142 w1 ^= w4 ^ 30; g4(tab, w4);

143 w4 ^= w3 ^ 31; g0(tab, w3);

144 w3 ^= w2 ^ 32; g1(tab, w2);

145

146 Block::Put(xorBlock, outBlock)(w4)(w3)(w2)(w1);

147 }

148

149 /**

150 * Decrypt a single block of data.

151 */

152 void SKIPJACK::Dec::ProcessAndXorBlock(const byte *inBlock, const byte *xorBlock, byte *outBlock) const

153 {

154 word16 w1, w2, w3, w4;

155 Block::Get(inBlock)(w4)(w3)(w2)(w1);

156

157 /* stepping rule A: */

158 h1(tab, w2); w3 ^= w2 ^ 32;

159 h0(tab, w3); w4 ^= w3 ^ 31;

160 h4(tab, w4); w1 ^= w4 ^ 30;

161 h3(tab, w1); w2 ^= w1 ^ 29;

162 h2(tab, w2); w3 ^= w2 ^ 28;

163 h1(tab, w3); w4 ^= w3 ^ 27;

164 h0(tab, w4); w1 ^= w4 ^ 26;

165 h4(tab, w1); w2 ^= w1 ^ 25;

166

167 /* stepping rule B: */

168 w1 ^= w2 ^ 24; h3(tab, w2);

169 w2 ^= w3 ^ 23; h2(tab, w3);

170 w3 ^= w4 ^ 22; h1(tab, w4);

171 w4 ^= w1 ^ 21; h0(tab, w1);

172 w1 ^= w2 ^ 20; h4(tab, w2);

173 w2 ^= w3 ^ 19; h3(tab, w3);

174 w3 ^= w4 ^ 18; h2(tab, w4);

175 w4 ^= w1 ^ 17; h1(tab, w1);

176

177 /* stepping rule A: */

178 h0(tab, w2); w3 ^= w2 ^ 16;

179 h4(tab, w3); w4 ^= w3 ^ 15;

180 h3(tab, w4); w1 ^= w4 ^ 14;

181 h2(tab, w1); w2 ^= w1 ^ 13;

182 h1(tab, w2); w3 ^= w2 ^ 12;

183 h0(tab, w3); w4 ^= w3 ^ 11;

184 h4(tab, w4); w1 ^= w4 ^ 10;

185 h3(tab, w1); w2 ^= w1 ^ 9;

186

187 /* stepping rule B: */

188 w1 ^= w2 ^ 8; h2(tab, w2);

189 w2 ^= w3 ^ 7; h1(tab, w3);

190 w3 ^= w4 ^ 6; h0(tab, w4);

191 w4 ^= w1 ^ 5; h4(tab, w1);

192 w1 ^= w2 ^ 4; h3(tab, w2);

193 w2 ^= w3 ^ 3; h2(tab, w3);

194 w3 ^= w4 ^ 2; h1(tab, w4);

195 w4 ^= w1 ^ 1; h0(tab, w1);

196

197 Block::Put(xorBlock, outBlock)(w4)(w3)(w2)(w1);

198 }

199

200 NAMESPACE_END

201

202 #endif



Литература

1. Biham, E., Biryukov, A., Shamir, A. (1999). Cryptanalysis of Skipjack reduced to 31 rounds using impossible differentials. EUROCRYPT 1999, pp12-23.

2. E.F.Brickell, D.E.Denning, S.T.Kent, D.P.Mahler, W.Tuchman, "SKIPJACK Review ", Interim Report, July 28, (1993), 8 pages. Available at: http://www.cs.georgetown.edu/~denning/crypto/clipper/SKIPJACK.txt

3. L.R.Knudsen, M.J.B. Robshaw, D. Wagner, «Truncated differentials and Skipjack», CRYPTO 1999.

4. L.Granboulan, «Flaws in differential cryptanalysis of Skipjack», FSE 2001.

5. R.Chung-Wei Phan, «Cryptanalysis of full Skipjack block cipher», Electronics Letters, Volume 38, Issue 2, p. 69--71, 2002.

Размещено на Allbest.ru

...