16e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrompackage org.bouncycastle.math.ec; 26e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom 36e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstromimport java.math.BigInteger; 46e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom 56e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom/** 66e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * Class implementing the WTNAF (Window 76e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * <code>τ</code>-adic Non-Adjacent Form) algorithm. 86e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom */ 96e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstromclass WTauNafMultiplier implements ECMultiplier 106e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom{ 116e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom /** 126e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * Multiplies a {@link org.bouncycastle.math.ec.ECPoint.F2m ECPoint.F2m} 136e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * by <code>k</code> using the reduced <code>τ</code>-adic NAF (RTNAF) 146e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * method. 156e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * @param p The ECPoint.F2m to multiply. 166e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * @param k The integer by which to multiply <code>k</code>. 176e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * @return <code>p</code> multiplied by <code>k</code>. 186e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom */ 196e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom public ECPoint multiply(ECPoint point, BigInteger k, PreCompInfo preCompInfo) 206e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom { 216e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom if (!(point instanceof ECPoint.F2m)) 226e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom { 236e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom throw new IllegalArgumentException("Only ECPoint.F2m can be " + 246e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom "used in WTauNafMultiplier"); 256e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom } 266e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom 276e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom ECPoint.F2m p = (ECPoint.F2m)point; 286e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom 296e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom ECCurve.F2m curve = (ECCurve.F2m) p.getCurve(); 306e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom int m = curve.getM(); 316e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom byte a = curve.getA().toBigInteger().byteValue(); 326e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom byte mu = curve.getMu(); 336e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom BigInteger[] s = curve.getSi(); 346e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom 356e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom ZTauElement rho = Tnaf.partModReduction(k, m, a, s, mu, (byte)10); 366e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom 376e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom return multiplyWTnaf(p, rho, preCompInfo, a, mu); 386e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom } 396e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom 406e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom /** 416e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * Multiplies a {@link org.bouncycastle.math.ec.ECPoint.F2m ECPoint.F2m} 426e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * by an element <code>λ</code> of <code><b>Z</b>[τ]</code> using 436e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * the <code>τ</code>-adic NAF (TNAF) method. 446e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * @param p The ECPoint.F2m to multiply. 456e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * @param lambda The element <code>λ</code> of 466e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * <code><b>Z</b>[τ]</code> of which to compute the 476e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * <code>[τ]</code>-adic NAF. 486e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * @return <code>p</code> multiplied by <code>λ</code>. 496e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom */ 506e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom private ECPoint.F2m multiplyWTnaf(ECPoint.F2m p, ZTauElement lambda, 516e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom PreCompInfo preCompInfo, byte a, byte mu) 526e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom { 536e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom ZTauElement[] alpha; 546e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom if (a == 0) 556e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom { 566e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom alpha = Tnaf.alpha0; 576e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom } 586e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom else 596e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom { 606e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom // a == 1 616e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom alpha = Tnaf.alpha1; 626e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom } 636e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom 646e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom BigInteger tw = Tnaf.getTw(mu, Tnaf.WIDTH); 656e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom 666e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom byte[]u = Tnaf.tauAdicWNaf(mu, lambda, Tnaf.WIDTH, 676e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom BigInteger.valueOf(Tnaf.POW_2_WIDTH), tw, alpha); 686e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom 696e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom return multiplyFromWTnaf(p, u, preCompInfo); 706e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom } 716e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom 726e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom /** 736e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * Multiplies a {@link org.bouncycastle.math.ec.ECPoint.F2m ECPoint.F2m} 746e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * by an element <code>λ</code> of <code><b>Z</b>[τ]</code> 756e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * using the window <code>τ</code>-adic NAF (TNAF) method, given the 766e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * WTNAF of <code>λ</code>. 776e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * @param p The ECPoint.F2m to multiply. 786e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * @param u The the WTNAF of <code>λ</code>.. 796e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * @return <code>λ * p</code> 806e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom */ 816e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom private static ECPoint.F2m multiplyFromWTnaf(ECPoint.F2m p, byte[] u, 826e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom PreCompInfo preCompInfo) 836e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom { 846e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom ECCurve.F2m curve = (ECCurve.F2m)p.getCurve(); 856e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom byte a = curve.getA().toBigInteger().byteValue(); 866e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom 876e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom ECPoint.F2m[] pu; 886e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom if ((preCompInfo == null) || !(preCompInfo instanceof WTauNafPreCompInfo)) 896e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom { 906e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom pu = Tnaf.getPreComp(p, a); 916e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom p.setPreCompInfo(new WTauNafPreCompInfo(pu)); 926e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom } 936e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom else 946e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom { 956e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom pu = ((WTauNafPreCompInfo)preCompInfo).getPreComp(); 966e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom } 976e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom 986e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom // q = infinity 996e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom ECPoint.F2m q = (ECPoint.F2m) p.getCurve().getInfinity(); 1006e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom for (int i = u.length - 1; i >= 0; i--) 1016e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom { 1026e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom q = Tnaf.tau(q); 1036e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom if (u[i] != 0) 1046e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom { 1056e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom if (u[i] > 0) 1066e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom { 1076e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom q = q.addSimple(pu[u[i]]); 1086e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom } 1096e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom else 1106e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom { 1116e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom // u[i] < 0 1126e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom q = q.subtractSimple(pu[-u[i]]); 1136e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom } 1146e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom } 1156e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom } 1166e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom 1176e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom return q; 1186e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom } 1196e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom} 120