_ Git - BoarSSL/blob - Crypto/ECDSA.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 using System.IO;
  27
  28 namespace Crypto {
  29
  30 /*
  31  * This class implements the ECDSA signature algorithm. The static methods
  32  * provide access to the algorithm primitives. The hash of the signed data
  33  * must be provided externally.
  34  *
  35  * Signatures may be encoded in either "ASN.1" or "raw" formats; "ASN.1"
  36  * is normally used (e.g. in SSL/TLS) but some protocols and API expect
  37  * the raw format (e.g. PKCS#11 and OpenPGP). An ECDSA signature consists
  38  * in two integers r and s, which are values modulo the subgroup order q.
  39  * In ASN.1 format, the signature is the DER encoding of the ASN.1
  40  * structure:
  41  *
  42  *    ECDSA-signature ::= SEQUENCE {
  43  *            r INTEGER,
  44  *            s INTEGER
  45  *    }
  46  *
  47  * In raw format, the two integers r and s are encoded with unsigned
  48  * big-endian encoding (with the same encoding length) and concatenated.
  49  *
  50  * The Sign() and Verify() methods use the ASN.1 format. The SignRaw()
  51  * and VerifyRaw() use the raw format. The SigRawToAsn1() and SigAsn1ToRaw()
  52  * allow for converting between the two formats.
  53  */
  54
  55 public class ECDSA : DSAUtils {
  56
  57         /*
  58          * Verify an ECDSA signature (ASN.1 format). Returned value is true
  59          * on success. If the signature is invalid, then false is returned.
  60          * Internal exceptions (due to an incorrect public key) are also
  61          * converted to a returned value of false.
  62          *
  63          * There are four methods, depending on the source operands.
  64          */
  65
  66         public static bool Verify(ECPublicKey pk,
  67                 byte[] hash, byte[] sig)
  68         {
  69                 return Verify(pk, hash, 0, hash.Length, sig, 0, sig.Length);
  70         }
  71
  72         public static bool Verify(ECPublicKey pk,
  73                 byte[] hash, int hashOff, int hashLen, byte[] sig)
  74         {
  75                 return Verify(pk, hash, hashOff, hashLen, sig, 0, sig.Length);
  76         }
  77
  78         public static bool Verify(ECPublicKey pk,
  79                 byte[] hash, byte[] sig, int sigOff, int sigLen)
  80         {
  81                 return Verify(pk, hash, 0, hash.Length, sig, sigOff, sigLen);
  82         }
  83
  84         public static bool Verify(ECPublicKey pk,
  85                 byte[] hash, int hashOff, int hashLen,
  86                 byte[] sig, int sigOff, int sigLen)
  87         {
  88                 byte[] raw = SigAsn1ToRaw(sig, sigOff, sigLen);
  89                 if (raw == null) {
  90                         return false;
  91                 }
  92                 return VerifyRaw(pk,
  93                         hash, hashOff, hashLen, raw, 0, raw.Length);
  94         }
  95
  96         /*
  97          * Verify an ECDSA signature (raw format). Returned value is true
  98          * on success. If the signature is invalid, then false is returned.
  99          * Internal exceptions (due to an incorrect public key) are also
 100          * converted to a returned value of false.
 101          *
 102          * There are four methods, depending on the source operands.
 103          */
 104
 105         public static bool VerifyRaw(ECPublicKey pk,
 106                 byte[] hash, byte[] sig)
 107         {
 108                 return VerifyRaw(pk,
 109                         hash, 0, hash.Length, sig, 0, sig.Length);
 110         }
 111
 112         public static bool VerifyRaw(ECPublicKey pk,
 113                 byte[] hash, int hashOff, int hashLen, byte[] sig)
 114         {
 115                 return VerifyRaw(pk,
 116                         hash, hashOff, hashLen, sig, 0, sig.Length);
 117         }
 118
 119         public static bool VerifyRaw(ECPublicKey pk,
 120                 byte[] hash, byte[] sig, int sigOff, int sigLen)
 121         {
 122                 return VerifyRaw(pk,
 123                         hash, 0, hash.Length, sig, sigOff, sigLen);
 124         }
 125
 126         public static bool VerifyRaw(ECPublicKey pk,
 127                 byte[] hash, int hashOff, int hashLen,
 128                 byte[] sig, int sigOff, int sigLen)
 129         {
 130                 try {
 131                         /*
 132                          * Get the curve.
 133                          */
 134                         ECCurve curve = pk.Curve;
 135
 136                         /*
 137                          * Get r and s from signature. This also verifies
 138                          * that they do not exceed the subgroup order.
 139                          */
 140                         if (sigLen == 0 || (sigLen & 1) != 0) {
 141                                 return false;
 142                         }
 143                         int tlen = sigLen >> 1;
 144                         ModInt oneQ = new ModInt(curve.SubgroupOrder);
 145                         oneQ.Set(1);
 146                         ModInt r = oneQ.Dup();
 147                         ModInt s = oneQ.Dup();
 148                         r.Decode(sig, sigOff, tlen);
 149                         s.Decode(sig, sigOff + tlen, tlen);
 150
 151                         /*
 152                          * If either r or s was too large, it got set to
 153                          * zero. We also don't want real zeros.
 154                          */
 155                         if (r.IsZero || s.IsZero) {
 156                                 return false;
 157                         }
 158
 159                         /*
 160                          * Convert the hash value to an integer modulo q.
 161                          * As per FIPS 186-4, if the hash value is larger
 162                          * than q, then we keep the qlen leftmost bits of
 163                          * the hash value.
 164                          */
 165                         int qBitLength = oneQ.ModBitLength;
 166                         int hBitLength = hashLen << 3;
 167                         byte[] hv;
 168                         if (hBitLength <= qBitLength) {
 169                                 hv = new byte[hashLen];
 170                                 Array.Copy(hash, hashOff, hv, 0, hashLen);
 171                         } else {
 172                                 int qlen = (qBitLength + 7) >> 3;
 173                                 hv = new byte[qlen];
 174                                 Array.Copy(hash, hashOff, hv, 0, qlen);
 175                                 int rs = (8 - (qBitLength & 7)) & 7;
 176                                 BigInt.RShift(hv, rs);
 177                         }
 178                         ModInt z = oneQ.Dup();
 179                         z.DecodeReduce(hv);
 180
 181                         /*
 182                          * Apply the verification algorithm:
 183                          *   w = 1/s mod q
 184                          *   u = z*w mod q
 185                          *   v = r*w mod q
 186                          *   T = u*G + v*Pub
 187                          *   test whether T.x mod q == r.
 188                          */
 189                         /*
 190                          * w = 1/s mod q
 191                          */
 192                         ModInt w = s.Dup();
 193                         w.Invert();
 194
 195                         /*
 196                          * u = z*w mod q
 197                          */
 198                         w.ToMonty();
 199                         ModInt u = w.Dup();
 200                         u.MontyMul(z);
 201
 202                         /*
 203                          * v = r*w mod q
 204                          */
 205                         ModInt v = w.Dup();
 206                         v.MontyMul(r);
 207
 208                         /*
 209                          * Compute u*G
 210                          */
 211                         MutableECPoint T = curve.MakeGenerator();
 212                         uint good = T.MulSpecCT(u.Encode());
 213
 214                         /*
 215                          * Compute v*iPub
 216                          */
 217                         MutableECPoint M = pk.iPub.Dup();
 218                         good &= M.MulSpecCT(v.Encode());
 219
 220                         /*
 221                          * Compute T = u*G+v*iPub
 222                          */
 223                         uint nd = T.AddCT(M);
 224                         M.DoubleCT();
 225                         T.Set(M, ~nd);
 226                         good &= ~T.IsInfinityCT;
 227
 228                         /*
 229                          * Get T.x, reduced modulo q.
 230                          * Signature is valid if and only if we get
 231                          * the same value as r (and we did not encounter
 232                          * an error previously).
 233                          */
 234                         s.DecodeReduce(T.X);
 235                         return (good & r.EqCT(s)) != 0;
 236
 237                 } catch (CryptoException) {
 238                         /*
 239                          * Exceptions may occur if the key or signature
 240                          * have invalid values (non invertible, out of
 241                          * range...). Any such occurrence means that the
 242                          * signature is not valid.
 243                          */
 244                         return false;
 245                 }
 246         }
 247
 248         /*
 249          * Compute an ECDSA signature (ASN.1 format). On error (e.g. due
 250          * to an invalid private key), an exception is thrown.
 251          *
 252          * Internally, the process described in RFC 6979 is used to
 253          * compute the per-signature random value 'k'. If 'rfc6979Hash'
 254          * is not null, then a clone of that function is used for that
 255          * process, and signatures are fully deterministic and should
 256          * match RFC 6979 test vectors; if 'rfc6979Hash' is null, then
 257          * the engine uses SHA-256 with additional randomness, resulting
 258          * in randomized signatures. The systematic use of RFC 6979 in
 259          * both cases ensures the safety of the private key even if the
 260          * system RNG is predictible.
 261          *
 262          * There are four methods, depending on the source operands.
 263          */
 264
 265         public static byte[] Sign(ECPrivateKey sk, IDigest rfc6979Hash,
 266                 byte[] hash)
 267         {
 268                 return Sign(sk, rfc6979Hash, hash, 0, hash.Length);
 269         }
 270
 271         public static byte[] Sign(ECPrivateKey sk, IDigest rfc6979Hash,
 272                 byte[] hash, int hashOff, int hashLen)
 273         {
 274                 return SigRawToAsn1(SignRaw(sk, rfc6979Hash,
 275                         hash, hashOff, hashLen));
 276         }
 277
 278         public static int Sign(ECPrivateKey sk, IDigest rfc6979Hash,
 279                 byte[] hash, byte[] outBuf, int outOff)
 280         {
 281                 return Sign(sk, rfc6979Hash,
 282                         hash, 0, hash.Length, outBuf, outOff);
 283         }
 284
 285         public static int Sign(ECPrivateKey sk, IDigest rfc6979Hash,
 286                 byte[] hash, int hashOff, int hashLen,
 287                 byte[] outBuf, int outOff)
 288         {
 289                 byte[] sig = Sign(sk, rfc6979Hash, hash, hashOff, hashLen);
 290                 Array.Copy(sig, 0, outBuf, outOff, sig.Length);
 291                 return sig.Length;
 292         }
 293
 294         /*
 295          * Compute an ECDSA signature (raw format). On error (e.g. due
 296          * to an invalid private key), an exception is thrown.
 297          *
 298          * Internally, the process described in RFC 6979 is used to
 299          * compute the per-signature random value 'k'. If 'rfc6979Hash'
 300          * is not null, then a clone of that function is used for that
 301          * process, and signatures are fully deterministic and should
 302          * match RFC 6979 test vectors; if 'rfc6979Hash' is null, then
 303          * the engine uses SHA-256 with additional randomness, resulting
 304          * in randomized signatures. The systematic use of RFC 6979 in
 305          * both cases ensures the safety of the private key even if the
 306          * system RNG is predictible.
 307          *
 308          * The signature returned by these methods always has length
 309          * exactly twice that of the encoded subgroup order (they are
 310          * not minimalized). Use SigRawMinimalize() to reduce the
 311          * signature size to its minimum length.
 312          *
 313          * There are four methods, depending on the source operands.
 314          */
 315
 316         public static byte[] SignRaw(ECPrivateKey sk, IDigest rfc6979Hash,
 317                 byte[] hash)
 318         {
 319                 return SignRaw(sk, rfc6979Hash, hash, 0, hash.Length);
 320         }
 321
 322         public static int SignRaw(ECPrivateKey sk, IDigest rfc6979Hash,
 323                 byte[] hash, byte[] outBuf, int outOff)
 324         {
 325                 return SignRaw(sk, rfc6979Hash,
 326                         hash, 0, hash.Length, outBuf, outOff);
 327         }
 328
 329         public static int SignRaw(ECPrivateKey sk, IDigest rfc6979Hash,
 330                 byte[] hash, int hashOff, int hashLen,
 331                 byte[] outBuf, int outOff)
 332         {
 333                 byte[] sig = SignRaw(sk, rfc6979Hash, hash, hashOff, hashLen);
 334                 Array.Copy(sig, 0, outBuf, outOff, sig.Length);
 335                 return sig.Length;
 336         }
 337
 338         public static byte[] SignRaw(ECPrivateKey sk, IDigest rfc6979Hash,
 339                 byte[] hash, int hashOff, int hashLen)
 340         {
 341                 ECCurve curve = sk.Curve;
 342                 byte[] q = curve.SubgroupOrder;
 343                 RFC6979 rf = new RFC6979(rfc6979Hash, q, sk.X,
 344                         hash, hashOff, hashLen, rfc6979Hash != null);
 345                 ModInt mh = rf.GetHashMod();
 346                 ModInt mx = mh.Dup();
 347                 mx.Decode(sk.X);
 348
 349                 /*
 350                  * Compute DSA signature. We use a loop to enumerate
 351                  * candidates for k until a proper one is found (it
 352                  * is VERY improbable that we may have to loop).
 353                  */
 354                 ModInt mr = mh.Dup();
 355                 ModInt ms = mh.Dup();
 356                 ModInt mk = mh.Dup();
 357                 byte[] k = new byte[q.Length];
 358                 for (;;) {
 359                         rf.NextK(k);
 360                         MutableECPoint G = curve.MakeGenerator();
 361                         if (G.MulSpecCT(k) == 0) {
 362                                 /*
 363                                  * We may get an error here only if the
 364                                  * curve is invalid (generator does not
 365                                  * produce the expected subgroup).
 366                                  */
 367                                 throw new CryptoException(
 368                                         "Invalid EC private key / curve");
 369                         }
 370                         mr.DecodeReduce(G.X);
 371                         if (mr.IsZero) {
 372                                 continue;
 373                         }
 374                         ms.Set(mx);
 375                         ms.ToMonty();
 376                         ms.MontyMul(mr);
 377                         ms.Add(mh);
 378                         mk.Decode(k);
 379                         mk.Invert();
 380                         ms.ToMonty();
 381                         ms.MontyMul(mk);
 382
 383                         byte[] sig = new byte[q.Length << 1];
 384                         mr.Encode(sig, 0, q.Length);
 385                         ms.Encode(sig, q.Length, q.Length);
 386                         return sig;
 387                 }
 388         }
 389
 390         /*
 391          * Generate a new EC key pair in the specified curve.
 392          */
 393         public static ECPrivateKey Generate(ECCurve curve)
 394         {
 395                 return new ECPrivateKey(curve,
 396                         BigInt.RandIntNZ(curve.SubgroupOrder));
 397         }
 398 }
 399
 400 }