From 5f8de423f190bbb79a62f804151bc24824fa32d8 Mon Sep 17 00:00:00 2001 From: "Matt A. Tobin" Date: Fri, 2 Feb 2018 04:16:08 -0500 Subject: Add m-esr52 at 52.6.0 --- python/PyECC/MANIFEST.in | 1 + python/PyECC/README.md | 29 ++ python/PyECC/ecc/Key.py | 320 +++++++++++++++++++++ python/PyECC/ecc/Rabbit.py | 270 ++++++++++++++++++ python/PyECC/ecc/SecurityViolationException.py | 2 + python/PyECC/ecc/__init__.py | 0 python/PyECC/ecc/curves.py | 81 ++++++ python/PyECC/ecc/eccrypt.py | 65 +++++ python/PyECC/ecc/ecdsa.py | 153 ++++++++++ python/PyECC/ecc/elliptic.py | 381 +++++++++++++++++++++++++ python/PyECC/ecc/encoding.py | 178 ++++++++++++ python/PyECC/ecc/performance.py | 50 ++++ python/PyECC/ecc/primes.py | 82 ++++++ python/PyECC/ecc/shacrypt.py | 38 +++ python/PyECC/setup.py | 77 +++++ 15 files changed, 1727 insertions(+) create mode 100644 python/PyECC/MANIFEST.in create mode 100644 python/PyECC/README.md create mode 100644 python/PyECC/ecc/Key.py create mode 100644 python/PyECC/ecc/Rabbit.py create mode 100644 python/PyECC/ecc/SecurityViolationException.py create mode 100644 python/PyECC/ecc/__init__.py create mode 100644 python/PyECC/ecc/curves.py create mode 100644 python/PyECC/ecc/eccrypt.py create mode 100644 python/PyECC/ecc/ecdsa.py create mode 100644 python/PyECC/ecc/elliptic.py create mode 100644 python/PyECC/ecc/encoding.py create mode 100644 python/PyECC/ecc/performance.py create mode 100644 python/PyECC/ecc/primes.py create mode 100644 python/PyECC/ecc/shacrypt.py create mode 100644 python/PyECC/setup.py (limited to 'python/PyECC') diff --git a/python/PyECC/MANIFEST.in b/python/PyECC/MANIFEST.in new file mode 100644 index 000000000..bb3ec5f0d --- /dev/null +++ b/python/PyECC/MANIFEST.in @@ -0,0 +1 @@ +include README.md diff --git a/python/PyECC/README.md b/python/PyECC/README.md new file mode 100644 index 000000000..be67fff04 --- /dev/null +++ b/python/PyECC/README.md @@ -0,0 +1,29 @@ +ecc +=== + +Pure Python implementation of an elliptic curve cryptosystem based on FIPS 186-3 + +License +======= + +The MIT License (MIT) + +Copyright (c) 2010-2015 Toni Mattis + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +THE SOFTWARE. diff --git a/python/PyECC/ecc/Key.py b/python/PyECC/ecc/Key.py new file mode 100644 index 000000000..8ba268576 --- /dev/null +++ b/python/PyECC/ecc/Key.py @@ -0,0 +1,320 @@ +# ==================================================================== +# +# ELLIPTIC CURVE KEY ENCAPSULATION +# Version 2011-01-26 +# +# Copyright (c) 2010 - 2011 | Toni Mattis +# +# ==================================================================== + +""" +== Elliptic Curve Key Encapsulation == + +Keypairs +-------- +Keypairs are generated using: Key.generate(bits) + +The number of bits is tied to the NIST-proposed elliptic curves +and has to be 192, 224, 256, 384 or 521 (not 512!). +The result is a Key object containing public and private key. + +private() is a method for checking whether the Key object is a +pure public key or also includes the private part. + + +Exchange +-------- +Public keys have to be exported using the export()-Method without +passing an argument. The result is a string which can be safely +transmitted. + +Using Key.decode() the receiver obtains a new +public Key object of the sender. + + +Storage +------- +For storing a key, export(True) exports both private and public +key as a string. Make sure this information is properly encrypted +when stored. + +Key.decode() obtains the full Key object from the +encoded keypair. + + +Public Keys +----------- +A public Key object can perform the following cryptographic +operations: + +* validate() Checks key integrity, i.e. after loading the + key from a file. Returns True if the key is + valid. Invalid keys should be discarded. + +* fingerprint() Returns the public key fingerprint used to + identify the key. Optional arguments: + 1. as_hex - True, if output should be formatted + as hexadecimal number (default: True). + 2. hashfunc - The official name of the hash + function being used (default: 'sha1') + For supported hash functions see below. + +* keyid() Returns a (mostly) unique Key ID, which is + shorter than the fingerprint. The result + is an integer of max. 64 bits. + +* verify() Verifies whether the given data (argument 1) + matches the signature (argument 2) issued + by the owner of this key. A falsification + can have multiple causes: + + - Data, public key or signature were altered + during transmission/storage. + - The siganture was not issued by the owner + of this key but may be valid with another + key. + - The signature was issued for different data. + - The signature was issued using a different + hash function. Another hash function may work. + + Optionally, the name of a hash algorithm + can be provided. For hash names see below. + +* encrypt() Encrypts a packet of data destined for the owner + of this key*. After encryption only the holder + of this Key's private part is able to decrypt + the message. + +Private Keys / Keypairs +----------------------- + +If the key object is private, then it is a keypair consisting of +a public and a private key. Therefore all Public key operations +are supported. + +Additional functions: + +* sign() Signs given data using this private key. The + result is a signature which can be passed as + argument to the verify() function in addition + to the data being verified. + + As additional argument the name of the hash + function can be provided (defaults to 'sha256'). + For hash names see below. + +* auth_encrypt() Performs authenticated encryption of data + (argument 1) for the holder of the key provided + as second argument. Only the receiver whose + public key is given is able to derypt and verify + the message. The message will be implicitly + signed using the own private key. * + +* decrypt() Decrypts a message which has been encrypted + using the public key of this keypair*. If + decryption yields random data, this can have + multiple causes: + - You were not the intended receiver, a different + private key may be able to decrypt it. + - The message was altered. + - Your private key is damaged. + +* auth_decrypt() Decrypts a message while verifying whether + it has been authentically issued by the holder + of the given key (argument 2). When + authentication failed, a + SecurityViolationException is thrown. Reasons + for this to happen are those mentioned with + decrypt() and verify(). * + +*) The encryption used here depends on the "eccrypt" module imported +by this module. Default implementation should use RABBIT as cipher +and do the asymmetric part using an optimized El-Gamal scheme. + + + +Hash functions +-------------- +The following hash functions can be passed at the moment: + +name | hash size | security level + | (bits, bytes, hex digits) +---------+------------------------+---------------- +'sha1' 160 / 20 / 40 medium +'sha224' 224 / 28 / 56 medium-strong +'sha256' 256 / 32 / 64 strong +'sha384' 384 / 48 / 96 very strong +'sha512' 512 / 64 / 128 very strong + +'md5' 128 / 16 / 32 weak (not recommended!) + + +Curves +------ +According to FIPS 186-3, Appendix D.1.2 there are 5 elliptic +curves recommended. All of those are strong, but those with +a higher bit number even stronger. + +192 and 224 bits are sufficient for most purposes. +256 bits offer an additional magnitude of security. + (i.e. for classified / strongly confidential data) +384 and 521 bits provide exceptionally strong security. According + to current research they most probably keep this level for + decades in the future. + +FIPS also recommends curves over polynomial fields but actually +only prime fields are implemented here. (Because 2^521-1 is a mersenne +prime having great security characteristics, 521 bits are preferred +over a constructed 512 bit field.) +""" + +from encoding import * +from eccrypt import * +import ecdsa +import hashlib +from SecurityViolationException import * + +class Key: + + # --- KEY SETUP ------------------------------------------------------------ + + def __init__(self, public_key, private_key = None): + '''Create a Key(pair) from numeric keys.''' + self._pub = public_key + self._priv = private_key + self._fingerprint = {} + self._id = None + + @staticmethod + def generate(bits): + '''Generate a new ECDSA keypair''' + return Key(*ecdsa.keypair(bits)) + + # --- BINARY REPRESENTATION ------------------------------------------------ + + def encode(self, include_private = False): + '''Returns a strict binary representation of this Key''' + e = Encoder().int(self.keyid(), 8) + e.int(self._pub[0], 2).point(self._pub[1], 2) + if include_private and self._priv: + e.long(self._priv[1], 2) + else: + e.long(0, 2) + return e.out() + + def compress(self): + '''Returns a compact public key representation''' + + + @staticmethod + def decode(s): + '''Constructs a new Key object from its binary representation''' + kid, ksize, pub, priv = Decoder(s).int(8).int(2).point(2).long(2).out() + k = Key((ksize, pub), (ksize, priv) if priv else None) + if kid == k.keyid(): + return k + else: + raise ValueError, "Invalid Key ID" + + # --- IDENTIFICATION AND VALIDATION ---------------------------------------- + + def private(self): + '''Checks whether Key object contains private key''' + return bool(self._priv) + + def validate(self): + '''Checks key validity''' + if ecdsa.validate_public_key(self._pub): + if self._priv: # ? validate and match private key + return ecdsa.validate_private_key(self._priv) and \ + ecdsa.match_keys(self._pub, self._priv) + else: + return True # : everything valid + else: + return False + + def fingerprint(self, as_hex = True, hashfunc = 'sha1'): + '''Get the public key fingerprint''' + if hashfunc in self._fingerprint: + return self._fingerprint[hashfunc] if not as_hex else \ + self._fingerprint[hashfunc].encode("hex") + else: + h = hashlib.new(hashfunc, enc_point(self._pub[1])) + d = h.digest() + self._fingerprint[hashfunc] = d + return d.encode("hex") if as_hex else d + + def keyid(self): + '''Get a short, unique identifier''' + if not self._id: + self._id = dec_long(self.fingerprint(False, 'sha1')[:8]) + return self._id + + # --- DIGITAL SIGNATURES --------------------------------------------------- + + def sign(self, data, hashfunc = 'sha256'): + '''Sign data using the specified hash function''' + if self._priv: + h = dec_long(hashlib.new(hashfunc, data).digest()) + s = ecdsa.sign(h, self._priv) + return enc_point(s) + else: + raise AttributeError, "Private key needed for signing." + + def verify(self, data, sig, hashfunc = 'sha256'): + '''Verify the signature of data using the specified hash function''' + h = dec_long(hashlib.new(hashfunc, data).digest()) + s = dec_point(sig) + return ecdsa.verify(h, s, self._pub) + + # --- HYBRID ENCRYPTION ---------------------------------------------------- + + def encrypt(self, data): + '''Encrypt a message using this public key''' + ctext, mkey = encrypt(data, self._pub) + return Encoder().point(mkey).str(ctext, 4).out() + + def decrypt(self, data): + '''Decrypt an encrypted message using this private key''' + mkey, ctext = Decoder(data).point().str(4).out() + return decrypt(ctext, mkey, self._priv) + + # --- AUTHENTICATED ENCRYPTION --------------------------------------------- + + def auth_encrypt(self, data, receiver): + '''Sign and encrypt a message''' + sgn = self.sign(data) + ctext, mkey = encrypt(data, receiver._pub) + return Encoder().point(mkey).str(ctext, 4).str(sgn, 2).out() + + def auth_decrypt(self, data, source): + '''Decrypt and verify a message''' + mkey, ctext, sgn = Decoder(data).point().str(4).str(2).out() + text = decrypt(ctext, mkey, self._priv) + if source.verify(text, sgn): + return text + else: + raise SecurityViolationException, "Invalid Signature" + + +if __name__ == "__main__": + + import time + + def test_overhead(): + print "sender", "receiver", "+bytes", "+enctime", "+dectime" + for s in [192, 224, 256, 384, 521]: + sender = Key.generate(s) + for r in [192, 224, 256, 384, 521]: + receiver = Key.generate(r) + t = time.time() + e = sender.auth_encrypt("", receiver) + t1 = time.time() - t + t = time.time() + receiver.auth_decrypt(e, sender) + t2 = time.time() - t + print s, r, len(e), t1, t2 + + + + diff --git a/python/PyECC/ecc/Rabbit.py b/python/PyECC/ecc/Rabbit.py new file mode 100644 index 000000000..209f01e1e --- /dev/null +++ b/python/PyECC/ecc/Rabbit.py @@ -0,0 +1,270 @@ +# ------------------------------------------------------------------------------ +# +# R A B B I T Stream Cipher +# by M. Boesgaard, M. Vesterager, E. Zenner (specified in RFC 4503) +# +# +# Pure Python Implementation by Toni Mattis +# +# ------------------------------------------------------------------------------ + + +WORDSIZE = 0x100000000 + +rot08 = lambda x: ((x << 8) & 0xFFFFFFFF) | (x >> 24) +rot16 = lambda x: ((x << 16) & 0xFFFFFFFF) | (x >> 16) + +def _nsf(u, v): + '''Internal non-linear state transition''' + s = (u + v) % WORDSIZE + s = s * s + return (s ^ (s >> 32)) % WORDSIZE + +class Rabbit: + + def __init__(self, key, iv = None): + '''Initialize Rabbit cipher using a 128 bit integer/string''' + + if isinstance(key, str): + # interpret key string in big endian byte order + if len(key) < 16: + key = '\x00' * (16 - len(key)) + key + # if len(key) > 16 bytes only the first 16 will be considered + k = [ord(key[i + 1]) | (ord(key[i]) << 8) + for i in xrange(14, -1, -2)] + else: + # k[0] = least significant 16 bits + # k[7] = most significant 16 bits + k = [(key >> i) & 0xFFFF for i in xrange(0, 128, 16)] + + # State and counter initialization + x = [(k[(j + 5) % 8] << 16) | k[(j + 4) % 8] if j & 1 else + (k[(j + 1) % 8] << 16) | k[j] for j in xrange(8)] + c = [(k[j] << 16) | k[(j + 1) % 8] if j & 1 else + (k[(j + 4) % 8] << 16) | k[(j + 5) % 8] for j in xrange(8)] + + self.x = x + self.c = c + self.b = 0 + self._buf = 0 # output buffer + self._buf_bytes = 0 # fill level of buffer + + self.next() + self.next() + self.next() + self.next() + + for j in xrange(8): + c[j] ^= x[(j + 4) % 8] + + self.start_x = self.x[:] # backup initial key for IV/reset + self.start_c = self.c[:] + self.start_b = self.b + + if iv != None: + self.set_iv(iv) + + def reset(self, iv = None): + '''Reset the cipher and optionally set a new IV (int64 / string).''' + + self.c = self.start_c[:] + self.x = self.start_x[:] + self.b = self.start_b + self._buf = 0 + self._buf_bytes = 0 + if iv != None: + self.set_iv(iv) + + def set_iv(self, iv): + '''Set a new IV (64 bit integer / bytestring).''' + + if isinstance(iv, str): + i = 0 + for c in iv: + i = (i << 8) | ord(c) + iv = i + + c = self.c + i0 = iv & 0xFFFFFFFF + i2 = iv >> 32 + i1 = ((i0 >> 16) | (i2 & 0xFFFF0000)) % WORDSIZE + i3 = ((i2 << 16) | (i0 & 0x0000FFFF)) % WORDSIZE + + c[0] ^= i0 + c[1] ^= i1 + c[2] ^= i2 + c[3] ^= i3 + c[4] ^= i0 + c[5] ^= i1 + c[6] ^= i2 + c[7] ^= i3 + + self.next() + self.next() + self.next() + self.next() + + + def next(self): + '''Proceed to the next internal state''' + + c = self.c + x = self.x + b = self.b + + t = c[0] + 0x4D34D34D + b + c[0] = t % WORDSIZE + t = c[1] + 0xD34D34D3 + t // WORDSIZE + c[1] = t % WORDSIZE + t = c[2] + 0x34D34D34 + t // WORDSIZE + c[2] = t % WORDSIZE + t = c[3] + 0x4D34D34D + t // WORDSIZE + c[3] = t % WORDSIZE + t = c[4] + 0xD34D34D3 + t // WORDSIZE + c[4] = t % WORDSIZE + t = c[5] + 0x34D34D34 + t // WORDSIZE + c[5] = t % WORDSIZE + t = c[6] + 0x4D34D34D + t // WORDSIZE + c[6] = t % WORDSIZE + t = c[7] + 0xD34D34D3 + t // WORDSIZE + c[7] = t % WORDSIZE + b = t // WORDSIZE + + g = [_nsf(x[j], c[j]) for j in xrange(8)] + + x[0] = (g[0] + rot16(g[7]) + rot16(g[6])) % WORDSIZE + x[1] = (g[1] + rot08(g[0]) + g[7]) % WORDSIZE + x[2] = (g[2] + rot16(g[1]) + rot16(g[0])) % WORDSIZE + x[3] = (g[3] + rot08(g[2]) + g[1]) % WORDSIZE + x[4] = (g[4] + rot16(g[3]) + rot16(g[2])) % WORDSIZE + x[5] = (g[5] + rot08(g[4]) + g[3]) % WORDSIZE + x[6] = (g[6] + rot16(g[5]) + rot16(g[4])) % WORDSIZE + x[7] = (g[7] + rot08(g[6]) + g[5]) % WORDSIZE + + self.b = b + return self + + + def derive(self): + '''Derive a 128 bit integer from the internal state''' + + x = self.x + return ((x[0] & 0xFFFF) ^ (x[5] >> 16)) | \ + (((x[0] >> 16) ^ (x[3] & 0xFFFF)) << 16)| \ + (((x[2] & 0xFFFF) ^ (x[7] >> 16)) << 32)| \ + (((x[2] >> 16) ^ (x[5] & 0xFFFF)) << 48)| \ + (((x[4] & 0xFFFF) ^ (x[1] >> 16)) << 64)| \ + (((x[4] >> 16) ^ (x[7] & 0xFFFF)) << 80)| \ + (((x[6] & 0xFFFF) ^ (x[3] >> 16)) << 96)| \ + (((x[6] >> 16) ^ (x[1] & 0xFFFF)) << 112) + + + def keystream(self, n): + '''Generate a keystream of n bytes''' + + res = "" + b = self._buf + j = self._buf_bytes + next = self.next + derive = self.derive + + for i in xrange(n): + if not j: + j = 16 + next() + b = derive() + res += chr(b & 0xFF) + j -= 1 + b >>= 1 + + self._buf = b + self._buf_bytes = j + return res + + + def encrypt(self, data): + '''Encrypt/Decrypt data of arbitrary length.''' + + res = "" + b = self._buf + j = self._buf_bytes + next = self.next + derive = self.derive + + for c in data: + if not j: # empty buffer => fetch next 128 bits + j = 16 + next() + b = derive() + res += chr(ord(c) ^ (b & 0xFF)) + j -= 1 + b >>= 1 + self._buf = b + self._buf_bytes = j + return res + + decrypt = encrypt + + + +if __name__ == "__main__": + + import time + + # --- Official Test Vectors --- + + # RFC 4503 Appendix A.1 - Testing without IV Setup + + r = Rabbit(0) + assert r.next().derive() == 0xB15754F036A5D6ECF56B45261C4AF702 + assert r.next().derive() == 0x88E8D815C59C0C397B696C4789C68AA7 + assert r.next().derive() == 0xF416A1C3700CD451DA68D1881673D696 + + r = Rabbit(0x912813292E3D36FE3BFC62F1DC51C3AC) + assert r.next().derive() == 0x3D2DF3C83EF627A1E97FC38487E2519C + assert r.next().derive() == 0xF576CD61F4405B8896BF53AA8554FC19 + assert r.next().derive() == 0xE5547473FBDB43508AE53B20204D4C5E + + r = Rabbit(0x8395741587E0C733E9E9AB01C09B0043) + assert r.next().derive() == 0x0CB10DCDA041CDAC32EB5CFD02D0609B + assert r.next().derive() == 0x95FC9FCA0F17015A7B7092114CFF3EAD + assert r.next().derive() == 0x9649E5DE8BFC7F3F924147AD3A947428 + + # RFC 4503 Appendix A.2 - Testing with IV Setup + + r = Rabbit(0, 0) + assert r.next().derive() == 0xC6A7275EF85495D87CCD5D376705B7ED + assert r.next().derive() == 0x5F29A6AC04F5EFD47B8F293270DC4A8D + assert r.next().derive() == 0x2ADE822B29DE6C1EE52BDB8A47BF8F66 + + r = Rabbit(0, 0xC373F575C1267E59) + assert r.next().derive() == 0x1FCD4EB9580012E2E0DCCC9222017D6D + assert r.next().derive() == 0xA75F4E10D12125017B2499FFED936F2E + assert r.next().derive() == 0xEBC112C393E738392356BDD012029BA7 + + r = Rabbit(0, 0xA6EB561AD2F41727) + assert r.next().derive() == 0x445AD8C805858DBF70B6AF23A151104D + assert r.next().derive() == 0x96C8F27947F42C5BAEAE67C6ACC35B03 + assert r.next().derive() == 0x9FCBFC895FA71C17313DF034F01551CB + + + # --- Performance Tests --- + + def test_gen(n = 1048576): + '''Measure time for generating n bytes => (total, bytes per second)''' + + r = Rabbit(0) + t = time.time() + r.keystream(n) + t = time.time() - t + return t, n / t + + def test_enc(n = 1048576): + '''Measure time for encrypting n bytes => (total, bytes per second)''' + + r = Rabbit(0) + x = 'x' * n + t = time.time() + r.encrypt(x) + t = time.time() - t + return t, n / t diff --git a/python/PyECC/ecc/SecurityViolationException.py b/python/PyECC/ecc/SecurityViolationException.py new file mode 100644 index 000000000..c4fc13687 --- /dev/null +++ b/python/PyECC/ecc/SecurityViolationException.py @@ -0,0 +1,2 @@ +class SecurityViolationException(Exception): + pass diff --git a/python/PyECC/ecc/__init__.py b/python/PyECC/ecc/__init__.py new file mode 100644 index 000000000..e69de29bb diff --git a/python/PyECC/ecc/curves.py b/python/PyECC/ecc/curves.py new file mode 100644 index 000000000..ee5847fc5 --- /dev/null +++ b/python/PyECC/ecc/curves.py @@ -0,0 +1,81 @@ +# +# Predefined Elliptic Curves +# for use in signing and key exchange +# +''' +Predefined elliptic curves for use in signing and key exchange. +This Module implements FIPS approved standard curves P-192, P-224, P-256, +P-384 and P-521 along with two weak non-standard curves of field size 128 +and 160 bits. + +The weak curves cannot be used for signing but provide a faster way to +obfuscate non-critical transmissions. +''' + +# FIPS approved elliptic curves over prime fields +# (see FIPS 186-3, Appendix D.1.2) +DOMAINS = { + # Bits : (p, order of E(GF(P)), parameter b, base point x, base point y) + 192 : (0xfffffffffffffffffffffffffffffffeffffffffffffffffL, + 0xffffffffffffffffffffffff99def836146bc9b1b4d22831L, + 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1L, + 0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012L, + 0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811L), + + 224 : (0xffffffffffffffffffffffffffffffff000000000000000000000001L, + 0xffffffffffffffffffffffffffff16a2e0b8f03e13dd29455c5c2a3dL, + 0xb4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4L, + 0xb70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21L, + 0xbd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34L), + + 256 : (0xffffffff00000001000000000000000000000000ffffffffffffffffffffffffL, + 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551L, + 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604bL, + 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296L, + 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5L), + + 384 : (0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000000000ffffffffL, + 0xffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf581a0db248b0a77aecec196accc52973L, + 0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aefL, + 0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7L, + 0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5fL), + + 521 : (0x1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffL, + 0x1fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffa51868783bf2f966b7fcc0148f709a5d03bb5c9b8899c47aebb6fb71e91386409L, + 0x051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00L, + 0x0c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66L, + 0x11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650L) + } + + +# Additional non-standard curves for low security but high performance +# (not intended for use in signing, hence the missing group order) + +DOMAINS.update({ + 128 : (0xffffffffffffffffffffffffffffff61L, + None, + 0xd83d3eb8266a89927d73d5fe263d5f23L, + 0xa94d2d8531f7af8bde367def12b98eadL, + 0x9f44e1d671beb68fd2df7f877ab13fa6L), + + 160 : (0xffffffffffffffffffffffffffffffffffffffd1L, + None, + 0x94bfe70deef7b94742c089ca4db3ca27fbe1f754L, + 0xcc6562c2969ac57524b8d0f300d1f598c908c121L, + 0x952ddde80a252683dd7ba90fb5919899b5af69f5L) + }) + +CURVE_P = 3 # global parameter of all curves (for efficiency reasons) + + +def get_curve(bits): + '''Get a known curve of the given size => (bits, prime, order, p, q, point). + Order may be None if unknown.''' + if bits in DOMAINS: + p, n, b, x, y = DOMAINS[bits] + return bits, p, n, CURVE_P, p - b, (x, y) + else: + raise KeyError, "Key size not implemented: %s" % bits + +def implemented_keys(must_sign = False): + return [k for k in DOMAINS if not must_sign or DOMAINS[k][1]] diff --git a/python/PyECC/ecc/eccrypt.py b/python/PyECC/ecc/eccrypt.py new file mode 100644 index 000000000..c38876d07 --- /dev/null +++ b/python/PyECC/ecc/eccrypt.py @@ -0,0 +1,65 @@ +# Elliptic Curve Hybrid Encryption Scheme +# +# COPYRIGHT (c) 2010 by Toni Mattis +# + +from curves import get_curve +from elliptic import mulp +from encoding import enc_long +from random import SystemRandom +from Rabbit import Rabbit + +# important for cryptographically secure random numbers: +random = SystemRandom() + +# Encryption Algorithm: +# --------------------- +# Input: Message M, public key Q +# +# 0. retrieve the group from which Q was generated. +# 1. generate random number k between 1 and the group order. +# 2. compute KG = k * G (where G is the base point of the group). +# 3. compute SG = k * Q (where Q is the public key of the receiver). +# 4. symmetrically encrypt M to M' using SG's x-coordinate as key. +# +# Return: Ciphertext M', temporary key KG + + +def encrypt(message, qk, encrypter = Rabbit): + '''Encrypt a message using public key qk => (ciphertext, temp. pubkey)''' + bits, q = qk + try: + bits, cn, n, cp, cq, g = get_curve(bits) + if not n: + raise ValueError, "Key size %s not suitable for encryption" % bits + except KeyError: + raise ValueError, "Key size %s not implemented" % bits + + k = random.randint(1, n - 1) # temporary private key k + kg = mulp(cp, cq, cn, g, k) # temporary public key k*G + sg = mulp(cp, cq, cn, q, k) # shared secret k*Q = k*d*G + + return encrypter(enc_long(sg[0])).encrypt(message), kg + +# Decryption Algorithm: +# --------------------- +# Input: Ciphertext M', temporary key KG, private key d +# +# 0. retrieve the group from which d and KG were generated. +# 1. compute SG = q * KG. +# 2. symmetrically decrypt M' to M using SG's x-coordinate as key. +# +# Return: M + +def decrypt(message, kg, dk, decrypter = Rabbit): + '''Decrypt a message using temp. public key kg and private key dk''' + bits, d = dk + try: + bits, cn, n, cp, cq, g = get_curve(bits) + except KeyError: + raise ValueError, "Key size %s not implemented" % bits + + sg = mulp(cp, cq, cn, kg, d) # shared secret d*(k*G) = k*d*G + return decrypter(enc_long(sg[0])).decrypt(message) + + diff --git a/python/PyECC/ecc/ecdsa.py b/python/PyECC/ecc/ecdsa.py new file mode 100644 index 000000000..6b52aeaa5 --- /dev/null +++ b/python/PyECC/ecc/ecdsa.py @@ -0,0 +1,153 @@ +# +# Elliptic Curve Digital Signature Algorithm (ECDSA) +# +# COPYRIGHT (c) 2010 by Toni Mattis +# + +from elliptic import inv, mulf, mulp, muladdp, element +from curves import get_curve, implemented_keys +from os import urandom + +import hashlib + +def randkey(bits, n): + '''Generate a random number (mod n) having the specified bit length''' + rb = urandom(bits / 8 + 8) # + 64 bits as recommended in FIPS 186-3 + c = 0 + for r in rb: + c = (c << 8) | ord(r) + return (c % (n - 1)) + 1 + +def keypair(bits): + '''Generate a new keypair (qk, dk) with dk = private and qk = public key''' + try: + bits, cn, n, cp, cq, g = get_curve(bits) + except KeyError: + raise ValueError, "Key size %s not implemented" % bits + if n > 0: + d = randkey(bits, n) + q = mulp(cp, cq, cn, g, d) + return (bits, q), (bits, d) + else: + raise ValueError, "Key size %s not suitable for signing" % bits + +def supported_keys(): + '''Return a list of all key sizes implemented for signing''' + return implemented_keys(True) + +def validate_public_key(qk): + '''Check whether public key qk is valid''' + bits, q = qk + x, y = q + bits, cn, n, cp, cq, g = get_curve(bits) + return q and 0 < x < cn and 0 < y < cn and \ + element(q, cp, cq, cn) and (mulp(cp, cq, cn, q, n) == None) + +def validate_private_key(dk): + '''Check whether private key dk is valid''' + bits, d = dk + bits, cn, n, cp, cq, g = get_curve(bits) + return 0 < d < cn + +def match_keys(qk, dk): + '''Check whether dk is the private key belonging to qk''' + bits, d = dk + bitz, q = qk + if bits == bitz: + bits, cn, n, cp, cq, g = get_curve(bits) + return mulp(cp, cq, cn, g, d) == q + else: + return False + +def truncate(h, hmax): + '''Truncate a hash to the bit size of hmax''' + while h > hmax: + h >>= 1 + return h + +def sign(h, dk): + '''Sign the numeric value h using private key dk''' + bits, d = dk + bits, cn, n, cp, cq, g = get_curve(bits) + h = truncate(h, cn) + r = s = 0 + while r == 0 or s == 0: + k = randkey(bits, cn) + kinv = inv(k, n) + kg = mulp(cp, cq, cn, g, k) + r = kg[0] % n + if r == 0: + continue + s = (kinv * (h + r * d)) % n + return r, s + +def verify(h, sig, qk): + '''Verify that 'sig' is a valid signature of h using public key qk''' + bits, q = qk + try: + bits, cn, n, cp, cq, g = get_curve(bits) + except KeyError: + return False + h = truncate(h, cn) + r, s = sig + if 0 < r < n and 0 < s < n: + w = inv(s, n) + u1 = (h * w) % n + u2 = (r * w) % n + x, y = muladdp(cp, cq, cn, g, u1, q, u2) + return r % n == x % n + return False + +def hash_sign(s, dk, hashfunc = 'sha256'): + h = int(hashlib.new(hashfunc, s).hexdigest(), 16) + return (hashfunc,) + sign(h, dk) + +def hash_verify(s, sig, qk): + h = int(hashlib.new(sig[0], s).hexdigest(), 16) + return verify(h, sig[1:], qk) + + +if __name__ == "__main__": + + import time + + testh1 = 0x0123456789ABCDEF + testh2 = 0x0123456789ABCDEE + + for k in supported_keys(): + qk, dk = keypair(k) + s1 = sign(testh1, dk) + s2 = sign(testh1, (dk[0], dk[1] ^ 1)) + s3 = (s1[0], s1[1] ^ 1) + qk2 = (qk[0], (qk[1][0] ^ 1, qk[1][1])) + + assert verify(testh1, s1, qk) # everything ok -> must succeed + assert not verify(testh2, s1, qk) # modified hash -> must fail + assert not verify(testh1, s2, qk) # different priv. key -> must fail + assert not verify(testh1, s3, qk) # modified signature -> must fail + assert not verify(testh1, s1, qk2) # different publ. key -> must fail + + + def test_perf(bits, rounds = 50): + '''-> (key generations, signatures, verifications) / second''' + h = 0x0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF + d = get_curve(bits) + + t = time.time() + for i in xrange(rounds): + qk, dk = keypair(bits) + tgen = time.time() - t + + t = time.time() + for i in xrange(rounds): + s = sign(0, dk) + tsign = time.time() - t + + t = time.time() + for i in xrange(rounds): + verify(0, s, qk) + tver = time.time() - t + + return rounds / tgen, rounds / tsign, rounds / tver + + diff --git a/python/PyECC/ecc/elliptic.py b/python/PyECC/ecc/elliptic.py new file mode 100644 index 000000000..9191a8848 --- /dev/null +++ b/python/PyECC/ecc/elliptic.py @@ -0,0 +1,381 @@ + +# --- ELLIPTIC CURVE MATH ------------------------------------------------------ +# +# curve definition: y^2 = x^3 - p*x - q +# over finite field: Z/nZ* (prime residue classes modulo a prime number n) +# +# +# COPYRIGHT (c) 2010 by Toni Mattis +# ------------------------------------------------------------------------------ + +''' +Module for elliptic curve arithmetic over a prime field GF(n). +E(GF(n)) takes the form y**2 == x**3 - p*x - q (mod n) for a prime n. + +0. Structures used by this module + + PARAMETERS and SCALARS are non-negative (long) integers. + + A POINT (x, y), usually denoted p1, p2, ... + is a pair of (long) integers where 0 <= x < n and 0 <= y < n + + A POINT in PROJECTIVE COORDINATES, usually denoted jp1, jp2, ... + takes the form (X, Y, Z, Z**2, Z**3) where x = X / Z**2 + and y = Y / z**3. This form is called Jacobian coordinates. + + The NEUTRAL element "0" or "O" is represented by None + in both coordinate systems. + +1. Basic Functions + + euclid() Is the Extended Euclidean Algorithm. + inv() Computes the multiplicative inversion modulo n. + curve_q() Finds the curve parameter q (mod n) + when p and a point are given. + element() Tests whether a point (x, y) is on the curve. + +2. Point transformations + + to_projective() Converts a point (x, y) to projective coordinates. + from_projective() Converts a point from projective coordinates + to (x, y) using the transformation described above. + neg() Computes the inverse point -P in both coordinate + systems. + +3. Slow point arithmetic + + These algorithms make use of basic geometry and modular arithmetic + thus being suitable for small numbers and academic study. + + add() Computes the sum of two (x, y)-points + mul() Perform scalar multiplication using "double & add" + +4. Fast point arithmetic + + These algorithms make use of projective coordinates, signed binary + expansion and a JSP-like approach (joint sparse form). + + The following functions consume and return projective coordinates: + + addf() Optimized point addition. + doublef() Optimized point doubling. + mulf() Highly optimized scalar multiplication. + muladdf() Highly optimized addition of two products. + + The following functions use the optimized ones above but consume + and output (x, y)-coordinates for a more convenient usage: + + mulp() Encapsulates mulf() + muladdp() Encapsulates muladdf() + + For single additions add() is generally faster than an encapsulation of + addf() which would involve expensive coordinate transformations. + Hence there is no addp() and doublep(). +''' + +# BASIC MATH ------------------------------------------------------------------- + +def euclid(a, b): + '''Solve x*a + y*b = ggt(a, b) and return (x, y, ggt(a, b))''' + # Non-recursive approach hence suitable for large numbers + x = yy = 0 + y = xx = 1 + while b: + q = a // b + a, b = b, a % b + x, xx = xx - q * x, x + y, yy = yy - q * y, y + return xx, yy, a + +def inv(a, n): + '''Perform inversion 1/a modulo n. a and n should be COPRIME.''' + # coprimality is not checked here in favour of performance + i = euclid(a, n)[0] + while i < 0: + i += n + return i + +def curve_q(x, y, p, n): + '''Find curve parameter q mod n having point (x, y) and parameter p''' + return ((x * x - p) * x - y * y) % n + +def element(point, p, q, n): + '''Test, whether the given point is on the curve (p, q, n)''' + if point: + x, y = point + return (x * x * x - p * x - q) % n == (y * y) % n + else: + return True + +def to_projective(p): + '''Transform point p given as (x, y) to projective coordinates''' + if p: + return (p[0], p[1], 1, 1, 1) + else: + return None # Identity point (0) + +def from_projective(jp, n): + '''Transform a point from projective coordinates to (x, y) mod n''' + if jp: + return (jp[0] * inv(jp[3], n)) % n, (jp[1] * inv(jp[4], n)) % n + else: + return None # Identity point (0) + +def neg(p, n): + '''Compute the inverse point to p in any coordinate system''' + return (p[0], (n - p[1]) % n) + p[2:] if p else None + + +# POINT ADDITION --------------------------------------------------------------- + +# addition of points in y**2 = x**3 - p*x - q over +def add(p, q, n, p1, p2): + '''Add points p1 and p2 over curve (p, q, n)''' + if p1 and p2: + x1, y1 = p1 + x2, y2 = p2 + if (x1 - x2) % n: + s = ((y1 - y2) * inv(x1 - x2, n)) % n # slope + x = (s * s - x1 - x2) % n # intersection with curve + return (x, n - (y1 + s * (x - x1)) % n) + else: + if (y1 + y2) % n: # slope s calculated by derivation + s = ((3 * x1 * x1 - p) * inv(2 * y1, n)) % n + x = (s * s - 2 * x1) % n # intersection with curve + return (x, n - (y1 + s * (x - x1)) % n) + else: + return None + else: # either p1 is not none -> ret. p1, otherwiese p2, which may be + return p1 if p1 else p2 # none too. + + +# faster addition: redundancy in projective coordinates eliminates +# expensive inversions mod n. +def addf(p, q, n, jp1, jp2): + '''Add jp1 and jp2 in projective (jacobian) coordinates.''' + if jp1 and jp2: + + x1, y1, z1, z1s, z1c = jp1 + x2, y2, z2, z2s, z2c = jp2 + + s1 = (y1 * z2c) % n + s2 = (y2 * z1c) % n + + u1 = (x1 * z2s) % n + u2 = (x2 * z1s) % n + + if (u1 - u2) % n: + + h = (u2 - u1) % n + r = (s2 - s1) % n + + hs = (h * h) % n + hc = (hs * h) % n + + x3 = (-hc - 2 * u1 * hs + r * r) % n + y3 = (-s1 * hc + r * (u1 * hs - x3)) % n + z3 = (z1 * z2 * h) % n + + z3s = (z3 * z3) % n + z3c = (z3s * z3) % n + + return (x3, y3, z3, z3s, z3c) + + else: + if (s1 + s2) % n: + return doublef(p, q, n, jp1) + else: + return None + else: + return jp1 if jp1 else jp2 + +# explicit point doubling using redundant coordinates +def doublef(p, q, n, jp): + '''Double jp in projective (jacobian) coordinates''' + if not jp: + return None + x1, y1, z1, z1p2, z1p3 = jp + + y1p2 = (y1 * y1) % n + a = (4 * x1 * y1p2) % n + b = (3 * x1 * x1 - p * z1p3 * z1) % n + x3 = (b * b - 2 * a) % n + y3 = (b * (a - x3) - 8 * y1p2 * y1p2) % n + z3 = (2 * y1 * z1) % n + z3p2 = (z3 * z3) % n + + return x3, y3, z3, z3p2, (z3p2 * z3) % n + + +# SCALAR MULTIPLICATION -------------------------------------------------------- + +# scalar multiplication p1 * c = p1 + p1 + ... + p1 (c times) in O(log(n)) +def mul(p, q, n, p1, c): + '''multiply point p1 by scalar c over curve (p, q, n)''' + res = None + while c > 0: + if c & 1: + res = add(p, q, n, res, p1) + c >>= 1 # c = c / 2 + p1 = add(p, q, n, p1, p1) # p1 = p1 * 2 + return res + + +# this method allows _signed_bin() to choose between 1 and -1. It will select +# the sign which leaves the higher number of zeroes in the binary +# representation (the higher GDB). +def _gbd(n): + '''Compute second greatest base-2 divisor''' + i = 1 + if n <= 0: return 0 + while not n % i: + i <<= 1 + return i >> 2 + + +# This method transforms n into a binary representation having signed bits. +# A signed binary expansion contains more zero-bits hence reducing the number +# of additions required by a multiplication algorithm. +# +# Example: 15 ( 0b1111 ) can be written as 16 - 1, resulting in (1,0,0,0,-1) +# and saving 2 additions. Subtraction can be performed as +# efficiently as addition. +def _signed_bin(n): + '''Transform n into an optimized signed binary representation''' + r = [] + while n > 1: + if n & 1: + cp = _gbd(n + 1) + cn = _gbd(n - 1) + if cp > cn: # -1 leaves more zeroes -> subtract -1 (= +1) + r.append(-1) + n += 1 + else: # +1 leaves more zeroes -> subtract +1 (= -1) + r.append(+1) + n -= 1 + else: + r.append(0) # be glad about one more zero + n >>= 1 + r.append(n) + return r[::-1] + + +# This multiplication algorithm combines signed binary expansion and +# fast addition using projective coordinates resulting in 5 to 10 times +# faster multiplication. +def mulf(p, q, n, jp1, c): + '''Multiply point jp1 by c in projective coordinates''' + sb = _signed_bin(c) + res = None + jp0 = neg(jp1, n) # additive inverse of jp1 to be used fot bit -1 + for s in sb: + res = doublef(p, q, n, res) + if s: + res = addf(p, q, n, res, jp1) if s > 0 else \ + addf(p, q, n, res, jp0) + return res + +# Encapsulates mulf() in order to enable flat coordinates (x, y) +def mulp(p, q, n, p1, c): + '''Multiply point p by c using fast multiplication''' + return from_projective(mulf(p, q, n, to_projective(p1), c), n) + + +# Sum of two products using Shamir's trick and signed binary expansion +def muladdf(p, q, n, jp1, c1, jp2, c2): + '''Efficiently compute c1 * jp1 + c2 * jp2 in projective coordinates''' + s1 = _signed_bin(c1) + s2 = _signed_bin(c2) + diff = len(s2) - len(s1) + if diff > 0: + s1 = [0] * diff + s1 + elif diff < 0: + s2 = [0] * -diff + s2 + + jp1p2 = addf(p, q, n, jp1, jp2) + jp1n2 = addf(p, q, n, jp1, neg(jp2, n)) + + precomp = ((None, jp2, neg(jp2, n)), + (jp1, jp1p2, jp1n2), + (neg(jp1, n), neg(jp1n2, n), neg(jp1p2, n))) + res = None + + for i, j in zip(s1, s2): + res = doublef(p, q, n, res) + if i or j: + res = addf(p, q, n, res, precomp[i][j]) + return res + +# Encapsulate muladdf() +def muladdp(p, q, n, p1, c1, p2, c2): + '''Efficiently compute c1 * p1 + c2 * p2 in (x, y)-coordinates''' + return from_projective(muladdf(p, q, n, + to_projective(p1), c1, + to_projective(p2), c2), n) + +# POINT COMPRESSION ------------------------------------------------------------ + +# Compute the square root modulo n + + +# Determine the sign-bit of a point allowing to reconstruct y-coordinates +# when x and the sign-bit are given: +def sign_bit(p1): + '''Return the signedness of a point p1''' + return p1[1] % 2 if p1 else 0 + +# Reconstruct the y-coordinate when curve parameters, x and the sign-bit of +# the y coordinate are given: +def y_from_x(x, p, q, n, sign): + '''Return the y coordinate over curve (p, q, n) for given (x, sign)''' + + # optimized form of (x**3 - p*x - q) % n + a = (((x * x) % n - p) * x - q) % n + + + +if __name__ == "__main__": + import rsa + import time + + t = time.time() + n = rsa.get_prime(256/8, 20) + tp = time.time() - t + p = rsa.random.randint(1, n) + p1 = (rsa.random.randint(1, n), rsa.random.randint(1, n)) + q = curve_q(p1[0], p1[1], p, n) + r1 = rsa.random.randint(1,n) + r2 = rsa.random.randint(1,n) + q1 = mulp(p, q, n, p1, r1) + q2 = mulp(p, q, n, p1, r2) + s1 = mulp(p, q, n, q1, r2) + s2 = mulp(p, q, n, q2, r1) + s1 == s2 + tt = time.time() - t + + def test(tcount, bits = 256): + n = rsa.get_prime(bits/8, 20) + p = rsa.random.randint(1, n) + p1 = (rsa.random.randint(1, n), rsa.random.randint(1, n)) + q = curve_q(p1[0], p1[1], p, n) + p2 = mulp(p, q, n, p1, rsa.random.randint(1, n)) + + c1 = [rsa.random.randint(1, n) for i in xrange(tcount)] + c2 = [rsa.random.randint(1, n) for i in xrange(tcount)] + c = zip(c1, c2) + + t = time.time() + for i, j in c: + from_projective(addf(p, q, n, + mulf(p, q, n, to_projective(p1), i), + mulf(p, q, n, to_projective(p2), j)), n) + t1 = time.time() - t + t = time.time() + for i, j in c: + muladdp(p, q, n, p1, i, p2, j) + t2 = time.time() - t + + return tcount, t1, t2 + + + diff --git a/python/PyECC/ecc/encoding.py b/python/PyECC/ecc/encoding.py new file mode 100644 index 000000000..24d3eb5a8 --- /dev/null +++ b/python/PyECC/ecc/encoding.py @@ -0,0 +1,178 @@ +# +# Encodings and Formats for Elliptic Curve Cryptography +# + +import StringIO + +# Big-Endian Encoding + +def enc_long(n): + '''Encodes arbitrarily large number n to a sequence of bytes. + Big endian byte order is used.''' + s = "" + while n > 0: + s = chr(n & 0xFF) + s + n >>= 8 + return s + +def enc_int(n): + '''Encodes an integer n to a 4-byte string. + Big endian byte order is used.''' + return chr((n >> 24) & 0xFF) + chr((n >> 16) & 0xFF) + \ + chr((n >> 8) & 0xFF) + chr( n & 0xFF) + +def enc_fixed_long(n, length): + return enc_long(n)[:length].rjust(length, '\x00') + +def dec_long(s): + '''Decodes s to its numeric representation. + Big endian byte order is used.''' + n = 0 + for c in s: + n = (n << 8) | ord(c) + return n + +# dec_int not necessary, +# dec_long does the same when provided with 4 bytes input. + +# Chunks + +def enc_chunks(*args): + '''Chain given string args or sub-chunks to a single chunk''' + return ''.join([enc_int(len(a)) + a for a in args]) + +def dec_chunks(s): + '''Split a chunk into strings or sub-chunks''' + i = 0 + result = [] + while i < len(s): + size = dec_long(s[i : i + 4]) + i += 4 + result.append(s[i : i + size]) + i += size + return result + +# Point and signature data + +def enc_point(p): + '''Encode a point p = (x, y)''' + x, y = p + sx = enc_long(x) + sy = enc_long(y) + diff = len(sx) - len(sy) + if diff > 0: + sy = '\x00' * diff + sy + elif diff < 0: + sx = '\x00' * -diff + sx + return sx + sy + +def dec_point(s): + '''Decode an even length string s to a point(x, y)''' + d = len(s) / 2 + return (dec_long(s[:d]), dec_long(s[d:])) + + +class Encoder: + + def __init__(self): + self._io = StringIO.StringIO() + + def int(self, n, size = 4): + self._io.write(enc_fixed_long(n, size)) + return self + + def long(self, n, pre = 2): + lstr = enc_long(n) + self._io.write(enc_fixed_long(len(lstr), pre) + lstr) + return self + + def str(self, s, pre = 2): + self._io.write(enc_fixed_long(len(s), pre) + s) + return self + + def point(self, p, pre = 2): + lstr = enc_point(p) + self._io.write(enc_fixed_long(len(lstr), pre) + lstr) + return self + + def chunk(self, enc, pre = 2): + lstr = enc.out() + self._io.write(enc_fixed_long(len(lstr), pre) + lstr) + return self + + def out(self): + return self._io.getvalue() + +class Decoder: + + def __init__(self, data, offset = 0): + self._io = StringIO.StringIO(data) + self._io.seek(offset) + self._res = [] + self._limit = None + self._parent = None + + def _ret(self): +## if self._parent and self._io.tell() >= self._limit: +## return self.exit() +## else: +## return self + return self + + def int(self, size = 4): + self._res.append(dec_long(self._io.read(size))) + return self._ret() + + + def long(self, pre = 2): + llen = dec_long(self._io.read(pre)) + self._res.append(dec_long(self._io.read(llen))) + return self._ret() + + def str(self, pre = 2): + llen = dec_long(self._io.read(pre)) + self._res.append(self._io.read(llen)) + return self._ret() + + def point(self, pre = 2): + llen = dec_long(self._io.read(pre)) + self._res.append(dec_point(self._io.read(llen))) + return self._ret() + + def enter(self, pre = 2): + llen = dec_long(self._io.read(pre)) + subcoder = Decoder("") + subcoder._io = self._io + subcoder._parent = self + subcoder._limit = self._io.tell() + llen + return subcoder + + def chunk(self, pre = 2): + llen = dec_long(self._io.read(pre)) + self._res.append(Decoder(self._io.read(llen))) + return self._ret() + + def exit(self): + if self._parent: + self._parent._io.seek(self._limit) + self._parent._res.append(self._res) + return self._parent + else: + raise RuntimeError, "Cannont exit top level Decoder" + + def continues(self): + return (not self._limit) or (self._io.tell() < self._limit) + + def out(self, exit_all = False): + if exit_all and self._parent: + return self.exit().out() + else: + r = self._res + self._res = [] + return r + + def only(self): + if self._res: + return self._res.pop(0) + else: + return RuntimeError, "Only what? (Empty decoder stack)" diff --git a/python/PyECC/ecc/performance.py b/python/PyECC/ecc/performance.py new file mode 100644 index 000000000..724176aef --- /dev/null +++ b/python/PyECC/ecc/performance.py @@ -0,0 +1,50 @@ +from Key import Key +import time +from collections import OrderedDict + +def test_generation_perf(n = 100): + results = OrderedDict() + for bits in (192, 224, 256, 384, 521): + t = time.time() + for i in xrange(n): + k = Key.generate(bits) + t = time.time() - t + results[bits] = t + return results + +def test_signing_perf(n = 100): + results = OrderedDict() + for bits in (192, 224, 256, 384, 521): + k = Key.generate(bits) + t = time.time() + for i in xrange(n): + k.sign("random string") + t = time.time() - t + results[bits] = t + return results + +def test_verification_perf(n = 100): + results = OrderedDict() + for bits in (192, 224, 256, 384, 521): + k = Key.generate(bits) + s = k.sign("random string") + t = time.time() + for i in xrange(n): + k.verify("random string", s) + t = time.time() - t + results[bits] = t + return results + +def print_dict(title, d): + print title + print '-' * len(title) + for k, v in d.items(): + print k, '\t', v + print + +n = 100 +print_dict("Key generation", test_generation_perf(n)) +print_dict("Signing", test_signing_perf(n)) +print_dict("Verifying", test_verification_perf(n)) + + diff --git a/python/PyECC/ecc/primes.py b/python/PyECC/ecc/primes.py new file mode 100644 index 000000000..a8bc1424b --- /dev/null +++ b/python/PyECC/ecc/primes.py @@ -0,0 +1,82 @@ +''' +This module implements simple prime generation and primality testing. +''' + +from random import SystemRandom +random = SystemRandom() +from os import urandom + +def exp(x, n, m): + '''Efficiently compute x ** n mod m''' + y = 1 + z = x + while n > 0: + if n & 1: + y = (y * z) % m + z = (z * z) % m + n //= 2 + return y + + +# Miller-Rabin-Test + +def prime(n, k): + '''Checks whether n is probably prime (with probability 1 - 4**(-k)''' + + if n % 2 == 0: + return False + + d = n - 1 + s = 0 + + while d % 2 == 0: + s += 1 + d /= 2 + + for i in xrange(k): + + a = long(2 + random.randint(0, n - 4)) + x = exp(a, d, n) + if (x == 1) or (x == n - 1): + continue + + for r in xrange(1, s): + x = (x * x) % n + + if x == 1: + return False + + if x == n - 1: + break + + else: + return False + return True + + +# Generate and Test Algorithms + +def get_prime(size, accuracy): + '''Generate a pseudorandom prime number with the specified size (bytes).''' + + while 1: + + # read some random data from the operating system + rstr = urandom(size - 1) + r = 128 | ord(urandom(1)) # MSB = 1 (not less than size) + for c in rstr: + r = (r << 8) | ord(c) + r |= 1 # LSB = 1 (odd) + + # test whether this results in a prime number + if prime(r, accuracy): + return r + + +def get_prime_upto(n, accuracy): + '''Find largest prime less than n''' + n |= 1 + while n > 0: + n -= 2 + if prime(n, accuracy): + return n diff --git a/python/PyECC/ecc/shacrypt.py b/python/PyECC/ecc/shacrypt.py new file mode 100644 index 000000000..69ee7b943 --- /dev/null +++ b/python/PyECC/ecc/shacrypt.py @@ -0,0 +1,38 @@ +# ------------------------------------------------------------------------------ +# +# SHA-512-BASED FEISTEL CIPHER +# by Toni Mattis +# +# Feistel Function: SHA-512(Block || Key) +# Key Size: Fully Dynamic +# Block Size: 1024 Bits +# Rounds: User-Specified +# +# ------------------------------------------------------------------------------ + +from hashlib import sha512 + +BPOS = tuple(range(64)) + +def enc_block(block, key, rounds = 16): + x = block[:64] + y = block[64:] + for i in xrange(rounds): + h = sha512(x + key).digest() + y = ''.join([chr(ord(y[k]) ^ ord(h[k])) for k in BPOS]) + h = sha512(y + key).digest() + x = ''.join([chr(ord(x[k]) ^ ord(h[k])) for k in BPOS]) + return x + y + +def dec_block(block, key, rounds = 16): + x = block[:64] + y = block[64:] + for i in xrange(rounds): + h = sha512(y + key).digest() + x = ''.join([chr(ord(x[k]) ^ ord(h[k])) for k in BPOS]) + h = sha512(x + key).digest() + y = ''.join([chr(ord(y[k]) ^ ord(h[k])) for k in BPOS]) + return x + y + + + diff --git a/python/PyECC/setup.py b/python/PyECC/setup.py new file mode 100644 index 000000000..b9e507c18 --- /dev/null +++ b/python/PyECC/setup.py @@ -0,0 +1,77 @@ +#!/usr/bin/python2.4 +# +# Copyright 2007 The Python-Twitter Developers +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. +# +# copied from https://github.com/bear/python-twitter/blob/master/setup.py +# + +'''The setup and build script for the python-twitter library.''' + +__author__ = 'niccokunzmann@aol.com' +__version__ = '0.0.1' + + +# The base package metadata to be used by both distutils and setuptools +METADATA = dict( + name = "ecc", + version = __version__, + packages = ['ecc'], + author='Toni Mattis', + author_email='solaris@live.de', + description='Pure Python implementation of an elliptic curve cryptosystem based on FIPS 186-3', + license='MIT', + url='https://github.com/niccokunzmann/ecc', + keywords='elliptic curve cryptosystem rabbit cipher', +) + +# Extra package metadata to be used only if setuptools is installed +SETUPTOOLS_METADATA = dict( + install_requires = [], + include_package_data = True, + classifiers = [ + 'Development Status :: 4 - Beta', + 'Intended Audience :: Developers', + 'License :: OSI Approved :: MIT License', + 'Topic :: Software Development :: Libraries :: Python Modules', + 'Topic :: Communications', + 'Topic :: Security :: Cryptography', + 'Topic :: Internet', + ], +## test_suite = 'distacc_test', +) + + +def Read(file): + return open(file).read() + +def BuildLongDescription(): + return '\n'.join([Read('README.md'), ]) + +def Main(): + # Build the long_description from the README and CHANGES + METADATA['long_description'] = BuildLongDescription() + + # Use setuptools if available, otherwise fallback and use distutils + try: + import setuptools + METADATA.update(SETUPTOOLS_METADATA) + setuptools.setup(**METADATA) + except ImportError: + import distutils.core + distutils.core.setup(**METADATA) + + +if __name__ == '__main__': + Main() -- cgit v1.2.3