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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
SODJ
0 / 0 / 0
Регистрация: 18.05.2014
Сообщений: 13
#1

Шифрование RSA - C++

02.06.2014, 15:06. Просмотров 1907. Ответов 4
Метки нет (Все метки)

Доброго всем времени суток. Делаю курсовую работу по криптографии - реализация алгоритма RSA. Вот написал уже целый код, который работает при небольших значениях (их брал с вики).
Использую такие данные: p=3557 q=2579 d=3 e=6111579 исходный_текст=111111, шифрованный текст получается 4051753, собственно и расшифровка происходит тоже верно.
А вот когда уже беру числа из задания исходный_текст=2006201801310518 p=85785751 q=63284773, то уже получается неверно. Пожалуйста, помогите разобраться, в чём у меня проблема.
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <stdlib.h> 
#include <stdio.h>  
#include <time.h>
#include <math.h>
#include <locale.h>
#include <Windows.h>
 
using namespace System;
using namespace std;
 
long long p, q, n, m; 
long long rand_d, d, e, c;//c - для  вычисления целой части после деления
long long a, b, r;
long long E_matrix[2][2]={1,0,0,1}, B_matrix[2][2]={0,1,1,1}, C_matrix[2][2]; 
int i, j;
long long source_text=2006201801310518, shifro_text, deshifro_text;
 
int main(array<System::String ^> ^args)
{
    SetConsoleCP(1251);  //для работы русского языка + надо менять в консоли шрифт
    SetConsoleOutputCP(1251);
    p=85785751;//инициализация моих данных
    q=63284773;
    m=p*q;
    n=(p-1)*(q-1);
    cout<<"\nm="<<m<<", n="<<n;
    srand (time(NULL));
    while(1)
    {
    while (1) //бесконечный цикл. Если числа не взаимнопростые, то делаем новый рандом
    {
        rand_d=rand() %9000 +1000;
        cout<<"\nrand_d="<<rand_d;
        //Алгоритм Евклида
        a=n;
        b=rand_d;
        while (1) //бесконечный цикл
        {
            r=a%b;
            if (r==0)
                break;
            else
            {
                a=b;
                b=r;
            }
        }
        cout<<"\nr="<<r<<"\nb="<<b<<"\na="<<a;
        if (b>1)
            cout<<"\nЧисла не взаимно простые.";
        else
        {
            cout<<"\nЧисла взаимно простые.";
            break;
        }
    }
    d=rand_d;
    d=3553;//временная инициализация чтобы не гонять рандом
    cout<<"\nВыбраный ключ d="<<d;
    //модифицированный алгоритм Евклида для поиска ключа 'e'
    a=n;
    b=d;
    while (1)//бесконечный цикл
    {
        r=a%b;
        if (r==0)
            break;
        else
        {
            c=a/b;//целая часть от деления
            cout<<"\nq="<<c<<", r="<<r;//промежуточные значения для отладки
            B_matrix[1][1]=-c;//-q
            C_matrix[0][0]=E_matrix[0][0]*B_matrix[0][0]+E_matrix[0][1]*B_matrix[1][0];
            C_matrix[0][1]=E_matrix[0][0]*B_matrix[0][1]+E_matrix[0][1]*B_matrix[1][1];
            C_matrix[1][0]=E_matrix[1][0]*B_matrix[0][0]+E_matrix[1][1]*B_matrix[1][0];
            C_matrix[1][1]=E_matrix[1][0]*B_matrix[0][1]+E_matrix[1][1]*B_matrix[1][1];
            for (i=0;i<2;i++)
                for (j=0;j<2;j++)
                    E_matrix[i][j]=C_matrix[i][j];
            a=b;
            b=r;
        }
    }
    cout<<"\nX="<<E_matrix[0][1]<<", Y="<<E_matrix[1][1];
    if (E_matrix[1][1]<0)
        E_matrix[1][1]+=n;
    cout<<"\nX="<<E_matrix[0][1]<<", e="<<E_matrix[1][1];
    e=E_matrix[1][1];
    //проверка результатов
    cout<<"\n(e*d)%n="<<(e*d)%n;
    cout<<"\n(e*d)/n="<<(e*d)/n;
    if (((e*d)%n)==1)
        break;
    }
    _getch();
    //шифрование вариант с быстрым возведением в степень
    long long a,b;
    c=0;
    long long binary[100]; // для записи степени в двоичной форме
    a=d;
    for (i=0;a>0;i++)
    {
        binary[i]=a%2;
        //cout<<binary[i];
        a=(a-binary[i])/2;
        c++;
    }
    cout<<("\nrezultat =");
    for (i=0;i<c;i++)
        cout<<binary[i];
    long long itog=1,vozvodimoe_chislo=source_text, modul=m;
    for (i=c;i>-1;i--)
    {
        if (binary[i]==1)
        {
            itog=(((itog*itog)%modul)*vozvodimoe_chislo)%modul;
        }
        else
            itog=(itog*itog)%modul;
        if (itog<0)
        itog+=modul;
        cout<<"\nitog="<<itog;
    }
    shifro_text=itog;
    cout<<"\notvet="<<itog;
    cout<<"\nШифрованое сообщение (вариант 0): "<<shifro_text;
    
    //Дешифрование
    c=0;
    a=e;
    a=a%(modul-1);//сокращение степени
    cout<<"\na="<<a;
    for (i=0;a>0;i++)
    {
        binary[i]=a%2;
        a=(a-binary[i])/2;
        c++;
    }
    
    cout<<("\nrezultat =");
    for (i=0;i<c;i++)
        cout<<binary[i];
    itog=1;
    vozvodimoe_chislo=shifro_text; 
    for (i=c;i>-1;i--)
    {
        if (binary[i]==1)
        {
            itog=(((itog*itog)%modul)*vozvodimoe_chislo)%modul;
        }
        else
            itog=(itog*itog)%modul;
        if (itog<0)
        itog+=modul;
        cout<<"\nitog="<<itog;
    }
    deshifro_text=itog;
    cout<<"\notvet="<<itog;
    cout<<"\nДешифрованое сообщение (вариант 0): "<<deshifro_text;
        _getch();
    return 0;
}
Заранее благодарен за помощь! =)

Добавлено через 8 минут
Среда разработки VS 2012
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.06.2014, 15:06
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Шифрование RSA (C++):

RSA шифрование - C++
Здравствуйте уважаемые форумчане. Знаю, есть темы подобные моей, но использовать готовое, когда есть что-то свое, не хочется. ...

шифрование RSA - C++
Помогите пожалуйста с задачей: Составить программу на языке программирования С++, которая осуществляет шифрование информации по правилу...

RSA шифрование - C++
Народ кому не жалко выложите алгоритм шифрования методом RSA нужен самописный а не с помощью библиотек

Асимметричное шифрование, RSA - C++
Задача такая: для зашифровки текста нужно возвести число в большую степень и взять по нем модуль. Не могу никак реализовать больше, чем...

Шифрование файлов алгоритмом RSA - C++
Алгоритм шифрование написан шифрует пока только числа. Подкиньте идею как шифровать файлы. Я ни как не разберусь. Открывать их побитово и...

RSA Шифрование.Найдите ошибку пожалуйста - C++
уважаемые Гуру программисты найдите в этом коде ошибку заранее спасибо!!! #include &lt;iostream&gt; #include &lt;string&gt; using namespace std; ...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
OstapBender
583 / 521 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
02.06.2014, 16:59 #2
скорей всего где-то выходит за границы long long. демонстрируйте на небольших числах, либо используйте библиотеки для работы с большими числами...
SODJ
0 / 0 / 0
Регистрация: 18.05.2014
Сообщений: 13
02.06.2014, 18:26  [ТС] #3
Спасибо за ответ, а какие есть библиотеки, и какие использовать лучше/проще? Да и вообще как их правильно использовать, а то опыта у меня в этом маловато? (=

Добавлено через 20 минут
Попробовал подключить ntl, но походу дела что-то делаю не так.
Качаю от сюда - http://www.shoup.net/ntl/download.html
Папку include/ntl кладу в папку VC/include
Далее прописываю строку в проекте:
C++
1
#include <NTL/ZZ.h>
Пробую запустить, вылезают вот такие ошибки:
Миниатюры
Шифрование RSA  
OstapBender
583 / 521 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
02.06.2014, 18:56 #4
Сообщение было отмечено автором темы, экспертом или модератором как ответ
SODJ, из моего опыта я использовал только GMP
не скажу, что там супер удобный интерфейс (он С-стайл), но для не особо сложных целей подходит...
кстати RSA считается там как mpz_powm(res,v,e,n); как следует из википедия =)
правда подключение там не очень легкое. но если захочешь все же использовать то могу помочь:
http://rghost.net/56091446
хедеры и либу распаковывай в папку с исходным кодом и пиши сверху
C++
1
2
3
4
#include "config.h"
#include "gmp-mparam.h"
#include "gmp.h"
#pragma comment(lib, "gmp.lib")
код для теста:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main()
{
    mpz_t var, var2;
    mpz_init_set_str(var, "6123712312391231203162370123123712311273", 10);
    mpz_init_set_str(var2, "111111111", 10);
 
    mpz_t res;
 
    mpz_init(res);
 
    mpz_add(res, var, var2);
 
    printf("var + var2 = ");
    mpz_out_str(stdout, 10, res);
 
    mpz_clear(var);
    mpz_clear(var2);
    mpz_clear(res);
    getchar();
}
SODJ
0 / 0 / 0
Регистрация: 18.05.2014
Сообщений: 13
02.06.2014, 23:54  [ТС] #5
Вау, спасибо большое =) Только вот теперь что-то не могу понять, как правильно все математические операции привести к нужному типу (да и в целом мне пока не понятны такого рода махинации), чтобы MVS их не подчёркивала.
Цитата Сообщение от OstapBender Посмотреть сообщение
mpz_init_set_str(var, "6123712312391231203162370123123712311273", 10);
и что означает цифра 10 в конце?

Добавлено через 4 часа 22 минуты
OstapBender, Решил пока написать программу попроще с использованием gmp, но при компиляции теперь выдаются такие ошибки линковщика, не знаете в чём может проблема?
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
#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <time.h>
#include <locale.h>
#include <Windows.h>
#include "config.h"
#include "gmp-mparam.h"
#include "gmp.h"
#pragma comment(lib, "gmp.lib")
#pragma comment(linker, "/NODEFAULTLIB:MSVCRTD.lib") 
 
mpz_t p, q, n, m, k; 
mpz_t d, e;
 
mpz_t source_text, shifro_text, deshifro_text;
mpz_t odin, proverka_dlya_vihoda;
 
 
int main()
{
    SetConsoleCP(1251);  //для работы русского языка + надо менять в консоли шрифт
    SetConsoleOutputCP(1251);
    mpz_init_set_str (source_text, "2006201801310518",10);
    mpz_init_set_str (odin, "1",10);
    
    mpz_init_set_str (p, "85785751",10);//инициализация моих данных
    mpz_init_set_str (q, "63284773",10);
    mpz_mul(m,p,q);
    mpz_mul(n,p-1,q-1);
 
    mpz_init_set_str (d,"3553",10);
    std::cout<<"\nВыбраный ключ d=";
    mpz_out_str(stdout, 10, d);
 
    mpz_init_set_str (e,"80983218792217",10);
    std::cout<<"\nВыбраный ключ e=";
    mpz_out_str(stdout, 10, e);
 
    mpz_mul(k,e,d);
    mpz_mod (proverka_dlya_vihoda, k, n);
    if (proverka_dlya_vihoda==odin)
    {
        std::cout<<"\nРезультат проверки k=";
        mpz_out_str(stdout, 10, k);
    }
    _getch();
    mpz_powm (shifro_text, source_text, d, m);//Шифрование
    std::cout<<"\nШифрованое сообщение (вариант 0): ";
    mpz_out_str(stdout, 10, shifro_text);
 
    mpz_powm (deshifro_text, shifro_text, e, m);//Дешифрование
    std::cout<<"\nДешифрованое сообщение (вариант 2): ";
    mpz_out_str(stdout, 10, deshifro_text);
    _getch();
    return 0;
}
Лог построения:
1>------ Построение начато: проект: Test, Конфигурация: Debug Win32 ------
1> Test.cpp
1>MSVCMRTD.lib(mstartup.obj) : error LNK2020: эхЁрчЁх°хээр* ыхъёхьр (0A0000C7) __native_startup_state
1>MSVCMRTD.lib(mstartup.obj) : error LNK2020: эхЁрчЁх°хээр* ыхъёхьр (0A000134) __native_startup_lock
1>MSVCMRTD.lib(mstartup.obj) : error LNK2020: эхЁрчЁх°хээр* ыхъёхьр (0A000135) __native_dllmain_reason
1>MSVCMRTD.lib(mstartup.obj) : error LNK2001: эхЁрчЁх°хээ√щ тэх°эшщ ёшьтюы "___native_dllmain_reason"
1>MSVCMRTD.lib(mstartup.obj) : error LNK2001: эхЁрчЁх°хээ√щ тэх°эшщ ёшьтюы "___native_startup_state"
1>MSVCMRTD.lib(mstartup.obj) : error LNK2001: эхЁрчЁх°хээ√щ тэх°эшщ ёшьтюы "___native_startup_lock"
1>C:\Users\Gin\Documents\Visual Studio 2012\Projects\Test\Debug\Test.exe : fatal error LNK1120: эхЁрчЁх°хээ√ї тэх°эшї ¤ыхьхэЄют: 6
========== Построение: успешно: 0, с ошибками: 1, без изменений: 0, пропущено: 0 ==========



Изменил конфигурацию на Release и добавил
#pragma comment(linker, "/NODEFAULTLIB:msvcrt.lib")
Вот что получил опять.
1>MSVCMRT.lib(mstartup.obj) : error LNK2020: неразрешенная лексема (0A0000C6) __native_startup_state
1>MSVCMRT.lib(mstartup.obj) : error LNK2020: неразрешенная лексема (0A000131) __native_startup_lock
1>MSVCMRT.lib(mstartup.obj) : error LNK2020: неразрешенная лексема (0A000132) __native_dllmain_reason
1>MSVCMRT.lib(mstartup.obj) : error LNK2001: неразрешенный внешний символ "___native_dllmain_reason"
1>MSVCMRT.lib(mstartup.obj) : error LNK2001: неразрешенный внешний символ "___native_startup_state"
1>MSVCMRT.lib(mstartup.obj) : error LNK2001: неразрешенный внешний символ "___native_startup_lock"
1>C:\Users\Gin\Documents\Visual Studio 2012\Projects\Test\Release\Test.exe : fatal error LNK1120: неразрешенных внешних элементов: 6
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.06.2014, 23:54
Привет! Вот еще темы с ответами:

Шифрование/дешифрование методом RSA с открытым ключом. С++ - C++
Помогите, пожалуйста, написать программу. Задали задание, а я совершенно не понимаю С++, как это сделать. :cry::cry::cry: Основные...

RSA - C++
бьюсь головой об стол с перерывами на обед... вот код: bool prost(int z) { for(int i=2; i&lt;=sqrt((float)z); i++) if(z%i == 0) ...

PolarSSL RSA - C++
Помогите разобраться с криптобиблиотеками PolarSSL (сейчас она уже называется mbed TLS), а именно с библиотекой RSA. Уже который день никак...

RSA - иероглифы - C++
Привет всем! Возникла проблема. Есть программа на RSA (честно, помогали люди) - но почему - то при шифровании выводит иероглифы, и мне...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
02.06.2014, 23:54
Ответ Создать тему
Опции темы

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