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 */ 95db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Rootpublic class WTauNafMultiplier extends AbstractECMultiplier 106e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom{ 11d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root // TODO Create WTauNafUtil class and move various functionality into it 12d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root static final String PRECOMP_NAME = "bc_wtnaf"; 13d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 146e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom /** 1579d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro * Multiplies a {@link org.bouncycastle.math.ec.ECPoint.AbstractF2m ECPoint.AbstractF2m} 166e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * by <code>k</code> using the reduced <code>τ</code>-adic NAF (RTNAF) 176e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * method. 1879d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro * @param point The ECPoint.AbstractF2m to multiply. 196e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * @param k The integer by which to multiply <code>k</code>. 206e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * @return <code>p</code> multiplied by <code>k</code>. 216e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom */ 225db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root protected ECPoint multiplyPositive(ECPoint point, BigInteger k) 236e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom { 2479d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro if (!(point instanceof ECPoint.AbstractF2m)) 256e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom { 2679d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro throw new IllegalArgumentException("Only ECPoint.AbstractF2m can be " + 276e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom "used in WTauNafMultiplier"); 286e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom } 296e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom 3079d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro ECPoint.AbstractF2m p = (ECPoint.AbstractF2m)point; 3179d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro ECCurve.AbstractF2m curve = (ECCurve.AbstractF2m)p.getCurve(); 3279d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro int m = curve.getFieldSize(); 336e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom byte a = curve.getA().toBigInteger().byteValue(); 3479d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro byte mu = Tnaf.getMu(a); 356e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom BigInteger[] s = curve.getSi(); 366e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom 376e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom ZTauElement rho = Tnaf.partModReduction(k, m, a, s, mu, (byte)10); 386e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom 39d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root return multiplyWTnaf(p, rho, curve.getPreCompInfo(p, PRECOMP_NAME), a, mu); 406e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom } 416e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom 426e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom /** 4379d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro * Multiplies a {@link org.bouncycastle.math.ec.ECPoint.AbstractF2m ECPoint.AbstractF2m} 446e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * by an element <code>λ</code> of <code><b>Z</b>[τ]</code> using 456e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * the <code>τ</code>-adic NAF (TNAF) method. 4679d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro * @param p The ECPoint.AbstractF2m to multiply. 476e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * @param lambda The element <code>λ</code> of 486e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * <code><b>Z</b>[τ]</code> of which to compute the 496e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * <code>[τ]</code>-adic NAF. 506e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * @return <code>p</code> multiplied by <code>λ</code>. 516e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom */ 5279d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro private ECPoint.AbstractF2m multiplyWTnaf(ECPoint.AbstractF2m p, ZTauElement lambda, 536e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom PreCompInfo preCompInfo, byte a, byte mu) 546e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom { 55d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ZTauElement[] alpha = (a == 0) ? Tnaf.alpha0 : Tnaf.alpha1; 566e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom 576e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom BigInteger tw = Tnaf.getTw(mu, Tnaf.WIDTH); 586e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom 596e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom byte[]u = Tnaf.tauAdicWNaf(mu, lambda, Tnaf.WIDTH, 60d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root BigInteger.valueOf(Tnaf.POW_2_WIDTH), tw, alpha); 616e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom 626e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom return multiplyFromWTnaf(p, u, preCompInfo); 636e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom } 646e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom 656e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom /** 6679d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro * Multiplies a {@link org.bouncycastle.math.ec.ECPoint.AbstractF2m ECPoint.AbstractF2m} 676e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * by an element <code>λ</code> of <code><b>Z</b>[τ]</code> 686e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * using the window <code>τ</code>-adic NAF (TNAF) method, given the 696e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * WTNAF of <code>λ</code>. 7079d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro * @param p The ECPoint.AbstractF2m to multiply. 716e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * @param u The the WTNAF of <code>λ</code>.. 726e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom * @return <code>λ * p</code> 736e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom */ 7479d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro private static ECPoint.AbstractF2m multiplyFromWTnaf(ECPoint.AbstractF2m p, byte[] u, PreCompInfo preCompInfo) 756e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom { 7679d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro ECCurve.AbstractF2m curve = (ECCurve.AbstractF2m)p.getCurve(); 776e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom byte a = curve.getA().toBigInteger().byteValue(); 786e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom 7979d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro ECPoint.AbstractF2m[] pu; 806e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom if ((preCompInfo == null) || !(preCompInfo instanceof WTauNafPreCompInfo)) 816e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom { 826e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom pu = Tnaf.getPreComp(p, a); 83d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 84d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root WTauNafPreCompInfo pre = new WTauNafPreCompInfo(); 85d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root pre.setPreComp(pu); 86d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root curve.setPreCompInfo(p, PRECOMP_NAME, pre); 876e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom } 886e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom else 896e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom { 906e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom pu = ((WTauNafPreCompInfo)preCompInfo).getPreComp(); 916e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom } 926e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom 9379d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro // TODO Include negations in precomp (optionally) and use from here 9479d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro ECPoint.AbstractF2m[] puNeg = new ECPoint.AbstractF2m[pu.length]; 9579d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro for (int i = 0; i < pu.length; ++i) 9679d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro { 9779d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro puNeg[i] = (ECPoint.AbstractF2m)pu[i].negate(); 9879d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro } 9979d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro 10079d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro 1016e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom // q = infinity 10279d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro ECPoint.AbstractF2m q = (ECPoint.AbstractF2m) p.getCurve().getInfinity(); 10379d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro 10479d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro int tauCount = 0; 1056e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom for (int i = u.length - 1; i >= 0; i--) 1066e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom { 10779d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro ++tauCount; 10879d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro int ui = u[i]; 109d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (ui != 0) 1106e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom { 11179d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro q = q.tauPow(tauCount); 11279d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro tauCount = 0; 11379d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro 11479d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro ECPoint x = ui > 0 ? pu[ui >>> 1] : puNeg[(-ui) >>> 1]; 11579d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro q = (ECPoint.AbstractF2m)q.add(x); 1166e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom } 1176e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom } 11879d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro if (tauCount > 0) 11979d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro { 12079d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro q = q.tauPow(tauCount); 12179d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro } 1226e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom return q; 1236e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom } 1246e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom} 125