Crystals-Kyber

Kyber je kriptografski sustav razmjene ključeva i enkripcije koji se temelji na težini rješavanja
problema učenja s greškama (LWE) preko modul rešetki. Osnovna jednadžba glasi B = As + e    mod q
Finalist je NIST-ovog post-kvantnog kriptografskog natječaja.

Uvod

Koristimo neslužbenu implementaciju koju se može preuzeti kao zip datoteku i koja sadrži izvorni kod algoritma. U sklopu projekta, u programskom jeziku Python, napravljeno je sučelje za demonstraciju rada Kyber-a.

Implementacija

Potrebno je raspakirati skinutu zip datoteku, zatim se pozicionirati u /pyky, te dodati datoteku: main.py

Demonstracija

Python program pokreće se iz direktorija u kojemu se nalazi datoteka main.py sljedećom naredbom:

Otvara se prozor:

Pritiskom na dio prozora u kojemu piše "KEY ENCAPSULATION MECHANISM" otvara se sljedeći prozor:

Pritiskom na gumb "Generiraj seed" generiramo seed koji se koristi za kreiranje privatnog i javnog ključa. Pritiskom na gumb "Generiraj par ključeva" generiramo privatni i javni ključ. Pritiskom na gumb "Enkapsuliraj" dobivamo šifru i zajedničku tajnu.

Pritiskom na gumb "Dekapsuliraj - provjeri zajedničku tajnu" provjerava se je li šifra generirana iz javnog ključa valjana za zadani tajni ključ.

Poruka o ispravnosti postupka enkapsulacije prikazuje se u doljnjem prozoru. Pritiskom na gumb olovčice u poljima "Javni ključ", "Privatni ključ" i "Seed" moguće je ručno promijeniti vrijednosti navedenih polja. Ukoliko tajni ključ ne odgovara javnom ključu, enkapsulacija će biti neispravna.

Program se također sastoji i od enkripcije.

Pritiskom na gumb "Generiraj seed" generiramo seed koji se koristi za kreiranje privatnog i javnog ključa. Pritiskom na gumb "Generiraj par ključeva" generiramo privatni i javni ključ. Pritiskom na gumb "Kriptiraj" dobivamo šifru.

Pritiskom na gumb "Dekriptiraj poruku" provodi se dekripcija šifre korištenjem tajnog ključa.

Crystals-Kyber ostvaren je na nekoliko razina sigurnosti. Ovdje su navedeni odgovarajući setovi parametara.

Funkcije enkapsulacije

z ← B32
(pk, sk') := Kyber.CPAPKE.KeyGen()
sk := (sk' ‖ pk ‖ H(pk) ‖ z)
return (pk, sk)

m ← B32
m ← H(m)
(K, r) := G(m ‖ H(pk))
c := Kyber.CPAPKE.Enc(pk, m, r)
K := KDF(K ‖ H(c))
return (c, K)

pk := sk + 12 · k · n/8
h := sk + 24 · k · n/8 + 32 ∈ B32
z := sk + 24 · k · n/8 + 64
m' := Kyber.CPAPKE.Dec(s, (u, v))
(K', r') := G(m' ‖ h)
c' := Kyber.CPAPKE.Enc(pk, m', r')
if c = c' then
return K := KDF(K' ‖ H(c))
else
return K := KDF(z ‖ H(c))
end if
return K

Funkcije enkripcije

d ← B32
(ρ, σ) := G(d)
N := 0
for i from 0 to k - 1 do  
  for j from 0 to k - 1 do
    Â[i][j] := Parse(XOF(ρ, j, i))
  end for
end for
for i from 0 to k - 1 do 
  s[i] := CBDη1(PRF(σ, N ))
  N := N + 1
end for
for i from 0 to k - 1 do  
  e[i] := CBDη1(PRF(σ, N ))
  N := N + 1
end for
ŝ := NTT(s)
ê := NTT(e)
t̂ := Â ◦ ŝ + ê
pk := (Encode12(t̂ mod+q)‖ρ) . pk := As + e
sk := Encode12(ŝ mod+q) . sk := s
return (pk , sk)
                  

N := 0
t̂ := Decode12(pk )
ρ := pk + 12 · k · n/8
for i from 0 to k - 1 do 
  for j from 0 to k - 1 do 
    ÂT [i][j] := Parse(XOF(ρ, i, j))
  end for
end for
for i from 0 to k - 1 do  
  r[i] := CBDη1(PRF(r, N ))
  N := N + 1
end for
for i from 0 to k - 1 do  
  e1[i] := CBDη2 (PRF(r, N ))
  N := N + 1
end for
e2 := CBDη1(PRF(r, N )) 
r̂ := NTT(r)
u := NTT-1(ÂT ◦ r̂) + e1 
v := NTT-1(t̂T ◦ r̂) + e2 + Decompressq(Decode1(m), 1) 
c1 := Encodedu(Compressq(u, du))
c2 := Encodedv(Compressq(v, dv))
return c = (c1 ‖ c2)

u := Decompressq(Decodedu(c), du)
v := Decompressq(Decodedv(c + du · k · n/8), dv)
ŝ := Decode12(sk)
m := Encode1(Compressq(v - NTT-1(ŝT ◦ NTT(u)), 1))
return m

Generiranje ključa

Alice generira matricu A dimenzija n x n nasumičnih koeficijenata,
te dva vektora, s dimenzije K i vektor e, vrlo malih koeficijenata.
Nakon toga računa vektor t također dimenzije K.
Objavljuje javni ključ (A,t) te za sebe ostavlja privatni ključ (s)

Enkripcija poruke

Bob generira nasumični vektor r duljine K te pomoću njega,
javnog ključa dobivenog od Alice, malih error-a e1 i e2 te same poruke m dobiva šifru (u, v).

Računanje v dijela

U ovom koraku t se rastavlja na svoje dijelove A x s + e.
Množenjem svih komponenti s r dobivamo rAs + re.
Imajući na umu da su koeficijenti greški (e, e1, e2) izrazito mali, oni ne pridonose mnogo cjelini.
Onda je r x e vrlo mal i objedinjujemo ga s e2 te i dalje imamo vrlo neznatan vektor. (Na slici žuti bez naziva)
Ono što nam ostaje na kraju je rAs + greška + m