summaryrefslogtreecommitdiffstats
path: root/vendor/web-token/jwt-key-mgmt/KeyConverter
diff options
context:
space:
mode:
authorAnton Luka Šijanec <anton@sijanec.eu>2022-01-11 12:35:47 +0100
committerAnton Luka Šijanec <anton@sijanec.eu>2022-01-11 12:35:47 +0100
commit19985dbb8c0aa66dc4bf7905abc1148de909097d (patch)
tree2cd5a5d20d7e80fc2a51adf60d838d8a2c40999e /vendor/web-token/jwt-key-mgmt/KeyConverter
download1ka-19985dbb8c0aa66dc4bf7905abc1148de909097d.tar
1ka-19985dbb8c0aa66dc4bf7905abc1148de909097d.tar.gz
1ka-19985dbb8c0aa66dc4bf7905abc1148de909097d.tar.bz2
1ka-19985dbb8c0aa66dc4bf7905abc1148de909097d.tar.lz
1ka-19985dbb8c0aa66dc4bf7905abc1148de909097d.tar.xz
1ka-19985dbb8c0aa66dc4bf7905abc1148de909097d.tar.zst
1ka-19985dbb8c0aa66dc4bf7905abc1148de909097d.zip
Diffstat (limited to 'vendor/web-token/jwt-key-mgmt/KeyConverter')
-rw-r--r--vendor/web-token/jwt-key-mgmt/KeyConverter/ECKey.php273
-rw-r--r--vendor/web-token/jwt-key-mgmt/KeyConverter/KeyConverter.php256
-rw-r--r--vendor/web-token/jwt-key-mgmt/KeyConverter/RSAKey.php244
3 files changed, 773 insertions, 0 deletions
diff --git a/vendor/web-token/jwt-key-mgmt/KeyConverter/ECKey.php b/vendor/web-token/jwt-key-mgmt/KeyConverter/ECKey.php
new file mode 100644
index 0000000..4ab0090
--- /dev/null
+++ b/vendor/web-token/jwt-key-mgmt/KeyConverter/ECKey.php
@@ -0,0 +1,273 @@
+<?php
+
+declare(strict_types=1);
+
+/*
+ * The MIT License (MIT)
+ *
+ * Copyright (c) 2014-2018 Spomky-Labs
+ *
+ * This software may be modified and distributed under the terms
+ * of the MIT license. See the LICENSE file for details.
+ */
+
+namespace Jose\Component\KeyManagement\KeyConverter;
+
+use Base64Url\Base64Url;
+use FG\ASN1\ASNObject;
+use FG\ASN1\ExplicitlyTaggedObject;
+use FG\ASN1\Universal\BitString;
+use FG\ASN1\Universal\Integer;
+use FG\ASN1\Universal\ObjectIdentifier;
+use FG\ASN1\Universal\OctetString;
+use FG\ASN1\Universal\Sequence;
+
+/**
+ * @internal
+ */
+class ECKey
+{
+ /**
+ * @var array
+ */
+ private $values = [];
+
+ /**
+ * ECKey constructor.
+ */
+ private function __construct(array $data)
+ {
+ $this->loadJWK($data);
+ }
+
+ /**
+ * @return ECKey
+ */
+ public static function createFromPEM(string $pem): self
+ {
+ $data = self::loadPEM($pem);
+
+ return new self($data);
+ }
+
+ /**
+ * @throws \Exception
+ */
+ private static function loadPEM(string $data): array
+ {
+ $data = \base64_decode(\preg_replace('#-.*-|\r|\n#', '', $data), true);
+ $asnObject = ASNObject::fromBinary($data);
+
+ if (!$asnObject instanceof Sequence) {
+ throw new \InvalidArgumentException('Unable to load the key.');
+ }
+ $children = $asnObject->getChildren();
+ if (self::isPKCS8($children)) {
+ $children = self::loadPKCS8($children);
+ }
+
+ if (4 === \count($children)) {
+ return self::loadPrivatePEM($children);
+ }
+ if (2 === \count($children)) {
+ return self::loadPublicPEM($children);
+ }
+
+ throw new \Exception('Unable to load the key.');
+ }
+
+ /**
+ * @param ASNObject[] $children
+ */
+ private static function loadPKCS8(array $children): array
+ {
+ $binary = \hex2bin($children[2]->getContent());
+ $asnObject = ASNObject::fromBinary($binary);
+ if (!$asnObject instanceof Sequence) {
+ throw new \InvalidArgumentException('Unable to load the key.');
+ }
+
+ return $asnObject->getChildren();
+ }
+
+ /**
+ * @param ASNObject[] $children
+ */
+ private static function loadPublicPEM(array $children): array
+ {
+ if (!$children[0] instanceof Sequence) {
+ throw new \InvalidArgumentException('Unsupported key type.');
+ }
+
+ $sub = $children[0]->getChildren();
+ if (!$sub[0] instanceof ObjectIdentifier) {
+ throw new \InvalidArgumentException('Unsupported key type.');
+ }
+ if ('1.2.840.10045.2.1' !== $sub[0]->getContent()) {
+ throw new \InvalidArgumentException('Unsupported key type.');
+ }
+ if (!$sub[1] instanceof ObjectIdentifier) {
+ throw new \InvalidArgumentException('Unsupported key type.');
+ }
+ if (!$children[1] instanceof BitString) {
+ throw new \InvalidArgumentException('Unable to load the key.');
+ }
+
+ $bits = $children[1]->getContent();
+ $bits_length = \mb_strlen($bits, '8bit');
+ if ('04' !== \mb_substr($bits, 0, 2, '8bit')) {
+ throw new \InvalidArgumentException('Unsupported key type');
+ }
+
+ $values = ['kty' => 'EC'];
+ $values['crv'] = self::getCurve($sub[1]->getContent());
+ $values['x'] = Base64Url::encode(\hex2bin(\mb_substr($bits, 2, ($bits_length - 2) / 2, '8bit')));
+ $values['y'] = Base64Url::encode(\hex2bin(\mb_substr($bits, ($bits_length - 2) / 2 + 2, ($bits_length - 2) / 2, '8bit')));
+
+ return $values;
+ }
+
+ private static function getCurve(string $oid): string
+ {
+ $curves = self::getSupportedCurves();
+ $curve = \array_search($oid, $curves, true);
+ if (!\is_string($curve)) {
+ throw new \InvalidArgumentException('Unsupported OID.');
+ }
+
+ return $curve;
+ }
+
+ private static function getSupportedCurves(): array
+ {
+ return [
+ 'P-256' => '1.2.840.10045.3.1.7',
+ 'P-384' => '1.3.132.0.34',
+ 'P-521' => '1.3.132.0.35',
+ ];
+ }
+
+ private static function verifyVersion(ASNObject $children)
+ {
+ if (!$children instanceof Integer || '1' !== $children->getContent()) {
+ throw new \InvalidArgumentException('Unable to load the key.');
+ }
+ }
+
+ private static function getXAndY(ASNObject $children, ?string &$x, ?string &$y)
+ {
+ if (!$children instanceof ExplicitlyTaggedObject || !\is_array($children->getContent())) {
+ throw new \InvalidArgumentException('Unable to load the key.');
+ }
+ if (!$children->getContent()[0] instanceof BitString) {
+ throw new \InvalidArgumentException('Unable to load the key.');
+ }
+
+ $bits = $children->getContent()[0]->getContent();
+ $bits_length = \mb_strlen($bits, '8bit');
+
+ if ('04' !== \mb_substr($bits, 0, 2, '8bit')) {
+ throw new \InvalidArgumentException('Unsupported key type');
+ }
+
+ $x = \mb_substr($bits, 2, ($bits_length - 2) / 2, '8bit');
+ $y = \mb_substr($bits, ($bits_length - 2) / 2 + 2, ($bits_length - 2) / 2, '8bit');
+ }
+
+ private static function getD(ASNObject $children): string
+ {
+ if (!$children instanceof OctetString) {
+ throw new \InvalidArgumentException('Unable to load the key.');
+ }
+
+ return $children->getContent();
+ }
+
+ private static function loadPrivatePEM(array $children): array
+ {
+ self::verifyVersion($children[0]);
+ $x = null;
+ $y = null;
+ $d = self::getD($children[1]);
+ self::getXAndY($children[3], $x, $y);
+
+ if (!$children[2] instanceof ExplicitlyTaggedObject || !\is_array($children[2]->getContent())) {
+ throw new \InvalidArgumentException('Unable to load the key.');
+ }
+ if (!$children[2]->getContent()[0] instanceof ObjectIdentifier) {
+ throw new \InvalidArgumentException('Unable to load the key.');
+ }
+
+ $curve = $children[2]->getContent()[0]->getContent();
+
+ $values = ['kty' => 'EC'];
+ $values['crv'] = self::getCurve($curve);
+ $values['d'] = Base64Url::encode(\hex2bin($d));
+ $values['x'] = Base64Url::encode(\hex2bin($x));
+ $values['y'] = Base64Url::encode(\hex2bin($y));
+
+ return $values;
+ }
+
+ /**
+ * @param ASNObject[] $children
+ */
+ private static function isPKCS8(array $children): bool
+ {
+ if (3 !== \count($children)) {
+ return false;
+ }
+
+ $classes = [0 => Integer::class, 1 => Sequence::class, 2 => OctetString::class];
+ foreach ($classes as $k => $class) {
+ if (!$children[$k] instanceof $class) {
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+ /**
+ * @param ECKey $private
+ *
+ * @return ECKey
+ */
+ public static function toPublic(self $private): self
+ {
+ $data = $private->toArray();
+ if (\array_key_exists('d', $data)) {
+ unset($data['d']);
+ }
+
+ return new self($data);
+ }
+
+ /**
+ * @return array
+ */
+ public function toArray()
+ {
+ return $this->values;
+ }
+
+ private function loadJWK(array $jwk)
+ {
+ $keys = [
+ 'kty' => 'The key parameter "kty" is missing.',
+ 'crv' => 'Curve parameter is missing',
+ 'x' => 'Point parameters are missing.',
+ 'y' => 'Point parameters are missing.',
+ ];
+ foreach ($keys as $k => $v) {
+ if (!\array_key_exists($k, $jwk)) {
+ throw new \InvalidArgumentException($v);
+ }
+ }
+
+ if ('EC' !== $jwk['kty']) {
+ throw new \InvalidArgumentException('JWK is not an Elliptic Curve key.');
+ }
+ $this->values = $jwk;
+ }
+}
diff --git a/vendor/web-token/jwt-key-mgmt/KeyConverter/KeyConverter.php b/vendor/web-token/jwt-key-mgmt/KeyConverter/KeyConverter.php
new file mode 100644
index 0000000..17a5428
--- /dev/null
+++ b/vendor/web-token/jwt-key-mgmt/KeyConverter/KeyConverter.php
@@ -0,0 +1,256 @@
+<?php
+
+declare(strict_types=1);
+
+/*
+ * The MIT License (MIT)
+ *
+ * Copyright (c) 2014-2018 Spomky-Labs
+ *
+ * This software may be modified and distributed under the terms
+ * of the MIT license. See the LICENSE file for details.
+ */
+
+namespace Jose\Component\KeyManagement\KeyConverter;
+
+use Base64Url\Base64Url;
+
+/**
+ * @internal
+ */
+class KeyConverter
+{
+ /**
+ * @throws \InvalidArgumentException
+ */
+ public static function loadKeyFromCertificateFile(string $file): array
+ {
+ if (!\file_exists($file)) {
+ throw new \InvalidArgumentException(\sprintf('File "%s" does not exist.', $file));
+ }
+ $content = \file_get_contents($file);
+
+ return self::loadKeyFromCertificate($content);
+ }
+
+ /**
+ * @throws \InvalidArgumentException
+ */
+ public static function loadKeyFromCertificate(string $certificate): array
+ {
+ try {
+ $res = \openssl_x509_read($certificate);
+ } catch (\Exception $e) {
+ $certificate = self::convertDerToPem($certificate);
+ $res = \openssl_x509_read($certificate);
+ }
+ if (false === $res) {
+ throw new \InvalidArgumentException('Unable to load the certificate.');
+ }
+
+ $values = self::loadKeyFromX509Resource($res);
+ \openssl_x509_free($res);
+
+ return $values;
+ }
+
+ /**
+ * @param resource $res
+ *
+ * @throws \Exception
+ */
+ public static function loadKeyFromX509Resource($res): array
+ {
+ $key = \openssl_get_publickey($res);
+
+ $details = \openssl_pkey_get_details($key);
+ if (isset($details['key'])) {
+ $values = self::loadKeyFromPEM($details['key']);
+ \openssl_x509_export($res, $out);
+ $x5c = \preg_replace('#-.*-#', '', $out);
+ $x5c = \preg_replace('~\R~', PHP_EOL, $x5c);
+ $x5c = \trim($x5c);
+ $values['x5c'] = [$x5c];
+
+ $values['x5t'] = Base64Url::encode(\openssl_x509_fingerprint($res, 'sha1', true));
+ $values['x5t#256'] = Base64Url::encode(\openssl_x509_fingerprint($res, 'sha256', true));
+
+ return $values;
+ }
+
+ throw new \InvalidArgumentException('Unable to load the certificate');
+ }
+
+ /**
+ * @throws \Exception
+ */
+ public static function loadFromKeyFile(string $file, ?string $password = null): array
+ {
+ $content = \file_get_contents($file);
+
+ return self::loadFromKey($content, $password);
+ }
+
+ /**
+ * @throws \Exception
+ */
+ public static function loadFromKey(string $key, ?string $password = null): array
+ {
+ try {
+ return self::loadKeyFromDER($key, $password);
+ } catch (\Exception $e) {
+ return self::loadKeyFromPEM($key, $password);
+ }
+ }
+
+ /**
+ * @throws \Exception
+ */
+ private static function loadKeyFromDER(string $der, ?string $password = null): array
+ {
+ $pem = self::convertDerToPem($der);
+
+ return self::loadKeyFromPEM($pem, $password);
+ }
+
+ /**
+ * @throws \Exception
+ */
+ private static function loadKeyFromPEM(string $pem, ?string $password = null): array
+ {
+ if (\preg_match('#DEK-Info: (.+),(.+)#', $pem, $matches)) {
+ $pem = self::decodePem($pem, $matches, $password);
+ }
+
+ self::sanitizePEM($pem);
+
+ $res = \openssl_pkey_get_private($pem);
+ if (false === $res) {
+ $res = \openssl_pkey_get_public($pem);
+ }
+ if (false === $res) {
+ throw new \InvalidArgumentException('Unable to load the key.');
+ }
+
+ $details = \openssl_pkey_get_details($res);
+ if (!\is_array($details) || !\array_key_exists('type', $details)) {
+ throw new \InvalidArgumentException('Unable to get details of the key');
+ }
+
+ switch ($details['type']) {
+ case OPENSSL_KEYTYPE_EC:
+ $ec_key = ECKey::createFromPEM($pem);
+
+ return $ec_key->toArray();
+ case OPENSSL_KEYTYPE_RSA:
+ $rsa_key = RSAKey::createFromPEM($pem);
+ $rsa_key->optimize();
+
+ return $rsa_key->toArray();
+ default:
+ throw new \InvalidArgumentException('Unsupported key type');
+ }
+ }
+
+ /**
+ * This method modifies the PEM to get 64 char lines and fix bug with old OpenSSL versions.
+ */
+ private static function sanitizePEM(string &$pem)
+ {
+ \preg_match_all('#(-.*-)#', $pem, $matches, PREG_PATTERN_ORDER);
+ $ciphertext = \preg_replace('#-.*-|\r|\n| #', '', $pem);
+
+ $pem = $matches[0][0].PHP_EOL;
+ $pem .= \chunk_split($ciphertext, 64, PHP_EOL);
+ $pem .= $matches[0][1].PHP_EOL;
+ }
+
+ /**
+ * Be careful! The certificate chain is loaded, but it is NOT VERIFIED by any mean!
+ * It is mandatory to verify the root CA or intermediate CA are trusted.
+ * If not done, it may lead to potential security issues.
+ */
+ public static function loadFromX5C(array $x5c): array
+ {
+ $certificate = null;
+ $last_issuer = null;
+ $last_subject = null;
+ foreach ($x5c as $cert) {
+ $current_cert = '-----BEGIN CERTIFICATE-----'.PHP_EOL.\chunk_split($cert,64,PHP_EOL).'-----END CERTIFICATE-----';
+ $x509 = \openssl_x509_read($current_cert);
+ if (false === $x509) {
+ $last_issuer = null;
+ $last_subject = null;
+
+ break;
+ }
+ $parsed = \openssl_x509_parse($x509);
+
+ \openssl_x509_free($x509);
+ if (false === $parsed) {
+ $last_issuer = null;
+ $last_subject = null;
+
+ break;
+ }
+ if (null === $last_subject) {
+ $last_subject = $parsed['subject'];
+ $last_issuer = $parsed['issuer'];
+ $certificate = $current_cert;
+ } else {
+ if (\json_encode($last_issuer) === \json_encode($parsed['subject'])) {
+ $last_subject = $parsed['subject'];
+ $last_issuer = $parsed['issuer'];
+ } else {
+ $last_issuer = null;
+ $last_subject = null;
+
+ break;
+ }
+ }
+ }
+
+ return self::loadKeyFromCertificate($certificate);
+ }
+
+ /**
+ * @param string[] $matches
+ */
+ private static function decodePem(string $pem, array $matches, ?string $password = null): string
+ {
+ if (null === $password) {
+ throw new \InvalidArgumentException('Password required for encrypted keys.');
+ }
+
+ $iv = \pack('H*', \trim($matches[2]));
+ $iv_sub = \mb_substr($iv, 0, 8, '8bit');
+ $symkey = \pack('H*', \md5($password.$iv_sub));
+ $symkey .= \pack('H*', \md5($symkey.$password.$iv_sub));
+ $key = \preg_replace('#^(?:Proc-Type|DEK-Info): .*#m', '', $pem);
+ $ciphertext = \base64_decode(\preg_replace('#-.*-|\r|\n#', '', $key), true);
+
+ $decoded = \openssl_decrypt($ciphertext, \mb_strtolower($matches[1]), $symkey, OPENSSL_RAW_DATA, $iv);
+ if (!\is_string($decoded)) {
+ throw new \InvalidArgumentException('Incorrect password. Key decryption failed.');
+ }
+
+ $number = \preg_match_all('#-{5}.*-{5}#', $pem, $result);
+ if (2 !== $number) {
+ throw new \InvalidArgumentException('Unable to load the key');
+ }
+
+ $pem = $result[0][0].PHP_EOL;
+ $pem .= \chunk_split(\base64_encode($decoded), 64);
+ $pem .= $result[0][1].PHP_EOL;
+
+ return $pem;
+ }
+
+ private static function convertDerToPem(string $der_data): string
+ {
+ $pem = \chunk_split(\base64_encode($der_data), 64, PHP_EOL);
+ $pem = '-----BEGIN CERTIFICATE-----'.PHP_EOL.$pem.'-----END CERTIFICATE-----'.PHP_EOL;
+
+ return $pem;
+ }
+}
diff --git a/vendor/web-token/jwt-key-mgmt/KeyConverter/RSAKey.php b/vendor/web-token/jwt-key-mgmt/KeyConverter/RSAKey.php
new file mode 100644
index 0000000..f76b5d4
--- /dev/null
+++ b/vendor/web-token/jwt-key-mgmt/KeyConverter/RSAKey.php
@@ -0,0 +1,244 @@
+<?php
+
+declare(strict_types=1);
+
+/*
+ * The MIT License (MIT)
+ *
+ * Copyright (c) 2014-2018 Spomky-Labs
+ *
+ * This software may be modified and distributed under the terms
+ * of the MIT license. See the LICENSE file for details.
+ */
+
+namespace Jose\Component\KeyManagement\KeyConverter;
+
+use Base64Url\Base64Url;
+use Jose\Component\Core\JWK;
+use Jose\Component\Core\Util\BigInteger;
+
+/**
+ * @internal
+ */
+class RSAKey
+{
+ /**
+ * @var array
+ */
+ private $values = [];
+
+ /**
+ * RSAKey constructor.
+ */
+ private function __construct(array $data)
+ {
+ $this->loadJWK($data);
+ }
+
+ /**
+ * @return RSAKey
+ */
+ public static function createFromKeyDetails(array $details): self
+ {
+ $values = ['kty' => 'RSA'];
+ $keys = [
+ 'n' => 'n',
+ 'e' => 'e',
+ 'd' => 'd',
+ 'p' => 'p',
+ 'q' => 'q',
+ 'dp' => 'dmp1',
+ 'dq' => 'dmq1',
+ 'qi' => 'iqmp',
+ ];
+ foreach ($details as $key => $value) {
+ if (\in_array($key, $keys, true)) {
+ $value = Base64Url::encode($value);
+ $values[\array_search($key, $keys, true)] = $value;
+ }
+ }
+
+ return new self($values);
+ }
+
+ /**
+ * @return RSAKey
+ */
+ public static function createFromPEM(string $pem): self
+ {
+ $res = \openssl_pkey_get_private($pem);
+ if (false === $res) {
+ $res = \openssl_pkey_get_public($pem);
+ }
+ if (false === $res) {
+ throw new \InvalidArgumentException('Unable to load the key.');
+ }
+
+ $details = \openssl_pkey_get_details($res);
+ \openssl_free_key($res);
+ if (!\array_key_exists('rsa', $details)) {
+ throw new \InvalidArgumentException('Unable to load the key.');
+ }
+
+ return self::createFromKeyDetails($details['rsa']);
+ }
+
+ /**
+ * @return RSAKey
+ */
+ public static function createFromJWK(JWK $jwk): self
+ {
+ return new self($jwk->all());
+ }
+
+ public function isPublic(): bool
+ {
+ return !\array_key_exists('d', $this->values);
+ }
+
+ /**
+ * @param RSAKey $private
+ *
+ * @return RSAKey
+ */
+ public static function toPublic(self $private): self
+ {
+ $data = $private->toArray();
+ $keys = ['p', 'd', 'q', 'dp', 'dq', 'qi'];
+ foreach ($keys as $key) {
+ if (\array_key_exists($key, $data)) {
+ unset($data[$key]);
+ }
+ }
+
+ return new self($data);
+ }
+
+ public function toArray(): array
+ {
+ return $this->values;
+ }
+
+ private function loadJWK(array $jwk)
+ {
+ if (!\array_key_exists('kty', $jwk)) {
+ throw new \InvalidArgumentException('The key parameter "kty" is missing.');
+ }
+ if ('RSA' !== $jwk['kty']) {
+ throw new \InvalidArgumentException('The JWK is not a RSA key.');
+ }
+
+ $this->values = $jwk;
+ }
+
+ public function toJwk(): JWK
+ {
+ return new JWK($this->values);
+ }
+
+ /**
+ * This method will try to add Chinese Remainder Theorem (CRT) parameters.
+ * With those primes, the decryption process is really fast.
+ */
+ public function optimize()
+ {
+ if (\array_key_exists('d', $this->values)) {
+ $this->populateCRT();
+ }
+ }
+
+ /**
+ * This method adds Chinese Remainder Theorem (CRT) parameters if primes 'p' and 'q' are available.
+ */
+ private function populateCRT()
+ {
+ if (!\array_key_exists('p', $this->values) && !\array_key_exists('q', $this->values)) {
+ $d = BigInteger::createFromBinaryString(Base64Url::decode($this->values['d']));
+ $e = BigInteger::createFromBinaryString(Base64Url::decode($this->values['e']));
+ $n = BigInteger::createFromBinaryString(Base64Url::decode($this->values['n']));
+
+ list($p, $q) = $this->findPrimeFactors($d, $e, $n);
+ $this->values['p'] = Base64Url::encode($p->toBytes());
+ $this->values['q'] = Base64Url::encode($q->toBytes());
+ }
+
+ if (\array_key_exists('dp', $this->values) && \array_key_exists('dq', $this->values) && \array_key_exists('qi', $this->values)) {
+ return;
+ }
+
+ $one = BigInteger::createFromDecimal(1);
+ $d = BigInteger::createFromBinaryString(Base64Url::decode($this->values['d']));
+ $p = BigInteger::createFromBinaryString(Base64Url::decode($this->values['p']));
+ $q = BigInteger::createFromBinaryString(Base64Url::decode($this->values['q']));
+
+ $this->values['dp'] = Base64Url::encode($d->mod($p->subtract($one))->toBytes());
+ $this->values['dq'] = Base64Url::encode($d->mod($q->subtract($one))->toBytes());
+ $this->values['qi'] = Base64Url::encode($q->modInverse($p)->toBytes());
+ }
+
+ /**
+ * @return BigInteger[]
+ */
+ private function findPrimeFactors(BigInteger $d, BigInteger $e, BigInteger $n): array
+ {
+ $zero = BigInteger::createFromDecimal(0);
+ $one = BigInteger::createFromDecimal(1);
+ $two = BigInteger::createFromDecimal(2);
+
+ $k = $d->multiply($e)->subtract($one);
+
+ if ($k->isEven()) {
+ $r = $k;
+ $t = $zero;
+
+ do {
+ $r = $r->divide($two);
+ $t = $t->add($one);
+ } while ($r->isEven());
+
+ $found = false;
+ $y = null;
+
+ for ($i = 1; $i <= 100; ++$i) {
+ $g = BigInteger::random($n->subtract($one));
+ $y = $g->modPow($r, $n);
+
+ if ($y->equals($one) || $y->equals($n->subtract($one))) {
+ continue;
+ }
+
+ for ($j = $one; $j->lowerThan($t->subtract($one)); $j = $j->add($one)) {
+ $x = $y->modPow($two, $n);
+
+ if ($x->equals($one)) {
+ $found = true;
+
+ break;
+ }
+
+ if ($x->equals($n->subtract($one))) {
+ continue;
+ }
+
+ $y = $x;
+ }
+
+ $x = $y->modPow($two, $n);
+ if ($x->equals($one)) {
+ $found = true;
+
+ break;
+ }
+ }
+
+ if (true === $found) {
+ $p = $y->subtract($one)->gcd($n);
+ $q = $n->divide($p);
+
+ return [$p, $q];
+ }
+ }
+
+ throw new \InvalidArgumentException('Unable to find prime factors.');
+ }
+}