_ Git - BoarSSL/blob - Crypto/DSAUtils.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  * This class contains some utility methods used for DSA and ECDSA.
  31  */
  32
  33 public class DSAUtils {
  34
  35         /*
  36          * Convert an ASN.1 DSA signature to "raw" format. A "raw" signature
  37          * is the concatenation of two unsigned big-endian integers of
  38          * the same length. An ASN.1 signature is a DER-encoded SEQUENCE
  39          * of two INTEGER values. The returned signature will have the
  40          * minimum length that can hold the two signature elements; use
  41          * SigRawNormalize() to adjust that length.
  42          *
  43          * If the source signature is syntaxically invalid (not valid DER),
  44          * then null is returned.
  45          */
  46         public static byte[] SigAsn1ToRaw(byte[] sig)
  47         {
  48                 return SigAsn1ToRaw(sig, 0, sig.Length);
  49         }
  50
  51         public static byte[] SigAsn1ToRaw(byte[] sig, int off, int len)
  52         {
  53                 int lim = off + len;
  54                 if (len <= 2 || sig[off ++] != 0x30) {
  55                         return null;
  56                 }
  57                 int tlen = DecodeLength(sig, ref off, lim);
  58                 if (tlen != (lim - off)) {
  59                         return null;
  60                 }
  61                 int roff, rlen;
  62                 int soff, slen;
  63                 if (!DecodeInteger(sig, ref off, lim, out roff, out rlen)) {
  64                         return null;
  65                 }
  66                 if (!DecodeInteger(sig, ref off, lim, out soff, out slen)) {
  67                         return null;
  68                 }
  69                 if (off != lim) {
  70                         return null;
  71                 }
  72                 int ulen = Math.Max(rlen, slen);
  73                 byte[] raw = new byte[ulen << 1];
  74                 Array.Copy(sig, roff, raw, ulen - rlen, rlen);
  75                 Array.Copy(sig, soff, raw, (ulen << 1) - slen, slen);
  76                 return raw;
  77         }
  78
  79         static int DecodeLength(byte[] buf, ref int off, int lim)
  80         {
  81                 if (off >= lim) {
  82                         return -1;
  83                 }
  84                 int fb = buf[off ++];
  85                 if (fb < 0x80) {
  86                         return fb;
  87                 }
  88                 int elen = fb - 0x80;
  89                 if (elen == 0) {
  90                         return -1;
  91                 }
  92                 int acc = 0;
  93                 while (elen -- > 0) {
  94                         if (off >= lim) {
  95                                 return -1;
  96                         }
  97                         if (acc > 0x7FFFFF) {
  98                                 return -1;
  99                         }
 100                         acc = (acc << 8) + buf[off ++];
 101                 }
 102                 return acc;
 103         }
 104
 105         static bool DecodeInteger(byte[] buf, ref int off, int lim,
 106                 out int voff, out int vlen)
 107         {
 108                 voff = -1;
 109                 vlen = -1;
 110                 if (off >= lim || buf[off ++] != 0x02) {
 111                         return false;
 112                 }
 113                 int len = DecodeLength(buf, ref off, lim);
 114                 if (len <= 0 || len > (lim - off)) {
 115                         return false;
 116                 }
 117                 voff = off;
 118                 vlen = len;
 119                 off += len;
 120                 while (vlen > 1 && buf[voff] == 0x00) {
 121                         voff ++;
 122                         vlen --;
 123                 }
 124                 return true;
 125         }
 126
 127         /*
 128          * Reduce a "raw" signature to its minimal length. The minimal
 129          * length depends on the values of the inner elements; normally,
 130          * that length is equal to twice the length of the encoded
 131          * subgroup order, but it can be shorter by a few bytes
 132          * (occasionally by two bytes; shorter signatures are very
 133          * rare).
 134          *
 135          * If the source signature is null or has an odd length, then
 136          * null is returned. If the source signature already has
 137          * minimal length, then it is returned as is. Otherwise,
 138          * a new array is created with the minimal length, filled,
 139          * and returned.
 140          */
 141         public static byte[] SigRawMinimalize(byte[] sigRaw)
 142         {
 143                 int minLen = GetMinRawLength(sigRaw);
 144                 if (minLen <= 0) {
 145                         return null;
 146                 }
 147                 if (minLen == sigRaw.Length) {
 148                         return sigRaw;
 149                 }
 150                 int m = sigRaw.Length >> 1;
 151                 int lh = minLen >> 1;
 152                 byte[] sig = new byte[lh + lh];
 153                 Array.Copy(sigRaw, m - lh, sig, 0, lh);
 154                 Array.Copy(sigRaw, m + m - lh, sig, lh, lh);
 155                 return sig;
 156         }
 157
 158         /*
 159          * Normalize a "raw" signature to the specified length. If
 160          * the source array already has the right length, then it is
 161          * returned as is. Otherwise, a new array is created with the
 162          * requested length, and filled with the signature elements.
 163          *
 164          * If the source signature is null, or has an odd length, then
 165          * null is returned. If the requested length is not valid (odd
 166          * length) or cannot be achieved (because the signature elements
 167          * are too large), then null is returned.
 168          */
 169         public static byte[] SigRawNormalize(byte[] sigRaw, int len)
 170         {
 171                 int minLen = GetMinRawLength(sigRaw);
 172                 if (minLen <= 0) {
 173                         return null;
 174                 }
 175                 if ((len & 1) != 0) {
 176                         return null;
 177                 }
 178                 int hlen = len >> 1;
 179                 if (sigRaw.Length == len) {
 180                         return sigRaw;
 181                 }
 182                 int m = sigRaw.Length >> 1;
 183                 int lh = minLen >> 1;
 184                 byte[] sig = new byte[len];
 185                 Array.Copy(sigRaw, m - lh, sig, hlen - lh, lh);
 186                 Array.Copy(sigRaw, m + m - lh, sig, len - lh, lh);
 187                 return sig;
 188         }
 189
 190         static int GetMinRawLength(byte[] sig)
 191         {
 192                 if (sig == null || (sig.Length & 1) != 0) {
 193                         return -1;
 194                 }
 195                 int m = sig.Length << 1;
 196                 int lr, ls;
 197                 for (lr = m; lr > 0; lr --) {
 198                         if (sig[m - lr] != 0) {
 199                                 break;
 200                         }
 201                 }
 202                 for (ls = m; ls > 0; ls --) {
 203                         if (sig[m + m - ls] != 0) {
 204                                 break;
 205                         }
 206                 }
 207                 return Math.Max(lr, ls) << 1;
 208         }
 209
 210         /*
 211          * Convert a "raw" DSA signature to ASN.1. A "raw" signature
 212          * is the concatenation of two unsigned big-endian integers of
 213          * the same length. An ASN.1 signature is a DER-encoded SEQUENCE
 214          * of two INTEGER values.
 215          *
 216          * If the source signature is syntaxically invalid (zero length,
 217          * or odd length), then null is returned.
 218          */
 219         public static byte[] SigRawToAsn1(byte[] sig)
 220         {
 221                 return SigRawToAsn1(sig, 0, sig.Length);
 222         }
 223
 224         public static byte[] SigRawToAsn1(byte[] sig, int off, int len)
 225         {
 226                 if (len <= 0 || (len & 1) != 0) {
 227                         return null;
 228                 }
 229                 int tlen = len >> 1;
 230                 int rlen = LengthOfInteger(sig, off, tlen);
 231                 int slen = LengthOfInteger(sig, off + tlen, tlen);
 232                 int ulen = 1 + LengthOfLength(rlen) + rlen
 233                         + 1 + LengthOfLength(slen) + slen;
 234                 byte[] s = new byte[1 + LengthOfLength(ulen) + ulen];
 235                 int k = 0;
 236                 s[k ++] = 0x30;
 237                 k += EncodeLength(ulen, s, k);
 238                 k += EncodeInteger(sig, off, tlen, s, k);
 239                 k += EncodeInteger(sig, off + tlen, tlen, s, k);
 240                 // DEBUG
 241                 if (k != s.Length) {
 242                         throw new Exception("DSA internal error");
 243                 }
 244                 return s;
 245         }
 246
 247         /*
 248          * Get the length of the value of an INTEGER containing a
 249          * specified value. Returned length includes the leading 0x00
 250          * byte (if applicable) but not the tag or length fields.
 251          */
 252         static int LengthOfInteger(byte[] x, int off, int len)
 253         {
 254                 while (len > 0 && x[off] == 0) {
 255                         off ++;
 256                         len --;
 257                 }
 258                 if (len == 0) {
 259                         return 1;
 260                 }
 261                 return (x[off] >= 0x80) ? len + 1 : len;
 262         }
 263
 264         static int LengthOfLength(int len)
 265         {
 266                 if (len < 0x80) {
 267                         return 1;
 268                 } else if (len < 0x100) {
 269                         return 2;
 270                 } else if (len < 0x10000) {
 271                         return 3;
 272                 } else if (len < 0x1000000) {
 273                         return 4;
 274                 } else {
 275                         return 5;
 276                 }
 277         }
 278
 279         static int EncodeLength(int len, byte[] dst, int off)
 280         {
 281                 if (len < 0x80) {
 282                         dst[off] = (byte)len;
 283                         return 1;
 284                 }
 285                 int k = 0;
 286                 for (int z = len; z != 0; z >>= 8) {
 287                         k ++;
 288                 }
 289                 dst[off] = (byte)(0x80 + k);
 290                 for (int i = 0; i < k; i ++) {
 291                         dst[off + k - i] = (byte)(len >> (i << 3));
 292                 }
 293                 return k + 1;
 294         }
 295
 296         static int EncodeInteger(byte[] x, int off, int len,
 297                 byte[] dst, int dstOff)
 298         {
 299                 int orig = dstOff;
 300                 dst[dstOff ++] = 0x02;
 301                 while (len > 0 && x[off] == 0) {
 302                         off ++;
 303                         len --;
 304                 }
 305                 if (len == 0) {
 306                         dst[dstOff ++] = 0x01;
 307                         dst[dstOff ++] = 0x00;
 308                         return dstOff - orig;
 309                 }
 310                 if (x[off] >= 0x80) {
 311                         dstOff += EncodeLength(len + 1, dst, dstOff);
 312                         dst[dstOff ++] = 0x00;
 313                 } else {
 314                         dstOff += EncodeLength(len, dst, dstOff);
 315                 }
 316                 Array.Copy(x, off, dst, dstOff, len);
 317                 dstOff += len;
 318                 return dstOff - orig;
 319         }
 320 }
 321
 322 }