Quote
Hi Burt,
Rob forwarded your email to me.
I am the current SECG chair, so I will try to provide a partial answer. I did not know that BitCoin is using secp256k1. Indeed, I am surprised to see anybody use secp256k1 instead of secp256r1. With my SECG chair hat on, I am pleased because this curve is a pure SECG curve, not a NIST curve (but see * below).
Minor aside: SECG updated SEC2 in 2010. The curve secp256k1 is now in Section 2.4, which is smaller because SECG removed the very small curves.
I was not involved in the parameter selection for secp256k1, and may not have even been a Certicom employee at the time of secp256k1 parameter selection. I am going to assume that you are mainly concerned about a potential backdoor, given the coincidence of your query with certain news coverage. I will attempt to address this concern mainly by looking directly SEC2 document and parameters.
1. The defining Weierstrass coefficients (a,b) of the curve are (0,7). The SEC2 document says, in Section 2.1, “The recommended parameters associated with a Koblitz curve were chosen by repeatedly selecting parameters admitting an efficiently computable endomorphism until a prime order curve was found”. Furthermore, I see that the small values 0 and 7 are certainly nothing-up-my-sleeve values. More precisely, they cannot be the result of a malicious exhaustive search of curve selection until the curve lands in a weak class. So, the only risk is that the special class, with small coefficient and efficient endomorphism is somehow weak. I am not aware of any such weakness. Indeed, I highly doubt such a weakness, at least in the ECDLP: it would constitute a major breakthrough in ECDLP. Also, some ECC theorists have established the equivalence ECDLP between curves of the same order, via something called isogenies. I am not expert in that area, but it may imply that mere fact that the curve coefficients are small is insufficient to constitute a weak class of ECDLP.
2. The defining field size p seems to be a 256-bit prime of the special form 2^256-s where s is small. This form is for efficiency. I am not sure why this particular value of s is chosen, because I expect that smaller s could be found. Nevertheless, there does not seem to be too much wiggle room in this choice of s, because s itself also has a special form: s = 2^32 + t, where t < 1024. I would not be surprised if s was the smallest value of this form, but I did not check. In any case, there are no known weak classes of prime order field for elliptic curves.
3. The base point G is something I cannot explain, but the general understanding, at the time and still now, is that the base point G cannot contain a backdoor in the main problem underlying ECC, namely ECDLP and ECDHP. Indeed, random self-reducibility applies to prove that the choice of G is irrelevant for most versions of these problems. Some cryptographic schemes, including ECDSA, seem to depend mildly on some other problems, in which the choice of G may be more relevant. In particular, the ECDSA verification of a signature (r,s) includes a check that r is not zero. If this check is dropped, then there is a possibility that party who chose G can have chosen G in such that to make some signature (0,s) valid for a particular message m. (For details and examples, see my chapter in Advances in Cryptology II, or my paper “Generic Groups, Collisiion Resistance, and ECDSA”, or my IACR eprint “The One-Up Problem for ECDSA”.) I strongly doubt that G is malicious, because these properties were not widely known at the time, and the adversary seems to have little to gain, the verifier has to be faulty.
4. Rob Lambert and John Goyo were present at the time Certicom generated the secp256k1 parameters, but were not directly involved either. John Goyo recalls that two former employees generated the domain parameters. In particular, no external organization, including any that some now asperse with backdoor insertion, generated the parameters. We will continue to investigate our records and archives.
I hope that the four points above address your main concerns, despite them not fully answering your questions. Feel free to request further clarification, but, unfortunately, I am not sure if we have maintained all the archives.
(*) With my SECG chair hat off now, I recognize some validity of the following argument: the NIST curves have received more scrutiny than the other SECG curves, because the prominence of NIST created a greater incentive to study these curves. Putting my SECG chair back on, a mild counterargument to the latter argument is that: none of the known weak classes of curves resulted by targeting particular parameters. Rather they are results from basic research on ECC.
Best regards,
Dan
Rob forwarded your email to me.
I am the current SECG chair, so I will try to provide a partial answer. I did not know that BitCoin is using secp256k1. Indeed, I am surprised to see anybody use secp256k1 instead of secp256r1. With my SECG chair hat on, I am pleased because this curve is a pure SECG curve, not a NIST curve (but see * below).
Minor aside: SECG updated SEC2 in 2010. The curve secp256k1 is now in Section 2.4, which is smaller because SECG removed the very small curves.
I was not involved in the parameter selection for secp256k1, and may not have even been a Certicom employee at the time of secp256k1 parameter selection. I am going to assume that you are mainly concerned about a potential backdoor, given the coincidence of your query with certain news coverage. I will attempt to address this concern mainly by looking directly SEC2 document and parameters.
1. The defining Weierstrass coefficients (a,b) of the curve are (0,7). The SEC2 document says, in Section 2.1, “The recommended parameters associated with a Koblitz curve were chosen by repeatedly selecting parameters admitting an efficiently computable endomorphism until a prime order curve was found”. Furthermore, I see that the small values 0 and 7 are certainly nothing-up-my-sleeve values. More precisely, they cannot be the result of a malicious exhaustive search of curve selection until the curve lands in a weak class. So, the only risk is that the special class, with small coefficient and efficient endomorphism is somehow weak. I am not aware of any such weakness. Indeed, I highly doubt such a weakness, at least in the ECDLP: it would constitute a major breakthrough in ECDLP. Also, some ECC theorists have established the equivalence ECDLP between curves of the same order, via something called isogenies. I am not expert in that area, but it may imply that mere fact that the curve coefficients are small is insufficient to constitute a weak class of ECDLP.
2. The defining field size p seems to be a 256-bit prime of the special form 2^256-s where s is small. This form is for efficiency. I am not sure why this particular value of s is chosen, because I expect that smaller s could be found. Nevertheless, there does not seem to be too much wiggle room in this choice of s, because s itself also has a special form: s = 2^32 + t, where t < 1024. I would not be surprised if s was the smallest value of this form, but I did not check. In any case, there are no known weak classes of prime order field for elliptic curves.
3. The base point G is something I cannot explain, but the general understanding, at the time and still now, is that the base point G cannot contain a backdoor in the main problem underlying ECC, namely ECDLP and ECDHP. Indeed, random self-reducibility applies to prove that the choice of G is irrelevant for most versions of these problems. Some cryptographic schemes, including ECDSA, seem to depend mildly on some other problems, in which the choice of G may be more relevant. In particular, the ECDSA verification of a signature (r,s) includes a check that r is not zero. If this check is dropped, then there is a possibility that party who chose G can have chosen G in such that to make some signature (0,s) valid for a particular message m. (For details and examples, see my chapter in Advances in Cryptology II, or my paper “Generic Groups, Collisiion Resistance, and ECDSA”, or my IACR eprint “The One-Up Problem for ECDSA”.) I strongly doubt that G is malicious, because these properties were not widely known at the time, and the adversary seems to have little to gain, the verifier has to be faulty.
4. Rob Lambert and John Goyo were present at the time Certicom generated the secp256k1 parameters, but were not directly involved either. John Goyo recalls that two former employees generated the domain parameters. In particular, no external organization, including any that some now asperse with backdoor insertion, generated the parameters. We will continue to investigate our records and archives.
I hope that the four points above address your main concerns, despite them not fully answering your questions. Feel free to request further clarification, but, unfortunately, I am not sure if we have maintained all the archives.
(*) With my SECG chair hat off now, I recognize some validity of the following argument: the NIST curves have received more scrutiny than the other SECG curves, because the prominence of NIST created a greater incentive to study these curves. Putting my SECG chair back on, a mild counterargument to the latter argument is that: none of the known weak classes of curves resulted by targeting particular parameters. Rather they are results from basic research on ECC.
Best regards,
Dan
