Реализация RSA, причина неправильной дешифровки

@fescar · Регистрация: 17.10.2009

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

Пытался я реализовать данный алгоритм, но он неправильно дешифрует.....

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
#include "RSA.h"
// -------------------------------------------------------------------
// Алгоритм "решето Сундарама". Выбирает все простые числа
// до заданного (случайно сгенерированного).
 
int sundaram(int n) {
    int *a = new int[n], i, j, k;
    memset(a, 0, sizeof(int) * n);
    for (i = 1; 3 * i + 1 < n; i++) {
        for (j = 1; (k = i + j + 2 * i * j) < n && j <= i; j++)
            a[k] = 1;
    }
    // Выбирает из списка простых чисел ближайшее к заданному.
    for (i = n - 1; i >= 1; i--)
        if (a[i] == 0) {
            return (2 * i + 1);
            break;
        }
    delete[]a;
}
 
// --------------------------------------------------------------------
// Алгоритм Евклида. Алгоритм для нахождения наибольшего
// общего делителя двух целых чисел. Используется для проверки
// чисел на взаимопростоту.
int gcd(int a, int b) {
    int c;
    while (b) {
        c = a % b;
        a = b;
        b = c;
    }
    return abs(a);
}
 
// --------------------------------------------------------------------
// генерация открытого и закрытого ключа
void keygen(int p, int q, int &p_simple, int &q_simple, int&d, unsigned int &e,
    unsigned int &n) {
    p_simple = sundaram(p);
    q_simple = sundaram(q);
    // Находим число n.
    n = p_simple * q_simple;
    // Генерация числа d и проверка его на взаимопростоту
    // с числом ((p_simple-1)*(q_simple-1)).
    int d_simple = 0, e_simple = 0;
    while (d_simple != 1) {
        d = rand() % 100;
        d_simple = gcd(d, ((p_simple - 1) * (q_simple - 1)));
    }
    // Определение числа e, для которого является истинным
    // соотношение (e*d)%((p_simple-1)*(q_simple-1))=1.
    while (e_simple != 1) {
        e += 1;
        e_simple = (e * d) % ((p_simple - 1) * (q_simple - 1));
    }
}
 
char * encrypt(char *Text, const int MAX, unsigned int e, unsigned int n) {
    // Массив для хранения шифротекста.
    unsigned int *CryptoText = new unsigned int[MAX];
    char *Text1 = new char[MAX];
    // Получение из введённых данных десятичного кода ASCII и
    // дальнейшее его преобразование по формуле ci = (mj^e)%n.
    int b = 301;
    int c;
    for (int j = 0; j < MAX; j++) {
        c = 1;
        unsigned int i = 0;
        int ASCIIcode = (static_cast<int>(Text[j])) + b;
        while (i < e) {
            c = c * ASCIIcode;
            c = c % n;
            i++;
        }
        CryptoText[j] = c;
        b += 1;
    }
    for (int j = 0; j < MAX; j++) {
        Text1[j] = static_cast<char>(CryptoText[j]);
    }
    return Text1;
}
 
char * decrypt(char *Text, const int MAX, int d, unsigned int n) {
    unsigned int *CryptoText = new unsigned int[MAX];
    unsigned int *Tdecrypt = new unsigned int[MAX];
    char *Text1 = new char[MAX];
    for (int j = 0; j < MAX; j++) {
        CryptoText[j] = static_cast<int>(Text[j]);
    }
    // Расшифровка полученного кода по формуле mi = (ci^d)%n
    // и перевод его в десятичный код ASCII.
    int b = 301;
    int m;
    for (int j = 0; j < MAX; j++) {
        m = 1;
        unsigned int i = 0;
        while (i < d) {
            m = m * CryptoText[j];
            m = m % n;
            i++;
        }
        m = m - b;
        Tdecrypt[j] = m;
        b += 1;
    }
    for (int j = 0; j < MAX; j++) {
        Text1[j] = static_cast<char>(Tdecrypt[j]);
    }
    return Text1;
}

Сам проект во вложении... Не понятна причина неправильной дешифровки.Помогите разобраться.

@Avazart · 27.12.2012, 23:05

Ну так у вас все по ф-циям разбито - вот и проверяйте правильность выполнения каждой по очереди...

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

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

C++
1
2
unsigned int *CryptoText = new unsigned int[MAX]; 
char *Text1 = new char[MAX];

А освободить память ?

@fescar · 27.12.2012, 23:52 **[ТС]**

ну освободить память там оду строчку добавить

C++
1
delete [] Text1;

она тут не причем. Проверял я эти функции CryptoText совпадает и в шифровании и в расшифровке, и не знаю почему так.... если напрямую шифровать и расшифровать без сохранения в файл то все работает

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
char * endecrypt(char *Text, const int MAX, unsigned int e, unsigned int n,int d) {
    // Массив для хранения шифротекста.
    unsigned int *CryptoText = new unsigned int[MAX];
    char *Text1 = new char[MAX];
    // Получение из введённых данных десятичного кода ASCII и
    // дальнейшее его преобразование по формуле ci = (mj^e)%n.
    int b = 301;
    int c;
    for (int j = 0; j < MAX; j++) {
        c = 1;
        unsigned int i = 0;
        int ASCIIcode = (static_cast<int>(Text[j])) + b;
        while (i < e) {
            c = c * ASCIIcode;
            c = c % n;
            i++;
        }
        CryptoText[j] = c;
        b += 1;
    }
    
    unsigned int *Tdecrypt = new unsigned int[MAX];
    char *Text1 = new char[MAX];
   
    // Расшифровка полученного кода по формуле mi = (ci^d)%n
    // и перевод его в десятичный код ASCII.
[ b = 301;
    int m;
    for (int j = 0; j < MAX; j++) {
        m = 1;
        unsigned int i = 0;
        while (i < d) {
            m = m * CryptoText[j];
            m = m % n;
            i++;
        }
        m = m - b;
        Tdecrypt[j] = m;
        b += 1;
    }
    for (int j = 0; j < MAX; j++) {
        Text1[j] = static_cast<char>(Tdecrypt[j]);
    }
    return Text1;
}

вот так работает, но мне надо разделить операции шифрования и дешифровки

mimicria · 28.12.2012, 08:03

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

если напрямую шифровать и расшифровать без сохранения в файл то все работает

Можно сделать логичное предположение, что проблема кроется в сохранении/считывании файла.

@fescar · 28.12.2012, 10:32 **[ТС]**

C++
1
2
3
4
for (int j = 0; j < MAX; j++) {
        Text1[j] = static_cast<char>(CryptoText[j]);
    }
    return Text1;

при переводе в строку СryptoText иногда обрезался, поэтому решил напрямую в файл записывать его

запись шифра

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
AnsiString Path = GetCurrentDir() + "//cripting.RSA";
    // Открываем первый файл на чтение
    HANDLE in = CreateFile(Fname, GENERIC_READ, 0, NULL, OPEN_EXISTING,
        FILE_ATTRIBUTE_NORMAL, NULL);
    if (in == INVALID_HANDLE_VALUE) {
        ShowMessage("Ошибка открытия файла");
        return;
    }
    HANDLE out = CreateFile(Path.c_str(), GENERIC_WRITE, 0, NULL, CREATE_ALWAYS,
        FILE_ATTRIBUTE_NORMAL, NULL);
    if (out == INVALID_HANDLE_VALUE) {
        ShowMessage("Ошибка открытия файла");
        return;
    }
    const int size = floor(log(n) / log(2));;
    char *buffer = new char[size];
    DWORD readed, written;
    while (true) {
        ReadFile(in, buffer, size, &readed, NULL);
        if (readed == 0)
            break;
        CryptoText= encrypt(buffer, size, e, n);
        WriteFile(out, CryptoText, readed, &written, NULL);
    }
    CloseHandle(out);
    CloseHandle(in);

а считываю теперь так

считывание

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
AnsiString Path = GetCurrentDir() + "//cripting.RSA";
    AnsiString Path1 = GetCurrentDir() + "//decripting" + ext;
    // Открываем первый файл на чтение
    HANDLE in = CreateFile(Path.c_str(), GENERIC_READ, 0, NULL, OPEN_EXISTING,
        FILE_ATTRIBUTE_NORMAL, NULL);
    if (in == INVALID_HANDLE_VALUE) {
        ShowMessage("Ошибка открытия файла");
        return;
    }
    HANDLE out = CreateFile(Path1.c_str(), GENERIC_WRITE, 0, NULL,
        CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL, NULL);
    if (out == INVALID_HANDLE_VALUE) {
        ShowMessage("Ошибка открытия файла");
        return;
    }
    const int size = floor(log(n) / log(2.0));
    char *buffer = new char[size];
    unsigned int *CryptoText = new unsigned int[size];
    DWORD readed, written;
    while (true) {
        ReadFile(in, CryptoText, size, &readed, NULL);
        if (readed == 0)
            break;
        buffer = decrypt(CryptoText, size, d, n);
        WriteFile(out, buffer, readed, &written, NULL);
    }

но он не правильно все считывает...

mimicria · 28.12.2012, 12:33

Не то чтобы совет, скорее моё предположение.
Если внутри функции выделяется память с помощью new, в ней же эта память должна освобождаться delete. Это правило хорошего тона. Отсюда для вас вытекает два варианта:
1. Переданный в функцию массив всё равно больше не используется, можно по переданному указателю переписать его выходным массивом
2. Передать в функцию указатель на выходной массив типа

C++
1
void endecrypt(char *Text, char *Out, ....

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

@fescar · 28.12.2012, 23:26 **[ТС]**

эммм я решил сохранять сами блоки

C++
1
2
3
4
5
6
7
8
9
10
11
ReadFile(in, buffer, size, &readed, NULL);
        if (readed == 0)
            break;
        wr="";
        encrypt(buffer,CryptoText, size, e, n);
        for (int i = 0; i<size; i++) {
 
           wr=wr+IntToStr((int)CryptoText[i]);
           wr=wr+"|";
        }
        WriteFile(out, wr.c_str(), readed, &written, NULL);

затем считываю в строку rd из которой потом блоки заносятся в TStringlist для удобства восстановления CryptoText с помощью функции AnalizeAnswer(rd) ;

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
*buffer = new char[4096];
    char *wr = new char[size];
    unsigned int *CryptoText = new unsigned int[size];
    DWORD readed, written;
    AnsiString rd="";
    while (true) {
        ReadFile(in,buffer,4096, &readed, NULL);
        if (readed == 0)
            break;
           rd=rd+buffer ;
           }
      AnalizeAnswer(rd) ;
      int j=0;
      buffer="";
     for(int i=0; i<StringList->Count ;i++){
            CryptoText[j]=StrToInt(StringList->Strings[i]) ;
            j++;
            if (j==size || i==StringList->Count-1) {
              decrypt(CryptoText,wr, size,d,n);
              WriteFile(out, wr, readed, &written, NULL);
              j=0;
            }
    }

вроде должно работать, но при считывании из файла с последним блоком берется какой-то мусор.... не понимаю откуда. Из за него выдается ошибка так мусор не возможно привести к типу int в 16 строке. помогите понять откуда он.

@fescar · 28.12.2012, 23:35 **[ТС]**

исходники то что получилось

mimicria · 29.12.2012, 08:06

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

при считывании из файла с последним блоком берется какой-то мусор

1. Если читать железно заданными блоками по 4096, то и получится в последнем блоке мусор. В конце надо считывать только остаток.
2. Зачем динамический массив, если размер заранее жёстко задан? Пользуйтесь стековым.
3. Сомнительное удовольствие читать в AnsiString, служебные символы там могут похериться.
Вобщем прекращайте уже из крайности в крайность бросаться. Сделайте функции шифрования/дешифрования, в которые передаётся указатель на массив char[] и возвращайте результат в той же массив. Потом массив пишите в файл FileWrite(), потом читайте FileRead и на вход дешифрования. Только результат дешифрования уже можно пихать в стринги, потому что это читабельный текст.

@fescar · 29.12.2012, 13:42 **[ТС]**

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

1. Если читать железно заданными блоками по 4096, то и получится в последнем блоке мусор. В конце надо считывать только остаток.
2. Зачем динамический массив, если размер заранее жёстко задан? Пользуйтесь стековым.
3. Сомнительное удовольствие читать в AnsiString, служебные символы там могут похериться.
Вобщем прекращайте уже из крайности в крайность бросаться. Сделайте функции шифрования/дешифрования, в которые передаётся указатель на массив char[] и возвращайте результат в той же массив. Потом массив пишите в файл FileWrite(), потом читайте FileRead и на вход дешифрования. Только результат дешифрования уже можно пихать в стринги, потому что это читабельный текст.

1,2)эмм ну 4096 был выбран для более быстрого считывания
3) служебные символы не используются, поэтому использую AnsiString в файле должны быть только значение блоков и разделительный символ.Записать просто CryptoText нельзя так как элементы в нем имеют разную длину к примеру:
CryptoText[0]-99
CryptoText[1]-76
CryptoText[2]-123
CryptoText[3]-1256
если привести их к чару как я делал раньше большие значения блоков урезаются.
Поэтому надо сохранять сами значения через разделительный символ. Потом считав их обратно формировать CryptoText.

mimicria · 29.12.2012, 14:11

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

эмм ну 4096 был выбран для более быстрого считывания

Серьёзно? Вы правда считаете, что считать хрен знает сколько раз по 4096 быстрее, чем весь файл за 1 раз?

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

в файле должны быть только значение блоков и разделительный символ

Это сами придумали про разделители?

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

элементы в нем имеют разную длину

Это не длина, это значение

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

если привести их к чару

А если не к чару, а к short int? 2 байта хватит?

Добавлено через 13 минут
На всякий еще раз накидаю структуру как должно примерно выглядеть

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
void encrypt(char *in, unsigned short int *out) // можно убрать short, если не хватает 2-х байт
{
 // тут шифрование, вывод записывается по указателю в out
}
 
void decrypt(unsigned short int *in, char *out) 
{
 // тут дешифрование, вывод записывается по указателю в out
}
 
main
{
 char *in = new char[размер_сообщения];
 FileRead(fh,in,size);
 unsigned short int *out = new char[размер_сообщения];
 encrypt(in, out);
 FileWrite(fh2, out, size2); // вывод в другой файл, size2 соотв size*sizeof(unsigned short int)
// и в обратку
 FileRead (fh2, out, size2);
 decrypt (out, in);
 // вывод in
 delete [] in;
 delete [] out;
}

Новые блоги и статьи Все статьи Все блоги /
Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .
Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .	Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при создании или изменении элементов справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной записи электронной. . .