Зашифровать и расшифровать свою фамилию с помощью алгоритма RSA

@toytamat · Регистрация: 06.03.2018

Студворк — интернет-сервис помощи студентам

Добрый день, уважаемые форумчане!

Имею задание: зашифровать и расшифровать свою фамилию с помощью алгоритма RSA.

Написан следующий код:

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
#include <cstdlib>
#include <iostream>
#include <ctime>
#include <cstring>
#include <cmath>
 
using namespace std;
 
int vpch (int eiler, int n)
{
    int t;
    int e = 2;
    for (e = 2; e < n; )
    {
        int count = 0;
        t = 2;
 
        for (int j = 0; j < e; j++)
        {
        if ( eiler % t == 0 && e % t == 0)  count = count + 1;
        t++;
        }
        if (count > 0) e++;
        else break;
    } 
    return e;
}
 
unsigned long int stepen (long a, int b)
{
    long result = 1;
    for (int i = 0; i < b; i++)
    {
        result = result * a;
    }
    
return result;
}
 
int main(int argc, char *argv[])
{
    setlocale (LC_ALL, "Russian_Russia.1251");
    
    //выбор простого числа из списка
    
    
    int prosto[11] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
    int e;
    int n;
    int k;
    int d;
    int eiler;
    int result = 1;   
    string name;
    string changed;
    string alphabit;
    
    for (char i = 'a'; i <= 'z'; i++)
    {
        alphabit = alphabit + i;
    }
    
    srand(time(NULL)); //сброс счётчика для выбора случайного числа
    int p = prosto[rand()%11];
    cout<<"p = "<<p<<'\n';
    
    srand(time(NULL)); //сброс счётчика для выбора случайного числа
    int q = prosto[rand()%11];
    cout<<"q = "<<q<<'\n';
    
    n = p * q;
    cout<<"n = "<<n<<'\n';
    eiler = (p-1)*(q-1);
    cout<<"eiler = "<<eiler<<'\n';
    
    
    //взаимно простые числа
    e = vpch(eiler, n);
    cout<<"e = "<<e<<'\n';
    
    
    //секретный ключ d
    
    d = 1; 
    do 
    {
      if ( (d*e)%eiler == 1 ) break;
      else d++;       
    }
    while ( (d*e)%eiler != 1 );
    cout<<"d = "<<d<<'\n';
    
    
    cout<<"Введите фамилию: ";
    cin>>name;
    unsigned long int rsa [name.length()][4];
    
    
 
    //поиск номера символа в алфавите
    for (int i = 0; i < name.length(); i++)
    {
        
        for (int j = 0; j < alphabit.length(); j++)
        {
            if (name[i] == alphabit[j]) rsa[i][0] = j;
        }
        
        rsa[i][1] = (stepen(rsa[i][0], e))%n;
        rsa[i][2] = (stepen(rsa[i][1], d))%n;
        cout<<rsa[i][0]<<"  "<<rsa[i][1]<<"  "<<rsa[i][2]<<'\n';
    }
       
    system("PAUSE");
    return EXIT_SUCCESS;
}

Шифрует, но не дешифрует. Не могу понять из-за чего.

@nonedark2008 · 08.03.2018, 23:55

Сообщение от toytamat

//сброс счётчика для выбора случайного числа

Вызывая постоянно srand ты делаешь только хуже. Вероятность того, что ты получишь неслучайное число, только возрастает.

Сообщение от toytamat

Не могу понять из-за чего.

Самый простой вариант решения твоей проблемы - это взять какой-нибудь простой случай и посчитать его на бумажке или с помощью мат. пакета.

Где гарантия в твоем коде, что числа p и q будут различными?

А так, основная твоя проблема находится в функции возведения в степень, там у тебя возникает переполнение.

@toytamat · 09.03.2018, 18:38 **[ТС]**

Сообщение от nonedark2008

зведения в степень, там у тебя возникает перепол

Есть предположения, как от этого переполнения избавиться?
Я пытался менять типы данных на long long и т.п., ничего не меняется

Добавлено через 5 часов 48 минут

Вызывая постоянно srand ты делаешь только хуже. Вероятность того, что ты получишь неслучайное число, только возрастает.

Оно по коду не особо случайное, там задан диапазон чисел

Самый простой вариант решения твоей проблемы - это взять какой-нибудь простой случай и посчитать его на бумажке или с помощью мат. пакета.

Считал на бумажке, ответ ровно такой, какой даёт программа, но он некорректный, для расшифровки

Где гарантия в твоем коде, что числа p и q будут различными?

А они в принципе могут быть как разные, так и одинаковые. Насколько я знаю, то, что p и q должны быть разными, условиями при создании ключа RSA не регламентируется.

А так, основная твоя проблема находится в функции возведения в степень, там у тебя возникает переполнение.

Возможно, как писал выше, менял везде тип данных на long long, даже при объявлении переменных - результат не меняется, уж не знаю куда больше.
Прописывал вместо рандомных p и q - фиксированные, самые мелкие p = 2, q = 3, в результате после дешифровке получаю тоже самое что и после зашифровки, т.е. одни и те же цифры.
Перепроверял формулы в соответствии с формулами C = Т^e mod n и Т = C^d mod n., все корректно, результат по прежнему такой же

@nonedark2008 · 09.03.2018, 22:47

Сообщение от toytamat

Есть предположения, как от этого переполнения избавиться?

Подсказка: $https://www.cyberforum.ru/cgi-bin/latex.cgi?a^b \text{ mod } n = (a \cdot a \text{ mod } n) \cdot (a ^{b-2} \text{ mod } n)$
А в твоем случае, попробуй посчитать 50 в степени 50 и сравнить результат.

Сообщение от toytamat

все корректно, результат по прежнему такой же

Давай дальше работать от конкретных примеров ошибки? Ты показываешь пример вычислений, а я говорю в чем у тебя проблема.

Добавлено через 1 час 39 минут

Сообщение от nonedark2008

Подсказка:

Так чуть проще: $https://www.cyberforum.ru/cgi-bin/latex.cgi?a^b \text{ mod } n \equiv a \cdot (a^{b-1} \text{ mod } n) \text{ mod } n$

@toytamat · 10.03.2018, 13:05 **[ТС]**

Сделал немного иначе, но всё заработало.
Проблема была именно в переполнении цикла stepen
Прописал там остаток от деления на n при каждой итерации.

Рабочий вариант кода ниже. В нем, правда, p и q задаются изначально в коде, но, думаю, кому нужно, сделает ввод с клавиатуры самостоятельно, там ничего сложного, в общем-то, нет.

Спасибо nonedark2008 за помощь

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
#include <cstdlib>
#include <iostream>
#include <ctime>
#include <cstring>
#include <cmath>
 
using namespace std;
 
int vpch (int eiler, int n)
{
    int t;
    int e = 2;
    for (e = 2; e < n; )
    {
        int count = 0;
        t = 2;
 
        for (int j = 0; j < e; j++)
        {
        if ( eiler % t == 0 && e % t == 0)  count = count + 1;
        t++;
        }
        if (count > 0) e++;
        else break;
    } 
    return e;
}
 
long stepen (long a, long b, int n)
{
    long result = 1;
    for (int i = 0; i < b; i++)
    {
    result = (result*a)%n;
    }  
return result;
}
 
int encr (int a, int d, int n)
{
    int result2;
    for (int x=0; x<=n; x++)
    {
        if ((a/pow(n*x, 1/d))<n)
        result2 = fmod (a,(pow(n*x, 1/d)));
    }
    return result2;
}
 
 
int main(int argc, char *argv[])
{
    setlocale (LC_ALL, "Russian_Russia.1251");
    
    //выбор простого числа из списка
    
    
    int prosto[11] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
    int e;
    int n;
    int k;
    int d;
    int eiler;
    int result = 1;   
    string name;
    string changed;
    string alphabit;
    
    for (char i = 'a'; i <= 'z'; i++)
    {
        alphabit = alphabit + i;
    }
    
    int p = 17;
    cout<<"p = "<<p<<'\n';
    
    int q = 19;
    cout<<"q = "<<q<<'\n';
    
    n = p * q;
    cout<<"n = "<<n<<'\n';
    eiler = (p-1)*(q-1);
    cout<<"eiler = "<<eiler<<'\n';
    
    
    //взаимно простые числа
    e = vpch(eiler, n);
    cout<<"e = "<<e<<'\n';
    
    
    //секретный ключ d
    
    d = 1; 
    do 
    {
      if ( (d*e)%eiler == 1 ) break;
      else d++;       
    }
    while ( (d*e)%eiler != 1 );
    cout<<"d = "<<d<<'\n';
    
    
    cout<<"Введите фамилию: ";
    cin>>name;
    unsigned long int rsa [name.length()][4];
    
    
 
    //поиск номера символа в алфавите
    for (int i = 0; i < name.length(); i++)
    {
        
        for (int j = 0; j < alphabit.length(); j++)
        {
            if (name[i] == alphabit[j]) rsa[i][0] = j+1;
        }
        
        rsa[i][1] = (stepen(rsa[i][0], e, n));
        rsa[i][2] = (stepen(rsa[i][1], d, n));
        
        cout<<rsa[i][0]<<"  "<<rsa[i][1]<<"  "<<rsa[i][2]<<'\n';
    }
       
    system("PAUSE");
    return EXIT_SUCCESS;
}

Добавлено через 18 минут
И да, функцию

C++
1
2
3
4
5
6
7
8
9
10
int encr (int a, int d, int n)
{
    int result2;
    for (int x=0; x<=n; x++)
    {
        if ((a/pow(n*x, 1/d))<n)
        result2 = fmod (a,(pow(n*x, 1/d)));
    }
    return result2;
}

можно убрать из кода, она там так, рудимент

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

Зашифровать и расшифровать свою фамилию с помощью алгоритма RSA

Решение