331 lines
6.9 KiB
D
331 lines
6.9 KiB
D
module angel.utils.cryptography.gcm.galoisfield;
|
|
|
|
import std.traits: isIntegral;
|
|
import std.array;
|
|
|
|
package:
|
|
@safe
|
|
struct GF128
|
|
{
|
|
|
|
alias ubyte T;
|
|
alias T[BLOCKLEN/(T.sizeof*8)] block;
|
|
|
|
enum BLOCKLEN = 128;
|
|
|
|
enum T R = 0xE1<<(T.sizeof*8-8);
|
|
|
|
enum T ONE = 0x80<<(T.sizeof*8-8);
|
|
|
|
/**
|
|
* raises x to the power 'pow' by squaring
|
|
* x <- x^pow
|
|
*
|
|
* Params:
|
|
* x = this value gets raised to the power pow
|
|
* pow = the power
|
|
*/
|
|
static void power(T)(T[] x, ulong pow) nothrow @nogc
|
|
if(isIntegral!T)
|
|
in {
|
|
assert(x.length*T.sizeof*8 == BLOCKLEN, "invalid length. expected 16 bytes.");
|
|
}
|
|
body {
|
|
block squared;
|
|
squared[] = x[];
|
|
|
|
block exp;
|
|
exp[0] = ONE; // little endian 1
|
|
|
|
block one;
|
|
one[0] = ONE; // little endian 1
|
|
|
|
while(pow > 0) {
|
|
|
|
if(pow & 0x1) {
|
|
multiply(exp, squared);
|
|
} else {
|
|
multiply(exp, one); // dummy multiplication to avoid timing attacks
|
|
}
|
|
|
|
multiply(squared, squared);
|
|
|
|
pow = pow >> 1;
|
|
}
|
|
|
|
x[] = exp[];
|
|
}
|
|
|
|
// test power
|
|
unittest {
|
|
immutable ubyte[] x = cast(immutable ubyte[]) x"66e94bd4ef8a2c3b884cfa59ca342b2e";
|
|
|
|
ubyte[16] naivePow;
|
|
naivePow[0] = 0x80; // little endian 1
|
|
|
|
immutable uint pow = 13;
|
|
|
|
for(uint i = 0; i < pow; ++i) {
|
|
multiply(naivePow, x);
|
|
}
|
|
|
|
ubyte[16] powBySquare;
|
|
powBySquare[] = x[];
|
|
|
|
power(powBySquare, pow);
|
|
|
|
assert(naivePow == powBySquare, "power() failed");
|
|
}
|
|
|
|
/// Multiplies x by y using schoolbook multiplication. Result stored in x.
|
|
static void multiply(T[] x, in T[] y) nothrow @nogc
|
|
in {
|
|
assert(x.length*T.sizeof*8 == BLOCKLEN, "x: invalid length.");
|
|
}
|
|
body {
|
|
|
|
block v = x;
|
|
block z;
|
|
|
|
for(uint i = 0; i < y.length; ++i) {
|
|
T currWord = y[i];
|
|
|
|
for(int j = T.sizeof*8-1; j >= 0; --j) {
|
|
|
|
// if((currWord >> j) & 0x01) {
|
|
// z[] ^= v[];
|
|
// }
|
|
// avoid branching:
|
|
//z[] ^= v[]&(-(cast(T)((currWord >> j) & 1)));
|
|
z[] ^= v[] & cast(T)(-cast(int)((currWord >> j) & 1)); // less prone to timing attacks than if statement
|
|
|
|
T lsb = v[$-1] & 1;
|
|
shiftRight(v);
|
|
|
|
// if(lsb) {
|
|
// v[0] ^= R;
|
|
// }
|
|
// Avoid branching by using conditional XOR:
|
|
v[0] ^= R&(-lsb); // -lsb is either 0x00, or 0xFF
|
|
}
|
|
}
|
|
|
|
x[] = z[];
|
|
}
|
|
|
|
/// test multiplication by one
|
|
unittest {
|
|
immutable block x0 = cast(immutable block) x"66e94bd4ef8a2c3b884cfa59ca342b2e";
|
|
block x1 = x0;
|
|
|
|
block one;
|
|
one[0] = ONE;
|
|
|
|
multiply(x1, one);
|
|
|
|
assert(x1 == x0, "GCM multiplication by ONE failed!");
|
|
}
|
|
|
|
/// test multiplication
|
|
unittest {
|
|
|
|
immutable block H = cast(immutable block)x"66e94bd4ef8a2c3b884cfa59ca342b2e";
|
|
|
|
block x1 = cast(immutable block) x"0388dace60b6a392f328c2b971b2fe78";
|
|
|
|
multiply(x1, H);
|
|
|
|
assert(x1 == x"5e2ec746917062882c85b0685353deb7", "GCM multiplication failed!");
|
|
}
|
|
|
|
// http://www.ieee802.org/1/files/public/docs2011/bn-randall-test-vectors-0511-v1.pdf
|
|
unittest {
|
|
|
|
immutable block H = cast(immutable block) x"73A23D80121DE2D5A850253FCF43120E";
|
|
block X1 = cast(immutable block) x"D609B1F056637A0D46DF998D88E5222A";
|
|
|
|
multiply(X1, H);
|
|
|
|
assert(X1 == x"6B0BE68D67C6EE03EF7998E399C01CA4", "GCM multiplication failed!");
|
|
}
|
|
|
|
// http://www.ieee802.org/1/files/public/docs2011/bn-randall-test-vectors-0511-v1.pdf
|
|
unittest {
|
|
|
|
immutable block H = cast(immutable block) x"286D73994EA0BA3CFD1F52BF06A8ACF2";
|
|
block X1 = cast(immutable block) x"D609B1F056637A0D46DF998D88E5222A";
|
|
|
|
multiply(X1, H);
|
|
|
|
assert(X1 == x"BA7C26F578254853CF321281A48317CA", "GCM multiplication failed!");
|
|
}
|
|
|
|
// http://www.ieee802.org/1/files/public/docs2011/bn-randall-test-vectors-0511-v1.pdf
|
|
unittest {
|
|
|
|
immutable block H = cast(immutable block) x"E4E01725D724C1215C7309AD34539257";
|
|
block X1 = cast(immutable block) x"E20106D7CD0DF0761E8DCD3D88E54000";
|
|
|
|
multiply(X1, H);
|
|
|
|
assert(X1 == x"8DAD4981E33493018BB8482F69E4478C", "GCM multiplication failed!");
|
|
}
|
|
|
|
/**
|
|
* multiplication by P (only bit 1 = 1)
|
|
*/
|
|
static void multiplyP(T[] x) nothrow @nogc
|
|
in {
|
|
assert(x.length == 16, "x: invalid length. must be 16.");
|
|
}
|
|
body {
|
|
T lsb = x[$-1] & 0x01;
|
|
shiftRight(x);
|
|
x[0] ^= R * lsb;
|
|
}
|
|
|
|
// test multiplyP()
|
|
unittest {
|
|
|
|
block X = cast(immutable block) x"E20106D7CD0DF0761E8DCD3D88E54000";
|
|
immutable block P = cast(immutable block) x"40000000000000000000000000000000";
|
|
|
|
block XmultP;
|
|
XmultP = X;
|
|
|
|
multiplyP(XmultP);
|
|
|
|
multiply(X, P);
|
|
|
|
assert(X == XmultP, "multiplyP() failed");
|
|
}
|
|
|
|
/**
|
|
* multiplication by P^8
|
|
*/
|
|
static void multiplyP8(T)(T[] x)
|
|
{
|
|
T lsw = x[$-1];
|
|
shiftRight8(x);
|
|
for (int i = 7; i >= 0; --i)
|
|
{
|
|
// if (lsw & (1 << i))
|
|
// {
|
|
// x[0] ^= ((R<<(T.sizeof*8-8)) >> (7 - i));
|
|
// }
|
|
// avoid branching:
|
|
x[0] ^= (((R<<(T.sizeof*8-8)) >> (7 - i))) * (lsw & (1 << i));
|
|
}
|
|
}
|
|
|
|
// test multiplyP8()
|
|
unittest {
|
|
|
|
block X = cast(immutable block) x"E20106D7CD0DF0761E8DCD3D88E54000";
|
|
immutable block P = cast(immutable block) x"40000000000000000000000000000000";
|
|
|
|
block XmultP8;
|
|
XmultP8 = X;
|
|
|
|
multiplyP8(XmultP8);
|
|
|
|
foreach(i;0..8){
|
|
multiply(X, P);
|
|
}
|
|
|
|
assert(X == XmultP8, "multiplyP8() failed");
|
|
}
|
|
|
|
/**
|
|
* Shift big endian number a 1 bit to the right.
|
|
*/
|
|
static void shiftRight(T)(T[] a) nothrow @nogc
|
|
if(isIntegral!T)
|
|
{
|
|
T carryBit = 0;
|
|
for(size_t i = 0; i < a.length; ++i) {
|
|
T b = a[i];
|
|
a[i] >>= 1;
|
|
a[i] |= carryBit;
|
|
carryBit = cast(T)(b << (T.sizeof * 8 - 1));
|
|
}
|
|
}
|
|
|
|
// test right shift with bytes
|
|
unittest {
|
|
ubyte[] a = [0xf1,0x83,0x01];
|
|
shiftRight(a);
|
|
assert(a == [0x78,0xc1,0x80], "right shift failed");
|
|
}
|
|
|
|
// test shiftRight
|
|
unittest {
|
|
|
|
ubyte[16] a = cast(immutable ubyte[16]) x"59ed3f2bb1a0aaa07c9f56c6a504647b";
|
|
foreach(i;0..8) {
|
|
shiftRight(a);
|
|
}
|
|
|
|
assert(a == x"0059ed3f2bb1a0aaa07c9f56c6a50464", "right shift failed");
|
|
}
|
|
|
|
// with ints
|
|
unittest {
|
|
uint[] a = [0xfedcba98,0x76543210];
|
|
foreach(i;0..8) {
|
|
shiftRight(a);
|
|
}
|
|
assert(a == [0x00fedcba,0x98765432], "right shift failed");
|
|
}
|
|
|
|
// with longs
|
|
unittest {
|
|
ulong[] a = [0x59ed3f2bb1a0aaa0,0x7c9f56c6a504647b];
|
|
foreach(i;0..8) {
|
|
shiftRight(a);
|
|
}
|
|
assert(a == [0x0059ed3f2bb1a0aa,0xa07c9f56c6a50464], "right shift failed");
|
|
}
|
|
|
|
/**
|
|
* Shift big endian number a 8 bits to the right.
|
|
*/
|
|
static void shiftRight8(T)(T[] a) nothrow @nogc {
|
|
T carryBit = 0;
|
|
for(size_t i = 0; i < a.length; ++i) {
|
|
T b = a[i];
|
|
a[i] >>= 8;
|
|
a[i] |= carryBit;
|
|
carryBit = cast(T)(b << (T.sizeof * 8 - 8));
|
|
}
|
|
}
|
|
|
|
// static void shiftRight(T)(T[] a, ubyte n) nothrow @nogc {
|
|
// T carryBit = 0;
|
|
// for(size_t i = 0; i < a.length; ++i) {
|
|
// T b = a[i];
|
|
// a[i] >>= n;
|
|
// a[i] |= carryBit;
|
|
// carryBit = cast(T)(b << (T.sizeof * 8 - n));
|
|
// }
|
|
// }
|
|
|
|
|
|
// static void shiftRight(ubyte[] a, ubyte n) nothrow @nogc {
|
|
// shiftRight(cast(uint[])a, n);
|
|
// }
|
|
|
|
// test shiftRight8()
|
|
unittest {
|
|
ubyte[16] a = cast(immutable ubyte[16])x"59ed3f2bb1a0aaa07c9f56c6a504647b";
|
|
ubyte[16] b = a;
|
|
foreach(i;0..8) {
|
|
shiftRight(a);
|
|
}
|
|
|
|
shiftRight8(b);
|
|
|
|
assert(a == b, "right shift by 8 bits failed");
|
|
}
|
|
|
|
} |