В этой статье я расскажу вам о библиотеке, при помощи которой можно выполнять арифметические операции над числами большой разрядности. Она понадобится например в случае, если требуется реализовать какую-нибудь криптографическую схему. Чтобы показать, насколько это просто, в качестве примера приведу реализацию алгоритма RSA.
Итак...
Библиотека GMP используется для работы над знаковыми целыми, рациональными числами и числами с плавающей точкой. Главная особенность библиотеки — разрядность чисел (precision) практически неограничена. Поэтому основная область применения — криптография, компьютерные алгебраические вычисления и др. Распространяется по лицензии GNU LGPL и является частью project GNU.
Платформа Linux для этой библиотеки является родной. Чтобы использовать ее под Windows придется немного напрячься.
Установка GMP под Windows
Для начала необходимо скачать последнюю версию GMP (на момент написания статьи — 4.2.4). Потом необходимо скачать соответствующий архив проекта Visual Studio 2005/2008 — идем сюда и находим ссылку на архив (для версии 4.2.4 — вот). Хочу выразить Brian Gladman-у респект за то, что он приложил усилия по портированию кода под msvc :)
Далее распаковываем два архива в один каталог (при необходимости соглашаемся на мерж), находим файл солюшена gmp.sln, запускаем его и компилируем библиотеку. Трудностей возникнуть не должно, разве что при запуске проекта вылезут различные предупреждения. Их можно пропустить — это не отразится на конечном результате (по-крайней мере, у меня было так). При удачном стечении обстоятельств, мы должны получить две либы: gmp.lib и gmpxx.lib.
За подробностями обращайтесь в readme или задавайте ваши вопросы здесь в комментариях — я постараюсь ответить.
Использование GMP на примере алгоритма RSA
Понять принцип работы библиотеки очень просто. Достаточно вникнуть в один пример, и все станет ясным. Название каждой функции имеет понятный смысл. Для полноты картины стоит также почитать подробный мануал (eng).
RSA — криптографический алгоритм с открытым ключом. Система RSA используется для защиты программного обеспечения и в схемах цифровой подписи. Вашему вниманию предлагаю реализацию алгоритма цифровой подписи RSA:
#include <stdio.h>
#include <gmp.h>
#include <cassert>
using namespace std;
// Функция проверяет, является ли число простым.
// Если нет, то делает таковым
void check_for_prime(mpz_ptr p)
{
int forprimep = mpz_probab_prime_p (p, 50);
while (forprimep == 0) {
mpz_add_ui (p, p, 1);
forprimep = mpz_probab_prime_p (p, 50);
};
}
// Размер ключей
enum {
SIZE = 512
};
int main(int argc, char* argv[])
{
mpz_t p, q;
// Инициализация рандома
gmp_randstate_t state;
gmp_randinit_default(state);
// 1. Генерируется случайные простые числа p и q
mpz_init2(p,SIZE);
mpz_urandomb(p, state, SIZE);
check_for_prime(p);
mpz_init2(q,SIZE);
mpz_urandomb(q, state, SIZE);
check_for_prime(q);
puts("p = ");
mpz_out_str (stdout, 10, p);
puts("\nq = ");
mpz_out_str (stdout, 10, q);
// 2. Вычисляется их произведение n = pq
mpz_t n;
mpz_init(n);
mpz_mul(n,p,q);
puts("\nn = ");
mpz_out_str (stdout, 10, n);
// 3. Вычисляется значение функция Эйлера от числа n
mpz_t fi;
mpz_init(fi);
mpz_t p_m, q_m;
mpz_init(p_m);
mpz_init(q_m);
mpz_sub_ui(p_m, p, 1);
mpz_sub_ui(q_m, q, 1);
mpz_mul(fi, p_m, q_m);
puts("\nfi = ");
mpz_out_str (stdout, 10, fi);
// 4.Выбирается целое число e, взаимно простое со значением функции fi
// часто выбирают один из простых чисел Ферма 17, 257, или 65537
int possible_values[] = {
17, 257, 65537
};
mpz_t e;
mpz_init(e);
mpz_t gcd;
mpz_init(gcd);
int i = 0;
for (; i < 3; ++i)
{
mpz_set_ui(e,possible_values[i]);
mpz_gcd(gcd, e, fi);
int compgcd = mpz_cmp_ui(gcd, 1);
if (compgcd == 0)
break;
}
assert(i != 3); // выбор был сделан
puts("\ne = ");
mpz_out_str (stdout, 10, e);
// 5. Вычисляется число d мультипликативное обратное к числу e по модулю fi
mpz_t d;
mpz_init(d);
mpz_invert(d, e, fi);
puts("\nd = ");
mpz_out_str (stdout, 10, d);
// Пара P = (e,n) публикуется в качестве открытого ключа RSA
// Пара S = (d,n) играет роль секретного ключа RSA
// Цифровая подпись
// Открытый текст
// В качестве текста возьмем рандомное число. Так или иначе, текст
// необходимо привести к какому-то числу
mpz_t M;
mpz_init2(M,SIZE / 2);
mpz_urandomb(M, state, SIZE / 2);
puts("\nM = ");
mpz_out_str (stdout, 10, M);
// Создаем цифровую подпись sigma с помощью своего секретного ключа S
mpz_t sigma;
mpz_init(sigma);
mpz_powm(sigma, M, d, n);
puts("\nsigma = ");
mpz_out_str (stdout, 10, sigma);
// Проверяем подлинность подписи (Pa должно равняться M)
mpz_t Pa;
mpz_init(Pa);
mpz_powm(Pa, sigma, e, n);
puts("\nPa = ");
mpz_out_str (stdout, 10, Pa);
int compgcd = mpz_cmp(M, Pa);
if (compgcd == 0) {
puts("\nM == Pa");
}
else {
puts("\nM != Pa");
}
return 0;
}
Как видите, все просто :) Я использовал процедурные возможности библиотеки. Однако, в последних версиях появились классы-обертки, и пользоваться gmp стало еще проще.
Ссылки по теме:
- Скачать проект VS-2005
- The GNU MP Bignum Library
- A Native GMP Port Using Microsoft Visual Studio
- Wikipedia - RSA (rus & eng)
P.S. На этот пост меня подтолкнула статья про шароварную криптографию — не так страшна криптография, как ее рисуют ;)
