给定公钥，找到点和椭圆曲线

Question

我正在尝试解决这个问题。一旦公钥已知，我想知道用于生成该公钥的点和椭圆曲线。

例如，给定这个ECC公钥：

04 6b fb ee c6 9d e7 2c 66 a6 68 ec e1 aa f1 a2 64 a3 c9 b2 88 fb 32 d0 59 e9 2c 3e 5d 5b d4 d7 b5 01 48 78 f4 47 9c 13 c8 83 d0 54 55 5c d9 0e cd 13 6e c4 cc 34 64 89 cd d6 4e 69 43 f3 33 86 4a b9 df e4 42 dc bf 8f 69 c1 9e 71 d0 35 ff 31 7f c0 32 fc 21 55 ca ea a6 5b 49 3d 19 1d 39 9a c0

如何确定用于生成该ECC公钥的点和椭圆曲线？

- avm_69

---

你应该在crypto上问这个问题。在我看来，如果你只知道公钥，那么没有简单有效的方法可以做到这一点。 - Qiu

@Qiu 另一方面，在加密 avm_69 上，他不会得到代码 :P - Maarten Bodewes

请勿删除您的问题内容。要将问题标记为已解决，请将最有帮助的答案标记为已接受。同时，给所有帮助过您的答案点赞。 - Gilles 'SO- stop being evil'

Answer 1

如果椭圆曲线是联邦政府使用的推荐椭圆曲线之一，您可以轻松找到域参数(p,a,b,G,n,h)，其中G是基点，公钥的位长度将告诉您曲线名称。

EC公钥是曲线上的一个点，例如：y^2 = x^3 + ax + b (mod p)，其中p是素数模数。

该点表示为八进制字符串，压缩或未压缩形式按照ANSI X9.62的规定。

因此，您提到的示例公钥由x坐标和y坐标组成：

公钥=标签+x坐标+y坐标

未压缩形式由tag = 0x04指示，压缩形式由tag = 0x02或tag = 0x03指示（请参见第2.2节）。

现在，示例公钥可以写成：

04
6bfbeec69de72c66a668ece1aaf1a264a3c9b288fb32d059e92c3e5d5bd4d7b5014878f4479c13c883d054555cd90ecd
136ec4cc346489cdd64e6943f333864ab9dfe442dcbf8f69c19e71d035ff317fc032fc2155caeaa65b493d191d399ac0

每个坐标的长度为48字节或384位。因此，该示例公钥“似乎是”来自EC P-384曲线。

- mazhar islam

---

请仅在代码中使用代码格式，而不是随意的单词。 - Gilles 'SO- stop being evil'

@Gilles，收到，先生。 - mazhar islam

这个答案的设置和描述都很好。而且很容易验证它是错误的。所使用的曲线是Brainpool曲线，而不是NIST曲线。 - Maarten Bodewes

尊敬的MaartenBodewes先生，我刚试图告诉OP如何找到曲线名称，其中该曲线是NIST推荐的。这就是为什么我的回答以“if”开头的原因。如果您仍然要求，我可以删除我的回答。 - mazhar islam

我认为修改答案以表明它也可能是另一条曲线（即Brainpool曲线）是可以接受的。我并不是在进行任何十字军东征，只是因为错误就是错误。答案的其余部分已经足够好了，我们应该保留它 :) - Maarten Bodewes

Answer 2

您应该按概率顺序检查每个已知（命名）曲线。当然，概率取决于情况，我不知道您从哪里获取了该点。

因此，您需要执行以下操作：

1. 循环遍历所有可找到的命名曲线； 2. 检查该点是否在曲线上有效且不为无穷大。

现在，如果您这样做，您会发现这是一个BrainpoolP384r1曲线，而不是NIST曲线。

---

好的，否则这段Java代码将会失效：

import java.util.Enumeration;
import java.util.LinkedList;
import java.util.List;

import org.bouncycastle.asn1.nist.NISTNamedCurves;
import org.bouncycastle.asn1.sec.SECNamedCurves;
import org.bouncycastle.asn1.teletrust.TeleTrusTNamedCurves;
import org.bouncycastle.asn1.x9.X962NamedCurves;
import org.bouncycastle.asn1.x9.X9ECParameters;
import org.bouncycastle.math.ec.ECPoint;
import org.bouncycastle.util.encoders.Hex;

public class CurveFinder {

    interface CurveRetriever {
        X9ECParameters getByName(String name);
        Enumeration<String> getNames();
    }

    public static void main(String[] args) {
        byte[] wd = Hex.decode("04 6b fb ee c6 9d e7 2c 66 a6 68 ec e1 aa f1 a2 64 a3 c9 b2 88 fb 32 d0 59 e9 2c 3e 5d 5b d4 d7 b5 01 48 78 f4 47 9c 13 c8 83 d0 54 55 5c d9 0e cd 13 6e c4 cc 34 64 89 cd d6 4e 69 43 f3 33 86 4a b9 df e4 42 dc bf 8f 69 c1 9e 71 d0 35 ff 31 7f c0 32 fc 21 55 ca ea a6 5b 49 3d 19 1d 39 9a c0".replaceAll("\\s+", ""));
        String name = findCurveName(wd);
        if (name == null) {
            System.out.println("Curve not found");
        } else {
            System.out.println("Curve: " + name);
        }
    }

    private static String findCurveName(byte[] wd) {
        List<CurveRetriever> retrievers = new LinkedList<>();
        retrievers.add(new CurveRetriever() {
            @Override
            public X9ECParameters getByName(String name) {
                return SECNamedCurves.getByName(name);
            }

            @Override
            public Enumeration<String> getNames() {
                return SECNamedCurves.getNames();
            }
        });
        retrievers.add(new CurveRetriever() {
            @Override
            public X9ECParameters getByName(String name) {
                return TeleTrusTNamedCurves.getByName(name);
            }
            @Override
            public Enumeration<String> getNames() {
                return TeleTrusTNamedCurves.getNames();
            }
        });
        retrievers.add(new CurveRetriever() {
            @Override
            public X9ECParameters getByName(String name) {
                return NISTNamedCurves.getByName(name);
            }
            @Override
            public Enumeration<String> getNames() {
                return NISTNamedCurves.getNames();
            }
        });
        retrievers.add(new CurveRetriever() {
            @Override
            public X9ECParameters getByName(String name) {
                return X962NamedCurves.getByName(name);
            }
            @Override
            public Enumeration<String> getNames() {
                return X962NamedCurves.getNames();
            }
        });
        for (CurveRetriever curveRetriever : retrievers) {
            String name = retrieveAndValidate(wd, curveRetriever);
            if (name != null) {
                return name;
            }
        }
        return null;
    }

    private static String retrieveAndValidate(byte[] wd,
            CurveRetriever retriever) {
        ECPoint decodedPoint = null;
        Enumeration<String> names = retriever.getNames();
        while (names.hasMoreElements()) {
            String name = names.nextElement();
            X9ECParameters curveParams = retriever.getByName(name);
            try {
                decodedPoint = curveParams.getCurve().decodePoint(wd);
            } catch (IllegalArgumentException e) {
                continue;
            }
            if (decodedPoint.isInfinity() || !decodedPoint.isValid()) {
                continue;
            }
            return name;
        }
        return null;
    }
}

显然，这段代码需要Bouncy Castle的轻量级API。我不知道为什么没有使用Bouncy Castle JCE提供程序 - 我想这个提供程序可以更好地控制曲线。

- Maarten Bodewes

---

公钥可以从此网站检索 https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/CSCA/csca-germany_101_self_signed_cer.zip?__blob=publicationFile ，您可以在此处找到更多信息 https://www.bsi.bund.de/EN/Topics/ElectrIDDocuments/CSCAcertGermany/cscaGermany_node.html。 鉴于这是Brainpool曲线，请问如何知道使用的点？ - avm_69

链接证书可以明确指定参数，也可以从前一个证书“借用”参数（第一个证书必须包括参数）。公共点本身当然包含在证书中，它与私有值$s$一起在某个HSM中生成。生成器g，也是一个点，是参数的一部分。 - Maarten Bodewes

所以，这是一个脑池曲线，并且该点是由公钥减去标签0x04得到的x,y坐标？ - avm_69

没错，就是这样。当然，在实际计算中，您仍需要将x、y坐标解释为一组固定大小的大端整数才能使用。请注意，如果需要更改参数，链接证书只会包括这些参数（这是允许的）。 - Maarten Bodewes