Subject: [pkix] Fermat 4 Standard

From: Anderson Farias <[email-masked]>
Date: Thu, 2 Oct 2014 17:03:07 -0300

Hi,

After comparing two PKCS#10 with public exponent fermat 4, I found out that
one of them was generated with a value composed by three octets (01 00 01)
and the other one with a value composed by 4 octets (00 01 00 01). 

Even using different values, both PKCS#10 were decoded by ASN1 editors.

I searched on RFC 5280 but I didn´t find any standard for using Fermat 4  in
X.509 public key infrastructure certificates. 
 
Is there any RFC  with requirements for Fermat 4 usage with X.509?
 
Thanks and best regards,
 
Anderson Farias

---

From: Erwann Abalea <[email-masked]>
Date: Thu, 2 Oct 2014 22:26:21 +0200

Bonsoir,

2014-10-02 22:03 GMT+02:00 Anderson Farias <[email-masked]>:

> After comparing two PKCS#10 with public exponent fermat 4, I found out
> that one of them was generated with a value composed by three octets (01 00
> 01) and the other one with a value composed by 4 octets (00 01 00 01).
>
>
The second one is invalid DER encoding, as the length is not the smallest
possible.

Different binary encodings, but the values are the same.
I guess that your first one ends with "02 03 01 00 01" while the second one
ends with "02 04 00 01 00 01".
The first "02" declares an INTEGER, "03"/"04" is the length of the encoded
value, the rest is the value. 0x00010001 and 0x010001 are 2 different
textual representations of the same value (65537), that's similar here.

I searched on RFC 5280 but I didn´t find any standard for using Fermat
4  in X.509 public key infrastructure certificates.
X.509 prefers DER encoding (X.690) of objects, you're talking about RSA
keys, which are defined in PKCS#1. All this is standardized, and the
standards are freely downloadable.

-- 
Erwann.

---

From: Anderson Farias <[email-masked]>
Date: Thu, 2 Oct 2014 18:06:57 -0300

Hi Erwann,

Your answer was perfect for my understanding.

Thank you very much,

Anderson

De: Erwann Abalea [mailto:[email-masked]] 
Enviada em: quinta-feira, 2 de outubro de 2014 17:26
Para: Anderson Farias
Cc: [email-masked]
Assunto: Re: [pkix] Fermat 4 Standard

Bonsoir,

After comparing two PKCS#10 with public exponent fermat 4, I found out that one of them was generated with a value composed by three octets (01 00 01) and the other one with a value composed by 4 octets (00 01 00 01).

The second one is invalid DER encoding, as the length is not the smallest possible.

I guess that your first one ends with "02 03 01 00 01" while the second one ends with "02 04 00 01 00 01".

The first "02" declares an INTEGER, "03"/"04" is the length of the encoded value, the rest is the value. 0x00010001 and 0x010001 are 2 different textual representations of the same value (65537), that's similar here.

I searched on RFC 5280 but I didn´t find any standard for using Fermat 4  in X.509 public key infrastructure certificates. 

X.509 prefers DER encoding (X.690) of objects, you're talking about RSA keys, which are defined in PKCS#1. All this is standardized, and the standards are freely downloadable.

-- 
Erwann.

---

From: Peter Sylvester <[email-masked]>
Date: Fri, 03 Oct 2014 09:56:16 +0200

On 10/02/2014 11:06 PM, Anderson Farias wrote:
> *De:*Erwann Abalea [mailto:[email-masked]]
> *Enviada em:* quinta-feira, 2 de outubro de 2014 17:26
> *Para:* Anderson Farias
> *Cc:* [email-masked]
> *Assunto:* Re: [pkix] Fermat 4 Standard
>
> Bonsoir,
>
> 2014-10-02 22:03 GMT+02:00 Anderson Farias <[email-masked] 
> <mailto:[email-masked]>>:
>
> After comparing two PKCS#10 with public exponent fermat 4, I found out that one of them was 
> generated with a value composed by three octets (01 00 01) and the other one with a value composed 
> by 4 octets (00 01 00 01).
>
> The first "02" declares an INTEGER, "03"/"04" is the length of the encoded value, the rest is the 
> value. 0x00010001 and 0x010001 are 2 different textual representations of the same value (65537), 
> that's similar here.
>
> X.509 prefers DER encoding (X.690) of objects, you're talking about RSA keys, which are defined in 
> PKCS#1. All this is standardized, and the standards are freely downloadable.
>
> -- 
> Erwann.
>
On 10/02/2014 11:34 PM, Viktor Dukhovni wrote:
> On Thu, Oct 02, 2014 at 04:25:16PM -0300, Anderson Farias wrote:
>> that one of them was generated with a value composed by three octets (01
>> 00 01) and the other one with a value composed by 4 octets (00 01 00 01).
> These are not different values, they are different BER encodings
> of the same value.  The first form is also DER, while the second
> is not.
>> I searched on RFC 5280 but I didn't find any standard for using Fermat 4
>> in X.509 public key infrastructure certificates.
> This has nothing to do with F_4, rather the issue is how the integer
> exponent in X.509 SPKI RSA keys is encoded.  BER encodings are
> widely tolerated in X.509 for interoperability reasons, so both
> encodings are usable though of course the DER format should be
> used.
>
> No, but there are ITU documents that define ASN.1 encoding.
>
>      Recommendation ITU-T X.690 (2002) | ISO/IEC 8825-1:2002, Information
>      technology - ASN.1 encoding rules: Specification of Basic Encoding
>      Rules (BER), Canonical Encoding Rules (CER) and Distinguished
>      Encoding Rules (DER)
>
Well, actually it is the following but the rules concerning content encoding for integers
haven't changed since 30 years.

ITU X.690 (11/2008) | ISO/IEC 8825-1:2008

02 03 010001   is a correct BER and DER encoding of the F4 integer

02 04 00010001   is simply incorrect. (violates 8.3.2b)

02 82 0003 010001  is a correct BER encoding but not DER. (does not respect 10.1)

8.3 Encoding of an integer value

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:
a)  shall not all be ones; and
b)  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.
NOTE – The value of a two's complement binary number is derived by numbering the bits in the 
contents octets, starting with bit
1 of the last octet as bit zero and ending the numbering with bit 8 of the first octet. Each bit is 
assigned a numerical value of 2 N ,
where N is its position in the above numbering sequence. The value of the two's complement binary 
number is obtained by
summing the numerical values assigned to each bit for those bits which are set to one, excluding bit 
8 of the first octet, and then
reducing this value by the numerical value assigned to bit 8 of the first octet if that bit is set 
to one.

DER does not have restrictions for the encoding of the content octets of an integer.

10 Distinguished encoding rules
The encoding of a data values employed by the distinguished encoding rules is the basic encoding 
described in clause
8, together with the following restrictions and those also listed in clause 11.
10.1 Length forms
The definite form of length encoding shall be used, encoded in the minimum number of octets. [Contrast
with 8.1.3.2 b).]

best
Peter