summaryrefslogtreecommitdiffstats
path: root/python/PyECC
diff options
context:
space:
mode:
Diffstat (limited to 'python/PyECC')
-rw-r--r--python/PyECC/MANIFEST.in1
-rw-r--r--python/PyECC/README.md29
-rw-r--r--python/PyECC/ecc/Key.py320
-rw-r--r--python/PyECC/ecc/Rabbit.py270
-rw-r--r--python/PyECC/ecc/SecurityViolationException.py2
-rw-r--r--python/PyECC/ecc/__init__.py0
-rw-r--r--python/PyECC/ecc/curves.py81
-rw-r--r--python/PyECC/ecc/eccrypt.py65
-rw-r--r--python/PyECC/ecc/ecdsa.py153
-rw-r--r--python/PyECC/ecc/elliptic.py381
-rw-r--r--python/PyECC/ecc/encoding.py178
-rw-r--r--python/PyECC/ecc/performance.py50
-rw-r--r--python/PyECC/ecc/primes.py82
-rw-r--r--python/PyECC/ecc/shacrypt.py38
-rw-r--r--python/PyECC/setup.py77
15 files changed, 1727 insertions, 0 deletions
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(<encoded key>) 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(<encoded key>) 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
--- /dev/null
+++ b/python/PyECC/ecc/__init__.py
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 <solaris@live.de>
+#
+
+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 <solaris@live.de>
+#
+
+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 <solaris@live.de>
+# ------------------------------------------------------------------------------
+
+'''
+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 <Z/nZ*; +>
+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()
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-11 19:17:12 +0000