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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
SODJ
 Аватар для SODJ
0 / 0 / 0
Регистрация: 18.05.2014
Сообщений: 9
02.06.2014, 15:06     Шифрование RSA #1
Доброго всем времени суток. Делаю курсовую работу по криптографии - реализация алгоритма 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
Посмотрите здесь:

RSA шифрование C++
RSA Шифрование.Найдите ошибку пожалуйста C++
C++ шифрование RSA
C++ RSA
C++ шифр RSA
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
OstapBender
 Аватар для OstapBender
581 / 519 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
02.06.2014, 16:59     Шифрование RSA #2
скорей всего где-то выходит за границы long long. демонстрируйте на небольших числах, либо используйте библиотеки для работы с большими числами...
SODJ
 Аватар для SODJ
0 / 0 / 0
Регистрация: 18.05.2014
Сообщений: 9
02.06.2014, 18:26  [ТС]     Шифрование RSA #3
Спасибо за ответ, а какие есть библиотеки, и какие использовать лучше/проще? Да и вообще как их правильно использовать, а то опыта у меня в этом маловато? (=

Добавлено через 20 минут
Попробовал подключить ntl, но походу дела что-то делаю не так.
Качаю от сюда - http://www.shoup.net/ntl/download.html
Папку include/ntl кладу в папку VC/include
Далее прописываю строку в проекте:
C++
1
#include <NTL/ZZ.h>
Пробую запустить, вылезают вот такие ошибки:
Миниатюры
Шифрование RSA  
OstapBender
 Аватар для OstapBender
581 / 519 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
02.06.2014, 18:56     Шифрование RSA #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
 Аватар для SODJ
0 / 0 / 0
Регистрация: 18.05.2014
Сообщений: 9
02.06.2014, 23:54  [ТС]     Шифрование RSA #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
Yandex
Объявления
02.06.2014, 23:54     Шифрование RSA
Ответ Создать тему
Опции темы

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