Могу ли я извлечь R и S из сигнатуры ECDSA в битовой форме, и наоборот?

4303
BenM

Я искал форум и нашел соответствующую информацию, но не ответил на этот вопрос. Я работаю в среде с крайне ограниченной пропускной способностью, и мне нужно создать как можно меньше подписей ECDSA. На данный момент мы используем OpenSSL. Также - поскольку данные подписи должны иметь предсказуемую длину - фиксированный размер.

Я понимаю, что сигнатура ECDSA состоит из двух целых чисел S и R, длина битов которых равна размеру кривой. Кроме того, 6-7 байт, кажется, добавляются, когда я пытаюсь создать подпись, считывая размер из cygwin wc -cкоманды. Я читал во многих местах, что эти издержки могут варьироваться - поэтому мы теряем предсказуемость длины подписи.

Возможное решение - извлечь S и R и передать в двоичном (?) Виде - как поток битов. Я не уверен, возможно ли это, потому что я предполагаю, что он теряет совместимость с библиотекой OpenSSL. Таким образом, нам нужно будет повернуть процесс вспять, построив сигнатуру, используя S и R в кодировке, которую OpenSSL примет.

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

2
R и S должны быть в кодировке DER. Вы можете извлечь их и отправить их «сырыми» и перекодировать их на другом конце. В случае, если какое-либо значение слишком мало (вероятность составляет $ 2 ^ {- 8} = 1/256 $), вы можете обнулить их до максимального размера (то есть размера кривой). [Смотрите медведя для некоторых деталей] (http://crypto.stackexchange.com/a/1797/23623) SEJPM 8 лет назад 0
Спасибо, если декодирование / повторное кодирование работает, это было бы здорово. Тем не менее, посмотрев статью, я не уверен в следующем: 1) Действительно ли возможно декодировать из DER и получать только S и R - как насчет метаданных OpenSSL / других библиотек - их нет? Если есть метаданные, я предполагаю, что они должны быть сохранены, но я был бы счастлив, если бы это не так. 2) Правильно ли я считаю, что DER декодирует стандартное действие, поэтому я могу просто погуглить его, чтобы найти стандартные библиотеки? Я был бы очень признателен за дальнейшую разработку. У меня ограниченный опыт подобных реализаций. BenM 8 лет назад 0
1) Я не уверен, я еще этого не сделал. Но вы можете посмотреть, что дает вам ваш декодер DER, и выяснить, что вам нужно (вероятно, два целых числа в последовательности, которые имеют правильный размер. Если есть метаданные, это, скорее всего, будет что-то вроде кривой-информации, которая вы можете восстановить на другом конце (я полагаю). 2) Да, [декодирование DER] (https://en.wikipedia.org/wiki/Distinguished_Encoding_Rules) является очень стандартной операцией, и у вас не будет проблем с поиском декодеров ( Я надеюсь). SEJPM 8 лет назад 0

1 ответ на вопрос

3
Frode

I know it's old, but I've spent some time trying to figure out the same question lately, so here's an answer of sorts.

Let's assume you've created a signature like so:

$ openssl dgst -sha256 -sign private_secp160k1.pem foo.txt > sign.bin 

Because the curve is 160 bits, the signature is two 20 byte numbers. By default, OpenSSL will have written it in ASN.1's binary DER format. Inspecting it, we should find at least 2 * 20 bytes:

$ xxd -i < sign.bin 0x30, 0x2d, 0x02, 0x14, 0x22, 0xd0, 0x8b, 0xc1, 0x0d, 0x0b, 0x7b, 0xff, 0xe6, 0xc1, 0x77, 0xc1, 0xdc, 0xc4, 0x2f, 0x64, 0x05, 0x17, 0x71, 0xc8, 0x02, 0x15, 0x00, 0xdd, 0xf4, 0x67, 0x10, 0x39, 0x92, 0x1b, 0x13, 0xf2, 0x40, 0x20, 0xcd, 0x15, 0xe7, 0x6a, 0x63, 0x0b, 0x86, 0x07, 0xb6 

In this particular DER encoded signature, there's 47 bytes. A DER or PEM encoded signature can be inspected with OpenSSL's asn1parse command to find out what the bytes are:

$ openssl asn1parse -inform DER -in sign.bin 0:d=0 hl=2 l= 45 cons: SEQUENCE 2:d=1 hl=2 l= 20 prim: INTEGER :22D08BC10D0B7BFFE6C177C1DCC42F64051771C8 24:d=1 hl=2 l= 21 prim: INTEGER :DDF4671039921B13F24020CD15E76A630B8607B6 

In short, it says:

  • At byte 0, there is a DER header of length 2, indicating a there's a SEQUENCE of elements to follow, with a total combined length of 45 bytes.
  • At byte 2, there is a DER header of length 2, indicating an INTEGER element of length 20, the first element of the SEQUENCE (20 bytes are then printed in hex)
  • At byte 24, there is a DER header of length 2, indicating an INTEGER element of length 21, the second element of the SEQUENCE (20 bytes are then printed in hex)

(The d=N just means "depth", so the two INTEGER elements have d==1, because they are part of a sequence.)

Pretty printing the raw bytes from earlier, one can recognize the elements:

$ xxd -i < sign.bin 0x30, 0x2d, # Sequence of length 45 to follow (45 == 0x2d) 0x02, 0x14, # Integer of length 20 to follow (20 == 0x14) # Here come the 20 bytes: 0x22, 0xd0, 0x8b, 0xc1, 0x0d, 0x0b, 0x7b, 0xff, 0xe6, 0xc1, 0x77, 0xc1, 0xdc, 0xc4, 0x2f, 0x64, 0x05, 0x17, 0x71, 0xc8, 0x02, 0x15, # Integer of length 21 to follow (21 == 0x15) 0x00, # The first of the 21 integer bytes (see explanation below!) # Here come the remaining 20 bytes 0xdd, 0xf4, 0x67, 0x10, 0x39, 0x92, 0x1b, 0x13, 0xf2, 0x40, 0x20, 0xcd, 0x15, 0xe7, 0x6a, 0x63, 0x0b, 0x86, 0x07, 0xb6 

So why is the second integer 21 bytes?

Integers in DER are two's complement, so if the first byte of the 20 byte integer is >0x7F, an extra 0x00 byte is prepended, that way the first bit is always 0. In other words, while R and S are 20 bytes numbers, encoding them to DER integers may take an extra byte.

In OpenSSL, the ECDSA_SIG type contains two BIGNUMs. So once you've decoded the DER bytes with d2i_ECDSA_SIG, you can access them with yourSig->r and yourSig->s, which will be <=20 bytes (for 160 bits curves).

It's also possible that R or S need less than 20 bytes, if their first most significant digits happen to be zero. You can find the number of bytes needed for each one with BN_num_bytes, and then write them to a regular byte array with BN_bn2bin for serialiazation.

ECDSA_SIG* ecSig = d2i_ECDSA_SIG(NULL, derBuf, derBufSize); int rBytes = BN_num_bytes(ecSig->r), // Number of bytes needed for R sBytes = BN_num_bytes(ecSig->s); // Number of bytes needed for S // ... unsigned char someBuffer[40] = ; BN_bn2bin( ecSig->r, someBuffer + 20 - rBytes ); // Place R first in the buffer BN_bn2bin( ecSig->s, someBuffer + 40 - sBytes ); // Place S last in the buffer 

On the receiving end, you would then simply recreate the ECDSA_SIG instance by setting its r and s members:

ECDSA_SIG* ecSig = ECDSA_SIG_new(); BN_bin2bn( someBuffer, 20, ecSig->r ); BN_bin2bn( someBuffer + 20, 20, ecSig->s ); 
+1 за это, за то, что помог мне добраться до аналогичной позиции по другой (пока связанной) проблеме, которая у меня была. Для любых будущих искателей форматом фиксированной длины для кодирования значений * R * и * S * является * IEEE P1363 *, который «выравнивает по правому краю» байты * R * и * S * в двух половинах массива байтов , что может быть актуально для любого, кто выполняет взаимодействие между Java (который использует ASN.1 DER) и C # (который использует IEEE P1363) - см. https://www.codeproject.com/kb/security/cryptointeropsign.aspx для получения дополнительной информации. ... jimbobmcgee 7 лет назад 0

Похожие вопросы