7 internal class TestEC {
9 internal static void Main(string[] args)
13 } catch (Exception e) {
14 Console.WriteLine(e.ToString());
19 internal static void TestECInt()
22 SpeedCurve(EC.Curve25519);
24 TestCurve(NIST.P256, KAT_P256);
25 TestCurve(NIST.P384, KAT_P384);
26 TestCurve(NIST.P521, KAT_P521);
28 SpeedCurve(NIST.P256);
29 SpeedCurve(NIST.P384);
30 SpeedCurve(NIST.P521);
33 static void TestCurve25519()
35 Console.Write("Test Curve25519: ");
38 "a546e36bf0527c9d3b16154b82465edd62144c0ac1fc5a18506a2244ba449ac4",
39 "e6db6867583030db3594c1a424b15f7c726624ec26b3353b10a903a6d0ab1c4c",
40 "c3da55379de9c6908e94ea4df28d084f32eccf03491c71f754b4075577a28552");
42 "4b66e9d4d1b4673c5ad22691957d6af5c11b6421e0ea01d42ca4169e7918ba0d",
43 "e5210f12786811d3f4b7959d0538ae2c31dbe7106fc03c3efc4cd549c715a493",
44 "95cbde9476e8907d7aade45cb4b873f88b595a68799fa152e6f8f7647aac7957");
46 byte[] u = EC.Curve25519.GetGenerator(false);
47 byte[] k = new byte[u.Length];
48 Array.Copy(u, 0, k, 0, u.Length);
50 byte[] nk = new byte[u.Length];
52 for (int i = 1; i <= 1000; i ++) {
53 EC.Curve25519.Mul(u, k, nk, false);
54 Array.Copy(k, 0, u, 0, u.Length);
56 Array.Copy(nk, 0, k, 0, u.Length);
59 byte[] z = ToBin(C25519_MC_1);
65 } else if (i == 1000) {
66 byte[] z = ToBin(C25519_MC_1000);
70 "Curve25519 MC 1000");
80 if (!Eq(k, ToBin(C25519_MC_1000000))) {
81 throw new Exception("Curve25519 MC 1000");
85 Console.WriteLine(" done.");
88 static string C25519_MC_1 = "422c8e7a6227d7bca1350b3e2bb7279f7897b87bb6854b783c60e80311ae3079";
89 static string C25519_MC_1000 = "684cf59ba83309552800ef566f2f4d3c1c3887c49360e3875f2eb94d99532c51";
91 static string C25519_MC_1000000 = "7c3911e0ab2586fd864497297e575e6f3bc601c0883c30df5f4dd2d24f665424";
94 static void Byteswap(byte[] t)
96 for (int i = 0; i < (t.Length >> 1); i ++) {
98 t[i] = t[t.Length - 1 - i];
99 t[t.Length - 1 - i] = x;
103 static void TestCurve25519KAT(string sscalar, string s_in, string s_out)
105 byte[] tmp = ToBin(sscalar);
106 byte[] scalar = new byte[tmp.Length];
107 for (int i = 0; i < tmp.Length; i ++) {
108 scalar[i] = tmp[tmp.Length - 1 - i];
110 byte[] A = ToBin(s_in);
111 byte[] B = new byte[A.Length];
112 if (EC.Curve25519.Mul(A, scalar, B, false) != 0xFFFFFFFF) {
113 throw new Exception("Curve25519 multiplication failed");
115 byte[] C = ToBin(s_out);
117 throw new Exception("Curve25519 KAT failed");
122 static void TestCurve(ECCurve curve, string[] kat)
124 Console.Write("Test {0}: ", curve.Name);
126 // ====================================================
130 ZInt p = ZInt.DecodeUnsignedBE(((ECCurvePrime)curve).mod);
131 ZInt a = ZInt.DecodeUnsignedBE(((ECCurvePrime)curve).a);
132 ZInt b = ZInt.DecodeUnsignedBE(((ECCurvePrime)curve).b);
133 Console.WriteLine("p = {0}", p.ToHexString());
134 Console.WriteLine("a = {0}", a.ToHexString());
135 Console.WriteLine("b = {0}", b.ToHexString());
136 MutableECPoint F1 = curve.MakeGenerator();
137 byte[] enc = F1.Encode(false);
138 int flen = enc.Length >> 1;
139 for (int i = 0; i < enc.Length; i ++) {
140 if (i == 1 || i == 1 + (enc.Length >> 1)) {
143 Console.Write("{0:X2}", enc[i]);
146 byte[] X = new byte[flen];
147 byte[] Y = new byte[flen];
148 Array.Copy(enc, 1, X, 0, flen);
149 Array.Copy(enc, 1 + flen, Y, 0, flen);
150 ZInt x1 = ZInt.DecodeUnsignedBE(X);
151 ZInt y1 = ZInt.DecodeUnsignedBE(Y);
152 Console.WriteLine("X1 = {0}", x1.ToHexString());
153 Console.WriteLine("Y1 = {0}", y1.ToHexString());
154 MutableECPoint F2 = F1.Dup();
156 MutableECPoint F3 = F2.Dup();
157 MutableECPoint F4 = F2.Dup();
158 enc = F2.Encode(false);
159 for (int i = 0; i < enc.Length; i ++) {
160 if (i == 1 || i == 1 + (enc.Length >> 1)) {
163 Console.Write("{0:X2}", enc[i]);
166 Array.Copy(enc, 1, X, 0, flen);
167 Array.Copy(enc, 1 + flen, Y, 0, flen);
168 ZInt x2 = ZInt.DecodeUnsignedBE(X);
169 ZInt y2 = ZInt.DecodeUnsignedBE(Y);
170 Console.WriteLine("X2 = {0}", x2.ToHexString());
171 Console.WriteLine("Y2 = {0}", y2.ToHexString());
172 if ((x1 * x1 * x1 + a * x1 + b - y1 * y1) % p != 0) {
173 throw new Exception("Generator not on curve");
175 if ((x2 * x2 * x2 + a * x2 + b - y2 * y2) % p != 0) {
176 throw new Exception("Double not on curve");
179 if (F3.AddCT(F1) == 0) {
180 throw new Exception("Addition failed");
182 MutableECPoint F5 = F3.Dup();
183 enc = F3.Encode(false);
184 for (int i = 0; i < enc.Length; i ++) {
185 if (i == 1 || i == 1 + (enc.Length >> 1)) {
188 Console.Write("{0:X2}", enc[i]);
191 Array.Copy(enc, 1, X, 0, flen);
192 Array.Copy(enc, 1 + flen, Y, 0, flen);
193 ZInt x3 = ZInt.DecodeUnsignedBE(X);
194 ZInt y3 = ZInt.DecodeUnsignedBE(Y);
195 Console.WriteLine("X3 = {0}", x3.ToHexString());
196 Console.WriteLine("Y3 = {0}", y3.ToHexString());
197 if ((x3 * x3 * x3 + a * x3 + b - y3 * y3) % p != 0) {
198 throw new Exception("Triple not on curve");
200 ZInt l3 = ((p + y2 - y1)
201 * ZInt.ModPow(p + x2 - x1, p - 2, p)) % p;
202 ZInt x3p = (l3 * l3 + p + p - x1 - x2) % p;
203 ZInt y3p = (l3 * (p + x1 - x3p) + p - y1) % p;
204 Console.WriteLine("X3p = {0}", x3p.ToHexString());
205 Console.WriteLine("Y3p = {0}", y3p.ToHexString());
206 Console.WriteLine("[X:{0}, Y:{1}]", x3 == x3p, y3 == y3p);
208 if (F5.AddCT(F4) == 0) {
209 throw new Exception("Addition failed");
211 enc = F5.Encode(false);
212 for (int i = 0; i < enc.Length; i ++) {
213 if (i == 1 || i == 1 + (enc.Length >> 1)) {
216 Console.Write("{0:X2}", enc[i]);
219 Array.Copy(enc, 1, X, 0, flen);
220 Array.Copy(enc, 1 + flen, Y, 0, flen);
221 ZInt x5 = ZInt.DecodeUnsignedBE(X);
222 ZInt y5 = ZInt.DecodeUnsignedBE(Y);
223 Console.WriteLine("X5 = {0}", x5.ToHexString());
224 Console.WriteLine("Y5 = {0}", y5.ToHexString());
225 if ((x5 * x5 * x5 + a * x5 + b - y5 * y5) % p != 0) {
226 throw new Exception("Quintuple not on curve");
228 ZInt l5 = ((p + y3 - y2)
229 * ZInt.ModPow(p + x3 - x2, p - 2, p)) % p;
230 ZInt x5p = (l5 * l5 + p + p - x2 - x3) % p;
231 ZInt y5p = (l5 * (p + x2 - x5p) + p - y2) % p;
232 Console.WriteLine("X5p = {0}", x5p.ToHexString());
233 Console.WriteLine("Y5p = {0}", y5p.ToHexString());
234 Console.WriteLine("[X:{0}, Y:{1}]", x5 == x5p, y5 == y5p);
236 F1.Set(curve.MakeGenerator());
237 if (F1.MulSpecCT(new byte[] { 0x05 }) == 0) {
238 throw new Exception("Multiplication failed");
240 enc = F1.Encode(false);
241 for (int i = 0; i < enc.Length; i ++) {
242 if (i == 1 || i == 1 + (enc.Length >> 1)) {
245 Console.Write("{0:X2}", enc[i]);
248 Array.Copy(enc, 1, X, 0, flen);
249 Array.Copy(enc, 1 + flen, Y, 0, flen);
250 ZInt x5t = ZInt.DecodeUnsignedBE(X);
251 ZInt y5t = ZInt.DecodeUnsignedBE(Y);
252 Console.WriteLine("X5t = {0}", x5t.ToHexString());
253 Console.WriteLine("Y5t = {0}", y5t.ToHexString());
254 if ((x5t * x5t * x5t + a * x5t + b - y5t * y5t) % p != 0) {
255 throw new Exception("Quintuple not on curve (2)");
257 Console.WriteLine("[X:{0}, Y:{1}]", x5t == x5p, y5t == y5p);
261 if (F1.AddCT(F2) == 0) {
262 throw new Exception("Addition failed (+0)");
264 enc = F1.Encode(false);
265 for (int i = 0; i < enc.Length; i ++) {
266 if (i == 1 || i == 1 + (enc.Length >> 1)) {
269 Console.Write("{0:X2}", enc[i]);
272 Array.Copy(enc, 1, X, 0, flen);
273 Array.Copy(enc, 1 + flen, Y, 0, flen);
274 ZInt x5q = ZInt.DecodeUnsignedBE(X);
275 ZInt y5q = ZInt.DecodeUnsignedBE(Y);
276 Console.WriteLine("X5q = {0}", x5q.ToHexString());
277 Console.WriteLine("Y5q = {0}", y5q.ToHexString());
278 Console.WriteLine("[X:{0}, Y:{1}]", x5q == x5p, y5q == y5p);
281 if (F2.AddCT(F1) == 0) {
282 throw new Exception("Addition failed (0+)");
284 enc = F2.Encode(false);
285 for (int i = 0; i < enc.Length; i ++) {
286 if (i == 1 || i == 1 + (enc.Length >> 1)) {
289 Console.Write("{0:X2}", enc[i]);
292 Array.Copy(enc, 1, X, 0, flen);
293 Array.Copy(enc, 1 + flen, Y, 0, flen);
294 ZInt x5r = ZInt.DecodeUnsignedBE(X);
295 ZInt y5r = ZInt.DecodeUnsignedBE(Y);
296 Console.WriteLine("X5r = {0}", x5r.ToHexString());
297 Console.WriteLine("Y5r = {0}", y5r.ToHexString());
298 Console.WriteLine("[X:{0}, Y:{1}]", x5r == x5p, y5r == y5p);
300 EC rG = EC.Make(p.ToBytesUnsignedBE(),
301 a.ToBytesUnsignedBE(), b.ToBytesUnsignedBE());
302 rG.Set(x1.ToBytesUnsignedBE(), y1.ToBytesUnsignedBE());
303 for (int i = 1; i <= 30; i ++) {
305 ZInt n = ZInt.MakeRand(i);
306 byte[] nb = n.ToBytesUnsignedBE();
307 F1 = curve.MakeGenerator();
308 if (F1.MulSpecCT(nb) == 0) {
309 throw new Exception("Multiplication error");
311 enc = F1.Encode(false);
313 if (enc.Length == 1) {
317 Array.Copy(enc, 1, X, 0, flen);
318 Array.Copy(enc, 1 + flen, Y, 0, flen);
319 xp = ZInt.DecodeUnsignedBE(X);
320 yp = ZInt.DecodeUnsignedBE(Y);
324 ZInt xh = ZInt.DecodeUnsignedBE(rH.X);
325 ZInt yh = ZInt.DecodeUnsignedBE(rH.Y);
326 if (xp != xh || yp != yh) {
328 Console.WriteLine("n = {0}", n);
329 Console.WriteLine("xp = {0}", xp.ToHexString());
330 Console.WriteLine("yp = {0}", yp.ToHexString());
331 Console.WriteLine("xh = {0}", xh.ToHexString());
332 Console.WriteLine("yh = {0}", yh.ToHexString());
333 throw new Exception("Bad mult result");
339 // ====================================================
342 MutableECPoint G = curve.MakeGenerator();
344 throw new Exception("Generator is infinity");
346 MutableECPoint P = G.Dup();
347 MutableECPoint Q = G.Dup();
348 MutableECPoint R = G.Dup();
349 MutableECPoint S = G.Dup();
350 MutableECPoint T = G.Dup();
352 for (int i = 0; i < 10; i ++) {
355 u = MakeRandPoint(P);
357 v = MakeRandPoint(Q);
358 } while (BigInt.Compare(u, v) == 0);
359 // byte[] s = BigInt.Add(u, v);
362 w = MakeRandPoint(R);
363 t = BigInt.Add(v, w);
364 } while (BigInt.Compare(u, w) == 0
365 || BigInt.Compare(v, w) == 0
366 || BigInt.Compare(u, t) == 0);
367 if (P.Eq(Q) || P.Eq(R) || Q.Eq(R)) {
368 throw new Exception("Equal points");
376 if (!S.Eq(T) || !T.Eq(S)) {
377 throw new Exception("Associativity error");
380 if (!S.Eq(T) || !T.Eq(S)) {
381 throw new Exception("Normalization error (1)");
384 if (!S.Eq(T) || !T.Eq(S)) {
385 throw new Exception("Normalization error (2)");
388 byte[] enc1 = P.Encode(false);
389 byte[] enc2 = P.Encode(true);
390 byte[] enc3 = new byte[enc1.Length];
391 Array.Copy(enc1, 1, enc3, 1, enc1.Length - 1);
392 enc3[0] = (byte)(enc2[0] | 0x04);
394 if (!P.Eq(Q) || !Q.Eq(P)) {
395 throw new Exception("Encode/decode error 1");
398 if (!P.Eq(Q) || !Q.Eq(P)) {
399 throw new Exception("Encode/decode error 2");
402 if (!P.Eq(Q) || !Q.Eq(P)) {
403 throw new Exception("Encode/decode error 3");
408 for (int i = 0; i < kat.Length; i += 2) {
410 byte[] n = ToBin(kat[i]);
411 if (P.MulSpecCT(n) == 0) {
412 throw new Exception("Multiplication error");
414 byte[] er = ToBin(kat[i + 1]);
415 if (!Eq(er, P.Encode(false))) {
416 throw new Exception("KAT failed");
418 byte[] eg = curve.GetGenerator(false);
419 byte[] ed = new byte[eg.Length];
420 curve.Mul(eg, n, ed, false);
422 throw new Exception("KAT failed (API 2)");
430 static void SpeedCurve(ECCurve curve)
432 byte[][] nn = new byte[100][];
433 for (int i = 0; i < nn.Length; i ++) {
434 nn[i] = BigInt.RandIntNZ(curve.SubgroupOrder);
436 MutableECPoint G = curve.MakeGenerator();
437 MutableECPoint P = G.Dup();
440 long orig = DateTime.Now.Ticks;
441 for (int i = 0, j = 0; i < num; i ++) {
443 if (++ j == nn.Length) {
447 long end = DateTime.Now.Ticks;
448 double tt = (double)(end - orig) / 10000000.0;
453 double f = (double)num / tt;
454 Console.WriteLine("{0,10} {1,9:f3} mul/s",
461 * Create a random non-infinity point by multiplying the
462 * curve subgroup generator with a random non-zero integer
463 * modulo the subgroup order. The multiplier is returned.
465 static byte[] MakeRandPoint(MutableECPoint P)
467 ECCurve curve = P.Curve;
468 P.Set(curve.MakeGenerator());
469 byte[] n = BigInt.RandIntNZ(curve.SubgroupOrder);
470 if (P.MulSpecCT(n) == 0) {
471 throw new Exception("Multiplication failed");
476 static void Add(MutableECPoint P, MutableECPoint Q)
481 if (P.AddCT(Q) == 0) {
482 throw new Exception("Addition failed");
487 static bool Eq(byte[] a1, byte[] a2)
492 if (a1 == null || a2 == null) {
496 if (n != a2.Length) {
499 for (int i = 0; i < n; i ++) {
500 if (a1[i] != a2[i]) {
507 static byte[] ToBin(string str)
509 MemoryStream ms = new MemoryStream();
512 foreach (char c in str) {
514 if (c >= '0' && c <= '9') {
516 } else if (c >= 'A' && c <= 'F') {
518 } else if (c >= 'a' && c <= 'f') {
520 } else if (c == ' ' || c == '\t' || c == ':') {
523 throw new ArgumentException(String.Format(
524 "not hex: U+{0:X4}", (int)c));
529 ms.WriteByte((byte)((acc << 4) + d));
534 throw new ArgumentException("final half byte");
539 static string[] KAT_P256 = {
540 "C9AFA9D845BA75166B5C215767B1D6934E50C3DB36E89B127B8A622B120F6721",
541 "0460FED4BA255A9D31C961EB74C6356D68C049B8923B61FA6CE669622E60F29FB67903FE1008B8BC99A41AE9E95628BC64F2F1B20C2D7E9F5177A3C294D4462299"
544 static string[] KAT_P384 = {
545 "6B9D3DAD2E1B8C1C05B19875B6659F4DE23C3B667BF297BA9AA47740787137D896D5724E4C70A825F872C9EA60D2EDF5",
546 "04EC3A4E415B4E19A4568618029F427FA5DA9A8BC4AE92E02E06AAE5286B300C64DEF8F0EA9055866064A254515480BC138015D9B72D7D57244EA8EF9AC0C621896708A59367F9DFB9F54CA84B3F1C9DB1288B231C3AE0D4FE7344FD2533264720"
549 static string[] KAT_P521 = {
550 "00FAD06DAA62BA3B25D2FB40133DA757205DE67F5BB0018FEE8C86E1B68C7E75CAA896EB32F1F47C70855836A6D16FCC1466F6D8FBEC67DB89EC0C08B0E996B83538",
551 "0401894550D0785932E00EAA23B694F213F8C3121F86DC97A04E5A7167DB4E5BCD371123D46E45DB6B5D5370A7F20FB633155D38FFA16D2BD761DCAC474B9A2F5023A400493101C962CD4D2FDDF782285E64584139C2F91B47F87FF82354D6630F746A28A0DB25741B5B34A828008B22ACC23F924FAAFBD4D33F81EA66956DFEAA2BFDFCF5"