16  * interprets the message as the coefficients of a polynomial in GF(2^128) and
17  * evaluates that polynomial at a secret point.  POLYVAL has a simple
18  * mathematical relationship with GHASH, but it uses a better field convention
21  * POLYVAL is not a cryptographic hash function, and it should be used only by
30  * This file provides a library API for POLYVAL.  This API can delegate to
31  * either a generic implementation or an architecture-optimized implementation.
34  * to GF(2^128) multiplication.  That approach is not constant-time and requires
35  * a lot of memory.  Instead, we use a different approach which emulates
40  * "holes" trick and a presentation by Shay Gueron
42  * 256-bit => 128-bit reduction algorithm.
47 /* Do a 64 x 64 => 128 bit carryless multiplication. */
48 static void clmul64(u64 a, u64 b, u64 *out_lo, u64 *out_hi)  in clmul64()  argument
53 	 * written out as a series of additions in the schoolbook manner.  in clmul64()
60 	 * Instead, mask off 4 bits from one multiplicand, giving a max of 15  in clmul64()
63 	u64 a0 = a & 0x1111111111111110;  in clmul64()
64 	u64 a1 = a & 0x2222222222222220;  in clmul64()
65 	u64 a2 = a & 0x4444444444444440;  in clmul64()
66 	u64 a3 = a & 0x8888888888888880;  in clmul64()
73 	/* Multiply the high 60 bits of @a by @b. */  in clmul64()
83 	/* Multiply the low 4 bits of @a by @b. */  in clmul64()
84 	u64 e0 = -(a & 1) & b;  in clmul64()
85 	u64 e1 = -((a >> 1) & 1) & b;  in clmul64()
86 	u64 e2 = -((a >> 2) & 1) & b;  in clmul64()
87 	u64 e3 = -((a >> 3) & 1) & b;  in clmul64()
104 /* Do a 32 x 32 => 64 bit carryless multiplication. */
105 static u64 clmul32(u32 a, u32 b)  in clmul32()  argument
110 	 * out as a series of additions in the schoolbook manner.  The value 8  in clmul32()
113 	u32 a0 = a & 0x11111111;  in clmul32()
114 	u32 a1 = a & 0x22222222;  in clmul32()
115 	u32 a2 = a & 0x44444444;  in clmul32()
116 	u32 a3 = a & 0x88888888;  in clmul32()
139 /* Do a 64 x 64 => 128 bit carryless multiplication. */
140 static void clmul64(u64 a, u64 b, u64 *out_lo, u64 *out_hi)  in clmul64()  argument
142 	u32 a_lo = (u32)a;  in clmul64()
143 	u32 a_hi = a >> 32;  in clmul64()
157 /* Compute @a = @a * @b * x^-128 in the POLYVAL field. */
159 polyval_mul_generic(struct polyval_elem *a, const struct polyval_elem *b)  in polyval_mul_generic()  argument
164 	 * Carryless-multiply @a by @b using Karatsuba multiplication.  Store  in polyval_mul_generic()
167 	clmul64(le64_to_cpu(a->lo), le64_to_cpu(b->lo), &c0, &c1);  in polyval_mul_generic()
168 	clmul64(le64_to_cpu(a->hi), le64_to_cpu(b->hi), &c2, &c3);  in polyval_mul_generic()
169 	clmul64(le64_to_cpu(a->lo ^ a->hi), le64_to_cpu(b->lo ^ b->hi),  in polyval_mul_generic()
177 	 * Cancel out the low 128 bits of the product by adding multiples of  in polyval_mul_generic()
178 	 * G(x) = x^128 + x^127 + x^126 + x^121 + 1.  Do this in two steps, each  in polyval_mul_generic()
180 	 * parts: 1, x^64 * (x^63 + x^62 + x^57), and x^128 * 1.  in polyval_mul_generic()
203 	/* Return (c2, c3).  This implicitly multiplies by x^-128. */  in polyval_mul_generic()
204 	a->lo = cpu_to_le64(c2);  in polyval_mul_generic()
205 	a->hi = cpu_to_le64(c3);  in polyval_mul_generic()
232  * polyval_mul_generic() and polyval_blocks_generic() take the key as a
233  * polyval_elem rather than a polyval_key, so that arch-optimized
234  * implementations with a different key format can use it as a fallback (if they