JCA design for RFC 7748

[Xuelei Fan]

Hi,

I want to extend the comment a little bit.

1. The background
A elliptic curve is determined by either an equation of form
      y^2 = x^3 + ax + b            (1) [Weierstrass form]
or
      y^2 + xy = x^3 + ax^2 + b.    (2)

However, some other forms may also be used.  For example:
      y^2 = x(x-1)(x-r)             (3)
or
      By^2 = x^3 + Ax^2 + x         (4) [RFC 7748, Montgomery curve]
      x^2 + y^2 = 1 + dx^2y^2       (5) [RFC 7748, Edwards curve]

In general, any elliptic curve can be written in Weierstrass form (1) or 
(2).  That's, Montgomery curve and Edwards curve can be expressed in 
Weierstrass form.

2. Where we are now?
In JDK, an elliptic curve is defined in the Weierstrass form ((1)/(2)). 
See java.security.spec.EllipticCurve:

     EllipticCurve​(ECField field, BigInteger a, BigInteger b)

In theory, the existing APIs can be used for RFC 7748, by converting the 
Montgomery curve and Edwards curve to the Weierstrass form.  However, 
the conversion can be misleading and complicate the implementation 
significantly.  For example, before using a point Weierstrass form (x, 
y), the implementation need to convert it to Montgomery curve (x', -) so 
as to use the fully potential of RFC 7748.   The curves returned in 
public APIs need to use (x, y), while the implementation need to use 
(x', y').  It's very confusing and the compatibility impact could be 
significant.  For example:

     public something(ECPublicKey ecPublicKey)  {
        // Problem: If no other information, it is unclear
        // whether the ecPublicKey can be used for a particular
        // signature verification or not when the RFC 7748/8032
        // get supported.

        // Problem: an old application may use ecPublicKey for
        // the old style operation, even the ecPublicKey is supposed
        // to be x25519.  It's not easy to control the behavior in
        // legacy application code, and may introduce unexpected
        // security issues.
     }

     public KeyAgreement getKeyAgreement(AlgorithmParameterSpec aps) {
        // Problem: the code bellow should be comment in the current
        // code.  However, the ECParameterSpec may not be able to use
        // for the old style "EC" key agreement.
        //
        // JDK crypto provider can take special action to avoid this
        // issue in the JCA/JCE implementation.  But it cannot be
        // granted other provider can do this as well, and old
        // provider may run into problems as well.
        if (aps instance of ECParameterSpec) {
            return KeyAgreement.getInstance("EC");
        }
     }

What's the problem with ECPublicKey/ECPrivateKey/ECKey? It's mainly 
about the ECParameterSpec:

      ECParameterSpec ECKey.getParams​()

and ECParameterSpec is using java.security.spec.EllipticCurve.  This 
design makes it pretty confusing to use ECPublicKey/ECPrivateKey/ECKey 
for RFC 7748 (Edwards curve form and Montgomery curve form).

Can EllipticCurve be extended to support more forms? The 
java.security.spec.EllipticCurve defines two methods to get the 
coefficients of Weierstrass form.
      public BigInteger getA()
      public BigInteger getB()

The 'A' and 'B' may not exist in other forms, for example the (3)(4)(5) 
forms above.  While, the spec might be able to be updated by throwing 
UnsupportedOperationException for getA() and getB() for the (3)(4)(5) 
forms, and define new extended classes for new forms, like:
      public MCEllipticCurve extends EllipticCurve   // Montgomery curve
      public EDEllipticCurve extends EllipticCurve   // Edwards curve

However, I'm not very sure of the compatibility impact (see above).

3. Where we are not now?
Using named curves is popular.  There is a ECGenParameterSpec class 
using named curves:
      ECGenParameterSpec​ ecgp =
          new ECGenParameterSpec​(secp256r1);
      KeyPairGenerator kpg = KeyPairGenerator.getInstance("EC");
      kpg.initialize(ecpg);
      KeyPair kp = kpg.generateKeyPair​();

      ECPublicKey pubKey = (ECPublicKey)kp.getPublic();
      String keyAlgorithm = pubKey.getAlgorithm​();  // "EC"

However, it is used for key generation only.  Once the keys are 
generated, there is no public API to know the name of the curve in 
ECKey.  ECKey.getAlgorithm() will return "EC" only.  If it is required 
to known whether a key is of a named curve, the solution is not 
straightforward.

4. A general proposal
Support named curves could be a solution for #2 and #3 concerns above. 
For named curves, the parameters are defined explicitly.  So, it is 
REQUIRED to have the public APIs for named curves' parameters any more. 
It can be something hidden in the implementation layer.  The key pair 
generation may looks like:

     KeyPairGenerator kpg =
         KeyPairGenerator.getInstance("ECWithSecp256k1");
     KeyPair kp = kpg.generateKeyPair​();

     PublicKey pubKey = kp.getPublic();
     String keyAlgorithm = pubKey.getAlgorithm​();  // "ECWithSecp256k1"

As no explicit parameters is required, the EllipticCurve issue for 
Edwards curve form and Montgomery curve form in #2 is not a issue any 
more here.

The compatibility impact is limited as the name "ECWithSecp256k1" is not 
used in the past, and the Weierstrass form APIs, like 
ECKey/ECParameterSpec/EllipticCurve, are not necessarily to be used in 
this solution.

The benefits: simplify the APIs for named curves (including the 
Weierstrass form), and simplify the support of named curves for Edwards 
curve form and Montgomery curve form.

The disadvantages: no support of arbitrary curves (no surprise as this 
is a named curve solution), and new learn curve to use this new solution.

5. Can be more aggressive?
It looks amazing to support arbitrary curves for Edwards curve form and 
Montgomery curve form, as JDK did for Weierstrass form.  However, 
because of the compatibility impact (see #2), a new set of algorithms 
names, interfaces and specs may be required.  It could be overloaded if 
the requirements are not so strong in practice.  If arbitrary curves 
support is strong, it can be re-considered in the future.

Per my understanding, supporting named curves and arbitrary curves can 
be two things, and can be considered in different stages.  However, the 
design needs to take care of the potential conflicts between the two 
solutions.

Thanks,
Xuelei

On 8/8/2017 12:43 PM, Adam Petcher wrote:
> On 8/8/2017 12:50 PM, Michael StJohns wrote:
> 
>>
>> We'll leave this for later.  But generally, the JCA is a general 
>> interface to a set of crypto primitives modeled on just a few key 
>> types.  To go in the direction you want to go it you need to explain 
>> why its impossible to model an elliptic curve as an elliptic curve. As 
>> I noted, I think that the inclusion of extension of ECField is 
>> probably all that's necessary for representing both public and private 
>> key pairs here.
> 
> The problem with the existing EC classes (EllipticCurve, ECPoint, etc.) 
> is that they are intended to represent curves in Weierstrass form: y^2 = 
> x^3 + ax + b. EllipticCurve has two parameters "a" and "b" corresponding 
> to the coefficients in the equation above. RFC 7748 uses elliptic curves 
> in Montgomery form: y^2 = x^3 + ax^2 + x. So the parameters are 
> different. Further complicating things: every curve in Montgomery form 
> has an isomorphic curve in Weierstrass form (but not vice-versa).
> 
> So if we reuse EllipticCurve (and related classes), we could map the 
> parameters onto Montgomery curve coefficients. For example interpret "a" 
> as the second-degree coefficient instead of the first-degree 
> coefficient, and ignore "b". But we have the problem that the programmer 
> may not know when the parameters will be interpreted as Weierstrass 
> coefficients instead of Montgomery coefficients. I am particularly 
> concerned about this because these parameters were always interpreted as 
> Weierstrass coefficients in the past.
> 
> So we would want a way to tag the objects and check the tags to ensure 
> that they are not misused. You suggested making new ECField subclasses 
> for Montgomery/Edwards curves. The field used in RFC 7748/8032 is GF(p), 
> which corresponds to the existing class ECFieldFp. So it seems strange 
> and surprising to use this member to identify how coefficients should be 
> interpreted, because this has nothing to do with the field. Though I can 
> see why this approach is appealing, because the field is the only part 
> of EllipticCurve that was designed to be extensible. If the coefficients 
> (and their interpretation) were similarly extensible, then we wouldn't 
> have these problems.
> 
> In short: I'm not sure that reusing the existing EC classes is a good 
> idea, because they were intended for something else, they are not 
> general enough, and the potential for misuse/confusion is high.
> 
>