_ Git - BoarSSL/blob - Crypto/ECCurve.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 represents an elliptic curve.
  31  */
  32
  33 public abstract class ECCurve {
  34
  35         /*
  36          * Get the subgroup order for this curve (big-endian unsigned
  37          * notation). The subgroup order is supposed to be a prime
  38          * integer.
  39          */
  40         public byte[] SubgroupOrder {
  41                 get {
  42                         return subgroupOrder;
  43                 }
  44         }
  45
  46         /*
  47          * Get the cofactor fors this curve (big-endian unsigned notation).
  48          * The cofactor is the quotient of the curve order by the subgroup
  49          * order.
  50          */
  51         public byte[] Cofactor {
  52                 get {
  53                         return cofactor;
  54                 }
  55         }
  56
  57         /*
  58          * Get the curve symbolic name.
  59          */
  60         public abstract string Name {
  61                 get;
  62         }
  63
  64         /*
  65          * Get the curve type.
  66          */
  67         public abstract ECCurveType CurveType {
  68                 get;
  69         }
  70
  71         /*
  72          * Get the length (in bytes) of an encoded point. The "point at
  73          * infinity" may use a shorter encoding than other points. This
  74          * uses the "normal" encoding (not compressed).
  75          */
  76         public abstract int EncodedLength {
  77                 get;
  78         }
  79
  80         /*
  81          * Get the length (in bytes) of an encoded compressed point.
  82          * The "point at infinity" may use a shorter encoding than
  83          * other points.
  84          */
  85         public abstract int EncodedLengthCompressed {
  86                 get;
  87         }
  88
  89         /*
  90          * Perform extensive curve validity checks. These tests may be
  91          * computationally expensive.
  92          */
  93         public abstract void CheckValid();
  94
  95         /*
  96          * Get the encoded generator for this curve. This is
  97          * a conventional point that generates the subgroup of prime
  98          * order on which computations are normally done.
  99          */
 100         public virtual byte[] GetGenerator(bool compressed)
 101         {
 102                 return MakeGenerator().Encode(compressed);
 103         }
 104
 105         /*
 106          * Get the offset and length of the X coordinate of a point,
 107          * within its encoded representation. When doing a Diffie-Hellman
 108          * key exchange, the resulting shared secret is the X coordinate
 109          * of the resulting point.
 110          */
 111         public abstract int GetXoff(out int len);
 112
 113         /*
 114          * Multiply the provided (encoded) point G by a scalar x. Scalar
 115          * encoding is big-endian. The scalar value shall be non-zero and
 116          * lower than the subgroup order (exception: some curves allow
 117          * larger ranges).
 118          *
 119          * The result is written in the provided D[] array, using either
 120          * compressed or uncompressed format (for some curves, output is
 121          * always compressed). The array shall have the appropriate length.
 122          * Returned value is -1 on success, 0 on error. If 0 is returned
 123          * then the array contents are indeterminate.
 124          *
 125          * G and D need not be distinct arrays.
 126          */
 127         public uint Mul(byte[] G, byte[] x, byte[] D, bool compressed)
 128         {
 129                 MutableECPoint P = MakeZero();
 130                 uint good = P.DecodeCT(G);
 131                 good &= ~P.IsInfinityCT;
 132                 good &= P.MulSpecCT(x);
 133                 good &= P.Encode(D, compressed);
 134                 return good;
 135         }
 136
 137         /*
 138          * Given points A and B, and scalar x and y, return x*A+y*B. This
 139          * is used for ECDSA. Scalars use big-endian encoding and must be
 140          * non-zero and lower than the subgroup order.
 141          *
 142          * The result is written in the provided D[] array, using either
 143          * compressed or uncompressed format (for some curves, output is
 144          * always compressed). The array shall have the appropriate length.
 145          * Returned value is -1 on success, 0 on error. If 0 is returned
 146          * then the array contents are indeterminate.
 147          *
 148          * Not all curves support this operation; if the curve does not,
 149          * then an exception is thrown.
 150          *
 151          * A, B and D need not be distinct arrays.
 152          */
 153         public uint MulAdd(byte[] A, byte[] x, byte[] B, byte[] y,
 154                 byte[] D, bool compressed)
 155         {
 156                 MutableECPoint P = MakeZero();
 157                 MutableECPoint Q = MakeZero();
 158
 159                 /*
 160                  * Decode both points.
 161                  */
 162                 uint good = P.DecodeCT(A);
 163                 good &= Q.DecodeCT(B);
 164                 good &= ~P.IsInfinityCT & ~Q.IsInfinityCT;
 165
 166                 /*
 167                  * Perform both point multiplications.
 168                  */
 169                 good &= P.MulSpecCT(x);
 170                 good &= Q.MulSpecCT(y);
 171                 good &= ~P.IsInfinityCT & ~Q.IsInfinityCT;
 172
 173                 /*
 174                  * Perform addition. The AddCT() function may fail if
 175                  * P = Q, in which case we must compute 2Q and use that
 176                  * value instead.
 177                  */
 178                 uint z = P.AddCT(Q);
 179                 Q.DoubleCT();
 180                 P.Set(Q, ~z);
 181
 182                 /*
 183                  * Encode the result. The Encode() function will report
 184                  * an error if the addition result is infinity.
 185                  */
 186                 good &= P.Encode(D, compressed);
 187                 return good;
 188         }
 189
 190         /*
 191          * Generate a new random secret value appropriate for an ECDH
 192          * key exchange (WARNING: this might not be sufficiently uniform
 193          * for the generation of the per-signature secret value 'k' for
 194          * ECDSA).
 195          *
 196          * The value is returned in unsigned big-endian order, in an array
 197          * of the same size of the subgroup order.
 198          */
 199         public abstract byte[] MakeRandomSecret();
 200
 201         /* ============================================================= */
 202
 203         byte[] subgroupOrder;
 204         byte[] cofactor;
 205
 206         internal ECCurve(byte[] subgroupOrder, byte[] cofactor)
 207         {
 208                 this.subgroupOrder = subgroupOrder;
 209                 this.cofactor = cofactor;
 210         }
 211
 212         /*
 213          * Create a new mutable point instance, initialized to the point
 214          * at infinity.
 215          *
 216          * (On some curves whose implementations do not support generic
 217          * point addition, this method may return a non-infinity point
 218          * which serves as placeholder to obtain MutableECPoint instances.)
 219          */
 220         internal abstract MutableECPoint MakeZero();
 221
 222         /*
 223          * Create a new mutable point instance, initialized to the
 224          * defined subgroup generator.
 225          */
 226         internal abstract MutableECPoint MakeGenerator();
 227
 228         /*
 229          * Create a new mutable point instance by decoding the provided
 230          * value.
 231          */
 232         internal abstract MutableECPoint Decode(byte[] enc);
 233 }
 234
 235 }