2
$\begingroup$

I am trying to learn more about Crystals Kyber. I am playing around with a Java implementation. I am only focussing on Kyber-512 for now, I have locally changed the source code in order to remove the DER PKCS8/X.509 encodings so my public/private keys are simple byte arrays instead of objects, which I succeeded. Everything is still compiling and I can successfully share a secret.

Inside this implementations KyberPrivateKey.java and KyberPublicKey.java classes are 2 large variables p and g, called "prime modulus and base generator", which in his implementation example always seems to be a default value (which is defined in the file KyberParams.java).

I do not understand what this p and g are, I cannot find a reference in their specification about such large prime modulus and base generator. It seems it is only used in this PKCS8/X.509 encodings and seem to work fine without any reference to those variables.

Am I not understanding this correctly? Could someone explain me what those variables are and why they seem not necessary?

Improve this question
$\endgroup$
3
  • $\begingroup$ In the title you denote the base generator with $g$ while in the text you denote it as $q$. Could you specify which is the correct one? $\endgroup$ Commented Sep 6, 2024 at 14:06
  • $\begingroup$ Moreover, without finding a reference through their specification, my best guesses would be: $p$ denotes the modulus (which is prime). You can also find it as $q$ sometimes. This means that the computations of the protocol happen in modular arithmetic with modulus $p$. The base generator $g$ probably denotes the generator of the group that the computations are happening. With a generator, you can "construct" the group using only $g$ and its powers ($g^2,g^3,...$). $\endgroup$ Commented Sep 6, 2024 at 14:20
  • $\begingroup$ That is interesting, but what I do not understand is why I can remove them without breaking the entire algorithm. $\endgroup$ Commented Sep 6, 2024 at 15:06

1 Answer 1

Reset to default
4
$\begingroup$

This is curious.

The prime p=0xfca682ce8e12caba26efccf7110e526db078b05edecbcd1eb4a208f3ae1617ae01f35b91a47e6df63413c5e12ed0899bcd132acd50d99151bdc43ee737592e17 is a 512-bit prime with $p-1=2\times 4243\times 101833\times C_{483}$ where $C_{483}$ is a 482-bit composite.

The number g=0x678471b27a9cf44ee91a49c5147db1a9aaf244f05a434d6486931d2d14271b9e35030b71fd73da179069b32e2935630e1c2062354d0da20a6c416e50be794ca4 is a $C_{483}$ power mod $p$ (and one would guess more precisely a $\ell$th power for some pirme $\ell|C_{483}$). In particular it is not a primitive root (generator for the multiplicative group mod $p$).

These numbers should have no relevance whatsoever to Kyber. My best guess is that they are a legacy stub from where a Diffie-Hellman test params file has been used as a template for a public key parameters file. They should certainly be possible to delete without affecting Kyber functionality. If you are especially concerned, you could email the github owner.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Well that explains why (after rewriting to remove the encodings), I was left over with unused variables p and g. Thanks for the explination for both those numbers and why I do not need them. $\endgroup$ Commented Sep 7, 2024 at 17:23

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.