Back  | Code Snippets |  [Bill's Home]

RSA Calculator

RSA VB Program ZIP [EXE]
RSA C Program ZIP
RSA C# Program

RSA Theory

The RSA encryption algorithm uses a one-way function, which is relatively easy to calculate in one direction, but extremely difficult to reverse the calculation. For example it is relatively simple for someone to calculate the square of a value using a pencil and paper, but it is difficult to find the square root of a value. Most of us could calculate the square of 63 as 3969, but what is the square root of 6889? The answer is 93, which is not a easy to determine (without the aid of a calculator).

Public-key encryption is the best way to secure data. With this method a user generates two electronic keys, typically with hundreds or thousands of bits. These keys are special number and relate to extremely large prime numbers (as it is difficult to factorise large prime numbers. For example, I have two prime numbers (small ones), and when I multiple them together I get the value of:

1,354,657

What was the original prime numbers [answer at the bottom of this page]? With public key encryption these numbers typically have thousands of bits, which gives values from 1 to 1,797,693,134, 862, 315,907,729,305,190,789, ...... (in total, it has 309 digits). Imagine finding the factors for two number that are this long?

Algorithm

With RSA, initially the person picks two prime numbers. For example:

p=11 and q=3

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

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 private key, d of 7.

Thus n=33, e=3 and d=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.

RSA Source code (VB program)

An example program which has a limited range of prime numbers is given next:

and another:

The VB code is:

rem Simple RSA Program
rem (c) W.Buchanan
rem Jan 2002

Function check_prime(ByVal val As Long) As Boolean
Dim primes
primes = Array(1, 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)
check_prime = False

For i = 0 To 78
If (val = primes(i)) Then
prime = True
End If
Next i
check_prime = prime
End Function

Function decrypt(ByVal c, ByVal n, ByVal d As Long)

Dim i, g, f As Long

On Error GoTo errorhandler

If (d Mod 2 = 0) Then
g = 1
Else
g = c
End If

For i = 1 To d / 2

f = c * c Mod n
g = f * g Mod n
Next i
decrypt = g

Exit Function
errorhandler:
Select Case Err.Number ' Evaluate error number.
Case 6
status.Text = "Calculation overflow, please select smaller values"
Case Else
status.Text = "Calculation error"
End Select

End Function


Function getD(ByVal e As Long, ByVal PHI As Long) As Long
Dim u(3) As Long
Dim v(3) As Long
Dim q, temp1, temp2, temp3 As Long

u(0) = 1
u(1) = 0
u(2) = PHI
v(0) = 0
v(1) = 1
v(2) = e

While (v(2) <> 0)
q = Int(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
Wend
If (u(1) < 0) Then
getD = (u(1) + PHI)
Else
getD = u(1)
End If
End Function


Function getE(ByVal PHI As Long) As Long
Dim great, e As Long

great = 0
e = 2

While (great <> 1)
e = e + 1
great = get_common_denom(e, PHI)
Wend
getE = e
End Function


Function get_common_denom(ByVal e As Long, ByVal PHI As Long)
Dim great, temp, a As Long

If (e > PHI) Then
While (e Mod PHI <> 0)
temp = e Mod PHI
e = PHI
PHI = temp
Wend
great = PHI
Else
While (PHI Mod e <> 0)
a = PHI Mod e
PHI = e
e = a
Wend
great = e
End If
get_common_denom = great
End Function

Private Sub show_primes()
status.Text = "1"
no_primes = 1
For i = 2 To 400
prime = True
For j = 2 To (i / 2)
If ((i Mod j) = 0) Then
prime = False
End If
Next j

If (prime = True) Then
no_primes = no_primes + 1
status.Text = status.Text + ", " + Str(i)
End If
Next i
status.Text = status.Text + vbCrLf + "Number of primes found:" + Str(no_primes)
End Sub


Private Sub Command1_Click()
Dim p, q, n, e, PHI, d, m, c As Long

p = Text1.Text
q = Text2.Text
If (check_prime(p) = False) Then
status.Text = "p is not a prime or is too large, please re-enter"
ElseIf (check_prime(q) = False) Then
status.Text = "q is not a prime or is too large, please re-enter"
Else
n = p * q
Text3.Text = n

PHI = (p - 1) * (q - 1)
e = getE((PHI))
d = getD((e), (PHI))
Text4.Text = PHI
Text5.Text = d
Text6.Text = e
m = Text7.Text

c = (m ^ e) Mod n
Text8.Text = c
m = decrypt(c, n, d)
Text9.Text = m
Label12.Caption = "Decrypt key =<" + Str(d) + "," + Str(n) + ">"
Label13.Caption = "Encrypt key =<" + Str(e) + "," + Str(n) + ">"
End If
End Sub

Private Sub Command2_Click()
End
End Sub

Private Sub Command3_Click()
frmBrowser.Show
End Sub

Private Sub Command4_Click()
Call show_primes
End Sub

 

RSA Source code (C program)

An example program which has a limited range of prime numbers is given next.

/* Program by W.Buchanan, 2002 */
/* Simple implementation of the RSA Algorithm */

#include <stdio.h>
#include <math.h>

#define TRUE 1
#define FALSE 0

void get_prime( long *val);
long getE( long PHI);
long get_common_denom( long e, long PHI);
long getD( long e, long PHI);
long decrypt(long c,long n, long d);

int main(void)
{
long a,b,n,e,PHI,d,m,c;

get_prime(&a);
get_prime(&b);
n=a*b;
PHI=(a-1)*(b-1);
e=getE(PHI);

d= getD(e,PHI);
printf("Enter input value >> "); scanf("%ld",&m);

printf("a=%ld b=%ld n=%ld PHI=%ld\n",a,b,n,PHI);

c=(long)pow(m,e) % n; /* note, this may overflow with large numbers */
/* when e is relatively large */

printf("e=%ld d=%ld c=%ld\n",e,d,c);

m=decrypt(c,n,d); /* this function required as c to */
/*the power of d causes an overflow */
printf("Message is %ld ",m);
return(0);
}

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);
}

long getD( long e, long PHI)
{
long u[3]={1,0,PHI};
long v[3]={0,1,e};
long q,temp1,temp2,temp3;

while (v[2]!=0)
{
q=floor(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 getE( long PHI)
{
long great=0, e=2;

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

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);
}

void get_prime( long *val)
{
#define NO_PRIMES 13
long primes[NO_PRIMES]={3,5,7,11,13,17,19,23,29,31,37,41,43};
long prime,i;
do
{
prime=FALSE;
printf("Enter a prime number >> ");
scanf("%ld",val);
for (i=0;i<NO_PRIMES;i++)
if (*val==primes[i]) prime=TRUE;
} while (prime==FALSE);
}

 

Answer is 1487 times 911. If you interested in encryption, have a look at some of the work that my researcher (who is now working in Tawain) has done, especially Chapter 3 which outlines some of the main principles of encryption. She found new ways of speeding-up the encryption method most commonly used in public-key encryption (but don't tell the government or they might come after us).