/* * This is a simple implementation of a modulus where discrete logarithm * is easy. The modulus is a 2046-bit integer which is the product of all * small primes from 3 to 1471. */ using System; using System.Collections.Generic; public class EasyDL { public static void Main(string[] args) { /* * Make the modulus as the product of small primes from * 3 to 1471. We also put 2 as first element in the array * so that we may use it for factorization of small integers. */ ZInt p = 1; var pp = new List(); pp.Add(2); for (ZInt q = 3;; q += 2) { if (!q.IsPrime) { continue; } pp.Add(q); p *= q; if (p.BitLength >= 2046) { break; } } Console.WriteLine("p = {0}", p.ToHexString()); Console.WriteLine("num primes = {0} ({1} to {2})", pp.Count - 1, pp[1], pp[pp.Count - 1]); /* * Create a random generator g and exponent x, and compute * y = g^x mod p. */ ZInt g = ZInt.MakeRand(p); ZInt x = ZInt.MakeRand(p); ZInt y = ZInt.ModPow(g, x, p); Console.WriteLine("g = {0}", g.ToHexString()); Console.WriteLine("x = {0}", x.ToHexString()); Console.WriteLine("y = {0}", y.ToHexString()); /* * Now we "forget" x and try to find it again. It is * possible we don't find the same x, but any solution to * the discrete logarithm is acceptable. */ /* * We keep in the following arrays the information obtained * so far: * qj[i] greatest prime power so far (from prime p_i) * dj[i] x modulo qj[i] */ var qj = new ZInt[pp.Count]; var dj = new ZInt[pp.Count]; for (int i = 0; i < pp.Count; i ++) { qj[i] = 1; dj[i] = 0; } foreach (ZInt pi in pp) { if (pi == 2) { continue; } /* * Compute y_i = y mod p_i, and g_i = g mod p_i. * If g_i = 0, then we ignore that prime p_i (by * construction, we must have y_i = 0 in that case). */ ZInt yi = y % pi; ZInt gi = g % pi; if (gi == 0) { if (yi != 0) { throw new Exception("1"); } continue; } /* * Compute order n_i and local solution x_i, * brutally. As a sub-case, if n_i = 1, then * x_i = 0, and this brings no new information, * so we can also ignore p_i in such a situation. */ if (gi == 1) { if (yi != 1) { throw new Exception("2"); } continue; } ZInt ni = 0; ZInt r = 1; ZInt xi = -1; for (;;) { if (r == yi) { xi = ni; } r = (r * gi) % pi; ni ++; if (r == 1) { break; } } /* * Factor n_i into small primes. Reduce xi modulo * each small prime power, and merge that information * with that which was already obtained. */ for (int j = 0;; j ++) { if (ni == 1) { break; } ZInt pj = pp[j]; ZInt q = 1; while (ni % pj == 0) { ni /= pj; q *= pj; } if (q == 1) { continue; } /* * q is a non-trivial prime power that * divides ni. We merge the new information * from xi mod q with what we already had. */ ZInt xq = xi % q; if (q > qj[j]) { qj[j] = q; dj[j] = xq; } else { if (xq != xi % q) { throw new Exception("3"); } } } } /* * We now rebuild the solution x from qj and dj. The * elements of qj[] are prime to each other, so this is * a matter of applying the CRT repeatedly. * * At each step: * m is the product of values of qj processed so far * s = x mod m * * At then end, s is the solution we are looking for. */ ZInt m = 1; ZInt s = 0; for (int i = 0; i < qj.Length; i ++) { ZInt q = qj[i]; if (q == 1) { continue; } if (m == 1) { m = q; s = dj[i]; continue; } ZInt invm = m.ModInverse(q); s += m * (invm * (dj[i] - s).Mod(q)).Mod(q); m *= q; } /* * We verify that our solution s is correct. */ if (ZInt.ModPow(g, s, p) != y) { throw new Exception("4"); } Console.WriteLine("s = {0}", s.ToHexString()); } }