bug 1190603 - import PyECC library r=gps,gerv
authorDavid Keeler <dkeeler@mozilla.com>
Mon, 03 Aug 2015 15:17:00 -0700
changeset 258047 ece1a3c3f06f4661b772b447fc0adadb2a9c30b7
parent 258046 87623e7c8a541e6e4ce297c5a268b97db5e8dbe8
child 258048 6360708999c9e42e77bae241f5a65b0784b30d55
push id29241
push userkwierso@gmail.com
push dateTue, 18 Aug 2015 00:00:46 +0000
treeherdermozilla-central@6ae3e9ff53b2 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersgps, gerv
bugs1190603
milestone43.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
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()