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
