////////////////////////////////////////////////////////////////////
// BigIntRSA.cs
// Copyright © 2005, 2008 Carl Johansen
// 
// Crude demonstration of RSA encryption using the BigInt datatype.
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Lesser General Public License as published
// by the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Lesser General Public License for more
// details (<http://www.gnu.org/licenses/>).
////////////////////////////////////////////////////////////////////

using System;

namespace CarlJohansen
{
    /// <summary>
    /// Crude demonstration of RSA encryption using the BigInt datatype
    /// </summary>
    public class BigIntRSA
    {
        public static void DoDemo()
        {
            BigInt p = "398075086424064937397125500550386491199064362342526708406385189575946388957261768583317";
            BigInt q = "472772146107435302536223071973048224632914695302097116459852171130520711256363590397527";

            BigInt d, e, n;
            GenerateKeyPair(p, q, out d, out e, out n);
            Console.WriteLine("public key is ({0}, {1})", d, n);
            Console.WriteLine("private key is ({0}, {1})", e, n);
            Console.WriteLine();
            BigInt msg = "130107090319172105011309198"; // = "MAGIC SQUEAMISH" using A=01, B=02, Z=26, etc
            Console.WriteLine("plaintext is {0}", msg);
            BigInt encryptedMsg = BigInt.modpower(msg, d, n);
            Console.WriteLine("plaintext encrypted using public key: {0} -> {1}", msg, encryptedMsg);
            Console.WriteLine("cyphertext decrypted using private key: {0} -> {1}", encryptedMsg, BigInt.modpower(encryptedMsg, e, n));
        }

        public static void GenerateKeyPair(BigInt p, BigInt q, out BigInt d, out BigInt e, out BigInt n)
        {
            d = 0; e = 0;
            ushort c = 0, testLimit;
            BigInt r;
            bool done;

            n = p * q;
            BigInt phiN = (p - 1) * (q - 1);
            done = false;

            do
            {
                c++;
                r = phiN.ShortMultiply(c) + 1; // this must be odd, since phi must be even (product of two even numbers)
                testLimit = 500;
                for (d = 3; d < testLimit && (r % d != 0); d += 2) ;
                if (d < testLimit)
                {
                    e = r / d;
                    if (!((d % phiN) == (e % phiN)))
                        done = true;
                }
            } while (!done);
        }
    }
}