_ Git - BoarSSL/blob - Crypto/RSAPrivateKey.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 a RSA private key. The private key elements can
  31  * be exported as arrays of bytes (minimal unsigned big-endian
  32  * representation).
  33  *
  34  * Private key elements are:
  35  *   n    modulus
  36  *   e    public exponent
  37  *   d    private exponent
  38  *   p    first modulus factor
  39  *   q    second modulus factor
  40  *   dp   d mod (p-1)
  41  *   dq   d mod (q-1)
  42  *   iq   (1/q) mod p
  43  */
  44
  45 public class RSAPrivateKey : IPrivateKey {
  46
  47         public byte[] N {
  48                 get {
  49                         return n;
  50                 }
  51         }
  52
  53         public byte[] E {
  54                 get {
  55                         return e;
  56                 }
  57         }
  58
  59         public byte[] D {
  60                 get {
  61                         return d;
  62                 }
  63         }
  64
  65         public byte[] P {
  66                 get {
  67                         return p;
  68                 }
  69         }
  70
  71         public byte[] Q {
  72                 get {
  73                         return q;
  74                 }
  75         }
  76
  77         public byte[] DP {
  78                 get {
  79                         return dp;
  80                 }
  81         }
  82
  83         public byte[] DQ {
  84                 get {
  85                         return dq;
  86                 }
  87         }
  88
  89         public byte[] IQ {
  90                 get {
  91                         return iq;
  92                 }
  93         }
  94
  95         public int KeySizeBits {
  96                 get {
  97                         return ((n.Length - 1) << 3)
  98                                 + BigInt.BitLength(n[0]);
  99                 }
 100         }
 101
 102         public string AlgorithmName {
 103                 get {
 104                         return "RSA";
 105                 }
 106         }
 107
 108         IPublicKey IPrivateKey.PublicKey {
 109                 get {
 110                         return this.PublicKey;
 111                 }
 112         }
 113
 114         public RSAPublicKey PublicKey {
 115                 get {
 116                         return new RSAPublicKey(n, e);
 117                 }
 118         }
 119
 120         byte[] n, e, d, p, q, dp, dq, iq;
 121
 122         /*
 123          * Create a new instance with the provided elements. Values are
 124          * in unsigned big-endian representation.
 125          *
 126          *   n    modulus
 127          *   e    public exponent
 128          *   d    private exponent
 129          *   p    first modulus factor
 130          *   q    second modulus factor
 131          *   dp   d mod (p-1)
 132          *   dq   d mod (q-1)
 133          *   iq   (1/q) mod p
 134          *
 135          * Rules verified by this constructor:
 136          *   n must be odd and at least 512 bits
 137          *   e must be odd
 138          *   p must be odd
 139          *   q must be odd
 140          *   p and q are greater than 1
 141          *   n is equal to p*q
 142          *   dp must be non-zero and lower than p-1
 143          *   dq must be non-zero and lower than q-1
 144          *   iq must be non-zero and lower than p
 145          *
 146          * This constructor does NOT verify that:
 147          *   p and q are prime
 148          *   d is equal to dp modulo p-1
 149          *   d is equal to dq modulo q-1
 150          *   dp is the inverse of e modulo p-1
 151          *   dq is the inverse of e modulo q-1
 152          *   iq is the inverse of q modulo p
 153          */
 154         public RSAPrivateKey(byte[] n, byte[] e, byte[] d,
 155                 byte[] p, byte[] q, byte[] dp, byte[] dq, byte[] iq)
 156         {
 157                 n = BigInt.NormalizeBE(n);
 158                 e = BigInt.NormalizeBE(e);
 159                 d = BigInt.NormalizeBE(d);
 160                 p = BigInt.NormalizeBE(p);
 161                 q = BigInt.NormalizeBE(q);
 162                 dp = BigInt.NormalizeBE(dp);
 163                 dq = BigInt.NormalizeBE(dq);
 164                 iq = BigInt.NormalizeBE(iq);
 165
 166                 if (n.Length < 64 || (n.Length == 64 && n[0] < 0x80)) {
 167                         throw new CryptoException(
 168                                 "Invalid RSA private key (less than 512 bits)");
 169                 }
 170                 if (!BigInt.IsOdd(n)) {
 171                         throw new CryptoException(
 172                                 "Invalid RSA private key (even modulus)");
 173                 }
 174                 if (!BigInt.IsOdd(e)) {
 175                         throw new CryptoException(
 176                                 "Invalid RSA private key (even exponent)");
 177                 }
 178                 if (!BigInt.IsOdd(p) || !BigInt.IsOdd(q)) {
 179                         throw new CryptoException(
 180                                 "Invalid RSA private key (even factor)");
 181                 }
 182                 if (BigInt.IsOne(p) || BigInt.IsOne(q)) {
 183                         throw new CryptoException(
 184                                 "Invalid RSA private key (trivial factor)");
 185                 }
 186                 if (BigInt.Compare(n, BigInt.Mul(p, q)) != 0) {
 187                         throw new CryptoException(
 188                                 "Invalid RSA private key (bad factors)");
 189                 }
 190                 if (dp.Length == 0 || dq.Length == 0) {
 191                         throw new CryptoException(
 192                                 "Invalid RSA private key"
 193                                 + " (null reduced private exponent)");
 194                 }
 195
 196                 /*
 197                  * We can temporarily modify p[] and q[] (to compute
 198                  * p-1 and q-1) since these are freshly produced copies.
 199                  */
 200                 p[p.Length - 1] --;
 201                 q[q.Length - 1] --;
 202                 if (BigInt.Compare(dp, p) >= 0 || BigInt.Compare(dq, q) >= 0) {
 203                         throw new CryptoException(
 204                                 "Invalid RSA private key"
 205                                 + " (oversized reduced private exponent)");
 206                 }
 207                 p[p.Length - 1] ++;
 208                 q[q.Length - 1] ++;
 209                 if (iq.Length == 0 || BigInt.Compare(iq, p) >= 0) {
 210                         throw new CryptoException(
 211                                 "Invalid RSA private key"
 212                                 + " (out of range CRT coefficient)");
 213                 }
 214                 this.n = n;
 215                 this.e = e;
 216                 this.d = d;
 217                 this.p = p;
 218                 this.q = q;
 219                 this.dp = dp;
 220                 this.dq = dq;
 221                 this.iq = iq;
 222         }
 223
 224         /*
 225          * Create a new instance with the provided elements: the two
 226          * factors, and the public exponent. The other elements are
 227          * computed. Values are in unsigned big-endian representation.
 228          * Rules verified by this constructor:
 229          *   p must be odd
 230          *   q must be odd
 231          *   e must be relatively prime to both p-1 and q-1
 232          *   e must be greater than 1
 233          *   p*q must have size at least 512 bits
 234          * TODO: not implemented yet.
 235          */
 236         public RSAPrivateKey(byte[] p, byte[] q, byte[] e)
 237         {
 238                 throw new Exception("NYI");
 239         }
 240
 241         /*
 242          * Create a new instance with the provided elements: the two
 243          * factors, and the public exponent. The other elements are
 244          * computed. The factors are in unsigned big-endian
 245          * representation; the public exponent is a small integer.
 246          * Rules verified by this constructor:
 247          *   p must be odd
 248          *   q must be odd
 249          *   e must be relatively prime to both p-1 and q-1
 250          *   p*q must have size at least 512 bits
 251          * TODO: not implemented yet.
 252          */
 253         public RSAPrivateKey(byte[] p, byte[] q, uint e)
 254                 : this(p, q, ToBytes(e))
 255         {
 256         }
 257
 258         static byte[] ToBytes(uint x)
 259         {
 260                 byte[] r = new byte[4];
 261                 r[0] = (byte)(x >> 24);
 262                 r[1] = (byte)(x >> 16);
 263                 r[2] = (byte)(x >> 8);
 264                 r[3] = (byte)x;
 265                 return r;
 266         }
 267
 268         /*
 269          * CheckValid() will verify that the prime factors are indeed
 270          * prime, and that all other values are correct.
 271          */
 272         public void CheckValid()
 273         {
 274                 /*
 275                  * Factors ought to be prime.
 276                  */
 277                 if (!BigInt.IsPrime(p) || !BigInt.IsPrime(q)) {
 278                         throw new CryptoException("Invalid RSA private key"
 279                                 + " (non-prime factor)");
 280                 }
 281
 282                 /*
 283                  * FIXME: Verify that:
 284                  *   dp = d mod p-1
 285                  *   e*dp = 1 mod p-1
 286                  *   dq = d mod q-1
 287                  *   e*dq = 1 mod q-1
 288                  * (This is not easy with existing code because p-1 and q-1
 289                  * are even, but ModInt tolerates only odd moduli.)
 290                  *
 291                 CheckExp(p, d, dp, e);
 292                 CheckExp(q, d, dq, e);
 293                  */
 294
 295                 /*
 296                  * Verify that:
 297                  *   q*iq = 1 mod p
 298                  */
 299                 ModInt x = new ModInt(p);
 300                 ModInt y = x.Dup();
 301                 x.DecodeReduce(q);
 302                 x.ToMonty();
 303                 y.Decode(iq);
 304                 x.MontyMul(y);
 305                 if (!x.IsOne) {
 306                         throw new CryptoException("Invalid RSA private key"
 307                                 + " (wrong CRT coefficient)");
 308                 }
 309         }
 310 }
 311
 312 }