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 Rabbit (and which is a light-weight stream encryption method:
Elliptic Curve Integrated Encryption Scheme (ECIES) with Rabbit |
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) r = 123456 print public R = scalar_mult(r,curve.g) S = scalar_mult(r,public) print "Encryption key:",S[0] msg=Rabbit(enc_long(S[0])).encrypt(message) print "Encrypted:\t",binascii.hexlify(msg) text=Rabbit(enc_long(S[0])).decrypt(msg) print "Decrypted:\t",text
Sample run
A sample run is:
('Private key:', '0x7a504ce309427cf39013e0d7505ab997d28c6f011cf2557b9c85542df25110aL') Public key: (0x7fc09de319e43697778297255904eba692792eaf7af2229a37b35ab30a111bcd, 0xaf62370b2529b4d39be585229bb13d3bc250f66ac70a9f7da1c78db628e67e37) ========================= (57784056103323309453310392137562918816296897796403596046191771130480433372109L, 79328279410942098239884401491423137948592842599756290040805436956713064758839L) ======Symmetric key======== Encryption key: 80713038787559702650537445941094042144451128383246997006058901402979379214338 Encrypted: 31d9b20358 Decrypted: Hello
Coding
The code is based on [here]:
# https://asecuritysite.com/encryption/ecc2 import collections import hashlib import random import rabbit import binascii import sys 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 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 range(14, -1, -2)] else: # k[0] = least significant 16 bits # k[7] = most significant 16 bits k = [(key >> i) & 0xFFFF for i in range(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 range(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 range(8)] self.x = x self.c = c self.b = 0 self._buf = 0 # output buffer self._buf_bytes = 0 # fill level of buffer next(self) next(self) next(self) next(self) for j in range(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 next(self) next(self) next(self) next(self) 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 range(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 range(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 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]) print(('Curve:', curve.name)) private, public = make_keypair() print(("Private key:", hex(private))) print(("Public key: (0x{:x}, 0x{:x})".format(*public))) r = 123456 print(public) R = scalar_mult(r,curve.g) S = scalar_mult(r,public) print("Encryption key:",S[0]) msg=Rabbit(enc_long(S[0])).encrypt(message) print("Encrypted:\t",binascii.hexlify(msg.encode())) text=Rabbit(enc_long(S[0])).decrypt(msg) print("Decrypted:\t",text)