Stojan Dimitrovski

2018-03-20 20:55:05 UTC

Hi all,

I have a few questions regarding RFC 8235 over EC, specifically Curve 25519.

I wrote a simple implementation to prove that the protocol does work

(duh, of course it does). However, in the process of which I had to

modify libsodium to do scalar multiplication over Ed25519 without

clamping.

This was done specifically when calculating `G x [r]` since the scalar

`r` comes out of a computation.

Now, I'm not an expert at EC mathematics, but as far as I can tell

clamping on scalars is done to make sure that the scalar is always a

multiple of the subgroup's cofactor (`h = 8` for Ed25519).

Now, I am curious to know how I can avoid accidentally placing `r` in

an unfortunate subgroup, but to avoid clamping?

Would this be enough:

`r = h * (v - a * c) mod n`

or ... by knowing that since `v` is already "clamped" i.e. `v`, `a`,

and `c` are already multiples of `h`, it goes by definition that the

value `r` cannot be in an unfortunate subgroup?

Another question I have is: do you see any relevance in the _hinting_

of the RFC to use subgroups with a small cofactor (1, 2, 4) contrasted

with the cofactor 8 of Curve 25519?

Thanks!

For brevity, I paste the RFC 8235 protocol over ECs here:

In the setup of the scheme, Alice publishes her public key

A = G x [a], where a is the private key chosen uniformly at random

from [1, n-1].

The protocol works in three passes:

1. Alice chooses a number v uniformly at random from [1, n-1] and

computes V = G x [v]. She sends V to Bob.

2. Bob chooses a challenge c uniformly at random from [0, 2^t-1],

where t is the bit length of the challenge (say, t = 80). Bob

sends c to Alice.

3. Alice computes r = v - a * c mod n and sends it to Bob.

At the end of the protocol, Bob performs the following checks. If

any check fails, the verification is unsuccessful.

1. To verify A is a valid point on the curve and A x [h] is not the

point at infinity;

2. To verify V = G x [r] + A x [c].

The first check ensures that A is a valid public key, hence the

discrete logarithm of A with respect to the base G actually exists.

Unlike in the DSA-like group setting where a full modular

exponentiation is required to validate a public key, in the ECDSA-

like setting, the public key validation incurs almost negligible cost

due to the cofactor being small (e.g., 1, 2, or 4).

I have a few questions regarding RFC 8235 over EC, specifically Curve 25519.

I wrote a simple implementation to prove that the protocol does work

(duh, of course it does). However, in the process of which I had to

modify libsodium to do scalar multiplication over Ed25519 without

clamping.

This was done specifically when calculating `G x [r]` since the scalar

`r` comes out of a computation.

Now, I'm not an expert at EC mathematics, but as far as I can tell

clamping on scalars is done to make sure that the scalar is always a

multiple of the subgroup's cofactor (`h = 8` for Ed25519).

Now, I am curious to know how I can avoid accidentally placing `r` in

an unfortunate subgroup, but to avoid clamping?

Would this be enough:

`r = h * (v - a * c) mod n`

or ... by knowing that since `v` is already "clamped" i.e. `v`, `a`,

and `c` are already multiples of `h`, it goes by definition that the

value `r` cannot be in an unfortunate subgroup?

Another question I have is: do you see any relevance in the _hinting_

of the RFC to use subgroups with a small cofactor (1, 2, 4) contrasted

with the cofactor 8 of Curve 25519?

Thanks!

For brevity, I paste the RFC 8235 protocol over ECs here:

In the setup of the scheme, Alice publishes her public key

A = G x [a], where a is the private key chosen uniformly at random

from [1, n-1].

The protocol works in three passes:

1. Alice chooses a number v uniformly at random from [1, n-1] and

computes V = G x [v]. She sends V to Bob.

2. Bob chooses a challenge c uniformly at random from [0, 2^t-1],

where t is the bit length of the challenge (say, t = 80). Bob

sends c to Alice.

3. Alice computes r = v - a * c mod n and sends it to Bob.

At the end of the protocol, Bob performs the following checks. If

any check fails, the verification is unsuccessful.

1. To verify A is a valid point on the curve and A x [h] is not the

point at infinity;

2. To verify V = G x [r] + A x [c].

The first check ensures that A is a valid public key, hence the

discrete logarithm of A with respect to the base G actually exists.

Unlike in the DSA-like group setting where a full modular

exponentiation is required to validate a public key, in the ECDSA-

like setting, the public key validation incurs almost negligible cost

due to the cofactor being small (e.g., 1, 2, or 4).

--

Stojan Dimitrovski

http://stojan.me

Stojan Dimitrovski

http://stojan.me