VPF::RSA с длинными числами на C++ - Форум программистов

Catherine92

Дата 12.12.2011, 02:42 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 4
Регистрация: 12.12.2011
Где: Санкт-Петербург

Репутация: нет
Всего: нет

Помогите сформировать программу пожалуйста.

Задание:Задача заключается в шифровании (или дешифровании) данных с помощью алгоритма RSA. Во входном файле rsa.in находится три строки. На первой строке находятся два числа n и d. На второй строке находится число k. На третьей строке находится k кодированных чисел a_0 a_1 .. a_(k-1), где k=0..k В выходной файл rsa.out необходимо вывести k дешифрованных (или все-таки шифрованных?) чисел.

Это я сделала считывание данных из файла

Код

#include <fstream>
#include <stdio.h>
#include <cstdlib>
#include <iostream>
using namespace std;
int main()
{
int D,N,K;
ifstream in("in.txt");
ofstream of("out.txt");
in>>D>>N;
in>>K;
int* cAr = new int[K];
for(int i = 0; i<k;>>cAr;
}
return 0;
}

Ввод обычного числа в длинное, для дальнейших опреаций..

Код

BigInt A(countOfNumbers(a1));
A.Size=countOfNumbers(a1);
int a2 = a1;
for(int i=0; i<countofnumbers(a1);>=(short)(a2);
a2/=10;
}

возведения в степень, неявно использующий двоичное представление(вычисляющий его на лету) и ненуждающийся в long2binary():

Код

long powmod(long a, long k, long n)
{
lоng b=1;

while (k) {
if (k%2==0) {
k /= 2;
a *= a; // [ a = (a*a)%n; ]
}
else {
k--;
b *= a; // [ b = (b*a)%n; ]
}
}
return b;
}

А как это объединить и заставить работать не знаю(

Модератор: не забываем пользоваться кнопочкой "Код"

Это сообщение отредактировал(а) bsa - 12.12.2011, 11:05

bsa

Дата 12.12.2011, 11:10 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

Не уверен, что тебе long подойдет для реализации алгоритма RSA. Обычно, используют числа с разрядностью 512 и выше (даже максимальный long long - только 64).

Почитай это: http://www.di-mgt.com.au/bigdigits.html

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

cutwater

Дата 12.12.2011, 13:52 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 592
Регистрация: 24.6.2008

Репутация: 2
Всего: 10

Я бы предложил использовать библиотеки которые включают в себя работу с большими числами.
Это GMP (http://gmplib.org/) и Miracl (http://www.shamus.ie/)

Если нужно решение данной задачи не в академических целях, то будет более правильно использовать уже реализованный алгоритм RSA, например в OpenSSL или Crypto++

--------------------

Catherine92

Дата 12.12.2011, 16:39 (ссылка)

(нет голосов)

Загрузка ...

Данная программа необходима для сдачи экзамена. Но к сожалею моих знаний на данный момент недостаточно для полного её написания( Поэтому и обратилась на форум.

bsa

Дата 12.12.2011, 17:41 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

Ничего себе экзамены...

Catherine92, я тебе дал ссылку на ПРОСТУЮ библиотеку больших чисел. Там среди прочего есть примеры расчета с ее помощью RSA. Посмотри, почитай. Возьми главное и напиши свою программу используя библиотеку, как подсказку.

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

Catherine92

Дата 12.12.2011, 17:43 (ссылка)

(нет голосов)

Загрузка ...

Спасибо, попробую)

cutwater

Дата 13.12.2011, 14:46 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 592
Регистрация: 24.6.2008

Репутация: 2
Всего: 10

Цитата(bsa @ 12.12.2011, 16:41

)

Ничего себе экзамены...

[offtop]
Да нормальные экзамены. Мы в свое время писали и библиотеки для работы с большими числами и реализации алгоритмов шифрования на них на лабораторных.

--------------------

Catherine92

Дата 13.12.2011, 23:03 (ссылка)

(нет голосов)

Загрузка ...

Код


#include <iostream>
#include <fstream>
 
 
unsigned long long coding(unsigned long long num, unsigned long long pow, unsigned long long mod)
{
    unsigned long long test;
    for(test = 1; pow; pow >>= 1)
    {
        if (pow & 1)
            test = (test * num) % mod;
        num = (num * num) % mod;
    }
 
    return test;
 
}
 
 
int main()
{
using namespace std;
 
 
ifstream in_stream;
ofstream out_stream;
 
unsigned long long n,d,k;
 
in_stream.open("rsa.in");
out_stream.open("rsa.out");
 
in_stream>>n;
in_stream>>d;
in_stream>>k;
 
unsigned long long *a=(unsigned long long*)malloc(k*sizeof(unsigned long long));
unsigned long long *deck=(unsigned long long*)malloc(k*sizeof(unsigned long long));
for (int i=0;i<k;i++)
in_stream>>a[i];
 
for (int i=0;i<k;i++)
deck[i]=coding(a[i], d, n);
 
for (int j=0;j<k;j++)
out_stream << deck[j] << " ";
 
in_stream.close();
out_stream.close();
free(a);
free(deck);
 
//system("PAUSE");
return 0;
}

может кому пригодиться

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »