Минимальная реализация алгоритма RSA на C++

Описание программы

Алгоритм асимметричного шифрования RSA основан на практической сложности факторизации больших чисел, что делает его на сегодняшний день одним из самых популярных криптографических алгоритмов.
Однако он имеет свои отрицательные стороны, например среди них достаточно низкая скорость шифрования, поэтому зачастую используют смешанную криптосистему, в которой сначала две стороны передают симметричный ключ с помощью RSA, а затем шифруют сообщение с помощью какого-либо симметрического алгоритма, например AES.
О самом алгоритме можно почитать например тут.
RSA может шифровать числа до так называемого модуля, который является частью ключа. В настоящее время используются модули длиной в 1024, 2048 и даже 4096 бит. В нашей реализации без длинной арифметики получится иметь дело максимум с 64-битными ключами, однако для наглядности этого хватит. Для того, чтобы сообщение при шифровании многократно не увеличивалось в размере, шифровать его надо блоками по $k — 1$ бит, где $k$ — битность ключа. При этом каждый блок перейдет в $k$-битное число, то есть на больших файлах прирост размера составит всего лишь $\frac{k}{k-1}$ раз, и чем больше ключ — тем меньше этот прирост.
В программе делением массива чисел одной битности на числа другой битности занимается функция resize, дополняя недостающие биты нулями.
Шифрованием и одновременно дешифрованием занимается функция process_bytes, так как в RSA оба этих процесса имеют идентичные алгоритмы, отличающиеся только размером блока входа и выхода. Для этого используется алгоритм быстрого возведения в степень.
Также программа может генерировать ключи на основании предустановленных простых чисел (в будущем случайных), или на основании простых чисел, введенных пользователем. Для этого используется нахождении обратного в кольце по модулю расширенным алгоритмом Евклида.
Программа реализована в интерактивном виде, список команд можно вызвать командой h.

Код

#include <iostream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <climits>
#include <stack>
#include <random>
#include <fstream>

using namespace std;

//Структура ключа
typedef struct {
    uint64_t e;
    uint64_t m;
} key;

//Расширенный алгоритм Евклида
int64_t gcdex(int64_t a, int64_t b, int64_t &x, int64_t &y) {
    if (a == 0) {
        x = 0;
        y = 1;
        return b;
    }
    int64_t x1, y1;
    int64_t d = gcdex(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}

//Обратное по модулю
int64_t invmod(int64_t a, int64_t m) {
    int64_t x, y;
    gcdex(a, m, x, y);
    x = (x % m + m) % m;
    return x;
}

uint64_t sqr(uint64_t x) {
    return x * x;
}

//Быстрое возведение в степень
uint64_t binpow(uint64_t a, uint64_t e, uint64_t mod = LLONG_MAX) {
    return e == 0 ? 1 : (e & 1U ? a * binpow(a, e - 1, mod) % mod : sqr(binpow(a, e / 2, mod)) % mod);
}

//Генерация пары ключей
pair<key, key> gen_keys(uint64_t p, uint64_t q) {
    uint64_t phi = (p - 1) * (q - 1);
    uint64_t n = p * q;
    //Простое число Мерсенна, обычно используется в RSA в виде открытой экспоненты для увеличения производительности
    uint64_t e = 65537;
    uint64_t d = invmod(e, phi);
    return {{e, n},
            {d, n}};
}

//Размер блока шифрования ключа
uint8_t get_chunk_size(key k) {
    return 32 - __builtin_clz(k.m);
}

//Резбиение/обьединение данных в блоки
vector<uint64_t> resize(const vector<uint64_t> &data, uint8_t in_size, uint8_t out_size) {
    vector<uint64_t> res;
    uint8_t done = 0;
    uint64_t cur = 0;
    for (uint64_t byte: data)
        for (uint8_t i = 0; i < in_size; i++) {
            cur = (cur << 1U) + (((uint64_t) byte & (1U << (uint64_t) (in_size - 1 - i))) != 0);
            done++;
            if (done == out_size) {
                done = 0;
                res.push_back(cur);
                cur = 0;
            }
        }
    //Дополнение нулями
    if (done != 0)
        res.push_back(cur << (uint64_t) (out_size - done));
    return res;
}

//(Де)шифрование
vector<uint8_t> process_bytes(const vector<uint8_t> &data, key k, bool encrypt) {
    vector<uint64_t> data_64(data.size());
    for (int i = 0; i < data.size(); i++)
        data_64[i] = (uint64_t) data[i];
    vector<uint64_t> resized_data = resize(data_64, 8, get_chunk_size(k) - encrypt); //Если мы шифруем, то размер блока K - 1, иначе K
    vector<uint64_t> encrypted_data(resized_data.size());
    for (int i = 0; i < resized_data.size(); i++)
        encrypted_data[i] = binpow(resized_data[i], k.e, k.m);
    vector<uint64_t> result_64 = resize(encrypted_data, get_chunk_size(k) - !encrypt, 8);
    vector<uint8_t> result(result_64.size());
    for (int i = 0; i < result_64.size(); i++)
        result[i] = (uint8_t) result_64[i];
    return result;
}

//Функции работы с файлами
vector<uint8_t> read_bytes(const char *filename) {
    ifstream fin(filename);
    fin.seekg(0, ios::end);
    size_t len = fin.tellg();
    auto *bytes = new char[len];
    fin.seekg(0, ios::beg);
    fin.read(bytes, len);
    fin.close();
    vector<uint8_t> ret(len);
    for (int i = 0; i < len; i++)
        ret[i] = (uint8_t) bytes[i];
    delete[] bytes;
    return ret;
}

void write_bytes(const char *filename, const vector<uint8_t> &data) {
    ofstream fout(filename);
    char *buf = new char[data.size()];
    for (int i = 0; i < data.size(); i++)
        buf[i] = (char) data[i];
    fout.write(buf, data.size());
    fout.close();
}

void help() {
    cout << "---- tinyRSA\n"
            "e <exp> <mod> <file in> <file out> -- Encrypt file\n"
            "d <exp> <mod> <file in> <file out> -- Decrypt file\n"
            "g -- Generate key pair from default primes\n"
            "G <p> <q> -- Generate key pair from primes\n"
            "h -- Help\n"
            "q -- Exit\n" << endl;
}

int main() {
    help();
    while (true) {
        char cmd;
        cin >> cmd;
        if (cmd == 'q') {
            cout << "Bye." << endl;
            break;
        } else if (cmd == 'e') {
            uint64_t e, m;
            string fin, fout;
            cin >> hex >> e >> hex >> m >> fin >> fout;
            auto in = read_bytes(fin.c_str());
            write_bytes(fout.c_str(), process_bytes(in, {e, m}, true));
            cout << "Done." << endl;
        } else if (cmd == 'd') {
            uint64_t e, m;
            string fin, fout;
            cin >> hex >> e >> hex >> m >> fin >> fout;
            auto in = read_bytes(fin.c_str());
            write_bytes(fout.c_str(), process_bytes(in, {e, m}, false));
            cout << "Done." << endl;
        } else if (cmd == 'g') {
            auto key_pair = gen_keys(3557, 2579);
            cout << "OPEN KEY  : " << hex << key_pair.first.e << ' ' << hex << key_pair.first.m << endl;
            cout << "SECRET KEY: " << hex << key_pair.second.e << ' ' << hex << key_pair.second.m << endl;
        } else if (cmd == 'G') {
            uint64_t p, q;
            cin >> p >> q;
            auto key_pair = gen_keys(p, q);
            cout << "OPEN KEY  : " << hex << key_pair.first.e << ' ' << hex << key_pair.first.m << endl;
            cout << "SECRET KEY: " << hex << key_pair.second.e << ' ' << hex << key_pair.second.m << endl;
        } else if (cmd == 'h')
            help();
    }
    return 0;
}

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

166

167

168

169

170

171

172

173

#include <iostream>

#include <vector>

#include <iomanip>

#include <cmath>

#include <climits>

#include <stack>

#include <random>

#include <fstream>

using namespace std;

//Структура ключа

typedef struct {

uint64_t e;

uint64_t m;

} key;

//Расширенный алгоритм Евклида

int64_t gcdex(int64_t a, int64_t b, int64_t &x, int64_t &y) {

if (a == 0) {

x = 0;

y = 1;

return b;

}

int64_t x1, y1;

int64_t d = gcdex(b % a, a, x1, y1);

x = y1 - (b / a) * x1;

y = x1;

return d;

}

//Обратное по модулю

int64_t invmod(int64_t a, int64_t m) {

int64_t x, y;

gcdex(a, m, x, y);

x = (x % m + m) % m;

return x;

}

uint64_t sqr(uint64_t x) {

return x * x;

}

//Быстрое возведение в степень

uint64_t binpow(uint64_t a, uint64_t e, uint64_t mod = LLONG_MAX) {

return e == 0 ? 1 : (e & 1U ? a * binpow(a, e - 1, mod) % mod : sqr(binpow(a, e / 2, mod)) % mod);

}

//Генерация пары ключей

pair<key, key> gen_keys(uint64_t p, uint64_t q) {

uint64_t phi = (p - 1) * (q - 1);

uint64_t n = p * q;

//Простое число Мерсенна, обычно используется в RSA в виде открытой экспоненты для увеличения производительности

uint64_t e = 65537;

uint64_t d = invmod(e, phi);

return {{e, n},

{d, n}};

}

//Размер блока шифрования ключа

uint8_t get_chunk_size(key k) {

return 32 - __builtin_clz(k.m);

}

//Резбиение/обьединение данных в блоки

vector<uint64_t> resize(const vector<uint64_t> &data, uint8_t in_size, uint8_t out_size) {

vector<uint64_t> res;

uint8_t done = 0;

uint64_t cur = 0;

for (uint64_t byte: data)

for (uint8_t i = 0; i < in_size; i++) {

cur = (cur << 1U) + (((uint64_t) byte & (1U << (uint64_t) (in_size - 1 - i))) != 0);

done++;

if (done == out_size) {

done = 0;

res.push_back(cur);

cur = 0;

}

//Дополнение нулями

if (done != 0)

res.push_back(cur << (uint64_t) (out_size - done));

return res;

}

//(Де)шифрование

vector<uint8_t> process_bytes(const vector<uint8_t> &data, key k, bool encrypt) {

vector<uint64_t> data_64(data.size());

for (int i = 0; i < data.size(); i++)

data_64[i] = (uint64_t) data[i];

vector<uint64_t> resized_data = resize(data_64, 8, get_chunk_size(k) - encrypt); //Если мы шифруем, то размер блока K - 1, иначе K

vector<uint64_t> encrypted_data(resized_data.size());

for (int i = 0; i < resized_data.size(); i++)

encrypted_data[i] = binpow(resized_data[i], k.e, k.m);

vector<uint64_t> result_64 = resize(encrypted_data, get_chunk_size(k) - !encrypt, 8);

vector<uint8_t> result(result_64.size());

for (int i = 0; i < result_64.size(); i++)

result[i] = (uint8_t) result_64[i];

return result;

}

//Функции работы с файлами

vector<uint8_t> read_bytes(const char *filename) {

ifstream fin(filename);

fin.seekg(0, ios::end);

size_t len = fin.tellg();

auto *bytes = new char[len];

fin.seekg(0, ios::beg);

fin.read(bytes, len);

fin.close();

vector<uint8_t> ret(len);

for (int i = 0; i < len; i++)

ret[i] = (uint8_t) bytes[i];

delete[] bytes;

return ret;

}

void write_bytes(const char *filename, const vector<uint8_t> &data) {

ofstream fout(filename);

char *buf = new char[data.size()];

for (int i = 0; i < data.size(); i++)

buf[i] = (char) data[i];

fout.write(buf, data.size());

fout.close();

}

void help() {

cout << "---- tinyRSA\n"

"e <exp> <mod> <file in> <file out> -- Encrypt file\n"

"d <exp> <mod> <file in> <file out> -- Decrypt file\n"

"g -- Generate key pair from default primes\n"

"G <p> <q> -- Generate key pair from primes\n"

"h -- Help\n"

"q -- Exit\n" << endl;

}

int main() {

help();

while (true) {

char cmd;

cin >> cmd;

if (cmd == 'q') {

cout << "Bye." << endl;

break;

} else if (cmd == 'e') {

uint64_t e, m;

string fin, fout;

cin >> hex >> e >> hex >> m >> fin >> fout;

auto in = read_bytes(fin.c_str());

write_bytes(fout.c_str(), process_bytes(in, {e, m}, true));

cout << "Done." << endl;

} else if (cmd == 'd') {

uint64_t e, m;

string fin, fout;

cin >> hex >> e >> hex >> m >> fin >> fout;

auto in = read_bytes(fin.c_str());

write_bytes(fout.c_str(), process_bytes(in, {e, m}, false));

cout << "Done." << endl;

} else if (cmd == 'g') {

auto key_pair = gen_keys(3557, 2579);

cout << "OPEN KEY : " << hex << key_pair.first.e << ' ' << hex << key_pair.first.m << endl;

cout << "SECRET KEY: " << hex << key_pair.second.e << ' ' << hex << key_pair.second.m << endl;

} else if (cmd == 'G') {

uint64_t p, q;

cin >> p >> q;

auto key_pair = gen_keys(p, q);

cout << "OPEN KEY : " << hex << key_pair.first.e << ' ' << hex << key_pair.first.m << endl;

cout << "SECRET KEY: " << hex << key_pair.second.e << ' ' << hex << key_pair.second.m << endl;

} else if (cmd == 'h')

help();

}

return 0;

}

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Минимальная реализация алгоритма RSA на C++

Описание программы

Код

Related Images:

Понравилось это:

Похожее

Добавить комментарий Отменить ответ

Описание программы

Код

Related Images:

Поделиться ссылкой:

Понравилось это:

Похожее

Добавить комментарий Отменить ответ