ECDHSS: A Two-Party Key Generation Scheme Combining Elliptic Curve Diffie–Hellman and Shamir’s Secret Sharing

2.1 Elliptic Curve Diffie–Hellman

ECDH is a key agreement protocol that allows two parties, each having an elliptic-curve public–private key pair, to establish a shared secret over an insecure channel. This shared secret may be directly used as a key or to derive another key. The key, or the derived key, can then be used to encrypt subsequent communications using a symmetric-key cipher [9].

Diffie–Hellman (DH) is one of the first public key protocols invented by Whitfield Diffie and Martin Hellman, DH is mathematical method that generates a shared encryption key between two parties over a public channel [10].

DH key exchange protocols are accomplished by the following routine:

Alice and Bob publicly agree on using a large prime number (p) and a base value (g).

Alice and Bob separately choose a secret value (a the secret value of Alice, and b the secret value of Bob) and exchange the result of the following equation with each other (A= ga mod p, B=gb mod p).

Alice computes s (s=Ba mod p), and Bob also compute s (s= Ab mod p), where s is considered the shared key.

Elliptic Curves (EC) represent a fundamental mathematical construct with major impact on modern cryptographic systems. These curves are defined over finite fields using the following equation (${{y}^{2}}\equiv {{x}^{3}}+ax+b~mod~p$) where a, b are constants defining the curve and p is a prime number that defines the finite field, elliptic curves have unique algebraic properties that make them particularly suitable for secure key exchange protocols. The geometric interpretation of elliptic curves allows for the definition of a specialized addition operation, where combining two points on the curve produces another point belonging to that curve. This operation, combined with the existence of an identity element known as the point at infinity, forms the basis of an Abelian group structure that underlies their cryptographic applications [11].

The cryptographic strength of elliptic curves came from the complexity of mathematical problems defined over the structure of the curve. The elliptic curve discrete logarithm problem presents difficult computational challenges that make the key exchange mechanisms secure enough, and this is why protocols like the ECDH key agreement are secure. ECDH leverages scalar multiplication operations on the curve, where private keys are used to generate corresponding public keys through repeated point addition, and shared secrets are derived through carefully constructed combinations of these elements.

2.2 Shamir’s Secret Sharing

Secret sharing is a cryptographic technique that takes a secret and breaks it up into multiple shares, and distributes these shares among multiple parties or locations. The secret can only be reconstructed when enough shares are combined in a mathematical process [12-14].

Sensitive data are often protected, and their security is improved by employing this method in combination with other methods. There are many useful applications of secret sharing, such as Key management, Data recovery, Password recovery, Access control, and Secure transactions [14]. Figure 1 shows the schema of secret sharing.

Figure 1. Secret sharing schema [15]

Secret Sharing is done over finite field arithmetic, particularly over a prime field GF(p) or Galois fields GF(2^m) to keep the shares within the field range. Through calculations in GF(p), SSS guarantees that all operations are feasible and consistent with the desired mathematical range.

SSS over GF(2^m) can be used to enable binary field operations, making them appropriate for digital systems that favor binary data representation. Utilizing the characteristics of Galois fields, SSS can be optimized for effective operation with digital data, providing adaptability in security applications across various hardware platforms.

To generate shares using SSS, the following requirements are needed:

1. The secret (S).
2. The number of shares to generate (n).
3. Threshold, the minimum number of shares to reconstruct the secret (k) where k < n.
4. A large prime number GF(p).
5. Random coefficients (a_i) where i equal to k-1.

Shares are generated using the following equation:

$f\left( x \right)=S+{{a}_{1}}x+{{a}_{2}}{{x}^{2}}+\ldots ++{{a}_{k-1}}{{x}^{k-1}}mod~GF\left( p \right)$

where f(0) = S and each share consist of (xi, f(xi)).

To reconstruct the secret, the following information needs to be prepared:

1. At least k Shares.
2. A large prime number GF(p) that has been used in secret generating process.

Secret is reconstructed using the following equation:

$S=f\left( 0 \right)=~\underset{i=0}{\overset{k-1}{\mathop \sum }}\,{{y}_{i}}{{l}_{i}}\left( x \right)$

where, l_i$~$is found using the following equation:

${{l}_{i}}=\frac{x-{{x}_{0}}}{{{x}_{i}}-{{x}_{0}}}\times \ldots \times \frac{x-{{x}_{k-1}}}{{{x}_{i}}-{{x}_{k-1}}}$

To evaluate the strength of the shares in terms of key strength and randomness, the following tests have been used:

1. Entropy Test (Shannon Entropy) [16] Measures the unpredictability of the key by calculating how random it is, Shannon Entropy quantifies the uncertainty or randomness in a sequence of values. The higher the entropy, the less predictable the sequence is. Ideal randomness is achieved when entropy is equal to 1.0 (for a balanced binary string).
2. Key Uniformity (Chi-Square Test) [17] Verifies that the shares do not have biased distributions of 0s and 1 s, The Chi-square test compares the observed frequency distribution of bits with the expected distribution in a uniform random sequence (50% 0 s and 50% 1 s). For the Chi-square test, the critical value is 6.63, meaning that the sequence passes the test if Chi-Square value is less than 6.63.
3. Collision Resistance (Hamming Distance) [18] Measures how different two keys are when one bit is altered, A key with high collision resistance should have large differences when slightly changed. The Hamming distance between two keys should be close to 50% for an ideal cryptographic key.
4. NIST Statistical Test Suite (SP800-22) [19] is a collection of statistical tests designed to evaluate the randomness of binary sequences, the tests analyze various patterns and deviations from true randomness, these tests include commonly applied NIST SP800-22 tests such as Frequency (Monobit), Block Frequency, Runs, Longest Run of Ones, Discrete Fourier Transform, Template Matching, Serial, Approximate Entropy, and Cumulative Sums tests. A test is considered successful (Pass) if the p-value ≥ 0.01 (for a significance level of α = 1%). Some tests have additional criteria (e.g., proportion of sequence passing, uniformity of p-values). Table 2 gives the tests results for the generated 20 keys, while Table 3 gives the NIST STS test results over 100 generated values, the same ECDH shared secret was used with HMAC-based Extract-and-Expand Key Derivation Function (HKDF) [20] to generate 100 keys to compare with the proposed scheme generated keys.

The evaluation was conducted on sequences generated using the proposed scheme, where 100 consecutive keys were produced and concatenated to form input sequences suitable for statistical testing. The NIST SP800-22 tests were applied using standard configurations, and all p-values were obtained based on the recommended significance level (α = 0.01).

The generated keys present strong statistical randomness properties, indicating their suitability as statistically strong cryptographic keys. The Shannon Entropy values in Table 2 for the 20 samples used are close to 1, where 1 is the ideal balance between binary states. The Chi-square test results remain below the critical threshold (6.63), confirming the absence of statistical bias in the distribution of the bits.

Table 2. Evaluation results of the generated keys

The Hamming distance between generated keys is approximately 50% of the key length, indicating a high level of independence between keys and strong resistance to correlation-based attacks. This ensures that when applying a small variation in the input, this will lead to an output that is differ by a high variation, which is desirable in secure key generation schemes.

NIST SP800-22 statistical tests results in Table 3, which were done over 100 keys, also validate the randomness of the generated sequences. Most tests achieved high test-pass rates with p-values exceeding the required threshold (0.01), indicating no significant deviation from ideal randomness. Although slight variations appear in certain tests, such as the Non-overlapping Template test, the overall performance remains within acceptable limits and does not indicate weaknesses in the structure of the proposed scheme.

Table 3. NIST Statistical Test for 100 consecutive generated keys