Elliptic Curve Integrated Encryption Scheme (ECIES) with AES

Theory

In this method Alice generates a random private key (\(d_A\)) and the takes a point on an elliptic curve (\(G\)) and then determines her public key (\(Q_A\)):

\(Q_A = d_A \times G\)

G and \(Q_A\) are thus points on an elliptic curve. Alice then sends \(Q_A\) to Bob. Next Bob will generate:

\(R = r \times G\)

\(S = r \times Q_A\)

and where r is a random number generated by Bob. The symmetric key (S) is then used to encrypt a message.

Alice will then receive the encrypted message along with \(R\). She is then able to determine the same encryption key with::

\(S = d_A \times R\)

which is:

\(S = d_A \times (r \times G)\)

\(S = r \times (d_A \times G)\)

\(S = r \times Q_A\)

and which is the same as the key that Bob generated.

The method is illustrated here:

Here is the code to generate this:

private, public = make_keypair()
print "Private key:", hex(private)
print("Public key: (0x{:x}, 0x{:x})".format(*public))

print "========================="

r = 123456

print public

R = scalar_mult(r,curve.g)
S = scalar_mult(r,public)

print "======Symmetric key========"

print "Encryption key:",S[0]

cipher=AESCipher(enc_long(S[0])).encrypt(message)
print "Encrypted:\t",binascii.hexlify(cipher)

text=AESCipher(enc_long(S[0])).decrypt(cipher)

print "Decrypted:\t",text

Sample run

A sample run is:

Private key: 0xc9f4f55bdeb5ba0bd337f2dbc952a5439e20ef9af6203d25d014e7102d86aaeeL
Public key: (0xc44370819cb3b7b57b2aa7edf550a9a5410c234d27aff497458bbbfec8b6a327, 0x52a1a3e222cd89cbd2764b69bd9b0ea5c4fd6ca28861e1f2140eeff9c2e76487)
=========================
(88772473565586973514902937985112496892381185018903565851282868575188339303207L, 37375247042524808816835324803014353920874001993630427922412845098560699982983L)
======Symmetric key========
Encryption key: 22561442351397855214022358574418722265071325216816484432705938053528680410600
Encrypted:	5273534b2f44726c58644137492b714b6f2b794f6b673d3d
Decrypted:	Hello

Coding

The code is based on [here]:

import collections
import hashlib
import random
import binascii
import sys
from hashlib import md5
from base64 import b64decode
from base64 import b64encode
from Crypto.Cipher import AES

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




# Padding for the input string --not
# related to encryption itself.
BLOCK_SIZE = 16  # Bytes
pad = lambda s: s + (BLOCK_SIZE - len(s) % BLOCK_SIZE) * \
                chr(BLOCK_SIZE - len(s) % BLOCK_SIZE)
unpad = lambda s: s[:-ord(s[len(s) - 1:])]


class AESCipher:
    """
    Usage:
        c = AESCipher('password').encrypt('message')
        m = AESCipher('password').decrypt(c)
    Tested under Python 3 and PyCrypto 2.6.1.
    """

    def __init__(self, key):
        self.key = key

    def encrypt(self, raw):
        raw = pad(raw)
        cipher = AES.new(self.key, AES.MODE_ECB)
        return b64encode(cipher.encrypt(raw))

    def decrypt(self, enc):
        enc = b64decode(enc)
        cipher = AES.new(self.key, AES.MODE_ECB)
        return unpad(cipher.decrypt(enc)).decode('utf8')


EllipticCurve = collections.namedtuple('EllipticCurve', 'name p a b g n h')

curve = EllipticCurve(
    'secp256k1',
    # Field characteristic.
    p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f,
    # Curve coefficients.
    a=0,
    b=7,
    # Base point.
    g=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,
       0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8),
    # Subgroup order.
    n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141,
    # Subgroup cofactor.
    h=1,
)


# Modular arithmetic ##########################################################

def inverse_mod(k, p):
    """Returns the inverse of k modulo p.
    This function returns the only integer x such that (x * k) % p == 1.
    k must be non-zero and p must be a prime.
    """
    if k == 0:
        raise ZeroDivisionError('division by zero')

    if k < 0:
        # k ** -1 = p - (-k) ** -1  (mod p)
        return p - inverse_mod(-k, p)

    # Extended Euclidean algorithm.
    s, old_s = 0, 1
    t, old_t = 1, 0
    r, old_r = p, k

    while r != 0:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        old_s, s = s, old_s - quotient * s
        old_t, t = t, old_t - quotient * t

    gcd, x, y = old_r, old_s, old_t

    assert gcd == 1
    assert (k * x) % p == 1

    return x % p


# Functions that work on curve points #########################################

def is_on_curve(point):
    """Returns True if the given point lies on the elliptic curve."""
    if point is None:
        # None represents the point at infinity.
        return True

    x, y = point

    return (y * y - x * x * x - curve.a * x - curve.b) % curve.p == 0


def point_neg(point):
    """Returns -point."""
    assert is_on_curve(point)

    if point is None:
        # -0 = 0
        return None

    x, y = point
    result = (x, -y % curve.p)

    assert is_on_curve(result)

    return result


def point_add(point1, point2):
    """Returns the result of point1 + point2 according to the group law."""
    assert is_on_curve(point1)
    assert is_on_curve(point2)

    if point1 is None:
        # 0 + point2 = point2
        return point2
    if point2 is None:
        # point1 + 0 = point1
        return point1

    x1, y1 = point1
    x2, y2 = point2

    if x1 == x2 and y1 != y2:
        # point1 + (-point1) = 0
        return None

    if x1 == x2:
        # This is the case point1 == point2.
        m = (3 * x1 * x1 + curve.a) * inverse_mod(2 * y1, curve.p)
    else:
        # This is the case point1 != point2.
        m = (y1 - y2) * inverse_mod(x1 - x2, curve.p)

    x3 = m * m - x1 - x2
    y3 = y1 + m * (x3 - x1)
    result = (x3 % curve.p,
              -y3 % curve.p)

    assert is_on_curve(result)

    return result


def scalar_mult(k, point):
    """Returns k * point computed using the double and point_add algorithm."""
    assert is_on_curve(point)

    if k % curve.n == 0 or point is None:
        return None

    if k < 0:
        # k * point = -k * (-point)
        return scalar_mult(-k, point_neg(point))

    result = None
    addend = point

    while k:
        if k & 1:
            # Add.
            result = point_add(result, addend)

        # Double.
        addend = point_add(addend, addend)

        k >>= 1

    assert is_on_curve(result)

    return result


# Keypair generation and ECDSA ################################################

def make_keypair():
    """Generates a random private-public key pair."""
    private_key = random.randrange(1, curve.n)
    public_key = scalar_mult(private_key, curve.g)

    return private_key, public_key


def verify_signature(public_key, message, signature):
    z = hash_message(message)

    r, s = signature

    w = inverse_mod(s, curve.n)
    u1 = (z * w) % curve.n
    u2 = (r * w) % curve.n

    x, y = point_add(scalar_mult(u1, curve.g),
                     scalar_mult(u2, public_key))

    if (r % curve.n) == (x % curve.n):
        return 'signature matches'
    else:
        return 'invalid signature'


message="Hello"
if (len(sys.argv)>1):
	message=str(sys.argv[1])


private, public = make_keypair()
print "Private key:", hex(private)
print("Public key: (0x{:x}, 0x{:x})".format(*public))


print "========================="

r = 123456

print public

R = scalar_mult(r,curve.g)
S = scalar_mult(r,public)

print "======Symmetric key========"

print "Encryption key:",S[0]

cipher=AESCipher(enc_long(S[0])).encrypt(message)
print "Encrypted:\t",binascii.hexlify(cipher)

text=AESCipher(enc_long(S[0])).decrypt(cipher)

print "Decrypted:\t",text

Presentation