2 * Copyright (c) 2017 Thomas Pornin <pornin@bolet.org>
4 * Permission is hereby granted, free of charge, to any person obtaining
5 * a copy of this software and associated documentation files (the
6 * "Software"), to deal in the Software without restriction, including
7 * without limitation the rights to use, copy, modify, merge, publish,
8 * distribute, sublicense, and/or sell copies of the Software, and to
9 * permit persons to whom the Software is furnished to do so, subject to
10 * the following conditions:
12 * The above copyright notice and this permission notice shall be
13 * included in all copies or substantial portions of the Software.
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
16 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
17 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
18 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
19 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
20 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
21 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
30 * An implementation of MutableECPoint for curves in a prime field.
31 * Jacobian coordinates are used.
34 internal class MutableECPointPrime : MutableECPoint {
37 * Internal representation:
40 * For the point at infinity, Z == 0.
42 * When 'affine' is true (0xFFFFFFFF), then mx and my are in
43 * normal representation, and mz is either 0 (point at infinity)
44 * or 1 (otherwise). When 'affine' is false (0x00000000), then
45 * mx, my and mz are in Montgomery representation.
47 * Note that in affine coordinates, the point at infinity admits
48 * several equivalent representations. In non-affine
49 * coordinates, all points have several equivalent
56 ModInt mt1, mt2, mt3, mt4, mt5;
57 ModInt ms1, ms2, ms3, ms4, ms5, ms6;
60 * Create a new instance. It is initialized to the point at
63 internal MutableECPointPrime(ECCurvePrime curve)
83 internal override ECCurve Curve {
89 internal override uint IsInfinityCT {
95 internal override void Normalize()
100 internal override byte[] Encode(bool compressed)
107 byte[] enc = new byte[curve.EncodedLengthCompressed];
108 enc[0] = (byte)(0x02 + my.GetLSB());
109 mx.Encode(enc, 1, enc.Length - 1);
112 byte[] enc = new byte[curve.EncodedLength];
113 int flen = (enc.Length - 1) >> 1;
115 mx.Encode(enc, 1, flen);
116 my.Encode(enc, 1 + flen, flen);
121 internal override uint Encode(byte[] dst, bool compressed)
125 int len = curve.EncodedLengthCompressed;
126 if (dst.Length != len) {
127 throw new CryptoException(
128 "invalid output length");
130 dst[0] = (byte)(0x02 + my.GetLSB());
131 mx.Encode(dst, 1, len - 1);
133 int len = curve.EncodedLength;
134 if (dst.Length != len) {
135 throw new CryptoException(
136 "invalid output length");
138 int flen = (len - 1) >> 1;
140 mx.Encode(dst, 1, flen);
141 my.Encode(dst, 1 + flen, flen);
143 return ~IsInfinityCT;
146 internal override uint DecodeCT(byte[] enc)
149 * Format (specified in IEEE P1363, annex E):
151 * 0x00 point at infinity
152 * 0x02+b <X> compressed, b = lsb of Y
153 * 0x04 <X> <Y> uncompressed
154 * 0x06+b <X> <Y> uncompressed, b = lsb of Y
156 * Coordinates X and Y are in unsigned big-endian
157 * notation with exactly the length of the modulus.
159 * We want constant-time decoding, up to the encoded
160 * length. This means that the four following situations
161 * can be differentiated:
162 * -- Point is zero (length = 1)
163 * -- Point is compressed (length = 1 + flen)
164 * -- Point is uncompressed or hybrid (length = 1 + 2*flen)
165 * -- Length is neither 1, 1+flen or 1+2*flen.
168 int flen = curve.flen;
169 uint good = 0xFFFFFFFF;
170 if (enc.Length == 1) {
172 * 1-byte encoding is point at infinity; the
173 * byte shall have value 0.
176 good &= ~(uint)((z | -z) >> 31);
178 } else if (enc.Length == 1 + flen) {
180 * Compressed encoding. Leading byte is 0x02 or
183 int z = (enc[0] & 0xFE) - 0x02;
184 good &= ~(uint)((z | -z) >> 31);
185 uint lsbValue = (uint)(enc[0] & 1);
186 good &= mx.Decode(enc, 1, flen);
188 if (curve.pMod4 == 3) {
189 good &= my.SqrtBlum();
192 * Square roots modulo a non-Blum prime
193 * are a bit more complex. We do not
194 * support them yet (TODO).
200 * Adjust Y depending on LSB.
204 uint dn = (uint)-(int)(my.GetLSB() ^ lsbValue);
205 my.CondCopy(mt1, dn);
208 * A corner case: LSB adjustment works only if
209 * Y != 0. If Y is 0 and requested LSB is 1,
210 * then the decoding fails. Note that this case
211 * cannot happen with usual prime curves, because
212 * they have a prime order, implying that there is
213 * no valid point such that Y = 0 (that would be
214 * a point of order 2).
216 good &= ~(uint)-(int)(my.GetLSB() ^ lsbValue);
219 } else if (enc.Length == 1 + (flen << 1)) {
221 * Uncompressed or hybrid. Leading byte is either
222 * 0x04, 0x06 or 0x07. We verify that the X and
223 * Y coordinates fulfill the curve equation.
226 int z = (fb & 0xFC) - 0x04;
227 good &= ~(uint)((z | -z) >> 31);
229 good &= (uint)((z | -z) >> 31);
230 good &= mx.Decode(enc, 1, flen);
234 good &= my.Decode(enc, 1 + flen, flen);
237 good &= mt1.EqCT(mt2);
240 * We must check the LSB for hybrid encoding.
241 * The check fails if the encoding is marked as
242 * hybrid AND the LSB does not match.
244 int lm = (fb >> 1) & ((int)my.GetLSB() ^ fb) & 1;
253 * If decoding failed, then we force the value to 0.
254 * Otherwise, we got a value. Either way, this uses
255 * affine coordinates.
257 mx.CondCopy(curve.mp, ~good);
258 my.CondCopy(curve.mp, ~good);
259 mz.CondCopy(curve.mp, ~good);
264 internal override byte[] X {
271 internal override byte[] Y {
278 internal override MutableECPoint Dup()
280 MutableECPointPrime Q = new MutableECPointPrime(curve);
285 internal void Set(byte[] X, byte[] Y, bool check)
296 internal void Set(ModInt X, ModInt Y, bool check)
309 curve.RebuildY2(mx, mt1, mt2);
314 throw new CryptoException(
315 "Point is not on the curve");
319 internal override void SetZero()
327 internal override void Set(MutableECPoint Q)
329 MutableECPointPrime R = SameCurve(Q);
336 internal override void Set(MutableECPoint Q, uint ctl)
338 MutableECPointPrime R = SameCurve(Q);
339 mx.CondCopy(R.mx, ctl);
340 my.CondCopy(R.my, ctl);
341 mz.CondCopy(R.mz, ctl);
342 affine ^= ctl & (affine ^ R.affine);
345 internal override void SetMux(uint ctl,
346 MutableECPoint P1, MutableECPoint P2)
348 SetMuxInner(ctl, SameCurve(P1), SameCurve(P2));
351 void SetMuxInner(uint ctl,
352 MutableECPointPrime P1, MutableECPointPrime P2)
354 mx.CopyMux(ctl, P1.mx, P2.mx);
355 my.CopyMux(ctl, P1.my, P2.my);
356 mz.CopyMux(ctl, P1.mz, P2.mz);
357 affine = P2.affine ^ (ctl & (P1.affine ^ P2.affine));
360 internal override void DoubleCT()
369 * Y' = M*(S - X') - 8*Y^4
372 * These formulas also happen to work properly (with our
373 * chosen representation) when the source point has
374 * order 2 (Y = 0 implies Z' = 0) and when the source
375 * point is already the point at infinity (Z = 0 implies
378 * When a = -3, the value of M can be computed with the
379 * more efficient formula:
380 * M = 3*(X+Z^2)*(X-Z^2)
394 * Set t2 = X-Z^2 and then t1 = X+Z^2.
401 * Set t1 = 3*(X+Z^2)*(X-Z^2).
423 mt2.MontyMul(curve.ma);
426 * Set t1 = 3*X^2 + a*Z^4.
432 * Compute S = 4*X*Y^2 in t2. We also save 2*Y^2 in mt3.
442 * Compute X' = M^2 - 2*S.
450 * Compute Z' = 2*Y*Z.
456 * Compute Y' = M*(S - X') - 8*Y^4. We already have
467 internal override uint AddCT(MutableECPoint Q)
469 MutableECPointPrime P2 = SameCurve(Q);
471 if (P2.affine != 0) {
477 ms6.SetMonty(~ms6.IsZeroCT);
478 return AddCTInner(ms4, ms5, ms6, true);
480 return AddCTInner(P2.mx, P2.my, P2.mz, false);
485 * Inner function for addition. The Jacobian coordinates for
486 * the operand are provided in Montogomery representation. If
487 * p2affine is true, then it is guaranteed that p2z is 1
488 * (converted to Montogomery).
490 uint AddCTInner(ModInt p2x, ModInt p2y, ModInt p2z, bool p2affine)
493 * In this comment, the two operands are called P1 and
494 * P2. P1 is this instance; P2 is the operand. Coordinates
495 * of P1 are (X1,Y1,Z1). Coordinates of P2 are (X2,Y2,Z2).
504 * X3 = R^2 - H^3 - 2*U1*H^2
505 * Y3 = R*(U1*H^2 - X3) - S1*H^3
508 * If both P1 and P2 are 0, then the formulas yield 0,
509 * which is fine. If one of P1 and P2 is 0 (but not both),
510 * then we get 0 as result, which is wrong and must be
513 * If U1 == U2 and S1 == S2 then this means that either
514 * P1 or P2 is 0 (or both), or P1 == P2. In the latter
515 * case, the formulas are wrong and we must report
518 * If U1 == U2 and S1 != S2 then P1 + P2 = 0. We get H = 0,
519 * which implies that we obtain the point at infinity,
523 uint P1IsZero = mz.IsZeroCT;
524 uint P2IsZero = p2z.IsZeroCT;
529 * Save this value, in case the operand turns out to
530 * be the point at infinity.
537 * Compute U1 = X1*Z2^2 in t1, and S1 = Y1*Z2^3 in t3.
550 //PrintMR(" u1 = x1*z2^2", mt1);
551 //PrintMR(" s1 = y1*z2^3", mt3);
554 * Compute U2 = X2*Z1^2 in t2, and S2 = Y2*Z1^3 in t4.
562 //PrintMR(" u2 = x2*z1^2", mt2);
563 //PrintMR(" s2 = y2*z1^3", mt4);
566 * Compute H = U2 - U1 in t2, and R = S2 - S1 in t4.
570 //PrintMR(" h = u2-u1", mt2);
571 //PrintMR(" r = s2-s1", mt4);
574 * If both H and R are 0, then we may have a problem
575 * (either P1 == P2, or P1 == 0, or P2 == 0).
577 uint formProb = mt2.IsZeroCT & mt4.IsZeroCT;
580 * Compute U1*H^2 in t1 and H^3 in t5.
586 //PrintMR(" u1*h^2", mt1);
587 //PrintMR(" h^3", mt5);
590 * Compute X3 = R^2 - H^3 - 2*U1*H^2.
597 //PrintMR(" x3 = r^2-h^3-2*u1*h^2", mx);
600 * Compute Y3 = R*(U1*H^2 - X3) - S1*H^3.
607 //PrintMR(" y3 = r*(u1*h^2-x3)-s1*h^3", my);
610 * Compute Z3 = H*Z1*Z2.
616 //PrintMR(" z3 = h*z1*z2", mz);
619 * Fixup: handle the cases where P1 = 0 or P2 = 0.
621 mx.CondCopy(ms1, P2IsZero);
622 my.CondCopy(ms2, P2IsZero);
623 mz.CondCopy(ms3, P2IsZero);
624 mx.CondCopy(p2x, P1IsZero);
625 my.CondCopy(p2y, P1IsZero);
626 mz.CondCopy(p2z, P1IsZero);
629 * Report failure when P1 == P2, except when one of
630 * the points was zero (or both) because that case
631 * was properly handled.
633 return (~formProb) | P1IsZero | P2IsZero;
636 internal override void NegCT()
641 internal override uint MulSpecCT(byte[] n)
643 uint good = 0xFFFFFFFF;
646 * Create and populate window.
648 * If this instance is 0, then we only add 0 to 0 and
649 * double 0, for which DoubleCT() and AddCT() work
652 * If this instance (P) is non-zero, then x*P for all
653 * x in the 1..16 range shall be non-zero and distinct,
654 * since the subgroup order is prime and at least 17.
655 * Thus, we never add two equal points together in the
656 * window construction.
658 * We MUST ensure that all points are in the same
659 * coordinate convention (affine or Jacobian) to ensure
660 * constant-time execution. TODO: measure to see which
661 * is best: all affine or all Jacobian. All affine implies
662 * 14 or 15 extra divisions, but saves a few hundreds of
665 MutableECPointPrime[] w = new MutableECPointPrime[16];
666 w[0] = new MutableECPointPrime(curve);
668 w[1] = new MutableECPointPrime(curve);
671 for (int i = 2; (i + 1) < w.Length; i += 2) {
672 w[i] = new MutableECPointPrime(curve);
675 w[i + 1] = new MutableECPointPrime(curve);
677 good &= w[i + 1].AddCT(this);
681 for (int i = 0; i < w.Length; i ++) {
683 w[i].Print("Win " + i);
686 Console.WriteLine("good = {0}", (int)good);
690 * Set this value to 0. We also set it already to
691 * Jacobian coordinates, since it will be done that
692 * way anyway. This instance will serve as accumulator.
700 * We process the multiplier by 4-bit nibbles, starting
701 * with the most-significant one (the high nibble of the
702 * first byte, since we use big-endian notation).
704 * For each nibble, we perform a constant-time lookup
705 * in the window, to obtain the point to add to the
706 * current value of the accumulator. Thanks to the
707 * conditions on the operands (prime subgroup order and
708 * so on), all the additions below must work.
710 MutableECPointPrime t = new MutableECPointPrime(curve);
711 for (int i = (n.Length << 1) - 1; i >= 0; i --) {
712 int b = n[n.Length - 1 - (i >> 1)];
713 int j = (b >> ((i & 1) << 2)) & 0x0F;
714 for (int k = 0; k < 16; k ++) {
715 t.Set(w[k], ~(uint)(((j - k) | (k - j)) >> 31));
729 internal override uint EqCT(MutableECPoint Q)
731 MutableECPointPrime R = SameCurve(Q);
738 return EqCTMixed(R, this);
740 } else if (R.affine != 0) {
741 return EqCTMixed(this, R);
745 * Both points are in Jacobian coordinates.
746 * If Z1 and Z2 are non-zero, then equality is
747 * achieved if and only if both following equations
749 * X1*(Z2^2) = X2*(Z1^2)
750 * Y1*(Z2^3) = Y2*(Z1^3)
751 * If Z1 or Z2 is zero, then equality is achieved
752 * if and only if both are zero.
762 uint r = mt3.EqCT(mt4);
770 uint z1z = mz.IsZeroCT;
771 uint z2z = R.mz.IsZeroCT;
772 return (r & ~(z1z | z2z)) ^ (z1z & z2z);
776 * Mixed comparison: P1 is in Jacobian coordinates, P2 is in
777 * affine coordinates.
779 uint EqCTMixed(MutableECPointPrime P1, MutableECPointPrime P2)
782 * If either P1 or P2 is infinity, then they are equal
783 * if and only if they both are infinity.
785 * If neither is infinity, then we must check the following:
788 * Beware that X1, Y1 and Z1 are in Montgomery representation,
789 * while X2 and Y2 are not.
797 uint r = mt2.EqCT(mt3);
803 uint z1z = P1.mz.IsZeroCT;
804 uint z2z = P2.mz.IsZeroCT;
805 return (r & ~(z1z | z2z)) ^ (z1z & z2z);
808 MutableECPointPrime SameCurve(MutableECPoint Q)
810 MutableECPointPrime R = Q as MutableECPointPrime;
811 if (R == null || !curve.Equals(R.curve)) {
812 throw new CryptoException("Mixed curves");
818 * Convert to Jabobian coordinates (if not already done).
827 * Since Z = 0 or 1 in affine coordinates, we can
832 mz.SetMonty(~mz.IsZeroCT);
837 * Convert to affine coordinates (if not already done).
846 * Divisions are expensive, so we want to make only one,
847 * not two. This involves some games with Montgomery
850 * A number a in Montgomery representation means that
851 * the value we have is equal to aR. Montgomery
852 * multiplication of a by b yields ab/R (so, if we
853 * apply it to aR and bR, we get abR).
856 /* Save Z*R in mt1. */
859 /* Compute Z^3 in mz. */
864 /* Compute t2 = 1/Z^3. */
867 uint cc = ~mt2.IsZeroCT;
872 /* Compute t2 = 1/Z^2. */
879 * If the point is infinity (division by Z^2 failed),
880 * then set all coordinates to 0. Otherwise, set mz
883 mx.CondCopy(curve.mp, ~cc);
884 my.CondCopy(curve.mp, ~cc);
891 * Compute Y^2 into my, using the value in mx as X. Both values
892 * are in normal (non-Montgomery) representation.
901 mt1.MontyMul(curve.ma);