With ECIES we use the public key from Elliptic Curve Cryptography in order to derive a symmetric key. In this case we create a symmetric key from Elliptic Curve Cryptography, and then use this to encrypt with 256-bit AES in ECB mode:
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:
dA, Qa = make_keypair() print "Private key:", hex(dA) print("Public key: (0x{:x}, 0x{:x})".format(*Qa)) print "=========================" r = random.randint(0, 2**128) print "Public key: ",Qa rG = scalar_mult(r,curve.g) S = scalar_mult(r,Qa) print "======Symmetric key========" print "Encryption key:",S[0] cipher=AESCipher(enc_long(S[0])).encrypt(message) print "Encrypted:\t",binascii.hexlify(cipher) Snew = scalar_mult(dA,rG) text=AESCipher(enc_long(Snew[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 Crypto.Cipher import AES import Padding 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:])] def encrypt(plaintext,key, mode): encobj = AES.new(key,mode) return(encobj.encrypt(plaintext)) def decrypt(ciphertext,key, mode): encobj = AES.new(key,mode) return(encobj.decrypt(ciphertext)) 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]) dA, Qa = make_keypair() print("Private key:", hex(dA)) print(("Public key: (0x{:x}, 0x{:x})".format(*Qa))) print("\n\n=========================") r = random.randint(0, 2**128) rG = scalar_mult(r,curve.g) S = scalar_mult(r,Qa) print("Random value: " , r) print("rG: " , rG) print("\n\n======Symmetric key========") print("Encryption key:",S[0],str(S[0])) password='hello' key = hashlib.sha256(str(S[0]).encode()).digest() message = Padding.appendPadding(message,blocksize=Padding.AES_blocksize,mode=0) ciphertext = encrypt(message.encode(),key,AES.MODE_ECB) print("Encrypted:\t",binascii.hexlify(ciphertext)) Snew = scalar_mult(dA,rG) key = hashlib.sha256(str(Snew[0]).encode()).digest() text = decrypt(ciphertext,key,AES.MODE_ECB) print("Decrypted:\t",Padding.removePadding(text.decode(),mode=0))