WEBVTT - This file was automatically generated by VIMEO

0
00:00:07.100 --> 00:00:10.900
In the previous video we looked at the specification of as

1
00:00:10.900 --> 00:00:13.300
 algorithm and detailed the

2
00:00:13.300 --> 00:00:15.600
 steps that compose each of its rounds.

3
00:00:16.500 --> 00:00:19.800
We saw that mixed columns and adron key

4
00:00:19.800 --> 00:00:22.300
 steps involve some arithmetic at the

5
00:00:22.300 --> 00:00:22.600
 bite level.

6
00:00:23.500 --> 00:00:26.300
In this video, we'll clarify this arithmetic.

7
00:00:27.400 --> 00:00:30.500
They would be some mathematics over polynomials, but no worries.

8
00:00:31.200 --> 00:00:34.400
We'll go through it step by step and we'll see

9
00:00:34.400 --> 00:00:35.800
 together plenty of examples.

10
00:00:37.700 --> 00:00:40.300
We all use arithmetic in our daily life

11
00:00:40.300 --> 00:00:43.200
 when we manage our money or when we

12
00:00:43.200 --> 00:00:43.900
 do shopping for example.

13
00:00:45.200 --> 00:00:48.900
These arithmetic involves real numbers and operations

14
00:00:48.900 --> 00:00:52.000
 like addition subtraction multiplication

15
00:00:51.400 --> 00:00:52.900
 or division.

16
00:00:53.500 --> 00:00:56.800
That we or our calculator or our

17
00:00:56.800 --> 00:00:59.300
 Excel sheet apply over these numbers.

18
00:01:00.800 --> 00:01:03.400
As inventors Richmond and Daemon use another

19
00:01:03.400 --> 00:01:05.800
 type of arithmetic for the bytes.

20
00:01:06.800 --> 00:01:10.200
These arithmetic is a bit different from the usual arithmetic

21
00:01:09.200 --> 00:01:12.400
 over real numbers. It is called

22
00:01:12.400 --> 00:01:14.400
 arithmetic over finite fields.

23
00:01:15.300 --> 00:01:18.700
Let's see its properties first before seeing

24
00:01:18.700 --> 00:01:19.200
 how it works.

25
00:01:22.600 --> 00:01:25.200
Three numbers is infinite. And this

26
00:01:25.200 --> 00:01:28.400
 is the first major difference with finite fields.

27
00:01:29.100 --> 00:01:32.000
The set of elements in finite Fields is finite.

28
00:01:32.800 --> 00:01:35.400
And gf2 to

29
00:01:35.400 --> 00:01:38.700
 the power of 8, which is one instance of finite Fields

30
00:01:38.700 --> 00:01:41.500
 is composed of two to the

31
00:01:41.500 --> 00:01:42.600
 power of 8 elements.

32
00:01:43.800 --> 00:01:46.900
2 to the power of 8 is 256 which

33
00:01:46.900 --> 00:01:49.600
 exactly corresponds to the number of values

34
00:01:49.600 --> 00:01:51.000
 that byte can take

35
00:01:53.500 --> 00:01:56.400
finite Fields have special property that

36
00:01:56.400 --> 00:01:59.800
 operations such as addition subtraction

37
00:01:59.800 --> 00:02:01.400
 multiplication or division.

38
00:02:02.100 --> 00:02:05.400
On elements always cause the result to remain

39
00:02:05.400 --> 00:02:06.100
 in that fit.

40
00:02:06.700 --> 00:02:09.400
So when we add multiply elements in

41
00:02:09.400 --> 00:02:10.800
 gf228.

42
00:02:11.600 --> 00:02:14.300
the result remains in gf228

43
00:02:15.300 --> 00:02:18.200
Which is exactly what we want when doing arithmetic on

44
00:02:18.200 --> 00:02:18.500
 bytes.

45
00:02:19.200 --> 00:02:22.200
We don't want when we add two bytes to obtain a value

46
00:02:22.200 --> 00:02:25.200
 that cannot be represented on a bite and can only be

47
00:02:25.200 --> 00:02:27.800
 represented on 16-bit Word.

48
00:02:28.500 --> 00:02:31.300
If this was not the case would have to worry about

49
00:02:31.300 --> 00:02:32.700
 overflow problems.

50
00:02:33.700 --> 00:02:37.200
So the fact that we have the finite set

51
00:02:36.200 --> 00:02:38.600
 of numbers.

52
00:02:39.600 --> 00:02:41.400
and the properties that

53
00:02:42.500 --> 00:02:43.500
the operations

54
00:02:44.700 --> 00:02:47.300
provide us members that remain in

55
00:02:47.300 --> 00:02:50.400
 the same field are the two interesting properties of

56
00:02:50.400 --> 00:02:51.300
 finite fields.

57
00:02:52.300 --> 00:02:55.500
Let's see how we map the bytes to these

58
00:02:55.500 --> 00:02:58.000
 elements of gf228.

59
00:02:59.400 --> 00:03:02.600
A bite B can be represented as a

60
00:03:02.600 --> 00:03:05.500
 bit string as you see here. We have

61
00:03:05.500 --> 00:03:08.400
 8 Bits going from B7 to b0.

62
00:03:09.300 --> 00:03:10.500
in gf28

63
00:03:11.200 --> 00:03:14.500
this bit string is a represented as

64
00:03:14.500 --> 00:03:15.500
 a polynomial.

65
00:03:16.500 --> 00:03:18.100
with binary coefficients

66
00:03:19.300 --> 00:03:22.000
this B7 B6 Etc all the way

67
00:03:22.200 --> 00:03:22.800
 to be zeros.

68
00:03:23.700 --> 00:03:27.000
And each of these B can

69
00:03:26.400 --> 00:03:29.500
 take the value 0 or 1 exactly like

70
00:03:29.500 --> 00:03:30.000
 a bit.

71
00:03:31.500 --> 00:03:32.300
So for example

72
00:03:33.400 --> 00:03:37.100
5A is written as the

73
00:03:36.100 --> 00:03:39.300
 speed string 0 1 0 1

74
00:03:39.300 --> 00:03:41.200
 1 0 1 0.

75
00:03:42.400 --> 00:03:46.600
it will be mapped to the following polynomial 0x7

76
00:03:45.600 --> 00:03:48.200
 plus 1 x 6

77
00:03:48.200 --> 00:03:51.300
 plus 0x5 plus 1 x 4

78
00:03:51.300 --> 00:03:54.300
 plus 1 x 3 plus 0 x 2 plus

79
00:03:54.300 --> 00:03:55.800
 1 X plus u

80
00:03:57.400 --> 00:04:01.200
the monomials with zero coefficients can

81
00:04:00.200 --> 00:04:02.000
 be removed.

82
00:04:02.800 --> 00:04:06.600
So this polynomial is exactly corresponds

83
00:04:05.600 --> 00:04:06.900
 to this.

84
00:04:07.600 --> 00:04:11.100
polynomial X6 plus X4 plus X3

85
00:04:10.100 --> 00:04:12.000
 plus X

86
00:04:13.800 --> 00:04:15.600
We provide two more examples.

87
00:04:16.400 --> 00:04:19.300
Feel free to stop the video and take your time to

88
00:04:19.300 --> 00:04:20.400
 check each of them.

89
00:04:22.400 --> 00:04:25.600
Each polynomial in gf28 is

90
00:04:25.600 --> 00:04:27.200
 of degree at most 7.

91
00:04:28.400 --> 00:04:31.500
For example the polynomial corresponding to

92
00:04:31.500 --> 00:04:34.700
 the value FF is exactly of

93
00:04:34.700 --> 00:04:35.600
 degree 7.

94
00:04:36.100 --> 00:04:40.100
As its largest non-zero monomial is X7.

95
00:04:41.200 --> 00:04:44.100
while the polynomial corresponding to

96
00:04:44.100 --> 00:04:47.900
 the value to C is of degree 5 as

97
00:04:47.900 --> 00:04:50.200
 you see we don't have coefficients for

98
00:04:51.800 --> 00:04:52.400
X6 and X7

99
00:04:53.700 --> 00:04:57.000
There is no purpose from defining the real

100
00:04:56.200 --> 00:04:59.200
 numbers if we don't Define how to

101
00:04:59.200 --> 00:04:59.700
 add.

102
00:05:00.800 --> 00:05:03.200
multiply subtract or divide

103
00:05:03.200 --> 00:05:03.400
 them

104
00:05:04.200 --> 00:05:08.400
Similarly, we need to Define how to do arithmetic

105
00:05:07.400 --> 00:05:10.900
 operations for the gf28

106
00:05:10.900 --> 00:05:11.300
 elements.

107
00:05:12.200 --> 00:05:13.200
Let's start with addition.

108
00:05:14.400 --> 00:05:16.500
to add elements in gf28

109
00:05:17.200 --> 00:05:19.700
we do addition of the polynomials.

110
00:05:20.400 --> 00:05:23.500
And then in the result, we replace every two

111
00:05:23.500 --> 00:05:24.300
 by zero.

112
00:05:25.300 --> 00:05:29.000
Why because as we said in the previous slide in

113
00:05:28.500 --> 00:05:31.900
 element of gf28 is polynomial with

114
00:05:31.900 --> 00:05:33.000
 binary coefficients.

115
00:05:33.600 --> 00:05:36.200
So coefficients take either 0 or

116
00:05:36.200 --> 00:05:39.200
 1 so we cannot have value 2

117
00:05:39.200 --> 00:05:41.900
 so we will replace it with zero.

118
00:05:42.500 --> 00:05:45.500
Because 2 and 0 have the same parity.

119
00:05:46.500 --> 00:05:49.000
Let's see an example of how we do

120
00:05:49.000 --> 00:05:49.500
 addition.

121
00:05:50.400 --> 00:05:53.900
So we'll take the previous bytes.

122
00:05:53.900 --> 00:05:57.400
 The previous values that we have seen 5A and

123
00:05:57.400 --> 00:05:57.700
 2C.

124
00:05:58.500 --> 00:06:01.600
So these are their corresponding polynomials.

125
00:06:02.800 --> 00:06:05.600
So to do the addition we need just need to add the

126
00:06:05.600 --> 00:06:08.700
 polynomials. So the polynomial corresponding to

127
00:06:08.700 --> 00:06:08.800
 the

128
00:06:09.800 --> 00:06:12.900
To the addition is the following X6 plus

129
00:06:12.900 --> 00:06:13.500
 X5.

130
00:06:14.200 --> 00:06:17.700
Let's X4 plus 2 X 3 because each

131
00:06:17.700 --> 00:06:20.300
 of 5A and

132
00:06:20.300 --> 00:06:23.200
 to CL has X3 plus X2.

133
00:06:24.200 --> 00:06:24.700
plus X

134
00:06:25.900 --> 00:06:28.500
and as we said the two will be

135
00:06:28.500 --> 00:06:31.500
 replaced by 0. So the monomial will

136
00:06:31.500 --> 00:06:34.500
 disappear from the result. So the result

137
00:06:34.500 --> 00:06:35.700
 is then is the

138
00:06:36.800 --> 00:06:39.300
following polynomial X6 plus

139
00:06:39.300 --> 00:06:42.400
 X5 plus X4 plus X2 plus

140
00:06:42.400 --> 00:06:42.700
 X.

141
00:06:43.700 --> 00:06:46.400
This is corresponding to the following bit string

142
00:06:46.400 --> 00:06:48.400
 0 1 1.

143
00:06:49.900 --> 00:06:53.200
0 1 1 0 which corresponds

144
00:06:52.200 --> 00:06:55.900
 to the value 76 so

145
00:06:55.900 --> 00:06:58.800
 5A plus 2C is

146
00:06:58.800 --> 00:07:00.300
 equal to 76.

147
00:07:02.200 --> 00:07:06.600
you might have noticed that actually this addition in gf28 is

148
00:07:06.600 --> 00:07:09.600
 actually actually just a bitwise xor

149
00:07:11.100 --> 00:07:14.500
because when we xor we do it component

150
00:07:14.500 --> 00:07:16.500
 wise like for polynomials.

151
00:07:17.300 --> 00:07:19.100
and also for xor

152
00:07:19.700 --> 00:07:22.800
one xor 1 gives you which is

153
00:07:22.800 --> 00:07:25.400
 exactly what we have done here by replacing the

154
00:07:25.400 --> 00:07:26.400
 two is you

155
00:07:27.300 --> 00:07:31.200
So you can check here on the xor operation.

156
00:07:32.200 --> 00:07:35.700
that the addition in gf28 is simply in xor

157
00:07:37.500 --> 00:07:39.100
let's now move to multiplication.

158
00:07:40.300 --> 00:07:43.500
To multiply in gf228. We multiply

159
00:07:43.500 --> 00:07:44.500
 the polynomials.

160
00:07:45.300 --> 00:07:49.000
Then we do reduction module polynomial of

161
00:07:48.500 --> 00:07:52.200
 degree 8 the following degree 8

162
00:07:51.200 --> 00:07:54.800
 polynomial X8 plus X4

163
00:07:54.800 --> 00:07:57.400
 plus X3 plus X Plus

164
00:07:57.400 --> 00:07:57.600
 1.

165
00:07:59.100 --> 00:08:02.800
This reduction is what gives us the interesting property that

166
00:08:02.800 --> 00:08:05.200
 we have seen when we introduce the finite fields.

167
00:08:05.900 --> 00:08:08.900
Which is that the result always remain in

168
00:08:08.900 --> 00:08:09.400
 the field?

169
00:08:10.900 --> 00:08:13.100
What does it mean reduction module or

170
00:08:13.100 --> 00:08:13.800
 another polynomial?

171
00:08:14.600 --> 00:08:17.500
It means that whenever we obtain a polynomial

172
00:08:17.500 --> 00:08:20.100
 of degree strictly larger than 7

173
00:08:20.100 --> 00:08:23.800
 for example polynomial of degree 8 or 9. We have

174
00:08:23.800 --> 00:08:26.300
 to reduce it by this degree 8

175
00:08:26.300 --> 00:08:27.000
 polynomial.

176
00:08:27.900 --> 00:08:30.500
To bring it back of degree at

177
00:08:30.500 --> 00:08:34.000
 most 7, so it is still representable in

178
00:08:33.000 --> 00:08:35.100
 gf28.

179
00:08:36.200 --> 00:08:38.700
Let's see some examples to clarify this idea.

180
00:08:39.600 --> 00:08:43.000
We start with the trivial example of multiplying

181
00:08:42.400 --> 00:08:45.100
 with the byte 00.

182
00:08:46.100 --> 00:08:49.400
So we have again our byte 5A and

183
00:08:49.400 --> 00:08:52.900
 we will multiply it with a byte 00. So this

184
00:08:52.900 --> 00:08:55.300
 is the polynomial of 5A when we multiply

185
00:08:55.300 --> 00:08:58.700
 with a polynomial zero. We obtain the

186
00:08:58.700 --> 00:09:01.400
 polynomial zero so multiplication of

187
00:09:01.400 --> 00:09:04.600
 the byte 5A by the by 0 0 gives

188
00:09:04.600 --> 00:09:06.200
 the byte 0 0

189
00:09:08.300 --> 00:09:11.900
the next trivial example is multiplication with

190
00:09:11.900 --> 00:09:13.500
 a byte01.

191
00:09:14.100 --> 00:09:17.100
So when we multiply with the byteser 1

192
00:09:17.800 --> 00:09:20.900
we will multiply actually the polynomial with

193
00:09:20.900 --> 00:09:22.500
 the polynomial one.

194
00:09:23.200 --> 00:09:28.400
Which gives us exactly the same polynomial X6

195
00:09:26.400 --> 00:09:29.700
 plus X4 plus X3

196
00:09:29.700 --> 00:09:30.100
 plus X.

197
00:09:31.300 --> 00:09:34.300
These polynomial is of degree 6, so

198
00:09:34.300 --> 00:09:37.300
 it does not require a reduction so we are

199
00:09:37.300 --> 00:09:37.600
 done.

200
00:09:38.600 --> 00:09:41.700
So the result of the multiplication of the byte

201
00:09:41.700 --> 00:09:44.300
 5A with the by Tier 1 is the

202
00:09:44.300 --> 00:09:45.600
 same byte 5A.

203
00:09:47.300 --> 00:09:50.300
We will skip the multiplication is zero two and

204
00:09:50.300 --> 00:09:53.100
 zero three on purpose because they're very similar

205
00:09:53.100 --> 00:09:54.900
 to the multiplication with zero one.

206
00:09:55.400 --> 00:09:58.500
the respective results remain small of

207
00:09:58.500 --> 00:09:59.200
 degree

208
00:09:59.800 --> 00:10:02.200
less than 8 and do not need

209
00:10:02.200 --> 00:10:03.000
 to be reduced.

210
00:10:03.900 --> 00:10:06.400
You can double check that by doing the multiplication by

211
00:10:06.400 --> 00:10:06.700
 yourself.

212
00:10:07.900 --> 00:10:10.400
However, things get interesting when we multiply

213
00:10:10.400 --> 00:10:12.400
 with the value 0 4.

214
00:10:14.400 --> 00:10:14.900
Okay, so

215
00:10:16.100 --> 00:10:19.900
After multiplying with X2 which corresponds

216
00:10:19.900 --> 00:10:23.100
 to the byte04. We obtain

217
00:10:22.100 --> 00:10:26.100
 a polynomial of degree 8

218
00:10:25.100 --> 00:10:28.900
 the following X8 plus X6 plus

219
00:10:28.900 --> 00:10:30.700
 X5 plus X3.

220
00:10:31.500 --> 00:10:34.800
So now we need to do a reduction module this

221
00:10:34.800 --> 00:10:35.900
 polynomial here.

222
00:10:37.400 --> 00:10:38.600
the trick is that

223
00:10:39.500 --> 00:10:42.900
to perform this reduction. We just need to replace X8.

224
00:10:43.700 --> 00:10:47.400
the monomial X8 by the following polynomial X4

225
00:10:46.400 --> 00:10:48.800
 plus X3 plus X Plus 1

226
00:10:49.400 --> 00:10:53.600
So we just need to plug that into our result

227
00:10:52.600 --> 00:10:54.800
 polynomial.

228
00:10:55.500 --> 00:10:59.100
So we replace the X8 with this polynomial.

229
00:11:00.700 --> 00:11:03.900
And we keep the the other monomials

230
00:11:03.900 --> 00:11:04.900
 of multiplication.

231
00:11:06.100 --> 00:11:10.000
And now we obtain the following polynomial X6 plus

232
00:11:09.400 --> 00:11:11.700
 X5 plus 2 x 3.

233
00:11:12.400 --> 00:11:14.300
plus X4 plus X Plus 1

234
00:11:15.600 --> 00:11:18.300
as usual the two needs to be replaced by

235
00:11:18.300 --> 00:11:21.300
 0. So this monomial this monomial would

236
00:11:21.300 --> 00:11:24.600
 disappear and we obtain X6 plus X5 plus

237
00:11:24.600 --> 00:11:27.800
 X4 plus X Plus 1 which corresponds to

238
00:11:27.800 --> 00:11:30.500
 the bit string 0 1 1

239
00:11:30.500 --> 00:11:32.400
 0 0 1 1

240
00:11:33.300 --> 00:11:36.600
which is the value 73 in

241
00:11:36.600 --> 00:11:40.000
 bytes, so the byte 5a multiplied

242
00:11:39.200 --> 00:11:42.900
 by the byte04 gives the byte

243
00:11:42.900 --> 00:11:43.400
 73

244
00:11:45.100 --> 00:11:48.400
you might be saying okay this time we could

245
00:11:48.400 --> 00:11:51.600
 solve it as we obtained the monomial X8

246
00:11:51.600 --> 00:11:52.500
 after the product.

247
00:11:53.400 --> 00:11:56.300
But what if we obtain the monomial X9 or

248
00:11:56.300 --> 00:11:57.400
 another larger?

249
00:11:59.900 --> 00:12:02.200
See for X9 first and then you will

250
00:12:02.200 --> 00:12:04.600
 get the mechanic of doing it.

251
00:12:06.100 --> 00:12:07.200
Actually X9.

252
00:12:07.900 --> 00:12:10.800
can be written as X8 times x

253
00:12:11.900 --> 00:12:14.100
and as we said the X8 can be

254
00:12:14.100 --> 00:12:17.200
 replaced with X4 plus X3 plus X Plus

255
00:12:17.200 --> 00:12:19.700
 1. So we just need to plug X8 here.

256
00:12:20.700 --> 00:12:24.500
And this gives us following polynomial X5

257
00:12:23.500 --> 00:12:26.200
 plus X4 plus X2 plus

258
00:12:26.200 --> 00:12:26.500
 X.

259
00:12:27.100 --> 00:12:30.100
So whenever we see X9, we just need

260
00:12:30.100 --> 00:12:32.600
 to replace it with the following polynomial.

261
00:12:33.300 --> 00:12:36.800
And similarly we can obtain expressions for

262
00:12:36.800 --> 00:12:38.900
 extend X11 Etc.

263
00:12:39.800 --> 00:12:42.700
So, let's see an example when we will multiply

264
00:12:42.700 --> 00:12:45.300
 the byte 5A with a byte 08.

265
00:12:46.700 --> 00:12:50.800
We have the following polynomials X6

266
00:12:49.800 --> 00:12:52.300
 plus X4 plus X3 plus

267
00:12:52.300 --> 00:12:53.900
 X multiplied by X3.

268
00:12:54.600 --> 00:12:57.800
Which gives us X9 plus X7 plus

269
00:12:57.800 --> 00:12:59.700
 X6 plus X4.

270
00:13:00.700 --> 00:13:03.100
We replace X9 with its.

271
00:13:04.800 --> 00:13:07.600
Corresponding polynomial X5 plus X4 plus

272
00:13:07.600 --> 00:13:10.300
 X2 plus X and we keep the previous

273
00:13:10.300 --> 00:13:11.000
 monobles.

274
00:13:11.900 --> 00:13:14.600
And we replace the two which gives

275
00:13:14.600 --> 00:13:18.300
 us the following final polynomial X7

276
00:13:17.300 --> 00:13:20.800
 plus X6 plus X5 plus

277
00:13:20.800 --> 00:13:22.000
 X2 plus X.

278
00:13:23.300 --> 00:13:27.700
Which corresponds to the value E6 so

279
00:13:27.700 --> 00:13:30.400
 5A times zero eight gives

280
00:13:30.400 --> 00:13:31.300
 E6.

281
00:13:32.900 --> 00:13:35.100
We have seen in this video how we can

282
00:13:35.100 --> 00:13:38.400
 do addition and multiplication in gf28.

283
00:13:39.600 --> 00:13:42.300
In the same way we Define the addition we can

284
00:13:42.300 --> 00:13:45.300
 Define subtraction and in the same

285
00:13:45.300 --> 00:13:48.400
 way we Define multiplication we can also Define

286
00:13:48.400 --> 00:13:48.900
 division.

287
00:13:50.100 --> 00:13:52.600
finite fields are not only used in as

288
00:13:53.200 --> 00:13:56.900
they are the Cornerstone of constructing the arithmetic

289
00:13:56.900 --> 00:13:59.200
 needed in many cryptographic algorithms.

290
00:14:00.300 --> 00:14:04.100
Due to their interesting property that any operation performed

291
00:14:03.100 --> 00:14:06.700
 with elements returns an element contained

292
00:14:06.700 --> 00:14:07.600
 in the original set.

293
00:14:08.800 --> 00:14:11.600
They're also very efficient to implement both in

294
00:14:11.600 --> 00:14:12.500
 hardware and software.

295
00:14:13.100 --> 00:14:16.600
And they can be easily customized to the need of your Construction.

296
00:14:17.700 --> 00:14:20.500
For example, we have seen gf28 to do arithmetic with

297
00:14:20.500 --> 00:14:23.900
 bytes. We can also have gf24 to

298
00:14:23.900 --> 00:14:27.000
 do arithmetic with nibbles. So a bit

299
00:14:26.300 --> 00:14:29.700
 strings of four bits or with a

300
00:14:29.700 --> 00:14:32.600
 larger GF to represent.

301
00:14:33.800 --> 00:14:35.100
larger bit shrinks

302
00:14:36.800 --> 00:14:38.300
we reach the end of this section.

303
00:14:39.200 --> 00:14:42.400
We describe several aspects of symmetric key

304
00:14:42.400 --> 00:14:45.300
 cryptography from the protocol all the

305
00:14:45.300 --> 00:14:47.000
 way to the underlying arithmetic.

306
00:14:48.200 --> 00:14:50.700
So far we focused on confidentiality.

307
00:14:51.800 --> 00:14:54.700
On the next section, we will continue with the symmetric

308
00:14:54.700 --> 00:14:57.300
 key cryptography, but we look at how we

309
00:14:57.300 --> 00:15:00.100
 can achieve integrity and Authentication.

310
00:15:01.300 --> 00:15:03.000
So see you in the next section.
