椭圆曲线密码学中的点减法

Question

我希望在一个素数域上的椭圆曲线上进行点减法。我尝试将要减去的点表示为(x,-y log(p))，但我的答案似乎不匹配。

这是我尝试进行减法的方式：

 s9=point_addition(s6.a,s6.b,((s8.a)%211) ,-((s8.b)%211));

这里的 s9、s6 和 s8 都是包含两个 int 的结构体。

这是我的点加函数：

structure point_addition(int x1, int y1, int x2, int y2)
{
    int s,xL,yL;
    if((x1-x2)!=0)
    {
        if ((((y1-y2)/(x1-x2)) % 211)>0)
              s=(((y1-y2)/(x1-x2)) % 211);
        else
              s=(((y1-y2)/(x1-x2)) % 211) + 211;
        if ((((s*s)-(x1+x2)) % 211)>0)
              xL= (((s*s)-(x1+x2)) % 211) ;
        else
              xL= (((s*s)-(x1+x2)) % 211) + 211;
        if(((-y1+s*(x1-x2)) % 211)>0)
              yL= ((-y1+s*(x1-xL)) % 211);
        else
              yL= ((-y1+s*(x1-x2)) % 211) + 211;
    }
    else
    {
        xL= 198 ;
        yL= 139;
    }

    s7.a= xL;
    s7.b= yL;

    return s7 ;
}

该程序似乎没有给我正确的坐标，请帮我修复这段椭圆曲线密码学代码。

- Jowin Sathianesan

---

不要忘记在Jowin中标记你进行计算的语言，即使只是为了增加浏览量。我猜测是C语言，但你可以重新编辑问题来更改。 - Maarten Bodewes

Jowin，“division” mod p 意味着你必须计算一个模反元素。使用s=(((y1-y2)/(x1-x2)) % 211)不是正确的方法。 - President James K. Polk

GregS，我看到我必须编辑我的代码来使用模反元素法进行除法...但是我想知道即使使用普通除法，我得到的任何点都在椭圆曲线上！非常感谢您的答案！在我的程序中，无穷远点必须考虑椭圆，我可以采用什么点？ - Jowin Sathianesan

Answer 1

参考 GregS 对于除法模 p 的评论。你需要找到分母的逆元素然后相乘。为了计算模反元素，你可以使用扩展欧几里得算法。

同时，你将 y 坐标取反并在之后加上 211 的方式有些奇怪。最好在传递作为参数的域元素时保持其正确的范围，例如要获得 -y mod p，请使用 p-y。

我假设这只是一个学习练习，因为你使用的是非常小的域 :)

- Frank

---

请您详细解释一下，我感觉p-y是我在程序中寻找来替换-y mod(p)的。如果我说错了，请纠正我。 - Jowin Sathianesan

是的，我认为在您的情况下这样做没问题。我只是想说，使用同一字段元素的不同表示会引发问题。例如，如果您将x1 = 210和x2 = -1传递给point_addition函数，则检查if((x1-x2)!=0)将无法正常工作。 - Frank

Answer 2

我不明白你在做什么，不知道你的log(p)是什么意思，以及你的域参数在哪里输入，但减法很容易： 取反y坐标(-Y = modulus - y)，然后像平常一样简单相加。

如果你想要计算参考，你可以使用我的开源软件“Academic Signature”，链接在this link。它的计算非常透明，并且以人类可读的十六进制符号表示ECDSA签名结果。但我目前不确定它是否能够处理你所使用的这种短模量的计算。

关于如何正确编程ECC操作以及如何使用软件的描述，请参阅手册：Link to ecc Manual 祝好 Michael Anders

- Michael Anders

---

谢谢你的回复，迈克尔。我想做的是在C语言中实现以下教程http://www.dkrypt.com/home/ecc。p是椭圆曲线方程{y2 mod p = x3 + ax + b mod p}中的p。我下载了你的程序，它很棒，能否用这个程序找到以下内容：给定椭圆曲线方程y^2 mod(211) = (x^3 - 4) mod(p)，私钥为4，生成点为(2,2)，将0-200的数字映射到曲线上，使用教程中的方法加密要发送的数字4、5、6，它能告诉加密点和解密点吗？ - Jowin Sathianesan