Home  [Bill's Home]

Simple RSA key generation With RSA, initially the person picks two prime numbers. [Lecture][Tutorial] For example: p=11 and q=3 In the following you can either manually add your own values, or generate random ones by pressing the button: P:  Q:    Next, the n value is calculated. Thus: n = p x q = 11 x 3 = 33 Next PHI is calculated by: PHI = (p-1)(q-1) = 20 The factors of PHI are 1, 2, 4, 5, 10 and 20. Next the public exponent e is generated so that the greatest common divisor of e and PHI is 1 (e is relatively prime with PHI). Thus, the smallest value for e is: e = 3 N:  PHI:  E: The factors of e are 1 and 3, thus 1 is the highest common factor of them. Thus n (33) and the e (3) values are the public keys. The private key (d) is the inverse of e modulo PHI. d=e^(-1) mod [(p-1)x(q-1)] This can be calculated by using extended Euclidian algorithm, to give the =7. D: The encryption and decryption keys are then:   Public Key (n,e)  Private key (n,d) As a test you can manually put in p=11 and q=3, and get the keys of (n,e)=(33,3) and (n,d)=(33,7). The PARTY2 can be given the public keys of e and n, so that PARTY2 can encrypt the message with them. PARTY1, using d and n can then decrypt the encrypted message. For example, if the message value to decrypt is 4, then: c = m^e mod n = 43 mod 33 = 31 Therefore, the encrypted message (c) is 31. The encrypted message (c) is then decrypted by PARTY1 with: m = c^d mod n = 317 mod 33 = 4 which is equal to the message value.  Encryption/Decryption: Message: Encrypt: Decrypt:

   In this case the encryption is:

using System;
using System.Data;
using System.Configuration;
using System.Web;
using System.Web.Security;
using System.Web.UI;
using System.Web.UI.WebControls;
using System.Web.UI.WebControls.WebParts;
using System.Web.UI.HtmlControls;
using System.Collections;
using System.Security.Cryptography;
using System.IO;
using System.Text;

public partial class _Default : System.Web.UI.Page
{
    long p, q, n, PHI,ev,d;
    Random r;

    protected void Page_Load(object sender, EventArgs e)
    {
        r = new Random();
    }

    protected void Button1_Click(object sender, EventArgs e)
    {
        r = new Random();
        p = get_prime();

        q = get_prime();
        this.tbP.Text = Convert.ToString(p);
        this.tbQ.Text = Convert.ToString(q);


    }
    protected void Button2_Click(object sender, EventArgs e)
    {
        p = Convert.ToInt32(this.tbP.Text);
        q = Convert.ToInt32(this.tbQ.Text);
        n = p*q;

        PHI = (p - 1) * (q - 1);
        ev = getRandomEv(PHI);
        this.tbN.Text = Convert.ToString(n);
        tbPHI.Text = Convert.ToString(PHI);
        this.tbE.Text = Convert.ToString(ev);

    }
    protected void Button3_Click1(object sender, EventArgs e)
    {
        ev = Convert.ToInt32(this.tbE.Text);
        PHI = Convert.ToInt32(this.tbPHI.Text);
        n = Convert.ToInt32(this.tbN.Text);

        d = getD(ev, PHI);
        this.tbd.Text = Convert.ToString(d);

        this.tbPublic.Text = "("+tbN.Text+","+tbE.Text+")";

       this.tbPrivate.Text = "("+tbN.Text+","+tbd.Text+")";
        long m=123;

        long c = decrypt(m, n, ev);
        this.tbEnc.Text = Convert.ToString(c);

        long mdec = decrypt(c, n, d);
        this.tbDec.Text = Convert.ToString(mdec);
    }
    public long get_prime()
    {
        long[] primes;
        primes = new long[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 
131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 
223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 
311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397 };

        return (primes[r.Next(primes.Length - 1)]);
    }

    public  long getEv(long PHI)
    {
        long great = 0, e = 2;

        while (great != 1)
        {
            e = e + 1;
            great = get_common_denom(e, PHI);
        }
        return (e);
    }
    public long getRandomEv(long PHI)
    {
        long great = 0, e = 0;

        //Random number generator cannot handle long values, this is a weaknes of this setup
        int int_phi;
        try
        {
            int_phi = (int)(PHI);
        }
        catch
        {
            int_phi = (int)(Int16.MaxValue - 1);
        }

        for (; ; )
        {
            e = r.Next(2, int_phi);

            if (e < 2 || e > PHI)
                continue;

            if (1 == get_common_denom(e, PHI))  break;
        }

        return (e);
    }

    public  long get_common_denom(long e, long PHI)
    {
        long great, temp, a;

        if (e > PHI)
        {
            while (e % PHI != 0)
            {
                temp = e % PHI;
                e = PHI;
                PHI = temp;
            }
            great = PHI;
        }
        else
        {
            while (PHI % e != 0)
            {
                a = PHI % e;
                PHI = e;
                e = a;
            }
            great = e;
        }
        return (great);
    }
    long getD( long e, long PHI)
    {
        long[] u;
        long [] v;
        long q,temp1,temp2,temp3;

        u = new long[] { 0, 0, 0 };
        v = new long[] { 0, 0, 0 };

        u[0]=1; u[1]=0; u[2]=PHI;
        v[0]=0; v[1]=1; v[2]=e;

        while (v[2]!=0)
        {
            q=(long)Math.Floor((decimal)u[2]/v[2]);
            temp1=u[0]-q*v[0];
            temp2=u[1]-q*v[1];
            temp3=u[2]-q*v[2];
            u[0]=v[0];
            u[1]=v[1];
            u[2]=v[2];
            v[0]=temp1;
            v[1]=temp2;
            v[2]=temp3;
        }
        if (u[1]<0) return(u[1]+PHI);
        else return(u[1]);
}
    long decrypt(long c, long n, long d)
    {
        long i, g, f;

        if (d % 2 == 0) g = 1; else g = c;

        for (i = 1; i <= d / 2; i++)
        {
            f = c * c % n;
            g = f * g % n;
        }
        return (g);
    }
}

If you would like the full code, please contact me.