On Tue, 15 Jan 2002 10:01:57 -0500, James Comen
>Content-Type: text/plain; charset=us-ascii
>I've got a question about the encoding of an integer, specifically an
>integer within a public key.
>In this public key, there are two integers, a modulus and a public
>The modulus is 64 bytes long but since integers are encoded in two's
>there is a leading 00 byte so that the modulus is not considered
>negative. Thus the integer is 65 bytes
This is the correct incoding for the modulus, assuming that it is 512
bit modulus (size a multiple of 8). The ASN.1 INTEGER is designed to
encode positive and negative values, with negative values using the
2;s complement scheme. Finite field values are strictly positive.
Since the most significant bit of the most significant byte of the 64
byte number is a 1, an insignificant octet of zeros must be prepended
to it in order to maintain a positive value. If this were not done, an
ASN.1 decoder would consider the number to be a negative value in the
2's complement form.
Keep in mind that not everybody follows the rules. I remember a case
where Microsoft violated the ASN.1 encoding and it created an
>0241 00C8934A 22BE0C99......
>The public exponent value is 65537. However it is encoded as
>65537 is 010001H which is 0000 0001 0000 0000 0000 0001B
Since this is a 17 bit number (size not a multiple of 8), the most
significant bit of the most significant byte is zero, the number would
be considered positive by any ASN.1 decoder. The leading,
insignificant zero byte is not necessary.
>Two's complement would be 1111 1110 1111 1111 1111 1110B + 1B =
> 1111 1110 1111
>1111 1111 1111B
> F E
>F F F F
>Does this look right? If so, the 65537 isn't encoded as two's
>I created many public keys and the exponent was always encoded this way.
>Any ideas why it doesn't seem to be two's complement?
>I assume all integers are encoded as two's complement.
Here's your mistake. Only negative numbers are encoded as 2's form.
and the most significant bit indicates the sign of the number. If the
most significant bit is zero, the sign is positive and the number is
encoded as a positive number. If the most significant bit is a one,
the sign is negative and the value is in 2's complement form.
Quote:>But the publicexponent in
>the public key does not seem to be encoded that way.
Because it is already positive.