9
$\begingroup$

See RFC 5931 § 2.2.1 which talks about "finite field cryptography" as opposed to elliptic curve cryptography and it looks like it is describing the Diffie-Hellman protocol. But Diffie-Hellman is not a done over a finite field, so is this some different class of algorithm?

$\endgroup$
1
  • 4
    $\begingroup$ "finite field crypto" = "group based crypto over the integers modulo a prime" (which is a field) $\endgroup$
    – SEJPM
    Apr 3, 2016 at 18:49

2 Answers 2

9
$\begingroup$

"Finite field cryptography" is fancy language for group-based cryptography done over the integers modulo a prime (instantiating a field) to distinguish this more "classic" approach from the new fancier elliptic curve cryptography.

Example:
Finite Field Diffie-Hellman: Diffie-Hellman done in $\mathbb F_p$.

$\endgroup$
6
  • 2
    $\begingroup$ What about the other finite fields? The ones that aren't the integers mod a prime. Do they just not come up? $\endgroup$ Apr 3, 2016 at 23:13
  • 3
    $\begingroup$ @user2357112 The size of a finite field is always of the form $p^n$ where $p$ is a prime and $n$ is a positive integer. This means you can find finite fields of size $5^2 = 25$ and $3^3 = 27$, but you can never find a finite field of size $2 * 13 =26$ because it has two different prime factors. However cryptography has not found a use for all kinds of finite fields. The finite fields which have proven to be useful are those of size $2^n$ and those of size $p$ for some large prime $p$. $\endgroup$
    – kasperd
    Apr 3, 2016 at 23:18
  • $\begingroup$ Note that the term "finite field" excludes elliptic curves because these curves are only groups, not fields. $\endgroup$
    – Nayuki
    Apr 3, 2016 at 23:23
  • 1
    $\begingroup$ @kasperd: Correct. In an elliptic curve, you can only add two points together or take the negation of a point. You can also multiply a point by a scalar, which is merely shorthand for adding a point to itself repeatedly. You can't multiply two points, thus it's not a ring. $\endgroup$
    – Nayuki
    Apr 4, 2016 at 15:55
  • 1
    $\begingroup$ I think @user2357112 question was interesting. What about other finite fields? $\endgroup$ May 29, 2019 at 23:57
3
$\begingroup$

The term "finite field cryptography" exists to distinguish from group-based cryptography. It is true that every field contains two groups, but a group is not necessarily part of a field. Every prime number $p$ has a finite field $\mathbb{Z}_p$, and these prime fields are used in cryptosystems such as RSA and DSA.

The Diffie-Hellman key exchange operates strictly over a group, but it is okay to take field and ignore the unneeded parts, just focusing on doing exponentiation in the multiplicative group. (We can't use the additive group because multiplicative inverses are too easy to compute.)

Elliptic curves are a popular and powerful tool for asymmetric cryptography. These curves are merely groups, not fields - thus they don't fall under the umbrella term "finite field cryptography". You can add two points on a curve or take the additive inverse of a point. You can multiply a point by a scalar number, but this is just shorthand for repeatedly adding a point to itself. Elliptic curves are not fields because you cannot multiply two points together or take the multiplicative inverse of a point.

You could perhaps also look at the "finite" part of the term "finite field cryptography", but I am not aware of any practical cryptographic schemes that use an infinite field (such as unbounded rational numbers). This makes sense, because a finite field means that every value can be encoded in a constant amount of space (such as 256 bits), which is very convenient for practical implementations.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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