A threshold scheme allows us to create a number of secret and then define a threshold number of the shares to come back together again. If we have n shares we can define that t shares need to come back together to reconstruct the original data. The following implements Elliptic Curve Cryptography to split and recover the shares [Shamir secret shares]:
Threshold scheme with ECC |
Details
What we want is for Bob and Alice to generate a key pair (either for the session or long-term keys). They will then pass their public keys to each other, and at the end will have a shared key. This key is then used to secure each of the shares:
The starting point of the method is for Bob and Alice to agree on a shared key. For this Alice will create a private key (\(a\)) and Bob will create his private key (\(b\)). Each of them will then generate their public key with \(aG \pmod p \) and \(bG \pmod p\), and exchange these values:
Next Alice will split a secret message (\(m\)) into a number of secret shares (\(n\)) and which have a threshold of \(t\). She then converts each of the shares into points on the elliptic curve with \(P_i=m_i+a b G\):
These points can then be passed to Bob. He will take \(t\) points and then compute \(m_i = P_i - a b G\):
An application of this is to split up the shares and then distribute them over different cloud systems, and then reconstruct from \(t\) shares. In this way we get both security and resilience, and one cloud could fail, and we would still be able to reconstruct the data:
Coding
First we create a random number (\(s_{key}\)). Next we create generate the public key (\(p_{key}\) using the generator point (\(G\)) as:
\(p_{key} = s_{key} \times G \pmod O\)
and where \(O\) is the order of the elliptic curve. As we use a Sepc256k1 curve (\(y^2 = x^3+7\)) the parameters are:
O = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
G = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8
We then split up the secret key for \(n\) shares and with a threshold of \(t\):
coef = [secret] + [randrange(SECP256k1.order) for i in range(1, t)] f = lambda x: sum([ coef[i] * pow(x, i) for i in range(t)]) % O secret_share = list(map(f, list(range(1, n + 1)))) F = [ coef[j] * G for j in range(t) ]
The output is then \(secret_{share}\) and which contains the secret, and F which contains a list of the public parameters used to generate the secret share.
A sample run for a threshold of 2 and with 4 shares is:
=================================== Elliptic curve: SECP256k1 Parameters G_x= 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798L G_y= 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8L Order: 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141L =================================== =================================== t: 2 n: 4 =================================== =================================== Original key 0x1b39b5771afbe1a01928e87c957a55a9681586f836593b7ad63f5cf5cbc85576L =================================== =================================== Share 0x3defd23c1ec75f353d9917e9c12f78270ae74f589ad00e030935c0f4f2cbaa6L Verfied: True Share 0xec8444d068dd0a468e8a3a80a2ab995a33f63fd98c4966814ab9b9b5a2c76117L Verfied: True Share 0xd5298c7d0fcd9e99c93ae382a9443b333c8f2dd6df9d2be6a50db8cf262bc647L Verfied: True Share 0xbdced429b6be32ed03eb8c84afdcdd0c45281bd432f0f14bff61b7e8a9902b77L Verfied: True =================================== Reconstructed key: 0x1b39b5771afbe1a01928e87c957a55a9681586f836593b7ad63f5cf5cbc85576L =================================== Original message: 5555 Reconstructed message: 5555.0
Sample code
Some from code from [here] is:
# https://asecuritysite.com/encryption/ecc_thres # Based on https://github.com/fernandolobato/ecc_verifiable_threshold_cryptosystem/blob/master/threshold.py import sys from ecdsa.util import randrange from ecdsa.curves import SECP256k1 from ecdsa.ellipticcurve import Point from ecdsa.ecdsa import curve_secp256k1 from ecdsa.numbertheory import inverse_mod def secret_split(secret, t, n, G=SECP256k1.generator, O=SECP256k1.order): """ Splits a secret into n shares out which t can reconstruct the key. PARAMS ------ secret: (int) Secret to be split. t: (int) Size of the sub set that should be able to reconstruct key. n: (int) Number of shares into which the secret is split. G: (ecdsa.ellipticcurve.Point) Base point for the elliptic curve. O: (int) Order of elliptic curve RETURNS ------- secret_share: (list) A list containing the splits of the secret. F: (list) list of public parameters used to generate secret_share. coeficients used multiplied by the EC generator to make them public. """ assert(n >= t) coef = [secret] + [randrange(SECP256k1.order) for i in range(1, t)] f = lambda x: sum([ coef[i] * pow(x, i) for i in range(t)]) % O secret_share = list(map(f, list(range(1, n + 1)))) F = [ coef[j] * G for j in range(t) ] return (secret_share, F) def verify_secret_share(secret_share, i, F, G=SECP256k1.generator): """ Verifies that a specific share of a set of secret shares is valid against a list of public parameters used to generate it. PARAMS ------ secret_share: (int) specific share to be verified. i: (int) index of the secrete instance in the share F: (list) set of public parameters with which the share was generated. G: (ecdsa.ellipticcurve.Point) Base point for the elliptic curve. RETURNS ------- boolean value indicating if specific share is valid. """ verify = F[0] for j in range(1, len(F)): verify += pow(i+1, j) * F[j] return verify == secret_share * G def reconstruct_key(sub_secret_share, t, O=SECP256k1.order): """ Reconstructs a secret from a share of sub secrets. Requires a subset of size t. The sub secret share is the split of the original split. PARAMS ------ sub_secret_share: (int) sub set of secrets that can reconstruct secret. t: (int) size of sub set that can reconstruct secret. G: (ecdsa.ellipticcurve.Point) Base point for the elliptic curve. RETURNS ------- reconstructed key. """ assert(len(sub_secret_share) >= t) recon_key = 0 for j in range(1, t + 1): mult = 1 for h in range(1, t + 1): if h != j: mult *= ( h / (h - j)) recon_key += (sub_secret_share[j - 1] * int(mult)) % O return recon_key % O def encrypt(pub_key, message, G=SECP256k1.generator, O=SECP256k1.order): """ Encrypts a message with an ECC threshold public key. Standard ECC encryption. PARAMS ------ pub_key: (ecdsa.ellipticcurve.Point) public key with which to encrypt message. message: (int) message to be encrypted. G: (ecdsa.ellipticcurve.Point) Base point for the elliptic curve. O: (int) Order of elliptic curve RETURNS ------- (P, c) touple with encrypted message. """ k = randrange(O) P = k * G H = k * pub_key c = message * H.y() % O return (P, c) def decrypt(sec_key, cipher, O=SECP256k1.order): """ Descrypts a ciphertext encrypted with the corresponding public key to the private key being provided. PARAMS ------ sec_key: (int) secret key corresponding to the public key used to encrypt message. cipher: (ecdsa.ellipticcurve.Point, int) encrypted message. RETURNS ------- message: (int) original message. """ (P, c) = cipher H = sec_key * P message = c * inverse_mod(H.y(), O) % O return round(message) def generate_key(order=SECP256k1.order): """ Generates a private key for use with ECC. Basically a random number generator with mod order. PARAMS ------ order: (int) the order of the curve. RETURNS ------- (int) private key. """ return randrange(order) def generate_threshold_parameters(t, n): """ Generates the required parameters for a threshold cryptosystem. PARAMS ------ t: size of subset that can reconstruct private key. n: number of splits for private key. RETURNS ------- s_key: (int) private key. p_key: (int) public key corresponding to private key. s: (list) list of shares that can reconstruct private key. F: (list) public parameters that were used to generate share of secrets. """ s_key = generate_key() p_key = s_key * SECP256k1.generator (s, F) = secret_split(s_key, t, n) return (s_key, p_key, s, F) t=2 n=5 m=5555 (s_key, p_key, s, F) = generate_threshold_parameters(t, n) print("Original key",s_key) print() for i in range(n): print(s[i], end=' ') print("Verfied:",verify_secret_share(s[i], i, F)) r_key = reconstruct_key(s, t) print("\nReconstructed key:",r_key) cipher = encrypt(p_key, m) _message = decrypt(r_key, cipher) print (_message)
Presentation
The following is an outline presentation on the method [slides]: