我想实现ECDH，用户可以在其中定义椭圆曲线的a，b和p参数。
如何计算发电机基点G？是满足椭圆曲线方程$ y ^ 2 \ equiv x ^ 3 + ax + b \ pmod p $的点吗？
在给定基点的情况下，如何计算阶次n和辅因子h ？
#1 楼
可以在可接受的时间内找到所需的值。TL; DR：找到曲线阶数，将其分解为因子，选择一个（随机）点，直到获得具有所需阶数的点为止，然后首先，您可以使用yyyyyyy的答案，使用Schoof算法找到所描述曲线的阶次$ n $。请注意，此顺序应为素数或素数的小数倍（4x-8x），以增强安全性，但不必具有这些属性即可使方案起作用。
下一步，您需要实际考虑该顺序。这是可行的，因为此顺序的长度通常约为500位（如果您不打算使用256位安全级别，则长度会少很多），这可以为FREAK完成，也可以做到。当然，如果曲线阶数是素数或素数的小倍数（4x-8x），则可能不需要使用GNFS获得因式分解，而是可以给出（素数情况）或通过试验除法找到（小倍数情况） ）。
最后，您只需选择一个曲线点并确定其顺序，直到您按所需的顺序$ t $击中一个点，这也会产生辅助因子$ h = n / t $。通常，您会希望拥有$ h \ leq 8 $，并且通常还会从具有较小x坐标的点开始，然后逐步尝试所有操作，直到达到一个完全满足条件的条件。
可以在文献中的很多地方找到用于此目的的算法，假设我们正在测试点A且$ n = p_1 ^ {e_1}，我将在《应用密码学手册》中快速重申这一算法。 \ cdot p_2 ^ {e_2} \ cdot \ cdot \ cdot p_k ^ {e_k} $：
从$ 1 $设置$ t \ get n $
到$ k $，请执行以下操作：
设置$ t \得到t / p_i ^ {e_i} $
计算$ A_1 \得到t \ cdot A $
在$ A_1 \ neq \ mathcal O $执行以下操作时：计算$ A_1 \得到p_i * A_1 $并设置$ t \ get t \ cdot p_i $
输出$ t $按照$ A $的顺序
请注意：我强烈建议您不要在用户选择参数的情况下使用自定义曲线。这些可能容易受到安全曲线项目中记录的攻击的影响。应首选标准化曲线（例如Curve448或Curve25519），以简化实施并更好地分析安全性。
评论
$ \ begingroup $
您无需考虑$ \ mathbf F_p $理性点组的顺序，只需确保该顺序为质数（对于蒙哥马利曲线或爱德华兹曲线，则为质数的四倍）。这可以比分解更有效地完成。考虑到在找到合适的曲线之前必须先测试许多曲线，因此尝试分解所有阶数将浪费时间。
$ \ endgroup $
– Calodeon
2015年9月11日在23:29
$ \ begingroup $
@Calodeon，“确保订单是素数或素数的四倍。” -我认为这是分解的一部分：首先确定它是否是素数，如果不先尝试小因子，OP明确表示他不会自己选择$ a，b，p $，而是提供这些值，因此答案可能不会假设任何有关$ a，b，p $或$ n $的信息。
$ \ endgroup $
– SEJPM♦
2015年9月12日在13:03
$ \ begingroup $
我假设$（a，b，p）$是ECCDH的有效三元组（如果不是，则ECCDH是不安全的），那么$ n $必须是素数。所以Calodeon有权利。如果$ n $不是大质数，则应用Pohlig-Hellman。由于OP在ECCDH中很有趣，因此域参数有很多约束（一个是$ n $是素数）。
$ \ endgroup $
– 111
2015年9月16日下午2:13
$ \ begingroup $
@ 111，OP表示用户选择了参数$（a，b，p）$，这意味着他无法影响它们，这意味着他无法拒绝任何参数集和查找任务确定参数是否安全将委托给用户。此外，OP在他的问题中的任何时候都没有使用“安全”或“安全”或类似的词。因此，答案将不会假设$ n $是质数（或质数的一小部分）。但请您明确指出：答案确实强烈表明，使用标准化曲线会更好。
$ \ endgroup $
– SEJPM♦
2015年9月16日20:18在
评论
小心。在许多情况下，必须考虑生成ECC参数。请参阅safecurves.cr.yp.to。我的这个答案解释了如何计算椭圆曲线的阶数。
另请参阅eprint.iacr.org/2015/366.pdf，以获取一种为ECC生成参数的新方法。
eprint.iacr.org/2015/659.pdf和csrc.nist.gov/groups/ST/ecc-workshop-2015/presentations/…应该有用
有弹性的城堡包含生成EC参数的方法。我同意SEJPM的观点，这不应掉以轻心。仅当您真的不信任NIST或Brainpool曲线时，才应该这样做。我不认为NIST曲线已经过时，但是我个人相信德国的公司和大学组成的财团比NIST还要痛苦得多，尤其是在Dual-DRBG惨败之后。或者，您当然可以使用其中一种安全的安全曲线。