3
$\begingroup$

I am trying to understand the below paragraph.

Elliptic curve Diffie-Hellman is often calculated using the Montgomery ladder. This gives a simple and efficient calculation that is naturally resistant to timing side channels. The Montgomery ladder also allows each party's public key to be a Montgomery u-coordinate. Using a single coordinate instead of the whole point makes public keys smaller without the expense of point decompression.

I read about Elliptic curves and Montgomery ladder at Wikipedia. Can someone please explain this paragraph in naive language.Also please answer below questions.

  1. What is Montgomery u-coordinate.
  2. A brief explanation of requirement of point decompression.
$\endgroup$
  • 1
    $\begingroup$ Welcome to crypto, interesting first question! Note that I made your title somewhat more specific and changed the way that the list is generated, you can take a look at the edit to see how. $\endgroup$ – Maarten Bodewes May 14 '17 at 15:34
3
$\begingroup$

Montgomery form and ladder

People are typically introduced to elliptic curves in Weierstrass form, namely the points $(x,y)$ that satisfy $y^2 = x^3 + ax + b$. Specifying $a$ and $b$ pick out a particular curve.

There is an alternative representation of elliptic curves, called the Montgomery form:

$Bv^2 = u^3 + Au^2 + u$

Peter Montgomery introduced this form in his 1987 paper. Here, the points are $(u,v)$ pairs and specifying $A$ and $B$ pick out a curve. You can convert from one form to the other. The $u$ here is the u-coordinate you referred to.

Why is this useful?

When doing scalar multiplication on elliptic curves over a field $\mathbb{F}_p$, you have to do a lot of modular divisons / inverses. However, in Montgomery form, $u$ and $v$ are projective coordinates. What this gets you is letting you postpone expensive division operations for as long as possible, giving nice speedups. So think of $u$ as a ratio of two coordinates, similar to (not equal to!) $x/y$.

Very roughly, the Montgomery ladder is doing a "double-and-add" operation on a point in projective space. The input to the ladder is a scale factor $k$ and the u-coordinate, and the output is only the u-coordinate of the scaled point. That's why the Montgomery ladder is called a single-coordinate ladder. If necessary and if you have both $u$ and $v$, you can compute both coordinates of the scaled point, but if you only need the scaled $u$, you get this quickly without having to spend time computing the "baggage" of the other coordinate, like with point compression and decompression.

Point Compression and Decompression

See Section 2.3 for a description of the calculation to do point compression and decompression. The basic idea is it's better to carry one number around than two if you can, so take $(u,v)$ in projective space and combine the two coordinates into a "compressed" value $\tau$ which can later be "decompressed" into $(u,v)$ or $(x,y)$ form. These compression and decompression operations involve taking modular square roots and modular inversion which are expensive. The Montgomery ladder lets you avoid this computation.

$\endgroup$
  • $\begingroup$ I'm slightly confused by your second part. The Montgomery ladder doesn't need $v$ as input. But assuming that you do have it, you can recover the full point at the end. Otherwise you can't. $\endgroup$ – CurveEnthusiast May 19 '17 at 11:42
  • $\begingroup$ You are correct; I was inaccurate about the inputs to the ladder (in my implementations, I just threw $v$ away). I made some edits to that section; thank you! $\endgroup$ – user47922 May 19 '17 at 12:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.