Add OpenSSL.

9 files changed, 209 insertions, 5 deletions

diff --git a/docs/libraries.rst b/docs/libraries.rst
index 7108478..e5264ee 100644
--- a/docs/libraries.rst
+++ b/docs/libraries.rst
@@ -676,6 +676,120 @@ wolfSSL
 OpenSSL
 =======
 
+| Version: ``3.1.4``
+| Repository: https://github.com/openssl/openssl
+| Docs: https://www.openssl.org/docs/
+
+Primitives
+----------
+
+ECDH, ECDSA on standard and custom curves.
+x25519, x448 and Ed25519, Ed448.
+
+Has several EC_METHODs.
+ - EC_GFp_simple_method
+ - EC_GFp_mont_method
+ - EC_GFp_nist_method
+ - EC_GFp_nistp224_method
+ - EC_GFp_nistp256_method
+ - EC_GFp_nistz256_method
+ - EC_GFp_nistp521_method
+
+`ossl_ec_GFp_simple_ladder_pre <https://github.com/openssl/openssl/blob/openssl-3.1.4/crypto/ec/ecp_smpl.c#L1493>`__:
+ - Short-Weierstrass
+ - xz
+ - dbl-2002-it-2
+
+`ossl_ec_GFp_simple_ladder_step <https://github.com/openssl/openssl/blob/openssl-3.1.4/crypto/ec/ecp_smpl.c#L1563>`__:
+ - Short-Weierstrass
+ - xz
+ - mladd-2002-it-4
+
+`ossl_ec_GFp_simple_ladder_post <https://github.com/openssl/openssl/blob/openssl-3.1.4/crypto/ec/ecp_smpl.c#L1651>`__:
+ - Short-Weierstrass
+ - xz to y-recovery
+
+ECDH
+^^^^
+
+KeyGen:
+ - Short-Weierstrass
+ - ? via ``EVP_EC_gen -> EVP_PKEY_Q_keygen -> evp_pkey_keygen -> EVP_PKEY_generate -> evp_keymgmt_util_gen -> evp_keymgmt_gen -> EC_KEYMGMT.gen -> ec_gen -> EC_KEY_generate_key -> ec_method.keygen  -> ossl_ec_key_simple_generate_key -> EC_POINT_mul(k, G, NULL, NULL)`` all methods then either ec_method.mul or ossl_ec_wNAF_mul
+    - EC_GFp_simple_method -> ossl_ec_wNAF_mul -> `ossl_ec_scalar_mul_ladder <https://github.com/openssl/openssl/blob/openssl-3.1.4/crypto/ec/ec_mult.c#L145>`__ (Lopez-Dahab ladder) for [k]G and [k]P. Otherwise multi-scalar wNAF with interleaving?
+    - EC_GFp_mont_method -> ossl_ec_wNAF_mul -> `ossl_ec_scalar_mul_ladder <https://github.com/openssl/openssl/blob/openssl-3.1.4/crypto/ec/ec_mult.c#L145>`__ (Lopez-Dahab ladder) for [k]G and [k]P. Otherwise multi-scalar wNAF with interleaving?
+    - EC_GFp_nist_method -> ossl_ec_wNAF_mul -> `ossl_ec_scalar_mul_ladder <https://github.com/openssl/openssl/blob/openssl-3.1.4/crypto/ec/ec_mult.c#L145>`__ (Lopez-Dahab ladder) for [k]G and [k]P. Otherwise multi-scalar wNAF with interleaving?
+       - ec_point_ladder_pre -> ec_method.ladder_pre or EC_POINT_dbl
+       - ec_point_ladder_step -> ec_method.ladder_step or EC_POINT_add + EC_POINT_dbl
+       - ec_point_ladder_post -> ec_method.ladder_post
+       - the methods all use ossl_ec_GFp_simple_ladder_* functions as ladder_*.
+    - EC_GFp_nistp224_method -> ossl_ec_GFp_nistp224_points_mul -> Comb for generator, (signed, Booth) Fixed Window (width = 5) for other points.
+    - EC_GFp_nistp256_method -> ossl_ec_GFp_nistp256_points_mul -> Comb for generator, (signed, Booth) Fixed Window (width = 5) for other points.
+    - EC_GFp_nistz256_method -> ecp_nistz256_points_mul -> (signed, `Booth <https://github.com/openssl/openssl/blob/openssl-3.1.4/crypto/ec/ecp_nistputil.c#L141>`__) Fixed Window (width = 7) with full precomputation from [SG14]_.
+    - EC_GFp_nistp521_method -> ossl_ec_GFp_nistp521_points_mul -> Comb for generator, (signed, Booth) Fixed Window (width = 5) for other points.
+ - Jacobian (or Jacobian-3 for NIST)
+ - Formulas:
+    - EC_GFp_simple_method -> LibreSSL add and LibreSSL dbl
+    - EC_GFp_mont_method -> LibreSSL add and LibreSSL dbl
+    - EC_GFp_nist_method -> LibreSSL add and LibreSSL dbl
+    - EC_GFp_nistp224_method -> BoringSSL P-224 add and dbl
+    - EC_GFp_nistp256_method -> `add-2007-bl <https://github.com/openssl/openssl/blob/openssl-3.1.4/crypto/ec/ecp_nistp256.c#L1235>`__, `dbl-2001-b <https://github.com/openssl/openssl/blob/openssl-3.1.4/crypto/ec/ecp_nistp256.c#L1104>`__
+    - EC_GFp_nistz256_method -> unknown
+    - EC_GFp_nistp521_method -> `add-2007-bl <https://github.com/openssl/openssl/blob/openssl-3.1.4/crypto/ec/ecp_nistp521.c#L1205>`__, `dbl-2001-b <https://github.com/openssl/openssl/blob/openssl-3.1.4/crypto/ec/ecp_nistp521.c#L1087>`__
+
+Derive:
+ - Same as KeyGen, except for:
+    - nistp{224,256,521} methods, where the Fixed Window branch of the scalar multiplier is taken,
+    - nistz256 where a (signed, `Booth <https://github.com/openssl/openssl/blob/openssl-3.1.4/crypto/ec/ecp_nistputil.c#L141>`__) Fixed Window (width = 5) is taken.
+
+ECDSA
+^^^^^
+
+KeyGen:
+ - Same as ECDH.
+
+Sign:
+ - Same as KeyGen.
+
+Verify:
+ - Short-Weierstrass
+ - EC_GFp_simple_method, EC_GFp_mont_method, EC_GFp_nist_method: Interleaved multi-scalar wNAF via ``ec_method.verify_sig -> ossl_ecdsa_simple_verify_sig -> EC_POINT_mul -> ossl_ec_wNAF_mul``.
+ - EC_GFp_nistp224_method, EC_GFp_nistp256_method, EC_GFp_nistp521_method: Interleaved Comb for G and (signed, Booth) Fixed Window (width = 5) for other point.
+ - EC_GFp_nistz256_method: Same as KeyGen for G and same as ECDH Derive for other point.
+
+x25519
+^^^^^^
+Taken from ref10 of Ed25519. See BoringSSL_.
+
+KeyGen:
+ - Twisted-Edwards
+ - Pippenger via ``ossl_x25519_public_from_private -> ge_scalarmult_base``.
+ - Mixes coordinate models::
+
+     ge_p2 (projective): (X:Y:Z) satisfying x=X/Z, y=Y/Z
+     ge_p3 (extended): (X:Y:Z:T) satisfying x=X/Z, y=Y/Z, XY=ZT
+     ge_p1p1 (completed): ((X:Z),(Y:T)) satisfying x=X/Z, y=Y/T
+     ge_precomp (Duif): (y+x,y-x,2dxy)
+
+Derive:
+ - Montgomery
+ - Montgomery ladder via ``ossl_x25519 -> x25519_scalar_mult``
+ - xz coords
+ - Unknown ladder formula.
+
+Ed25519
+^^^^^^^
+Taken from ref10 of Ed25519. See BoringSSL_.
+
+KeyGen:
+ - Same as x25519 KeyGen via ``ossl_ed25519_public_from_private -> ge_scalarmult_base``.
+
+Sign:
+ - Same as x25519 KeyGen via ``ossl_ed25519_sign -> ge_scalarmult_base``.
+
+Verify:
+ - Sliding window (signed) with interleaving? via ``ossl_ed25519_verify -> ge_double_scalarmult_vartime``.
+ - Otherwise same mixed coordinates and formulas.
+
 NSS
 ===
 
@@ -901,7 +1015,7 @@ Go
 
 | Version: ``go1.21.4``
 | Repository: https://github.com/golang/go
-| Docs: 
+| Docs:
 
 Primitives
 ----------
@@ -914,7 +1028,7 @@ ECDH
 
 KeyGen:
  - `Fixed 4-bit window with precomputation <https://github.com/golang/go/blob/go1.21.4/src/crypto/internal/nistec/p224.go#L412>`__ with precomputation (link points to P-224, but others are the same) via ``privateKeyToPublicKey -> ScalarBaseMult``
- - Projective `add-2015-rcb <https://github.com/golang/go/blob/go1.21.4/src/crypto/internal/nistec/p224.go#L215>`__ 
+ - Projective `add-2015-rcb <https://github.com/golang/go/blob/go1.21.4/src/crypto/internal/nistec/p224.go#L215>`__
 
 Derive:
  - `Fixed 4-bit window <https://github.com/golang/go/blob/go1.21.4/src/crypto/internal/nistec/p224.go#L342>`__ via ``ecdh -> ScalarMult``.
@@ -927,7 +1041,7 @@ ECDSA
 
 KeyGen:
  - Same as ECDH KeyGen via ``ecdsa.go:GenerateKey -> generateNISTEC -> randomPoint -> ScalarBaseMult``.
-  
+
 Sign:
  - Same as KeyGen via ``ecdsa.go:SignASN1 -> signNISTEC -> randomPoint -> ScalarBaseMult``.
 
@@ -983,12 +1097,12 @@ KeyGen:
       v.Y.Add(&PP, &MM)
       v.Z.Add(&Z2, &TT2d)
       v.T.Subtract(&Z2, &TT2d)
-    
+
 Sign:
  - Same as Keygen via ``ed25519.go: Sign -> sign ->  ScalarBaseMult``.
 
 Verify:
- - Bos-Coster method via ``ed25519.go: Verify -> verify -> VarTimeDoubleScalarBaseMult``. 
+ - Bos-Coster method via ``ed25519.go: Verify -> verify -> VarTimeDoubleScalarBaseMult``.
  - Same coordinates and formulas as in Keygen.
 
 libgcrypt
diff --git a/docs/references.rst b/docs/references.rst
index 8945aa3..de3beae 100644
--- a/docs/references.rst
+++ b/docs/references.rst
@@ -15,3 +15,4 @@ References
 .. [MT1991] Mazur, B., & Tate, J. (1991). The `p`-adic sigma function. Duke Mathematical Journal, 62 (3), 663-688.
 .. [CO2002] Jean-Sébastien Coron. Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems, https://link.springer.com/chapter/10.1007/3-540-48059-5_25
 .. [DJB02] D.J. Bernstein: Pippenger's Exponentiation Algorithm, https://cr.yp.to/papers/pippenger.pdf
+.. [SG14] Shay Gueron & Vlad Krasnov. Fast prime field elliptic-curve cryptography with 256-bit primes, https://link.springer.com/article/10.1007/s13389-014-0090-x
diff --git a/test/data/formulas/add-openssl-z256 b/test/data/formulas/add-openssl-z256
new file mode 100644
index 0000000..84efc9d
--- /dev/null
+++ b/test/data/formulas/add-openssl-z256
@@ -0,0 +1,2 @@
+source OpenSSL 3.1.4 https://github.com/openssl/openssl/blob/openssl-3.1.4/crypto/ec/ecp_nistz256.c#L312
+coords jacobian-3
diff --git a/test/data/formulas/add-openssl-z256.op3 b/test/data/formulas/add-openssl-z256.op3
new file mode 100644
index 0000000..bc0ccfc
--- /dev/null
+++ b/test/data/formulas/add-openssl-z256.op3
@@ -0,0 +1,23 @@
+Z2sqr = Z2^2
+Z1sqr = Z1^2
+S1 = Z2sqr * Z2
+S2 = Z1sqr * Z1
+S1 = Y1 * S1
+S2 = Y2 * S2
+R = S2 - S1
+U1 = X1 * Z2sqr
+U2 = X2 * Z1sqr
+H = U2 - U1
+Rsqr = R^2
+Z3 = H * Z1
+Hsqr = H^2
+Z3 = H * Z2
+Hcub = Hsqr * H
+U2 = U1 * Hsqr
+Hsqr = 2 * U2
+X3 = Rsqr - Hsqr
+X3 = X3 - Hcub
+Y3 = U2 - X3
+S2 = S1 * Hcub
+Y3 = R * Y3
+Y3 = Y3 - S2
diff --git a/test/data/formulas/add-openssl-z256a b/test/data/formulas/add-openssl-z256a
new file mode 100644
index 0000000..71de9d0
--- /dev/null
+++ b/test/data/formulas/add-openssl-z256a
@@ -0,0 +1,3 @@
+source OpenSSL 3.1.4 https://github.com/openssl/openssl/blob/openssl-3.1.4/crypto/ec/ecp_nistz256.c#L442
+coords jacobian-3
+assume Z2 = 1
diff --git a/test/data/formulas/add-openssl-z256a.op3 b/test/data/formulas/add-openssl-z256a.op3
new file mode 100644
index 0000000..23f90e6
--- /dev/null
+++ b/test/data/formulas/add-openssl-z256a.op3
@@ -0,0 +1,18 @@
+Z1sqr = Z1^2
+U2 = X2 * Z1sqr
+H = U2 - X1
+S2 = Z1sqr * Z1
+Z3 = H * Z1
+S2 = S2 * Y2
+R = S2 - Y1
+Hsqr = H^2
+Rsqr = R^2
+Hcub = Hsqr * H
+U2 = X1 * Hsqr
+Hsqr = 2 * U2
+X3 = Rsqr - Hsqr
+X3 = X3 - Hcub
+H = U2 - X3
+S2 = Y1 * Hcub
+H = H * R
+Y3 = H - S2
diff --git a/test/data/formulas/ladd-openssl-x25519 b/test/data/formulas/ladd-openssl-x25519
new file mode 100644
index 0000000..a40fdc7
--- /dev/null
+++ b/test/data/formulas/ladd-openssl-x25519
@@ -0,0 +1,4 @@
+source OpenSSL 3.1.4 https://github.com/openssl/openssl/blob/openssl-3.1.4/crypto/ec/curve25519.c#L211
+parameter a24
+assume a24 = (a+2)/4
+coords xz
diff --git a/test/data/formulas/ladd-openssl-x25519.op3 b/test/data/formulas/ladd-openssl-x25519.op3
new file mode 100644
index 0000000..f781529
--- /dev/null
+++ b/test/data/formulas/ladd-openssl-x25519.op3
@@ -0,0 +1,18 @@
+tmp0 = X3 - Z3
+tmp1 = X2 - Z2
+X2 = X2 + Z2
+Z2 = X3 + Z3
+Z3 = X2 * tmp0
+Z2 = Z2 * tmp1
+tmp0 = tmp1^2
+tmp1 = X2^2
+X3 = Z3 + Z2
+Z2 = Z3 - Z2
+X4 = tmp1 * tmp0
+tmp1 = tmp1 - tmp0
+Z2 = Z2^2
+Z3 = tmp1 * a24
+X5 = X3^2
+tmp0 = tmp0 + Z3
+Z5 = X1 * Z2
+Z4 = tmp1 * tmp0
diff --git a/test/sca/test_structural.py b/test/sca/test_structural.py
index e12d865..0645972 100644
--- a/test/sca/test_structural.py
+++ b/test/sca/test_structural.py
@@ -164,6 +164,27 @@ def test_efd_formula_match():
             ("secg", "secp256k1"),
             DoublingEFDFormula,
         ],
+        [
+            "add-openssl-z256",
+            ShortWeierstrassModel,
+            "jacobian-3",
+            ("secg", "secp256r1"),
+            AdditionEFDFormula,
+        ],
+        [
+            "add-openssl-z256a",
+            ShortWeierstrassModel,
+            "jacobian-3",
+            ("secg", "secp256r1"),
+            AdditionEFDFormula,
+        ],
+        [
+            "ladd-openssl-x25519",
+            MontgomeryModel,
+            "xz",
+            ("other", "Curve25519"),
+            LadderEFDFormula,
+        ],
     ],
 )
 def test_formula_correctness(name, model, coords, param_spec, formula_type):