bug 1190603 - import PyECC library r=gps,gerv
authorDavid Keeler <dkeeler@mozilla.com>
Mon, 03 Aug 2015 15:17:00 -0700
changeset 258053 ece1a3c3f06f4661b772b447fc0adadb2a9c30b7
parent 258052 87623e7c8a541e6e4ce297c5a268b97db5e8dbe8
child 258054 6360708999c9e42e77bae241f5a65b0784b30d55
push idunknown
push userunknown
push dateunknown
reviewersgps, gerv
bugs1190603
milestone43.0a1
bug 1190603 - import PyECC library r=gps,gerv Obtained from https://github.com/amintos/PyECC.git (commit 1bfd3a41410c3650e57d58f7bd016bb0819af250)
build/virtualenv_packages.txt
python/PyECC/MANIFEST.in
python/PyECC/README.md
python/PyECC/ecc/Key.py
python/PyECC/ecc/Rabbit.py
python/PyECC/ecc/SecurityViolationException.py
python/PyECC/ecc/__init__.py
python/PyECC/ecc/curves.py
python/PyECC/ecc/eccrypt.py
python/PyECC/ecc/ecdsa.py
python/PyECC/ecc/elliptic.py
python/PyECC/ecc/encoding.py
python/PyECC/ecc/performance.py
python/PyECC/ecc/primes.py
python/PyECC/ecc/shacrypt.py
python/PyECC/setup.py
--- a/build/virtualenv_packages.txt
+++ b/build/virtualenv_packages.txt
@@ -26,8 +26,9 @@ objdir:build
 gyp.pth:media/webrtc/trunk/tools/gyp/pylib
 pyasn1.pth:python/pyasn1
 pyasn1_modules.pth:python/pyasn1-modules
 bitstring.pth:python/bitstring
 redo.pth:python/redo
 requests.pth:python/requests
 rsa.pth:python/rsa
 futures.pth:python/futures
+ecc.pth:python/PyECC
new file mode 100644
--- /dev/null
+++ b/python/PyECC/MANIFEST.in
@@ -0,0 +1,1 @@
+include README.md
new file mode 100644
--- /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.
new file mode 100644
--- /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
+
+                
+                
+    
new file mode 100644
--- /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
new file mode 100644
--- /dev/null
+++ b/python/PyECC/ecc/SecurityViolationException.py
@@ -0,0 +1,2 @@
+class SecurityViolationException(Exception):
+    pass
new file mode 100644
new file mode 100644
--- /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]]
new file mode 100644
--- /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)
+    
+    
new file mode 100644
--- /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
+
+    
new file mode 100644
--- /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
+        
+
+        
new file mode 100644
--- /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)"
new file mode 100644
--- /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))
+
+        
new file mode 100644
--- /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
new file mode 100644
--- /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
+
+
+    
new file mode 100644
--- /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()