Добавление точки эллиптической кривой с использованием bouncycastle

Question

Моя проблема очень проста: мне нужно добавить две точки над Fp с использованием Java. Как только java api не хватает некоторых ecc utils, я использую bouncycastle.

Здесь используются формулы:

P + Q = -R 
α = (yq - yp)/(xq-xp) 
уr = -yp + α(xp - xr) 
xr = α^2 - xp - xq 

И быстрое внедрение вышеуказанных формул в Java:

String newline = System.lineSeparator(); 
BigInteger yp = new BigInteger("4018974056539037503335449422937059775635739389905545080690979365213431566280"); 
BigInteger yq = new BigInteger("17614944419213781543809391949654080031942662045363639260709847859438286763994"); 
BigInteger xp = new BigInteger("2"); 
BigInteger xq = new BigInteger("57520216126176808443631405023338071176630104906313632182896741342206604859403"); 
BigInteger p = new BigInteger("57896044618658097711785492504343953926634992332820282019728792003956564821041"); 
BigInteger a_ = new BigInteger("7"); 
BigInteger b_ = new BigInteger("43308876546767276905765904595650931995942111794451039583252968842033849580414"); 
ECFieldElement x1 = new ECFieldElement.Fp(p, xp); 
ECFieldElement y1 = new ECFieldElement.Fp(p, yp); 

ECFieldElement x2 = new ECFieldElement.Fp(p, xq); 
ECFieldElement y2 = new ECFieldElement.Fp(p, yq); 


ECFieldElement a = new ECFieldElement.Fp(p, a_); 
System.out.print("A = " + a.toBigInteger() + newline); 
ECFieldElement b = new ECFieldElement.Fp(p, b_); 
System.out.print("B = " + b.toBigInteger() + newline); 

BigInteger alpha = (yq.subtract(yp)).divide((xq.subtract(xp))); 
ECFieldElement alpha_ = new ECFieldElement.Fp(p, alpha); 

ECFieldElement xr = new ECFieldElement.Fp(p,alpha.pow(2).subtract(x1.toBigInteger()).subtract(x2.toBigInteger())); 
ECFieldElement yr = new ECFieldElement.Fp(p,y1.negate().add(x1.multiply(alpha_)).subtract(xr.multiply(alpha_)).toBigInteger()); 
System.out.print("P + Q x coordinate:" + xr.toBigInteger() + newline); 
System.out.print("P + Q y coordinate:" + yr.toBigInteger() + newline); 

Выход следующим образом:

A = 7 
B = 43308876546767276905765904595650931995942111794451039583252968842033849580414 
P + Q x coordinate:-57520216126176808443631405023338071176630104906313632182896741342206604859405 
P + Q y coordinate:53877070562119060208450043081406894150999252942914736939037812638743133254761 

Эти результаты неверны, потому что следующий сценарий Sage и this сервис имеют одинаковый результат, и он отличается от моего.

p = 57896044618658097711785492504343953926634992332820282019728792003956564821041; 
A = 7; 
B = 43308876546767276905765904595650931995942111794451039583252968842033849580414; 
xp = 2; 
yp = 4018974056539037503335449422937059775635739389905545080690979365213431566280; 
xq = 57520216126176808443631405023338071176630104906313632182896741342206604859403; 
yq = 17614944419213781543809391949654080031942662045363639260709847859438286763994; 
F = GF(p) 
C = EllipticCurve(F, [ A, B ]) 
P = C(xp, yp) 
Q = C(xq, yq) 
P + Q 
(51107436475926671824327183547145585639291252685317542895128927043108270260044 : 8275382333273532770266263241039288966808027917805772529614893800343160424015 : 1) 

Может кто-нибудь, пожалуйста, укажите мне, что я исправлю, чтобы получить правильный результат?

Answer 1

Вот пример кода, показывающий как явный расчет, так и то, как вы просто используете встроенные функции библиотеки для этого. Выход согласуется с выходом Sage в обоих случаях.

package org.bc.sample; 

import java.math.BigInteger; 

import org.bouncycastle.math.ec.ECCurve; 
import org.bouncycastle.math.ec.ECFieldElement; 
import org.bouncycastle.math.ec.ECPoint; 

public class ECPointAddition 
{ 
    public static void main(String[] args) 
    { 
     BigInteger prime = new BigInteger("57896044618658097711785492504343953926634992332820282019728792003956564821041"); 
     BigInteger A = new BigInteger("7"); 
     BigInteger B = new BigInteger("43308876546767276905765904595650931995942111794451039583252968842033849580414"); 

     ECCurve curve = new ECCurve.Fp(prime, A, B); 

     BigInteger Px = new BigInteger("2"); 
     BigInteger Py = new BigInteger("4018974056539037503335449422937059775635739389905545080690979365213431566280"); 
     BigInteger Qx = new BigInteger("57520216126176808443631405023338071176630104906313632182896741342206604859403"); 
     BigInteger Qy = new BigInteger("17614944419213781543809391949654080031942662045363639260709847859438286763994"); 

     // Explicit affine addition 
     ECFieldElement xp = curve.fromBigInteger(Px), yp = curve.fromBigInteger(Py); 
     ECFieldElement xq = curve.fromBigInteger(Qx), yq = curve.fromBigInteger(Qy); 
     ECFieldElement alpha = yq.subtract(yp).divide(xq.subtract(xp)); 
     ECFieldElement xr = alpha.square().subtract(xp).subtract(xq); 
     ECFieldElement yr = xp.subtract(xr).multiply(alpha).subtract(yp); 

     System.out.println("EXPLICIT"); 
     System.out.println(xr.toBigInteger().toString(10)); 
     System.out.println(yr.toBigInteger().toString(10)); 

     // Point addition using built-in formulae 
     ECPoint P = curve.createPoint(Px, Py); 
     ECPoint Q = curve.createPoint(Qx, Qy); 
     ECPoint R = P.add(Q).normalize(); 

     System.out.println("BUILT-IN"); 
     System.out.println(R.getAffineXCoord().toBigInteger().toString(10)); 
     System.out.println(R.getAffineYCoord().toBigInteger().toString(10)); 
    } 
} 

Когда вы видите формулы, включающие координаты эллиптических точек кривой, следует понимать, что эти расчеты должны быть сделаны в конечном поле координаты принадлежат, в то время как вы вычисления, например, alpha просто используя математику BigInteger. В результате ошибки divide не совпадают.

Обратите также внимание, что явная формула здесь не будет работать, если две входные точки имеют одинаковую координату x. Встроенный библиотечный метод правильно обрабатывает этот вид края, поэтому я бы рекомендовал вам использовать его.

---

Исполняемая версия кода может быть найдена here.