2
$\begingroup$

I have some difficulties to understand why we are using finite fields in cryptography.

Why do we use field? Why not ring or group? Is that really necessary that the field is finite? Why not real field?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

One does not always use finite fields in cryptography. RSA for instance is based on residue class rings, discrete logartihm based cryptosystems work on suitable additive/multiplicative groups but these are also finite rings/groups.

Why one uses finite algebraic structures and not the field of the reals?

  • Elements of the field of the reals do not necessarily have a finite representation and thus cannot be represented on computers precisely (only approximations as floating point numbers of a certain precision). Consequently, field operations may only yield approximations of the resulting element. Working with such fields would introduce errors in the arithmetic operations, which we do not want in cryptography. Using finite fields allow to represent all elements precisely and also the output of any arithmetic operation in the field.

  • Furthermore, finite structures used in cryptography provide us with hard problems useful for constructing cryptographic protocols, such as the hardness of the discrete logarithm problem over suitable finite fields. Logarithms over the reals in contrast are easy to compute.

Improve this answer
$\endgroup$
1
$\begingroup$

Also, encrytion algorithms require inverses. Some of the other possible structures do not alwyas have inverses and so decryption is an issue. They could be used in hashing functions however or where only forward encryption is used as in some block chaining modes.

Improve this answer
$\endgroup$
1
  • $\begingroup$ It is the other way around: In continous structures, there are no "hard to inverse" problems, as far as I know. In the mathematical sense, there "is no inverse" if either it does not exist or the inverse is not unique. But this is something else than "you cant compute the inverse". And then there is the fact, that we usually deal with discrete elements e.g. 0 and 1. $\endgroup$
    – tylo
    Commented Jan 12, 2015 at 14:16

Your Answer

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

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