forked from moserware/AES-Illustrated
-
Notifications
You must be signed in to change notification settings - Fork 0
/
FiniteFieldMath.cs
309 lines (267 loc) · 11.2 KB
/
FiniteFieldMath.cs
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
using System;
using System.Collections;
using System.Linq;
namespace Moserware.AesIllustrated
{
/// <summary>
/// Performs mathematical operations in Rijndael's finite field (GF[2^8] for the Galois fans out there).
/// </summary>
/// <remarks>For performance reasons, most functions are just table lookups.
/// However, to be instructive, there are "Calculate" functions that actually do the
/// real math. These are used by the functions that create the tables.
/// </remarks>
internal static class FiniteFieldMath
{
private static byte[] _AntiLogTable;
private static byte[] _FTable;
private static byte[] _GTable;
private static byte[] _InvFTable; // Technically this isn't needed since we compute the s-box inverse without needing it.
private static byte[] _LogTable;
/// <summary>
/// Calculates x * b(x) mod m(x) where b(x) is represented by <paramref name="b"/> and
/// m(x) is the Rijndael polynomial x^8 ⊕ x^4 ⊕ x^3 ⊕ x ⊕ 1 = 0x11B.
/// </summary>
/// <remarks>For more details, see page 16 of
/// "The Design of Rijndael: AES - The Advanced Encryption Standard" by Vincent Rijmen
/// and Joan Daemen.
/// <param name="b">The polynomial b(x) represented by a byte.</param>
/// <returns>The value x * b(x) mod m(x).</returns>
public static byte XTime(byte b)
{
// (from p.53)
// 8 7 6 5 4 3 2 1
// b * x = b x ⊕ b x ⊕ b x ⊕ b x ⊕ b x ⊕ b x ⊕ b x ⊕ b x
// 7 6 5 4 3 2 1 0
// When we modulo m(x), we realize that it's a left shift
byte top = (byte) ((b << 1) & 0xFF);
// plus an xor to this polynomial if b7 is set:
// x^4 ⊕ x^3 ⊕ x ⊕ 1
// = 11011
// = 0x1B
bool highBitIsSet = (0x80 & b) == 0x80;
// In order to prevent a timing attack, we'd want to make sure both
// cases took the same amount of time
byte bottom = highBitIsSet ? (byte) 0x1B : (byte) 0;
byte sum = (byte) (top ^ bottom);
return sum;
}
private static byte XPlus1Time(byte b)
{
// x ⊕ 1 = 0x03, which is a generator in x^8 ⊕ x^4 ⊕ x^3 ⊕ x ⊕ 1,
// for more info, see http://www.samiam.org/galois.html
// (x ⊕ 1) * b = x * b ⊕ 1 * b = x*b
return (byte) (XTime(b) ^ b);
}
/// <summary>
/// Calculates the logarithm in the Rijndael finite field using (x⊕1) as the base.
/// </summary>
/// <param name="x">Polynomial to get the logarithm of.</param>
/// <returns>The logarithm of <paramref name="x"/>.</returns>
public static byte Log(byte x)
{
if (_LogTable == null)
{
_LogTable = CalculateLogTable(out _AntiLogTable);
}
return _LogTable[x];
}
/// <summary>
/// Calculates the inverse logarithm in the Rijndael finite field using (x⊕1) as the base.
/// </summary>
/// <param name="x">Polynomial to get the inverse logarithm of.</param>
/// <returns>The inverse logarithm of <paramref name="x"/>.</returns>
public static byte AntiLog(byte x)
{
if (_AntiLogTable == null)
{
_LogTable = CalculateLogTable(out _AntiLogTable);
}
return _AntiLogTable[x];
}
/// <summary>
/// Calculates the logarithm and inverse logarithm (antilog) in the Rijndael
/// finite field using (x⊕1) as the base/generator.
/// </summary>
/// <param name="antiLogTable">The antilog table</param>
/// <returns>The logarithm table.</returns>
private static byte[] CalculateLogTable(out byte[] antiLogTable)
{
byte[] logTable = new byte[256];
antiLogTable = new byte[256];
antiLogTable[0] = 1;
logTable[0] = 0;
for (int i = 1; i < 256; i++)
{
// Since (x⊕1) is a generator, we can keep multiplying our previous
// result by (x⊕1) and eventually we'll generate every element.
antiLogTable[i] = XPlus1Time(antiLogTable[i - 1]);
logTable[antiLogTable[i]] = (byte) i;
}
logTable[1] = 0;
return logTable;
}
/// <summary>
/// Calculates f(<paramref name="a"/>), which is an affine transform (e.g. it's a matrix
/// multiply followed by a vector add).
/// </summary>
/// <param name="a">The byte to apply the transform to.</param>
/// <returns>The result of F(<paramref name="a"/>)</returns>
public static byte F(byte a)
{
if (_FTable == null)
{
_FTable = CalculateFTable(out _InvFTable);
}
// Uses cached copy
return _FTable[a];
}
/// <summary>
/// Calculates f(<paramref name="a"/>), which is an affine transform (e.g. it's a matrix
/// multiply followed by a vector add).
/// </summary>
/// <param name="a">The byte to apply the transform to.</param>
/// <returns>The result of F(<paramref name="a"/)</returns>
private static byte CalculateF(byte a)
{
// Visually, b = f(a) is
//
// | b7 | | 1 1 1 1 1 0 0 0 | | a7 | | 0 |
// | b6 | | 0 1 1 1 1 1 0 0 | | a6 | | 1 |
// | b5 | | 0 0 1 1 1 1 1 0 | | a5 | | 1 |
// | b4 | * | 0 0 0 1 1 1 1 1 | * | a4 | + | 0 |
// | b3 | | 1 0 0 0 1 1 1 1 | | a3 | | 0 |
// | b2 | | 1 1 0 0 0 1 1 1 | | a2 | | 0 |
// | b1 | | 1 1 1 0 0 0 1 1 | | a1 | | 1 |
// | b0 | | 1 1 1 1 0 0 0 1 | | a0 | | 1 |
// Define the top row of the matrix
int[] shouldMultiplyBits = {1, 1, 1, 1, 1, 0, 0, 0};
// Create a function that converts the 1's and 0's to bits
Func<int[], BitArray> toBitArray = vector => new BitArray(vector.Select(b => b != 0).ToArray());
BitArray shouldMultiply = toBitArray(shouldMultiplyBits);
// Convert a to bits
BitArray aVector = new BitArray(new[] {a});
BitArray multiplyResult = new BitArray(8);
// Perform the multiply
for (int offset = 0; offset < 8; offset++)
{
for (int bit = 0; bit < 8; bit++)
{
bool currentMultiplyBitValue = shouldMultiplyBits[(8 + ((8 - offset) + bit))%8] != 0;
bool currentBitMultiplyResult = currentMultiplyBitValue && aVector[7 - bit];
if (currentBitMultiplyResult)
{
multiplyResult[offset] = !multiplyResult[offset];
}
}
}
// Perform the vector add, which is a simply xor
int[] affineVectorBits = {0, 1, 1, 0, 0, 0, 1, 1};
BitArray affineVector = toBitArray(affineVectorBits);
BitArray resultVector = multiplyResult.Xor(affineVector);
// We have the bits, now convert them back to a byte, we do this
// by OR-ing each bit to the value its position represents (if it is a 1).
byte result = 0;
byte multiplier = 0x80;
for (int i = 0; i < 8; i++)
{
if (resultVector[i])
{
result |= multiplier;
}
multiplier >>= 1;
}
return result;
}
/// <summary>
/// Computes a table for f(a) along with its inverse.
/// </summary>
/// <param name="invFTable">A table for the inverse of f(a). That is g, such that f(g(a)) = a.</param>
/// <returns>A table for f(a).</returns>
private static byte[] CalculateFTable(out byte[] invFTable)
{
var result = new byte[256];
invFTable = new byte[256];
for (int i = 0; i < 256; i++)
{
result[i] = CalculateF((byte) i);
invFTable[result[i]] = (byte) i;
}
return result;
}
/// <summary>
/// Multiplies two polynomials (each represented by a byte) in the Rijndael finite field.
/// </summary>
/// <param name="left">The first polynomial.</param>
/// <param name="right">The second polynomial.</param>
/// <returns><paramref name="left"/>*<paramref name="right"/></returns>
public static byte Multiply(byte left, byte right)
{
if (_LogTable == null)
{
_LogTable = CalculateLogTable(out _AntiLogTable);
}
if ((left != 0) && (right != 0))
{
byte result = _AntiLogTable[(_LogTable[left] + _LogTable[right])%255];
return result;
}
else
{
// Multiplying anything by 0 is 0.
// Note that we potentially have a timing attack here since this path is different than the non-zero path
return 0;
}
}
/// <summary>
/// Computes g(a) which is the inverse in the Rijndael field such that g(a) * a = 1.
/// </summary>
/// <returns>g(a)</returns>
public static byte G(byte a)
{
if (_GTable == null)
{
_GTable = CalculateGTable();
}
// We have it cached
return _GTable[a];
}
/// <summary>
/// Computes g(a) which is the inverse in the Rijndael field such that g(a) * a = 1.
/// </summary>
/// <returns>g(a)</returns>
private static byte CalculateG(byte a)
{
// 0 doesn't have an inverse
if (a == 0)
{
return 0;
}
// We do a brute-force search for the inverse (e.g. what we can
// multiply a by to get 1). This is reasonable since there are a max
// of 255 choices to try. It's simpler than working out the math to
// get the answer algebraically.
for (int i = 1; i < 256; i++)
{
if (Multiply((byte) i, a) == 1)
{
return (byte) i;
}
}
// We should always find an inverse, so we should never get here:
throw new InvalidOperationException();
}
/// <summary>
/// Computes a table of all g(a) values.
/// </summary>
/// <returns>Table of all g(a) values.</returns>
private static byte[] CalculateGTable()
{
byte[] result = new byte[256];
for (int i = 0; i < 256; i++)
{
result[i] = CalculateG((byte) i);
}
return result;
}
}
}