Skip to content

Commit

Permalink
minicrypt: add Curve25519 Python model and known-answer tests
Browse files Browse the repository at this point in the history
  • Loading branch information
Ian Harvey committed May 20, 2014
1 parent 17266cf commit bae88af
Show file tree
Hide file tree
Showing 2 changed files with 305 additions and 0 deletions.
141 changes: 141 additions & 0 deletions python-models/curve25519.py
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1,141 @@
import sys

# Field primitives

P25519 = (1 << 255) - 19

def f_add(a,b):
return (a+b) % P25519

def f_sub(a,b):
return (a-b) % P25519

def f_mul(a,b):
return (a*b) % P25519

def f_sqr(a):
return (a*a) % P25519

def f_get(s):
# String tp field element, little-endian
res = 0
shift = 0
for ch in s:
res += (ord(ch) << shift)
shift += 8
return res

def f_put(n):
# Field element to string, little-endian
s = ""
for i in range(32):
s += chr( n & 0xFF )
n >>= 8
return s

def f_modexp_inv(z):
# Computes z^(-1) by doing
# z^(2^255-21).
# This exponent = 0x7FFF....FFEB
# which is 11111 11111 .... 11111 01011

tmp = f_sqr(z) # z^2
tmp = f_sqr(tmp) # z^4
tmp = f_mul(tmp, z) # z^5
tmp = f_sqr(tmp) # z^10
res = f_mul(tmp, z) # z^11 (01011)
tmp = f_sqr(tmp) # z^20
tmp = f_mul(tmp,res) # z^31

for i in range(50):
# shift up tmp's exponent by 5 bits
for j in range(5):
tmp = f_sqr(tmp)
# 'Add' in exponent
res = f_mul(res, tmp)

return res

# Point operations

class XZPoint:
def __init__(self, X, Z):
self.X = X
self.Z = Z

def reduce(self):
return f_mul(self.X, f_modexp_inv(self.Z))

def monty_double_add(q, q_, qmqp):
x = z = xx = zz = xx_ = 0 # These are our temporaries

x = f_add(q.X, q.Z)
z = f_sub(q.X, q.Z)

xx = f_add(q_.X, q_.Z)
zz = f_sub(q_.X, q_.Z)

xx = f_mul(xx, z)
zz = f_mul(x, zz)

xx_ = f_add(xx, zz)
zz = f_sub(xx, zz)

q_.X= f_sqr(xx_)
zz = f_sqr(zz)
q_.Z= f_mul(zz, qmqp)

x = f_sqr(x)
z = f_sqr(z)
q.X = f_mul(x,z)

xx = f_sub(x,z)
z = f_mul(xx, (486662 / 4) )
z = f_add(z,x)
q.Z = f_mul(xx,z)


def scalarMul(a, P):
# P is x co-ord of point
assert( P < P25519 )
qmqp = P
npqp = XZPoint(P, 1)
nq = XZPoint(1, 0)
# Bit 254 forced to 1
monty_double_add(npqp, nq, qmqp)
# Bits 253..3 taken from multiplier
i = 253
while i >= 3:
if (a & (1<<i)):
monty_double_add(npqp, nq, qmqp)
else:
monty_double_add(nq, npqp, qmqp)
i -= 1
# Bits 2..0 forced to 0
while i >= 0:
monty_double_add(nq, npqp, qmqp)
i -= 1
return nq.reduce()


def curve25519(a_s, P_s):
return f_put( scalarMul(f_get(a_s), f_get(P_s)) )


if __name__ == '__main__':
import curve25519_kats
from binascii import a2b_hex, b2a_hex

errs = total = 0
for (a,P,want_aP) in curve25519_kats.tests:
got_aP = curve25519(a2b_hex(a),a2b_hex(P))
if b2a_hex(got_aP) != want_aP:
print "Error"
print " want", want_aP
print " got", got_aP
errs += 1
total += 1
print errs, "errors out of", total, "total"
if (errs > 0):
sys.exit("Tests failed")

164 changes: 164 additions & 0 deletions python-models/curve25519_kats.py
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1,164 @@
# Curve25519 known answer tests.
# Format is: privkey, basePoint/pubkey, result
tests = [
(
'0100000000000000000000000000000000000000000000000000000000000000',
'0900000000000000000000000000000000000000000000000000000000000000',
'2fe57da347cd62431528daac5fbb290730fff684afc4cfc2ed90995f58cb3b74',
),
(
'0200000000000000000000000000000000000000000000000000000000000000',
'0900000000000000000000000000000000000000000000000000000000000000',
'2fe57da347cd62431528daac5fbb290730fff684afc4cfc2ed90995f58cb3b74',
),
(
'0400000000000000000000000000000000000000000000000000000000000000',
'0900000000000000000000000000000000000000000000000000000000000000',
'2fe57da347cd62431528daac5fbb290730fff684afc4cfc2ed90995f58cb3b74',
),
(
'0800000000000000000000000000000000000000000000000000000000000000',
'0900000000000000000000000000000000000000000000000000000000000000',
'422c8e7a6227d7bca1350b3e2bb7279f7897b87bb6854b783c60e80311ae3079',
),
(
'1000000000000000000000000000000000000000000000000000000000000000',
'0900000000000000000000000000000000000000000000000000000000000000',
'8d20f8c7bbfb9af3da4ef532ed44efc68ce642bc5d0c5cb1d7b91b96c74edf02',
),
(
'8000000000000000000000000000000000000000000000000000000000000000',
'0900000000000000000000000000000000000000000000000000000000000000',
'a4c3e749664d138f80a1348889872344c11a86e95623b15f8db7ecf83aded927',
),
(
'0000000000000000000000000000000000000000000000000000000000000001',
'0900000000000000000000000000000000000000000000000000000000000000',
'fd3384e132ad02a56c78f45547ee40038dc79002b90d29ed90e08eee762ae715',
),
(
'0000000000000000000000000000000000000000000000000000000000000002',
'0900000000000000000000000000000000000000000000000000000000000000',
'ad8c48c26765aea7adc536289605c1abea95050093dbd218c96abd2481a03565',
),
(
'0000000000000000000000000000000000000000000000000000000000000004',
'0900000000000000000000000000000000000000000000000000000000000000',
'ec13d23a17daf174750df7ad67a86a1d4eabec8f517636605281c1db18c66649',
),
(
'0000000000000000000000000000000000000000000000000000000000000021',
'0900000000000000000000000000000000000000000000000000000000000000',
'193c4d673b002add94cb2403e893df7249a664acd27ba57dd22327ef99cfa324',
),
(
'0000000000000000000000000000000000000000000000000000000000000041',
'0900000000000000000000000000000000000000000000000000000000000000',
'fd3384e132ad02a56c78f45547ee40038dc79002b90d29ed90e08eee762ae715',
),
(
'0000000000000000000000000000000000000000000000000000000000000081',
'0900000000000000000000000000000000000000000000000000000000000000',
'fd3384e132ad02a56c78f45547ee40038dc79002b90d29ed90e08eee762ae715',
),
(
'2919217a44326ec1a7128a93fd5f1f88b43c075e490de27d9d42ab41ae473ba0',
'0900000000000000000000000000000000000000000000000000000000000000',
'83673edf5c14a1b0064b0d18e6b04d0cb4c4a921fcf7fe2ed8d82f5c3fe55a10',
),
(
'fc6e87c41024037fc96712e7fc7b766f37d76a45771a2954b3e6275b2160837a',
'0900000000000000000000000000000000000000000000000000000000000000',
'41fece60d04f29c07878f6905d2916b6c9b34fbcbfd8e2468c7b31537640922f',
),
(
'2919217a44326ec1a7128a93fd5f1f88b43c075e490de27d9d42ab41ae473ba0',
'41fece60d04f29c07878f6905d2916b6c9b34fbcbfd8e2468c7b31537640922f',
'8c58052ac39b59fc1e694ce28c7712311fc7be2d694c744f15a38c9d23422110',
),
(
'fc6e87c41024037fc96712e7fc7b766f37d76a45771a2954b3e6275b2160837a',
'83673edf5c14a1b0064b0d18e6b04d0cb4c4a921fcf7fe2ed8d82f5c3fe55a10',
'8c58052ac39b59fc1e694ce28c7712311fc7be2d694c744f15a38c9d23422110',
),
(
'4e491b133a728007a953ffba01de5fad6d877fc258b1135bcc3386bd1fdd1ef0',
'0900000000000000000000000000000000000000000000000000000000000000',
'9dec64f315b6702f45a0f63d332a573c107c9c7236ac39a58c61933cfbf6b200',
),
(
'0b5d93eed3f586a7843901bb6e3a015b10e4d299f6824a38c9edff1101440ba5',
'0900000000000000000000000000000000000000000000000000000000000000',
'd8e58e78cd3353d9f2aad93a05dcf5b9033746be7f35529e7e7dce05e8df5000',
),
(
'4e491b133a728007a953ffba01de5fad6d877fc258b1135bcc3386bd1fdd1ef0',
'd8e58e78cd3353d9f2aad93a05dcf5b9033746be7f35529e7e7dce05e8df5000',
'07d4b83a0f25551705bbe8f4d43a61babdad45447d01bb589a1ed8ab147a145d',
),
(
'0b5d93eed3f586a7843901bb6e3a015b10e4d299f6824a38c9edff1101440ba5',
'9dec64f315b6702f45a0f63d332a573c107c9c7236ac39a58c61933cfbf6b200',
'07d4b83a0f25551705bbe8f4d43a61babdad45447d01bb589a1ed8ab147a145d',
),
(
'32b0ca05db4e78fd0d9a7c0e39ce5271b80449275422c116c891e940280a87bb',
'0900000000000000000000000000000000000000000000000000000000000000',
'1716d86192ebaaf20c50f6f1d10c1aba25cb06e388d001b74e86396bd1b3232c',
),
(
'8474505f8cc6441453cddfa8cc0fd7fdab9d3f0e3117a9a0acb63833161806f1',
'0900000000000000000000000000000000000000000000000000000000000000',
'872ca91424ce040746a58dc948ba5cf858bc72dc57d14b96fbf0ded71596557d',
),
(
'32b0ca05db4e78fd0d9a7c0e39ce5271b80449275422c116c891e940280a87bb',
'872ca91424ce040746a58dc948ba5cf858bc72dc57d14b96fbf0ded71596557d',
'808628f10531ecfda1bb94564d406c7441c4856eefd09aac1733490deec4046a',
),
(
'8474505f8cc6441453cddfa8cc0fd7fdab9d3f0e3117a9a0acb63833161806f1',
'1716d86192ebaaf20c50f6f1d10c1aba25cb06e388d001b74e86396bd1b3232c',
'808628f10531ecfda1bb94564d406c7441c4856eefd09aac1733490deec4046a',
),
(
'23ca9d6b676f242aac04cc888f3010495830f3d45b7e46acdbdbeb1f12373a00',
'0900000000000000000000000000000000000000000000000000000000000000',
'7b572fea2630ba85bd87f4ef90b111f9a67a3effc3fda9be04904146b70cd86c',
),
(
'a5625554bebf1ddecfad5f6525d3af802c15836f73301f2fcf9fef42c59de56a',
'0900000000000000000000000000000000000000000000000000000000000000',
'074b7e5eb5b62cd14bb49d9fbc7599872cbbf555fcb61b199b130ae444708c68',
),
(
'23ca9d6b676f242aac04cc888f3010495830f3d45b7e46acdbdbeb1f12373a00',
'074b7e5eb5b62cd14bb49d9fbc7599872cbbf555fcb61b199b130ae444708c68',
'fdc921c137c6b8d29e5b6f22634b2e4c3b48bbee71923dfbae7ec34bb08bc548',
),
(
'a5625554bebf1ddecfad5f6525d3af802c15836f73301f2fcf9fef42c59de56a',
'7b572fea2630ba85bd87f4ef90b111f9a67a3effc3fda9be04904146b70cd86c',
'fdc921c137c6b8d29e5b6f22634b2e4c3b48bbee71923dfbae7ec34bb08bc548',
),
(
'494f80a100a5fd50ee35e11e0ddb11736bcbbb6cbd0f179339f88b1c9fa38482',
'0900000000000000000000000000000000000000000000000000000000000000',
'03ddd1330043096719fd3213f7aa0587ba02b39511bd7ba294d34fd76a484706',
),
(
'bdaa9cdf5cc38fe442faa975487df69f443b838613e8a0a544046b07297365db',
'0900000000000000000000000000000000000000000000000000000000000000',
'316f1daa27bc9a9c637761064bf3070c2c620b4e4ccda5982dd147e487ec9d3f',
),
(
'494f80a100a5fd50ee35e11e0ddb11736bcbbb6cbd0f179339f88b1c9fa38482',
'316f1daa27bc9a9c637761064bf3070c2c620b4e4ccda5982dd147e487ec9d3f',
'36541d281b9637e438cdffa84e1910b3a9a42c2afa2652d787b372deb696157f',
),
(
'bdaa9cdf5cc38fe442faa975487df69f443b838613e8a0a544046b07297365db',
'03ddd1330043096719fd3213f7aa0587ba02b39511bd7ba294d34fd76a484706',
'36541d281b9637e438cdffa84e1910b3a9a42c2afa2652d787b372deb696157f',
),
]

0 comments on commit bae88af

Please sign in to comment.