RSA, named after its three creators - Rivest, Shamir and Adleman, was the first effective public-key algorithm, and for years has withstood intense scrutiny by cryptanalysts all over the world.
Unlike symmetric key algorithms, where, as long as one presumes that an algorithm is not flawed, the security relies on having to try all possible keys, public-key algorithms rely on it being computationally unfeasible to recover the private key from the public key.
RSA relies on the fact that it is easy to multiply two large prime numbers together, but extremely hard (i.e. time consuming) to factor them back from the result (Ref. 6).
Factoring a number means finding its prime factors, which are the prime numbers that need to be multiplied together in order to produce that number. For example:
10 = 2 * 5
60 = 2 * 2 * 3 * 5
2^113 - 1 = 3391 * 23279 * 65993 * 1868569 * 1066818132868207
The algorithm:
Two very large prime numbers, normally of equal length, are randomly chosen then multiplied together.
N = A*B
T = (A-1) * (B-1)
A third number is then also chosen randomly as the public key (E) such that it has no common factors (i.e. is relatively prime) with T. The private key (D) is then:
D = E^-1 mod T
To encrypt a block of plaintext (M) into ciphertext (C):
C = M^E mod N
To decrypt:
M = C^D mod N
As an example:
1st prime (A) = 37
2nd prime (B) = 23
So,
N= 37*23 = 851
T = (37 - 1)*(23 - 1) = 36 * 23 = 792
E must have no factors other than 1 in common with 792.
E (public key) could be 5.
D (private key) = 5^-1 mod 792 = 317
To encrypt a message (M) of the character ‘G’:
If G is represented as 7 (7th letter in alphabet), then M= 7.
C (ciphertext) = 7^5 mod 851 = 638
To decrypt:
M = 638^317 mod 851 = 7
==================================================================================
#include< stdio.h>
#include< conio.h>
int phi,M,n,e,d,C,FLAG;
int check()
{
int i;
for(i=3;e%i==0 && phi%i==0;i+2)
{
FLAG = 1;
return;
}
FLAG = 0;
}
void encrypt()
{
int i;
C = 1;
for(i=0;i< e;i++)
C=C*M%n;
C = C%n;
printf("\n\tEncrypted keyword : %d",C);
}
void decrypt()
{
int i;
M = 1;
for(i=0;i< d;i++)
M=M*C%n;
M = M%n;
printf("\n\tDecrypted keyword : %d",M);
}
void main()
{
int p,q,s;
clrscr();
printf("Enter Two Relatively Prime Numbers\t: ");
scanf("%d%d",&p,&q);
n = p*q;
phi=(p-1)*(q-1);
printf("\n\tF(n)\t= %d",phi);
do
{
printf("\n\nEnter e\t: ");
scanf("%d",&e);
check();
}while(FLAG==1);
d = 1;
do
{
s = (d*e)%phi;
d++;
}while(s!=1);
d = d-1;
printf("\n\tPublic Key\t: {%d,%d}",e,n);
printf("\n\tPrivate Key\t: {%d,%d}",d,n);
printf("\n\nEnter The Plain Text\t: ");
scanf("%d",&M);
encrypt();
printf("\n\nEnter the Cipher text\t: ");
scanf("%d",&C);
decrypt();
getch();
}
/*************** OUTPUT *****************
Enter Two Relatively Prime Numbers : 7 17
F(n) = 96
Enter e : 5
Public Key : {5,119}
Private Key : {77,119}
Enter The Plain Text : 19
Encrypted keyword : 66
Enter the Cipher text : 66
Decrypted keyword : 19 */
Unlike symmetric key algorithms, where, as long as one presumes that an algorithm is not flawed, the security relies on having to try all possible keys, public-key algorithms rely on it being computationally unfeasible to recover the private key from the public key.
RSA relies on the fact that it is easy to multiply two large prime numbers together, but extremely hard (i.e. time consuming) to factor them back from the result (Ref. 6).
Factoring a number means finding its prime factors, which are the prime numbers that need to be multiplied together in order to produce that number. For example:
10 = 2 * 5
60 = 2 * 2 * 3 * 5
2^113 - 1 = 3391 * 23279 * 65993 * 1868569 * 1066818132868207
The algorithm:
Two very large prime numbers, normally of equal length, are randomly chosen then multiplied together.
N = A*B
T = (A-1) * (B-1)
A third number is then also chosen randomly as the public key (E) such that it has no common factors (i.e. is relatively prime) with T. The private key (D) is then:
D = E^-1 mod T
To encrypt a block of plaintext (M) into ciphertext (C):
C = M^E mod N
To decrypt:
M = C^D mod N
As an example:
1st prime (A) = 37
2nd prime (B) = 23
So,
N= 37*23 = 851
T = (37 - 1)*(23 - 1) = 36 * 23 = 792
E must have no factors other than 1 in common with 792.
E (public key) could be 5.
D (private key) = 5^-1 mod 792 = 317
To encrypt a message (M) of the character ‘G’:
If G is represented as 7 (7th letter in alphabet), then M= 7.
C (ciphertext) = 7^5 mod 851 = 638
To decrypt:
M = 638^317 mod 851 = 7
==================================================================================
#include< stdio.h>
#include< conio.h>
int phi,M,n,e,d,C,FLAG;
int check()
{
int i;
for(i=3;e%i==0 && phi%i==0;i+2)
{
FLAG = 1;
return;
}
FLAG = 0;
}
void encrypt()
{
int i;
C = 1;
for(i=0;i< e;i++)
C=C*M%n;
C = C%n;
printf("\n\tEncrypted keyword : %d",C);
}
void decrypt()
{
int i;
M = 1;
for(i=0;i< d;i++)
M=M*C%n;
M = M%n;
printf("\n\tDecrypted keyword : %d",M);
}
void main()
{
int p,q,s;
clrscr();
printf("Enter Two Relatively Prime Numbers\t: ");
scanf("%d%d",&p,&q);
n = p*q;
phi=(p-1)*(q-1);
printf("\n\tF(n)\t= %d",phi);
do
{
printf("\n\nEnter e\t: ");
scanf("%d",&e);
check();
}while(FLAG==1);
d = 1;
do
{
s = (d*e)%phi;
d++;
}while(s!=1);
d = d-1;
printf("\n\tPublic Key\t: {%d,%d}",e,n);
printf("\n\tPrivate Key\t: {%d,%d}",d,n);
printf("\n\nEnter The Plain Text\t: ");
scanf("%d",&M);
encrypt();
printf("\n\nEnter the Cipher text\t: ");
scanf("%d",&C);
decrypt();
getch();
}
/*************** OUTPUT *****************
Enter Two Relatively Prime Numbers : 7 17
F(n) = 96
Enter e : 5
Public Key : {5,119}
Private Key : {77,119}
Enter The Plain Text : 19
Encrypted keyword : 66
Enter the Cipher text : 66
Decrypted keyword : 19 */
