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