Elliptic curve cryptography - Revision history

NotATether: Multiplication of two points is not possible.

2024-12-11T06:40:07Z

Multiplication of two points is not possible.

← Older revision		Revision as of 06:40, 11 December 2024
Line 1:		Line 1:
	Elliptic Curve Cryptography (sometimes called ECC for short) is the study of elliptic curve equations and the arithmetic operations that apply to them. Normally, an elliptic curve involves two ~~variables~~ x and y which correspond to the X- and Y- coordinates of a point respectively. Curves have special operations for adding, subtracting, and ~~multiplying two points~~, and the way these operations work is very different from their scalar counterparts.		Elliptic Curve Cryptography (sometimes called ECC for short) is the study of elliptic curve equations and the arithmetic operations that apply to them. Normally, an elliptic curve involves two field elements <code>x</code> and <code>y</code> which correspond to the X- and Y- coordinates of a point respectively. Curves have special operations for adding and subtracting points, as well as multiplication by a field element and inversion, and the way these operations work is very different from their scalar counterparts.

	All curve points have a '''generator point''' <code>G</code> which can produce all the other points on the curve by means of multiplication by a scalar number. G also happens to be the multiplicative identity, while the additive identity is a special point called the point at infinity and it's represented as 0 or uppercase <code>O</code>. It can be thought of as a limit to both ends of the curve.		All curve points have a '''generator point''' <code>G</code> which can produce all the other points on the curve by means of multiplication by a scalar number. G also happens to be the multiplicative identity, while the additive identity is a special point called the point at infinity and it's represented as 0 or uppercase <code>O</code>. It can be thought of as a limit to both ends of the curve.

NotATether: Replace point multiplication with scalar multiplication

2024-12-11T06:36:10Z

Replace point multiplication with scalar multiplication

← Older revision		Revision as of 06:36, 11 December 2024
Line 55:		Line 55:
	=== Modular Multiplicative Inverse ===		=== Modular Multiplicative Inverse ===

	The modular multiplicative inverse of a point P<sup>-1</sup> is the problem of finding a factor <code>x</code> such that <code>xP ≅ 1 (mod p)</code>, where <code>p</code> is the curve group order. This is a congruence relation, for which there are some algorithms to this problem listed at<ref>https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/</ref>. Modular Multiplicate Inverse can be combined with ~~point~~ multiplication to ~~implement point~~ division, by inverting the ~~second operand~~.		The modular multiplicative inverse of a point P<sup>-1</sup> is the problem of finding a factor <code>x</code> such that <code>xP ≅ 1 (mod p)</code>, where <code>p</code> is the curve group order. This is a congruence relation, for which there are some algorithms to this problem listed at<ref>https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/</ref>. Modular Multiplicate Inverse can be combined with scalar multiplication to perform a division, by inverting the point.

	== References ==		== References ==

NotATether: It's scalar multiplication - point times a field element

2024-12-11T06:34:32Z

It's scalar multiplication - point times a field element

← Older revision		Revision as of 06:34, 11 December 2024
Line 49:		Line 49:
	The commutative property holds because it doesn't matter which way you add <code>Q + P</code> or <code>P + Q</code>; the line is the same. And the associative property also holds because it doesn't matter which points you add first before others, you will ultimately arrive at the same point.		The commutative property holds because it doesn't matter which way you add <code>Q + P</code> or <code>P + Q</code>; the line is the same. And the associative property also holds because it doesn't matter which points you add first before others, you will ultimately arrive at the same point.

	=== ~~Point~~ Multiplication ===		=== Scalar Multiplication ===

	It's possible to combine the two processes of point addition and point doubling to multiply ~~arbitrary~~ numbers~~, otherwise known as point multiplication~~. You can implement ~~point~~ multiplication as a series of point doubles and point additions or by using the [https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Montgomery_ladder Montgomery ladder] method for computing point multiplications.		It's possible to combine the two processes of point addition and point doubling to multiply a point with scalar numbers. You can implement scalar multiplication as a series of point doubles and point additions or by using the [https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Montgomery_ladder Montgomery ladder] method for computing point multiplications.

	=== Modular Multiplicative Inverse ===		=== Modular Multiplicative Inverse ===

NotATether: fix very serious point addition error

2021-08-28T01:52:03Z

fix very serious point addition error

← Older revision		Revision as of 01:52, 28 August 2021
Line 23:		Line 23:
	else:		else:
	# Point addition: P+Q		# Point addition: P+Q
	lambda = (y2 ~~- y1~~)(x2 ~~- x1~~)*-1		lambda = (y1 - y2)(x1 - x2)*-1
	x3 = lambda**2 - x1 - x2		x3 = lambda**2 - x1 - x2
	y3 = lambda*(x1 - x3) - y1		y3 = lambda*(x1 - x3) - y1

NotATether: fix indent error

2021-08-24T06:06:55Z

fix indent error

← Older revision		Revision as of 06:06, 24 August 2021
Line 24:		Line 24:
	# Point addition: P+Q		# Point addition: P+Q
	lambda = (y2 - y1)(x2 - x1)*-1		lambda = (y2 - y1)(x2 - x1)*-1
	x3 = lambda**2 - x1 - x2		x3 = lambda**2 - x1 - x2
	y3 = lambda*(x1 - x3) - y1		y3 = lambda*(x1 - x3) - y1

	It follows that <code>(x1,y1)</code> and <code>(x2,y2)</code> are the input points, The <code>lambda</code> variable is an expression made out of the x1,y1 and x2,y2 coordinates that refers to the slope of the name made by drawing a line between point A and point B. The result of the point addition is will always be the intersection between the curve, and the line formed by x1,y1 and x2,y2. It follows that since there are three intersection points between a line formed by point addition and the curve, two of them are the operands, and the third one is the ''negative'' of the sum of the two points. The exception is when you add the point-at-infinity ('''0''', sometimes written as uppercase O) to any point or you add the negative of a point to itself, in which case there will only be two intersection points but the result of those operations is well-defined as the original point and '''0''' respectively.		It follows that <code>(x1,y1)</code> and <code>(x2,y2)</code> are the input points, The <code>lambda</code> variable is an expression made out of the x1,y1 and x2,y2 coordinates that refers to the slope of the name made by drawing a line between point A and point B. The result of the point addition is will always be the intersection between the curve, and the line formed by x1,y1 and x2,y2. It follows that since there are three intersection points between a line formed by point addition and the curve, two of them are the operands, and the third one is the ''negative'' of the sum of the two points. The exception is when you add the point-at-infinity ('''0''', sometimes written as uppercase O) to any point or you add the negative of a point to itself, in which case there will only be two intersection points but the result of those operations is well-defined as the original point and '''0''' respectively.

NotATether: Add references

2021-07-28T00:53:34Z

Add references

← Older revision		Revision as of 00:53, 28 July 2021
Line 56:		Line 56:

	The modular multiplicative inverse of a point P<sup>-1</sup> is the problem of finding a factor <code>x</code> such that <code>xP ≅ 1 (mod p)</code>, where <code>p</code> is the curve group order. This is a congruence relation, for which there are some algorithms to this problem listed at<ref>https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/</ref>. Modular Multiplicate Inverse can be combined with point multiplication to implement point division, by inverting the second operand.		The modular multiplicative inverse of a point P<sup>-1</sup> is the problem of finding a factor <code>x</code> such that <code>xP ≅ 1 (mod p)</code>, where <code>p</code> is the curve group order. This is a congruence relation, for which there are some algorithms to this problem listed at<ref>https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/</ref>. Modular Multiplicate Inverse can be combined with point multiplication to implement point division, by inverting the second operand.

			== References ==

NotATether: add other operations. Also see https://bitcointalk.org/index.php?topic=5235482.0 (my own work)

2021-07-28T00:53:04Z

add other operations. Also see https://bitcointalk.org/index.php?topic=5235482.0 (my own work)

@@ Line 6: / Line 6: @@
 == Operations ==
 '''Point addition''' for two unequal points <code>(x3,y3) = (x1,y1) + (x2,y2)</code> can be performed in simple scalar arithmetic with the following pseudocode. Note that ''all'' arithmetic operation involving x or y coordinates are modulus of the characteristic (<code>mod p</code>) applied after it. All occurrences of the modulus are omitted from the pseudocode for brevity. Also displayed here is '''point doubling''' which is the case where both points are the same and the traditional point addition algorithm would otherwise not work on them.
@@ Line 24: / Line 26: @@
      x3 = lambda**2 - x1 - x2
      y3 = lambda*(x1 - x3) - y1

NotATether: Add ECC page

2021-06-12T18:29:04Z

Add ECC page

New page

Elliptic Curve Cryptography (sometimes called ECC for short) is the study of elliptic curve equations and the arithmetic operations that apply to them. Normally, an elliptic curve involves two variables x and y which correspond to the X- and Y- coordinates of a point respectively. Curves have special operations for adding, subtracting, and multiplying two points, and the way these operations work is very different from their scalar counterparts.

All curve points have a '''generator point''' <code>G</code> which can produce all the other points on the curve by means of multiplication by a scalar number. G also happens to be the multiplicative identity, while the additive identity is a special point called the point at infinity and it's represented as 0 or uppercase <code>O</code>. It can be thought of as a limit to both ends of the curve.

Each curve has a '''characteristic''' number which stands for the number of times the generator point can be added to itself before you end up back at <code>G</code>. The x and y coordinates must not be larger or equal to this scalar number. Each curve also has a curve '''order'''. All private keys (which themselves are represented as numbers) must be smaller than the group order.

== Operations ==

'''Point addition''' for two unequal points <code>(x3,y3) = (x1,y1) + (x2,y2)</code> can be performed in simple scalar arithmetic with the following pseudocode. Note that ''all'' arithmetic operation involving x or y coordinates are modulus of the characteristic (<code>mod p</code>) applied after it. All occurrences of the modulus are omitted from the pseudocode for brevity. Also displayed here is '''point doubling''' which is the case where both points are the same and the traditional point addition algorithm would otherwise not work on them.

if (x1,y1) == O
result = (x2,y2)
else if (x2,y2) == O
result = (x1,y1)
else if (x2,y2) == (x1,y1)**(-1)
result = O

if (x2,y2) == (x1,y1):
# Point doubling: 2P
lambda = (3 * x1**2) * (2*y1)**-1
else:
# Point addition: P+Q
lambda = (y2 - y1)*(x2 - x1)**-1
x3 = lambda**2 - x1 - x2
y3 = lambda*(x1 - x3) - y1