Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement