Author: Florian Moser (famoser)
Committer: GitHub (web-flow)
Pusher: Girgias
Date: 2025-05-05T14:10:29+01:00
Commit: https://github.com/php/php-src/commit/90da4821a2ad98fd5f4281e62df6a92d5326e2a5
Raw diff: https://github.com/php/php-src/commit/90da4821a2ad98fd5f4281e62df6a92d5326e2a5.diff
ext/gmp: Add GMP ECC test (#18363)
Co-authored-by: Gina Peter Banyard <[email protected]>
Changed paths:
A ext/gmp/tests/gmp_cryptography_ecc.phpt
A ext/gmp/tests/gmp_cryptography_overload_operators.phpt
M ext/gmp/tests/gmp_cryptography.phpt
Diff:
diff --git a/ext/gmp/tests/gmp_cryptography.phpt b/ext/gmp/tests/gmp_cryptography.phpt
index 771c557e5425a..cb7f17c8ce7da 100644
--- a/ext/gmp/tests/gmp_cryptography.phpt
+++ b/ext/gmp/tests/gmp_cryptography.phpt
@@ -1,36 +1,127 @@
--TEST--
-test some of the simple operations done in ECC cryptography (GH-16870)
+test operations done in finite field and elliptic curve cryptography. (GH-16870)
+--DESCRIPTION--
+Test operations using gmp with number sizes useful in cryptography.
+To gather the to-be-executed operations, the gmp_cryptography_ecc.phpt and
gmp_cryptography_ffc.phpt files have been analysed.
+
+For finite field crypto (FFC), the operations are executed in a 8192bit prime group, with a 512bit
factor.
+This is the biggest prime that was standarized in https://datatracker.ietf.org/doc/html/rfc3526.
+Note that this is insufficient according to the NIST guidelines for the security strength 256bit.
+However, it is doubtful that such big groups (or even bigger ones) are used, as then elliptic
curves are much more efficient.
+
+For elliptic curve crypto (EEC), the operations are executed in a 512bit prime group.
+This corresponds to the biggest curve standardized in https://www.secg.org/sec2-v2.pdf.
+Operations already executed as part of FCC are ommitted: As FFC operates on larger numbers, ECC
operations are implicitly covered.
+
+Further context:
+- See https://www.keylength.com/en/4/ for an overview
of the recommended key lengths by NIST.
+- See https://doi.org/10.6028/NIST.IR.8547.ipd for a
public draft of NIST which proposes to fade-out FFC/ECC crypto by 2035.
+
+Factors were produced using
+$random = gmp_random_bits(512);
+$randomHex = strtoupper(gmp_strval($random, 16));
+echo chunk_split(chunk_split($randomHex, 8, " "), 54);
--EXTENSIONS--
gmp
--FILE--
<?php
-$big_128 = gmp_init("275458973678998164972199298356823445708", 10);
-$big_256 =
gmp_init("105897378200704506708747774951422238999742054168150946506894304230846229930690",
10);
-$big_384 =
gmp_init("6416793922163250205142333121845147158821454739198730072980369042145699078647151545580979451456624745026383368515606",
10);
-$big_521 =
gmp_init("1780138296718969229154737597263093326930734138014367844231086609903991655888322554437298817404082596582997382075361284417827317144352840347188199593652743789",
10);
+// 8192-bit MODP Group of https://datatracker.ietf.org/doc/html/rfc3526
+$generator = gmp_init(2);
+$prime = gmp_init('
+FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
+29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
+EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
+E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
+EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D
+C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F
+83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D
+670C354E 4ABC9804 F1746C08 CA18217C 32905E46 2E36CE3B
+E39E772C 180E8603 9B2783A2 EC07A28F B5C55DF0 6F4C52C9
+DE2BCBF6 95581718 3995497C EA956AE5 15D22618 98FA0510
+15728E5A 8AAAC42D AD33170D 04507A33 A85521AB DF1CBA64
+ECFB8504 58DBEF0A 8AEA7157 5D060C7D B3970F85 A6E1E4C7
+ABF5AE8C DB0933D7 1E8C94E0 4A25619D CEE3D226 1AD2EE6B
+F12FFA06 D98A0864 D8760273 3EC86A64 521F2B18 177B200C
+BBE11757 7A615D6C 770988C0 BAD946E2 08E24FA0 74E5AB31
+43DB5BFC E0FD108E 4B82D120 A9210801 1A723C12 A787E6D7
+88719A10 BDBA5B26 99C32718 6AF4E23C 1A946834 B6150BDA
+2583E9CA 2AD44CE8 DBBBC2DB 04DE8EF9 2E8EFC14 1FBECAA6
+287C5947 4E6BC05D 99B2964F A090C3A2 233BA186 515BE7ED
+1F612970 CEE2D7AF B81BDD76 2170481C D0069127 D5B05AA9
+93B4EA98 8D8FDDC1 86FFB7DC 90A6C08F 4DF435C9 34028492
+36C3FAB4 D27C7026 C1D4DCB2 602646DE C9751E76 3DBA37BD
+F8FF9406 AD9E530E E5DB382F 413001AE B06A53ED 9027D831
+179727B0 865A8918 DA3EDBEB CF9B14ED 44CE6CBA CED4BB1B
+DB7F1447 E6CC254B 33205151 2BD7AF42 6FB8F401 378CD2BF
+5983CA01 C64B92EC F032EA15 D1721D03 F482D7CE 6E74FEF6
+D55E702F 46980C82 B5A84031 900B1C9E 59E7C97F BEC7E8F3
+23A97A7E 36CC88BE 0F1D45B7 FF585AC5 4BD407B2 2B4154AA
+CC8F6D7E BF48E1D8 14CC5ED2 0F8037E0 A79715EE F29BE328
+06A1D58B B7C5DA76 F550AA3D 8A1FBFF0 EB19CCB1 A313D55C
+DA56C9EC 2EF29632 387FE8D7 6E3C0468 043E8F66 3F4860EE
+12BF2D5B 0B7474D6 E694F91E 6DBE1159 74A3926F 12FEE5E4
+38777CB6 A932DF8C D8BEC4D0 73B931BA 3BC832B6 8D9DD300
+741FA7BF 8AFC47ED 2576F693 6BA42466 3AAB639C 5AE4F568
+3423B474 2BF1C978 238F16CB E39D652D E3FDB8BE FC848AD9
+22222E04 A4037C07 13EB57A8 1A23F0C7 3473FC64 6CEA306B
+4BCBC886 2F8385DD FA9D4B7F A2C087E8 79683303 ED5BDD3A
+062B3CF5 B3A278A6 6D2A13F8 3F44F82D DF310EE0 74AB6A36
+4597E899 A0255DC1 64F31CC5 0846851D F9AB4819 5DED7EA1
+B1D510BD 7EE74D73 FAF36BC3 1ECFA268 359046F4 EB879F92
+4009438B 481C6CD7 889A002E D5EE382B C9190DA6 FC026E47
+9558E447 5677E9AA 9E3050E2 765694DF C81F56E8 80B96E71
+60C980DD 98EDD3DF FFFFFFFF FFFFFFFF', 16);
+
+$factor512 = gmp_init('
+3F174D30 1AA08EF0 3556CF48 C6E53D8A 926067DA 50563B72
+42037431 C3144C7C A49937EF 1A6D940A 7228EC8E E2278808
+FD4C0344 D9E03882 A7C65C49 F47E843A', 16);
+
+$factor = gmp_powm($generator, $factor512, $prime);
+var_dump(gmp_strval($factor, 16));
+
+$result = gmp_add($factor, $prime);
+$result = gmp_mod($result, $prime);
+$result = gmp_sub($result, $factor);
+var_dump(gmp_cmp($result, 0) === 0);
+
+$factor = gmp_random_range(0, $prime);
+$factorInverted = gmp_invert($factor, $prime);
+$result = gmp_mul($factor, $factorInverted);
+$result = gmp_mod($result, $prime);
+var_dump(gmp_cmp($result, 1) === 0);
+
+$primeP = gmp_div($prime - 1, 2);
+var_dump(gmp_prob_prime($prime) > 0);
+
+
+// prime and b of secp521r1 from https://www.secg.org/sec2-v2.pdf
+$p = gmp_init('01FF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF
+FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF
+FFFFFFFF FFFFFFFF FFFFFFFF', 16);
+$b = gmp_init('0051 953EB961 8E1C9A1F 929A21A0 B68540EE A2DA725B 99B315F3
+B8B48991 8EF109E1 56193951 EC7E937B 1652C0BD 3BB1BF07 3573DF88
+3D2C34F1 EF451FD4 6B503F00', 16);
-// in ecc crypto key lengths of 256, 384 and 521 (yes, 521, not 512) are typical,
-// and the calculations seem to include squaring and cubing the key,
-// so test those operations
-var_dump((string) gmp_pow($big_128, 2));
-var_dump((string) gmp_pow($big_128, 3));
+$jacobi = gmp_jacobi($b, $p);
+var_dump($jacobi === 1);
-var_dump((string) gmp_pow($big_256, 2));
-var_dump((string) gmp_pow($big_256, 3));
+$result = gmp_and($p, $b);
+var_dump(gmp_cmp($result, $b) === 0);
-var_dump((string) gmp_pow($big_384, 2));
-var_dump((string) gmp_pow($big_384, 3));
+$result = gmp_xor($p, $p);
+var_dump(gmp_cmp($result, 0) === 0);
-var_dump((string) gmp_pow($big_521, 2));
-var_dump((string) gmp_pow($big_521, 3));
+$result = gmp_pow($b, 3);
+var_dump(gmp_strval($result, 16));
?>
--EXPECT--
-string(77)
"75877646180287003845291692588996321992008024509271171205840397374930023621264"
-string(116)
"20901178542000013443295783507452967008255111311111391381095411786512605029527130998551663048238767676593252458334912"
-string(155)
"11214254709783046066761897074581165564696209875788503860615296581570239055173596662994580613114615553617959320367624022951770022252133452732995602203876100"
-string(232)
"1187560172240926986956555551805946700914014146395850601682624192167183140821546786142042010581624015945796617035803644080855311724420346850512769661608026325318823192181186500090109111010574371273491473985103578154963883352347509000"
-string(230)
"41175244239511227932271803271789465275501438128816738161335879819867157609061333189838579416997011220296835767015204168726569753974321567200401024149587401209307771709029048946370759582286096704404540466667318675170269947865547236"
-string(345)
"264213056979683026715444213001489498112251992104549535125497320782388835160296854596249682279610208850530256165562505337646325742090947380083481042994421218556776724906795900034870043631716997303728488772811762108912277655229349137086580494553471889656657230883768271890897138746582039089128053875620299138149315547875444447674573987934196165016"
-string(313)
"3168892355445512933444812965909472020409957119791476182178991646344151155563236535370283312345943041041662641584330401473731788344553589640556705580180081371688996848117690101021660395072221488243400947129794119144961728431002781350889740682623487619845390287149216977767858293453242551076767446272230208078076521"
-string(469)
"5641066640108537808257411937508162073054596465771071759059984994432846497317882144255197676537588304873835452821393566559424565939427398239568910381599042586683472720047480341060077571873252225062218300704671408283921205864218742798766467986541832811143938893251282757214673131758780892167922492222473153470483402146144945253685265421614344082690235633775622262137908096304889066587289890823326962594240368957840634699139830536223598719285051876381571976198029149478069"
+string(2048)
"7208f40638094224980892dbbc1492f40ee0fc3c80e47ee1f49813c31a0e9efc7ed333ade96d418d0109e770f34582da66d1aa48240a599e5fdba7616b3237b378a9d221b97812e21006e0d945ba1b24551370b0bbd8cc09109c1e018940f778a299251d2fcc0128023ed76d581d5822d49e2aad36f5df207126c640343d7e0628a1a607a277609f7913f8b626eff9eac072d4e1aaa8020a94aeafecdd450751c602bf34023217899b1308fe8b7292f0728c655fbe8216e7ec2208d555e7839ace169e352782a4bc8215ebd48609379eddd04ce53752717334c1bf465595bbf86382996776d182383e902da67f0524d29e0e758cb97758a1de50f2578bee7ed994ffcfd0d1df4e34cc3844208162b0f0a10236a554f4c6083c0d564e14efe8eef5e037d79c0c9d15e01c4ac69cbca71c7aeda729ee68b3d5289960b0ae6dc796db6542d2fdf607a2566633676067e70b32de7b7f48d3672c4bd44ade7b228c3044779014aa7d182ea3e6781e4d9a9c31acac7a5fb4109d0a2f47961555b8ef0101f43c7e0d65f7c6df480114e819ecbb2e708ad4c1da08a952935d1bf16d96d5d8753761214d8fcec8c088ca06dc181d227f126987d6b1d1f8be2f4843065e46aae233169d09ec1f96a5a553a15bfa76054bf4bf41ffbe23b7a70e47be5b976932b8c1194d94d789e50ca91b6fb68ef2d5997ebbe3d27c48bdabb44a0876711c291330e949e2bab052c59fbdb74abcb0cfbcc8c9b73002857b8fcf24135ab4aee95dbc1d2e66c1eb584c02f81701b01f08c51f0d9d8b665ea038726485ef6cd3e1fb6ede445ac1204146f280150e0bcff344a6babc7bbd73dcf00466f259b87c24f79e74613a17e265411722a68fc3b84f4afd8741701447f6132215662e7562a65b8cbca9011ad090993b1905fe845ba8595f13523e9ce5062a810338251ef9389504a8916f741bc0af914e61ac21b422fbb54f6dbf2adf5e06f88145e1aab7c7bf7cecbb4e116c038182956b4e5efc62d66f056fbb263a486a5a0974edd9833f08a95ae3c018332bd4b903642000931bb325bd86dbc6b212ee2dd87cdd4e20cba77822f01485624848efce7711802797d231c598aea1482d6685d1b6e4439ffdb54fc9ff1ba0c873a569abe9ff8ee07255654793d1c169bac0ed3f7c9b159348c989d6c10d8e3a5e4c206c6af22355531ee6903ef4db78bdb6ee7874f31932227d8e5f6b97e7158059b1853d90e15c5d733f3345e7ee11f8ac3e8d5dde9fd0397251826541ada4080ee7ff5d23f2486164b9e774896a80923e94ded1b221fe204bc7d0b2a0fbbdcd5b9ecdea449d5743030f5153f7e60b2e55e35fa9a7e0155737a1d39ee04696ea9de477f9e855f01bed483dcedecee7f59058f0a053c7301e11bb7689dd9f562e7fa799e8e62e2de97fcb838a29df790875769f1132c5e3"
+bool(true)
+bool(true)
+bool(true)
+bool(true)
+bool(true)
+bool(true)
+string(389)
"84916bf590f1bad61b6ede6cd6da703bca41cfb661c94b8cf66a1c92f0e2ebb24ad4683b908600ddf7145cac3b4808d6bbed18332d58d93c8ced3e0d3d19fd214a987f86116dd46c9709fd7d8a2b8ade79ba75e41df983b02082e89e3f729de3c6f42613a6b79b5e1967ab712e34cfb79e0d6f6168f7f758c2785da8ac1c36624fbb421a6502b2bbe9ad035c2577864aa12eee3173db7ffb915fce65a918041b95239d66d339de820a7d162cfccdfbd2222c91383ef0c4e903128cbd04dc0bf000000"
diff --git a/ext/gmp/tests/gmp_cryptography_ecc.phpt b/ext/gmp/tests/gmp_cryptography_ecc.phpt
new file mode 100644
index 0000000000000..900005b3334f5
--- /dev/null
+++ b/ext/gmp/tests/gmp_cryptography_ecc.phpt
@@ -0,0 +1,382 @@
+--TEST--
+Examples of the usage of gmp for elliptic curve cryptography.
+--DESCRIPTION--
+DANGER: DO NOT USE IN SECURITY-RELATED USE-CASES.
+This implementation is not hardened or tested against side channels (e.g. time or cache).
+Side-channels as contained in this implementation may compromise secrets (e.g. secret keys).
+Hence, it MUST NOT BE USED IN SECURITY-RELATED USE-CASES.
+
+This implementation operates on the secp256r1 curve from https://www.secg.org/sec2-v2.pdf (also known as NIST
P-256).
+For addition and doublication, it implements https://www.secg.org/sec1-v2.pdf (2.2.1).
+For point decompression, it implements https://www.secg.org/sec1-v2.pdf (2.3.4).
+For scalar multiplication, it uses the well-known double-add-always pardigm.
+
+The implementation executes a diffie-hellman handshake.
+Omitted is an explicit demonstration of (public-key) encryption, commitments, zero-knowledge proofs
or similar common applications.
+However, the operations used for diffie-hellman is at the core of all these other applications,
hence these use-cases are implicitly covered.
+
+$aliceSecret and $bobSecret generated with
+$random = gmp_random_range(0, $n);
+$randomHex = strtoupper(gmp_strval($random, 16));
+echo chunk_split($randomHex, 8, " ");
+--EXTENSIONS--
+gmp
+--FILE--
+<?php
+
+/**
+ * Elliptic curve point with x and y coordinates
+ */
+class Point
+{
+ public function __construct(public \GMP $x, public \GMP $y)
+ {
+ }
+
+ public static function createInfinity(): Point
+ {
+ return new Point(gmp_init(0), gmp_init(0));
+ }
+
+ public function isInfinity(): bool
+ {
+ return gmp_cmp($this->x, 0) === 0 && gmp_cmp($this->y, 0) === 0;
+ }
+
+ public function equals(self $other): bool
+ {
+ return gmp_cmp($this->x, $other->x) === 0 && gmp_cmp($this->y,
$other->y) === 0;
+ }
+}
+
+
+/**
+ * In the finite field F_p,
+ * an elliptic curve in the short Weierstrass form y^2 = x^3 + ax + b is defined,
+ * forming a group over addition.
+ *
+ * A base point G of order n and cofactor h is picked in this group.
+ */
+class Curve
+{
+ public function __construct(
+ private readonly \GMP $p,
+ private readonly \GMP $a,
+ private readonly \GMP $b,
+ private readonly Point $G,
+ private readonly \GMP $n
+ ) {}
+
+ public function getP(): \GMP
+ {
+ return $this->p;
+ }
+
+ public function getA(): \GMP
+ {
+ return $this->a;
+ }
+
+ public function getB(): \GMP
+ {
+ return $this->b;
+ }
+
+ public function getG(): Point
+ {
+ return $this->G;
+ }
+
+ public function getN(): \GMP
+ {
+ return $this->n;
+ }
+}
+
+
+/**
+ * Math inside a prime field; hence always (mod p)
+ */
+class PrimeField
+{
+ private int $elementBitLength;
+
+ public function __construct(private readonly \GMP $prime)
+ {
+ $this->elementBitLength = strlen(gmp_strval($prime, 2));
+ }
+
+ public function getElementBitLength(): int
+ {
+ return $this->elementBitLength;
+ }
+
+ public function add(\GMP $a, \GMP $b): \GMP
+ {
+ $r = gmp_add($a, $b);
+ return gmp_mod($r, $this->prime);
+ }
+
+ public function mul(\GMP $a, \GMP $b): \GMP
+ {
+ $r = gmp_mul($a, $b);
+ return gmp_mod($r, $this->prime);
+ }
+
+ public function sub(\GMP $a, \GMP $b): \GMP
+ {
+ $r = gmp_sub($a, $b);
+ return gmp_mod($r, $this->prime);
+ }
+
+ public function mod(\GMP $a): \GMP
+ {
+ return gmp_mod($a, $this->prime);
+ }
+
+ public function invert(\GMP $z): \GMP|false
+ {
+ return gmp_invert($z, $this->prime);
+ }
+}
+
+class UnsafePrimeCurveMath
+{
+ private PrimeField $field;
+ public function __construct(private readonly Curve $curve)
+ {
+ $this->field = new PrimeField($this->curve->getP());
+ }
+
+ /**
+ * checks whether point fulfills the defining equation of the curve
+ */
+ public function isOnCurve(Point $point): bool
+ {
+ $left = gmp_pow($point->y, 2);
+ $right = gmp_add(
+ gmp_add(
+ gmp_pow($point->x, 3),
+ gmp_mul($this->curve->getA(), $point->x)
+ ),
+ $this->curve->getB()
+ );
+
+ $comparison = $this->field->sub($left, $right);
+
+ return gmp_cmp($comparison, 0) == 0;
+ }
+
+ /**
+ * implements https://www.secg.org/sec1-v2.pdf
2.3.4
+ */
+ public function fromXCoordinate(\GMP $x, bool $isEvenY): Point
+ {
+ $alpha = gmp_add(
+ gmp_add(
+ gmp_powm($x, gmp_init(3, 10), $this->curve->getP()),
+ gmp_mul($this->curve->getA(), $x)
+ ),
+ $this->curve->getB()
+ );
+
+ $jacobiSymbol = gmp_jacobi($alpha, $this->curve->getP());
+ if ($jacobiSymbol !== 1) {
+ throw new Exception('No square root of alpha.');
+ }
+
+ /*
+ * take the square root of alpha, while doing a (much cheaper) exponentiation
+ *
+ * observe that alpha^((p+1)/4) = y^((p+1)/2) = y^((p-1)/2) * y = y
+ * (p+1)/4 is an integer, as for our prime p it holds that p mod 4 = 3
+ * alpha = y^2 by the jacobi symbol check above that asserts y is a quadratic residue
+ * y^((p-1)/2) = 1 by Euler's Criterion applies to the quadratic residue y
+ */
+ $const = gmp_div(gmp_add($this->curve->getP(), 1), 4);
+ $beta = gmp_powm($alpha, $const, $this->curve->getP());
+
+ $yp = $isEvenY ? gmp_init(0) : gmp_init(1);
+ if (gmp_cmp(gmp_mod($beta, 2), $yp) === 0) {
+ return new Point($x, $beta);
+ } else {
+ return new Point($x, gmp_sub($this->curve->getP(), $beta));
+ }
+ }
+
+ /**
+ * rules from https://www.secg.org/SEC1-Ver-1.0.pdf (2.2..1)
+ */
+ private function add(Point $a, Point $b): Point
+ {
+ // rule 1 & 2
+ if ($a->isInfinity()) {
+ return clone $b;
+ } elseif ($b->isInfinity()) {
+ return clone $a;
+ }
+
+ if (gmp_cmp($a->x, $b->x) === 0) {
+ // rule 3
+ if (gmp_cmp($b->y, $a->y) !== 0) {
+ return Point::createInfinity();
+ }
+
+ // rule 5
+ return $this->double($a);
+ }
+
+ // rule 4 (note that a / b = a * b^-1)
+ $lambda = $this->field->mul(
+ gmp_sub($b->y, $a->y),
+ $this->field->invert(gmp_sub($b->x, $a->x))
+ );
+
+ $x = $this->field->sub(
+ gmp_sub(
+ gmp_pow($lambda, 2),
+ $a->x
+ ),
+ $b->x
+ );
+
+ $y = $this->field->sub(
+ gmp_mul(
+ $lambda,
+ gmp_sub($a->x, $x)
+ ),
+ $a->y
+ );
+
+ return new Point($x, $y);
+ }
+
+ private function double(Point $a): Point
+ {
+ if (gmp_cmp($a->y, 0) === 0) {
+ return Point::createInfinity();
+ }
+
+ // rule 5 (note that a / b = a * b^-1)
+ $lambda = $this->field->mul(
+ gmp_add(
+ gmp_mul(
+ gmp_init(3),
+ gmp_pow($a->x, 2)
+ ),
+ $this->curve->getA()
+ ),
+ $this->field->invert(
+ gmp_mul(2, $a->y)
+ )
+ );
+
+ $x = $this->field->sub(
+ gmp_pow($lambda, 2),
+ gmp_mul(2, $a->x)
+ );
+
+ $y = $this->field->sub(
+ gmp_mul(
+ $lambda,
+ gmp_sub($a->x, $x)
+ ),
+ $a->y
+ );
+
+ return new Point($x, $y);
+ }
+
+ private function conditionalSwap(Point $a, Point $b, int $swapBit): void
+ {
+ $this->conditionalSwapScalar($a->x, $b->x, $swapBit,
$this->field->getElementBitLength());
+ $this->conditionalSwapScalar($a->y, $b->y, $swapBit,
$this->field->getElementBitLength());
+ }
+
+ private function conditionalSwapScalar(GMP &$a, GMP &$b, int $swapBit, int
$elementBitLength): void
+ {
+ // create a mask (note how it inverts the maskbit)
+ $mask = gmp_init(str_repeat((string)(1 - $swapBit), $elementBitLength), 2);
+
+ // if mask is 1, tempA = a, else temp = 0
+ $tempA = gmp_and($a, $mask);
+ $tempB = gmp_and($b, $mask);
+
+ $a = gmp_xor($tempB, gmp_xor($a, $b)); // if mask is 1, then b XOR a XOR b = a, else 0 XOR
a XOR b = a XOR b
+ $b = gmp_xor($tempA, gmp_xor($a, $b)); // if mask is 1, then a XOR a XOR b = b, else 0 XOR
a XOR b XOR b = a
+ $a = gmp_xor($tempB, gmp_xor($a, $b)); // if mask is 1, then b XOR a XOR b = a, else 0 XOR
a XOR b XOR a = b
+
+ // hence if mask is 1 (= inverse of $swapBit), then no swap, else swap
+ }
+
+ /**
+ * multiplication using the double-add-always
+ */
+ public function mul(Point $point, \GMP $factor): Point
+ {
+ $mulField = new PrimeField($this->curve->getN());
+
+ // reduce factor once to ensure it is within our curve N bit size (and reduce computational
effort)
+ $reducedFactor = $mulField->mod($factor);
+
+ // normalize to the element bit length to always execute the double-add loop a constant
number of times
+ $factorBits = gmp_strval($reducedFactor, 2);
+ $normalizedFactorBits = str_pad($factorBits, $mulField->getElementBitLength(),
'0', STR_PAD_LEFT);
+
+ /**
+ * how this works:
+ * first, observe r[0] is infinity and r[1] our "real" point.
+ * r[0] and r[1] are swapped iff the corresponding bit in $factor is set to 1,
+ * hence if $j = 1, then the "real" point is added, else the "real"
point is doubled
+ */
+ /** @var Point[] $r */
+ $r = [Point::createInfinity(), clone $point];
+ for ($i = 0; $i < $mulField->getElementBitLength(); $i++) {
+ $j = (int)$normalizedFactorBits[$i];
+
+ $this->conditionalSwap($r[0], $r[1], $j ^ 1);
+
+ $r[0] = $this->add($r[0], $r[1]);
+ $r[1] = $this->double($r[1]);
+
+ $this->conditionalSwap($r[0], $r[1], $j ^ 1);
+ }
+
+ return $r[0];
+ }
+}
+
+// secp256r1 curve from https://www.secg.org/sec2-v2.pdf (also known as NIST
P-256).
+$p = gmp_init('FFFFFFFF 00000001 00000000 00000000 00000000 FFFFFFFF FFFFFFFF FFFFFFFF',
16);
+$a = gmp_init('FFFFFFFF 00000001 00000000 00000000 00000000 FFFFFFFF FFFFFFFF FFFFFFFC',
16);
+$b = gmp_init('5AC635D8 AA3A93E7 B3EBBD55 769886BC 651D06B0 CC53B0F6 3BCE3C3E 27D2604B',
16);
+
+$Gx = gmp_init('6B17D1F2 E12C4247 F8BCE6E5 63A440F2 77037D81 2DEB33A0 F4A13945 D898C296',
16);
+$Gy = gmp_init('4FE342E2 FE1A7F9B 8EE7EB4A 7C0F9E16 2BCE3357 6B315ECE CBB64068 37BF51F5',
16);
+$G = new Point($Gx, $Gy);
+
+$n = gmp_init('FFFFFFFF 00000000 FFFFFFFF FFFFFFFF BCE6FAAD A7179E84 F3B9CAC2 FC632551',
16);
+$curve = new Curve($p, $a, $b, $G, $n);
+$math = new UnsafePrimeCurveMath($curve);
+var_dump($math->isOnCurve($G)); // sanity check
+
+// do diffie hellman key exchange
+$aliceSecret = gmp_init('1421B466 CB12D4F1 298CF525 DE823345 B81B861F 25B5AA7B E86869F9
697C13D', 16);
+$bobSecret = gmp_init('3CFFD9D8 3D5EF967 3432932D D70EC213 8D559C30 7EFBCFF6 0EB96EAB
F08B0CBA', 16);
+
+$alicePublicKey = $math->mul($curve->getG(), $aliceSecret);
+$bobPublicKey = $math->mul($curve->getG(), $bobSecret);
+
+$bobPublicKeyReconstructed = $math->fromXCoordinate($bobPublicKey->x,
gmp_cmp(gmp_mod($bobPublicKey->y, 2), 0) === 0);
+$aliceSharedKey = $math->mul($bobPublicKey, $aliceSecret);
+
+$alicePublicKeyReconstructed = $math->fromXCoordinate($alicePublicKey->x,
gmp_cmp(gmp_mod($alicePublicKey->y, 2), 0) === 0);
+$bobSharedKey = $math->mul($alicePublicKey, $bobSecret);
+
+var_dump($aliceSharedKey->equals($bobSharedKey));
+var_dump(gmp_strval($aliceSharedKey->x, 16));
+?>
+--EXPECT--
+bool(true)
+bool(true)
+string(64) "f480daf4f56a674c16944cda9e7c9fd0ab2813eae3a5935bf9e091cadb5c9ac3"
diff --git a/ext/gmp/tests/gmp_cryptography_overload_operators.phpt
b/ext/gmp/tests/gmp_cryptography_overload_operators.phpt
new file mode 100644
index 0000000000000..7f387e0fbc3c0
--- /dev/null
+++ b/ext/gmp/tests/gmp_cryptography_overload_operators.phpt
@@ -0,0 +1,112 @@
+--TEST--
+test operations done in finite field and elliptic curve cryptography, using operator overloads.
(GH-16870)
+--DESCRIPTION--
+Test overload operators of gmp with number sizes useful in cryptography.
+It has the same content as gmp_cryptography.phpt, to which we refer for motivation of
the operations.
+
+The only difference in this file is that whenever possible operator overloads are used.
+The reason is that while fixing GH-16870, it was noticed that the overload operators and the
functions evolved independently.
+--EXTENSIONS--
+gmp
+--FILE--
+<?php
+// 8192-bit MODP Group of https://datatracker.ietf.org/doc/html/rfc3526
+$generator = gmp_init(2);
+$prime = gmp_init('
+FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
+29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
+EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
+E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
+EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D
+C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F
+83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D
+670C354E 4ABC9804 F1746C08 CA18217C 32905E46 2E36CE3B
+E39E772C 180E8603 9B2783A2 EC07A28F B5C55DF0 6F4C52C9
+DE2BCBF6 95581718 3995497C EA956AE5 15D22618 98FA0510
+15728E5A 8AAAC42D AD33170D 04507A33 A85521AB DF1CBA64
+ECFB8504 58DBEF0A 8AEA7157 5D060C7D B3970F85 A6E1E4C7
+ABF5AE8C DB0933D7 1E8C94E0 4A25619D CEE3D226 1AD2EE6B
+F12FFA06 D98A0864 D8760273 3EC86A64 521F2B18 177B200C
+BBE11757 7A615D6C 770988C0 BAD946E2 08E24FA0 74E5AB31
+43DB5BFC E0FD108E 4B82D120 A9210801 1A723C12 A787E6D7
+88719A10 BDBA5B26 99C32718 6AF4E23C 1A946834 B6150BDA
+2583E9CA 2AD44CE8 DBBBC2DB 04DE8EF9 2E8EFC14 1FBECAA6
+287C5947 4E6BC05D 99B2964F A090C3A2 233BA186 515BE7ED
+1F612970 CEE2D7AF B81BDD76 2170481C D0069127 D5B05AA9
+93B4EA98 8D8FDDC1 86FFB7DC 90A6C08F 4DF435C9 34028492
+36C3FAB4 D27C7026 C1D4DCB2 602646DE C9751E76 3DBA37BD
+F8FF9406 AD9E530E E5DB382F 413001AE B06A53ED 9027D831
+179727B0 865A8918 DA3EDBEB CF9B14ED 44CE6CBA CED4BB1B
+DB7F1447 E6CC254B 33205151 2BD7AF42 6FB8F401 378CD2BF
+5983CA01 C64B92EC F032EA15 D1721D03 F482D7CE 6E74FEF6
+D55E702F 46980C82 B5A84031 900B1C9E 59E7C97F BEC7E8F3
+23A97A7E 36CC88BE 0F1D45B7 FF585AC5 4BD407B2 2B4154AA
+CC8F6D7E BF48E1D8 14CC5ED2 0F8037E0 A79715EE F29BE328
+06A1D58B B7C5DA76 F550AA3D 8A1FBFF0 EB19CCB1 A313D55C
+DA56C9EC 2EF29632 387FE8D7 6E3C0468 043E8F66 3F4860EE
+12BF2D5B 0B7474D6 E694F91E 6DBE1159 74A3926F 12FEE5E4
+38777CB6 A932DF8C D8BEC4D0 73B931BA 3BC832B6 8D9DD300
+741FA7BF 8AFC47ED 2576F693 6BA42466 3AAB639C 5AE4F568
+3423B474 2BF1C978 238F16CB E39D652D E3FDB8BE FC848AD9
+22222E04 A4037C07 13EB57A8 1A23F0C7 3473FC64 6CEA306B
+4BCBC886 2F8385DD FA9D4B7F A2C087E8 79683303 ED5BDD3A
+062B3CF5 B3A278A6 6D2A13F8 3F44F82D DF310EE0 74AB6A36
+4597E899 A0255DC1 64F31CC5 0846851D F9AB4819 5DED7EA1
+B1D510BD 7EE74D73 FAF36BC3 1ECFA268 359046F4 EB879F92
+4009438B 481C6CD7 889A002E D5EE382B C9190DA6 FC026E47
+9558E447 5677E9AA 9E3050E2 765694DF C81F56E8 80B96E71
+60C980DD 98EDD3DF FFFFFFFF FFFFFFFF', 16);
+
+$factor512 = gmp_init('
+3F174D30 1AA08EF0 3556CF48 C6E53D8A 926067DA 50563B72
+42037431 C3144C7C A49937EF 1A6D940A 7228EC8E E2278808
+FD4C0344 D9E03882 A7C65C49 F47E843A', 16);
+
+$factor = gmp_powm($generator, $factor512, $prime);
+var_dump(gmp_strval($factor, 16));
+
+$result = $factor + $prime;
+$result = $result % $prime;
+$result = $result - $factor;
+var_dump(gmp_cmp($result, 0) === 0);
+
+$factor = gmp_random_range(0, $prime);
+$factorInverted = gmp_invert($factor, $prime);
+$result = $factor * $factorInverted;
+$result = $result % $prime;
+var_dump(gmp_cmp($result, 1) === 0);
+
+$primeP = ($prime - 1) / 2;
+var_dump(gmp_prob_prime($prime) > 0);
+
+
+// prime and b of secp521r1 from https://www.secg.org/sec2-v2.pdf
+$p = gmp_init('01FF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF
+FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF
+FFFFFFFF FFFFFFFF FFFFFFFF', 16);
+$b = gmp_init('0051 953EB961 8E1C9A1F 929A21A0 B68540EE A2DA725B 99B315F3
+B8B48991 8EF109E1 56193951 EC7E937B 1652C0BD 3BB1BF07 3573DF88
+3D2C34F1 EF451FD4 6B503F00', 16);
+
+$jacobi = gmp_jacobi($b, $p);
+var_dump($jacobi === 1);
+
+$result = $p & $b;
+var_dump(gmp_cmp($result, $b) === 0);
+
+$result = $p ^ $p;
+var_dump(gmp_cmp($result, 0) === 0);
+
+$result = $b ** 3;
+var_dump(gmp_strval($result, 16));
+
+?>
+--EXPECT--
+string(2048)
"7208f40638094224980892dbbc1492f40ee0fc3c80e47ee1f49813c31a0e9efc7ed333ade96d418d0109e770f34582da66d1aa48240a599e5fdba7616b3237b378a9d221b97812e21006e0d945ba1b24551370b0bbd8cc09109c1e018940f778a299251d2fcc0128023ed76d581d5822d49e2aad36f5df207126c640343d7e0628a1a607a277609f7913f8b626eff9eac072d4e1aaa8020a94aeafecdd450751c602bf34023217899b1308fe8b7292f0728c655fbe8216e7ec2208d555e7839ace169e352782a4bc8215ebd48609379eddd04ce53752717334c1bf465595bbf86382996776d182383e902da67f0524d29e0e758cb97758a1de50f2578bee7ed994ffcfd0d1df4e34cc3844208162b0f0a10236a554f4c6083c0d564e14efe8eef5e037d79c0c9d15e01c4ac69cbca71c7aeda729ee68b3d5289960b0ae6dc796db6542d2fdf607a2566633676067e70b32de7b7f48d3672c4bd44ade7b228c3044779014aa7d182ea3e6781e4d9a9c31acac7a5fb4109d0a2f47961555b8ef0101f43c7e0d65f7c6df480114e819ecbb2e708ad4c1da08a952935d1bf16d96d5d8753761214d8fcec8c088ca06dc181d227f126987d6b1d1f8be2f4843065e46aae233169d09ec1f96a5a553a15bfa76054bf4bf41ffbe23b7a70e47be5b976932b8c1194d94d789e50ca91b6fb68ef2d5997ebbe3d27c48bdabb44a0876711c291330e949e2bab052c59fbdb74abcb0cfbcc8c9b73002857b8fcf24135ab4aee95dbc1d2e66c1eb584c02f81701b01f08c51f0d9d8b665ea038726485ef6cd3e1fb6ede445ac1204146f280150e0bcff344a6babc7bbd73dcf00466f259b87c24f79e74613a17e265411722a68fc3b84f4afd8741701447f6132215662e7562a65b8cbca9011ad090993b1905fe845ba8595f13523e9ce5062a810338251ef9389504a8916f741bc0af914e61ac21b422fbb54f6dbf2adf5e06f88145e1aab7c7bf7cecbb4e116c038182956b4e5efc62d66f056fbb263a486a5a0974edd9833f08a95ae3c018332bd4b903642000931bb325bd86dbc6b212ee2dd87cdd4e20cba77822f01485624848efce7711802797d231c598aea1482d6685d1b6e4439ffdb54fc9ff1ba0c873a569abe9ff8ee07255654793d1c169bac0ed3f7c9b159348c989d6c10d8e3a5e4c206c6af22355531ee6903ef4db78bdb6ee7874f31932227d8e5f6b97e7158059b1853d90e15c5d733f3345e7ee11f8ac3e8d5dde9fd0397251826541ada4080ee7ff5d23f2486164b9e774896a80923e94ded1b221fe204bc7d0b2a0fbbdcd5b9ecdea449d5743030f5153f7e60b2e55e35fa9a7e0155737a1d39ee04696ea9de477f9e855f01bed483dcedecee7f59058f0a053c7301e11bb7689dd9f562e7fa799e8e62e2de97fcb838a29df790875769f1132c5e3"
+bool(true)
+bool(true)
+bool(true)
+bool(true)
+bool(true)
+bool(true)
+string(389)
"84916bf590f1bad61b6ede6cd6da703bca41cfb661c94b8cf66a1c92f0e2ebb24ad4683b908600ddf7145cac3b4808d6bbed18332d58d93c8ced3e0d3d19fd214a987f86116dd46c9709fd7d8a2b8ade79ba75e41df983b02082e89e3f729de3c6f42613a6b79b5e1967ab712e34cfb79e0d6f6168f7f758c2785da8ac1c36624fbb421a6502b2bbe9ad035c2577864aa12eee3173db7ffb915fce65a918041b95239d66d339de820a7d162cfccdfbd2222c91383ef0c4e903128cbd04dc0bf000000"