Public 键超过 Mod P？关于离散对数问题的澄清请求

Question

我试图观察/实现离散对数问题，但我注意到了一些事情；但在开始之前，让我先澄清一下，有待更正。

a = b^x mod P

其中

a = 地址的public键；

b = secp256k1 koblitz 曲线的生成点（这是上下文中的曲线);

x = 离散对数；

P = 模整数。

我耦合了以下所有参数：

A = 044f355bdcb7cc0af728ef3cceb9615d90684bb5b2ca5f859ab0f0b704075871aa385b6b1b8ead809ca67454d9683fcf2ba03456d6fe2c4abe2b07f0fbdbb2f1c1 (uncompressed public key)
034f355bdcb7cc0af728ef3cceb9615d90684bb5b2ca5f859ab0f0b704075871aa : (compressed public key)

B = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8 (uncompressed generator point)

02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 (compress generator point)

X = ?

P = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

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

N。 B : 我尝试将未压缩的 public 密钥设置为 Mod P，但未压缩的 public 密钥的大小超过了 Mod P。

我该怎么办？

Answer 1

a = b^x mod P Where as

a = 地址的public键；

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 只是意味着将点 B x 次添加到自身。

压缩

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

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

求y，将x代入曲线方程，用Tonelli-Shanks算法求解二次留数

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

secp256k1 的当前记录是 114 位，由 Aleksander Zieniewic 于 2020 年 6 月 16 日提供，他们提供了 their software。所以，如果你没有低目标，你就不能打破离散对数。

I tried the uncompressed public key to Mod P but the uncompressed public key exceeded the Mod P in size.

当使用仿射坐标系时，椭圆曲线中的一个点 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 算法求 [= 的平方根39=] 在这个等式 y^2 = a mod P 中找到 y 和 -y。根据压缩值选择y或-y.

根据评论更新

I tried using the compressed public key but it was still bigger than mod p.

压缩一个点需要关于什么是压缩的信息。现在你已经给出了两种形式的 public 键 a;

无压缩：因为开头是 04
压缩但选择 -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

Public 键超过 Mod P？关于离散对数问题的澄清请求

Public key Exceeding Mod P? A Clarification Request On The Discrete Logarithm Problem

cryptography

compression

public-key-encryption

secp256k1