Зашифровать и расшифровать свою фамилию с помощью алгоритма 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;
}

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

Новые блоги и статьи Все статьи Все блоги /
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Нашел на реддите интересную статью под названием «Кто-нибудь знает, где получить бесплатный компьютер или. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .

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

Решение