Skip to content

Instantly share code, notes, and snippets.

@kurtbrose
Created December 31, 2012 22:58
Show Gist options
  • Save kurtbrose/4423605 to your computer and use it in GitHub Desktop.
Save kurtbrose/4423605 to your computer and use it in GitHub Desktop.
Implementations of some basic elliptic curve cryptography primitives. Behavior specified by SECG in SEC1 version 1 and 2. Also ANSI X9.63. Curves specified from SEC2 version 1 and 2, and NIST "Recommended Elliptic Curves for Federal Government Use". See: http://en.wikipedia.org/wiki/Elliptic_curve_cryptography and http://www.johannes-bauer.com/c…
'''
Implementations of some basic elliptic curve cryptography primitivese.
Behavior specified by SECG in SEC1 version 1 and 2.
Also ANSI X9.63.
Curves specified from SEC2 version 1 and 2,
and NIST "Recommended Elliptic Curves for Federal Government Use".
See: http://en.wikipedia.org/wiki/Elliptic_curve_cryptography and
http://www.johannes-bauer.com/compsci/ecc/?menuid=4 and
http://www.dkrypt.com/home/ecc
for mathematical background.
'''
import collections, random, binascii
import hashlib, hmac
from Crypto.Cipher import DES3, XOR, AES
from Crypto.Util.strxor import strxor
class Point(collections.namedtuple("EC_Point", "x y curve")):
'represents a point on a prime field, curve of the form yy = xxx + ax + b'
def _add(self, other):
a = self.curve.a
prime = self.curve.p
p = self
q = other
if p != q:
s = _divmod(q.y - p.y, q.x - p.x, prime)
else: #point doubling
s = _divmod(3*p.x*p.x + a, 2*p.y, prime)
x = s*s - p.x - q.x
y = s*(p.x - x) - p.y
return Point(x % prime, y % prime, self.curve)
def __add__(self, other):
if other == 0: #TODO: what is zero for an EC_Point?
return self
#if not isinstance(other, Point):
# raise ValueError("Points can not be added to "+type(other).__name__)
if self.curve != other.curve:
raise ValueError("only points on the same curve can be added")
#implemented from http://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Point_addition
return self._add(other)
__radd__ = __add__
def __rmul__(self, num):
acc = 0 #TODO: what is zero for an EC_Point?
doubler = self
while num >= 1:
if num & 1:
acc += doubler
num >>= 1
doubler += doubler
return acc
__mul__ = __rmul__
def check(self): #sanity check that current point is on its own curve
lhs = self.y**2
rhs = self.x**3 + self.curve.a * self.x + self.curve.b
return lhs % self.curve.p == rhs % self.curve.p
def compress(self):
return self.x*2 + self.y
def sec_decode(curve, data):
'octet-string decoding as defined in section 2.3.3 of SEC1'
if data[0] == '\x04':
raise ValueError("uncompressed format not yet supported")
elif data[0] == '\x02':
y_p = 0
elif data[0] == '\x03':
y_p = 1
else:
raise ValueError("invalid data: first byte must be one of 02, 03, 04")
if isinstance(curve, Curve):
x = int(binascii.hexlify(data[1:]), 16)
assert x < curve.p, "encoded point is not within range of curve points"
alpha = ( x**3 + curve.a*x + curve.b ) % curve.p
beta = _sqrt_mod(alpha, curve.p)
if beta % 2 == y_p:
y = beta
else:
y = curve.p - beta
point = Point(x,y,curve)
elif isinstance(curve, BinaryFieldCurve):
x = _BinaryFieldInt(binascii.hexlify(data[1:]), 16)
#assert x < 2**(int(math.log(curve.f, 2))+1), "encoded point is not within range of curve points"
inv_x, _ = _extended_gcd(x, curve.f)
beta = (x + curve.a + curve.b * inv_x*inv_x) % curve.f
# "find an element z such that z**2 + z = beta"
z = _quadr_solve(beta, curve.f)
if z%2 == y_p:
y = (x * z) % curve.f
else:
y = (x * (z + 1)) % curve.f
point = BinaryPoint(x,y,curve)
else:
raise ValueError("unrecognized curve type")
if not point.check():
raise ValueError("point is not on curve")
return point
def sec_encode(point, compressed=True):
'octet-string encoding as defined in section 2.3.4 of SEC1'
curve = point.curve
#TODO: calculate length properly
x = "{0:X}".format(point.x)
if len(x)%2:
x = "0"+x
x = binascii.unhexlify(x)
if compressed:
if isinstance(curve, Curve):
y = point.y
else:
#inverse of point y for BinaryFieldCurve
y, _ = _extended_gcd(point.y, curve.f)
if y & 0x1: #don't use modulus
output = '\x03' + x
else:
output = '\x02' + x
return output
else:
y = "{0:X}".format(point.y)
if len(y)%2:
y = "0"+y
y = binascii.unhexlify(y)
return "\x04"+x+y
class BinaryPoint(Point):
'Represents a point on a binary field, curve of the form yy + xy = xxx + axx + b'
def __new__(cls, x, y, curve):
return Point.__new__(cls, _BinaryFieldInt(x), _BinaryFieldInt(y), curve)
def _add(self, other):
a = self.curve.a
b = self.curve.b
p = self
q = other
f = self.curve.f
if p == q: #point doubling
s = p.x + _divmod(p.y, p.x, f)
x = s*s + s + a
y = p.x*p.x + (s+1)*x
else:
s = _divmod(p.y + q.y, p.x + q.x, f)
x = s*s + s + p.x + q.x + a
y = s*(p.x + x) + x + p.y
return BinaryPoint(x%f, y%f, self.curve)
def check(self):
lhs = self.y*self.y + self.x*self.y
rhs = self.x*self.x*self.x + self.curve.a * self.x*self.x + self.curve.b
return lhs % self.curve.f == rhs % self.curve.f
Curve = collections.namedtuple("EllipticCurve", "a b p")
#representing the equation y**2 = x**3 + a*x + b % p
_BinaryFieldCurve = collections.namedtuple("BinaryFieldEllipticCurve", "a b f")
class BinaryFieldCurve(_BinaryFieldCurve):
def __new__(cls, a, b, f):
a = _BinaryFieldInt(a)
b = _BinaryFieldInt(b)
if type(f) is list:
f = sum([2**e for e in f]) + 1
f = _BinaryFieldInt(f)
return _BinaryFieldCurve.__new__(cls,a,b,f)
#representing the equation y*y + y*x = x*x*x + a*x*x + b
#over the field of polynomials whose coefficients are {0,1}, aka GF(2)
class Encryptor(object):
def __init__(self, curve, G, n, h):
self.curve = curve #the particular elliptic curve
self.G = G #a Generator EC_Point on the curve
self.n = n #the order of the curve generator G; that is n*G % p = G
#multiplying G by more than n is pointless -- it just loops back around
self.h = h # the cofactor of the curve, it is the quotient of the number of curve-points
#pre-calculate size of serialized field elements
if isinstance(curve, Curve):
curve_size = len("{0:x}".format(curve.p))
else:
curve_size = len("{0:x}".format(curve.f))
self.curve_size = (curve_size + curve_size%2)/2
@classmethod
def make_curve(self, curve, G_x, G_y, n, h=None):
G = Point(G_x, G_y, curve)
if not G.check():
raise ValueError("Invalid: generator point not on curve")
return Encryptor(curve, G, n, h)
@classmethod
def make_binary_curve(self, curve, G_x, G_y, n, h=None):
G = BinaryPoint(G_x, G_y, curve)
if not G.check():
raise ValueError("Invalid: generator point not on curve")
return Encryptor(curve, G, n, h)
def gen_keypair(self, private=None):
if private is None:
private = random.randint(1, self.n)
public = private * self.G
return private, public
def encrypt(self, public, r=None):
if r is None:
r = random.randint(1, self.n)
R = r * self.G #to be transmitted
S = r * public #secret key
#only with corresponding private key, can secret key S be recovered
return R, S
def decrypt(self, private, R):
S = private * R
return S
MODE_CERTICOM98 = "certicom98"
MODE_STANDARD = "standard"
class ECAES(object):
'''
Elliptic Curve Augmented Encryption Scheme,
aka Elliptic Curve Integrated Encryption Scheme (ECIES),
aka Elliptic Curve Encryption Scheme (ECES)
'''
def __init__(self, elliptic_curve_encryptor, public_key, private_key, key_hash=hashlib.sha1,
cipher=DES3, cipher_key_len=None, mac_hash=hashlib.sha1, compress_points=True,
cofactor_diffie_hellman=False, mode=MODE_STANDARD):
self.encryptor = elliptic_curve_encryptor
self.public_key = public_key
self.private_key = private_key
self.cipher = cipher
if cipher_key_len is None:
if cipher in (DES3, AES):
self.cipher_key_len = 24
else:
self.cipher_key_len = None
self.mac_len = len(mac_hash('test').digest())
self.mac_hash = mac_hash
self.key_hash = key_hash
self.compress_points = compress_points
self.cofactor_diffie_hellman = cofactor_diffie_hellman
self.mode = mode #certicom or standard
def encrypt(self, plaintext, r=None):
if r is None:
r = random.randint(1, self.encryptor.n)
point = r * self.public_key
cipher_key_len = self.cipher_key_len or len(plaintext) #for xor cipher
mac_key_len = self.mac_len
keys = self.derive_keys(point, cipher_key_len + mac_key_len)
cipher_key, mac_key = keys[:cipher_key_len], keys[cipher_key_len:]
if self.cipher is DES3:
cipher = DES3.new(cipher_key, mode=DES3.MODE_CBC)
elif self.cipher is AES:
cipher = AES.new(cipher_key, mode=AES.MODE_CBC)
elif self.cipher is XOR:
cipher = XOR.new(cipher_key)
ciphertext = cipher.encrypt(plaintext)
cmp_point = sec_encode(r * self.encryptor.G, self.compress_points)
mac = hmac.new(mac_key, ciphertext, self.mac_hash).digest()
return cmp_point + ciphertext + mac
def decrypt(self, data):
curve_size = self.encryptor.curve_size
point = data[:curve_size+1]
if self.mode == MODE_CERTICOM98:
mac_end = curve_size+1+self.mac_len
mac, ciphertext = data[curve_size+1:mac_end], data[mac_end:]
else:
ciphertext, mac = data[curve_size+1:-self.mac_len], data[-self.mac_len:]
point = sec_decode(self.encryptor.curve, point)
point = self.private_key * point
cipher_key_len = self.cipher_key_len or len(ciphertext) #for xor cipher
mac_key_len = self.mac_len
keys = self.derive_keys(point, cipher_key_len + mac_key_len)
cipher_key, mac_key = keys[:cipher_key_len], keys[cipher_key_len:]
#cur_mac = hmac.new(mac_key, ciphertext, self.mac_hash).digest()
#print binascii.hexlify(cur_mac).upper()
#print binascii.hexlify(mac).upper()
#assert mac == cur_mac, "mac mismatch"
if self.cipher is DES3:
cipher = DES3.new(cipher_key, mode=DES3.MODE_CBC)
elif self.cipher is AES:
cipher = AES.new(cipher_key, mode=AES.MODE_CBC)
elif self.cipher is XOR:
return strxor(cipher_key, ciphertext)
return cipher.decrypt(ciphertext)
def derive_keys(self, point, keylen):
'X9.63 key derivation function'
curve_size = self.encryptor.curve_size
if self.cofactor_diffie_hellman:
point = self.encryptor.h * point
shared_secret = binascii.unhexlify("{0:0{1:d}X}".format(point.x, curve_size*2))
#certicom does some crazy complex shared_secret derivation
sofar = 0
keys = []
if self.mode == MODE_CERTICOM98:
counter = 0
else:
counter = 1
while sofar < keylen:
count = '\0\0\0'+chr(counter)
if self.mode == MODE_CERTICOM98:
cur = count+shared_secret
else:
cur = shared_secret+count
keys.append(self.key_hash(cur).digest())
sofar += len(keys[-1])
counter += 1
return "".join(keys)[:keylen]
#division in integers modulus p means finding the inverse of the denominator
#modulo p and then multiplying the numerator by this inverse
#(Note: inverse of A is B such that A*B % p == 1)
#this can be computed via extended euclidean algorithm
# http://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Computation
def _extended_gcd(a, b):
x = 0
last_x = 1
y = 1
last_y = 0
while b != 0:
quot = a / b
a, b = b, a%b
x, last_x = last_x - quot * x, x
y, last_y = last_y - quot * y, y
return last_x, last_y
#TODO: optimize: a/b and a%b are the same operation underneath for _BinaryFieldInts
#this is the dominating operation performance wise, so reducing this will be 2x speedup
def _divmod(num, den, p):
inv, _ = _extended_gcd(den, p)
return num * inv
def jacobi(a, n):
t = 1
while a != 0:
while a % 2 == 0:
a >>= 1
if n % 8 == 3 or n % 8 == 5: t = -t
if a < n:
a, n = n, a
if a % 4 == 3 and n % 4 == 3: t = -t
a = (a - n) >> 1
if n % 8 == 3 or n % 8 == 5: t = -t
if n == 1: return t
else: return 0
#http://en.wikipedia.org/wiki/Shanks%E2%80%93Tonelli_algorithm
#http://codereview.stackexchange.com/questions/14982/tonelli-shanks-algorithm-in-python
def _sqrt_mod(a, p):
'Tonelli-Shanks algorithm, p must be a prime number'
a = a % p
if p % 8 == 3 or p % 8 == 7:
return pow(a, (p+1)/4, p)
elif p % 8 == 5:
x = pow(a, (p+3)/8, p)
c = (x*x) % p
if a == c:
return x
return (x * pow(2, (p-1)/4, p)) % p
else:
# find a quadratic non-residue d
d = 2
while jacobi(d, p) > -1:
d += 1
# set p-1 = 2^s * t with t odd
t = p - 1
s = 0
while t % 2 == 0:
t /= 2
s += 1
at = pow(a, t, p)
dt = pow(d, t, p)
m = 0
for i in xrange(0, s):
if pow(at * pow(dt, m), pow(2, s-1-i), p) == (p-1):
m = m + pow(2, i)
return (pow(a, (t+1)/2) * pow(dt, m/2)) % p
class _BinaryFieldInt(long):
def __add__(self, o): return _BinaryFieldInt(self ^ o)
__radd__ = __add__
__sub__ = __add__
__rsub__ = __add__
def __mul__(self, o):
acc = 0 #TODO: performance! ack
shift = 0
while o != 0:
if o & 1:
acc ^= self << shift
shift += 1
o >>= 1
return _BinaryFieldInt(acc)
__rmul__ = __mul__
def __mod__(self, base):
q, r = _bf_div(self, base)
return _BinaryFieldInt(r)
def __div__(self, o):
q, r = _bf_div(self, o)
return _BinaryFieldInt(q)
#the performance is probably terrible
def _bf_div(a, b):
r = a #remainder
q = 0 #quotient
#TODO: optimize by using hex instead of binary
rlen = len("{0:b}".format(r)) #NOTE: math.log() doesn't work on bignums
blen = len("{0:b}".format(b))
sweeper = 1 << (rlen-1)
while rlen >= blen:
shift = rlen - blen
q |= 1 << shift
r ^= b << shift
if r == 0: break #great, evenly divisible
while r and not sweeper & r:
sweeper >>= 1
rlen -= 1
return q, r
def _quadr_solve(beta, f):
'''
find a solution of the form z*z + z = b mod f, if a solution exists
note: z, b, f are all BinaryFieldInts, not regular numbers
return None if no solution exists
'''
z = beta
m = len("{0:b}".format(f))
for i in range( (m-1)/2 ):
z = (z*z) % f
z = (z*z + beta) % f
if (z*z + z) % f == beta:
return z
raise ValueError("no solution exists for z**2 + z = beta")
return None
#which specific fields?
#Standard curves recommended by NIST
#see http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf
P192 = Encryptor.make_curve(
Curve(a = -3,
b = 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1,
p = 6277101735386680763835789423207666416083908700390324961279),
G_x = 0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
G_y = 0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811,
n = 6277101735386680763835789423176059013767194773182842284081)
P224 = Encryptor.make_curve(
Curve(a = -3,
b = 0xb4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4,
p = 26959946667150639794667015087019630673557916260026308143510066298881),
G_x = 0xb70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21,
G_y = 0xbd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34,
n = 26959946667150639794667015087019625940457807714424391721682722368061)
P256 = Encryptor.make_curve(
Curve(a = -3,
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b,
p = 115792089210356248762697446949407573530086143415290314195533631308867097853951),
G_x = 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296,
G_y = 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5,
n = 115792089210356248762697446949407573529996955224135760342422259061068512044369)
P384 = Encryptor.make_curve(
Curve(a = -3,
b = int("b3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f"\
"5013875ac656398d8a2ed19d2a85c8edd3ec2aef", 16),
p = int("394020061963944792122790401001436138050797392704654466679482"\
"93404245721771496870329047266088258938001861606973112319")),
G_x = int("aa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b98"\
"59f741e082542a385502f25dbf55296c3a545e3872760ab7", 16),
G_y = int("3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147c"\
"e9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f", 16),
n = int("394020061963944792122790401001436138050797392704654466679469052796"\
"27659399113263569398956308152294913554433653942643"))
P521 = Encryptor.make_curve(
Curve(a = -3,
b = int("051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3"\
"b8b489918ef109e156193951ec7e937b1652c0bd"\
"3bb1bf073573df883d2c34f1ef451fd46b503f00", 16),
p = int("686479766013060971498190079908139321726943530014330540939446"\
"345918554318339765605212255964066145455497729631139148085803"\
"7121987999716643812574028291115057151")),
G_x = int("c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521"\
"f828af606b4d3dbaa14b5e77efe75928fe1dc127"\
"a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66", 16),
G_y = int("11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b4468"\
"17afbd17273e662c97ee72995ef42640c550b901"\
"3fad0761353c7086a272c24088be94769fd16650", 16),
n = int("686479766013060971498190079908139321726943530014330540939446345918"\
"5543183397655394245057746333217197532963996371363321113864768612440380"\
"340372808892707005449"))
K163 = Encryptor.make_binary_curve(
BinaryFieldCurve(a = 1, b = 1, f = [163, 7, 6, 3]),
G_x = 0x02FE13C0537BBC11ACAA07D793DE4E6D5E5C94EEE8,
G_y = 0x0289070FB05D38FF58321F2E800536D538CCDAA3D9,
n = 0x04000000000000000000020108A2E0CC0D99F8A5EF,
h = 2)
B163 = Encryptor.make_binary_curve(
BinaryFieldCurve(
a = 1, #this is the only value of a from 0-4096 which works
b = 0x20a601907b8c953ca1481eb10512f78744a3205fd,
f = [163, 7, 6, 3]),
G_x = 0x3f0eba16286a2d57ea0991168d4994637e8343e36,
G_y = 0x0d51fbc6c71a0094fa2cdd545b11c5c0c797324f1,
n = 5846006549323611672814742442876390689256843201587)
#standard curves from Secure Encryption Standard
#http://www.secg.org/collateral/sec2_final.pdf
SECP112_PRIME = (2**128 - 3)/76439
SECP112r1 = Encryptor.make_curve(
Curve(a = 0xDB7C2ABF62E35E668076BEAD2088,
b = 0x659EF8BA043916EEDE8911702B22,
p = SECP112_PRIME),
G_x = 0x09487239995A5EE76B55F9C2F098,
G_y = 0xA89CE5AF8724C0A23E0E0FF77500,
n = 0xDB7C2ABF62E35E7628DFAC6561C5,
h = 1)
SECP112r2 = Encryptor.make_curve(
Curve(a = 0x6127C24C05F38A0AAAF65C0EF02C,
b = 0x51DEF1815DB5ED74FCC34C85D709,
p = SECP112_PRIME),
G_x = 0x4BA30AB5E892B4E1649DD0928643,
G_y = 0xADCD46F5882E3747DEF36E956E97,
n = 0x36DF0AAFD8B8D7597CA10520D04B,
h = 4)
SECP128_PRIME = 2**128 - 2**97 - 1
SECP128r1 = Encryptor.make_curve(
Curve(a = 0xFFFFFFFDFFFFFFFFFFFFFFFFFFFFFFFC,
b = 0xE87579C11079F43DD824993C2CEE5ED3,
p = SECP128_PRIME),
G_x = 0x161FF7528B899B2D0C28607CA52C5B86,
G_y = 0xCF5AC8395BAFEB13C02DA292DDED7A83,
n = 0xFFFFFFFE0000000075A30D1B9038A115,
h = 1)
SECP128r2 = Encryptor.make_curve(
Curve(a = 0xD6031998D1B3BBFEBF59CC9BBFF9AEE1,
b = 0x5EEEFCA380D02919DC2C6558BB6D8A5D,
p = SECP128_PRIME),
G_x = 0x7B6AA5D85E572983E6FB32A7CDEBC140,
G_y = 0x27B6916A894D3AEE7106FE805FC34B44,
n = 0x3FFFFFFF7FFFFFFFBE0024720613B5A3,
h = 4)
SECP160k1 = Encryptor.make_curve(
Curve(a = 0,
b = 7,
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFAC73),
G_x = 0x3B4C382CE37AA192A4019E763036F4F5DD4D7EBB,
G_y = 0x938CF935318FDCED6BC28286531733C3F03C4FEE,
n = 0x100000000000000000001B8FA16DFAB9ACA16B6B3,
h = 1)
SECP160r1 = Encryptor.make_curve(
Curve(a = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF7FFFFFFC,
b = 0x1C97BEFC54BD7A8B65ACF89F81D4D4ADC565FA45,
p = 2**160 - 2**31 - 1),
G_x = 0x4A96B5688EF573284664698968C38BB913CBFC82,
G_y = 0x23A628553168947D59DCC912042351377AC5FB32,
n = 0x100000000000000000001F4C8F927AED3CA752257,
h = 1)
SECP160r2 = Encryptor.make_curve(
Curve(a = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFAC70,
b = 0xB4E134D3FB59EB8BAB57274904664D5AF50388BA,
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFAC73),
G_x = 0x52DCB034293A117E1F4FF11B30F7199D3144CE6D,
G_y = 0xFEAFFEF2E331F296E071FA0DF9982CFEA7D43F2E,
n = 0x0100000000000000000000351EE786A818F3A1A16B,
h = 1)
SECP192k1 = Encryptor.make_curve(
Curve(a = 0,
b = 3,
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFEE37),
G_x = 0xDB4FF10EC057E9AE26B07D0280B7F4341DA5D1B1EAE06C7D,
G_y = 0x9B2F2F6D9C5628A7844163D015BE86344082AA88D95E2F9D,
n = 0xFFFFFFFFFFFFFFFFFFFFFFFE26F2FC170F69466A74DEFD8D,
h = 1)
SECT163k1 = K163
SECT163r1 = Encryptor.make_binary_curve(
BinaryFieldCurve(
a = 0x07B6882CAAEFA84F9554FF8428BD88E246D2782AE2,
b = 0x0713612DCDDCB40AAB946BDA29CA91F73AF958AFD9,
f = [163, 7, 6, 3]),
G_x = 0x0369979697AB43897789566789567F787A7876A654,
G_y = 0x00435EDB42EFAFB2989D51FEFCE3C80988F41FF883,
n = 0x03FFFFFFFFFFFFFFFFFFFF48AAB689C29CA710279B,
h = 2)
SECT163r2 = Encryptor.make_binary_curve(
BinaryFieldCurve(
a = 1,
b = 0x020A601907B8C953CA1481EB10512F78744A3205FD,
f = [163, 7, 6, 3]),
G_x = 0x03F0EBA16286A2D57EA0991168D4994637E8343E36,
G_y = 0x00D51FBC6C71A0094FA2CDD545B11C5C0C797324F1,
n = 0x040000000000000000000292FE77E70C12A4234C33,
h = 2)
SECT233k1 = Encryptor.make_binary_curve(
BinaryFieldCurve(a = 0, b = 1, f = [233, 74]),
G_x = 0x017232BA853A7E731AF129F22FF4149563A419C26BF50A4C9D6EEFAD6126,
G_y = 0x01DB537DECE819B7F70F555A67C427A8CD9BF18AEB9B56E0C11056FAE6A3,
n = 0x8000000000000000000000000000069D5BB915BCD46EFB1AD5F173ABDF,
h = 4)
SECT233r1 = Encryptor.make_binary_curve(
BinaryFieldCurve(
a = 1,
b = 0x0066647EDE6C332C7F8C0923BB58213B333B20E9CE4281FE115F7D8F90AD,
f = [233, 74]),
G_x = 0x00FAC9DFCBAC8313BB2139F1BB755FEF65BC391F8B36F8F8EB7371FD558B,
G_y = 0x01006A08A41903350678E58528BEBF8A0BEFF867A7CA36716F7E01F81052,
n = 0x01000000000000000000000000000013E974E72F8A6922031D2603CFE0D7,
h = 2)
SECT239k1 = Encryptor.make_binary_curve(
BinaryFieldCurve(a = 0, b = 1, f = [239, 158]),
G_x = 0x29A0B6A887A983E9730988A68727A8B2D126C44CC2CC7B2A6555193035DC,
G_y = 0x76310804F12E549BDB011C103089E73510ACB275FC312A5DC6B76553F0CA,
n = 0x2000000000000000000000000000005A79FEC67CB6E91F1C1DA800E478A5,
h = 4)
SECT283k1 = Encryptor.make_binary_curve(
BinaryFieldCurve(a = 0, b = 1, f = [283, 12, 7, 5]),
G_x = 0x0503213F78CA44883F1A3B8162F188E553CD265F23C1567A16876913B0C2AC2458492836,
G_y = 0x01CCDA380F1C9E318D90F95D07E5426FE87E45C0E8184698E45962364E34116177DD2259,
n = 0x01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE9AE2ED07577265DFF7F94451E061E163C61,
h = 4)
#curves extracted from libcrvs.a
EC163a02 = SECT163k1
ALL_STD_CIPHERS = [P192, P224, P256, P384, P521, SECP112r1, SECP112r2, SECP128r1, SECP128r2,
SECP160k1, SECP160r1, SECP160r2, SECP192k1, SECT163k1, SECT163r1, SECT163r2, SECT233k1, SECT239k1]
'''
Encryptor.make_curve(
Curve(a = ,
b = ,
p = ),
G_x = ,
G_y = ,
n = ,
h = )
Encryptor.make_binary_curve(
BinaryFieldCurve(
a = ,
b = ,
f = ),
G_x = ,
G_y = ,
n = ,
h = )
'''
def test():
ecaes_test()
certicom_mult_test()
decrypt_test()
def test_cipher(encryptor):
private, public = encryptor.gen_keypair()
cipher, plain = encryptor.encrypt(public)
assert plain == encryptor.decrypt(private, cipher)
for encryptor in ALL_STD_CIPHERS:
print "testing cipher"
test_cipher(encryptor)
def ecaes_test():
#test vectors from http://www.secg.org/collateral/gec2.pdf
r = 501870566195266176721440888203272826969530834326
priv, pub = SECT163k1.gen_keypair(r)
assert pub.x == 0x072783FAAB9549002B4F13140B88132D1C75B3886C
assert pub.y == 0x05A976794EA79A4DE26E2E19418F097942C08641C7
assert sec_encode(pub) == binascii.unhexlify(
"02072783FAAB9549002B4F13140B88132D1C75B3886C")
#OMGWTFBBQ, standards doc test value is wrong -- 0x03 first byte when it should be 0x02
#or..... is the inverse function wrong?
ecaes = ECAES(SECT163k1, pub, priv, cipher=XOR)
plaintext = "abcdefghijklmnopqrst"
k = 936523985789236956265265265235675811949404040044
data = ecaes.encrypt(plaintext, k)
expected_data = binascii.unhexlify(
"0204994D2C41AA30E52952B0A94EC6511328C502DA9B"+\
"62A441E4ADF2866BAFEADA50B9DAC1047B2C83B3183301B4"+\
"14C82DFA91A58311369DF0E2A6F9642C")
assert data == expected_data
assert ecaes.decrypt(data) == plaintext
def certicom_mult_test():
priv = int('00ADB84D68BDCF71B62A4B2808F45DABF8DEA1287B', 16)
pub = binascii.unhexlify('03005716C55DB50BB7DDD2FDDB6186110A9492465DF5')
pub = sec_decode(EC163a02.curve, pub)
assert priv * EC163a02.G == pub
def decrypt_test():
public_key = sec_decode(EC163a02.curve, binascii.unhexlify('03005716C55DB50BB7DDD2FDDB6186110A9492465DF5'))
private_key = int('00ADB84D68BDCF71B62A4B2808F45DABF8DEA1287B', 16)
encrypted = '03027E67B352ACA3B31651D5B812B40A249278AA2E3EB3FCA0BE7D53418B6752A7FD6DB03EA9160B26A3C1B41D3'+\
'77E50BE769DC4056E7B54C01383855358EE24D662747D649F77138DA111349704BD44B196E217B1DFE8A39FCD2F21C57269398E'+\
'C0BE57A45AA5150A8C684B930C5C7FF93058CD220E8C923392A1AD303E0262B3C01BB9C3D126D978AF7EB74E766CC1ADC2B900D'+\
'499ABD1A9A2D27B70DDC89EC51B9EFCD639C4566D43'
encryptor = ECAES(EC163a02, public_key, private_key, cipher=XOR)
print binascii.hexlify(encryptor.decrypt(binascii.unhexlify(encrypted)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment