Как манипулировать большими целыми числами для алгоритма RSA в C?

Я хочу реализовать криптосистему RSA на C. Прямо сейчас я могу шифровать значения, которые умещаются в один байт (который, как я знаю, слишком мал для любой безопасности), но когда я увеличиваю размер простых чисел p и q (и, следовательно, модуля n = pq), и размера зашифрованных значений, это не работает.

Я считаю, что знаю причины, по которым мой код не работает:

  1. шифруемое значение должно быть меньше значения n (что не всегда так), и
  2. значение n = pq, которое я вычисляю, неверно, потому что реальное значение не может быть сохранено в типе переменной, который я использую, и вместо этого происходит переполнение.

Мой вопрос в том, как я могу использовать большие числа (упаковывать в 256 байтов, 512 байтов и т. д.) и манипулировать ими в C? Должен ли я использовать библиотеки (например, GMP)?


c rsa bignum
person wolfgunner    schedule 20.11.2016    source источник
comment
Вы можете посмотреть на OpenSSL. У него была поддержка BigNumber (BN). Он также имеет поддержку RSA.   -  person brian beuning    schedule 19.12.2016

Ответы (1)


arrow_upward
3
arrow_downward

В языке C нет встроенной поддержки целочисленной арифметики произвольной точности ("bignum"), поэтому вам либо придется использовать библиотеку, которая ее предоставляет (я слышал, что GMP является популярным выбором) или напишите свой собственный код для его обработки.

Если вы выберете путь «сделай сам», я бы рекомендовал представлять ваши числа в виде массивов некоторого достаточно большого собственного беззнакового целочисленного типа (например, uint32_t или uint64_t) с каждый элемент массива представляет цифру в базе 2k, где k — количество битов в исходных целых числах.

Для RSA вам не нужно беспокоиться о представлении отрицательных значений, так как все математические операции выполняются с числами в диапазоне от 0 до модуля RSA n. Если хотите, вы также можете воспользоваться верхним пределом n, чтобы зафиксировать количество цифр по основанию 2k, используемых для всех значений в конкретный экземпляр RSA, поэтому вам не нужно явно хранить его рядом с каждым массивом цифр.

Пс. Обратите внимание, что "учебник RSA" сам по себе не является безопасной схемой шифрования. Чтобы сделать его семантически безопасным, необходимо также включить подходящую схему рандомизированного заполнения, такую ​​как OAEP. Кроме того, с дополнением или без, обычный RSA может шифровать только сообщения короче, чем модуль, за вычетом длины, занимаемой дополнением, если таковое имеется. Для шифрования более длинных сообщений стандартным решением является использование гибридного шифрования, при котором вы сначала шифруете сообщение. используя симметричную схему шифрования (я бы рекомендовал AES-SIV) со случайным ключом, а затем зашифровать ключ с помощью RSA.

person Ilmari Karonen    schedule 20.11.2016
comment
Хорошо, и я могу использовать его для реализации GPU?? - person wolfgunner; 20.11.2016
comment
Судя по быстрому поиску в Google gmp gpu, это возможно. Вы также можете рассмотреть попробуйте вместо этого вилку GMP MPIR. Или, конечно, написание собственной реализации арифметики bignum. - person Ilmari Karonen; 20.11.2016
comment
Что ж, при использовании библиотек убедитесь, что они поддерживают какой-либо необходимый оператор (битовый сдвиг, модуль, деление) и отрицательное число (может потребоваться расширенный евклид) а, также для лучшей производительности он должен использовать умножение Карацубы. Просто немного моего опыта. Надеюсь, это поможет. @wolfgunner - person khôi nguyễn; 20.11.2016