hack rsa

#include <iostream>
#include <cmath>
#include <string>
using namespace std;


/*
*
Алгоритм отражает процесс генерации открытого и закрытого ключей для шифрования RSA, процесс шифрования и дешифрования сообщения с использованием этих ключей,
а также демонстрирует уязвимость данного алгоритма к взлому(в случае использования маленьких чисел) методом факторизации
*
Факторизация – процесс разложения числа на простые множители.
НОД – наибольший общий делитель.
Числа a и b называются взаимно простыми, если НОД этих чисел равен 1.
Функция Эйлера φ(n) – функция, равная количеству натуральных чисел, меньших n и взаимно простых с ним.

*/


// Функция для проверки, является ли число простым
bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}


// Функция для вычисления наибольшего общего делителя двух чисел с использованием алгоритма Евклида
int calculateNOD(int a, int b, int& x, int& y) {
    //Базовый случай : если одно из чисел равно нулю, возвращаем другое число как НОД,
    // устанавливаем значения коэффициентов расширенного алгоритма Евклида и завершаем рекурсию.
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    // Рекурсивный случай: вычисляем НОД для чисел b и a % b.
    //x1, y1 временные переменные для коэффициентов расширенного алгоритма Евклида
    int x1, y1;
    int nod = calculateNOD(b, a % b, x1, y1);
    // Вычисляем коэффициенты расширенного алгоритма Евклида для чисел a и b.
    x = y1;
    y = x1 - (a / b) * y1;
    // Возвращаем НОД(a, b)
    return nod;
}

// Функция для вычисления модулярного обратного 'publicKeyExponent' по модулю 'phi'
// phi - это такое число x, что (publicKeyExponent * x) mod phi = 1.

int calculateModInverse(int publicKeyExponent, int phi) {
    int x, y;
    // Вычисляем наибольший общий делитель с использованием алгоритма Евклида
    int nod = calculateNOD(publicKeyExponent, phi, x, y);
    // Если НОД(publicKeyExponent, phi) не равен 1, то обратного значения не существует по модулю m
    if (nod != 1) {
        throw runtime_error("Обратное значение не существует");
    }
    else {
        //(x % m + m) % m, чтобы результат был положительный(если х отриц)
        return (x % phi + phi) % phi;
    }
}

// Функция для генерации открытого и закрытого ключей для шифрования RSA

void generateRSAKeys(int prime1, int prime2, int& publicKeyExponent, int& privateKeyExponent, int& modulus) {
    // Вычисляем модуль как произведение двух простых чисел
    modulus = prime1 * prime2;
    int phi = (prime1 - 1) * (prime2 - 1);// Вычисляем значение функции Эйлера от модуля

    // Выбор открытого экспонента 'e'
    publicKeyExponent = 2; // Начинаем с общего выбора для e
    int x, y; // переменные для расширенного алгоритма Евклида

    // Пока НОД(publicKeyExponent, phi) не равен 1, увеличиваем publicKeyExponent.
    while (calculateNOD(publicKeyExponent, phi, x, y) != 1) {
        publicKeyExponent++;
    }
    // Вычисляем закрытый экспонент 'd' как модуль обратного 'e' по модулю phi
    privateKeyExponent = calculateModInverse(publicKeyExponent, phi);
}

// Функция для шифрования сообщения с использованием открытого ключа (e, n)
int encrypt(int message, int publicKeyExponent, int modulus) {
    int result = 1;
    for (int i = 0; i < publicKeyExponent; i++) {
        result = (result * message) % modulus;
    }
    return result;
}

// Функция для дешифрования с использованием закрытого ключа (d, n)
int decrypt(int ciphertext, int privateKeyExponent, int modulus) {
    int result = 1;
    for (int i = 0; i < privateKeyExponent; i++) {
        result = (result * ciphertext) % modulus;
    }
    return result;
}


// Функция для факторизации числа
void factorize(int n, int ciphertext, int publicKeyExponent) {
    for (int i = 2; i <= n / 2; i++) {
        if (n % i == 0 && isPrime(i) && isPrime(n / i)) {
            //с помощью них можем попробовать узнать приватный ключ
            cout << "Множители модуля, которые мы узнали с помощью факторизации: " << i << " и " << n / i << endl<<endl;
            // Здесь вычисляем закрытый ключ
            int prime1 = i;
            int prime2 = n / i;
            int modulus = prime1 * prime2;
            int phi = (prime1 - 1) * (prime2 - 1);
            int x, y;
            int privateKeyExponent = calculateModInverse(publicKeyExponent, phi);

            //
            cout << "Предполагаемый закрытый ключ (исходя из метода факторизации): {" << privateKeyExponent << ", " << modulus << "}" << std::endl;
            //
            cout << "Предполагаемое дешифрованное сообщение: " << decrypt(ciphertext, privateKeyExponent, modulus) << endl;
            return;
        }
    }
    cout << "Не удалось выполнить факторизацию." << std::endl;
}


// Функция для хэширования цифрового сообщения
//фиксированная длина✅
//Хеш должен быть быстр в вычислении и обладать свойством нереверсивности, то есть невозможности восстановления исходных данных из хеш - кода✅
int hashMessage(int message) {
    // Преобразуем сообщение в его строковое представление
    string messageStr = to_string(message);
    // Вычисляем сумму цифр сообщения
    int sum = 0;
    for (char digit : messageStr) {
        sum += (digit - '0'); // Преобразуем символ в число и добавляем к сумме
    }

    // Приводим сумму к фиксированной длине 2
    while (sum >= 100) {
        sum = (sum / 10) + (sum % 10); // Суммируем цифры числа
    }
    while (sum < 10) {
        sum=sum*sum;
    }
    return sum;
}

int main() {
    setlocale(LC_ALL, "Russian");
    // два простых числа
    int prime1 = 11;
    int prime2 = 13;
    //cin >> prime1;
    //cin >> prime2;
    int modulus, publicKeyExponent, privateKeyExponent;

    // Генерируем открытый и закрытый ключи для шифрования RSA
    generateRSAKeys(prime1, prime2, publicKeyExponent, privateKeyExponent, modulus);

    cout << "Открытый ключ: {" << publicKeyExponent << ", " << modulus << "}" << endl;
    cout << "Закрытый ключ: {" << privateKeyExponent << ", " << modulus << "}" << endl;

    // сообщение для шифрования, оно должно быть меньше 143(тк есть зависимость от модуля)для других чисел-другие ограничения
    int message = 141;

    // Шифруем хешированное сообщение
    int hashedMessage = hashMessage(message);
    cout << "Хэш сообщения: " << hashedMessage << endl;

    // Шифруем сообщение
    int ciphertext = encrypt(hashedMessage, publicKeyExponent, modulus);
    // Дешифруем
    int decryptedMessage = decrypt(ciphertext, privateKeyExponent, modulus);

    // Выводим исходное сообщение
    cout << "Исходное сообщение: " << message << endl<<endl;
    factorize(modulus, ciphertext, publicKeyExponent);

    // Выводим зашифрованное хешированное сообщение
    cout <<endl<< "Зашифрованное хешированное сообщение: " << ciphertext << endl;
    // Выводим дешифрованное сообщение
    cout << "Дешифрованное хешированное сообщение: " << decryptedMessage << endl << endl;

    // Проверяем, что расшифрованный хэш соответствует исходному хэшу
    if (decryptedMessage == hashedMessage) {
        cout << "Расшифрованный хэш соответствует исходному хэшу. Целостность данных подтверждена." << endl;
    }
    else {
        cout << "Расшифрованный хэш не соответствует исходному хэшу. Целостность данных нарушена." << endl;
    }

    return 0;
}