RSA code

Coordinator
Sep 13, 2014 at 10:01 AM
class Program
{
    static void Main(string[] args)
    {
        int ciphered = args.Length==0 ? 48 : Convert.ToInt32(args[0]);
        //Get all possible d and n (73)
        var possibleAnswers = new List<RSAKey>();
        for (int i = 0; i < 1000; i++)
        {
            for (int j = 0; j < 1000; j++)
            {
                if (3 * i + 4 * j - 100 == 781)
                {
                    possibleAnswers.Add(new RSAKey(i, j));
                }
            }
        }
        // get valid n (25)
        var rightN = possibleAnswers.Where(possibleAnswer => AreAllFactorPrimeAndHasOnly2Prime(possibleAnswer.N)).ToList();
        // compute e for public key
        foreach (var rsaKey in rightN)
        {
            var factors = Factor(rsaKey.N);
            factors.Remove(1);
            factors.Remove(rsaKey.N);
            int p = factors[0];
            int q = factors[1];
            var totient = (p - 1) * (q - 1);
            //e is > 1 and < totient
            for (int i = 2; i < totient; i++)
            {
                if ((i*rsaKey.D)%totient != 1) continue;
                //Check if the GCD of totient and i is 1
                if (Gcd(totient, i) != 1) continue;
                rsaKey.E = i;
                break;
            }
        }
        // filter only public key keys
        var rightE = rightN.Where(rsaKey => rsaKey.E != 0).ToList();
        //message is ciphered text
        foreach (var rsaKey in rightE)
        {
            rsaKey.SetCiphiredText(ciphered);
        }
        //Get valid entries
        rightE = rightE.Where(rsaKey => rsaKey.IsValid).ToList();
        //Display d n decipher
        Console.WriteLine("------------------------------");
        Console.WriteLine("d     n     Deciphered Message");
        Console.WriteLine("------------------------------");
        foreach (var rsaKey in rightE)
        {
            Console.WriteLine(rsaKey.D + "   " + rsaKey.N+"    " + rsaKey.DecryptedNumber);
        }
        Console.ReadLine();
    }
    public static List<int> Factor(int number)
    {
        var factors = new List<int>();
        var max = (int)Math.Sqrt(number);  //round down
        for (int factor = 1; factor <= max; ++factor)
        { //test from 1 to the square root, or the int below it, inclusive.
            if (number % factor == 0)
            {
                factors.Add(factor);
                if (factor != number / factor)
                { 
                    factors.Add(number / factor);
                }
            }
        }
        return factors;
    }
    public static bool AreAllFactorPrimeAndHasOnly2Prime(int number)
    {
        var factors = Factor(number);
        if (factors.Count != 4)
            return false;
        return factors.Where(factor => factor != 1 && factor != number).All(IsPrime);
    }
    public static bool IsPrime(int number)
    {
        var boundary = (int) Math.Floor(Math.Sqrt(number));
        if (number == 1) return false;
        if (number == 2) return true;
        for (var i = 2; i <= boundary; ++i)
        {
            if (number % i == 0) return false;
        }
        return true;
    }
    public static int Gcd(int p, int q)
    {
        if (q == 0)
        {
            return p;
        }
        var r = p % q;
        return Gcd(q, r);
    }
}
public class RSAKey
{
    public RSAKey(int d, int n)
    {
        D = d;
        N = n;
    }
    public void SetCiphiredText(int number)
    {
        DecryptedNumber = (int)BigInteger.ModPow(number, D, N);
        //encrypt the number and check if you are getting decrypted number back
        if (number == BigInteger.ModPow(DecryptedNumber, E, N))
        {
            IsValid = true;
        }
    }
    public int D { get; set; }
    public int N { get; set; }
    public int E { get; set; }
    public bool IsValid { get; private set; }
    public int DecryptedNumber { get; private set; }
}