Subject: Fermat 4 Standard

From: Anderson Farias <[email-masked]>
Date: Thu, 2 Oct 2014 16:25:16 -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: Viktor Dukhovni <[email-masked]>
Date: Thu, 2 Oct 2014 21:34:27 +0000

On Thu, Oct 02, 2014 at 04:25:16PM -0300, Anderson Farias wrote:
> 
> 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).

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.

> Is there any RFC  with requirements for Fermat 4 usage with X.509?

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)

-- 
	Viktor.

---

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

>      Rules (BER), Canonical Encoding Rules (CER) and Distinguished
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).]