_ Git - BoarSSL/blob - Crypto/ECCurve25519.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 Curve25519.
  31  */
  32
  33 internal class ECCurve25519 : ECCurve {
  34
  35         public override string Name {
  36                 get {
  37                         return "Curve25519";
  38                 }
  39         }
  40
  41         public override ECCurveType CurveType {
  42                 get {
  43                         return ECCurveType.Montgomery;
  44                 }
  45         }
  46
  47         public override int EncodedLength {
  48                 get {
  49                         return 32;
  50                 }
  51         }
  52
  53         public override int EncodedLengthCompressed {
  54                 get {
  55                         return 32;
  56                 }
  57         }
  58
  59         public override byte[] GetGenerator(bool compressed)
  60         {
  61                 byte[] G = new byte[32];
  62                 G[0] = 9;
  63                 return G;
  64         }
  65
  66         private static byte[] ORDER = {
  67                 0x10, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  68                 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  69                 0x14, 0xDE, 0xF9, 0xDE, 0xA2, 0xF7, 0x9C, 0xD6,
  70                 0x58, 0x12, 0x63, 0x1A, 0x5C, 0xF5, 0xD3, 0xED
  71         };
  72
  73         private static byte[] COFACTOR = {
  74                 0x08
  75         };
  76
  77         private static byte[] MOD = {
  78                 0x7F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
  79                 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
  80                 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
  81                 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xED
  82         };
  83
  84         internal ModInt mp;
  85         internal ModInt ma24;
  86
  87         internal ECCurve25519() : base(ORDER, COFACTOR)
  88         {
  89                 mp = new ModInt(MOD);
  90                 ma24 = mp.Dup();
  91                 ma24.Set(121665);
  92                 ma24.ToMonty();
  93         }
  94
  95         public override void CheckValid()
  96         {
  97                 /* Nothing to do, the curve is valid by construction. */
  98         }
  99
 100         public override int GetXoff(out int len)
 101         {
 102                 len = 32;
 103                 return 0;
 104         }
 105
 106         /* obsolete
 107         public override uint Mul(byte[] G, byte[] x, byte[] D, bool compressed)
 108         {
 109                 if (G.Length != 32 || D.Length != 32 || x.Length > 32) {
 110                         return 0;
 111                 }
 112
 113                 byte[] k = new byte[32];
 114                 Array.Copy(x, 0, k, 32 - x.Length, x.Length);
 115
 116                 k[31] &= 0xF8;
 117                 k[0] &= 0x7F;
 118                 k[0] |= 0x40;
 119
 120                 byte[] u = new byte[32];
 121                 for (int i = 0; i < 32; i ++) {
 122                         u[i] = G[31 - i];
 123                 }
 124                 u[0] &= 0x7F;
 125
 126                 ModInt x1 = mp.Dup();
 127                 x1.DecodeReduce(u);
 128                 x1.ToMonty();
 129                 ModInt x2 = mp.Dup();
 130                 x2.SetMonty(0xFFFFFFFF);
 131                 ModInt z2 = mp.Dup();
 132                 ModInt x3 = x1.Dup();
 133                 ModInt z3 = x2.Dup();
 134                 uint swap = 0;
 135
 136                 ModInt a = mp.Dup();
 137                 ModInt aa = mp.Dup();
 138                 ModInt b = mp.Dup();
 139                 ModInt bb = mp.Dup();
 140                 ModInt c = mp.Dup();
 141                 ModInt d = mp.Dup();
 142                 ModInt e = mp.Dup();
 143
 144                 for (int t = 254; t >= 0; t --) {
 145                         uint kt = (uint)-((k[31 - (t >> 3)] >> (t & 7)) & 1);
 146                         swap ^= kt;
 147                         x2.CondSwap(x3, swap);
 148                         z2.CondSwap(z3, swap);
 149                         swap = kt;
 150
 151                         a.Set(x2);
 152                         a.Add(z2);
 153                         aa.Set(a);
 154                         aa.MontySquare();
 155                         b.Set(x2);
 156                         b.Sub(z2);
 157                         bb.Set(b);
 158                         bb.MontySquare();
 159                         e.Set(aa);
 160                         e.Sub(bb);
 161                         c.Set(x3);
 162                         c.Add(z3);
 163                         d.Set(x3);
 164                         d.Sub(z3);
 165                         d.MontyMul(a);
 166                         c.MontyMul(b);
 167                         x3.Set(d);
 168                         x3.Add(c);
 169                         x3.MontySquare();
 170                         z3.Set(d);
 171                         z3.Sub(c);
 172                         z3.MontySquare();
 173                         z3.MontyMul(x1);
 174                         x2.Set(aa);
 175                         x2.MontyMul(bb);
 176                         z2.Set(e);
 177                         z2.MontyMul(ma24);
 178                         z2.Add(aa);
 179                         z2.MontyMul(e);
 180                 }
 181                 x2.CondSwap(x3, swap);
 182                 z2.CondSwap(z3, swap);
 183
 184                 z2.FromMonty();
 185                 z2.Invert();
 186                 x2.MontyMul(z2);
 187
 188                 x2.Encode(u);
 189                 for (int i = 0; i < 32; i ++) {
 190                         D[i] = u[31 - i];
 191                 }
 192                 return 0xFFFFFFFF;
 193         }
 194
 195         public override uint MulAdd(byte[] A, byte[] x, byte[] B, byte[] y,
 196                 byte[] D, bool compressed)
 197         {
 198                 throw new CryptoException(
 199                         "Operation not supported for Curve25519");
 200         }
 201         */
 202
 203         public override bool Equals(object obj)
 204         {
 205                 return (obj as ECCurve25519) != null;
 206         }
 207
 208         public override int GetHashCode()
 209         {
 210                 return 0x3E96D5F6;
 211         }
 212
 213         public override byte[] MakeRandomSecret()
 214         {
 215                 /*
 216                  * For Curve25519, we simply generate a random 32-byte
 217                  * array, to which we apply the "clamping" that will
 218                  * be done for point multiplication anyway.
 219                  */
 220                 byte[] x = new byte[32];
 221                 RNG.GetBytes(x);
 222                 x[0] &= 0x7F;
 223                 x[0] |= 0x40;
 224                 x[31] &= 0xF8;
 225                 return x;
 226         }
 227
 228         internal override MutableECPoint MakeZero()
 229         {
 230                 return new MutableECPointCurve25519();
 231         }
 232
 233         internal override MutableECPoint MakeGenerator()
 234         {
 235                 MutableECPointCurve25519 G = new MutableECPointCurve25519();
 236                 G.Decode(GetGenerator(false));
 237                 return G;
 238         }
 239
 240         internal override MutableECPoint Decode(byte[] enc)
 241         {
 242                 MutableECPointCurve25519 P = new MutableECPointCurve25519();
 243                 P.Decode(enc);
 244                 return P;
 245         }
 246 }
 247
 248 }