Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы
Алгоритм RSA
В этой статье рассмотрим еще один один алгоритм шифрования — алгоритм RSA. Будет приведено описание и программная реализация на языке программирования C#.
Алгоритм RSA. Описание
RSA (аббревиатура от фамилий создателей: Rivest, Shamir и Adleman) — один из самых популярных алгоритмов шифрования. Сначала приведем несколько определений:
mod — операция взятия остатка от деления.
Взаимно простыми называются такие числа, которые не имеют между собой ни одного общего делителя, кроме единицы.
Шаги алгоритма RSA
Теперь опишем последовательность шагов алгоритма RSA:
- выбрать два больших простых числа p и q;
- вычислить: n = p ⋅ q, m = (p — 1) ⋅ (q — 1);
- выбрать случайное число d, взаимно простое с m;
- определить такое число e, для которого является истинным выражение: (e ⋅ d) mod (m) = 1;
- числа e и n — это открытый ключ, а числа d и n — это закрытый ключ;
На практике это означает следующее: открытым ключом зашифровывают сообщение, а закрытым — расшифровывают. Пара чисел закрытого ключа держится в секрете.
Алгоритм шифрования RSA для начинающих. Часть 1
- разбить шифруемый текст на блоки, каждый из которых может быть представлен в виде числа M(i);
Обычно блок берут равным одному символу и представляют этот символ в виду числа — его номера в алфавите или кода в таблице символов (например ASCII или Unicode).
- шифрование алгоритмом RSA производится по формуле: C(i) = (M(i) e ) mod n;
- расшифровка сообщения производится с помощью формулы: M(i) = (C(i) d ) mod n.
Алгоритм RSA. Программная реализация
Программа для шифрования алгоритмом RSA имеет интерфейс, представленный на рисунке 1.
Рисунок 1. Пользовательский интерфейс программы
В программе будем использовать следующий алфавит:
Источник: vscode.ru
Реализация алгоритма RSA на C
RSA — это асимметричный криптографический алгоритм, используемый современными компьютерами для шифрования и дешифрования сообщений. Асимметричный означает, что есть два разных ключа. Это также называется криптографией с открытым ключом, потому что один из ключей может быть передан кому угодно. Другой ключ должен быть закрытым.
В этой статье не рассматривается работа алгоритма RSA. Мы предлагаем пройти простое объяснение, данное на Wikipedia для подробного пошагового объяснения.
Реализация:
Ниже приведена реализация криптографического алгоритма RSA на C. Программа ожидает входной файл, input.txt , который должен содержать обычный текст, и генерирует выходной файл, decipher.txt , который содержит наш расшифрованный текст. Он также генерирует промежуточный файл, cipher.txt , который содержит зашифрованный текст в битах.
Алгоритм шифрования RSA
Источник: www.techiedelight.com
Русские Блоги
Простая реализация алгоритма шифрования RSA на c ++
Нажмите, чтобы открыть оригинал
RSA — это алгоритм асимметричного шифрования, который широко используется в сфере открытых ключей и электронной коммерции. Он основан на очень простом факте теории чисел: два простых числа легко умножить, но сложно разложить произведение двух простых чисел на множители. Принцип больше не поясняется, я расскажу о процессе программной реализации алгоритма.
1.
Процесс шифрования и дешифрования RSA основан на следующей форме, где открытый текст — M, зашифрованный текст — C, открытый ключ PU = и ключ PR = .
1. Подготовительная работа, выберите два больших простых числа p и q, вычислите произведение n чисел p и q, вычислите произведение p-1 и q-1, выберите число e, которое является взаимно простым с произведением p-1 и q-1, Рассчитать d
2. Процесс шифрования
3. Процесс расшифровки
Программа не генерировала большие простые числа, но перечисляла простые числа в пределах 1000, случайным образом выбирала два простых числа p и q, вычисляла e и d с помощью алгоритма расширения Удридиана и использовала метод повторяющихся квадратов для питания чисел
2. Блок-схема программы
#include #include #include #include #include using namespace std; int Plaintext [100]; // Открытый текст long long Ciphertext [100]; // Зашифрованный текст int n, e = 0, d; // Двоичное преобразование int BianaryTransform(int num, int bin_num[]) < int i = 0, mod = 0; // Преобразуется в двоичный, обратный временно сохраняется в массиве temp [] while(num != 0) < mod = num%2; bin_num[i] = mod; num = num/2; i++; >// Возвращает количество цифр в двоичных числах return i; > // Повторное возведение в квадрат в степень long long Modular_Exonentiation(long long a, int b, int n) < int c = 0, bin_num[1000]; long long d = 1; int k = BianaryTransform(b, bin_num)-1; for(int i = k; i >= 0; i—) < c = 2*c; d = (d*d)%n; if(bin_num[i] == 1) < c = c + 1; d = (d*a)%n; >> return d; > // Генерация простых чисел в пределах 1000 int ProducePrimeNumber(int prime[]) < int c = 0, vis[1001]; memset(vis, 0, sizeof(vis)); for(int i = 2; i return c; > // Расширенный алгоритм Евклида int Exgcd(int m,int n,int int x1,y1,x0,y0, y; x0=1; y0=0; x1=0; y1=1; x=0; y=1; int r=m%n; int q=(m-r)/n; while(r) < x=x0-q*x1; y=y0-q*y1; x0=x1; y0=y1; x1=x; y1=y; m=n; n=r; r=m%n; q=(m-r)/n; >return n; > // Инициализация RSA void RSA_Initialize() < // Вынимаем простые числа в пределах 1000 и сохраняем их в массиве prime [] int prime[5000]; int count_Prime = ProducePrimeNumber(prime); // Случайно возьмем два простых числа p, q srand((unsigned)time(NULL)); int ranNum1 = rand()%count_Prime; int ranNum2 = rand()%count_Prime; int p = prime[ranNum1], q = prime[ranNum2]; n = p*q; int On = (p-1)*(q-1); // Используем расширенный алгоритм Евклида, чтобы найти e, d for(int j = 3; j < On; j+=1331) < int gcd = Exgcd(j, On, d); if( gcd == 1 d >0) < e = j; break; >> > // шифрование RSA void RSA_Encrypt() < cout// Расшифровка RSA void RSA_Decrypt() < int i = 0; for(i = 0; i < 100; i++) Ciphertext[i] = Modular_Exonentiation(Ciphertext[i], d, n); cout// Инициализация алгоритма void Initialize() < int i; srand((unsigned)time(NULL)); for(i = 0; i < 100; i++) Plaintext[i] = rand()%1000; coutint main()
результат операции:
Источник: russianblogs.com