_ Git - BoarSSL/blob - Crypto/MutableECPointCurve25519.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  * An implementation of MutableECPoint for Curve25519.
  31  * This is a partial implementation that only supports multiplication
  32  * by a scalar, not general addition.
  33  */
  34
  35 internal class MutableECPointCurve25519 : MutableECPoint {
  36
  37         ModInt x;
  38         ModInt x1, x2, z2, x3, z3;
  39         ModInt a, aa, b, bb, c, d, e;
  40         byte[] u;
  41
  42         /*
  43          * Create a new instance. It is initialized to the point at
  44          * infinity (represented with a 0).
  45          */
  46         internal MutableECPointCurve25519()
  47         {
  48                 ECCurve25519 ccc = (ECCurve25519)EC.Curve25519;
  49                 x = ccc.mp.Dup();
  50                 x1 = ccc.mp.Dup();
  51                 x2 = ccc.mp.Dup();
  52                 z2 = ccc.mp.Dup();
  53                 x3 = ccc.mp.Dup();
  54                 z3 = ccc.mp.Dup();
  55                 a = ccc.mp.Dup();
  56                 aa = ccc.mp.Dup();
  57                 b = ccc.mp.Dup();
  58                 bb = ccc.mp.Dup();
  59                 c = ccc.mp.Dup();
  60                 d = ccc.mp.Dup();
  61                 e = ccc.mp.Dup();
  62                 u = new byte[32];
  63         }
  64
  65         internal override ECCurve Curve {
  66                 get {
  67                         return EC.Curve25519;
  68                 }
  69         }
  70
  71         internal override uint IsInfinityCT {
  72                 get {
  73                         return 0;
  74                 }
  75         }
  76
  77         internal override void Normalize()
  78         {
  79         }
  80
  81         internal override byte[] Encode(bool compressed)
  82         {
  83                 byte[] r = new byte[32];
  84                 Encode(r, false);
  85                 return r;
  86         }
  87
  88         internal override uint Encode(byte[] dst, bool compressed)
  89         {
  90                 if (dst.Length != 32) {
  91                         throw new CryptoException("invalid output length");
  92                 }
  93                 x.Encode(u, 0, 32);
  94                 for (int i = 0; i < 32; i ++) {
  95                         dst[i] = u[31 - i];
  96                 }
  97                 return 0xFFFFFFFF;
  98         }
  99
 100         internal override uint DecodeCT(byte[] enc)
 101         {
 102                 if (enc.Length != 32) {
 103                         return 0;
 104                 }
 105                 for (int i = 0; i < 32; i ++) {
 106                         u[i] = enc[31 - i];
 107                 }
 108                 u[0] &= 0x7F;
 109                 x.DecodeReduce(u);
 110                 return 0xFFFFFFFF;
 111         }
 112
 113         internal override byte[] X {
 114                 get {
 115                         return x.Encode();
 116                 }
 117         }
 118
 119         internal override byte[] Y {
 120                 get {
 121                         throw new CryptoException(
 122                                 "Not implemented for Curve25519");
 123                 }
 124         }
 125
 126         internal override MutableECPoint Dup()
 127         {
 128                 MutableECPointCurve25519 Q = new MutableECPointCurve25519();
 129                 Q.Set(this);
 130                 return Q;
 131         }
 132
 133         internal void Set(byte[] X, byte[] Y, bool check)
 134         {
 135                 throw new CryptoException("Not implemented for Curve25519");
 136         }
 137
 138         internal void Set(ModInt X, ModInt Y, bool check)
 139         {
 140                 throw new CryptoException("Not implemented for Curve25519");
 141         }
 142
 143         internal override void SetZero()
 144         {
 145                 throw new CryptoException("Not implemented for Curve25519");
 146         }
 147
 148         internal override void Set(MutableECPoint Q)
 149         {
 150                 MutableECPointCurve25519 R = SameCurve(Q);
 151                 x.Set(R.x);
 152         }
 153
 154         internal override void Set(MutableECPoint Q, uint ctl)
 155         {
 156                 MutableECPointCurve25519 R = SameCurve(Q);
 157                 x.CondCopy(R.x, ctl);
 158         }
 159
 160         internal override void SetMux(uint ctl,
 161                 MutableECPoint P1, MutableECPoint P2)
 162         {
 163                 SetMuxInner(ctl, SameCurve(P1), SameCurve(P2));
 164         }
 165
 166         void SetMuxInner(uint ctl,
 167                 MutableECPointCurve25519 P1, MutableECPointCurve25519 P2)
 168         {
 169                 x.CopyMux(ctl, P1.x, P2.x);
 170         }
 171
 172         internal override void DoubleCT()
 173         {
 174                 throw new CryptoException("Not implemented for Curve25519");
 175         }
 176
 177         internal override uint AddCT(MutableECPoint Q)
 178         {
 179                 throw new CryptoException("Not implemented for Curve25519");
 180         }
 181
 182         internal override void NegCT()
 183         {
 184                 throw new CryptoException("Not implemented for Curve25519");
 185         }
 186
 187         internal override uint MulSpecCT(byte[] n)
 188         {
 189                 /*
 190                  * Copy scalar into a temporary array (u[]) for
 191                  * normalisation to 32 bytes and clamping.
 192                  */
 193                 if (n.Length > 32) {
 194                         return 0;
 195                 }
 196                 Array.Copy(n, 0, u, 32 - n.Length, n.Length);
 197                 for (int i = 0; i < 32 - n.Length; i ++) {
 198                         u[i] = 0;
 199                 }
 200                 u[31] &= 0xF8;
 201                 u[0] &= 0x7F;
 202                 u[0] |= 0x40;
 203
 204                 x1.Set(x);
 205                 x1.ToMonty();
 206                 x2.SetMonty(0xFFFFFFFF);
 207                 z2.Set(0);
 208                 x3.Set(x1);
 209                 z3.Set(x2);
 210                 uint swap = 0;
 211                 ModInt ma24 = ((ECCurve25519)EC.Curve25519).ma24;
 212
 213                 for (int t = 254; t >= 0; t --) {
 214                         uint kt = (uint)-((u[31 - (t >> 3)] >> (t & 7)) & 1);
 215                         swap ^= kt;
 216                         x2.CondSwap(x3, swap);
 217                         z2.CondSwap(z3, swap);
 218                         swap = kt;
 219
 220                         a.Set(x2);
 221                         a.Add(z2);
 222                         aa.Set(a);
 223                         aa.MontySquare();
 224                         b.Set(x2);
 225                         b.Sub(z2);
 226                         bb.Set(b);
 227                         bb.MontySquare();
 228                         e.Set(aa);
 229                         e.Sub(bb);
 230                         c.Set(x3);
 231                         c.Add(z3);
 232                         d.Set(x3);
 233                         d.Sub(z3);
 234                         d.MontyMul(a);
 235                         c.MontyMul(b);
 236                         x3.Set(d);
 237                         x3.Add(c);
 238                         x3.MontySquare();
 239                         z3.Set(d);
 240                         z3.Sub(c);
 241                         z3.MontySquare();
 242                         z3.MontyMul(x1);
 243                         x2.Set(aa);
 244                         x2.MontyMul(bb);
 245                         z2.Set(e);
 246                         z2.MontyMul(ma24);
 247                         z2.Add(aa);
 248                         z2.MontyMul(e);
 249                 }
 250                 x2.CondSwap(x3, swap);
 251                 z2.CondSwap(z3, swap);
 252
 253                 /*
 254                  * We need to restore z2 to normal representation before
 255                  * inversion. Then the final Montgomery multiplication
 256                  * will cancel out with x2, which is still in Montgomery
 257                  * representation.
 258                  */
 259                 z2.FromMonty();
 260                 z2.Invert();
 261                 x2.MontyMul(z2);
 262
 263                 /*
 264                  * x2 now contains the result.
 265                  */
 266                 x.Set(x2);
 267                 return 0xFFFFFFFF;
 268         }
 269
 270         internal override uint EqCT(MutableECPoint Q)
 271         {
 272                 MutableECPointCurve25519 R = SameCurve(Q);
 273                 return x.EqCT(R.x);
 274         }
 275
 276         MutableECPointCurve25519 SameCurve(MutableECPoint Q)
 277         {
 278                 MutableECPointCurve25519 R = Q as MutableECPointCurve25519;
 279                 if (R == null) {
 280                         throw new CryptoException("Mixed curves");
 281                 }
 282                 return R;
 283         }
 284 }
 285
 286 }