The strength of Elliptic curve cryptography (ECC) relies on curve choice. This work analyzes weak keys in standardized curves, i.e., private keys within small subgroups of the auxiliary group Z*. We quantify weak key prevalence across standardized curves, revealing a potential vulnerability due to numerous small divisors in auxiliary group orders. To address this, we leverage the implicit baby-steps giant-steps algorithm, which transforms the complex elliptic curve discrete logarithm problem into a simpler problem within Z*. This enables eficient detection of weak keys in small-order subgroups. Our findings highlight the importance of rigorous key testing in applications using standardized ECC. While random weak keys are unlikely, malicious actors could exploit this by manipulating key generation libraries. To this end, we show how users can assess their private key vulnerabilities and mitigate risks by eliminating weak keys. Hence, this work contributes to improved ECC security through proactive key management practices.
keys, thus proactively strengthen their cryptographic security by identifying potential weak keys.
Overall, this paper contributes to the field of ECC security by ofering a comprehensive analysis of weak keys in standardized curves, introducing an eficient detection method using the iBSGS algorithm, and highlighting the importance of proactive key testing.
The rest of the paper is organized as follows. In Section 2 we recall basic definitions about elliptic curves, the discrete logarithm problem, and the baby-step giant-step algorithm. The implicit version of this algorithm, dubbed iBSGS, is presented in Section 3. Section 4 covers the main contribution of this paper: first, we show how to apply the iBSGS algorithm for testing whether a key is weak; then, we analyse elliptic curves actually used in practice, providing an estimation of the weak keys which can be found within a given bound. Conclusions and directions for future work are in Section 5.
In this section, we lay the groundwork for our analysis by revisiting some fundamental concepts. We ifrst recall elliptic curves; next, we describe the discrete logarithm problem in additive groups, such as those arising from elliptic curves. Finally, we recall the baby-step giant-step algorithm, a powerful tool for solving the DLP.
An elliptic curve (EC) over a field K, denoted /K, is given by the Weierstraß equation : 2 + 1 + 3 = 3 + 22 + 4 + 6 (1) where the coeficients 1, 2, 3, 4, 6 ∈ K are such that for each point (1, 1) ∈ K2 satisfying Equation (1), the partial derivatives do not vanish simultaneously.
We refer to points on the curve as points with coordinates in K satisfying Equation (1). Points on with coordinates in the base field K form the set of K-rational points of E; we denote this set by (K) = {︀ (1, 1) ∈ K2 : 12 + 11 + 31 = 13 + 212 + 41 + 6}︀
It is well-known that this set can be turned into an additive group ((K), ⊕ , ) where the group law
is given by the chord-tangent operation ⊕ and the identity is given by the point at infinite [
In this work we focus exclusively on elliptic curves defined over finite fields of characteristic diferent from 2 and 3 so we can assume that the EC is given by a short Weierstraß equation: : 2 = 3 + 4 + 6 (2)
Moreover, we can assume the elliptic curve group (K) to be of order where is a prime. This is done for cryptographic purposes, since it increase the complexity of the Discrete Logarithm Problem.
Let (, ⊕ ) be an additive cyclic group of prime order and a generator for . The map : Z → ↦→ [] = ⊕ ⊕ · · · ⊕ ⏟ tim⏞es has kernel Z, thus leads to an isomorphism between (, ⊕ ) and (Z/Z, +) := Z. The problem of computing the inverse map is called the discrete logarithm problem (DLP) to the base of . It is the problem, given and , to determine ∈ Z such that = [ ] . Note that is unique only modulo the group order.
The complexity of this problem depends on the choice of and its operation. If = Z with generator 1, the discrete logarithm of ∈ Z is itself. If we choose a generator ∈ Z, where ̸= 1, the problem is still easy to solve because it reduces to compute the inverse of modulo .
The baby-step giant-step algorithm (BSGS algorithm) was firstly published by Shanks to compute ideal
class numbers of quadratic number fields [
The BSGS method is based on the following: Lemma 1. Let be a positive integer. Put := ⌊√⌋ + 1. Then for any with 0 ≤ < there are integers , , with 0 ≤ , ≤ − 1, such that = + .
Proof. If we divide by we have = + with 0 ≤ ≤ − 1. We note that ≤ − 1 = 2 − 1 = ( − 1) + ( − 1) and we know that ≤ − 1. Hence we have 0 ≤ ≤ − 1.
Assume now that the order of ∈ is and an integer modulus . Let = [ ] , then we have ⊕ [− ] = [], for some , as in Lemma 1. We have the following: Proposition 1. Let (, ⊕ ) be a finite, additive, cyclic group of order and let be a generator of . The following algorithm solves the discrete logarithm problem [ ] = in ( log ) steps, where is define as follows.
1. Let := ⌊√⌋ + 1.
2. Create the two lists:
baby-steps: , [
Proof. To compute the two lists we take at most 2 group operations. By Lemma 1, there exists a match between the two lists, that can be found in log √ steps by using standard searching algorithms or hash tables. Hence, the total running time for the algorithm is ( log ) steps.
In this section we describe an implicit version of the BSGS algorithm [
Assume (, ⊕ ) to be a finite, additive, cyclic group of prime order and let be a generator. We define the following (faithful) group action: : Z* →−
Aut() →↦− : →− →↦− [ ] It is easy to see that is a group homomorphism with kernel
ker = { ∈ Z* : ( ) = } = {1}
If ∈ Aut() and is a generator for , then ( ) = [ ] for some ∈ Z*. Thus we have an isomorphism Z* ≃ Aut() and we can identify the element [ ] ∈ with ∈ Z*.
We want to solve the discrete logarithm problem in by using the auxiliary group Z*. Let be a primitive element of Z*, then = for some 0 ≤ < and = [] . Let := ⌊√⌋ + 1. If we divide by we get , with 0 ≤ , ≤ − 1 such that = + , as in Lemma 1. It follows that = [] = [+] = [][] , which leads to
[− ] = []
However, we know that = [ ] , thus we have [− ][ ] = [] and this implies − = mod . Hence, if we find such an and , we can compute = + and we have the solution of the discrete logarithm problem. We can now proceed as in Proposition 1.
We put := ⌊√⌋ + 1 and we build the two following lists: baby-steps: [], [2], . . . , [] giant-steps: [− ], [− 2], . . . , [− 2 ]
Using binary search, we find a match that solves the DLP in time ( log ). The algorithm described above is what we call implicit baby-step giant-step (iBSGS).
If a divisor of − 1 is known, this idea can be improved. Let = − 1 be a generator for the √ order subgroup of Z*. We put ′ := ⌊ ⌋ + 1 and run the implicit baby-step giant-step by using instead of , that is, using the following lists: baby-steps: [], [2], . . . , [′ ] giant-steps: [− ′ ], [− 2′ ], . . . , [− ′2 ]
If the unknown lies in the -order subgroup of Z*, then will be equal to for some modulus and the algorithm will find a match [− ′ ] = [] . Hence, [− ′ ][ ] = [] , which lead to +′ and the DLP is solved in times (′ log ′). =
In this case we either find or verify that is not in the order subgroup after at most iterations. Thus, if is suficiently small and lies in the -order subgroup, the DLP can be solved much easily.
To summarize: Theorem 1. Let be an additive, cyclic group of prime order , with generator . Let = [ ] be another given element of (with unknown). For a given divisor of − 1, let be the subgroup of Z* of order . Then, one can decide whether belongs to in (√) steps. Moreover, if belongs to , the same algorithm will find the discrete logarithm in (√) steps.
In cryptographic applications using elliptic curve cryptosystems, the integer represent the , while the point = [ ] is the . Therefore, every public key for which the corresponding private key lies in a small subgroup of Z* is deemed to be weak.
This section tackles the vulnerability of weak keys in standardized elliptic curves. We begin by demonstrating how the iBSGS algorithm can eficiently test whether a key within a given curve belongs to a small-order subgroup of the auxiliary group Z*. Subsequently, we conduct a comprehensive analysis of standardized curves, enumerating weak keys residing in subgroups with orders below a specified threshold for each individual curve. Finally, we present a concise overview of our implementation of these algorithms in Rust and PARI/GP.
A simple approach to test whether the private key corresponding to a public key is weak is to set a bound for the order of the subgroups of Z*. We can run the iBSGS algorithm on all divisors of − 1 that are less than . However, this would be ineficient and redundant, because testing whether a key is in a subgroup of order also covers all subgroups of order divisible by . Thus, we instead generate a list of integers 1 < 2 < · · · < ≤ dividing − 1 such that ∤ for all 1 ≤ < ≤ .
As an example, let us consider the elliptic curve secp192r1 (P192) [
By using a computer algebra system (e.g., PARI/GP or SageMath [
Let us choose a public key as the point If we run the iBSGS algorithm, we find a match in a couple of seconds. This gives us the discrete logarithm in base of : which is the corresponding private key.
In this subsection we investigate elliptic curves described in [
For each curve we describe: () number of bits of the prime number which is the order of the generator of group (F); base-2 logarithm of the number of weak keys with order bounded by B. Since () is the number of generators of a cyclic group of order , i.e., the number of elements of order exactly , we define base-2 logarithm of the worst-case number of elliptic curve scalar multiplications required to test whether a key comes from a subgroup of order bounded by using iBSGS algorithm. Let (, ) = {1, . . . , : | − 1, ≤ , ∤ for all 1 ≤ < ≤ }. We define = log2 ∑︁ () |− 1 ≤ = log2
∑︁ ∈(,)
2⌈√⌉ Curve brainpoolP160r1 brainpoolP192r1 brainpoolP224r1 brainpoolP256r1 brainpoolP320r1 brainpoolP384r1 brainpoolP512r1
Here we describe the weak keys analysis of the curve secp192r1, as in Section 4.1. We use the computer
algebra system PARI/GP [
The elliptic curve group of secp192r1 is cyclic of prime order and the divisors of − 1 below the bound = 232 are
{2, 4, 5, 8, 10, 16, 20, 40, 80, 2389, 4778, 9556, 11945, 19112, 23890, 38224, 47780, 95560, 191120} thus by removing redundant divisors we get
() = {191120}
Doing the calculations we find that = 17.54 and = 9.8. This shows that secp192r1 has approximately 217.54 weak keys lying in subgroups of order below the bound = 232 and they can be detected in roughly 29.8 group operations in the elliptic curve group. We can repeat the test with a bound = 2160 and this leads to 2109.0 weak keys, computable in roughly 255.6 group operations.
Our analysis of weak keys within commonly used elliptic curves, specifically focusing on recommended and standardized ones, aims to identify them and to specify the worst-case scenario for their detection, expressed as the required number of scalar multiplications.
The results are summarized in tables, according to curve characteristics and standards: curves from the Brainpool standard (Table 1), curves defined over prime fields (Table 2), curves over binary ifelds (Table 3), and curves specifically used in Wireless Transport Layer Security (Table 4), a security protocol employed in the WPA architecture to ensure privacy, data integrity, and authentication during communication between wireless devices.
The data show that many curves have an abundance of weak keys at all levels, due to rather smooth factorization of − 1 and, in particular, many divisors of − 1 below the given bound . The actual counts of weak keys vary among the curves, but several of them has around 2160 weak keys within the bound = 2160.
Tables 1 to 4 show notable examples of curves that have remarkably few weak keys, especially Brainpool256r1, Brainpool224r1, secp224k1 and ECCp-359. Curves such as secp193r2, Curve25519, c2pnb163v3 and ECCp-353 have few weak keys at lower bounds, but many at ≥ 2128. Therefore, the dificulty of identifying weak keys in these curves varies depending on the attacker’s computational resources. While computationally constrained attackers may find this task arduous, adversaries with suficient computational power encounter a significantly reduced barrier, due to the fact that the density of weak keys does not scale linearly. Curve c2pnb163v1 c2pnb163v2 c2pnb163v3 c2tnb191v1 c2tnb191v2 c2tnb191v3 c2pnb208w1 sect193r2 c2tnb239v1 c2tnb239v2 c2tnb239v2 c2tnb271v2 c2pnb304w1 ECCp-353 c2pnb368w1 c2tnb431r1 ECCp-359
In most cases, however, our analysis show that the probability that a randomly selected key is weak (simply given by the number of weak keys divided by the total number of keys) is very low. Thus, only verifiable randomness in key generation, demonstrably achieved through rigorous audits, can ensure the low probability of picking weak keys susceptible to this attack.
Moreover, a malicious party could cause users to be assigned weak keys, for example via compromised key generation software. To mitigate potential vulnerabilities, it is thus highly advisable that each participant validates the security of their own private key through self-testing, before exposing the public key for any purpose. Conversely, in scenarios demanding high security, a participant should verify the public key of the other party in order to ensure the exchange is robust to attacks up to a bounded computational efort.
It is interesting to notice that we can also use the described method to generate private keys that are secure against this kind of attacks. For this aim we restrict them to be a random power of − 1 , where is a primitive root in Z and is a large prime factor of − 1, thus forcing the private key to lie in an -order subgroup of Z*.
We implemented the finite fields arithmetic and the elliptic curve arithmetic using the Rust programming language. We employ the Montgomery ladder algorithm in the generation of private and public key pairs, thus fortifying resistance against side-channel attacks.
Moreover, we implemented the iBSGS algorithm presented in [
Using PARI/GP we implemented a script to calculate the number of weak keys up to a given bound and the worst-case complexity of finding them in terms of scalar multiplications.
It is noteworthy that identifying weak keys in a specific curve primarily involves computing the
divisors of − 1, which translates to factoring. The comprehensive analysis of standardized curves
was completed within several days, primarily using a computer with a Intel® CoreTM i3-2350M CPU @
2.30GHz × 4 cores, running Linux. All these tools are available at [
In this work we have presented a comprehensive analysis of standardized elliptic curves employed in prevalent applications. Our objective has been to quantify the prevalence of weak keys, defined as private keys residing within subgroups of the auxiliary group Z* whose orders fall below a specified threshold (and hence amenable to recovery attacks). Furthermore, we have established the worst-case complexity associated with verifying whether a given key possesses this vulnerability.
To achieve these results, we leverage the implicit baby-step giant-step algorithm [
Our analysis reveals a potential vulnerability in many standardized curves where a significant number
of private keys reside within a small subgroup of the auxiliary group. This arises from the presence
of numerous small divisors in the auxiliary group order. While the likelihood of randomly selecting a
weak key remains low, malicious actors could exploit this weakness by manipulating the key generation
libraries utilized by applications. This manipulation would enable the construction of private keys
readily recoverable from their corresponding public keys via the iBSGS algorithm. Consequently, it is
imperative for applications to implement rigorous testing of keys generated by these libraries prior to
their usage. In fact, we have implemented all the algorithms used in this paper in Rust and PARI/GP.
These tools, available at [
Future Work. To counteract the positive impact of using the iBSGS algorithm, a possible solution would be to standardize elliptic curves whose group order is a safe prime, i.e., a prime such that = 2 + 1 where is also a prime. More efort should be made in order to evaluate and assess the possible pitfalls of using such a prime.
Moreover, it would be interesting to use the implicit representation to improve other algorithms such
as the Pohlig-Hellman [
This work has been partially supported by the Department Strategic Project on Artificial Intelligence (2020-25) of the University of Udine, and the project SERICS (PE00000014) under the NRRP MUR program funded by the EU - NGEU. We thank Luca Campa for discussions and suggestions about the content of this paper.