mdw@git.distorted.org.uk Git - catacomb/blob - utils/curve25519.sage

   1 #! /usr/local/bin/sage
   2 ### -*- mode: python; coding: utf-8 -*-
   3
   4 ###--------------------------------------------------------------------------
   5 ### Define the field.
   6
   7 p = 2^255 - 19; k = GF(p)
   8
   9 ###--------------------------------------------------------------------------
  10 ### Arithmetic implementation.
  11
  12 def sqrn(x, n):
  13   for i in xrange(n): x = x*x
  14   return x
  15
  16 def inv(x):
  17   t2 = sqrn(x, 1)        #   1 | 2
  18   u = sqrn(t2, 2)        #   3 | 8
  19   t = u*x                #   4 | 9
  20   t11 = t*t2             #   5 | 11
  21   u = sqrn(t11, 1)       #   6 | 22
  22   t = u*t                #   7 | 2^5 - 1 = 31
  23   u = sqrn(t, 5)         #  12 | 2^10 - 2^5
  24   t2p10m1 = u*t          #  13 | 2^10 - 1
  25   u = sqrn(t2p10m1, 10)  #  23 | 2^20 - 2^10
  26   t = u*t2p10m1          #  24 | 2^20 - 1
  27   u = sqrn(t, 20)        #  44 | 2^40 - 2^20
  28   t = u*t                #  45 | 2^40 - 1
  29   u = sqrn(t, 10)        #  55 | 2^50 - 2^10
  30   t2p50m1 = u*t2p10m1    #  56 | 2^50 - 1
  31   u = sqrn(t2p50m1, 50)  # 106 | 2^100 - 2^50
  32   t = u*t2p50m1          # 107 | 2^100 - 1
  33   u = sqrn(t, 100)       # 207 | 2^200 - 2^100
  34   t = u*t                # 208 | 2^200 - 1
  35   u = sqrn(t, 50)        # 258 | 2^250 - 2^50
  36   t = u*t2p50m1          # 259 | 2^250 - 1
  37   u = sqrn(t, 5)         # 264 | 2^255 - 2^5
  38   t = u*t11              # 265 | 2^255 - 21
  39   return t
  40
  41 assert inv(k(9))*9 == 1
  42
  43 ###----- That's all, folks --------------------------------------------------