Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: алгоритм rsa  (Прочитано 8068 раз)
0 Пользователей и 1 Гость смотрят эту тему.
alliance
Постоялец

ru
Offline Offline

« : 09-03-2010 17:50 » new

Здравствуйте пишу реализацию алгоритма на с++, открытый и закрытый ключ вычисляет правильно (проверил), простые числа находит и перемножает, но декодировать не хочет, не могу понять, где ошибка
Код:
#include <iostream>
#include <conio.h>
#include <math.h>
#include <vector>
#include <string>
#include <time.h>

class Shifr
{
private:
enum{N=100};
unsigned long long p;
unsigned long long q;
unsigned long long n;
unsigned long long d;
unsigned long long e;
//std::string str;
long str;
std::vector<unsigned long long > vec_snach;
std::vector<unsigned long long> p_num;
public:
Shifr(){p=q=n=d=e=0;}
void coding(unsigned long long m);
void encoding(unsigned long long c);
void vvod();
void vivod();
void resheto();
bool find_n();
void find_e();
unsigned long long gcd(unsigned long long x,unsigned long long y);
unsigned long long modinv(unsigned long long e,unsigned long long n); 
unsigned long long modpow(const unsigned long long & ib,const unsigned long long& ie,const unsigned long long& im);
};

void Shifr::vvod()
{
std::cout<<"\nwwedite stroku dlya shifrowaniya ";
//std::getline(std::cin,str);
std::cin>>str;

resheto();

/*for(int i=0;i<str.size();++i)
{
coding(str[i]);
}
*/
coding(str);
}
void Shifr::vivod()
{
unsigned char ch=0;

for(int i=0;i<vec_snach.size();++i)
encoding(vec_snach[i]);

for(int i=0;i<p_num.size();++i)
{
ch=p_num[i];
std::cout<<p_num[i];
std::cout<<ch;
}
}

void Shifr::coding(unsigned long long m)
{
long long num = (long long (pow(long double(m),long double(e))))%n;
vec_snach.push_back(num);
//vec_snach.push_back(modpow(m,d,n));
std::cout<<vec_snach.back()<<" ";
}

void Shifr::encoding(unsigned long long c)
{
long long num = (long long (pow(long double(c),long double(d))))%n;
p_num.push_back(num);
//p_num.push_back(modpow(c,e,n));
}

void Shifr::resheto()
{

long mas[N];

srand(time(0));

for(int i=0;i<N;++i)
mas[i]=i;
mas[1]=0;
for(int i=2;i<N;++i)
{
if(mas[i]!=0)
for(int j=i*2;j<N;j+=i)
mas[j]=0;
}

for(int i=0;i<N;++i)
if(mas[i]!=0)
p_num.push_back(mas[i]);

while(true)
{
if(find_n())
break;
}

int buf=5;
while (true)
{
while(true)
{
if(gcd(buf,(p-1)*(q-1))==1)
{
e=buf;
break;
}
buf+=2;
}

d=modinv(e,(p-1)*(q-1));
if(d<LONG_MAX)
break;
buf+=2;
}
p_num.clear();



}

bool Shifr::find_n()
{
int i=rand()%p_num.size();
int j=rand()%p_num.size();
if(i==j)
return false;
else
{
p=p_num[i];
q=p_num[j];
n=p*q;

return true;
}
}

unsigned long long Shifr::gcd(unsigned long long x, unsigned long long y)
{
while(true)
{
if(y==0)
return x;
x=x%y;
if(x==0)
return y;
y=y%x;
}
}

unsigned long long Shifr::modinv(unsigned long long e,unsigned long long n)
{
unsigned long long b = n;
unsigned long long c = e;
unsigned long long i=0;
unsigned long long j=1;

while(c!=0)
{
unsigned long long x= b/c;
unsigned long long y= b%c;
b=c;
c=y;
y=j;
j=i-j*x;
i=y;
}
if(i<0)
i+=n;
return i;
}
/*
unsigned long longShifr::modinv(unsigned long longe,unsigned long longn)
{
unsigned long longa=e,b=n+1;

while(true)
{
if((a*b)%n==1)
return b;
else
b+=n;
}
}
*/

unsigned long long Shifr::modpow(const unsigned long long & ib,const unsigned long long& ie,const unsigned long long& im )
{
unsigned long long result=1;
unsigned long long e =ie;
unsigned long long b =ib;

while(e>0)
{
if(e%2==0)
result=(result*b)%im;

e>>=1;
b=(b*b)%im;
}
return result;
}
Записан
Денисrf
Постоялец

ru
Offline Offline
Пол: Мужской

« Ответ #1 : 30-03-2010 19:22 » 

Ну ты уж извени, но в код я не полез. По опыту - проверь:
- Соблюдаешь ли ты словие при генерации случайного ОК (1<OK<=(F(p-1)(q-1)), F- http://algolist.manual.ru/maths/count_fast/phi_n.php и условие     НОД(ОК,F(n))=1
- Может ИМХО скорее всего при шифровке ошибка. Разбиваешь входную строку на части длинной N-1
-Верно ли функция шифрования устроина (Сi=Mi^OK(mod N))


Код блин можно и устать читать )))
Записан

Your password is personal - do not share it with anyone and make sure it is not easy to crack.
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #2 : 31-03-2010 03:43 » 

а чтобы в лазах не рябило от unsigned long long , делаем

typedef unsigned long long U64;

и дальше пользуемся U64 Улыбаюсь
Записан

Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines