← Back to branch summary

~ubuntu-branches/ubuntu/utopic/electrum/utopic-proposed

« back to all changes in this revision

Viewing changes to ecdsa/ellipticcurve.py

  • Committer: Package Import Robot
  • Author(s): Tristan Seligmann
  • Date: 2013-12-11 11:52:51 UTC
  • mfrom: (1.1.1)
  • Revision ID: package-import@ubuntu.com-20131211115251-4r3dhaxvmqlg2ilf
Tags: 1.9.5-1
http://bugs.debian.org/730353
http://bugs.debian.org/727232
* New upstream release (closes: #730353).
  - Contacts bugfix included in 1.8.1 (closes: #727232).
* Acknowledge NMU.
* Update watch file.
* Add myself to Uploaders.
* Update mk18n.py patch and ship new translations file.
* Bump dependency on python-ecdsa for secp256k1.
* Remove deprecated CDBS dependency management.

Show diffs side-by-side

added added

removed removed

Lines of Context:
ecdsa/ellipticcurve.py
32
32
#
33
33
# Written in 2005 by Peter Pearson and placed in the public domain.
34
34
 
35
 
import numbertheory
 
35
from __future__ import division
 
36
 
 
37
from .six import print_
 
38
from . import numbertheory
36
39
 
37
40
class CurveFp( object ):
38
41
  """Elliptic Curve over the field of integers modulo a prime."""
69
72
    # self.curve is allowed to be None only for INFINITY:
70
73
    if self.__curve: assert self.__curve.contains_point( x, y )
71
74
    if order: assert self * order == INFINITY
72
 
 
73
 
  def __cmp__( self, other ):
74
 
    """Return 0 if the points are identical, 1 otherwise."""
 
75
 
 
76
  def __eq__( self, other ):
 
77
    """Return True if the points are identical, False otherwise."""
75
78
    if self.__curve == other.__curve \
76
79
       and self.__x == other.__x \
77
80
       and self.__y == other.__y:
78
 
      return 0
 
81
      return True
79
82
    else:
80
 
      return 1
 
83
      return False
81
84
 
82
85
  def __add__( self, other ):
83
86
    """Add one point to another point."""
84
 
    
 
87
 
85
88
    # X9.62 B.3:
86
89
 
87
90
    if other == INFINITY: return self
100
103
 
101
104
    x3 = ( l * l - self.__x - other.__x ) % p
102
105
    y3 = ( l * ( self.__x - x3 ) - self.__y ) % p
103
 
    
 
106
 
104
107
    return Point( self.__curve, x3, y3 )
105
108
 
106
109
  def __mul__( self, other ):
108
111
 
109
112
    def leftmost_bit( x ):
110
113
      assert x > 0
111
 
      result = 1L
 
114
      result = 1
112
115
      while result <= x: result = 2 * result
113
116
      return result // 2
114
117
 
124
127
    negative_self = Point( self.__curve, self.__x, -self.__y, self.__order )
125
128
    i = leftmost_bit( e3 ) // 2
126
129
    result = self
127
 
    # print "Multiplying %s by %d (e3 = %d):" % ( self, other, e3 )
 
130
    # print_("Multiplying %s by %d (e3 = %d):" % ( self, other, e3 ))
128
131
    while i > 1:
129
132
      result = result.double()
130
133
      if ( e3 & i ) != 0 and ( e & i ) == 0: result = result + self
131
134
      if ( e3 & i ) == 0 and ( e & i ) != 0: result = result + negative_self
132
 
      # print ". . . i = %d, result = %s" % ( i, result )
 
135
      # print_(". . . i = %d, result = %s" % ( i, result ))
133
136
      i = i // 2
134
137
 
135
138
    return result
136
139
 
137
140
  def __rmul__( self, other ):
138
141
    """Multiply a point by an integer."""
139
 
    
 
142
 
140
143
    return self * other
141
144
 
142
145
  def __str__( self ):
159
162
 
160
163
    x3 = ( l * l - 2 * self.__x ) % p
161
164
    y3 = ( l * ( self.__x - x3 ) - self.__y ) % p
162
 
    
 
165
 
163
166
    return Point( self.__curve, x3, y3 )
164
167
 
165
168
  def x( self ):
170
173
 
171
174
  def curve( self ):
172
175
    return self.__curve
173
 
  
 
176
 
174
177
  def order( self ):
175
178
    return self.__order
176
179
 
177
180
 
178
181
# This one point is the Point At Infinity for all purposes:
179
 
INFINITY = Point( None, None, None )  
 
182
INFINITY = Point( None, None, None )
180
183
 
181
184
def __main__():
182
185
 
186
189
    p1 = Point( c, x1, y1 )
187
190
    p2 = Point( c, x2, y2 )
188
191
    p3 = p1 + p2
189
 
    print "%s + %s = %s" % ( p1, p2, p3 ),
 
192
    print_("%s + %s = %s" % ( p1, p2, p3 ), end=' ')
190
193
    if p3.x() != x3 or p3.y() != y3:
191
194
      raise FailedTest("Failure: should give (%d,%d)." % ( x3, y3 ))
192
195
    else:
193
 
      print " Good."
 
196
      print_(" Good.")
194
197
 
195
198
  def test_double( c, x1, y1, x3, y3 ):
196
199
    """We expect that on curve c, 2*(x1,y1) = (x3, y3)."""
197
200
    p1 = Point( c, x1, y1 )
198
201
    p3 = p1.double()
199
 
    print "%s doubled = %s" % ( p1, p3 ),
 
202
    print_("%s doubled = %s" % ( p1, p3 ), end=' ')
200
203
    if p3.x() != x3 or p3.y() != y3:
201
204
      raise FailedTest("Failure: should give (%d,%d)." % ( x3, y3 ))
202
205
    else:
203
 
      print " Good."
 
206
      print_(" Good.")
204
207
 
205
208
  def test_double_infinity( c ):
206
209
    """We expect that on curve c, 2*INFINITY = INFINITY."""
207
210
    p1 = INFINITY
208
211
    p3 = p1.double()
209
 
    print "%s doubled = %s" % ( p1, p3 ),
 
212
    print_("%s doubled = %s" % ( p1, p3 ), end=' ')
210
213
    if p3.x() != INFINITY.x() or p3.y() != INFINITY.y():
211
214
      raise FailedTest("Failure: should give (%d,%d)." % ( INFINITY.x(), INFINITY.y() ))
212
215
    else:
213
 
      print " Good."
 
216
      print_(" Good.")
214
217
 
215
218
  def test_multiply( c, x1, y1, m, x3, y3 ):
216
219
    """We expect that on curve c, m*(x1,y1) = (x3,y3)."""
217
220
    p1 = Point( c, x1, y1 )
218
221
    p3 = p1 * m
219
 
    print "%s * %d = %s" % ( p1, m, p3 ),
 
222
    print_("%s * %d = %s" % ( p1, m, p3 ), end=' ')
220
223
    if p3.x() != x3 or p3.y() != y3:
221
224
      raise FailedTest("Failure: should give (%d,%d)." % ( x3, y3 ))
222
225
    else:
223
 
      print " Good."
 
226
      print_(" Good.")
224
227
 
225
228
 
226
229
  # A few tests from X9.62 B.3:
240
243
  check = INFINITY
241
244
  for i in range( 7 + 1 ):
242
245
    p = ( i % 7 ) * g
243
 
    print "%s * %d = %s, expected %s . . ." % ( g, i, p, check ),
 
246
    print_("%s * %d = %s, expected %s . . ." % ( g, i, p, check ), end=' ')
244
247
    if p == check:
245
 
      print " Good."
 
248
      print_(" Good.")
246
249
    else:
247
250
      raise FailedTest("Bad.")
248
251
    check = check + g
249
252
 
250
253
  # NIST Curve P-192:
251
 
  p = 6277101735386680763835789423207666416083908700390324961279L
252
 
  r = 6277101735386680763835789423176059013767194773182842284081L
253
 
  s = 0x3045ae6fc8422f64ed579528d38120eae12196d5L
254
 
  c = 0x3099d2bbbfcb2538542dcd5fb078b6ef5f3d6fe2c745de65L
255
 
  b = 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1L
256
 
  Gx = 0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012L
257
 
  Gy = 0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811L
 
254
  p = 6277101735386680763835789423207666416083908700390324961279
 
255
  r = 6277101735386680763835789423176059013767194773182842284081
 
256
  #s = 0x3045ae6fc8422f64ed579528d38120eae12196d5L
 
257
  c = 0x3099d2bbbfcb2538542dcd5fb078b6ef5f3d6fe2c745de65
 
258
  b = 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1
 
259
  Gx = 0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012
 
260
  Gy = 0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811
258
261
 
259
262
  c192 = CurveFp( p, -3, b )
260
263
  p192 = Point( c192, Gx, Gy, r )
262
265
  # Checking against some sample computations presented
263
266
  # in X9.62:
264
267
 
265
 
  d = 651056770906015076056810763456358567190100156695615665659L
 
268
  d = 651056770906015076056810763456358567190100156695615665659
266
269
  Q = d * p192
267
 
  if Q.x() != 0x62B12D60690CDCF330BABAB6E69763B471F994DD702D16A5L:
 
270
  if Q.x() != 0x62B12D60690CDCF330BABAB6E69763B471F994DD702D16A5:
268
271
    raise FailedTest("p192 * d came out wrong.")
269
272
  else:
270
 
    print "p192 * d came out right."
 
273
    print_("p192 * d came out right.")
271
274
 
272
 
  k = 6140507067065001063065065565667405560006161556565665656654L
 
275
  k = 6140507067065001063065065565667405560006161556565665656654
273
276
  R = k * p192
274
 
  if R.x() != 0x885052380FF147B734C330C43D39B2C4A89F29B0F749FEADL \
275
 
     or R.y() != 0x9CF9FA1CBEFEFB917747A3BB29C072B9289C2547884FD835L:
 
277
  if R.x() != 0x885052380FF147B734C330C43D39B2C4A89F29B0F749FEAD \
 
278
     or R.y() != 0x9CF9FA1CBEFEFB917747A3BB29C072B9289C2547884FD835:
276
279
    raise FailedTest("k * p192 came out wrong.")
277
280
  else:
278
 
    print "k * p192 came out right."
 
281
    print_("k * p192 came out right.")
279
282
 
280
 
  u1 = 2563697409189434185194736134579731015366492496392189760599L
281
 
  u2 = 6266643813348617967186477710235785849136406323338782220568L
 
283
  u1 = 2563697409189434185194736134579731015366492496392189760599
 
284
  u2 = 6266643813348617967186477710235785849136406323338782220568
282
285
  temp = u1 * p192 + u2 * Q
283
 
  if temp.x() != 0x885052380FF147B734C330C43D39B2C4A89F29B0F749FEADL \
284
 
     or temp.y() != 0x9CF9FA1CBEFEFB917747A3BB29C072B9289C2547884FD835L:
 
286
  if temp.x() != 0x885052380FF147B734C330C43D39B2C4A89F29B0F749FEAD \
 
287
     or temp.y() != 0x9CF9FA1CBEFEFB917747A3BB29C072B9289C2547884FD835:
285
288
    raise FailedTest("u1 * p192 + u2 * Q came out wrong.")
286
289
  else:
287
 
    print "u1 * p192 + u2 * Q came out right."
 
290
    print_("u1 * p192 + u2 * Q came out right.")
288
291
 
289
292
if __name__ == "__main__":
290
293
  __main__()