1
$\begingroup$

Why are prime numbers important in cryptographic constructs? I am not interested in RSA examples where factorization is the hard problem itself, that makes sense. However wherever I go I encounter prime numbers, especially prime order groups and more specifically safe primes from Discrete Log to ECurves etc. Is it only due to Pohlig-Hellman??

Logic says that any type of modular operation is a kind of trap door function that hides the original information regardless of being modPrime.

$\endgroup$
  • 1
    $\begingroup$ Why it is important may depend exclusively on the details of the particular scheme being considered. In some schemes, it may not be important to use primes for anything. $\endgroup$ – Ella Rose Nov 19 '19 at 0:10
  • 1
    $\begingroup$ @EllaRose with some examples, it make a good answer. $\endgroup$ – DannyNiu Nov 19 '19 at 1:15
1
$\begingroup$

Any finite setting with addition that distributes over multiplication where neither operation loses information—except multiplying by zero—necessarily has a prime characteristic, which is the number of times you can add 1 to itself before you get back 0. Further, the size of any finite field is some power of its characteristic, so the size of any finite field is always a prime power (proof).

Finite fields are useful for polynomial evaluation authenticators like Poly1305 and GHASH—their security as a message authentication code follows from the fact that a polynomial of degree $d$ over a finite field has at most $d$ distinct roots. You could use a ring instead of a field, but then you would need a larger ring to attain the same security because multiplication even by a nonzero value may lose information.

The multiplicative group of certain finite fields—specifically prime fields $\mathbb Z/p\mathbb Z$ when $p$ is large, subject to certain other criteria—seems to be hard to compute discrete logs in. If we used a ring instead like $\mathbb Z/p_1^{e_1} p_2^{e_2} \dotsm p_k^{e_k}\mathbb Z$ for $\gcd\{p_1,p_2,\dotsc,p_k\}=1$, then we could compute discrete logs independently in the $\mathbb Z/p_i\mathbb Z$ and then lift the solutions to the whole ring using a combination of the Chinese remainder theorem and a magic trick called Hensel lifting in an algorithm chronicled by Eric Bach. So the DLOG security of $(\mathbb Z/m\mathbb Z)^\times$ depends on the size of the largest factor of the modulus $m$, and there's no reason to use a modulus with more than one factor. (In principle we could also use finite extension fields like $\operatorname{GF}(2^t)$, but the DLOG security story is pretty well demolished there these days.)

Finite fields also are needed to construct elliptic curves, which provide groups with much better DLOG security than the multiplicative groups of finite fields directly. (‘Elliptic curves’ over composite moduli lead to arithmetic errors eventually (attempts at division by noninvertible elements), an observation which turned out to inspire a state-of-the-art method of factoring, ECM!) Either way you get a group $G$ of size $n$, and as you observed, when $n$ is composite, the cost of Pohlig–Hellman—and also of Lim–Lee active small-subgroup attacks on Diffie–Hellman protocols—is determined by the size of the largest prime factor of $n$.

Generally, in any setting where you have a finite group $G$, the group $G$ decomposes into subgroups of $d$ elements apiece where $d$ divides $n$. And any setting of invertible transformations on a finite set leads to a finite group under composition, so there will necessarily be primes involved in the algebraic structure of the group.


All that said, not all cryptography involves large primes. For example, the polynomial evaluation hash GHASH—used in AES-GCM for message authentication—is defined over $\operatorname{GF}(2^{128})$, but the group structure of $\operatorname{GF}(2^{128})^\times$ is not relevant to its security so the only prime that's ‘really’ involved (whatever that might mean in math!) is 2. Code-based cryptosystems like McEliece public-key encryption and CFS public-key signature don't involve any group structures and are usually defined over binary Goppa codes, so, again, the prime 2 is involved, but other primes, maybe not so much.

|improve this answer|||||
$\endgroup$

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.