Re: [Cfrg] draft-irtf-cfrg-curves-07

[Thomas Pornin <[e-mail]>]

On Thu, Sep 03, 2015 at 05:58:55PM -0700, Michael Hamburg wrote:
> Out of curiosity, how is this specified for RSA?  Are implementations
> required to accept any (N,e)?  What if one or both are even?

As per PKCS#1, implementations are only required to correctly process
"valid RSA public keys". A RSA public key is valid consists in (n,e)
where n is a product of u distinct primes (u >= 2), and e is an integer
between 3 and n-1 such that GCD(e, lambda(n)) = 1. From these rules, we
can infer that in a valid RSA public key, n and e MUST be odd.

As far as I can see, there is no rule that mandates any kind of
verification of the public key. An implementation MAY reject a public
key with an even n or an even e, but is not required to. In any case, a
verifier cannot fully check that a RSA public key is valid (e.g. it
cannot easily check that the prime factors of the modulus are distinct).

To put things into perspective, nothing in PKCS#1 says that, say,
400-bit RSA keys should be rejected (except when using a hash function
such that the padded size would simply not fit in the modulus). Yet many
implementations will reject such key sizes, and nobody clamours about
the non-compliance of such a behaviour. In fact, it is generally
considered a good thing to refuse to use a public key which is way too
small to achieve decent security.


In practice, an even modulus messes up with Montgomery multiplication;
to support exponentiations modulo an even n, one must include some
specific extra code. An RSA implementation that uses a generic
big-integer library (say, a Java implementation that runs over
java.math.BigInteger) may accept an even modulus and compute the
"proper" value x^e mod n. A dedicated RSA implementation will either
reject an even modulus, or compute something else than x^e mod n,
because it will lack the code for handling modular exponentiations
modulo an even modulus.

As for an even public exponent, there again, some implementations will
accept it, others will reject, and I suppose that some will simply
assume that the least significant bit is 1 and ignore the provided
value (it depends on whether the implementation handles the exponent
bits from least to most significant, or not).

To give an actual example: Microsoft's implementation of RSA (CryptoAPI)
used to accept e=1. It was even documented as a feature, to be used for
simple plaintext extraction of symmetric key through key wrapping. In
Windows 8.1, this ceased to work; I could not find any documentation
about that change.


I suppose the theory is that when you use a public key, whether for
encryption or signature verification, then you already have validated
that the public key is "the right one", and attack models with a
corrupted public key then make no sense at all. This is the classic,
X.509-certificates view of things, which may be restrictive.


So, basically, PKCS#1 does not specify implementation behaviour against
invalid public keys. Rejection is allowed, not mandated.


	--Thomas Pornin