rsa2

Homework 01 - Deadline - 11 Oct 2018 23:59
Brute force breaking of RSA
Console application
a) Implement RSA key generation and encryption,
  ask for user input (choose primes, plaintext message (number))
b) Given the one side of the key and ciphertext, brute force the message.

---------------------------------------------------------------------------------
RSA implementation

Generate public and private keys
Encrypt and decrypt some strings, do it character by character.


Break cypher using "Brute Force approach", when you know the public key.



using System;
using System.Numerics;

namespace RSADemo
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Hello RSA!");

            var p = 7;
            var q = 19;
            Console.WriteLine($"p: {p} q:{q}");

            var n = p * q;
            var m = (p - 1) * (q - 1);
            Console.WriteLine($"n = p*q : {n}     m = (p - 1) * (q - 1) :{m}");

            // find smallest number e (co-prime), where gcd(m,e) == 1
            int e = 1;
            var gcd = 0;
            do
            {
                e++;
                gcd = Gcd(m, e);
                Console.WriteLine($"Gcd({m}, {e}) = {gcd}");
            } while (gcd != 1);

            Console.WriteLine($"Co-prime to the m:{m} is e:{e}");


            // Same as finding d,
            // which satisfies de=1 + km where k is any integer.
            // Rewrite this as d=(1+km)/e

            int k = 0;

            do
            {
                if ((1 + k * m) % e == 0) break;
                k++;
            } while (true);

            var d = (1 + k * m) / e;
            Console.WriteLine($"d: {d}");

            Console.WriteLine($"Public key: n:{n} e:{e}");
            Console.WriteLine($"Private key: p*q=n : {p}*{q}={n} d:{d}");

            Console.Write("Plaintext char:");
            var plainTextString = Console.ReadLine();
            if (plainTextString.Length >= 1)
            {
                var plainText = (int) plainTextString[0]-65;
                Console.WriteLine($"char code is:{plainText}");

                var cypher = ((int) Math.Pow(plainText, e)) % n;
                Console.WriteLine($"Cypher is:{cypher}");


                var decrypttext = BigInteger.ModPow(cypher, d, n);
                Console.WriteLine($"Decrypt text is:{decrypttext}");
            }


        }

        // Function to return Greatest Common Divisor of a and b
        static int Gcd(int a, int b)
        {
            if (a == 0)
                return b;
            return Gcd(b % a, a);
        }

    }
}