-
Notifications
You must be signed in to change notification settings - Fork 11
/
gf128mul.txt
360 lines (302 loc) · 22.1 KB
/
gf128mul.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
Mapping the GF(2^128) Galois Field to Byte Arrays in Memory
===========================================================
A polynomial representation will be used for the Galois Field with the
coefficients held in a 128-bit sequence in which the bits are numbered
according to the power of x that they represent. The field polynomial
that is used here is:
x^128 + x^7 + x^2 + x + 1
1 00000000 ... 10000111
0x01 0x00 ... 0x87
which is that used by the GCM combined encryption/authentication mode.
When arrays of bytes (or any other storage unit) in memory are used to
hold larger values, the bytes can be used to represent the larger value
in one of two ways. For example, a 32-bit integer can be formed in the
two different ways (where MS/LS = most/least numerically significant):
MS LS
xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx
big endian byte 0 byte 1 byte 2 byte 3
little endian byte 3 byte 2 byte 1 byte 0
In the first case lower numbered bytes are more numerically significant
and in the second case they are less significant. As indicated, the
term 'big-endian' is used to describe the former situation in which
lower numbered items are given higher numeric significance when used to
form larger objects. The term 'little endian' describes the opposite
situation.
Bytes are not normally subdivided into nibbles (4-bit units) in memory
but if they were, big and little endian ordering would be:
MS LS
xxxxxxxx xxxxxxxx
big endian: nibble 0 nibble 1
little endian: nibble 1 nibble 0
If we continue subdividing into 2 bit and then single bit objects we
would find that the natural big-endian numbering for bits in bytes is:
big endian: 01234567 -- bit n is that which represents 2^(7 - n)
little endian: 76543210 -- bit n is that which represents 2^n
So big (little) endian bit ordering is when bits with lower bit numbers
are placed in the more (less) numerically significant bits within bytes.
We can now describe the four common ways of mapping 128-bit sequences
onto arrays of 16 bytes:
bit[n] ==> byte[n / 8], 2^(n % 8) LE bytes LE bits (LL)
bit[n] ==> byte[n / 8], 2^(7 - n % 8) LE bytes BE bits (LB)
bit[n] ==> byte[15 - n / 8], 2^(n % 8) BE bytes LE bits (BL)
bit[n] ==> byte[15 - n / 8], 2^(7 - n % 8) BE bytes BE bits (BB)
The positions of the 128 bits when accessed as 8, 16, 32 and 64 bit big
and little endian objects are given below. In the following diagrams
the lowest eight bits are illustraated as the low 8 bits of the field
polynomial and bit 127 is marked with an M.
===========================================================
LL (favours LE) - Bit<n:0..127> => 2^(n % 8) in byte[n / 8]
===========================================================
LE/BE-8
x[0] x[1] x[2] x[3] x[4] x[5] x[6] x[7]
ms ls ms ls ms ls ms ls ms ls ms ls ms ls ms ls
10000111 ........ ........ ........ ........ ........ ........ ........
07....00 15....08 23....16 31....24 39....32 47....40 55....48 63....56
x[8] x[9] x[10] x[11] x[12] x[13] x[14] x[15]
ms ls ms ls ms ls ms ls ms ls ms ls ms ls ms ls
........ ........ ........ ........ ........ ........ ........ M.......
71....64 79....72 87....80 95....88 103...96 111..104 119..112 127..120
LE-16
ms x[0] ls ms x[1] ls ms x[2] ls ms x[3] ls
........10000111 ................ ................ ................
15...08 07...00 31...24 23...16 47...40 39...32 63...56 55...48
ms x[4] ls ms x[5] ls ms x[6] ls ms x[7] ls
................ ................ ................ M...............
79...72 71...64 95...88 87...80 111.104 103..96 127.120 119.112
LE-32
ms x[0] ls ms x[1] ls
........................10000111 ................................
31...24 23...16 15...08 07...00 63...56 55...48 47...40 39...32
ms x[2] ls ms x[3] ls
................................ M...............................
95...88 87...80 79...72 71...64 127.120 119.112 111.104 103..96
LE-64
ms x[0] ls
........................................................10000111
63....56 55...48 47...40 39...32 31...24 23...16 15...08 07...00
ms x[1] ls
M...............................................................
127..120 119.112 111.104 103..96 95...88 87...80 79...72 71...64
BE-16
ms x[0] ls ms x[1] ls ms x[2] ls ms x[3] ls
10000111........ ................ ................ ................
07....00 15...08 23...16 31...24 39...32 47...40 55...48 63...56
ms x[4] ls ms x[5 ] ls ms x[6] ls ms x[7] ls
................ ................ ................ ........M.......
71...64 79...72 87...80 95...88 103..96 111.104 119.112 127..120
BE-32
ms x[0] ls ms x[1] ls
10000111........................ ................................
07...00 15...08 23...16 31...24 39...32 47...40 55...48 63...56
ms x[2] ls ms x[3] ls
................................ ........................M.......
71...64 79...72 87...80 95...88 103..96 111.104 119.112 127..120
BE-64
ms x[0] ls
10000111........................................................
07....00 15...08 23...16 31...24 39...32 47...40 55...48 63...56
ms x[1] ls
........................................................M.......
71....64 79...72 87...80 95...88 103.96 111.104 119.112 127..120
===============================================================
LB (favours BE) - Bit<n:0..127> => 2^(7 - n % 8) in byte[n / 8]
===============================================================
LE/BE-8
x[0] x[1] x[2] x[3] x[4] x[5] x[6] x[7]
ms ls ms ls ms ls ms ls ms ls ms ls ms ls ms ls
11100001 ........ ........ ........ ........ ........ ........ ........
00....07 08....15 16....23 24....31 32....39 40....47 48....55 56....63
x[8] x[9] x[10] x[11] x[12] x[13] x[14] x[15]
ms ls ms ls ms ls ms ls ms ls ms ls ms ls ms ls
........ ........ ........ ........ ........ ........ ........ .......M
64....71 72....79 80....87 88....95 96...103 104..111 112..119 120..127
LE-16
ms x[0] ls ms x[1] ls ms x[2] ls ms x[3] ls
........11100001 ................ ................ ................
08...15 00...07 24...31 16...23 40...47 32...39 56...63 48...55
ms x[4] ls ms x[5] ls ms x[6] ls ms x[7] ls
................ ................ ................ .......M........
72...79 64...71 88...95 80...87 104.111 96..103 120..127 112.119
LE-32
ms x[0] ls ms x[1] ls
........................11100001 ................................
24...31 16...23 08...15 00...07 56...63 48...55 40...47 32...39
ms x[2] ls ms x[3] ls
................................ .......M........................
88...95 80...87 72...79 64...71 120..127 112.119 104.111 96..103
LE-64
ms x[0] ls
........................................................11100001
56...63 48...55 40...47 32...39 24...31 16...23 08...15 00....07
ms x[1] ls
.......M........................................................
120..127 112.119 104.111 96..103 88...95 80...87 72...79 64...71
BE-16
ms x[0] ls ms x[1] ls ms x[2] ls ms x[3] ls
11100001........ ................ ................ ................
00...07 08...15 16...23 24...31 32...39 40...47 48...55 56...63
ms x[4] ls ms x[5] ls ms x[6] ls ms x[7] ls
................ ................ ................ ...............M
64...71 72...79 80...87 88...95 96..103 104.111 112.119 120.127
BE-32
ms x[0] ls ms x[1] ls
11100001........................ ................................
00...07 08...15 16...23 24...31 32...39 40...47 48...55 56...63
ms x[2] ls ms x[3] ls
................................ ...............................M
64...71 72...79 80...87 88...95 96..103 104.111 112.119 120.127
BE-64
ms x[0] ls
11100001........................................................
00....07 08...15 16...23 24...31 32...39 40...47 48...55 56...63
ms x[1] ls
...............................................................M
64...71 72...79 80...87 88...95 96..103 104.111 112.119 120.127
================================================================
BL (favours BE) - Bit<n:0..127> => 2^(n % 8) in byte[15 - n / 8]
================================================================
LE/BE-8
x[0] x[1] x[2] x[3] x[4] x[5] x[6] x[7]
ms ls ms ls ms ls ms ls ms ls ms ls ms ls ms ls
M....... ........ ........ ........ ........ ........ ........ ........
127..120 119..112 111..104 103...96 95....88 87....80 79....72 71....64
x[8] x[9] x[10] x[11] x[12] x[13] x[14] x[15]
ms ls ms ls ms ls ms ls ms ls ms ls ms ls ms ls
........ ........ ........ ........ ........ ........ ........ 10000111
63....56 55....48 47....40 39....32 31....24 23....16 15....08 07....00
LE-16
ms x[0] ls ms x[1] ls ms x[2] ls ms x[3] ls
........M....... ................ ................ ................
119.112 127.120 103..96 111.104 87...80 95...88 71...64 79...72
ms x[4] ls ms x[5] ls ms x[6] ls ms x[7] ls
................ ................ ................ 10000111........
55...48 63...56 39...32 47...40 23...16 31...24 07....00 15...08
LE-32
ms x[0] ls ms x[1] ls
........................M....... ................................
103..96 111.104 119.112 127.120 71...64 79...72 87...80 95...88
ms x[2] ls ms x[3] ls
................................ 10000111........................
39...32 47...40 55...48 63...56 07....00 15...08 23...16 31...24
LE-64
ms x[0] ls
........................................................M.......
71...64 79...72 87...80 95...88 103..96 111.104 119.112 127..120
ms x[1] ls
10000111........................................................
07....00 15...08 23...16 31...24 39...32 47...40 55...48 63...56
BE-16
ms x[0] ls ms x[1] ls ms x[2] ls ms x[3] ls
M............... ................ ................ ................
127.120 119.112 111.104 103..96 95...88 87...80 79...72 71...64
ms x[4] ls ms x[5] ls ms x[7] ls ms x[7] ls
................ ................ ................ ........10000111
63...56 55...48 47...40 39...32 31...24 23...16 15...08 07...00
BE-32
ms x[0] ls ms x[1] ls
M............................... ................................
127.120 119.112 111.104 103..96 95...88 87...80 79...72 71...64
ms x[2] ls ms x[3] ls
................................ ........................10000111
63...56 55...48 47...40 39...32 31...24 23...16 15...08 07...00
BE-64
ms x[0] ls
M...............................................................
127.120 119.112 111.104 103..96 95...88 87...80 79...72 71...64
ms x[1] ls
........................................................10000111
63...56 55...48 47...40 39...32 31...24 23...16 15...08 07....00
====================================================================
BB (favours LE) - Bit<n:0..127> => 2^(7 - n % 8) in byte[15 - n / 8]
====================================================================
LE/BE-8
x[0] x[1] x[2] x[3] x[4] x[5] x[6] x[7]
ms ls ms ls ms ls ms ls ms ls ms ls ms ls ms ls
.......M ........ ........ ........ ........ ........ ........ ........
120..127 112..119 104..111 96...103 88....95 80....87 72....79 64....71
x[8] x[9] x[10] x[11] x[12] x[13] x[14] x[15]
ms ls ms ls ms ls ms ls ms ls ms ls ms ls ms ls
........ ........ ........ ........ ........ ........ ........ 11100001
56....63 48....55 40....47 32....39 24....31 16....23 08....15 00....07
LE-16
ms x[0] ls ms x[1] ls ms x[2] ls ms x[3] ls
...............M ................ ................ ................
112.119 120.127 96..103 104.111 80...87 88...95 64...71 72...79
ms x[4] ls ms x[5] ls ms x[6] ls ms x[7] ls
................ ................ ................ 11100001........
48...55 56...63 32...39 40...47 16...23 24...31 00....07 08...15
LE-32
ms x[0] ls ms x[1] ls
...............................M ................................
96..103 104.111 112.119 120.127 64...71 72...79 80...87 88...95
ms x[2] ls ms x[3] ls
................................ 11100001........................
32...39 40...47 48...55 56...63 00....07 08...15 16...23 24...31
LE-64
ms x[0] ls
...............................................................M
64...71 72...79 80...87 88...95 96..103 104.111 112.119 120.127
ms x[1] ls
11100001........................................................
00....07 08...15 16...23 24...31 32...39 40...47 48...55 56...63
BE-16
ms x[0] ls ms x[1] ls ms x[2] ls ms x[3] ls
.......M........ ................ ................ ................
120.127 112.119 104.111 96..103 88...95 80...87 72...79 64...71
ms x[4] ls ms x[5] ls ms x[6] ls ms x[7] ls
................ ................ ................ ........11100001
56...63 48...55 40...47 32...39 24...31 16...23 08...15 00....07
BE-32
ms x[0] ls ms x[1] ls
.......M........................ ................................
120.127 112.119 104.111 96..103 88...95 80...87 72...79 64...71
ms x[2] ls ms x[3] ls
................................ ........................11100001
56...63 48...55 40...47 32...39 24...31 16...23 08...15 00....07
BE-64
ms x[0] ls
........M.......................................................
120.127 112.119 104.111 96..103 88...95 80...87 72...79 64...71
ms x[1] ls
........................................................11100001
56...63 48...55 40...47 32...39 24...31 16...23 08...15 00....07
ll/le/008: 007:000 015:008 023:016 031:024 039:032 047:040 055:048 063:056 071:064 079:072 087:080 095:088 103:096 111:104 119:112 127:120
ll/le/016: 015:008 007:000 031:024 023:016 047:040 039:032 063:056 055:048 079:072 071:064 095:088 087:080 111:104 103:096 127:120 119:112
ll/le/032: 031:024 023:016 015:008 007:000 063:056 055:048 047:040 039:032 095:088 087:080 079:072 071:064 127:120 119:112 111:104 103:096
ll/le/064: 063:056 055:048 047:040 039:032 031:024 023:016 015:008 007:000 127:120 119:112 111:104 103:096 095:088 087:080 079:072 071:064
ll/le/128: 127:120 119:112 111:104 103:096 095:088 087:080 079:072 071:064 063:056 055:048 047:040 039:032 031:024 023:016 015:008 007:000
ll/be/008: 007:000 015:008 023:016 031:024 039:032 047:040 055:048 063:056 071:064 079:072 087:080 095:088 103:096 111:104 119:112 127:120
ll/be/016: 007:000 015:008 023:016 031:024 039:032 047:040 055:048 063:056 071:064 079:072 087:080 095:088 103:096 111:104 119:112 127:120
ll/be/032: 007:000 015:008 023:016 031:024 039:032 047:040 055:048 063:056 071:064 079:072 087:080 095:088 103:096 111:104 119:112 127:120
ll/be/064: 007:000 015:008 023:016 031:024 039:032 047:040 055:048 063:056 071:064 079:072 087:080 095:088 103:096 111:104 119:112 127:120
ll/be/128: 007:000 015:008 023:016 031:024 039:032 047:040 055:048 063:056 071:064 079:072 087:080 095:088 103:096 111:104 119:112 127:120
lb/le/008: 000:007 008:015 016:023 024:031 032:039 040:047 048:055 056:063 064:071 072:079 080:087 088:095 096:103 104:111 112:119 120:127
lb/le/016: 008:015 000:007 024:031 016:023 040:047 032:039 056:063 048:055 072:079 064:071 088:095 080:087 104:111 096:103 120:127 112:119
lb/le/032: 024:031 016:023 008:015 000:007 056:063 048:055 040:047 032:039 088:095 080:087 072:079 064:071 120:127 112:119 104:111 096:103
lb/le/064: 056:063 048:055 040:047 032:039 024:031 016:023 008:015 000:007 120:127 112:119 104:111 096:103 088:095 080:087 072:079 064:071
lb/le/128: 120:127 112:119 104:111 096:103 088:095 080:087 072:079 064:071 056:063 048:055 040:047 032:039 024:031 016:023 008:015 000:007
lb/be/008: 000:007 008:015 016:023 024:031 032:039 040:047 048:055 056:063 064:071 072:079 080:087 088:095 096:103 104:111 112:119 120:127
lb/be/016: 000:007 008:015 016:023 024:031 032:039 040:047 048:055 056:063 064:071 072:079 080:087 088:095 096:103 104:111 112:119 120:127
lb/be/032: 000:007 008:015 016:023 024:031 032:039 040:047 048:055 056:063 064:071 072:079 080:087 088:095 096:103 104:111 112:119 120:127
lb/be/064: 000:007 008:015 016:023 024:031 032:039 040:047 048:055 056:063 064:071 072:079 080:087 088:095 096:103 104:111 112:119 120:127
lb/be/128: 000:007 008:015 016:023 024:031 032:039 040:047 048:055 056:063 064:071 072:079 080:087 088:095 096:103 104:111 112:119 120:127
bl/le/008: 127:120 119:112 111:104 103:096 095:088 087:080 079:072 071:064 063:056 055:048 047:040 039:032 031:024 023:016 015:008 007:000
bl/le/016: 119:112 127:120 103:096 111:104 087:080 095:088 071:064 079:072 055:048 063:056 039:032 047:040 023:016 031:024 007:000 015:008
bl/le/032: 103:096 111:104 119:112 127:120 071:064 079:072 087:080 095:088 039:032 047:040 055:048 063:056 007:000 015:008 023:016 031:024
bl/le/064: 071:064 079:072 087:080 095:088 103:096 111:104 119:112 127:120 007:000 015:008 023:016 031:024 039:032 047:040 055:048 063:056
bl/le/128: 007:000 015:008 023:016 031:024 039:032 047:040 055:048 063:056 071:064 079:072 087:080 095:088 103:096 111:104 119:112 127:120
bl/be/008: 127:120 119:112 111:104 103:096 095:088 087:080 079:072 071:064 063:056 055:048 047:040 039:032 031:024 023:016 015:008 007:000
bl/be/016: 127:120 119:112 111:104 103:096 095:088 087:080 079:072 071:064 063:056 055:048 047:040 039:032 031:024 023:016 015:008 007:000
bl/be/032: 127:120 119:112 111:104 103:096 095:088 087:080 079:072 071:064 063:056 055:048 047:040 039:032 031:024 023:016 015:008 007:000
bl/be/064: 127:120 119:112 111:104 103:096 095:088 087:080 079:072 071:064 063:056 055:048 047:040 039:032 031:024 023:016 015:008 007:000
bl/be/128: 127:120 119:112 111:104 103:096 095:088 087:080 079:072 071:064 063:056 055:048 047:040 039:032 031:024 023:016 015:008 007:000
bb/le/008: 120:127 112:119 104:111 096:103 088:095 080:087 072:079 064:071 056:063 048:055 040:047 032:039 024:031 016:023 008:015 000:007
bb/le/016: 112:119 120:127 096:103 104:111 080:087 088:095 064:071 072:079 048:055 056:063 032:039 040:047 016:023 024:031 000:007 008:015
bb/le/032: 096:103 104:111 112:119 120:127 064:071 072:079 080:087 088:095 032:039 040:047 048:055 056:063 000:007 008:015 016:023 024:031
bb/le/064: 064:071 072:079 080:087 088:095 096:103 104:111 112:119 120:127 000:007 008:015 016:023 024:031 032:039 040:047 048:055 056:063
bb/le/128: 000:007 008:015 016:023 024:031 032:039 040:047 048:055 056:063 064:071 072:079 080:087 088:095 096:103 104:111 112:119 120:127
bb/be/008: 120:127 112:119 104:111 096:103 088:095 080:087 072:079 064:071 056:063 048:055 040:047 032:039 024:031 016:023 008:015 000:007
bb/be/016: 120:127 112:119 104:111 096:103 088:095 080:087 072:079 064:071 056:063 048:055 040:047 032:039 024:031 016:023 008:015 000:007
bb/be/032: 120:127 112:119 104:111 096:103 088:095 080:087 072:079 064:071 056:063 048:055 040:047 032:039 024:031 016:023 008:015 000:007
bb/be/064: 120:127 112:119 104:111 096:103 088:095 080:087 072:079 064:071 056:063 048:055 040:047 032:039 024:031 016:023 008:015 000:007
bb/be/128: 120:127 112:119 104:111 096:103 088:095 080:087 072:079 064:071 056:063 048:055 040:047 032:039 024:031 016:023 008:015 000:007