椭圆曲线上的标量乘法

Question

我将本文用于任务https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/

标量乘法为

其中n是自然数

我使用此代码查找Q

    import numpy as np
    def f(x,a,b):
        return x**3+a*x + b

    def bits(n):
        while n:
            yield n & 1
            n >>= 1

    def double_and_add(n, x):
        result = 0
        addend = x

        for bit in bits(n):
            if bit == 1:
                result += addend
            addend *= 2

        return result



    P = 3
    Q = double_and_add(P,151)  #453  <--- issue here

    xp = P
    yp = np.sqrt(f(xp)) #4 

    xq = Q
    yq = np.sqrt(f(xq))

为什么我的Q变量与站点https://cdn.rawgit.com/andreacorbellini/ecc/920b29a/interactive/reals-mul.html上的变量不匹配

Answer 1

本文具有误导性，因为double_and_add函数是为数字而不是点编写的。

P应该是一个点，即元组(3,4)。

然后您必须执行团体法。您可以使用参考中的代数加法公式：

a, b = -7, 10  # curve coefficients from your exemple

def add(P, Q):
    if P is None or Q is None: # check for the zero point 
        return P or Q
    xp, yp = P
    xq, yq = Q
    if xp == xq:
        return double(P)
    m = (yp - yq) / (xp - xq)
    xr = m**2 - xp - xq
    yr = yp + m * (xr - xp)
    return (xr, -yr)

def double(P): 
    if P is None:
        return None 
    xp, yp = P 
    m = (3 * xp ** 2 + a) / (2 * yp) 
    xr = m**2 - 2*xp 
    yr = yp + m * (xr - xp) 
    return (xr, -yr)

在double_and_add中，使用低位进行加法和加倍。

def double_and_add(n, P):
    result = None # This is our zero point
    addend = P
    for b in bits(n):
        if b:
            result = add(result, addend)
        addend = double(addend)
    return result

您可以验证：

> double_and_add(151, (3,4))
(7.12340267635097, 17.93315495174943)