Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



The Arithmetic of Scalar Multiplication on Elliptic Curve Cryptography
Posted:
Aug 13, 2013 8:20 PM


The Arithmetic of Scalar Multiplication on Elliptic Curve Cryptography: k times or k  1 times?
Point 'addition' on elliptic curves is both commutative P + Q = Q + P and associative (P + Q) + R = P + (Q + R)
So when point P on an elliptic curve is multiplied by a scalar k, should it be explained as 'p added to itself k  1 times' or 'p added to itself k times'?
Which definition of scalar multiplication on elliptic curves is right and why? Please make your explanation as simple as possible!
======== k  1 times ========
If point P on EC is added to itself (k1) times then we obtain a new point kP on elliptic curve and kP is termed as the scalar multiplication of point P by scalar k. Source: http://www.ijcsi.org/papers/IJCSI81131137.pdf
The fundamental operation for generating a finite abelian group over an elliptic curve is the addition of two points on it. If point P on EC is added to itself (k1) times then we obtain a new point kP on elliptic curve and kP is termed as the scalar multiplication of point P by scalar k. Source: http://www.ijcsi.org/papers/IJCSI81131137.pdf
Point iteration is adding a point to itself multiple times. If a point is added to itself k1 times, where k is a positive integer then point iteration is represented as: [k]P=P+P+ ..+P (k1 times). Source: http://dijiang.mobicloud.asu.edu/snac/document/ECCparingsportable.pdf
Scalar point multiplication is the major building block of all elliptic curve cryptosystems, an operation of the form where k is a positive integer and P is a point on the elliptic curve. Calculating gives the result of adding the point P to itself for exact k1 times, which results in another point Q on the elliptic curve. AND ALSO Scalar point multiplication is one of the major buildings of ECC block. An operation of form where is a positive integer, P is a point on the curve. The idea is adding the point P to itself k  1 times to get the resulted point Q. Source: http://www.ijser.org/paper/MakeaSecureConnectionUsingEllipticCurveDigitalSignature.html
... multiplication operation computes the multiple Q = kP, which corresponds to adding P to itself k  1 times Source: http://eprint.iacr.org/2013/131.pdf
====== k times ======
Cryptographic schemes based on ECC rely on scalar multiplication of elliptic curve points. As before given an integer k and a point P... scalar multiplication is the process of adding P to itself k times. Source: http://www.secg.org/collateral/sec1.pdf
The scalar integer multiplication of an elliptic curve point, P is defined as the process of adding P to itself k times. Q = k P. Source: http://mmogollon.com/app/download/6771222004/Chapter+8+Elliptic+Curve+Cryptography.pptx
Let k be a positive integer and P a point on an elliptic curve. Then elliptic curve scalar multiplication is the operation that computes the multiple Q = kP, defined as the point resulting of adding P to itself k times. Source: http://cacr.uwaterloo.ca/techreports/2011/cacr201107.pdf
Scalar Multiplication. Adding a point P to itself k times is called scalar multiplication or point multiplication, and is denoted as Q = kP Source: http://research.microsoft.com/pubs/193347/Published.pdf
Given an elliptic curve E and a point P on the curve, the point Q is calculated by point scalar multiplication where the point P is added to itself k times Source: http://hal.archivesouvertes.fr/docs/00/15/33/68/PDF/itng07.pdf
==========
So which definition of scalar multiplication on elliptic curves is right and why?
Thank you!
Jonathan Crabtree Mathematics Researcher Melbourne Australia (Currently over at http://bit.ly/Vrrx9Q)
P.S. Please post your comment as an 'inline' reply so there is only one discussion and each reply does NOT start a new discussion without the information above. Dear moderator, would you please ensure this?
Message was edited by: Jonathan Crabtree to include a P.S.



