Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: The Arithmetic of Scalar Multiplication on Elliptic Curve Cryptography
Replies: 0

 Search Thread: Advanced Search

 Jonathan J. Crabtree Posts: 355 From: Melbourne Australia Registered: 12/19/10
The Arithmetic of Scalar Multiplication on Elliptic Curve Cryptography
Posted: Aug 13, 2013 8:20 PM
 Plain Text Reply

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 (k-1) 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/IJCSI-8-1-131-137.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 (k-1) 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/IJCSI-8-1-131-137.pdf

Point iteration is adding a point to itself multiple times. If a point is added to itself k-1 times, where k is a positive integer then point iteration is represented as: [k]P=P+P+ ..+P (k-1 times).
Source: http://dijiang.mobicloud.asu.edu/snac/document/ECC-parings-portable.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 k-1 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/Make-a-Secure-Connection-Using-Elliptic-Curve-Digital-Signature.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/cacr2011-07.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.archives-ouvertes.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.

© The Math Forum at NCTM 1994-2018. All Rights Reserved.