公钥超过模组P?关于离散对数问题的澄清请求

Question

我试图观察/实现离散对数问题，但我注意到了一些事情;但在我进入它之前，让我给出一些可以纠正的澄清。

a = b^x mod P

其中作为

a = 地址的公钥;

b = secp256k1 科闪电曲线的发生点(这是 上下文中的曲线);

x = 离散日志;

P = 模整数。

我耦合了以下所有参数：

A = 044f355bdcb7cc0af728ef3cceb9615d90684bb5b2ca5f859ab0f0b704075871aa385b6b1b8ead809ca67454d9683fcf2ba03456d6fe2c4abe2b07f0fbdbb2f1c1 (未压缩的公钥)
034f355bdcb7cc0af728ef3cceb9615d90684bb5b2ca5f859ab0f0b704075871aa ： (压缩公钥)

B = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8(未压缩发电机点)

02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798(压缩发生点)

X = ？

P = FFFFFFFFF FFFFFFFFF FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC2F

我实际上不知道我应该使用参数的哪一部分(压缩或未压缩)

N. B ： 我尝试将未压缩的公钥转换为 Mod P，但未压缩的公钥的大小超过了 Mod P。

我该怎么办？

Answer 1

a = b^x mod P where as

a = 地址的公钥;

b = secp256k1 科闪电曲线的发生点(这是 上下文中的曲线);

x = 离散日志;

P = 模整数。

我们得到一个离散对数问题(DLOG)(也称为指数微积分);这是a, b,的，P找到x，以便举行a = b^x mod P。以上实际上是OP使用的有限域DLOG的乘法表示法。 ECC DLOG是加法的，并且具有不同的表示法;

• 这是给定的点A和底B找到x使得A = [x]B保持在曲线 E(F_P) 上。[x]B只是意味着将点Bx 倍添加到自身上。

压缩

起始字节提供有关压缩的信息。

• 02压缩并选择y
• 03压缩并选择-y
• 04无压缩

为了找到y，将x放入曲线方程中，并用Tonelli-Shanks算法求解二次残差。

---

在你的情况下，两者都给了，没问题。使用未压缩的公钥。

secp256k1 的当前记录是 114 位 2020 年 6 月 16 日由亚历山大·齐涅维奇提供，他们提供了他们的软件。因此，如果没有低目标，则无法中断离散日志。

我尝试将未压缩的公钥用于 Mod P，但未压缩的公钥的大小超过了 Mod P。

当使用仿射坐标系时，椭圆曲线中Q的点，它有两个坐标，Q=(x,y)x,y定义字段(在您的例子中为 P)。当检查点 Q 是否在曲线上或未放入曲线方程x和y时，y^2 = x^3+ax+b并检查相等性。

要解压缩，请将x的值插入方程x^3+ax+b mod P得到假设值a，然后使用Tonelli-Shanks算法找到该方程中a的平方根，y^2 = a mod P找到y和-y。根据压缩值选择y或-y。

每条评论更新

我尝试使用压缩公钥，但它仍然比 mod p 大。

压缩点需要有关压缩是什么的信息。现在您已经给出了两种形式的公钥a;

1. 无压缩：从04开始
2. 压缩，但选择-y，因为从03开始

在这里使用大写字母不要与十六进制a混淆;

A = 04
4f355bdcb7cc0af728ef3cceb9615d90684bb5b2ca5f859ab0f0b704075871aa
385b6b1b8ead809ca67454d9683fcf2ba03456d6fe2c4abe2b07f0fbdbb2f1c1

A = 03
4f355bdcb7cc0af728ef3cceb9615d90684bb5b2ca5f859ab0f0b704075871aa

您可以使用曲线方程推导具有所选-y的第二部分

您可以将坐标值与

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0x4f355bdcb7cc0af728ef3cceb9615d90684bb5b2ca5f859ab0f0b704075871aa
if a>p:
print("a")

或者用你的眼睛和头脑;

P   = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
x(A)= 4f355bdcb7cc0af728ef3cceb9615d90684bb5b2ca5f859ab0f0b704075871aa
y(A)= 385b6b1b8ead809ca67454d9683fcf2ba03456d6fe2c4abe2b07f0fbdbb2f1c1