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