Commit | Line | Data |
---|---|---|
553d59fe MW |
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() |