Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Quetzal
0 / 0 / 0
Регистрация: 19.08.2011
Сообщений: 71
#1

Кто-нибудь найдите ошибку в RSA кодировании!!! - C++

06.12.2011, 01:24. Просмотров 1007. Ответов 18
Метки нет (Все метки)

Стандартная задача. Вводятся p,q, e, d. Нужно по формуле ks=ks*c*Mod n, где n=p*q, c-ASCII код симвода. загвоздка в том что текста вводится из файла txt. Посмотрите почему раскодирует и кажется кодирует не так?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <locale.h>
#include <cmath>
#include <fstream>
#include <string>
using namespace std;
 
int main( )
{
    setlocale(LC_ALL, "russian");
    int q=19, p=13;
    int n, t, openExponent=0, ks=1, d=0;
    int A[100];
    char s;
    char B[100];
//  int code;
    cout<<"=============================="<<endl<<endl;
 
    cout<<"1. ÂûáèðГ*ГҐГ¬ äâГ* ïðîñòûõ Г·ГЁГ±Г«Г* p = "<<p<<", q = "<<q<<endl;
    n = p * q;
    cout<<"2. Âû÷èñëÿåì ìîäóëü n = p * q = "<<p<<" * "<<q<<" = "<<n<<endl;
    cout<<"3. Ââåäèòå îòêðûòûé êëþ÷ e = "<<endl;
    cin>>openExponent;
    cout<<"3. îòêðûòûé êëþ÷ e = "<<openExponent<<endl;
     cout<<"3. Ââåäèòå êëþ÷ Г°Г*ñøèôðîâêè d = "<<endl;
     cin>>d;
    cout<<"=============================="<<endl<<endl;
    
ifstream infile("file");
    
    if ( ! infile ) 
    {
        cerr << "ГЋГёГЁГЎГЄГ* îòêðûòèÿ âõîäГ*îãî ГґГ*éëГ*.\n";
        return -1;
    }
    string word, newword;
    infile >> word;
    cout << word << ' ';
    t=word.size();
    cout<<t<<endl;
for (int i=0; i<t; i++){
        A[i]= int(word[i]);
        cout<<"ASCII êîä ñòî÷êè ГІГҐГЄГ±ГІГ* "<<A[i];
        cout<<endl;
        for(int j=1; j<=openExponent; j++){
            ks=ks*A[i]%n;}
        s=char(ks);
        //cout<<"Г‡Г*øèôðîâГ*Г*Г*ûé ñèìâîë "<<s<<endl;
        newword=newword+s;      
    }
    cout<<newword<<endl;
    string unkeyword;
    cout<<endl<<"=============================="<<endl;
    ks=1;
    for (int i=0; i<newword.size(); i++){
        A[i]= int(newword[i]);
        cout<<"ASCII êîä ñòî÷êè ГІГҐГЄГ±ГІГ* "<<A[i];
        cout<<endl;
        for(int j=1; j<=d; j++){
            ks=ks*A[i]%n;}
        s=char(ks);
        //cout<<"ГђГ*ñøèôðîâГ*Г*Г*ûé ñèìâîë "<<s<<endl;
        unkeyword=unkeyword+s;      
    }
    cout<<unkeyword<<endl;
    system("pause");
    
        return 0;
        
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thinker
Эксперт C++
4220 / 2194 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.12.2011, 10:33     Кто-нибудь найдите ошибку в RSA кодировании!!! #2
Конечно, неправильно. вычисляете c^e (mod n), а потом обрезаете все до типа char - вот и данные тут же потеряли. Переменную ks надо каждый раз в цикле инициализировать единицей. Да и возведение в степень лучше бинарное использовать. Ваш алгоритм будет в лучшем случае работать (если ошибки устранить) для случая n<=256. Хотя, у вас p и q и так достаточно маленькие. Попробуйте с переменной ks разобраться
Quetzal
0 / 0 / 0
Регистрация: 19.08.2011
Сообщений: 71
06.12.2011, 11:04  [ТС]     Кто-нибудь найдите ошибку в RSA кодировании!!! #3
Сделала как вы сказали. но ответ все равно не расшифровывается=(
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <locale.h>
#include <cmath>
#include <fstream>
#include <string>
using namespace std;
 
int main( )
{
    setlocale(LC_ALL, "russian");
    int q=19, p=13;
    int n, t, e=0, ks=1, d=0;
    int A[100];
    char s;
    char B[100];
//  int code;
    cout<<"=============================="<<endl<<endl;
 
    cout<<"1. ÂûáèðГ*ГҐГ¬ äâГ* ïðîñòûõ Г·ГЁГ±Г«Г* p = "<<p<<", q = "<<q<<endl;
    n = p * q;
    cout<<"2. Âû÷èñëÿåì ìîäóëü n = p * q = "<<p<<" * "<<q<<" = "<<n<<endl;
    cout<<"3. Ââåäèòå îòêðûòûé êëþ÷ e = "<<endl;
    cin>>e;
    cout<<"3. îòêðûòûé êëþ÷ e = "<<e<<endl;
/*        cout<<"Г‚ ðåçóëüòГ*ГІГҐ ìû ïîëó÷èëè:"<<endl;
        cout<<" - îòêðûòûé êëþ÷ (e, n) = ("<<e<<", "<<n<<");"<<endl;*/
     cout<<"3. Ââåäèòå êëþ÷ Г°Г*ñøèôðîâêè d = "<<endl;
     cin>>d;
    cout<<"=============================="<<endl<<endl;
    
ifstream infile("file");
    
    if ( ! infile ) 
    {
        cerr << "ГЋГёГЁГЎГЄГ* îòêðûòèÿ âõîäГ*îãî ГґГ*éëГ*.\n";
        return -1;
    }
    string word, newword;
    infile >> word;
    cout << word << ' ';
    t=word.size();
    cout<<t<<endl;
for (int i=0; i<t; i++){
        A[i]= int(word[i]);
        cout<<"ASCII êîä ñòî÷êè ГІГҐГЄГ±ГІГ* "<<A[i];
        cout<<endl;
        ks=1;
        ks=A[i]^e%n;
        s=char(ks);
        //cout<<"Г‡Г*øèôðîâГ*Г*Г*ûé ñèìâîë "<<s<<endl;
        newword=newword+s;      
    }
    cout<<newword<<endl;
    string unkeyword;
    cout<<endl<<"=============================="<<endl;
    ks=1;
    for (int i=0; i<newword.size(); i++){
        A[i]= int(newword[i]);
        cout<<"ASCII êîä ñòî÷êè ГІГҐГЄГ±ГІГ* "<<A[i];
        cout<<endl;
        ks=1;
        ks=A[i]^d%n;
        s=char(ks);
        //cout<<"ГђГ*ñøèôðîâГ*Г*Г*ûé ñèìâîë "<<s<<endl;
        unkeyword=unkeyword+s;      
    }
    cout<<unkeyword<<endl;
    system("pause");
    
        return 0;
        
}
Quetzal
0 / 0 / 0
Регистрация: 19.08.2011
Сообщений: 71
06.12.2011, 11:09  [ТС]     Кто-нибудь найдите ошибку в RSA кодировании!!! #4
Вот скрин того что вывела прога.
Миниатюры
Кто-нибудь найдите ошибку в RSA кодировании!!!  
Thinker
Эксперт C++
4220 / 2194 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.12.2011, 11:11     Кто-нибудь найдите ошибку в RSA кодировании!!! #5
А зачем вы внутренний цикл убрали? он же нужен для возведения в степень. И надеюсь, что про ограничения на e и d помните:
http://www.cyberforum.ru/cgi-bin/latex.cgi?(e, \phi(n))=1
http://www.cyberforum.ru/cgi-bin/latex.cgi?ed \equiv 1 (mod \phi(n))
Quetzal
0 / 0 / 0
Регистрация: 19.08.2011
Сообщений: 71
06.12.2011, 11:31  [ТС]     Кто-нибудь найдите ошибку в RSA кодировании!!! #6
а по какой переменной будет суммирование?
и я чего-то не очень поняла про ограничение e и d. Поясите пожалуйста.
fasked
06.12.2011, 11:33
  #7

Не по теме:

Цитата Сообщение от Thinker Посмотреть сообщение
Ваш алгоритм будет в лучшем случае работать (если ошибки устранить) для случая n<=256.
А разве ключи "7" и "11" уже не в моде?

Quetzal
0 / 0 / 0
Регистрация: 19.08.2011
Сообщений: 71
06.12.2011, 11:35  [ТС]     Кто-нибудь найдите ошибку в RSA кодировании!!! #8
Цитата Сообщение от fasked Посмотреть сообщение

Не по теме:


А разве ключи "7" и "11" уже не в моде?

может и в моде. проверяют по ключам которые нам дали. А вы что скажите по поводу ошибок? я не очень понимаю что у меня не так.
Thinker
Эксперт C++
4220 / 2194 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.12.2011, 11:39     Кто-нибудь найдите ошибку в RSA кодировании!!! #9
Цитата Сообщение от fasked Посмотреть сообщение

Не по теме:


А разве ключи "7" и "11" уже не в моде?

Не по теме:

очень часто не понятно с каким настроением вы смеетесь.


Quetzal, у вас же в первой программе имеется внутренний цикл, отвечающий за возведение в степень, я про него говорю.
Quetzal
0 / 0 / 0
Регистрация: 19.08.2011
Сообщений: 71
06.12.2011, 11:55  [ТС]     Кто-нибудь найдите ошибку в RSA кодировании!!! #10
хорошо. а что с ограничением e и d.
можно как нибудь найти например d зная только е?
Thinker
Эксперт C++
4220 / 2194 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.12.2011, 11:58     Кто-нибудь найдите ошибку в RSA кодировании!!! #11
Цитата Сообщение от Quetzal Посмотреть сообщение
можно как нибудь найти например d зная только е?
Вам в теорию чисел, надо научиться решать сравнения.
Quetzal
0 / 0 / 0
Регистрация: 19.08.2011
Сообщений: 71
06.12.2011, 12:10  [ТС]     Кто-нибудь найдите ошибку в RSA кодировании!!! #12
а можете если вам не сложно написать программно формулу шифрования? а то по вашему сообщению я тогда вообще не понимаю откуда берется внутренний цикл когда мы все можем спокойно вычислить и без него.
Цитата Сообщение от Thinker Посмотреть сообщение
c^e (mod n),
Добавлено через 8 минут
на счет теории чисел согласна. мозг со временем в любом случае забывает все элементарное.
у меня есть скажем так точные значения для всех данных, но помогите, пожалуйста с формулой. я не понимаю какая она.
Thinker
Эксперт C++
4220 / 2194 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.12.2011, 12:50     Кто-нибудь найдите ошибку в RSA кодировании!!! #13
Цитата Сообщение от Quetzal Посмотреть сообщение
а можете если вам не сложно написать программно формулу шифрования?
Можно, НО если писать для общего случая, то нужна длинная арифметика. Если для маленьких чисел (стандартные типы), но как-то невесело. Нужно в любом случае вычислять значение функции Эйлера, искать взаимно простые числа, решать сравнение методом конечных цепных дробей, например, реализовывать быстрый алгоритм возведения в степень. Жаль на это время тратить.
fasked
Эксперт С++
4933 / 2513 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
06.12.2011, 12:52     Кто-нибудь найдите ошибку в RSA кодировании!!! #14
Цитата Сообщение от Thinker Посмотреть сообщение
Нужно в любом случае вычислять значение функции Эйлера, искать взаимно простые числа
Так им же генерацию ключей не надо писать. Только шифрование/расшифрование.
Thinker
Эксперт C++
4220 / 2194 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.12.2011, 13:02     Кто-нибудь найдите ошибку в RSA кодировании!!! #15
Цитата Сообщение от fasked Посмотреть сообщение
Так им же генерацию ключей не надо писать. Только шифрование/расшифрование.
Согласен, но ключи e и d подобрать надо. Зафиксировали, например, e, нужно проверить, что оно взаимно простое со значением функции Эйлера от n (она равна (p-1)(q-1)), потом надо решить сравнение
http://www.cyberforum.ru/cgi-bin/latex.cgi?ed \equiv 1(mod (p-1)(q-1)).
А потом уже просто шифрование и расшифрование. fasked, а если я, например, сам подберу ключи e и d, то это уже не шифрование будет, так как ключи то я знаю
fasked
Эксперт С++
4933 / 2513 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
06.12.2011, 13:05     Кто-нибудь найдите ошибку в RSA кодировании!!! #16
Цитата Сообщение от Thinker Посмотреть сообщение
Согласен, но ключи e и d подобрать надо. Зафиксировали, например, e, нужно проверить, что оно взаимно простое со значением функции Эйлера от n (она равна (p-1)(q-1)), потом надо решить сравнение
Цитата Сообщение от Quetzal Посмотреть сообщение
проверяют по ключам которые нам дали.
Я думаю, что числа из, например, методички, априори корректные.
Thinker
Эксперт C++
4220 / 2194 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.12.2011, 13:09     Кто-нибудь найдите ошибку в RSA кодировании!!! #17
Тогда там делов на пару минут, но под рукой нет компилятора, быть может, вечером, либо Вы, fasked, можете помочь, для Вас это совсем почти ничто
fasked
Эксперт С++
4933 / 2513 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
06.12.2011, 14:54     Кто-нибудь найдите ошибку в RSA кодировании!!! #18
Цитата Сообщение от Thinker Посмотреть сообщение
Тогда там делов на пару минут, но под рукой нет компилятора
Так скучно же. И неизвестно, что делать с переполнением стандартных типов. Если шифровать по одному байту, то n должно быть не меньше 256. У автора кстати не так.

Шифровать:
C++
1
cipher[i] = (unsigned)pow(open[i], e) % n;
Расшифровать:
C++
1
open[i] = (unsigned)pow(cipher[i], d) % n;
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.12.2011, 18:17     Кто-нибудь найдите ошибку в RSA кодировании!!!
Еще ссылки по теме:

Кто-нибудь знает, что это за ошибка? C++
C++ Кто-нибудь реализовывал класс множество?
C++ Кто нибудь, когда нибудь встречал Шрёдинбаг?
C++ Есть те, кто разбираются в алгоритме шифрования RSA?
не мог бы кто нибудь объяснить ошибку с темплейтами C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Thinker
Эксперт C++
4220 / 2194 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.12.2011, 18:17     Кто-нибудь найдите ошибку в RSA кодировании!!! #19
Цитата Сообщение от fasked Посмотреть сообщение
Так скучно же. И неизвестно, что делать с переполнением стандартных типов. Если шифровать по одному байту, то n должно быть не меньше 256. У автора кстати не так.

Шифровать:
C++
1
cipher[i] = (unsigned)pow(open[i], e) % n;
Расшифровать:
C++
1
open[i] = (unsigned)pow(cipher[i], d) % n;
Согласен, но контролировать переполнение можно проще, используя бинарный алгоритм возведения в степень.
Yandex
Объявления
06.12.2011, 18:17     Кто-нибудь найдите ошибку в RSA кодировании!!!
Ответ Создать тему
Опции темы

Текущее время: 19:53. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru