Как использовать отрицательное число с BIGNUM openssl?

Функция BN_set_negative устанавливает отрицательное число.

Отрицательное значение afd72b5835ad22ea5d68279ffac0b6527c1ab0fb31f1e646f728d75cbd3ae65d на самом деле равно -afd72b5835ad22ea5d68279ffac0b6527c1ab0fb31f1e646f728d75cbd3ae65d, точно так же, как -2 является отрицательным значением 2.

ff5028d4a7ca52dd15a297d860053f49ad83e54f04ce0e19b908d728a342c519a3 — большое положительное число.

Причина, по которой вы видите этот номер в Java, связана с вызовом toByteArray. Согласно документации , он выбирает минимальную ширину поля, которая составляет целое число байтов, а также может содержать представление отрицательного числа в дополнении до двух.

Другими словами, используя функцию toByteArray для числа, которое в настоящее время имеет 1 знаковый бит и 256 битов значения, вы получите ширину поля 264 бита. Однако, если первый полубайт вашего отрицательного числа был, например, 7, а не a, то (согласно этой документации - я на самом деле не пробовал) вы получите 256-битную ширину поля (т.е. 8028d4..., а не ff8028d4.

Начальный 00, который вы использовали в своем коде, не имеет значения в OpenSSL BN. Я не уверен, имеет ли это значение в BigInteger, хотя в документации для этого конструктора говорится: «Представление String состоит из необязательного знака минус или плюс, за которым следует последовательность из одной или нескольких цифр в указанной системе счисления». поэтому тот факт, что он принимает знак минус, предполагает, что если знак минус отсутствует, то ввод обрабатывается как большое положительное число, даже если его старший бит установлен. (Надеюсь, программист на Java сможет прояснить для меня этот абзац).

Убедитесь, что вы четко понимаете различие между большим отрицательным значением и большим положительным числом, полученным с помощью модульной арифметики для этого отрицательного значения, например, как результат toByteArray.

Итак, ваш вопрос действительно таков: есть ли в Openssl BN функция, которая эмулирует поведение BigInteger.toByteArray()?

Я не знаю, существует ли такая функция (имхо, у библиотеки BN довольно плохая документация, и я никогда не слышал, чтобы она использовалась вне OpenSSL, особенно в программе на C++). Я ожидаю, что нет, так как поведение toByteArray довольно странное; и в любом случае, все функции вывода BN, по-видимому, выводят с использованием формата знака-величины, а не формата дополнения до двух.

Но чтобы воспроизвести этот результат, вы можете добавить 2^256 или 2^264 к большому отрицательному числу, а затем сделать BN_bn2hex. В этом конкретном случае добавьте 2^264. В общем случае вам нужно будет измерить текущую битовую длину сохраняемого числа и округлить показатель степени до ближайшего кратного 8.

Или вы можете даже вывести в формате знака-величины (используя BN_bn2hex или BN_bn2mpi), а затем повторить итерацию, инвертируя каждый кусочек и исправляя начало!

NB. Есть ли какая-то конкретная причина, по которой вы хотите использовать OpenSSL BN? Есть много альтернатив.

Хотя это вопрос из 2014 года (более пяти лет назад), я хотел бы решить вашу проблему / прояснить ситуацию, что может помочь другим.

а) Дополнение до единицы и дополнение до двух

В теории конечных чисел существует представление чисел с «дополнением до единицы» и «дополнением до двух». Дополнение до единицы хранит только абсолютные (положительные) значения и не знает знак. Если вы хотите, чтобы знак числа хранился как дополнение, вам нужно хранить его отдельно, например. в одном бите (0=положительный, 1=отрицательный). Именно так обстоит дело с числами с плавающей запятой (IEEE 754). Мантисса хранится как дополнение до единицы вместе с показателем степени и одним дополнительным битом знака. Числа в дополнении до единицы имеют два нуля: -0 и +0, потому что вы обрабатываете знак независимо от самого абсолютного значения.

В дополнении до двух старший бит используется как бит знака. Нет «-0», потому что отрицание значения в дополнении до двух означает выполнение логической операции НЕ (в C: тильда), за которой следует добавление единицы. Например, один байт (в дополнении до двух) может быть одним из трех значений 0xFF, 0x00, 0x01, что означает -1, 0 и 1. Для -0 нет места. Если у вас есть, например. 0xFF (-1) и хотите инвертировать его, то логическая операция НЕ вычисляет 0xFF => 0x00. Добавление единицы дает 0x01, что равно 1.

б) OpenSSL BIGNUM и Java BigInteger

Реализация OpenSSL BIGNUM представляет числа как дополнение. Java BigInteger обрабатывает числа как дополнение до двух. Это была твоя катастрофа. Ваше большое целое число (в шестнадцатеричном формате) — 00afd72b5835ad22ea5d68279ffac0b6527c1ab0fb31f1e646f728d75cbd3ae65d. Это положительное 256-битное целое число. Он состоит из 33 байтов, потому что есть начальный нулевой байт 0x00, что абсолютно правильно для целого числа, хранящегося в виде дополнения до двух, потому что установлен старший бит (без начального 0x00) (в 0xAF), что сделало бы это число отрицательным. номер.

c) Решение, которое вы искали

Функция OpenSSL bin2bn работает только с абсолютными значениями. Для OpenSSL можно оставить начальный нулевой байт или отрезать его — без разницы, потому что OpenSSL все равно канонизирует входные данные, а это означает отсечение всех начальных нулевых байтов. Следующая проблема вашего кода заключается в том, как вы хотите сделать это целое число отрицательным: вы хотите умножить его на -1. Использование 0xFF в качестве единственного входного байта для bin2bn дает 255, а не -1. Фактически, вы умножаете свое большое целое число на 255, что дает общий результат AF27542CDD7775C7730ABF785AC5F59C299E964A36BFF460B031AE85607DAB76A3, который по-прежнему положительный.

Умножение на -1 работает так (фрагмент, без проверки ошибок):

BIGNUM* x = BN_bin2bn(&xBytes[0], (int)xBytes.size(), NULL);
BIGNUM* negative1 = BN_new();
BN_one(negative1); /* negative1 is +1 */
BN_set_negative(negative1, 1); /* negative1 is now -1 */
BN_CTX* ctx = BN_CTX_new();
BIGNUM* y = BN_new();
BN_mul(y, x, negative1, ctx);

Легче это:

BIGNUM* x = BN_bin2bn(&xBytes[0], (int)xBytes.size(), NULL);
BN_set_negative(x,1);

Это не решает вашу проблему, потому что, как сказал MM, это просто делает -afd72b5835ad22ea5d68279ffac0b6527c1ab0fb31f1e646f728d75cbd3ae65d из afd72b5835ad22ea5d68279ffac0b6527c1ab0fb31f1e646f7283d75cb.d283d75cb.d728d75cbd3ae65d

Вы ищете дополнение двух вашего большого целого числа, которое равно

int i;

for (i = 0; i < (int)sizeof(value); i++)
  value[i] = ~value[i];

for (i = ((int)sizeof(posvalue)) - 1; i >= 0; i--)
{
  value[i]++;
  if (0x00 != value[i])
    break;
}

Это неоптимизированная версия дополнения до двух, если «значение» - это ваш 33-байтовый входной массив, содержащий ваше большое целое число с префиксом байта 0x00. Результатом этой операции являются 33 байта ff5028d4a7ca52dd15a297d860053f49ad83e54f04ce0e19b908d728a342c519a3.

г) Работа с дополнением до двух и OpenSSL BIGNUM

Вся последовательность такая:

1. Пролог: если ввод отрицательный (проверьте старший бит), то вычислите дополнение до двух входных данных.
2. Преобразование в BIGNUM с помощью BN_bin2bn
3. Если ввод был отрицательным, вызовите BN_set_negative(x,1)
4. Основная функция: Выполнение всех арифметических операций с использованием пакета OpenSSL BIGNUM
5. Вызовите BN_is_negative, чтобы проверить отрицательный результат
6. Преобразование в необработанный двоичный байт с помощью BN_bn2bin
7. Если результат отрицательный, то вычисляется дополнение до двух результата.
8. Эпилог: если результат был положительным, а исходный результат (вывод шага 7) установлен в старшем значащем бите байта, то добавьте байт 0x00. Если результат был отрицательным, а старший бит необработанного байта результата чист, то добавьте байт 0xFF.