| 1 | ### -*-python-*- |
| 2 | ### |
| 3 | ### Testing finite-field functionality |
| 4 | ### |
| 5 | ### (c) 2019 Straylight/Edgeware |
| 6 | ### |
| 7 | |
| 8 | ###----- Licensing notice --------------------------------------------------- |
| 9 | ### |
| 10 | ### This file is part of the Python interface to Catacomb. |
| 11 | ### |
| 12 | ### Catacomb/Python is free software: you can redistribute it and/or |
| 13 | ### modify it under the terms of the GNU General Public License as |
| 14 | ### published by the Free Software Foundation; either version 2 of the |
| 15 | ### License, or (at your option) any later version. |
| 16 | ### |
| 17 | ### Catacomb/Python is distributed in the hope that it will be useful, but |
| 18 | ### WITHOUT ANY WARRANTY; without even the implied warranty of |
| 19 | ### MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| 20 | ### General Public License for more details. |
| 21 | ### |
| 22 | ### You should have received a copy of the GNU General Public License |
| 23 | ### along with Catacomb/Python. If not, write to the Free Software |
| 24 | ### Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, |
| 25 | ### USA. |
| 26 | |
| 27 | ###-------------------------------------------------------------------------- |
| 28 | ### Imported modules. |
| 29 | |
| 30 | import itertools as I |
| 31 | |
| 32 | import catacomb as C |
| 33 | import unittest as U |
| 34 | import testutils as T |
| 35 | |
| 36 | ###-------------------------------------------------------------------------- |
| 37 | class TestFields (T.GenericTestMixin): |
| 38 | """Test finite fields.""" |
| 39 | |
| 40 | def _test_field(me, k): |
| 41 | |
| 42 | ## Some initial values. |
| 43 | zero = k.zero |
| 44 | one = k.one |
| 45 | x = k(2760820866) |
| 46 | y = k(3757175895) |
| 47 | z = k(920571320) |
| 48 | |
| 49 | ## Check that they're all different. |
| 50 | v = [zero, one, x, y, z] |
| 51 | for i in T.range(len(v)): |
| 52 | for j in T.range(len(v)): |
| 53 | if i == j: me.assertEqual(v[i], v[j]) |
| 54 | else: me.assertNotEqual(v[i], v[j]) |
| 55 | |
| 56 | ## Basic arithmetic. Knowing the answers is too hard. For now, just |
| 57 | ## check that the field laws hold. |
| 58 | t = x + y; me.assertEqual(t - y, x); me.assertEqual(t - x, y) |
| 59 | t = x - y; me.assertEqual(t + y, x) |
| 60 | t = x*y; me.assertEqual(t/x, y); me.assertEqual(t/y, x) |
| 61 | me.assertEqual(+x, x) |
| 62 | me.assertEqual(x + -x, zero) |
| 63 | me.assertEqual(x - x, zero) |
| 64 | me.assertEqual(x*x.inv(), one) |
| 65 | me.assertEqual(x/x, one) |
| 66 | me.assertRaises(ZeroDivisionError, k.inv, zero) |
| 67 | |
| 68 | ## Exponentiation. At least we know the group exponent. |
| 69 | me.assertEqual(x**(k.q - 1), one) |
| 70 | |
| 71 | ## Comparisons. We've already done equality and inequality, and nothing |
| 72 | ## else should work. |
| 73 | me.assertRaises(TypeError, T.lt, x, y) |
| 74 | me.assertRaises(TypeError, T.le, x, y) |
| 75 | me.assertRaises(TypeError, T.ge, x, y) |
| 76 | me.assertRaises(TypeError, T.gt, x, y) |
| 77 | |
| 78 | ## Conversion back to integer. |
| 79 | me.assertEqual(int(x), 2760820866) |
| 80 | |
| 81 | ## Square and square-root. In a prime field, we may need to search |
| 82 | ## around to find a quadratic residue. In binary fields, squaring is |
| 83 | ## linear, and every element has a unique square root. |
| 84 | me.assertEqual(x*x, x.sqr()) |
| 85 | for i in T.range(128): |
| 86 | t = k(int(x) + i) |
| 87 | q = t.sqrt() |
| 88 | if q is not None: break |
| 89 | else: |
| 90 | me.fail("no quadratic residue found") |
| 91 | me.assertEqual(q.sqr(), t) |
| 92 | |
| 93 | ## Hex and octal conversions. |
| 94 | me.assertEqual(hex(x), hex(T.long(x.value)).rstrip("L")) |
| 95 | me.assertEqual(oct(x), oct(T.long(x.value)).rstrip("L")) |
| 96 | |
| 97 | if isinstance(k, C.PrimeField): |
| 98 | |
| 99 | ## Representation. |
| 100 | me.assertEqual(type(x.value), C.MP) |
| 101 | me.assertEqual(k.type, C.FTY_PRIME) |
| 102 | |
| 103 | ## Properties. |
| 104 | me.assertEqual(k.p, k.q) |
| 105 | |
| 106 | ## Operations. |
| 107 | me.assertEqual(x.dbl(), 2*x) |
| 108 | me.assertEqual(x.tpl(), 3*x) |
| 109 | me.assertEqual(x.qdl(), 4*x) |
| 110 | me.assertEqual(x.hlv(), x/2) |
| 111 | |
| 112 | else: |
| 113 | |
| 114 | ## Representation. |
| 115 | me.assertEqual(type(x.value), C.GF) |
| 116 | me.assertEqual(k.type, C.FTY_BINARY) |
| 117 | |
| 118 | ## Properties. |
| 119 | me.assertEqual(k.m, k.nbits) |
| 120 | me.assertEqual(k.p.degree, k.m) |
| 121 | if isinstance(k, C.BinNormField): |
| 122 | l = C.BinPolyField(k.p) |
| 123 | a, b = l.zero, l(k.beta) |
| 124 | for i in T.range(k.m): |
| 125 | a += b |
| 126 | b = b.sqr() |
| 127 | me.assertEqual(a, l.one) |
| 128 | |
| 129 | ## Operations. |
| 130 | for i in T.range(128): |
| 131 | t = k(int(x) + i) |
| 132 | u = t.quadsolve() |
| 133 | if u is not None: break |
| 134 | else: |
| 135 | me.fail("no quadratic solution found") |
| 136 | me.assertEqual(u*u + u, t) |
| 137 | |
| 138 | ## Encoding. |
| 139 | me.assertEqual(k.nbits, (k.q - 1).nbits) |
| 140 | me.assertEqual(k.noctets, (k.q - 1).noctets) |
| 141 | |
| 142 | TestFields.generate_testcases \ |
| 143 | (("%s-%s" % (name, suffix), getfn(C.eccurves[name])) |
| 144 | for suffix, getfn in [("coords", lambda einfo: einfo.curve.field), |
| 145 | ("scalars", lambda einfo: C.PrimeField(einfo.r))] |
| 146 | for name in ["nist-p256", "nist-k233", "nist-b163", "nist-b283n"]) |
| 147 | |
| 148 | ###----- That's all, folks -------------------------------------------------- |
| 149 | |
| 150 | if __name__ == "__main__": U.main() |