我使用标准投影坐标得到了点乘法错误的堆栈。我不知道我错过了什么,但相乘的点不在曲线上,有时它会输出类似算术异常的东西:整数不可逆。
public class ECPointArthimetic {
EllipticCurve ec;
private BigInteger x;
private BigInteger y;
private BigInteger z;
private BigInteger zinv;
private BigInteger one = BigInteger.ONE;
private BigInteger zero = BigInteger.ZERO;
private boolean infinity;
public ECPointArthimetic(EllipticCurve ec, BigInteger x, BigInteger y, BigInteger z) {
this.ec = ec;
this.x = x;
this.y = y;
// Projective coordinates: either zinv == null or z * zinv == 1
// z and zinv are just BigIntegers, not fieldElements
if (z == null) {
this.z = BigInteger.ONE;
} else {
this.z = z;
}
this.zinv = null;
infinity = false;
//TODO: compression flag
}
public BigInteger getX() {
if (this.zinv == null) {
this.zinv = this.z.modInverse(this.ec.getP());
}
return this.x.multiply(this.zinv).mod(this.ec.getP());
}
public BigInteger getY() {
if (this.zinv == null) {
this.zinv = this.z.modInverse(this.ec.getP());
}
return this.y.multiply(this.zinv).mod(this.ec.getP());
}
public boolean pointEquals(ECPointArthimetic other) {
if (other == this) {
return true;
}
if (this.isInfinity()) {
return other.isInfinity();
}
if (other.isInfinity()) {
return this.isInfinity();
}
BigInteger u, v;
// u = Y2 * Z1 - Y1 * Z2
u = other.y.multiply(this.z).subtract(this.y.multiply(other.z)).mod(this.ec.getP());
if (!u.equals(BigInteger.ZERO)) {
return false;
}
// v = X2 * Z1 - X1 * Z2
v = other.x.multiply(this.z).subtract(this.x.multiply(other.z)).mod(this.ec.getP());
return v.equals(BigInteger.ZERO);
}
public boolean isInfinity() {
if ((this.x == zero) && (this.y == zero)) {
return true;
}
return this.z.equals(BigInteger.ZERO) && !this.y.equals(BigInteger.ZERO);
}
public ECPointArthimetic negate() {
return new ECPointArthimetic(this.ec, this.x, this.y.negate(), this.z);
}
public ECPointArthimetic add(ECPointArthimetic b) {
if (this.isInfinity()) {
return b;
}
if (b.isInfinity()) {
return this;
}
ECPointArthimetic R = new ECPointArthimetic(this.ec, zero, zero, null);
// u = Y2 * Z1 - Y1 * Z2
BigInteger u = b.y.multiply(this.z).
subtract(this.y.multiply(b.z)).mod(this.ec.getP());
// v = X2 * Z1 - X1 * Z2
BigInteger v = b.x.multiply(this.z).
subtract(this.x.multiply(b.z)).mod(this.ec.getP());
if (BigInteger.ZERO.equals(v)) {
if (BigInteger.ZERO.equals(u)) {
return this.twice(); // this == b, so double
}
infinity = true; // this = -b, so infinity
return R;
}
BigInteger THREE = new BigInteger("3");
BigInteger x1 = this.x;
BigInteger y1 = this.y;
BigInteger x2 = b.x;
BigInteger y2 = b.y;
BigInteger v2 = v.pow(2);
BigInteger v3 = v2.multiply(v);
BigInteger x1v2 = x1.multiply(v2);
BigInteger zu2 = u.pow(2).multiply(this.z);
// x3 = v * (z2 * (z1 * u^2 - 2 * x1 * v^2) - v^3)
BigInteger x3 = zu2.subtract(x1v2.shiftLeft(1)).multiply(b.z).
subtract(v3).multiply(v).mod(this.ec.getP());
// y3 = z2 * (3 * x1 * u * v^2 - y1 * v^3 - z1 * u^3) + u * v^3
BigInteger y3 = x1v2.multiply(THREE).multiply(u).
subtract(y1.multiply(v3)).subtract(zu2.multiply(u)).
multiply(b.z).add(u.multiply(v3)).mod(this.ec.getP());
// z3 = v^3 * z1 * z2
BigInteger z3 = v3.multiply(this.z).multiply(b.z).mod(this.ec.getP());
return new ECPointArthimetic(this.ec, x3, y3, z3);
}
public ECPointArthimetic twice() {
if (this.isInfinity()) {
return this;
}
ECPointArthimetic R = new ECPointArthimetic(this.ec, zero, zero, null);
if (this.y.signum() == 0) {
infinity = true;
return R;
}
BigInteger THREE = new BigInteger("3");
BigInteger x1 = this.x;
BigInteger y1 = this.y;
BigInteger y1z1 = y1.multiply(this.z);
BigInteger y1sqz1 = y1z1.multiply(y1).mod(this.ec.getP());
BigInteger a = this.ec.getA();
// w = 3 * x1^2 + a * z1^2
BigInteger w = x1.pow(2).multiply(THREE);
if (!BigInteger.ZERO.equals(a)) {
w = w.add(this.z.pow(2).multiply(a));
}
w = w.mod(this.ec.getP());
// x3 = 2 * y1 * z1 * (w^2 - 8 * x1 * y1^2 * z1)
BigInteger x3 = w.pow(2).subtract(x1.shiftLeft(3).multiply(y1sqz1)).
shiftLeft(1).multiply(y1z1).mod(this.ec.getP());
// y3 = 4 * y1^2 * z1 * (3 * w * x1 - 2 * y1^2 * z1) - w^3
BigInteger y3 = (w.multiply(THREE).multiply(x1).subtract(y1sqz1.shiftLeft(1))).
shiftLeft(2).multiply(y1sqz1).subtract(w.pow(2).multiply(w)).mod(this.ec.getP());
// z3 = 8 * (y1 * z1)^3
BigInteger z3 = y1z1.pow(2).multiply(y1z1).shiftLeft(3).mod(this.ec.getP());
return new ECPointArthimetic(this.ec, x3, y3, z3);
}
public ECPointArthimetic multiply(BigInteger k) {
if (this.isInfinity()) {
return this;
}
ECPointArthimetic R = new ECPointArthimetic(this.ec, zero, zero, null);
if (k.signum() == 0) {
infinity = true;
return R;
}
BigInteger e = k;
BigInteger h = e.multiply(new BigInteger("3"));
ECPointArthimetic neg = this.negate();
R = this;
int i;
for (i = h.bitLength() - 2; i > 0; --i) {
R = R.twice();
boolean hBit = h.testBit(i);
boolean eBit = e.testBit(i);
if (hBit != eBit) {
R = R.add(hBit ? this : neg);
}
}
return R;
}
public ECPointArthimetic implShamirsTrick( BigInteger k,
ECPointArthimetic Q, BigInteger l){
int m = Math.max(k.bitLength(), l.bitLength());
ECPointArthimetic Z = this.add(Q);
ECPointArthimetic R = new ECPointArthimetic(ec,zero,zero,null);
for (int i = m - 1; i >= 0; --i){
R = R.twice();
if (k.testBit(i)){
if (l.testBit(i)){
R = R.add(Z);
}else{
R = R.add(this);
}
}else{
if (l.testBit(i)){
R = R.add(Q);
}
}
}
return R;
}
}
这是我使用的曲线:
package NISTCurves;
import ecc.*;
import java.math.BigInteger;
public class P192 implements ECDomainParameters {
String p192X = "188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012";
String p192Y = "07192b95ffc8da78631011ed6b24cdd573f977a11e794811";
String p192B = "64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1";
String p192P = "6277101735386680763835789423207666416083908700390324961279";
String p192Order = "6277101735386680763835789423176059013767194773182842284081";
String p192A = "-3";
BigInteger p = new BigInteger(p192P, 16);
EllipticCurve ec =
new EllipticCurve(p,
new BigInteger(p192A).mod(p),
new BigInteger(p192B, 16));
ECPointArthimetic G = new ECPointArthimetic(ec, new BigInteger(p192X,16),
new BigInteger(p192Y,16),null);
BigInteger order = new BigInteger(p192Order, 16);
@Override
public BigInteger getP() {
return p;
}
@Override
public EllipticCurve getECCurve() {
return ec;
}
@Override
public BigInteger getOrder() {
return order;
}
@Override
public ECPointArthimetic getGenerator() {
return G;
}
}
椭圆曲线域参数规范
package NISTCurves;
import ecc.ECPointArthimetic;
import ecc.EllipticCurve;
import java.math.BigInteger;
public interface ECDomainParameters {
public BigInteger getP();
public ECPointArthimetic getGenerator();
public EllipticCurve getECCurve();
public BigInteger getOrder();
}
椭圆曲线数字签名算法实现在这里。在这段代码中有 main 函数,所以用它来测试异常。
package ecc;
import NISTCurves.ECDomainParameters;
import NISTCurves.P192;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.math.BigInteger;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
/**
*
* @author Gere
*/
public class ECDSA {
private BigInteger r, s;
ECDomainParameters param;
private PrivateKey prvKey;
private PublicKey pubKey;
BigInteger zero = BigInteger.ZERO;
private BigInteger one = BigInteger.ONE;
private MessageDigest sha;
public ECDSA() {
try {
sha = MessageDigest.getInstance("SHA-512");
} catch (NoSuchAlgorithmException ex) {
ex.printStackTrace();
}
}
public void initSign(PrivateKey prvKey) {
this.prvKey = prvKey;
param = prvKey.getParam();
}
public void initVerify(PublicKey pubKey) {
this.pubKey = pubKey;
param = pubKey.getParam();
}
public void update(byte[] byteMsg) {
sha.update(byteMsg);
}
public byte[] sign() throws FileNotFoundException, IOException {
BigInteger c = new BigInteger(
param.getP().bitLength() + 64, Rand.sr);
BigInteger k = c.mod(param.getOrder().subtract(one)).add(one);
while (!(k.gcd(param.getOrder()).compareTo(one) == 0)) {
c = new BigInteger(param.getP().bitLength() + 64, Rand.sr);
k = c.mod(param.getOrder().subtract(one)).add(one);
}
BigInteger kinv = k.modInverse(param.getOrder());
ECPointArthimetic p = param.getGenerator().multiply(k);
if (p.getX().equals(zero)) {
return sign();
}
BigInteger hash = new BigInteger(sha.digest());
BigInteger r = p.getX().mod(param.getOrder());
BigInteger s = (kinv.multiply((hash.add((prvKey.getPrivateKey()
.multiply(r)))))).mod(param.getOrder());
if (s.compareTo(zero) == 0) {
return sign();
}
System.out.println("r at sign: " + r);
System.out.println("s at sign: " + s);
byte[] rArr = toUnsignedByteArray(r);
byte[] sArr = toUnsignedByteArray(s);
int nLength = (param.getOrder().bitLength() + 7) / 8;
byte[] res = new byte[2 * nLength];
System.arraycopy(rArr, 0, res, nLength - rArr.length, rArr.length);
System.arraycopy(sArr, 0, res, 2 * nLength - sArr.length,
sArr.length);
return res;
}
public boolean verify(byte[] res) {
int nLength = (param.getOrder().bitLength() + 7) / 8;
byte[] rArr = new byte[nLength];
System.arraycopy(res, 0, rArr, 0, nLength);
r = new BigInteger(rArr);
byte[] sArr = new byte[nLength];
System.arraycopy(res, nLength, sArr, 0, nLength);
s = new BigInteger(sArr);
System.out.println("r at verify: " + r);
System.out.println("s at verify: " + s);
BigInteger w, u1, u2, v;
// r in the range [1,n-1]
if (r.compareTo(one) < 0 || r.compareTo(param.getOrder()) >= 0) {
return false;
}
// s in the range [1,n-1]
if (s.compareTo(one) < 0 || s.compareTo(param.getOrder()) >= 0) {
return false;
}
w = s.modInverse(param.getOrder());
BigInteger hash = new BigInteger(sha.digest());
u1 = hash.multiply(w);
u2 = r.multiply(w);
ECPointArthimetic G = param.getGenerator();
ECPointArthimetic Q = pubKey.getPublicKey();
// u1G + u2Q
ECPointArthimetic temp = G.implShamirsTrick(u1, Q, u2);
v = temp.getX();
v = v.mod(param.getOrder());
return v.equals(r);
}
byte[] toUnsignedByteArray(BigInteger bi) {
byte[] ba = bi.toByteArray();
if (ba[0] != 0) {
return ba;
} else {
byte[] ba2 = new byte[ba.length - 1];
System.arraycopy(ba, 1, ba2, 0, ba.length - 1);
return ba2;
}
}
public static void main(String[] args) {
byte[] msg = "Hello".getBytes();
byte[] sig = null;
ECDomainParameters param = new P192();
PrivateKey prvObj = new PrivateKey(param);
PublicKey pubObj = new PublicKey(prvObj);
ECDSA ecdsa = new ECDSA();
ecdsa.initSign(prvObj);
ecdsa.update(msg);
try {
sig = ecdsa.sign();
} catch (FileNotFoundException ex) {
System.out.println(ex.getMessage());
} catch (IOException ex) {
System.out.println(ex.getMessage());
}
ecdsa.initVerify(pubObj);
ecdsa.update(msg);
if (ecdsa.verify(sig)) {
System.out.println("valid");
} else {
System.out.println("invalid");
}
}
}
这里 PrivateKey 类
package ecc;
import NISTCurves.ECDomainParameters;
import java.math.BigInteger;
import java.security.SecureRandom;
/**
*
* @author Gere
*/
public class PrivateKey {
private BigInteger d;
private ECDomainParameters param;
private BigInteger one = BigInteger.ONE;
private BigInteger zero;
private PublicKey pubKey;
public PrivateKey(ECDomainParameters param) {
this.param = param;
BigInteger c = new BigInteger(param.getOrder().bitLength() + 64,
new SecureRandom());
BigInteger n1 = param.getOrder().subtract(one);
d = c.mod(n1).add(one);
pubKey = new PublicKey(this);
}
public BigInteger getPrivateKey() {
return d;
}
public ECDomainParameters getParam() {
return param;
}
}
公钥类
package ecc;
import NISTCurves.ECDomainParameters;
/**
*
* @author Gere
*/
public class PublicKey {
private ECDomainParameters param;
private ECPointArthimetic Q;
public PublicKey(PrivateKey privObj) {
param = privObj.getParam();
Q = param.getGenerator().multiply(privObj.getPrivateKey());
}
public ECDomainParameters getParam() {
return param;
}
public ECPointArthimetic getPublicKey() {
return Q;
}
}
椭圆曲线
package ecc;
import java.math.BigInteger;
/**
*
* @author Gere
*/
public class EllipticCurve {
private BigInteger a;
private BigInteger b;
private BigInteger p;
public EllipticCurve(BigInteger a, BigInteger b, BigInteger p) {
this.a = a;
this.b = b;
this.p = p;
}
public BigInteger getA() {
return a;
}
public BigInteger getB() {
return b;
}
public BigInteger getP() {
return p;
}
}
兰德级
package ecc;
import java.security.SecureRandom;
/**
*
* @author Gere
*/
public class Rand {
public static final SecureRandom sr = new SecureRandom();
}
椭圆曲线界面
package ecc;
import java.math.BigInteger;
public interface ECConstants{
public static final BigInteger zero = BigInteger.valueOf(0);
public static final BigInteger one = BigInteger.valueOf(1);
public static final BigInteger two = BigInteger.valueOf(2);
public static final BigInteger three = BigInteger.valueOf(3);
public static final BigInteger four= BigInteger.valueOf(4);
}