0
$\begingroup$

I wonder if someone can give an explain about the different between two Diffie-Hellman Primitives defined in SP800-56A, CH5.7.1

5.7.1.1 Finite Field Cryptography Diffie-Hellman (FFC DH) Primitive 5.7.1.2 Elliptic Curve Cryptography Cofactor Diffie-Hellman (ECC CDH) Primitive

Actually the first one is named as (FFC DH) and its looked very similar to RSA way. And for the 2nd one , though it is based on ECC, but is also on a Finite Field.

$\endgroup$
2
$\begingroup$

A group if a set of elements and some operation that satisfy some requirements. This operation is usually called "addition" or "multiplication", depending on the group, even though it may not be actually the classic addition or multiplication. The integers $0 < x < p$ for some prime $p$ form a group under the modular multiplication operation (multiply the integers, then compute the remainder of the division by $p$). This group can be denoted by $\mathbb{Z}_p^*$.

A field is a set of elements with two operations that satisfy some requirements; you can think about it as consisting of two groups (one for each operation). The integers $0 <= x < p$ for some prime $p$ form a field under modular addition and multiplication. This field can be denoted by $\mathbb{F}_p$.

That is the field that is used by FFC DH. However, note that DH only requires a group, and not a field. FFC DH uses the multiplicative group of the finite field, i.e. $\mathbb{Z}_p^*$; the addition operation is never used.

An elliptic curve is a set of $(x, y)$ coordinates ("points") that satisfy some equation. In cryptography, these coordinates are elements of a finite field, e.g. $\mathbb{F}_p$. The curve also forms a group under the "point addition" operation, which takes two pair of points and return a third point also on the curve. Note that a curve forms a group, and uses an underlying field, but it's not a field itself.

(A curve has a "point multiplication" operation, but that's not a group operation between points, it's simply repeated addition, like exponentiation in $\mathbb{F}_p$ is just repeated multiplication).

$\endgroup$
  • 1
    $\begingroup$ That's a much better answer than mine. Nit: the second operation in a field doesn't quite form a group (because the identity element for the first operation doesn't have to have an inverse). $\endgroup$ – Martin Bonner Jun 6 at 13:53
  • $\begingroup$ @MartinBonner Thank you all--OK now I get some more insight, need find a text-book to study a while about Field and Group concept.. $\endgroup$ – LeonMSH Jun 6 at 16:32
0
$\begingroup$

A "field" in mathematics is a set (like {0,1,2}, or the set of all integers), and a pair of operations which satisfy some rules. A finite field is a field where the set has a finite number of members (so not "all integers").

Diffie-Hellman is a fairly general protocol that works on many (but not all) finite fields. The difference in the primitives is the fields they are defined over. The first uses the set of integers modulo some prime, with the operations being normal addition and multiplication. The second uses the set of points on an elliptic curve with the operations being "point addition" and "multiplication" (which mean rather different things on an elliptic curve).

$\endgroup$
  • $\begingroup$ Thanks for the reply. So I got some points, ECC CDH is utilizing the points on elliptic curve but all these points must be integer so they will be also on a "Finite Field", correct? $\endgroup$ – LeonMSH Jun 6 at 9:51
  • $\begingroup$ @LeonMSH The points on an elliptic curve form a field. If you only consider the points with integer coordinates, there are only finitely many of them, so it's a finite field. $\endgroup$ – Martin Bonner Jun 6 at 9:56
  • $\begingroup$ Thanks a lot! A ECC CDH could be based on an elliptic curve (for exp, secp256r1). But for this 1st term "FFC DH". My understanding there are plenty of "Finite Field" from mathematical point-of-view, so user is free to select what Finite Field they want, correct? @ $\endgroup$ – LeonMSH Jun 6 at 10:25
  • 1
    $\begingroup$ @LeonMSH The elliptic curve coordinates are in a finite field. The points themselves form a group, not a field. $\endgroup$ – Conrado Jun 6 at 11:50
  • $\begingroup$ @Leon : They can select whatever group they want, but DH will only offer any security if the "discrete log problem" in this group is hard. (Discrete log problem: given $$g^x$$ for some know $$g$$, find $$x$$, where exponentiation is defined as "repeatedly performing the operation on $$g$$ $$x$$ times" - so for EC, it is actually "repeatedly add $$g$$ to the point at infinity", or "multiply $$g$$ by $$x$$). $\endgroup$ – Martin Bonner Jun 6 at 20:19

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.