ASN.1/DER Кодирование целых чисел
В настоящее время я начинаю работать с кодировкой DER (Distinguished Encoding Rules) и у меня проблемы с пониманием кодировки целых чисел.
В справочном документе https://www.itu.int/ITU-T/studygroups/com17/languages/X.690-0207.pdf эта кодировка определяется следующим образом:
8.3.1 The encoding of an integer value shall be primitive. The contents octets shall consist of one or more octets.
8.3.2 If the contents octets of an integer value encoding consist of more than one octet, then the bits of the first octet and bit 8 of the second octet:
shall not all be ones; and
shall not all be zero.
NOTE – These rules ensure that an integer value is always encoded in the smallest possible number of octets.
8.3.3 The contents octets shall be a two's complement binary number equal to the integer value, and consisting of bits 8 to 1 of the first octet, followed by bits 8 to 1 of the second octet, followed by bits 8 to 1 of each octet in turn up to and including the last octet of the contents octets.
На другом сайте, https://docs.microsoft.com/en-us/windows/desktop/seccertenroll/about-integer, объясняется, что для положительных чисел, двоичное представление которых начинается с 1, впереди добавляется нулевой байт. Это также упоминается в ответах на предыдущий вопрос о stackoverflow: Основное правило кодирования ASN для целого числа.
К сожалению, из этих ответов я не понимаю, как эту последнюю инструкцию можно вывести из правил справочного документа.
Например, если я хочу закодировать число 128, почему я не могу сделать это как
[байт тега] [байт длины] 10000000?
Я знаю, что правильной кодировкой будет [байт тега] [байт длины] 00000000 10000000, но какое условие нарушено вариантом выше? Вероятно, это как-то связано с дополнением до двух, но разве дополнение до двух для числа 128 снова не равно 10000000?
Надеюсь, вы поможете мне понять, почему описание на сайте Microsoft эквивалентно исходному определению. Спасибо.
К сожалению, пока нет. Я уже рассматривал этот документ, но в нем также не упоминается, что для отрицательных целых чисел добавляется дополнительный нулевой байт. Вместо этого в документе говорится: «Кодирование отрицательных целых чисел имеет свои правила», а затем описывается дополнение до двойки своими словами. Но в справочном документе для ASN.1 слово «отрицательный» встречается только три раза, и ни один из них не относится к кодированию целых чисел. Вот я и до сих пор удивляюсь, откуда берутся эти "свои правила".
@Bilbo Это «есть», но ни один здравомыслящий человек не выразил бы это так. Знаковое ограничение состоит в том, что старший бит соответствует знаковому биту. Например. для положительного 0x80 это нарушается, и вы расширяетесь до 0x0080, чтобы выполнить ограничение знака.
Ответы 2
Правило Дополнение до двух (8.3.3) говорит, что если установлен старший бит первого (наименьшего индекса) байта содержимого, число отрицательное.
02 01 80 имеет содержимое 0b1000_0000. Поскольку установлен старший бит, число отрицательное.
Переверните все биты (0b0111_1111), затем добавьте один: 0b1000_0000; это означает, что он представляет отрицательное 128.
Для менее вырожденного примера 0b1000_0001 => 0b0111_1110 => 0b0111_1111, показывая, что 0x81 отрицательное число 127.
Для числа (положительного) 127, поскольку старший бит не установлен, число интерпретируется как положительное, поэтому содержимое просто 0b0111_1111 или 0x7F, что приводит к 02 01 7F
Извините, но я не понимаю, как это отвечает на мой вопрос. Возможно, я не смог ясно изложить свою мысль. Я в основном понимаю, как работает представление чисел в дополнении Two. Мой вопрос относится к предложению с веб-сайта Microsoft: «Если целое число положительное, но старший бит равен 1, к содержимому добавляется начальный 0x00, чтобы указать, что число не отрицательное». Я до сих пор не понимаю, откуда это?
Дополнительный 0 байт означает, что старший бит первого байта не установлен, поэтому значение равно положительным 15, а числу 0b000_0000_1000_0000 (128). Без него установлен старший бит, поэтому число отрицательное: дополнение до двух 7-битного значения 0b000_0000, что (в 8-битной стране) -128.
Хорошо, я думаю, теперь я вижу, где я был неправ. Я думал, что 1000 0000 — это двоичное представление числа 128; но это НЕ представление в виде дополнения до двух. Если мы рассматриваем подписанные байты, нам НУЖЕН 0 в начале, поэтому мы хотели бы поставить нулевой бит в начале. И поскольку мы должны использовать полные байты в нашей кодировке, мы должны поместить полный нулевой байт в начале.
@ Бильбо Да, это почти все.
Просто добавлю еще одну часть, которая внесла свой вклад в мое замешательство: в статье Microsoft говорится: «Поле Value триплета TLV содержит закодированное целое число, если оно положительное, или его дополнение до двух, если оно отрицательное». Здесь должна иметься в виду ОПЕРАЦИЯ взятия дополнения до двух (путем переключения битов и добавления 1); очевидно, напротив, в справочном документе говорится, что всегда (!) «октеты содержимого должны быть двоичным числом с дополнением до двух, равным целому значению». Здесь имеется в виду не операция, а ПРЕДСТАВЛЕНИЕ в дополнении до двойки, которое переключает биты только для отрицательных чисел.
Представление дополнения @Bilbo Two означает, что «если установлен старший бит, это отрицательное число в дополнении до двух» и «если он не установлен, это положительное целое число». Это раздел «Возможные неоднозначности терминологии» в Википедии.
Общий шаблон в ASN.1: TLV, тип/длина/значение.
Тип: один октет, 0x02 для целых чисел
Значение: ответ на дополнение до двух с ограничением знака приведен выше.
Кодирование длины имеет два модуса:
Старший бит октета первой длины не установлен: тогда октет представляет собой длину содержимого.
Устанавливается старший значащий бит первого октета длины: затем за первым октетом следуют (значение-128) октеты, формирующие фактическую длину как неотрицательное целое число, порядок байтов от старшего.
Длины 0...127 соответствуют первому правилу, 128... второму.
Может это поможет