ASN.1 Integer Encoding (RSA public key related)

ASN.1 Integer Encoding (RSA public key related)

Post by James Come » Thu, 17 Jan 2002 00:01:57



Hello,
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
exponent.

The modulus is 64 bytes long but since integers are encoded in two's
complement,
there is a leading 00 byte so that the modulus is not considered
negative.  Thus the
integer is 65 bytes
0241 00C8934A 22BE0C99......

The public exponent value is 65537.  However it is encoded as
020301 0001.

65537 is 010001H which is     0000 0001 0000 0000 0000 0001B
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
complement.
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.  But the public
exponent in
the public key does not seem to be encoded that way.

Thanks
Jim

--

Ericsson IP Infrastructure          Voice (919) 472 - 9932
920 Main Campus Drive, Suite 544    Fax   (919) 472 - 9999
Raleigh, NC 27606

 
 
 

ASN.1 Integer Encoding (RSA public key related)

Post by Doug Ste » Thu, 17 Jan 2002 04:37:21


On Tue, 15 Jan 2002 10:01:57 -0500, James Comen


>--------------6FFD609F64058827FDB7C1FF
>Content-Type: text/plain; charset=us-ascii
>Content-Transfer-Encoding: 7bit

>Hello,
>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
>exponent.

>The modulus is 64 bytes long but since integers are encoded in two's
>complement,
>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
interoperability problem.

Quote:>0241 00C8934A 22BE0C99......

>The public exponent value is 65537.  However it is encoded as
>020301 0001.

>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.

Quote:>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
>complement.
>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.

doug

 
 
 

1. RSA Public Key Crypto Systems

I am working on a term project for a Data Structures class, and I am
trying to locate any source code or algorithms for a Public Key Crypto System.
Someone here at school had suggested locating the source code for
Crypt.  I realize that, depending on where I get the source from, that
I will most probably not be able to use the code for my project.  What
I would like to code for is to have as many examples as possible to
examine.  So far I have only one source of information, and no code or
algorithms to go by.

Our source drive is down here at the university, or I would have
gotten the source from minix from someone here if that had been
possible.

Anything that any of you could suggest would be a great help...

Thank you
--
Aaron Herskowitz   <=========> University of Kentucky: Unix Lab Consultant,

(606)231-0049

2. The ultimate compression (large reply)

3. The difference between RSA and DSS public key?

4. ruggedizing st's

5. RSA Public-Key Encryption?

6. Cannot use SSH Mindterm to connect to FreeBSD box...

7. Can we use RSA's private key as DES's secret key?

8. Can RSA key users verify and/or decrypt a message encrypted/singed with a DH key

9. Signing a DH/DSS key with my old RSA key

10. RSA Keys on Key Server?

11. MIB browsers: ASN.1 INTEGERs signed/unsigned?

12. Differences in Public Key block (Sending key to keyserver Vs Copy + Paste)