Talk:Elliptic curve point multiplication

Initial

I've started a page on point multiplication because I couldn't find one. If one exists please link to it from the main ECC page. Tomstdenis (talk) 11:18, 3 August 2010 (UTC)

I think point and double algorithm should be

* Q = 0
 * for i from m to 0 do
    * P := 2P (using point doubling)m [Rather than Q=2Q] 
    * if di = 1 then Q := Q + P (using point addition)
 * Return Q

Correct me if i am wrong. —Preceding unsigned comment added by 117.194.231.98 (talk) 03:46, 15 January 2011 (UTC)

You're right, though I meant to give right-to-left algorithms so I fixed the 'for' statements to be "0 to m" instead of "m to 0". Thanks for the correction. Tomstdenis (talk) 14:17, 18 February 2011 (UTC)

"Point addition is defined as taking two points along a curve E and computing where a line through them intersects the curve." Wouldn't that be at those two points? Is this right? Should it read "outside of" ? 88.192.1.149 (talk) 20:46, 19 December 2012 (UTC)

This also confused me at first but I found an explanation. Nutshell version: an elliptic curve plotted on a simple X,Y grid bends back and forth in such a way that a straight line through any two points will also intersect the curve at a third point. An elliptic curve may even look like multiple pieces when converted to X,Y coordinates, even though in its own coordinate space it is still a single line. For example, see the diagram at [1] which looks like a flattened parabola and a separate oval. Is it worth adding something like this to the article? Swartzer (talk) 01:31, 29 May 2013 (UTC)

Diagram?

Does multiplication or at least addition have a geometrical meaning that could be clarified by a diagram?--Jrm2007 (talk) 06:21, 7 January 2014 (UTC)

I see that this is covered in the article about elliptical curves.--Jrm2007 (talk) 06:41, 7 January 2014 (UTC)

Point Addition and Point Doubling formulas seem to be incorrect

Good article and explanation. It was really useful. However, the formulas in point doubling and point addition seem to be at least somewhat incorrect.

I recommend taking the formulas from: http://www.secg.org/collateral/sec1_final.pdf I did not double check those formulas but the results produce working solutions, If I use equations from this article in sections 2 and 3, the results are not valid solutions.

Also there should probably be a discussion about doing this in modular arithmetic. (also covered by the same article).

If you don't mind I'll update those sections. — Preceding unsigned comment added by Zeruski (talk • contribs) 05:19, 15 January 2014 (UTC)

I think the preceding comment is right. The given formula for point addition doesn't even seem to make sense - the result doesn't depend in any way on $a$ or $b$, i.e. on what specific elliptic curve is being used.

Negative?

What does "negative of the intersection point" mean? This term is used in the definition of addition without first being defined. In my experience negation is usually defined as taking an element that when added to the original gives zero, but that would be a circular definition if we added it to this page.

98.167.44.17 (talk) 06:44, 15 March 2014 (UTC)

Correct misleading description of the montgomery ladder

This article has it's value in that it's giving a course (and partly incorrect) big picture over some concepts that are relevant in the context of elliptic curve cryptography. Because it's useful and helpful for the beginner.

There is extensive research literature about different point addition schemes, including wNAF and Montgomery ladder applications. It is generally accepted, that among these schemes the montgomery ladder is one of the safest schemes. It is, however, well known that a wrong *implementation* of any one of the algorithms is unsafe.

Most importantly, when considering side-channel attacks, these attacks do not attack the algorithm, but a vulnerable implementation.

It is my opinion, that within the scope of an article giving a course overview, reference to the extensive research literature should not be attempted. If references given, then to textbooks or introductory text.

Within this scope, I come to the conclusion, that the reference

YuvalYaromandNaomiBenger.RecoveringOpenSSLECDSAnoncesusingtheFLUSH+RELOADcacheside-channelattack. Cryptology ePrint Archive, Report 2014/140, 2014. http://eprint.iacr.org/

with the accompagning text

"However, it was shown by Yuval Yaromand and Naomi Benger that through application of FLUSH+RELOAD side channel attack the full private key can be revealed in only one multiplication operation."

does not fit into this scope at all and should be removed. This paper does deal with one very specific implementation weakness, relevant only for one specific CPU type and one special firmware implementation.

In my opinion, giving this (yet unprinted !) paper as sole reference for the whole wikipedia page gives the reader a wrong perception of the importance, quality and relevance of this paper.

I suggest to remove this article from the list of references.

If, the decision is taken to use the Wikipedia article as full review of research knowledge, then a representation of *ALL* relevant contributions should be appropriately presented. This would probably include a list of >> 100 research papers.

I also suggest to change the text

"This algorithm is in effect the same speed as the double-and-add approach except that it computes the same number of point additions and doubles regardless of the value of the multiplicand d. This means that at this level the algorithm does not leak any information through timing or power. However, it was shown by Yuval Yaromand and Naomi Benger that through application of FLUSH+RELOAD side channel attack the full private key can be revealed in only one multiplication operation."

to read

"This algorithm is in effect the same speed as the double-and-add approach except that it computes the same number of point additions and doubles regardless of the value of the multiplicand d. I.e. it is not the fastest algorithm available. However, the big advantage of the Montgomery ladder is, that the algorithm may be implemented more securely than other algorithms because it inherently executes in constant time. This provides protection against simple attacks that deduce information on the key by the time that the algorithm takes. It is important to note, that the montgomery ladder form of the addition formula alone does not provide protection against sophisticated so-called side-channel attacks (e.g. namely fault attacks, differential power attacks, etc.)."

Björn Haase (bjoern.m.haase@web.de)

85.183.211.233 (talk) 19:38, 19 April 2014 (UTC)

What is $\lambda$??

The symbol $\lambda$ is used without being defined. If it is common knowledge, it should be a link to what it means. Dscotese (talk) 02:26, 27 July 2015 (UTC)

Trapdor -> one-way

I've made this change as it is correctly explained in the article on trapdoor functions that:

"Functions related to the hardness of the discrete logarithm problem (either modulo a prime or in a group defined over an elliptic curve) are not known to be trapdoor functions, because there is no known "trapdoor" information about the group that enables the efficient computation of discrete logarithms." — Preceding unsigned comment added by Claus from Leipzig (talk • contribs) 07:59, 21 July 2017 (UTC)

Point multiplication explanation not complete

I think some of the implementation details are left out and are not complete. There is for example no comment on when the 'point of infinity' is reached in a calculation. When implementing recently the following standard was of much use to me (appendix A.10). https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=891000&tag=1 Stefdhaeseleer (talk) 08:17, 4 May 2018 (UTC)

Incomplete Windowed Method section.

The Point Multiplication => Windowed Method section has some pseudocode that references `point_double_repeat(Q, w)` but it fails to describe what that function is or how it works. I attempted to implement the windowed method from this Wikipedia article and failed because of this (but I was able, with some effort, to implement the traditional non-windowed method). — Preceding unsigned comment added by Micah71381 (talk • contribs) 03:47, 30 August 2019 (UTC)

Suggest removing the "Windowed Method" and "Sliding-Window Method" as they appear incorrect

See this Stack Exchange post, from where the initial questions reads "Update 10 Aug:" - it goes into details of how the algorithm for the Windowed Method doesn't make any sense. Unless we have a way to explain it properly I would suggest removing it to avoid confusion. — Preceding unsigned comment added by Syscronex (talk • contribs) 08:12, 11 August 2020 (UTC)

Confusing inconsistency in Point operations (diagram and text)

The text uses R to refer to the sum of P and Q i.e. $P+Q=R$. But the diagram (1) marks as R the negation of this sum i.e. $R_{diagram}=-(P+Q)$.
Also, the "Point doubling" section talks about doubling P. But in the diagram (2), it's Q that is doubled, and P is the result of this doubling.

As someone trying to learn point operations, I found the diagrams quite confusing because of this. Perhaps the diagrams could use ${\bar {R}}$ for the point of intersection in (1), to denote that it's really the negative of the result R. And it would be nicely consistent if the result of doubling in (2) was also called ${\bar {R}}$ (instead of P), and P was shown to be coincident with Q. This would match the text with the diagrams and avoid needless confusion.

SundaraRaman (talk) 21:39, 23 June 2021 (UTC)