2 * Copyright (c) 2017 Thomas Pornin <pornin@bolet.org>
4 * Permission is hereby granted, free of charge, to any person obtaining
5 * a copy of this software and associated documentation files (the
6 * "Software"), to deal in the Software without restriction, including
7 * without limitation the rights to use, copy, modify, merge, publish,
8 * distribute, sublicense, and/or sell copies of the Software, and to
9 * permit persons to whom the Software is furnished to do so, subject to
10 * the following conditions:
12 * The above copyright notice and this permission notice shall be
13 * included in all copies or substantial portions of the Software.
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
16 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
17 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
18 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
19 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
20 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
21 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
30 * Helper methods for handling big integers.
36 * Normalize a big integer to its minimal size encoding
37 * (unsigned big-endian). This function always returns
40 internal static byte[] NormalizeBE(byte[] val)
42 return NormalizeBE(val, false);
46 * Normalize a big integer to its minimal size encoding
47 * (big-endian). If 'signed' is true, then room for a sign
48 * bit (of value 0) is kept. Note that even if 'signed' is
49 * true, the source array is assumed positive (i.e. unsigned).
50 * This function always returns a new, fresh array.
52 internal static byte[] NormalizeBE(byte[] val, bool signed)
56 while (i < n && val[i] == 0) {
59 if (signed && (i == n || val[i] >= 0x80)) {
62 byte[] nval = new byte[n - i];
64 Array.Copy(val, 0, nval, 1, n);
66 Array.Copy(val, i, nval, 0, n - i);
72 * Compute the exact bit length of an integer (unsigned big-endian
75 internal static int BitLength(byte[] val)
77 return BitLength(val, 0, val.Length);
81 * Compute the exact bit length of an integer (unsigned big-endian
84 internal static int BitLength(byte[] val, int off, int len)
89 for (int i = 0; i < len; i ++) {
90 int b = (int)(val[off + i] & nf);
91 uint bnz = nf & (uint)((b | -b) >> 31);
92 tlen |= (int)bnz & (len - i);
96 return (tlen << 3) - 8 + BitLength(hb);
100 * Compute the exact bit length of an integer (in a 32-bit word).
102 internal static int BitLength(uint w)
105 for (int f = 16; f > 0; f >>= 1) {
108 uint ctl = (uint)((x | -x) >> 31);
109 w = (w & ~ctl) | (nw & ctl);
110 bitLen += f & (int)ctl;
112 return bitLen + (int)w;
116 * Compute a simple hashcode on an integer. The returned value
117 * depends on the numerical value (assuming that the array is
118 * in unsigned big-endian representation) but not on the presence
119 * of leading zeros. The memory access pattern of this method
120 * depends only on the length of the array x.
122 public static uint HashInt(byte[] x)
125 * We simply compute x modulo 4294967291 (0xFFFFFFFB),
126 * which is a prime number. The value is injected byte
127 * by byte, and we keep the running state on two words
128 * (16 bits per word, but we allow a few extra bits of
131 * For all iterations, "hi" contains at most 16 bits,
132 * and "lo" is less than 16*2^16 (i.e. it fits on 20 bits).
135 for (int i = 0; i < x.Length; i ++) {
136 hi = (hi << 8) + (lo >> 8);
137 lo = (lo & 0xFF) << 8;
138 lo += (uint)5 * (hi >> 16) + (uint)x[i];
143 * Final reduction. We first propagate the extra bits
144 * from the low word, which may induce one extra bit
145 * on the high word, which we propagate back.
149 lo += (uint)5 * (hi >> 16);
153 * If we have extra bits at that point, then this means
154 * that adding a 4-bits-or-less value to "hi" implied
155 * a carry, so now "hi" is small and the addition below
156 * won't imply a carry.
162 * At that point, value is on 32 bits. We want to do a
163 * final reduction for 0xFFFFFFFB..0xFFFFFFFF. Value is
164 * in this range if and only if 'hi' is 0xFFFF and 'lo'
165 * is at least 0xFFFB.
167 int z = (int)(((hi + 1) >> 16) | ((lo + 5) >> 16));
168 return (hi << 16) + lo + ((uint)5 & (uint)((z | -z) >> 31));
172 * Add two integers together. The two operands a[] and b[]
173 * use big-endian encoding. The returned product array is newly
174 * allocated and normalized. The operands are not modified. The
175 * operands need not be normalized and may be the same array.
177 public static byte[] Add(byte[] a, byte[] b)
181 int xLen = Math.Max(aLen, bLen) + 1;
182 byte[] x = new byte[xLen];
184 for (int i = 0; i < xLen; i ++) {
185 int wa = (i < aLen) ? (int)a[aLen - 1 - i] : 0;
186 int wb = (i < bLen) ? (int)b[bLen - 1 - i] : 0;
187 int wx = wa + wb + cc;
188 x[xLen - 1 - i] = (byte)wx;
191 return NormalizeBE(x);
195 * Subtract integer b[] from integer a[]. Both operands use
196 * big-endian encoding. If b[] turns out to be greater than a[],
197 * then this method returns null.
199 public static byte[] Sub(byte[] a, byte[] b)
203 int xLen = Math.Max(aLen, bLen);
204 byte[] x = new byte[aLen];
206 for (int i = 0; i < xLen; i ++) {
207 int wa = (i < aLen) ? (int)a[aLen - 1 - i] : 0;
208 int wb = (i < bLen) ? (int)b[bLen - 1 - i] : 0;
209 int wx = wa - wb - cc;
210 x[xLen - 1 - i] = (byte)wx;
216 return NormalizeBE(x);
220 * Multiply two integers together. The two operands a[] and b[]
221 * use big-endian encoding. The returned product array is newly
222 * allocated and normalized. The operands are not modified. The
223 * operands need not be normalized and may be the same array.
225 * The two source operands MUST NOT have length larger than
228 public static byte[] Mul(byte[] a, byte[] b)
232 if (a.Length > 32767 || b.Length > 32767) {
233 throw new CryptoException(
234 "Operands too large for multiplication");
238 int xLen = aLen + bLen;
239 uint[] x = new uint[xLen];
240 for (int i = 0; i < aLen; i ++) {
241 uint u = (uint)a[aLen - 1 - i];
242 for (int j = 0; j < bLen; j ++) {
243 x[i + j] += u * (uint)b[bLen - 1 - j];
246 byte[] y = new byte[xLen];
248 for (int i = 0; i < xLen; i ++) {
250 y[xLen - 1 - i] = (byte)w;
254 throw new CryptoException(
255 "Multiplication: internal error");
257 return NormalizeBE(y);
261 * Compare two integers (unsigned, big-endian). Returned value
262 * is -1, 0 or 1, depending on whether a[] is lower than, equal
263 * to, or greater then b[]. a[] and b[] may have distinct sizes.
265 * Memory access pattern depends on the most significant index
266 * (i.e. lowest index, since we use big-endian convention) for
267 * which the two values differ.
269 public static int Compare(byte[] a, byte[] b)
273 for (int i = Math.Max(a.Length, b.Length); i > 0; i --) {
274 byte xa = (i > na) ? (byte)0x00 : a[na - i];
275 byte xb = (i > nb) ? (byte)0x00 : b[nb - i];
277 return xa < xb ? -1 : 1;
284 * Compare two integers (unsigned, big-endian). Returned value
285 * is -1, 0 or 1, depending on whether a[] is lower than, equal
286 * to, or greater then b[]. a[] and b[] may have distinct sizes.
288 * This method's memory access pattern is independent of the
289 * contents of the a[] and b[] arrays.
291 public static int CompareCT(byte[] a, byte[] b)
297 for (int i = Math.Max(a.Length, b.Length); i > 0; i --) {
298 int xa = (i > na) ? 0 : a[na - i];
299 int xb = (i > nb) ? 0 : b[nb - i];
300 lt |= (uint)((xa - xb) >> 31) & ~(lt | gt);
301 gt |= (uint)((xb - xa) >> 31) & ~(lt | gt);
303 return (int)lt | -(int)gt;
307 * Check whether an integer (unsigned, big-endian) is zero.
309 public static bool IsZero(byte[] x)
311 return IsZeroCT(x) != 0;
315 * Check whether an integer (unsigned, big-endian) is zero.
316 * Memory access pattern depends only on the length of x[].
317 * Returned value is 0xFFFFFFFF is the value is zero, 0x00000000
320 public static uint IsZeroCT(byte[] x)
323 for (int i = 0; i < x.Length; i ++) {
326 return ~(uint)((z | -z) >> 31);
330 * Check whether an integer (unsigned, big-endian) is one.
332 public static bool IsOne(byte[] x)
334 return IsOneCT(x) != 0;
338 * Check whether an integer (unsigned, big-endian) is one.
339 * Memory access pattern depends only on the length of x[].
340 * Returned value is 0xFFFFFFFF is the value is one, 0x00000000
343 public static uint IsOneCT(byte[] x)
350 for (int i = 0; i < n - 1; i ++) {
354 return ~(uint)((z | -z) >> 31);
358 * Check whether the provided integer is odd (the source integer
359 * is in unsigned big-endian notation).
361 public static bool IsOdd(byte[] x)
363 return x.Length > 0 && (x[x.Length - 1] & 0x01) != 0;
367 * Compute a modular exponentiation (x^e mod n). Conditions:
368 * -- x[], e[] and n[] use big-endian encoding.
369 * -- x[] must be numerically smaller than n[].
370 * -- n[] must be odd.
371 * Result is returned as a newly allocated array of bytes of
372 * the same length as n[].
374 public static byte[] ModPow(byte[] x, byte[] e, byte[] n)
376 ModInt mx = new ModInt(n);
383 * Create a new random integer, chosen uniformly among integers
384 * modulo the provided max[].
386 public static byte[] RandInt(byte[] max)
388 return RandInt(max, false);
392 * Create a new random integer, chosen uniformly among non-zero
393 * integers modulo the provided max[].
395 public static byte[] RandIntNZ(byte[] max)
397 return RandInt(max, true);
400 static byte[] RandInt(byte[] max, bool notZero)
402 int mlen = BitLength(max);
403 if (mlen == 0 || (notZero && mlen == 1)) {
404 throw new CryptoException(
405 "Null maximum for random generation");
407 byte[] x = new byte[(mlen + 7) >> 3];
408 byte hm = (byte)(0xFF >> ((8 - mlen) & 7));
412 if (notZero && IsZero(x)) {
415 if (CompareCT(x, max) >= 0) {
423 * Create a new random prime with a specific length (in bits). The
424 * returned prime will have its two top bits set, _and_ its two
425 * least significant bits set as well. The size parameter must be
426 * greater than or equal to 9 (that is, the unsigned encoding of
427 * the prime will need at least two bytes).
429 public static byte[] RandPrime(int size)
432 throw new CryptoException(
433 "Invalid size for prime generation");
435 int len = (size + 7) >> 3;
436 byte[] buf = new byte[len];
437 int hm1 = 0xFFFF >> ((len << 3) - size);
438 int hm2 = 0xC000 >> ((len << 3) - size);
441 buf[len - 1] |= (byte)0x03;
442 int x = (buf[0] << 8) | buf[1];
445 buf[0] = (byte)(x >> 8);
454 * A bit-field for primes in the 0..255 range.
456 static uint[] SMALL_PRIMES_BF = {
457 0xA08A28AC, 0x28208A20, 0x02088288, 0x800228A2,
458 0x20A00A08, 0x80282088, 0x800800A2, 0x08028228
461 static bool IsSmallPrime(int x)
463 if (x < 2 || x >= 256) {
466 return ((SMALL_PRIMES_BF[x >> 5] >> (x & 31)) & (uint)1) != 0;
470 * Test an integer for primality. This function runs up to 50
471 * Miller-Rabin rounds, which is a lot of overkill but ensures
472 * that non-primes will be reliably detected (with overwhelming
473 * probability) even with maliciously crafted inputs. "Normal"
474 * non-primes will be detected most of the time at the first
477 * This function is not constant-time.
479 public static bool IsPrime(byte[] x)
486 * small primes (one byte) are known in a constant bit-field
487 * even numbers (larger than one byte) are non-primes
493 return IsSmallPrime(x[0]);
495 if ((x[x.Length - 1] & 0x01) == 0) {
500 * Perform some trial divisions by small primes.
502 for (int sp = 3; sp < 256; sp += 2) {
503 if (!IsSmallPrime(sp)) {
507 foreach (byte b in x) {
508 z = ((z << 8) + b) % sp;
516 * Run some Miller-Rabin rounds. We use as basis random
517 * integers that are one byte smaller than the modulus.
519 ModInt xm1 = new ModInt(x);
520 ModInt y = xm1.Dup();
523 byte[] e = xm1.Encode();
524 ModInt a = new ModInt(x);
525 byte[] buf = new byte[x.Length - 1];
526 for (int i = 0; i < 50; i ++) {
538 * Right-shift an array of bytes by some bits. The bit count MUST
539 * be positive or zero. Extra bits are dropped on the right, and
540 * left positions are filled with zeros.
542 public static void RShift(byte[] buf, int numBits)
544 RShift(buf, 0, buf.Length, numBits);
548 * Right-shift an array of bytes by some bits. The bit count MUST
549 * be positive or zero. Extra bits are dropped on the right, and
550 * left positions are filled with zeros.
552 public static void RShift(byte[] buf, int off, int len, int numBits)
555 int zlen = numBits >> 3;
557 for (int i = 0; i < len; i ++) {
562 Array.Copy(buf, off, buf, off + zlen, len - zlen);
563 for (int i = 0; i < zlen; i ++) {
572 for (int i = 0; i < len; i ++) {
573 int x = buf[off + i];
574 buf[off + i] = (byte)((x >> numBits) + cc);
575 cc = x << (8 - numBits);