Curve::mul() - Code Metrics - Inspection of "Key Factory reviewed" - web-token/jwt-framework - Measure and Improve Code Quality continuously with Scrutinizer

Failed Conditions

Push — master ( 1edcb4...1e22a0 )

by Florent

created 2017-10-26 11:29 UTC

Curve::mul() B

↳ Parent: Curve

Complexity

Conditions	5
Paths	7

Size

Total Lines	37
Code Lines	21

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
dl	0
loc	37
rs	8.439
c	0
b	0
f	0
cc	5
eloc	21
nc	7
nop	2

<?php

declare(strict_types=1);

/*
 * The MIT License (MIT)
 *
 * Copyright (c) 2014-2017 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\Core\Util\Ecc;

/**
 * This class is a representation of an EC over a field modulo a prime number.
 *
 * Important objectives for this class are:
 * - Does the curve contain a point?
 * - Comparison of two curves.
 */
final class Curve
{
    /**
     * Elliptic curve over the field of integers modulo a prime.
     *
     * @var \GMP
     */
    private $a;

    /**
     * @var \GMP
     */
    private $b;

    /**
     * @var \GMP
     */
    private $prime;

    /**
     * Binary length of keys associated with these curve parameters.
     *
     * @var int
     */
    private $size;

    /**
     * @var Point
     */
    private $generator;

    /**
     * @param int   $size
     * @param \GMP  $prime
     * @param \GMP  $a
     * @param \GMP  $b
     * @param Point $generator
     */
    public function __construct(int $size, \GMP $prime, \GMP $a, \GMP $b, Point $generator)
    {
        $this->size = $size;
        $this->prime = $prime;
        $this->a = $a;
        $this->b = $b;
        $this->generator = $generator;
    }

    /**
     * @return \GMP
     */
    public function getA(): \GMP
    {
        return $this->a;
    }

    /**
     * @return \GMP
     */
    public function getB(): \GMP
    {
        return $this->b;
    }

    /**
     * @return \GMP
     */
    public function getPrime(): \GMP
    {
        return $this->prime;
    }

    /**
     * @return int
     */
    public function getSize(): int
    {
        return $this->size;
    }

    /**
     * @param \GMP      $x
     * @param \GMP      $y
     * @param \GMP|null $order
     *
     * @return Point
     */
    public function getPoint(\GMP $x, \GMP $y, ?\GMP $order = null): Point
    {
        if (!$this->contains($x, $y)) {
            throw new \RuntimeException('Curve '.$this->__toString().' does not contain point ('.Math::toString($x).', '.Math::toString($y).')');
        }
        $point = Point::create($x, $y, $order);
        if (!is_null($order)) {
            $mul = $this->mul($point, $order);
            if (!$mul->isInfinity()) {
                throw new \RuntimeException('SELF * ORDER MUST EQUAL INFINITY. ('.(string) $mul.' found instead)');
            }
        }

        return $point;
    }

    /**
     * @param \GMP $x
     * @param \GMP $y
     *
     * @return PublicKey
     */
    public function getPublicKeyFrom(\GMP $x, \GMP $y): PublicKey
    {
        $zero = gmp_init(0, 10);
        if (Math::cmp($x, $zero) < 0 || Math::cmp($this->generator->getOrder(), $x) <= 0 || Math::cmp($y, $zero) < 0 || Math::cmp($this->generator->getOrder(), $y) <= 0) {
            throw new \RuntimeException('Generator point has x and y out of range.');
        }
        $point = $this->getPoint($x, $y);

        return PublicKey::create($point);
    }

    /**
     * @param \GMP $x
     * @param \GMP $y
     *
     * @return bool
     */
    public function contains(\GMP $x, \GMP $y): bool
    {
        $eq_zero = Math::equals(
            ModularArithmetic::sub(
                Math::pow($y, 2),
                Math::add(
                    Math::add(
                        Math::pow($x, 3),
                        Math::mul($this->getA(), $x)
                    ),
                    $this->getB()
                ),
                $this->getPrime()
            ),
            gmp_init(0, 10)
        );

        return $eq_zero;
    }

    /**
     * @param Point $one
     * @param Point $two
     *
     * @return Point
     */
    public function add(Point $one, Point $two): Point
    {
        if ($two->isInfinity()) {
            return clone $one;
        }

        if ($one->isInfinity()) {
            return clone $two;
        }

        if (Math::equals($two->getX(), $one->getX())) {
            if (Math::equals($two->getY(), $one->getY())) {
                return $this->getDouble($one);
            } else {
                return Point::infinity();
            }
        }

        $slope = ModularArithmetic::div(
            Math::sub($two->getY(), $one->getY()),
            Math::sub($two->getX(), $one->getX()),
            $this->getPrime()
        );

        $xR = ModularArithmetic::sub(
            Math::sub(Math::pow($slope, 2), $one->getX()),
            $two->getX(),
            $this->getPrime()
        );

        $yR = ModularArithmetic::sub(
            Math::mul($slope, Math::sub($one->getX(), $xR)),
            $one->getY(),
            $this->getPrime()
        );

        return $this->getPoint($xR, $yR, $one->getOrder());
    }

    /**
     * @param Point $one
     * @param \GMP  $n
     *
     * @return Point
     */
    public function mul(Point $one, \GMP $n): Point
    {
        if ($one->isInfinity()) {
            return Point::infinity();
        }

        /** @var \GMP $zero */
        $zero = gmp_init(0, 10);
        if (Math::cmp($one->getOrder(), $zero) > 0) {
            $n = Math::mod($n, $one->getOrder());
        }

        if (Math::equals($n, $zero)) {
            return Point::infinity();
        }

        /** @var Point[] $r */
        $r = [
            Point::infinity(),
            clone $one,
        ];

        $k = $this->getSize();
        $n = str_pad(Math::baseConvert(Math::toString($n), 10, 2), $k, '0', STR_PAD_LEFT);

        for ($i = 0; $i < $k; ++$i) {
            $j = $n[$i];
            Point::cswap($r[0], $r[1], $j ^ 1);
            $r[0] = $this->add($r[0], $r[1]);
            $r[1] = $this->getDouble($r[1]);
            Point::cswap($r[0], $r[1], $j ^ 1);
        }

        $this->validate($r[0]);

        return $r[0];
    }

    /**
     * @param Curve $other
     *
     * @return int
     */
    public function cmp(Curve $other): int
    {
        $equal = Math::equals($this->getA(), $other->getA());
        $equal &= Math::equals($this->getB(), $other->getB());
        $equal &= Math::equals($this->getPrime(), $other->getPrime());

        return $equal ? 0 : 1;
    }

    /**
     * @param Curve $other
     *
     * @return bool
     */
    public function equals(Curve $other): bool
    {
        return $this->cmp($other) === 0;
    }

    /**
     * @return string
     */
    public function __toString(): string
    {
        return 'curve('.Math::toString($this->getA()).', '.Math::toString($this->getB()).', '.Math::toString($this->getPrime()).')';
    }

    /**
     * @param Point $point
     */
    private function validate(Point $point)
    {
        if (!$point->isInfinity() && !$this->contains($point->getX(), $point->getY())) {
            throw new \RuntimeException('Invalid point');
        }
    }

    /**
     * @param Point $point
     *
     * @return Point
     */
    public function getDouble(Point $point): Point
    {
        if ($point->isInfinity()) {
            return Point::infinity();
        }

        $a = $this->getA();
        $threeX2 = Math::mul(gmp_init(3, 10), Math::pow($point->getX(), 2));

        $tangent = ModularArithmetic::div(
            Math::add($threeX2, $a),
            Math::mul(gmp_init(2, 10), $point->getY()),
            $this->getPrime()
        );

        $x3 = ModularArithmetic::sub(
            Math::pow($tangent, 2),
            Math::mul(gmp_init(2, 10), $point->getX()),
            $this->getPrime()
        );

        $y3 = ModularArithmetic::sub(
            Math::mul($tangent, Math::sub($point->getX(), $x3)),
            $point->getY(),
            $this->getPrime()
        );

        return $this->getPoint($x3, $y3, $point->getOrder());
    }

    /**
     * @return PrivateKey
     */
    public function createPrivateKey(): PrivateKey
    {
        return PrivateKey::create($this->generate());
    }

    /**
     * @param PrivateKey $privateKey
     *
     * @return PublicKey
     */
    public function createPublicKey(PrivateKey $privateKey): PublicKey
    {
        $point = $this->mul($this->generator, $privateKey->getSecret());

        return PublicKey::create($point);
    }

    /**
     * @return \GMP
     */
    private function generate(): \GMP
    {
        $max = $this->generator->getOrder();
        $numBits = $this->bnNumBits($max);
        $numBytes = (int) ceil($numBits / 8);
        // Generate an integer of size >= $numBits
        $bytes = random_bytes($numBytes);
        $value = Math::stringToInt($bytes);
        $mask = gmp_sub(gmp_pow(2, $numBits), 1);
        $integer = gmp_and($value, $mask);

        return $integer;
    }

    /**
     * Returns the number of bits used to store this number. Non-significant upper bits are not counted.
     *
     * @param \GMP $x
     *
     * @return int
     *
     * @see https://www.openssl.org/docs/crypto/BN_num_bytes.html
     */
    private function bnNumBits(\GMP $x): int
    {
        $zero = gmp_init(0, 10);
        if (Math::equals($x, $zero)) {
            return 0;
        }
        $log2 = 0;
        while (false === Math::equals($x, $zero)) {
            $x = Math::rightShift($x, 1);
            ++$log2;
        }

        return $log2;
    }

    /**
     * @return Point
     */
    public function getGenerator(): Point
    {
        return $this->generator;
    }
}


1			<?php
2
3			declare(strict_types=1);
4
5			/*
6			* The MIT License (MIT)
7			*
8			* Copyright (c) 2014-2017 Spomky-Labs
9			*
10			* This software may be modified and distributed under the terms
11			* of the MIT license. See the LICENSE file for details.
12			*/
13
14			namespace Jose\Component\Core\Util\Ecc;
15
16			/**
17			* This class is a representation of an EC over a field modulo a prime number.
18			*
19			* Important objectives for this class are:
20			* - Does the curve contain a point?
21			* - Comparison of two curves.
22			*/
23			final class Curve
24			{
25			/**
26			* Elliptic curve over the field of integers modulo a prime.
27			*
28			* @var \GMP
29			*/
30			private $a;
31
32			/**
33			* @var \GMP
34			*/
35			private $b;
36
37			/**
38			* @var \GMP
39			*/
40			private $prime;
41
42			/**
43			* Binary length of keys associated with these curve parameters.
44			*
45			* @var int
46			*/
47			private $size;
48
49			/**
50			* @var Point
51			*/
52			private $generator;
53
54			/**
55			* @param int $size
56			* @param \GMP $prime
57			* @param \GMP $a
58			* @param \GMP $b
59			* @param Point $generator
60			*/
61			public function __construct(int $size, \GMP $prime, \GMP $a, \GMP $b, Point $generator)
62			{
63			$this->size = $size;
64			$this->prime = $prime;
65			$this->a = $a;
66			$this->b = $b;
67			$this->generator = $generator;
68			}
69
70			/**
71			* @return \GMP
72			*/
73			public function getA(): \GMP
74			{
75			return $this->a;
76			}
77
78			/**
79			* @return \GMP
80			*/
81			public function getB(): \GMP
82			{
83			return $this->b;
84			}
85
86			/**
87			* @return \GMP
88			*/
89			public function getPrime(): \GMP
90			{
91			return $this->prime;
92			}
93
94			/**
95			* @return int
96			*/
97			public function getSize(): int
98			{
99			return $this->size;
100			}
101
102			/**
103			* @param \GMP $x
104			* @param \GMP $y
105			* @param \GMP\|null $order
106			*
107			* @return Point
108			*/
109			public function getPoint(\GMP $x, \GMP $y, ?\GMP $order = null): Point
110			{
111			if (!$this->contains($x, $y)) {
112			throw new \RuntimeException('Curve '.$this->__toString().' does not contain point ('.Math::toString($x).', '.Math::toString($y).')');
113			}
114			$point = Point::create($x, $y, $order);
115			if (!is_null($order)) {
116			$mul = $this->mul($point, $order);
117			if (!$mul->isInfinity()) {
118			throw new \RuntimeException('SELF * ORDER MUST EQUAL INFINITY. ('.(string) $mul.' found instead)');
119			}
120			}
121
122			return $point;
123			}
124
125			/**
126			* @param \GMP $x
127			* @param \GMP $y
128			*
129			* @return PublicKey
130			*/
131			public function getPublicKeyFrom(\GMP $x, \GMP $y): PublicKey
132			{
133			$zero = gmp_init(0, 10);
134			if (Math::cmp($x, $zero) < 0 \|\| Math::cmp($this->generator->getOrder(), $x) <= 0 \|\| Math::cmp($y, $zero) < 0 \|\| Math::cmp($this->generator->getOrder(), $y) <= 0) {
135			throw new \RuntimeException('Generator point has x and y out of range.');
136			}
137			$point = $this->getPoint($x, $y);
138
139			return PublicKey::create($point);
140			}
141
142			/**
143			* @param \GMP $x
144			* @param \GMP $y
145			*
146			* @return bool
147			*/
148			public function contains(\GMP $x, \GMP $y): bool
149			{
150			$eq_zero = Math::equals(
151			ModularArithmetic::sub(
152			Math::pow($y, 2),
153			Math::add(
154			Math::add(
155			Math::pow($x, 3),
156			Math::mul($this->getA(), $x)
157			),
158			$this->getB()
159			),
160			$this->getPrime()
161			),
162			gmp_init(0, 10)
163			);
164
165			return $eq_zero;
166			}
167
168			/**
169			* @param Point $one
170			* @param Point $two
171			*
172			* @return Point
173			*/
174			public function add(Point $one, Point $two): Point
175			{
176			if ($two->isInfinity()) {
177			return clone $one;
178			}
179
180			if ($one->isInfinity()) {
181			return clone $two;
182			}
183
184			if (Math::equals($two->getX(), $one->getX())) {
185			if (Math::equals($two->getY(), $one->getY())) {
186			return $this->getDouble($one);
187			} else {
188			return Point::infinity();
189			}
190			}
191
192			$slope = ModularArithmetic::div(
193			Math::sub($two->getY(), $one->getY()),
194			Math::sub($two->getX(), $one->getX()),
195			$this->getPrime()
196			);
197
198			$xR = ModularArithmetic::sub(
199			Math::sub(Math::pow($slope, 2), $one->getX()),
200			$two->getX(),
201			$this->getPrime()
202			);
203
204			$yR = ModularArithmetic::sub(
205			Math::mul($slope, Math::sub($one->getX(), $xR)),
206			$one->getY(),
207			$this->getPrime()
208			);
209
210			return $this->getPoint($xR, $yR, $one->getOrder());
211			}
212
213			/**
214			* @param Point $one
215			* @param \GMP $n
216			*
217			* @return Point
218			*/
219			public function mul(Point $one, \GMP $n): Point
220			{
221			if ($one->isInfinity()) {
222			return Point::infinity();
223			}
224
225			/** @var \GMP $zero */
226			$zero = gmp_init(0, 10);
227			if (Math::cmp($one->getOrder(), $zero) > 0) {
228			$n = Math::mod($n, $one->getOrder());
229			}
230
231			if (Math::equals($n, $zero)) {
232			return Point::infinity();
233			}
234
235			/** @var Point[] $r */
236			$r = [
237			Point::infinity(),
238			clone $one,
239			];
240
241			$k = $this->getSize();
242			$n = str_pad(Math::baseConvert(Math::toString($n), 10, 2), $k, '0', STR_PAD_LEFT);
243
244			for ($i = 0; $i < $k; ++$i) {
245			$j = $n[$i];
246			Point::cswap($r[0], $r[1], $j ^ 1);
247			$r[0] = $this->add($r[0], $r[1]);
248			$r[1] = $this->getDouble($r[1]);
249			Point::cswap($r[0], $r[1], $j ^ 1);
250			}
251
252			$this->validate($r[0]);
253
254			return $r[0];
255			}
256
257			/**
258			* @param Curve $other
259			*
260			* @return int
261			*/
262			public function cmp(Curve $other): int
263			{
264			$equal = Math::equals($this->getA(), $other->getA());
265			$equal &= Math::equals($this->getB(), $other->getB());
266			$equal &= Math::equals($this->getPrime(), $other->getPrime());
267
268			return $equal ? 0 : 1;
269			}
270
271			/**
272			* @param Curve $other
273			*
274			* @return bool
275			*/
276			public function equals(Curve $other): bool
277			{
278			return $this->cmp($other) === 0;
279			}
280
281			/**
282			* @return string
283			*/
284			public function __toString(): string
285			{
286			return 'curve('.Math::toString($this->getA()).', '.Math::toString($this->getB()).', '.Math::toString($this->getPrime()).')';
287			}
288
289			/**
290			* @param Point $point
291			*/
292			private function validate(Point $point)
293			{
294			if (!$point->isInfinity() && !$this->contains($point->getX(), $point->getY())) {
295			throw new \RuntimeException('Invalid point');
296			}
297			}
298
299			/**
300			* @param Point $point
301			*
302			* @return Point
303			*/
304			public function getDouble(Point $point): Point
305			{
306			if ($point->isInfinity()) {
307			return Point::infinity();
308			}
309
310			$a = $this->getA();
311			$threeX2 = Math::mul(gmp_init(3, 10), Math::pow($point->getX(), 2));
312
313			$tangent = ModularArithmetic::div(
314			Math::add($threeX2, $a),
315			Math::mul(gmp_init(2, 10), $point->getY()),
316			$this->getPrime()
317			);
318
319			$x3 = ModularArithmetic::sub(
320			Math::pow($tangent, 2),
321			Math::mul(gmp_init(2, 10), $point->getX()),
322			$this->getPrime()
323			);
324
325			$y3 = ModularArithmetic::sub(
326			Math::mul($tangent, Math::sub($point->getX(), $x3)),
327			$point->getY(),
328			$this->getPrime()
329			);
330
331			return $this->getPoint($x3, $y3, $point->getOrder());
332			}
333
334			/**
335			* @return PrivateKey
336			*/
337			public function createPrivateKey(): PrivateKey
338			{
339			return PrivateKey::create($this->generate());
340			}
341
342			/**
343			* @param PrivateKey $privateKey
344			*
345			* @return PublicKey
346			*/
347			public function createPublicKey(PrivateKey $privateKey): PublicKey
348			{
349			$point = $this->mul($this->generator, $privateKey->getSecret());
350
351			return PublicKey::create($point);
352			}
353
354			/**
355			* @return \GMP
356			*/
357			private function generate(): \GMP
358			{
359			$max = $this->generator->getOrder();
360			$numBits = $this->bnNumBits($max);
361			$numBytes = (int) ceil($numBits / 8);
362			// Generate an integer of size >= $numBits
363			$bytes = random_bytes($numBytes);
364			$value = Math::stringToInt($bytes);
365			$mask = gmp_sub(gmp_pow(2, $numBits), 1);
366			$integer = gmp_and($value, $mask);
367
368			return $integer;
369			}
370
371			/**
372			* Returns the number of bits used to store this number. Non-significant upper bits are not counted.
373			*
374			* @param \GMP $x
375			*
376			* @return int
377			*
378			* @see https://www.openssl.org/docs/crypto/BN_num_bytes.html
379			*/
380			private function bnNumBits(\GMP $x): int
381			{
382			$zero = gmp_init(0, 10);
383			if (Math::equals($x, $zero)) {
384			return 0;
385			}
386			$log2 = 0;
387			while (false === Math::equals($x, $zero)) {
388			$x = Math::rightShift($x, 1);
389			++$log2;
390			}
391
392			return $log2;
393			}
394
395			/**
396			* @return Point
397			*/
398			public function getGenerator(): Point
399			{
400			return $this->generator;
401			}
402			}
403

web-token / jwt-framework

Push — master ( 1edcb4...1e22a0 )

Curve::mul() B

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like