Skip to content

Commit

Permalink
First working version of curve25519
Browse files Browse the repository at this point in the history
  • Loading branch information
Ian Harvey committed May 28, 2014
1 parent bae88af commit 2dd6d73
Show file tree
Hide file tree
Showing 7 changed files with 698 additions and 9 deletions.
15 changes: 11 additions & 4 deletions host/Makefile
View file
Original file line number Diff line number Diff line change
Expand Up @@ -42,20 +42,26 @@ mpimul_mini_test: mpimul_mini.c
$(CC) $(CFLAGS) -DTEST_HARNESS -o $@ $^
TARGETS += mpimul_mini_test

MPI_OBJS= mpiadd_mini.o mpisub_mini.o mpimul_mini.o mpiutil_mini.o f25519util_mini.o
MPI_OBJS= mpiadd_mini.o mpisub_mini.o mpimul_mini.o mpiutil_mini.o

f25519add_mini_test: f25519add_mini.c $(MPI_OBJS)
f25519add_mini_test: f25519add_mini.c f25519util_mini.o $(MPI_OBJS)
$(CC) $(CFLAGS) -DTEST_HARNESS -o $@ $^
TARGETS += f25519add_mini_test

f25519sub_mini_test: f25519sub_mini.c $(MPI_OBJS)
f25519sub_mini_test: f25519sub_mini.c f25519util_mini.o $(MPI_OBJS)
$(CC) $(CFLAGS) -DTEST_HARNESS -o $@ $^
TARGETS += f25519sub_mini_test

f25519mul_mini_test: f25519mul_mini.c $(MPI_OBJS)
f25519mul_mini_test: f25519mul_mini.c f25519util_mini.o $(MPI_OBJS)
$(CC) $(CFLAGS) -DTEST_HARNESS -o $@ $^
TARGETS += f25519mul_mini_test

F25519_OBJS= f25519add_mini.o f25519sub_mini.o f25519mul_mini.o f25519util_mini.o $(MPI_OBJS)

curve25519_mini_test: curve25519_mini.c $(F25519_OBJS)
$(CC) $(CFLAGS) -DTEST_HARNESS -o $@ $^
TARGETS += curve25519_mini_test

# -------------------------------------

all: $(TARGETS)
Expand All @@ -79,4 +85,5 @@ test: $(TARGETS)
./f25519add_mini_test
./f25519sub_mini_test
./f25519mul_mini_test
./curve25519_mini_test

258 changes: 258 additions & 0 deletions python-models/bntestvectors.py
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1,258 @@
import random, os

class TestVector:

@staticmethod
def toWords(val, nWords):
assert( val >= 0 )
assert( val < (1 << (nWords*32)) )
return [ (val >> (i*32)) & 0xFFFFFFFF for i in range(nWords) ]

@staticmethod
def toC(val, nWords):
return "{ {" + (",".join(["0x%08X" % w for w in TestVector.toWords(val, nWords)])) + "} }"

@staticmethod
def toStruct(items):
res = " {\n"
res += ",\n".join([" " + i for i in items])
res += "\n },\n\n"
return res

def __init__(self):
pass

def writeFile(self, filename):
count = 0
with open(filename, "w") as fout:
fout.write(self.file_header())
for tv in self.generateTestVectors():
fout.write(self.convert(tv))
count += 1
fout.write(self.file_footer())
print "Wrote", filename, "(", count, "vectors )"

def file_header(self):
return "/* AUTOGENERATED - do not edit */\n"

def file_footer(self):
return ""

def convert(self, tv):
(inA, inB, res) = [ TestVector.toC(val, 8) for val in tv ]
return TestVector.toStruct([inA, inB, res])


class MulTestVectors(TestVector):
def __init__(self):
self.inputs = [
0,
1,
0xFFFF,
0x10000,
0xFFFF0000,
0xFFFFFFFF,
(1 << 32),
random.getrandbits(64),
(1 << 128)-1,
random.getrandbits(160),
(1<<224) - 1,
random.getrandbits(256),
(1<<256) - 1
]

def convert(self, tv):
(inA, inB, res) = tv
return TestVector.toStruct([
TestVector.toC(inA, 8),
TestVector.toC(inB, 8),
TestVector.toC(res, 16)
])

def generateTestVectors(self):
for i in range(len(self.inputs)):
for j in range(i+1):
x = self.inputs[i]
y = self.inputs[j]
res = x*y
yield( (x,y,res) )

class AddTestVectors(TestVector):
def __init__(self):
self.inputs = [
0x0001,
0x10000,
0xFFFE,
0xFFFF,
random.getrandbits(32),
0xFFFFFFFFF,
random.getrandbits(64),
(1<<255)-1,
random.getrandbits(256),
random.getrandbits(256),
(1<<256)-1
]

def convert(self, tv):
(inA, inB, res, carry) = tv
return TestVector.toStruct([
TestVector.toC(inA, 8),
TestVector.toC(inB, 8),
TestVector.toC(res, 8),
"%d" % carry
])

def generateTestVectors(self):
nvals = len(self.inputs)
for i in range(nvals):
for j in range(i+1):
x = self.inputs[i]
y = self.inputs[j]
res = x+y
carry = 1 if (res >= (1 << 256)) else 0
res -= (carry << 256)
yield( (x,y,res,carry) )

class SubTestVectors(TestVector):
def __init__(self):
self.inputs = [
0x0,
0x1,
0xFFFE,
0xFFFF,
random.getrandbits(32),
0xFFFFFFFFF,
random.getrandbits(64),
(1<<255)-1,
random.getrandbits(256),
random.getrandbits(256),
(1<<256)-1
]

def convert(self, tv):
(inA, inB, res, carry) = tv
return TestVector.toStruct([
TestVector.toC(inA, 8),
TestVector.toC(inB, 8),
TestVector.toC(res, 8),
"0x%X" % carry
])

def generateTestVectors(self):
nvals = len(self.inputs)
for i in range(nvals):
for j in range(nvals):
x = self.inputs[i]
y = self.inputs[j]
res = x-y
if (res < 0):
res += (1 << 256)
carry = 0xFFFFFFFF
else:
carry = 0
yield( (x,y,res,carry) )

F25519 = (1 << 255)-19

F25519_elements = [
# Not a complete list ;-)
0x0,
0x1,
random.getrandbits(32),
0x80000000,
(1<<127)-1,
random.getrandbits(256) % F25519,
random.getrandbits(256) % F25519,
F25519-0x80000000,
F25519-1,
]

class F25519AddTestVectors(TestVector):
def __init__(self):
pass

def generateTestVectors(self):
for i in range(len(F25519_elements)):
for j in range(i+1):
x = F25519_elements[i]
y = F25519_elements[j]
res = (x + y) % F25519
yield( (x,y,res) )

class F25519SubTestVectors(TestVector):
def __init__(self):
pass

def generateTestVectors(self):
for i in range(len(F25519_elements)):
for j in range(len(F25519_elements)):
x = F25519_elements[i]
y = F25519_elements[j]
res = (x - y) % F25519
yield( (x,y,res) )

class F25519MulTestVectors(TestVector):
def __init__(self):
pass

def generateTestVectors(self):
for i in range(len(F25519_elements)):
for j in range(i+1):
x = F25519_elements[i]
y = F25519_elements[j]
res = (x * y) % F25519
yield( (x,y,res) )


class Curve25519TestVectors(TestVector):
baseP = chr(0x09) + (chr(0) * 31)

def __init__(self, referenceImplFn):
self.curveFn = referenceImplFn

@staticmethod
def toC(v):
assert(len(v)==32)
return "{ {" + (",".join([hex(ord(ch)) for ch in v])) + "} }"

def convert(self, tv):
return self.toStruct([self.toC(v) for v in tv])

def doKAT(self, a, P):
aP = self.curveFn(a, P)
return (a, P, aP)

def generateTestVectors(self):
# Checks of LSB operation
for b0 in [ 0x01, 0x02, 0x04, 0x08, 0x10, 0x80 ]:
yield(self.doKAT( chr(b0) + (chr(0)*31), self.baseP ))

# Checks of high single bits
for bN in [ 0x01, 0x02, 0x04, 0x21, 0x41, 0x81 ]:
yield(self.doKAT( (chr(0)*31) + chr(bN), self.baseP ))

# Simulate DH key generation and exchange

for i in range(5):
privA = os.urandom(32)
pubA = self.curveFn(privA, self.baseP)
yield(self.doKAT( privA, self.baseP ))

privB = os.urandom(32)
pubB = self.curveFn(privB, self.baseP)
yield(self.doKAT( privB, self.baseP ))

yield(self.doKAT (privA, pubB))
yield(self.doKAT (privB, pubA))


if __name__ == '__main__':
#MulTestVectors().writeFile("mpimul.inc")
#AddTestVectors().writeFile("mpiadd.inc")
#SubTestVectors().writeFile("mpisub.inc")
#F25519AddTestVectors().writeFile("f25519add.inc")
#F25519SubTestVectors().writeFile("f25519sub.inc")
#F25519MulTestVectors().writeFile("f25519mul.inc")
import curve25519
Curve25519TestVectors(curve25519.curve25519).writeFile("curve25519.inc")

Loading

0 comments on commit 2dd6d73

Please sign in to comment.