公钥是否超出Mod P?对离散对数问题的澄清要求 [英] Public key Exceeding Mod P? A Clarification Request On The Discrete Logarithm Problem

问题描述

我试图观察/实现离散对数问题，但是我注意到了一些有关它的信息.但是在开始讨论之前，请允许我澄清一下，可以纠正.

I tried to observe / implement the discrete logarithm problem but I noticed something about it; but before I get into it let me give some clarification which is open to correction.

a = b ^ x mod P

a = b^x mod P

为

a =地址的公钥；

a = the public key of the address;

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

b = the generator point of the secp256k1 koblitz curve (this is the curve in context);

x =离散日志；

P =模整数.

我结合了以下所有参数:

I coupled all parameters below:

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

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

B = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A68554199C47D08F FB10D4B8(未压缩的生成器点)

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 59F2815B16F81798(压缩发生器点)

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

X =?

P = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFEFFFFFC2F

P = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

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

I don't actually know what part of the parameters I should use ( compressed or uncompressed)

N.B:我尝试将未压缩的公钥设置为Mod P，但未压缩的公钥的大小超出了Mod P.

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

我该怎么办?

推荐答案

a = b ^ x mod P其中

a = b^x mod P Where as

a =地址的公钥；

a = the public key of the address;

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

b = the generator point of the secp256k1 koblitz curve (this is the curve in context);

x =离散日志；

P =模整数.

我们得到了离散对数问题(DLOG)(也称为索引演算)；给定 a，b，和 P 找到 x ，这样就可以保存 a = b ^ x mod P .上面实际上是OP使用的有限域DLOG的乘法符号.ECC DLOG是可加的，并且具有不同的表示法；

We are given a discrete logarithm problem (DLOG) ( also called the index calculus ); That is given a, b, and P find x such that a = b^x mod P is held. The above is actually the multiplicative notation for finite field DLOG as used by OP. ECC DLOG is additive and has different notation as;

• 在给定点 A 和基本 B 的情况下找到 x ，这样 A = [x] B 保持在曲线E(F _P )上. [x] B 只是意味着将点 B x倍添加到自身.

• That is given points A and the base B find x such that A = [x]B is held on the curve E(F_P). [x]B simply means that add the point B x-times to itself.

压缩

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

The beginning byte provides information about compression.

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

• 02 compression and choose y
• 03 compression and choose -y
• 04 No compression

要找到 y ，请将 x 放入曲线方程中，并通过Tonelli-Shanks算法求解二次余数.

To find the y, put the x into the curve equation and solve the quadratic residue by the Tonelli-Shanks algorithm.

在您的情况下，两个都给出，没问题.使用未压缩的公钥.

In your case, both are given, no problem. Use the uncompressed public key.

secp256k1的当前记录是114位，由Aleksander Zieniewic在2020年6月16日提供，他们提供了其软件.因此，如果您的目标不低，就无法打破离散日志.

The current record for secp256k1 is 114-bit On 16 June 2020 by Aleksander Zieniewic and they provided their software. So, if you don't have a low target, you cannot break the discrete log.

我尝试将未压缩的公钥设置为Mod P，但是未压缩的公钥的大小超出了Mod P.

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 并检查是否相等.

A point Q in the Elliptic curve when used affine coordinate system it has two coordinates as Q=(x,y) where x,y from the defining field (P in your case). When checking a point Q is either on the curve or not put x and y into the curve equation y^2 = x^3+ax+b and check the equality.

要解压缩，将 x 的值插入到等式 x ^ 3 + ax + b mod P 中，得出值 a ，然后使用Tonelli-Shanks算法在此等式中找到 a 的平方根 y ^ 2 = mod P 来找到 y 和 -y .根据压缩值选择 y 或 -y .

To uncompress insert the value of x into the equation x^3+ax+b mod P to get let say value a, then use the Tonelli-Shanks algorithm to find the square root of a in this equation y^2 = a mod P to find y and -y. According to compression value choose y or -y.

每个评论的更新

我尝试使用压缩的公钥，但它仍然大于mod p.

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

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

Compression a point requires information about what is the compression. Now you have given two forms of the public key a;

1. 无压缩:因为开头是 04
2. 压缩，但选择 -y ，因为它是从 03
开始的

1. No compression: since the beginning starts with 04
2. Compression but choose the -y since starts wiht 03

在此处使用大写字母不要与十六进制 a ;

Using capitals here not to confuse with hex a;

A = 04
4f355bdcb7cc0af728ef3cceb9615d90684bb5b2ca5f859ab0f0b704075871aa
385b6b1b8ead809ca67454d9683fcf2ba03456d6fe2c4abe2b07f0fbdbb2f1c1

A = 03
4f355bdcb7cc0af728ef3cceb9615d90684bb5b2ca5f859ab0f0b704075871aa

您可以使用曲线方程式来导出选择了 -y

You can use the curve equation to derive the second part with chosen -y

您可以将坐标值与

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

或者用你的眼睛和思想；

or use yours eye and mind;

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

这篇关于公钥是否超出Mod P?对离散对数问题的澄清要求的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！