Implementing RSA, C#

I had an assignment to implement RSA algorithm, according to our textbook, the steps are like below

I have made my form so that user can enter the values of the prime numbers, p, q, and the public key, e, or the user can press on a buttons to generate these numbers randomly, I have made it very simple, with no validations, and encrypting only numbers below the length n of the RSA algorithm.

I have called the text fields p,q,e,d,m,c with IDs  txtP, txtQ, txtE, txtD, txtM, txtC

To generate random p, and q, I am using a function RandomIntegerBelow (which I created with the help of some posts from stackoverflow) to generate a random BigInteger below a specific number then test if this number is prime or not using Rabin Millar test(I posted it in previous post) , and keep looping until I get it

        private void btnGenerateP_Click(object sender, EventArgs e)
        {
            BigInteger p = RandomIntegerBelow(BigInteger.Parse(txtMax.Text));
            while (!IsProbabilyPrime(p, 20))
            {
                p = RandomIntegerBelow(BigInteger.Parse(txtMax.Text));
            }
            txtP.Text = p.ToString();
        }

To get random e, I generated a random number below totient and tested if gcd(totient, e) = 1, and looped until I get it.

        private void btnGenerateE_Click(object sender, EventArgs e)
        {
            log("generating e randomely such that gcd(e,totient) = 1");
            BigInteger temp = 0;
            while (GCD_Euclidean(temp, BigInteger.Parse(txtTOT.Text)) != 1)
            {
                temp = RandomIntegerBelow(BigInteger.Parse(txtTOT.Text));
                log("new E =  " + temp);
            }
            txtE.Text = temp.ToString();
        }

I used the function Extended_GCD (I have posted in in previous post) to get the modulo multiplicative inverse for the e value to get d, this function returns array of the values gcd, x, y respectively that satisfies gcd(m,n) = m*x + n*y, and I am reading always y as my answer since I am sending the totient first then the value of e.

        private void btnCalculateD_Click(object sender, EventArgs e)
        {
            BigInteger[] result = new BigInteger[3];
            result = Extended_GCD(BigInteger.Parse(txtTOT.Text), BigInteger.Parse(txtE.Text));
            if (result[2] < 0)
                result[2] = result[2] + BigInteger.Parse(txtTOT.Text);
            txtD.Text = result[2].ToString();
        }

Now I have e,d,n (public key, private key, length) which are the important parameters for RSA algorithm

Lastly, to encrypt and decrypt

        private void btnEncrypt_Click(object sender, EventArgs e)
        {
            log("Encrypting, C = M^e mod n");
            txtC.Text = BigInteger.ModPow(BigInteger.Parse(txtM.Text), BigInteger.Parse(txtE.Text), BigInteger.Parse(txtN.Text)).ToString();
        }

        private void btnDecrypt_Click(object sender, EventArgs e)
        {
            log("Encrypting, M' = C^d mod n");
            txtMR.Text = BigInteger.ModPow(BigInteger.Parse(txtC.Text), BigInteger.Parse(txtD.Text), BigInteger.Parse(txtN.Text)).ToString();
        }

Below is the full code including the helper functions

        private void btnGenerateP_Click(object sender, EventArgs e)
        {
            BigInteger p = RandomIntegerBelow(BigInteger.Parse(txtMax.Text));
            while (!IsProbabilyPrime(p, 20))
            {
                p = RandomIntegerBelow(BigInteger.Parse(txtMax.Text));
            }
            txtP.Text = p.ToString();
        }

        private void btnGenerateQ_Click(object sender, EventArgs e)
        {
            BigInteger p = RandomIntegerBelow(BigInteger.Parse(txtMax.Text));
            while (!IsProbabilyPrime(p, 20))
            {
                p = RandomIntegerBelow(BigInteger.Parse(txtMax.Text));
            }
            txtQ.Text = p.ToString();
        }

        private void btnCalculateD_Click(object sender, EventArgs e)
        {
            BigInteger[] result = new BigInteger[3];
            result = Extended_GCD(BigInteger.Parse(txtTOT.Text), BigInteger.Parse(txtE.Text));
            if (result[2] < 0)
                result[2] = result[2] + BigInteger.Parse(txtTOT.Text);
            txtD.Text = result[2].ToString();
        }

        private void btnCalculateN_Click(object sender, EventArgs e)
        {
            log("N = P*Q = " + txtP.Text + " x " + txtQ.Text);
            txtN.Text = (BigInteger.Multiply(BigInteger.Parse(txtP.Text), BigInteger.Parse(txtQ.Text))).ToString();
        }

        private void btnCalculateTOT_Click(object sender, EventArgs e)
        {
            log("totient = (P-1)*(Q-1) = " + (BigInteger.Parse(txtP.Text) - 1) + " x " + (BigInteger.Parse(txtQ.Text) - 1));
            txtTOT.Text = (BigInteger.Multiply(BigInteger.Parse(txtP.Text) - 1, BigInteger.Parse(txtQ.Text) - 1)).ToString();
        }

        private void btnGenerateE_Click(object sender, EventArgs e)
        {
            log("generating e randomely such that gcd(e,totient) = 1");
            BigInteger temp = 0;
            while (GCD_Euclidean(temp, BigInteger.Parse(txtTOT.Text)) != 1)
            {
                temp = RandomIntegerBelow(BigInteger.Parse(txtTOT.Text));
                log("new E =  " + temp);
            }
            txtE.Text = temp.ToString();
        }

        private void btnEncrypt_Click(object sender, EventArgs e)
        {
            log("Encrypting, C = M^e mod n");
            txtC.Text = BigInteger.ModPow(BigInteger.Parse(txtM.Text), BigInteger.Parse(txtE.Text), BigInteger.Parse(txtN.Text)).ToString();
        }

        private void btnDecrypt_Click(object sender, EventArgs e)
        {
            log("Encrypting, M' = C^d mod n");
            txtMR.Text = BigInteger.ModPow(BigInteger.Parse(txtC.Text), BigInteger.Parse(txtD.Text), BigInteger.Parse(txtN.Text)).ToString();
        }

        #region helpers

        public void log(string s)
        {
            txtLog.Text += s + "\r\n";
        }

        public static BigInteger GCD_Loop(BigInteger A, BigInteger B)
        {
            BigInteger R = BigInteger.One;
            while (B != 0)
            {
                R = A % B;
                A = B;
                B = R;
            }
            return A;
        }

        public BigInteger GCD_Euclidean(BigInteger A, BigInteger B)
        {
            log("gcd(" + A + "," + B + ")");
            if (B == 0)
                return A;
            if (A == 0)
                return B;
            if (A > B)
                return GCD_Euclidean(B, A % B);
            else
                return GCD_Euclidean(B % A, A);
        }

        public bool IsProbabilyPrime(BigInteger n, int k)
        {
            bool result = false;
            if (n < 2)
                return false;
            if (n == 2)
                return true;
            // return false if n is even -> divisbla by 2
            if (n % 2 == 0)
                return false;
            //writing n-1 as 2^s.d
            BigInteger d = n - 1;
            BigInteger s = 0;
            while (d % 2 == 0)
            {
                d >>= 1;
                s = s + 1;
            }
            for (int i = 0; i < k; i++)
            {
                BigInteger a;
                do
                {
                    a = RandomIntegerBelow(n - 2);
                }
                while (a < 2 || a >= n - 2);

                if (BigInteger.ModPow(a, d, n) == 1) return true;
                for (int j = 0; j < s - 1; j++)
                {
                    if (BigInteger.ModPow(a, 2 * j * d, n) == n - 1)
                        return true;
                }
                result = false;
            }
            return result;
        }

        public BigInteger RandomIntegerBelow(int n)
        {
            var rng = new RNGCryptoServiceProvider();
            byte[] bytes = new byte[n / 8];

            rng.GetBytes(bytes);

            var msb = bytes[n / 8 - 1];
            var mask = 0;
            while (mask < msb)
                mask = (mask << 1) + 1;

            bytes[n - 1] &= Convert.ToByte(mask);
            BigInteger p = new BigInteger(bytes);
            return p;
        }

        public BigInteger RandomIntegerBelow(BigInteger bound)
        {
            var rng = new RNGCryptoServiceProvider();
            //Get a byte buffer capable of holding any value below the bound
            var buffer = (bound << 16).ToByteArray(); // << 16 adds two bytes, which decrease the chance of a retry later on

            //Compute where the last partial fragment starts, in order to retry if we end up in it
            var generatedValueBound = BigInteger.One << (buffer.Length * 8 - 1); //-1 accounts for the sign bit
            var validityBound = generatedValueBound - generatedValueBound % bound;

            while (true)
            {
                //generate a uniformly random value in [0, 2^(buffer.Length * 8 - 1))
                rng.GetBytes(buffer);
                buffer[buffer.Length - 1] &= 0x7F; //force sign bit to positive
                var r = new BigInteger(buffer);

                //return unless in the partial fragment
                if (r >= validityBound) continue;
                return r % bound;
            }
        }

        public BigInteger[] Extended_GCD(BigInteger A, BigInteger B)
        {
            BigInteger[] result = new BigInteger[3];
             bool reverse = false;
            if (A < B) //if A less than B, switch them
            {
                BigInteger temp = A;
                A = B;
                B = temp;
               reverse = true;
            }
            log("Extended GCD");
            BigInteger r = B;
            BigInteger q = 0;
            BigInteger x0 = 1;
            BigInteger y0 = 0;
            BigInteger x1 = 0;
            BigInteger y1 = 1;
            BigInteger x = 0, y = 0;
            log(A + "\t" + " " + "\t" + x0 + "\t" + y0);
            log(B + "\t" + " " + "\t" + x1 + "\t" + y1);
            while (A % B!=0)
            {
                r = A % B;
                q = A / B;
                x = x0 - q * x1;
                y = y0 - q * y1;
                x0 = x1;
                y0 = y1;
                x1 = x;
                y1 = y;
                A = B;
                B = r;
                log(B + "\t" + r + "\t" + x + "\t" + y);
            }
            result[0] = r;
            if (reverse)
            {
                result[1] = y;
                result[2] = x;
            }
            else
            {
                result[1] = x;
                result[2] = y;
            }
            return result;
        }

        public BigInteger Extended_GCD2(BigInteger n, BigInteger m)
        {
            BigInteger[] Quot = new BigInteger[50];
            bool reverse = false;
            if (n < m)
            {
                BigInteger z;
                z = n;
                n = m;
                m = z;
                reverse = true;
            }
            BigInteger originaln = n;
            BigInteger originalm = m;
            int xstep = 1;
            BigInteger r = 1;
            while (r != 0)
            {
                BigInteger q = n / m;
                r = n - m * q;
                log(" " + n + " = " + m + "*" + q + " + " + r);
                n = m;
                m = r;
                Quot[xstep] = q;
                ++xstep;
            }
            //setgcd(n)
            BigInteger gcd = n;
            BigInteger a = 1;
            BigInteger b = 0;
            for (int i = xstep; i > 0; i--)
            {
                BigInteger z = b - Quot[i] * a;
                b = a;
                a = z;
            }

            return a;
        }

        #endregion

Extended GCD algorithm (Extended Euclidean Algorithm)

I had exercise to implement the extended GCD

The aim of this algorithm is to find x,y that satisfies ax + by = gcd(a,b) for any number a,b

The algorithm is as per the text book as below

        public static BigInteger[] Extended_GCD(BigInteger A, BigInteger B)
        {
            BigInteger[] result = new BigInteger[3];
            if (A < B) //if A less than B, switch them
            { 
                BigInteger temp = A;
                A = B;
                B = temp;
            }
            BigInteger r = B; 
            BigInteger q = 0; 
            BigInteger x0 = 1;
            BigInteger y0 = 0;
            BigInteger x1 = 0;
            BigInteger y1 = 1;
            BigInteger x = 0, y = 0;
            while (r > 1)
            {
                r = A % B;
                q = A / B;
                x = x0 - q * x1;
                y = y0 - q * y1;
                x0 = x1;
                y0 = y1;
                x1 = x;
                y1 = y;
                A = B;
                B = r;
            }
            result[0] = r;
            result[1] = x;
            result[2] = y;
            return result;
        }

Simple Memory Management Unit with VHDL

I had an assignment to design a simple memory management unit that takes virtual address, looks up this address in TLB (translation lookaside buffer), if found in the TLB, read the physical address from it and adds the offset. if not found in TLB, then looks into the page table inside the memory.
Block diagram for this system

I have implemented all except the page fault handling routine.
The TLB design is simply a 8 rows of 28 bits register, the first 20 bits contain the virtual page number,  connected to a comparator, the comparator is also connected to the input page number. the comparator output is connected to tri-state buffer control pin. the input to the tri-state buffers is the last 8 bits of the register that represents the physical address. When the comparator output is “1”, this passes the physical address through the tri-state buffer.
below is a block diagram for the TLB

MMU entities
Package used to define the input

library ieee; use ieee.std_logic_1164.all; 
  package byte_pkg is 
    subtype byte is std_logic_vector(7 downto 0); 
    type byte_array_t is array(natural range <>) of byte; 
  end; 

tri-state buffer

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;

entity tbuff is
    PORT(
        inp:IN STD_LOGIC_VECTOR(7 DOWNTO 0);
        sel:IN STD_LOGIC;
        outp:OUT STD_LOGIC_VECTOR(7 DOWNTO 0));
end tbuff;

architecture Behavioral of tbuff is
begin
    outp <= "ZZZZZZZZ"
    WHEN (sel = '0')
    ELSE inp;
end Behavioral;

comparator

library IEEE;
use IEEE.STD_LOGIC_1164.all;

entity comparator is
port(
    IN1:in std_logic_vector(19 downto 0);
    IN2:in std_logic_vector(19 downto 0);
    equal:out std_logic);
end comparator;

architecture Behavioral of comparator is
begin
    process(IN1, IN2)
    begin
        
        if (IN1 = IN2 ) then  
            equal <= '1';
            else
            equal <= '0';
        end if;
    end process;  
end Behavioral;

TLB output multiplexer

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use work.byte_pkg.all;

entity out_sel is
Port( inp:in byte_array_t(0 to 7);
    outp:out std_logic_vector(7 downto 0);
    selector:in std_logic_vector(7 downto 0));
end out_sel;

architecture Behavioral of out_sel is
begin
process(selector,inp)
begin
    CASE selector IS
    WHEN"00000001"=>outp<=inp(0);
    WHEN"00000010"=>outp<=inp(1);
    WHEN"00000100"=>outp<=inp(2);
    WHEN"00001000"=>outp<=inp(3);
    WHEN"00010000"=>outp<=inp(4);
    WHEN"00100000"=>outp<=inp(5);
    WHEN"01000000"=>outp<=inp(6);
    WHEN"10000000"=>outp<=inp(7);
    WHEN OTHERS=>
    outp<="ZZZZZZZZ";
END CASE;    
end process;

end Behavioral;

TLB – uses generate statement to create 8 comparators, tri-state buffers

library ieee;
use ieee.std_logic_1164.all;
use ieee.std_logic_arith.all;
use work.byte_pkg.all;

entity TLB is
port (clock: in std_logic;
    pn:in std_logic_vector(19 downto 0);
    fn_in:in std_logic_vector(7 downto 0);
    fn_out:out std_logic_vector(7 downto 0);
    r:in std_logic;
    w:in std_logic;
    hit:out std_logic);
end TLB;
architecture Behavioral of TLB is
component tbuff
PORT( inp:IN std_logic_vector(7 DOWNTO 0);
    sel:IN std_logic;
   outp:OUT std_logic_vector(7 DOWNTO 0));
end component;
component comparator
Port(
    IN1:in std_logic_vector(19 downto 0);
    IN2:in std_logic_vector(19 downto 0);
   equal:out std_logic);
end component;
component out_sel
Port( inp:in byte_array_t(0 to 7);
    outp:out std_logic_vector(7 downto 0);
    selector:in std_logic_vector(7 downto 0));
end component;
type tlb_type is array (0 to 7) of 
    std_logic_vector(31 downto 0);
signal tlb: tlb_type;--type eqtype is array (0 to 7) of std_logic;
signal equal:std_logic_vector(7 downto 0);
signal out_array:byte_array_t(0 to 7);
signal Counter: integer range 0 to 7;
signal tempfn:std_logic_vector(7 downto 0);
begin
    -- initializing the 8 comparators, tri-state buffers
    comps:for i in 0 to 7 generate
        compx: comparator port map(tlb(i)(27 downto 8),pn , equal(i));
        tbuffx: tbuff port map(tlb(i)(7 downto 0), equal(i) , out_array(i));
    end generate comps;
    --inializing the output multiplexer
    MUX:out_sel port map (out_array, tempfn, equal);
    
    process (clock)
    begin
        if (clock'event and clock='1') AND r='1' then
            if equal(0) = '1' or equal(1) = '1' or equal(2) = '1' or equal(3) = '1' or equal(4) = '1'or equal(5) = '1' or equal(6) = '1' or equal(7) = '1' then
                hit<='1';
                fn_out<=tempfn;
            else
                hit <='0';
                fn_out <= (others => '0');
            end if;
        end if;
    end process;
    process (w, clock)
    begin
        if (clock'event and clock='1')  AND w='1' then
            tlb(Counter) <= "0001" & pn & fn_in;
            if Counter < 7 then
                Counter <= Counter +1;
            else
                Counter <=0;
            end if;
        end if;
    end process;
end Behavioral;

RAM

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.STD_LOGIC_ARITH.ALL;
use IEEE.STD_LOGIC_UNSIGNED.ALL;

entity testram is Port ( 
    address: in std_logic_vector(19 downto 0);
    data:     out std_logic_vector(7 downto 0)
    );
end testram;

architecture behavioral of testram is

type mem_array is array (0 to 79) of std_logic_vector(7 downto 0);
constant characters: mem_array := (

    "00000001",
    "00000010",
    "00000011",
    "00000100",
    "00000101",
    "00000110",
    "00000111",
    "00001000",
    "00001001",
    "00001010",
    "00001011",
    "00001100",
    "00001101",
    "00001110",
    "00001111",
    "00010000",
    "00010001",
    "00010010",
    "00010011",
    "00010100",
    "00010101",
    "00010110",
    "00010111",
    "00011000",
    "00011001",
    "00011010",
    "00011011",
    "00011100",
    "00011101",
    "00011110",
    "00011111",
    "00100000",
    "00100001",
    "00100010",
    "00100011",
    "00100100",
    "00100101",
    "00100110",
    "00100111",
    "00101000",
    "00101001",
    "00101010",
    "00101011",
    "00101100",
    "00101101",
    "00101110",
    "00101111",
    "00110000",
    "00110001",
    "00110010",
    "00110011",
    "00110100",
    "00110101",
    "00110110",
    "00110111",
    "00111000",
    "00111001",
    "00111010",
    "00111011",
    "00111100",
    "00111101",
    "00111110",
    "00111111",
    "01000000",
    "01000001",
    "01000010",
    "01000011",
    "01000100",
    "01000101",
    "01000110",
    "01000111",
    "01001000",
    "01001001",
    "01001010",
    "01001011",
    "01001100",
    "01001101",
    "01001110",
    "01001111",
    "01010000"
    );
begin

process (address )
begin
        data <= characters(conv_integer(address));
end process;

end behavioral;

MMU – State machine

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
entity MMU is
Port(clock:in std_logic;
    address_in:in std_logic_vector(31 downto 0);
    address_out:out std_logic_vector(19 downto 0);
    ram_address:out std_logic_vector(19 downto 0);
    ram_data:in std_logic_vector(7 downto 0); 
    enable:in std_logic; 
    r:in std_logic);
end MMU;
architecture Behavioral of MMU is
component TLB is
port (clock: in std_logic;
    pn:in std_logic_vector(19 downto 0);
    fn_in:in std_logic_vector(7 downto 0);
    fn_out:out std_logic_vector(7 downto 0);
    r:in std_logic;
    w:in std_logic;
    hit:out std_logic);
end component;

signal tlb_pageno: std_logic_vector(19 downto 0);
signal tlb_framenoin: std_logic_vector(7 downto 0);
signal tlb_framenoout: std_logic_vector(7 downto 0);
signal tlb_r: std_logic:= '0';
signal tlb_w: std_logic:= '0';
signal tlb_hit:std_logic:='Z';

TYPE STATE_TYPE IS (s0, s1, s2, s3, s4, s5, s6);
SIGNAL state   : STATE_TYPE;


begin
TLB1:TLB port map (clock, tlb_pageno, tlb_framenoin, tlb_framenoout, tlb_r, tlb_w,tlb_hit);
process(clock, enable, r)
begin
 IF enable = '0' THEN
        state <= s0;
        tlb_r <= '0';
        tlb_w <= '0';
    ELSIF (clock'EVENT AND clock = '1') THEN
        CASE state IS
            WHEN S0=>
                tlb_r <= '0';
                tlb_w <= '0';                
                if r = '1' then
                    state <= s1;
                end if;
            WHEN s1=>
                tlb_pageno <= address_in(31 downto 12);
                tlb_r<='1';    
                tlb_w<='Z';
                state <= s2;
            WHEN s2=>
                tlb_r<='0';
                IF tlb_hit = '1' THEN
                    state <= s4;
                ELSIF tlb_hit = '0' then
                    state <= s3;
                END IF;
            WHEN s3=>
                ram_address <= address_in(31 downto 12);
                state <= s5;
            WHEN s4=>
                address_out <= tlb_framenoout & address_in(11 downto 0);    
                state <= s0;
            WHEN s5=>
                tlb_framenoin <= ram_data;
                address_out <= ram_data & address_in(11 downto 0);
                tlb_w <= '1';
                state <= s0;
            when others =>
                state <= s0;
        END CASE;
    END IF;
END PROCESS;
end Behavioral;

Full circuit

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;

entity crct is
Port(clock:in std_logic;
    address_in:in std_logic_vector(31 downto 0);
    address_out:out std_logic_vector(19 downto 0);
    enable:in std_logic; 
    r:in std_logic);
end crct;

architecture Behavioral of crct is
component MMU is
Port(clock:in std_logic;
    address_in:in std_logic_vector(31 downto 0);
    address_out:out std_logic_vector(19 downto 0);
    ram_address:out std_logic_vector(19 downto 0);
    ram_data:in std_logic_vector(7 downto 0); 
    enable:in std_logic; 
    r:in std_logic);
end component;
component testram is
 Port ( 
    address: in std_logic_vector(19 downto 0);
    data:     out std_logic_vector(7 downto 0)
    );
end component;
signal ram_address:std_logic_vector(19 downto 0);
signal ram_data:std_logic_vector(7 downto 0);
begin
mmu1:MMU port map (clock, address_in, address_out, ram_address, ram_data, enable, r);
ram1:testram port map(ram_address, ram_data);
end Behavioral;

Test bench

LIBRARY ieee;
USE ieee.std_logic_1164.ALL;
USE ieee.numeric_std.ALL;
ENTITY TB_full IS
END TB_full;
ARCHITECTURE behavior OF TB_full IS 
    COMPONENT crct
        Port(clock:in std_logic;
            address_in:in std_logic_vector(31 downto 0);
            address_out:out std_logic_vector(19 downto 0);
            enable:in std_logic; 
            r:in std_logic);
    END COMPONENT;
    
   signal clock : std_logic := '0';
   signal address_in : std_logic_vector(31 downto 0) := (others => '0');
    signal r:std_logic:='0';
    signal enable:std_logic:='0';
   signal address_out : std_logic_vector(19 downto 0);
   constant clock_period : time := 10 ns;
 
BEGIN
   uut: crct PORT MAP (
          clock => clock,
          address_in => address_in,
          address_out => address_out,
             enable => enable,
             r => r);
   clock_process :process
   begin
        clock <= '0';
        wait for clock_period/2;
        clock <= '1';
        wait for clock_period/2;
   end process;
   stim_proc: process
   begin        
      wait for 100 ns;    

      wait for clock_period*10;
        enable <= '1';
        r<='1';
        address_in <= "00000000000000000011000000000001";
        wait for clock_period;
        r<='0';
      wait;
   end process;
END;