- RSA (Rivest–Shamir–Adleman) is an algorithm used by modern computers to encrypt and decrypt messages.
- It is an asymmetric cryptographic algorithm.
- Asymmetric means that there are two different keys.
- This is also called public key cryptography, because one of the keys can be given to anyone.
EXAMPLE :-
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
typedef struct
{
int d;
int x;
int y;
}EE;
EE extended_euclid(int a, int b) {
EE e1, e2, e3;
if (b == 0)
{
e1.d = a;
e1.x = 1;
e1.y = 0;
return e1;
}
else
{
e2 = extended_euclid(b, a % b);
e3.d = e2.d;
e3.x = e2.y;
e3.y = e2.x - floor(a / b) * e2.y;
return e3;
}
}
int modulo(int x, int N){
return (x % N + N) % N;
}
void decimal_to_binary(int op1, int pq[]){
int result, i = 0;
do
{
result = op1 % 2;
op1 /= 2;
pq[i] = result;
i++;
}
while(op1 > 0);
}
int modular_exponentiation(int a, int b, int n){
int *bb;
int count = 0, c = 0, d = 1, i;
count = (int) (log(b)/log(2)) + 1;
bb = (int *) malloc(sizeof(int*) * count);
decimal_to_binary(b, bb);
for (i = count - 1; i >= 0; i--)
{
c = 2 * c;
d = (d*d) % n;
if (bb[i] == 1)
{
c = c + 1;
d = (d*a) % n;
}
}
return d;
}
int get_d(int e, int phi1){
EE Ee;
Ee = extended_euclid(e, phi1);
return modulo(Ee.x, phi1);
}
int main(int argc, char* argv[])
{
int p1, q1, phi1, n1, e1, d1, m1, c1;
printf("Enter the value of p1: ");
scanf("%d", &p1);
printf("Enter the valeu of q1: ");
scanf("%d", &q1);
n1 = p1*q1;
phi1 = (p1 - 1) * (q1 - 1);
printf("Enter the value of e: ");
scanf("%d", &e1);
d1 = get_d(e1, phi1);
printf("Public Key: (n = %d, e = %d)\n", n1, e1);
printf("Private Key: (n = %d, d = %d)\n", n1, d1);
printf("Enter message to encrypt: ");
scanf("%d", &m1);
c1 = modular_exponentiation(m1, e1, n1);
printf("Encrypted message is: %d\n", c1);
m1 = modular_exponentiation(c1, d1, n1);
printf("Message is decrypted to %d\n", m1);
return 0;
}
OUTPUT
