_ Git - BoarSSL/blob - Crypto/ECCurvePrime.cs

   1 /*
   2  * Copyright (c) 2017 Thomas Pornin <pornin@bolet.org>
   3  *
   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:
  11  *
  12  * The above copyright notice and this permission notice shall be
  13  * included in all copies or substantial portions of the Software.
  14  *
  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
  22  * SOFTWARE.
  23  */
  24
  25 using System;
  26
  27 namespace Crypto {
  28
  29 /*
  30  * Implementation for elliptic curves in a prime field.
  31  */
  32
  33 internal class ECCurvePrime : ECCurve {
  34
  35         public override string Name {
  36                 get {
  37                         return name;
  38                 }
  39         }
  40
  41         public override ECCurveType CurveType {
  42                 get {
  43                         return ECCurveType.Prime;
  44                 }
  45         }
  46
  47         public override int EncodedLength {
  48                 get {
  49                         return 1 + (flen << 1);
  50                 }
  51         }
  52
  53         public override int EncodedLengthCompressed {
  54                 get {
  55                         return 1 + flen;
  56                 }
  57         }
  58
  59         string name;
  60
  61         /*
  62          * 'mp' always contains 0 modulo p.
  63          * 'ma' contains a.
  64          * 'mb' contains b.
  65          * pMod4 is p modulo 4.
  66          */
  67         internal ModInt mp;
  68         internal ModInt ma;
  69         internal ModInt mb;
  70         internal int pMod4;
  71
  72         /*
  73          * a and b are in unsigned big-endian notation.
  74          * aIsM3 is true when a == -3 modulo p.
  75          */
  76         internal byte[] a;
  77         internal byte[] b;
  78         internal bool aIsM3;
  79
  80         internal byte[] mod;
  81         internal int flen;
  82         byte[] gx;
  83         byte[] gy;
  84         int hashCode;
  85
  86         /*
  87          * Checks enforced by the constructor:
  88          * -- modulus is odd and at least 80-bit long
  89          * -- subgroup order is odd and at least 30-bit long
  90          * -- parameters a[] and b[] are lower than modulus
  91          * -- coordinates gx and gy are lower than modulus
  92          * -- coordinates gx and gy match curve equation
  93          */
  94         internal ECCurvePrime(string name, byte[] mod, byte[] a, byte[] b,
  95                 byte[] gx, byte[] gy, byte[] subgroupOrder, byte[] cofactor)
  96                 : base(subgroupOrder, cofactor)
  97         {
  98                 this.mod = mod = BigInt.NormalizeBE(mod);
  99                 int modLen = BigInt.BitLength(mod);
 100                 if (modLen < 80) {
 101                         throw new CryptoException(
 102                                 "Invalid curve: modulus is too small");
 103                 }
 104                 if ((mod[mod.Length - 1] & 0x01) == 0) {
 105                         throw new CryptoException(
 106                                 "Invalid curve: modulus is even");
 107                 }
 108                 int sgLen = BigInt.BitLength(subgroupOrder);
 109                 if (sgLen < 30) {
 110                         throw new CryptoException(
 111                                 "Invalid curve: subgroup is too small");
 112                 }
 113                 if ((subgroupOrder[subgroupOrder.Length - 1] & 0x01) == 0) {
 114                         throw new CryptoException(
 115                                 "Invalid curve: subgroup order is even");
 116                 }
 117
 118                 mp = new ModInt(mod);
 119                 flen = (modLen + 7) >> 3;
 120                 pMod4 = mod[mod.Length - 1] & 3;
 121
 122                 this.a = a = BigInt.NormalizeBE(a);
 123                 this.b = b = BigInt.NormalizeBE(b);
 124                 if (BigInt.CompareCT(a, mod) >= 0
 125                         || BigInt.CompareCT(b, mod) >= 0)
 126                 {
 127                         throw new CryptoException(
 128                                 "Invalid curve: out-of-range parameter");
 129                 }
 130                 ma = mp.Dup();
 131                 ma.Decode(a);
 132                 ma.Add(3);
 133                 aIsM3 = ma.IsZero;
 134                 ma.Sub(3);
 135                 mb = mp.Dup();
 136                 mb.Decode(b);
 137
 138                 this.gx = gx = BigInt.NormalizeBE(gx);
 139                 this.gy = gy = BigInt.NormalizeBE(gy);
 140                 if (BigInt.CompareCT(gx, mod) >= 0
 141                         || BigInt.CompareCT(gy, mod) >= 0)
 142                 {
 143                         throw new CryptoException(
 144                                 "Invalid curve: out-of-range coordinates");
 145                 }
 146                 MutableECPointPrime G = new MutableECPointPrime(this);
 147                 G.Set(gx, gy, true);
 148
 149                 hashCode = (int)(BigInt.HashInt(mod)
 150                         ^ BigInt.HashInt(a) ^ BigInt.HashInt(b)
 151                         ^ BigInt.HashInt(gx) ^ BigInt.HashInt(gy));
 152
 153                 if (name == null) {
 154                         name = string.Format("generic prime {0}/{1}",
 155                                 modLen, sgLen);
 156                 }
 157                 this.name = name;
 158         }
 159
 160         /*
 161          * Extra checks:
 162          * -- modulus is prime
 163          * -- subgroup order is prime
 164          * -- generator indeed generates subgroup
 165          */
 166         public override void CheckValid()
 167         {
 168                 /*
 169                  * Check that the modulus is prime.
 170                  */
 171                 if (!BigInt.IsPrime(mod)) {
 172                         throw new CryptoException(
 173                                 "Invalid curve: modulus is not prime");
 174                 }
 175
 176                 /*
 177                  * Check that the subgroup order is prime.
 178                  */
 179                 if (!BigInt.IsPrime(SubgroupOrder)) {
 180                         throw new CryptoException(
 181                                 "Invalid curve: subgroup order is not prime");
 182                 }
 183
 184                 /*
 185                  * Check that the G point is indeed a generator of the
 186                  * subgroup. Note that since it has explicit coordinates,
 187                  * it cannot be the point at infinity; it suffices to
 188                  * verify that, when multiplied by the subgroup order,
 189                  * it yields infinity.
 190                  */
 191                 MutableECPointPrime G = new MutableECPointPrime(this);
 192                 G.Set(gx, gy, false);
 193                 if (G.MulSpecCT(SubgroupOrder) == 0 || !G.IsInfinity) {
 194                         throw new CryptoException(
 195                                 "Invalid curve: generator does not match"
 196                                 + " subgroup order");
 197                 }
 198
 199                 /*
 200                  * TODO: check cofactor.
 201                  *
 202                  * If the cofactor is small, then we can simply compute
 203                  * the complete curve order by multiplying the cofactor
 204                  * with the subgroup order, and see whether it is in the
 205                  * proper range with regards to the field cardinal (by
 206                  * using Hasse's theorem). However, if the cofactor is
 207                  * larger than the subgroup order, then detecting a
 208                  * wrong cofactor value is a bit more complex. We could
 209                  * generate a few random points and multiply them by
 210                  * the computed order, but this may be expensive.
 211                  */
 212         }
 213
 214         public override int GetXoff(out int len)
 215         {
 216                 len = flen;
 217                 return 1;
 218         }
 219
 220         /* obsolete
 221         public override uint Mul(byte[] G, byte[] x, byte[] D, bool compressed)
 222         {
 223                 MutableECPointPrime P = new MutableECPointPrime(this);
 224                 uint good = P.DecodeCT(G);
 225                 good &= ~P.IsInfinityCT;
 226                 good &= P.MulSpecCT(x);
 227                 good &= P.Encode(D, compressed);
 228                 return good;
 229         }
 230
 231         public override uint MulAdd(byte[] A, byte[] x, byte[] B, byte[] y,
 232                 byte[] D, bool compressed)
 233         {
 234                 MutableECPointPrime P = new MutableECPointPrime(this);
 235                 MutableECPointPrime Q = new MutableECPointPrime(this);
 236
 237                 uint good = P.DecodeCT(A);
 238                 good &= Q.DecodeCT(B);
 239                 good &= ~P.IsInfinityCT & ~Q.IsInfinityCT;
 240
 241                 good &= P.MulSpecCT(x);
 242                 good &= Q.MulSpecCT(y);
 243                 good &= ~P.IsInfinityCT & ~Q.IsInfinityCT;
 244
 245                 uint z = P.AddCT(Q);
 246                 Q.DoubleCT();
 247                 P.Set(Q, ~z);
 248
 249                 good &= P.Encode(D, compressed);
 250                 return good;
 251         }
 252         */
 253
 254         public override byte[] MakeRandomSecret()
 255         {
 256                 /*
 257                  * We force the top bits to 0 to guarantee that the value
 258                  * is less than the subgroup order; and we force the
 259                  * least significant bit to 0 so that the value is not null.
 260                  * This is good enough for ECDH.
 261                  */
 262                 byte[] q = SubgroupOrder;
 263                 byte[] x = new byte[q.Length];
 264                 int mask = 0xFF;
 265                 while (mask >= q[0]) {
 266                         mask >>= 1;
 267                 }
 268                 RNG.GetBytes(x);
 269                 x[0] &= (byte)mask;
 270                 x[x.Length - 1] |= (byte)0x01;
 271                 return x;
 272         }
 273
 274         internal override MutableECPoint MakeZero()
 275         {
 276                 return new MutableECPointPrime(this);
 277         }
 278
 279         internal override MutableECPoint MakeGenerator()
 280         {
 281                 /*
 282                  * We do not have to check the generator, since
 283                  * it was already done in the constructor.
 284                  */
 285                 MutableECPointPrime G = new MutableECPointPrime(this);
 286                 G.Set(gx, gy, false);
 287                 return G;
 288         }
 289
 290         internal override MutableECPoint Decode(byte[] enc)
 291         {
 292                 MutableECPointPrime P = new MutableECPointPrime(this);
 293                 P.Decode(enc);
 294                 return P;
 295         }
 296
 297         public override bool Equals(object obj)
 298         {
 299                 return Equals(obj as ECCurvePrime);
 300         }
 301
 302         internal bool Equals(ECCurvePrime curve)
 303         {
 304                 if (this == curve) {
 305                         return true;
 306                 }
 307                 return BigInt.Compare(mod, curve.mod) == 0
 308                         && BigInt.Compare(a, curve.a) == 0
 309                         && BigInt.Compare(b, curve.b) == 0
 310                         && BigInt.Compare(gx, curve.gx) == 0
 311                         && BigInt.Compare(gy, curve.gy) == 0;
 312         }
 313
 314         public override int GetHashCode()
 315         {
 316                 return hashCode;
 317         }
 318
 319         /*
 320          * Given a value X in sx, this method computes X^3+aX+b into sd.
 321          * 'sx' is unmodified. 'st' is modified (it receives a*X).
 322          * The sx, sd and st instances MUST be distinct.
 323          */
 324         internal void RebuildY2(ModInt sx, ModInt sd, ModInt st)
 325         {
 326                 sd.Set(sx);
 327                 sd.ToMonty();
 328                 st.Set(sd);
 329                 sd.MontySquare();
 330                 sd.MontyMul(sx);
 331                 st.MontyMul(ma);
 332                 sd.Add(st);
 333                 sd.Add(mb);
 334         }
 335 }
 336
 337 }