Criptosistemul RSA

1.  Scurt istoric

             Algoritmul RSA (Rivest-Shamir-Adleman) a fost inventat de Ron Rivest, Adi Shamir et Leonard Adleman în 1977 şi este proprietate a societăţii americane RSA Data Security. Odată cu acest algoritm, părăsim zona algoritmilor istorici, uşor de supus criptanalizei.

             RSA face parte din clasa algoritmilor de criptare cu cheie publică ce au drept principală caracteristică existenţa a două chei: o cheie publică ce poate fi cunoscută de orice expeditor şi o cheie privată cunoscută doar de destinatar.

Din punct de vedere matematic, algoritmii de criptare cu două chei sunt denumiţi algoritmi asimetrici. Prin contrast, toţi algoritmii studiaţi până acum, vor fi numiţi algoritmi de criptare simetrici.

2.  Descrierea algoritmului

Să presupunem că două persoane, Bob şi Alice doresc să comunice într-un mod cât mai sigur mesaje secrete. Există însă şi o treia persoană, Eve, care doreşte să intercepteze şi să decripteze traficul de mesaje dintre Bob şi Alice. Alice şi Bob pot fi oameni de afaceri aflaţi la distanţă, avioane aflate în zbor sau chiar doi prieteni ce doresc să comunice într-un mod cât mai privat. În nici unul din cazuri Eve nu poate fi oprită să  ”asculte” traficul  radio sau cel de pe internet.

2.1 Generarea cheilor

1. Generaţi 2 numere prime p şi q cât mai mari
2. Fie n = p * q
3. Fie m = (p-1)*(q-1)
4. Alegeţi e astfel încât cmmdc(e,m) = 1
5. Găsiţi d astfel încât (d*e) % m = 1

Se vor publica cheile publice: e şi n.

Se vor păstra cheile private: d şi n.

2.2 Criptarea RSA

           C = M^e % n,

Unde:

• M = Mesaj
• e şi n sunt cheia publică
• C = CipherText (mesajul criptat)

2.3 Decriptarea RSA

M = C^d % n

Unde:

• C = CipherText
• d şi n sunt cheia privată
• M  = Mesajul initial

2.4    Dezavantaje ale algoritmului RSA:

• După cum se poate observa şi din descrierea algoritmului, RSA criptează numere şi nu litere. Pentru a cripta secvenţe de text sau imagini, va trebui sa aplicăm algoritmul pentru fiecare octet în parte. După cum am văzut deja, acest tip de criptare poate uşura foarte mult munca unui criptanalist care utilizează testul Kasiski şi poate conduce în cele din urmă la aflarea cheii private. Pentru a evita astfel de situaţii, de obicei, criptarea RSA mai introduce şi octeţi cu valori aleatorii.
• Din cauza complexităţii algoritmului de criptare / decriptare, RSA este considerat lent în comparaţie cu algoritmii simetrici de criptare.

2.5     Implementarea algoritmul RSA:

Cod Sursa C++

#include "stdafx.h"
#include <iostream>
#include <math.h>
#include <string.h>
#include <stdlib.h>
 
using namespace std;
 
long int p, q, n, t, flag, e[100], d[100], temp[100], j, m[100], en[100], i;
char msg[100];
int prime(long int);
void ce();
long int cd(long int);
void encrypt();
void decrypt();
 
int prime(long int pr)
 
{
	    int i;
	    j = sqrt(pr);
	    for (i = 2; i <= j; i++)
		    {
		        if (pr % i == 0)
			            return 0;
		    }
	    return 1;
}
 
int main()
{
	    cout << "\nENTER FIRST PRIME NUMBER\n";
	    cin >> p;
	    flag = prime(p);
	    if (flag == 0)
		    {
		        cout << "\nWRONG INPUT\n";
		        exit(1);
		    }
	    cout << "\nENTER ANOTHER PRIME NUMBER\n";
	    cin >> q;
	    flag = prime(q);
	    if (flag == 0 || p == q)
		    {
		        cout << "\nWRONG INPUT\n";
		        exit(1);
		    }
	    cout << "\nENTER MESSAGE\n";
	    fflush(stdin);
	    cin >> msg;
	    for (i = 0; msg[i] != NULL; i++)
		        m[i] = msg[i];
	    n = p * q;
	    t = (p - 1) * (q - 1);
	    ce();
	    cout << "\nPOSSIBLE VALUES OF e AND d ARE\n";
	    for (i = 0; i < j - 1; i++)
		        cout << e[i] << "\t" << d[i] << "\n";
	    encrypt();
	    decrypt();
	    return 0;
}
 
void ce()
{
	    int k;
	    k = 0;
	    for (i = 2; i < t; i++)
		    {
		        if (t % i == 0)
			            continue;
		        flag = prime(i);
		        if (flag == 1 && i != p && i != q)
			        {
			            e[k] = i;
			            flag = cd(e[k]);
			            if (flag > 0)
				            {
				                d[k] = flag;
				                k++;
				            }
			            if (k == 99)
				                break;
			        }
		    }
}
 
long int cd(long int x)
{
	    long int k = 1;
	    while (1)
		    {
		        k = k + t;
		        if (k % x == 0)
			            return (k / x);
		    }
}
 
void encrypt()
{
	    long int pt, ct, key = e[0], k, len;
	    i = 0;
	    len = strlen(msg);
	    while (i != len)
		    {
		        pt = m[i];
		        pt = pt - 96;
		        k = 1;
		        for (j = 0; j < key; j++)
			        {
 
			            k = k * pt;
 
			            k = k % n;
 
			        }
		        temp[i] = k;
		        ct = k + 96;
		        en[i] = ct;
		        i++;
		    }
	    en[i] = -1;
	    cout << "\nTHE ENCRYPTED MESSAGE IS\n";
	    for (i = 0; en[i] != -1; i++)
		        printf("%c", en[i]);
	}
 
void decrypt()
{
	    long int pt, ct, key = d[0], k;
	    i = 0;
	    while (en[i] != -1)
		    {
		        ct = temp[i];
		        k = 1;
		        for (j = 0; j < key; j++)
			        {
			            k = k * ct;
			            k = k % n;
			        }
		        pt = k + 96;
		        m[i] = pt;
		        i++;
		    }
	    m[i] = -1;
	    cout << "\nTHE DECRYPTED MESSAGE IS\n";
	    for (i = 0; m[i] != -1; i++)
		        printf("%c", m[i]);
		system("pause");
}

 Rezultat: