Back  | Code Snippets |  [Bill's Home]

# RSA Calculator

## 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 #include #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

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).