LibCrypto: Implement the SECP256r1 elliptic curve

This implementation of the secp256r1 elliptic curve uses two techniques
to improve the performance of the operations.

1. All coordinates are stored in Jacobian form, (X/Z^2, Y/Z^3, Z), which
   removes the need for division operations during point addition or
   doubling. The points are converted at the start of the computation,
   and converted back at the end.

2. All values are transformed to Montgomery form, to allow for faster
   modular multiplication using the Montgomery modular multiplication
   method. This means that all coordinates have to be converted into
   this form, and back out of this form before returning them.

1 files changed, 60 insertions, 0 deletions

diff --git a/Tests/LibCrypto/TestCurves.cpp b/Tests/LibCrypto/TestCurves.cpp
index 4017bba52b..91189803d0 100644
--- a/Tests/LibCrypto/TestCurves.cpp
+++ b/Tests/LibCrypto/TestCurves.cpp
@@ -5,6 +5,7 @@
  */
 
 #include <AK/ByteBuffer.h>
+#include <LibCrypto/Curves/SECP256r1.h>
 #include <LibCrypto/Curves/X25519.h>
 #include <LibCrypto/Curves/X448.h>
 #include <LibTest/TestCase.h>
@@ -160,3 +161,62 @@ TEST_CASE(test_x448)
 
     EXPECT_EQ(shared_alice, shared_bob);
 }
+
+TEST_CASE(test_secp256r1)
+{
+    // clang-format off
+    u8 alice_private_key_data[32] {
+        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
+    };
+
+    u8 alice_public_key_data[65] {
+        0x04,
+        0x6B, 0x17, 0xD1, 0xF2, 0xE1, 0x2C, 0x42, 0x47, 0xF8, 0xBC, 0xE6, 0xE5, 0x63, 0xA4, 0x40, 0xF2,
+        0x77, 0x03, 0x7D, 0x81, 0x2D, 0xEB, 0x33, 0xA0, 0xF4, 0xA1, 0x39, 0x45, 0xD8, 0x98, 0xC2, 0x96,
+        0x4F, 0xE3, 0x42, 0xE2, 0xFE, 0x1A, 0x7F, 0x9B, 0x8E, 0xE7, 0xEB, 0x4A, 0x7C, 0x0F, 0x9E, 0x16,
+        0x2B, 0xCE, 0x33, 0x57, 0x6B, 0x31, 0x5E, 0xCE, 0xCB, 0xB6, 0x40, 0x68, 0x37, 0xBF, 0x51, 0xF5,
+    };
+
+    u8 bob_private_key_data[32] {
+        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02,
+    };
+
+    u8 bob_public_key_data[65] {
+        0x04,
+        0x7C, 0xF2, 0x7B, 0x18, 0x8D, 0x03, 0x4F, 0x7E, 0x8A, 0x52, 0x38, 0x03, 0x04, 0xB5, 0x1A, 0xC3,
+        0xC0, 0x89, 0x69, 0xE2, 0x77, 0xF2, 0x1B, 0x35, 0xA6, 0x0B, 0x48, 0xFC, 0x47, 0x66, 0x99, 0x78,
+        0x07, 0x77, 0x55, 0x10, 0xDB, 0x8E, 0xD0, 0x40, 0x29, 0x3D, 0x9A, 0xC6, 0x9F, 0x74, 0x30, 0xDB,
+        0xBA, 0x7D, 0xAD, 0xE6, 0x3C, 0xE9, 0x82, 0x29, 0x9E, 0x04, 0xB7, 0x9D, 0x22, 0x78, 0x73, 0xD1,
+    };
+
+    u8 private_key_data[32] {
+        0x01, 0xff, 0xf8, 0x1f, 0xc0, 0x00, 0x00, 0x00, 0x00, 0xff, 0x80, 0x1f, 0xff, 0xc0, 0xf8, 0x1f,
+        0x01, 0xff, 0xf8, 0x00, 0x1f, 0xc0, 0x05, 0xff, 0xff, 0xff, 0x80, 0x00, 0x00, 0xff, 0xff, 0xfc,
+    };
+
+    u8 expected_public_key_data[65] {
+        0x04,
+        0x34, 0xdf, 0xbc, 0x09, 0x40, 0x4c, 0x21, 0xe2, 0x50, 0xa9, 0xb4, 0x0f, 0xa8, 0x77, 0x28, 0x97,
+        0xac, 0x63, 0xa0, 0x94, 0x87, 0x7d, 0xb6, 0x58, 0x62, 0xb6, 0x1b, 0xd1, 0x50, 0x7b, 0x34, 0xf3,
+        0xcf, 0x6f, 0x8a, 0x87, 0x6c, 0x6f, 0x99, 0xce, 0xae, 0xc8, 0x71, 0x48, 0xf1, 0x8c, 0x7e, 0x1e,
+        0x0d, 0xa6, 0xe1, 0x65, 0xff, 0xc8, 0xed, 0x82, 0xab, 0xb6, 0x59, 0x55, 0x21, 0x5f, 0x77, 0xd3,
+    };
+    // clang-format on
+
+    ReadonlyBytes alice_private_key { alice_private_key_data, 32 };
+    ReadonlyBytes alice_public_key { alice_public_key_data, 65 };
+    ReadonlyBytes bob_private_key { bob_private_key_data, 32 };
+    ReadonlyBytes bob_public_key { bob_public_key_data, 65 };
+
+    auto generated_alice_public = MUST(Crypto::Curves::SECP256r1::generate_public_key(alice_private_key));
+    EXPECT_EQ(alice_public_key, generated_alice_public);
+
+    auto generated_bob_public = MUST(Crypto::Curves::SECP256r1::generate_public_key(bob_private_key));
+    EXPECT_EQ(bob_public_key, generated_bob_public);
+
+    auto generated_public = MUST(Crypto::Curves::SECP256r1::generate_public_key({ private_key_data, 32 }));
+    ReadonlyBytes expected_public_key { expected_public_key_data, 65 };
+    EXPECT_EQ(expected_public_key, generated_public);
+}