RSA C: алгоритм шифрования и дешифрования данных

RSA (Rivest-Shamir-Adleman) является криптографическим алгоритмом, который используется для шифрования и дешифрации информации, а также для цифровой подписи. RSA основан на сложности задачи факторизации больших чисел, и именно это его основное преимущество перед другими алгоритмами.

Вот пример кода на языке программирования C, который иллюстрирует основную работу алгоритма RSA:

c
#include 
#include 
#include 
int isPrime(int num) {
    int i;
    for (i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) {
            return 0;
        }
    }
    return 1;
}
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}
int main() {
    int p = 17;  // простое число
    int q = 11;  // другое простое число
    int n = p * q;  // произведение p и q
    int phi = (p - 1) * (q - 1);  // значение функции Эйлера
    int e = 0;
    for (int i = 2; i < phi; i++) {
        if (gcd(i, phi) == 1 && isPrime(i) == 1) {
            e = i;  // находим открытый ключ e
            break;
        }
    }
    int d;  // секретный ключ
    int k = 2;
    while (1) {
        d = (k * phi + 1) / e;
        if (isPrime(d) == 1) {
            break;
        }
        k++;
    }
    int message = 88;  // исходное сообщение
    int encrypted = pow(message, e);  // шифрование сообщения
    int decrypted = pow(encrypted, d);  // дешифрование сообщения
    printf("Исходное сообщение: %d\n", message);
    printf("Зашифрованное сообщение: %d\n", encrypted);
    printf("Расшифрованное сообщение: %d\n", decrypted);
    return 0;
}

В данном примере используются два простых числа `p` и `q`, которые перемножаются для получения `n`. Затем вычисляется значение функции Эйлера `phi`, а затем находится открытый ключ `e`, который должен быть взаимнопростым с `phi` и простым числом. Секретный ключ `d` находится с помощью расширенного алгоритма Евклида.

Исходное сообщение `message` затем шифруется путем возведения в степень `e` и берется остаток от деления на `n`. Зашифрованное сообщение `encrypted` дешифруется путем возведения в степень `d` и берется остаток от деления на `n`.

В итоге выводятся исходное сообщение, зашифрованное сообщение и расшифрованное сообщение.