Skip to content
  • Nicola Tuveri's avatar
    EC point multiplication: add `ladder` scaffold · 37124360
    Nicola Tuveri authored
    
    for specialized Montgomery ladder implementations
    
    PR #6009 and #6070 replaced the default EC point multiplication path for
    prime and binary curves with a unified Montgomery ladder implementation
    with various timing attack defenses (for the common paths when a secret
    scalar is feed to the point multiplication).
    The newly introduced default implementation directly used
    EC_POINT_add/dbl in the main loop.
    
    The scaffolding introduced by this commit allows EC_METHODs to define a
    specialized `ladder_step` function to improve performances by taking
    advantage of efficient formulas for differential addition-and-doubling
    and different coordinate systems.
    
    - `ladder_pre` is executed before the main loop of the ladder: by
      default it copies the input point P into S, and doubles it into R.
      Specialized implementations could, e.g., use this hook to transition
      to different coordinate systems before copying and doubling;
    - `ladder_step` is the core of the Montgomery ladder loop: by default it
      computes `S := R+S; R := 2R;`, but specific implementations could,
      e.g., implement a more efficient formula for differential
      addition-and-doubling;
    - `ladder_post` is executed after the Montgomery ladder loop: by default
      it's a noop, but specialized implementations could, e.g., use this
      hook to transition back from the coordinate system used for optimizing
      the differential addition-and-doubling or recover the y coordinate of
      the result point.
    
    This commit also renames `ec_mul_consttime` to `ec_scalar_mul_ladder`,
    as it better corresponds to what this function does: nothing can be
    truly said about the constant-timeness of the overall execution of this
    function, given that the underlying operations are not necessarily
    constant-time themselves.
    What this implementation ensures is that the same fixed sequence of
    operations is executed for each scalar multiplication (for a given
    EC_GROUP), with no dependency on the value of the input scalar.
    
    Co-authored-by: default avatarSohaib ul Hassan <soh.19.hassan@gmail.com>
    Co-authored-by: default avatarBilly Brumley <bbrumley@gmail.com>
    
    Reviewed-by: default avatarAndy Polyakov <appro@openssl.org>
    Reviewed-by: default avatarMatt Caswell <matt@openssl.org>
    (Merged from https://github.com/openssl/openssl/pull/6690)
    37124360
To find the state of this project's repository at the time of any of these versions, check out the tags.