_ Git - BoarSSL/blob - Tests/TestMath.cs

   1 using System;
   2 using System.IO;
   3 using System.Reflection;
   4 using System.Text;
   5
   6 using Crypto;
   7
   8 internal class TestMath {
   9
  10         internal static void Main(string[] args)
  11         {
  12                 try {
  13                         TestModInt();
  14                 } catch (Exception e) {
  15                         Console.WriteLine(e.ToString());
  16                         Environment.Exit(1);
  17                 }
  18         }
  19
  20         static ZInt RandPrime(int k)
  21         {
  22                 if (k < 2) {
  23                         throw new ArgumentException();
  24                 }
  25                 ZInt min = ZInt.One << (k - 1);
  26                 ZInt max = ZInt.One << k;
  27                 for (;;) {
  28                         ZInt p = ZInt.MakeRand(min, max) | 1;
  29                         if (p.IsPrime) {
  30                                 return p;
  31                         }
  32                 }
  33         }
  34
  35         internal static void TestModInt()
  36         {
  37                 Console.Write("Test ModInt: ");
  38                 for (int k = 2; k <= 128; k ++) {
  39                         for (int i = 0; i < 10; i ++) {
  40                                 int kwlen = (k + 30) / 31;
  41                                 int kwb = 31 * kwlen;
  42
  43                                 ZInt p;
  44                                 if (k >= 9) {
  45                                         p = ZInt.DecodeUnsignedBE(
  46                                                 BigInt.RandPrime(k));
  47                                         if (p.BitLength != k) {
  48                                                 throw new Exception(
  49                                                         "wrong prime size");
  50                                         }
  51                                         if (!p.IsPrime) {
  52                                                 throw new Exception(
  53                                                         "not prime");
  54                                         }
  55                                 } else {
  56                                         p = RandPrime(k);
  57                                 }
  58
  59                                 ZInt a = ZInt.MakeRand(p);
  60                                 ZInt b = ZInt.MakeRand(p);
  61                                 ZInt v = ZInt.MakeRand(k + 60);
  62                                 if (b == ZInt.Zero) {
  63                                         b = ZInt.One;
  64                                 }
  65                                 byte[] ea = a.ToBytesBE();
  66                                 byte[] eb = b.ToBytesBE();
  67                                 byte[] ev = v.ToBytesBE();
  68                                 ModInt mz = new ModInt(p.ToBytesBE());
  69                                 ModInt ma = mz.Dup();
  70                                 ModInt mb = mz.Dup();
  71
  72                                 ma.Decode(ea);
  73                                 CheckEq(ma, a);
  74
  75                                 ma.Decode(ea);
  76                                 mb.Decode(eb);
  77                                 ma.Add(mb);
  78                                 CheckEq(ma, (a + b).Mod(p));
  79
  80                                 ma.Decode(ea);
  81                                 mb.Decode(eb);
  82                                 ma.Sub(mb);
  83                                 CheckEq(ma, (a - b).Mod(p));
  84
  85                                 ma.Decode(ea);
  86                                 ma.Negate();
  87                                 CheckEq(ma, (-a).Mod(p));
  88
  89                                 ma.Decode(ea);
  90                                 mb.Decode(eb);
  91                                 ma.MontyMul(mb);
  92                                 CheckEq((ZInt.DecodeUnsignedBE(ma.Encode())
  93                                         << kwb).Mod(p), (a * b).Mod(p));
  94
  95                                 ma.Decode(ea);
  96                                 ma.ToMonty();
  97                                 CheckEq(ma, (a << kwb).Mod(p));
  98                                 ma.FromMonty();
  99                                 CheckEq(ma, a);
 100
 101                                 ma.Decode(ea);
 102                                 mb.Decode(eb);
 103                                 ma.ToMonty();
 104                                 mb.ToMonty();
 105                                 ma.MontyMul(mb);
 106                                 ma.FromMonty();
 107                                 CheckEq(ma, (a * b).Mod(p));
 108
 109                                 mb.Decode(eb);
 110                                 mb.Invert();
 111                                 ZInt r = ZInt.DecodeUnsignedBE(mb.Encode());
 112                                 CheckEq(ZInt.One, (r * b).Mod(p));
 113
 114                                 ma.Decode(ea);
 115                                 ma.Pow(ev);
 116                                 CheckEq(ma, ZInt.ModPow(a, v, p));
 117
 118                                 ma.DecodeReduce(ev);
 119                                 CheckEq(ma, v.Mod(p));
 120
 121                                 mb.Decode(eb);
 122                                 ma.Set(mb);
 123                                 CheckEq(ma, b);
 124
 125                                 ModInt mv = new ModInt(
 126                                         ((p << 61) + 1).ToBytesBE());
 127                                 mv.Decode(ev);
 128                                 ma.Set(mv);
 129                                 CheckEq(ma, v.Mod(p));
 130
 131                                 if (k >= 9) {
 132                                         ma.Decode(ea);
 133                                         mb.Set(ma);
 134                                         mb.ToMonty();
 135                                         mb.MontyMul(ma);
 136                                         if ((int)mb.SqrtBlum() != -1) {
 137                                                 throw new CryptoException(
 138                                                         "square root failed");
 139                                         }
 140                                         if (!mb.Eq(ma)) {
 141                                                 mb.Negate();
 142                                         }
 143                                         CheckEq(mb, a);
 144
 145                                         mb.Decode(eb);
 146                                         mb.ToMonty();
 147                                         mb.MontySquare();
 148                                         mb.FromMonty();
 149                                         mb.Negate();
 150                                         if (mb.SqrtBlum() != 0) {
 151                                                 throw new CryptoException(
 152                                                         "square root should"
 153                                                         + " have failed");
 154                                         }
 155                                 }
 156                         }
 157                         Console.Write(".");
 158                 }
 159                 Console.WriteLine(" done.");
 160         }
 161
 162         static void CheckEq(ModInt m, ZInt z)
 163         {
 164                 CheckEq(ZInt.DecodeUnsignedBE(m.Encode()), z);
 165         }
 166
 167         static void CheckEq(ZInt x, ZInt z)
 168         {
 169                 if (x != z) {
 170                         throw new Exception(String.Format(
 171                                 "mismatch: x={0} z={1}", x, z));
 172                 }
 173         }
 174 }