mdw@git.distorted.org.uk Git - catacomb-python/blob - t/t-ec.py

   1 ### -*- mode: python, coding: utf-8 -*-
   2 ###
   3 ### Testing elliptic curve 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 catacomb as C
  31 import unittest as U
  32 import testutils as T
  33
  34 k = C.PrimeField(19)
  35 E = k.ec(-3, 6)
  36 P = E(0) # order 26
  37
  38 kk = C.BinPolyField(0x13)
  39 EE = kk.ec(1, 8)
  40 PP = EE(8) # order 20
  41
  42 ###--------------------------------------------------------------------------
  43 class TestCurvelessPoints (U.TestCase):
  44   """Test handling of points without an explicit curve."""
  45
  46   def test(me):
  47
  48     ## Construction.
  49     O = C.ECPt(); me.assertFalse(O)
  50     P = C.ECPt(12345, 67890); me.assertTrue(P)
  51     Q = C.ECPt(23456, 78901); me.assertTrue(Q); me.assertNotEqual(P, Q)
  52     R = C.ECPt(O); me.assertFalse(R); me.assertEqual(O, R); me.assertNotEqual(P, R)
  53     R = C.ECPt(None); me.assertFalse(R); me.assertEqual(O, R)
  54     me.assertEqual(C.ECPt("12345, 67890"), P)
  55     me.assertEqual(C.ECPt((12345, 67890)), P)
  56     me.assertRaises(TypeError, C.ECPt, ())
  57     me.assertRaises(TypeError, C.ECPt, (1234,))
  58     me.assertRaises(TypeError, C.ECPt, (1, 2, 3, 4))
  59     me.assertRaises(ValueError, C.ECPt, "12345")
  60     me.assertRaises(ValueError, C.ECPt, "12345,")
  61     me.assertRaises(ValueError, C.ECPt, "12345, xyzzy")
  62     me.assertRaises(ValueError, C.ECPt, "12345, 67890!??")
  63     me.assertRaises(ValueError, C.ECPt, (1, 2, 3))
  64     me.assertRaises(TypeError, C.ECPt, 1, 2, 3)
  65     me.assertRaises(TypeError, C.ECPt, 1234)
  66     me.assertRaises(TypeError, C.ECPt, object())
  67     me.assertRaises(TypeError, C.ECPt, 1, None)
  68     #me.assertRaises(TypeError, C.ECPt, (1, None))
  69
  70     ## Arithmetic shouldn't work.
  71     me.assertRaises(TypeError, T.neg, P)
  72     me.assertRaises(TypeError, T.add, P, Q)
  73
  74     ## Attributes.  We only have raw integer access.
  75     me.assertTrue(P.point is P)
  76     me.assertEqual(P.ix, 12345)
  77     me.assertEqual(P.iy, 67890)
  78     me.assertEqual(P.tobuf(), C.bytes("000230390003010932"))
  79     me.assertRaises(AttributeError, lambda: P.curve)
  80     me.assertRaises(AttributeError, lambda: P.x)
  81     me.assertRaises(AttributeError, lambda: P.y)
  82     me.assertRaises(AttributeError, lambda: P._x)
  83     me.assertRaises(AttributeError, lambda: P._y)
  84     me.assertRaises(AttributeError, lambda: P._z)
  85
  86     ## Encoding and decoding.
  87     P = C.ECPt(254, 291)
  88     me.assertEqual(O.tobuf(), C.bytes("0000"))
  89     me.assertEqual(C.ECPt(0, 0).tobuf(), C.bytes("000100000100"))
  90     me.assertEqual(P.tobuf(), C.bytes("0001fe00020123"))
  91     me.assertEqual(C.ECPt.frombuf(C.bytes("0001fe000201233f")),
  92                    (P, C.bytes("3f")))
  93     me.assertRaises(ValueError, C.ECPt.frombuf, C.bytes("0001fe000201"))
  94
  95     ## String conversion and parsing.
  96     me.assertEqual(str(P), "(254, 291)")
  97     me.assertEqual(C.ECPt.parse("254, 291)"), (P, ")"))
  98     me.assertEqual(C.ECPt.parse("(254, 291)"), (P, ""))
  99     me.assertRaises(ValueError, C.ECPt.parse, "(254, 291")
 100
 101 ###--------------------------------------------------------------------------
 102 class TestCurves (T.GenericTestMixin):
 103   """Test elliptic curves."""
 104
 105   def test_compare(me):
 106     me.assertEqual(E, E)
 107     E1 = k.ec(-3, 6)
 108     me.assertFalse(E is E1)
 109     me.assertEqual(E, E1)
 110     me.assertNotEqual(E, EE)
 111     me.assertNotEqual(E, [])
 112
 113   def _test_curve(me, einfo, checkfail = False):
 114
 115     ## Some useful values.
 116     E = einfo.curve
 117     P = einfo.G
 118     O = E()
 119     n = einfo.r
 120     h = einfo.h
 121     k = E.field
 122     me.assertTrue(n.primep()); l = C.NicePrimeField(n)
 123
 124     ## Check that things are basically sane.
 125     me.assertFalse(O)
 126     me.assertTrue(P)
 127     me.assertTrue(n)
 128     nP = n*P; me.assertFalse(nP); me.assertEqual(nP, O)
 129
 130     ## Check point construction.
 131     me.assertEqual(type(P.ix), C.MP)
 132     me.assertEqual(type(P.iy), C.MP)
 133     me.assertTrue(isinstance(P.x, C.FE))
 134     me.assertTrue(isinstance(P.y, C.FE))
 135     me.assertTrue(isinstance(P._x, C.FE))
 136     me.assertTrue(isinstance(P._y, C.FE))
 137     if isinstance(E, C.ECPrimeProjCurve) or isinstance(E, C.ECBinProjCurve):
 138       me.assertTrue(isinstance(P._z, C.FE))
 139     else:
 140       me.assertEqual(P._z, None)
 141     me.assertEqual(E(None), O)
 142     me.assertEqual(E(P.x, P.y), P)
 143     me.assertEqual(E((P.x, P.y)), P)
 144     me.assertEqual(E(P._x, P._y, P._z), P)
 145     me.assertEqual(E((P._x, P._y, P._z)), P)
 146     Q = E(P.point); me.assertEqual(type(Q), E); me.assertEqual(Q, P)
 147     me.assertEqual(E("%s, %s" % (P.ix, P.iy)), P)
 148     me.assertRaises(ValueError, E, "1234")
 149     me.assertRaises(ValueError, E, "1234,")
 150     me.assertRaises(ValueError, E, "1234, 5678?")
 151     me.assertRaises(TypeError, E, 1, None)
 152     Q = E(P.ix); me.assertTrue(Q == P or Q == -P)
 153     for i in T.range(128):
 154       x = P.ix + i
 155       try: E(x)
 156       except ValueError: badx = x; break
 157     else:
 158       me.fail("no off-curve point found")
 159
 160     ## Attributes.
 161     me.assertEqual(P.ix, P.point.ix)
 162     me.assertEqual(P.iy, P.point.iy)
 163     me.assertEqual(P.x, k(P.point.ix))
 164     me.assertEqual(P.y, k(P.point.iy))
 165     R = 6*P
 166     if isinstance(E, C.ECPrimeProjCurve) or isinstance(E, C.ECBinProjCurve):
 167       me.assertEqual(P._z, k.one)
 168       me.assertEqual(R._x, R.x*R._z**2)
 169       me.assertEqual(R._y, R.y*R._z**3)
 170       me.assertNotEqual(R._z, k.one)
 171     else:
 172       me.assertEqual(P._z, None)
 173       me.assertEqual(R._x, R.x)
 174       me.assertEqual(R._y, R.y)
 175       me.assertEqual(R._z, None)
 176     me.assertEqual(R.curve, E)
 177
 178     ## Arithmetic.
 179     Q = 17*P
 180     me.assertEqual(Q, P*17)
 181     me.assertEqual(-Q, (n - 17)*P)
 182     me.assertEqual(Q + R, 23*P)
 183     me.assertEqual(Q + R.point, 23*P)
 184     me.assertRaises(TypeError, T.add, Q.point, R.point)
 185     me.assertRaises(TypeError, T.mul, kk(1), Q)
 186     me.assertEqual(Q - R, 11*P)
 187     me.assertEqual(l(17)*P, Q)
 188     me.assertEqual(P*l(17), Q)
 189
 190     ## Ordering.
 191     me.assertTrue(P == P)
 192     me.assertTrue(P != Q)
 193     me.assertRaises(TypeError, T.lt, P, Q)
 194     me.assertRaises(TypeError, T.le, P, Q)
 195     me.assertRaises(TypeError, T.ge, P, Q)
 196     me.assertRaises(TypeError, T.gt, P, Q)
 197
 198     ## Encoding.
 199     Z0 = C.ByteString.zero(0)
 200     Z1 = C.ByteString.zero(1)
 201     me.assertEqual(O.ec2osp(), Z1)
 202     me.assertEqual(E.os2ecp(Z1), (O, Z0))
 203     t = C.WriteBuffer() \
 204          .putu8(0x04) \
 205          .put(P.ix.storeb(k.noctets)) \
 206          .put(P.iy.storeb(k.noctets)) \
 207          .contents
 208     me.assertEqual(P.ec2osp(), t)
 209     me.assertEqual(C.WriteBuffer().putecptraw(P).contents, t)
 210     me.assertEqual(C.WriteBuffer().ec2osp(P).contents, t)
 211     me.assertEqual(E.os2ecp(t), (P, Z0))
 212     me.assertEqual(C.ReadBuffer(t).getecptraw(E), P)
 213     me.assertEqual(C.ReadBuffer(t).os2ecp(E), P)
 214     if isinstance(k, C.PrimeField): ybit = int(P.iy&1)
 215     else:
 216       try: ybit = int((P.y/P.x).value&C.GF(1))
 217       except ZeroDivisionError: ybit = 0
 218     t = C.WriteBuffer() \
 219          .putu8(0x02 | ybit) \
 220          .put(P.ix.storeb(k.noctets)) \
 221          .contents
 222     me.assertEqual(P.ec2osp(C.EC_LSB), t)
 223     me.assertEqual(C.WriteBuffer().ec2osp(P, C.EC_LSB).contents, t)
 224     me.assertEqual(E.os2ecp(t, C.EC_LSB), (P, Z0))
 225     me.assertEqual(C.ReadBuffer(t).os2ecp(E, C.EC_LSB), P)
 226
 227     ## Curve methods.
 228     Q = E.find(P.x); me.assertTrue(Q == P or Q == -P)
 229     Q = E.find(P.ix); me.assertTrue(Q == P or Q == -P)
 230     me.assertRaises(ValueError, E.find, badx)
 231     for i in T.range(128):
 232       if E.rand() != P: break
 233     else:
 234       me.fail("random point always gives me P")
 235     for i in T.range(128):
 236       R = E.rand(C.LCRand(i))
 237       if R != P: break
 238     else:
 239       me.fail("random point always gives me P")
 240     me.assertEqual(R, E.rand(C.LCRand(i)))
 241     me.assertEqual(E.parse("%s, %s!xyzzy" % (P.ix, P.iy)), (P, "!xyzzy"))
 242
 243     ## Simultaneous multiplication.
 244     Q, R, S = 5*P, 7*P, 11*P
 245     me.assertEqual(E.mmul([Q, 9, R, 8, S, 5]), 156*P)
 246     me.assertEqual(E.mmul(Q, 9, R, 8, S, 5), 156*P)
 247
 248     ## Test other curve info things while we're here.
 249     if not checkfail: einfo.check()
 250     else: me.assertRaises(ValueError, einfo.check)
 251
 252   def test_tinycurves(me):
 253     me._test_curve(C.ECInfo(E, 2*P, 13, 2), checkfail = True)
 254     ei, _ = C.ECInfo.parse("binpoly: 0x13; bin: 0x01, 0x08; 0x02, 0x0c: 5*4")
 255     me._test_curve(ei, checkfail = True)
 256
 257 TestCurves.generate_testcases((name, C.eccurves[name]) for name in
 258   ["nist-p256", "nist-k233", "nist-b163", "nist-b283n"])
 259
 260 ###----- That's all, folks --------------------------------------------------
 261
 262 if __name__ == "__main__": U.main()