Some CRYSTALS-Kyber calculations
From Based on specs published in NIST FIPS 203 https://doi.org/10.6028/NIST.FIPS.203

Math 302 Cryptography
March 31, 2025

T. Ratliff, Wheaton College
ratliff_thomas@wheatoncollege.edu

Some functions
Recall we are working with vectors and matrices with coefficients in (Subscript[R, q])= (Subscript[ℤ, q])[x]/((x^n)+1)

(* Generate a random element of (Subscript[R, q]) *)
randomRq := x^(Range[n]-1).RandomInteger[{0,q-1},n]  
(* Generate a random element of (Subscript[R, q]) with coefficients in [0, 2η] *)
randomSmallRq :=x^(Range[n]-1).RandomInteger[{0,2*η},n] 

(* Simplify an element of (Subscript[R, q]) *)
rqReduce[exp_]:=PolynomialRemainder[exp,x^n+1, x, Modulus-> q]
(* Simplify a vector with entries in (Subscript[R, q]) *)
rqVecReduce[vec_]:=MapAt[PolynomialRemainder[#,x^n+1, x, Modulus-> q]&,vec, {All}]

(* Generate a random kx1 vector with entries in (Subscript[R, q]) *)
randomRqkvec := Table[randomRq, {i,1,k}]
(* Generate a random kx1 vector with entries in (Subscript[R, q]) whose coefficients are small *)
randomSmallRqkvec := Table[randomSmallRq, {i,1,k}]

(* Needed for encryption.
Converts a list m of 0's and 1's of length n to a value in (Subscript[R, q]) 
with coefficients equal to (q+1)/2 or 0, depending if entry in m is 1 or 0.
*)
mod2ToRq[m_]:=Expand[(x^(Range[n]-1).m)*(q+1)/2 ];

(* Needed for decryption: 
Takes an element of (Subscript[R, q]), 
  converts the coefficients to 1 or 0 (depending if closer to (q+1)/2 or 0 mdo q),
  and returns the values as a list.  *)
rqToMod2[poly_]:=Module[ {coeffs,mod2coeffs},
coeffs= CoefficientList[poly,x,n]; 
mod2coeffs =Floor[ Mod[coeffs + Floor[q/4],q]/ ( (q+1)/2)];
Return[ CoefficientList[x^{Range[n]-1}.mod2coeffs,x,n][[1]]]
]

Set parameters cf. Section 8 of FIPS 203

q=3329;  (* modulus for (Subscript[ℤ, q]) : q=3329 in specs *)
n=4;  (* exponent for (x^n) + 1 : n=256 in specs *) 
k = 2;  (* a is k x k matrix *)
η=2; (* η is the center of distribution for coefficients in small vectors
     I'm using the same value for the parameters (Subscript[η, 1]) and (Subscript[η, 2]) in the specs*)

Generate the private key s and public key (a,t)

a =Table[ randomRq , {i,1,k},{j,1,k}]

We still need to do a little more work to generate the private key s and the vector t that is part of the public key

Encrypt a message m that is an n-bit number

m=RandomInteger[{2^(n-1),2^n-1}]
mDigits=IntegerDigits[m,2]
mRq = mod2ToRq[mDigits]

We still need to do some work to encrypt

Now decrypt! 
You’ll need to use the rqToMod2[ ] and FromDigits[ ] functions at the end