Metode de cifrare pe câmpuri Galois

Câmpuri Galois GF(q) cu q = pⁿ

Un câmp Galois GF(q) cu q = pⁿ (unde p este prim) conține q elemente și se construiește cu ajutorul unui polinom primitiv f(t) de grad n peste GF(p).

Fiecare element x ∈ GF(q) admite două reprezentări:

Reprezentarea polinomială: x = c₀t^(n-1) + c₁t^(n-2) + ... + c_{n-2}t + c_{n-1}, cu 0 ≤ cᵢ < p

Reprezentarea exponențială: x = tᵏ pentru 1 ≤ k ≤ q-1, plus elementul 0

unde t este elementul primitiv al câmpului (satisface t^(q-1) = 1 și q-1 este cel mai mic exponent cu această proprietate).

Fiecărui element i se asociază o valoare numerică:

f(x) = c₀ · p^(n-1) + c₁ · p^(n-2) + ... + c_{n-1}

cu 0 ≤ f(x) ≤ q - 1.

Operații:

Adunare/scădere: se folosește reprezentarea polinomială (componentă cu componentă, modulo p)
Înmulțire/împărțire: se folosește reprezentarea exponențială (tᵏ · tᵐ = t^(k+m mod (q-1)))

Funcții de permutare

Un polinom f(x) = a₀xⁿ + a₁x^(n-1) + ... + aₙ cu coeficienți în GF(q) este polinom de permutare dacă imaginile f(x₁), f(x₂), ..., f(xq) ale tuturor elementelor câmpului formează o permutare a acestor elemente.

Cel mai simplu exemplu: f(x) = ax + b cu a ≠ 0 realizează o substituție simplă, unde a și b sunt elementele cheii de cifrare.

Schema generală de cifrare:

Fiecărei litere λ i se asociază valoarea numerică x
Se calculează f(x), care corespunde literei cifrate μ
Descifrarea: x = f⁻¹(y) folosind funcția inversă

Metoda N = pⁿ (cifrare cu recurență pe parametri)

Când numărul de litere ale alfabetului N poate fi scris ca pⁿ, se asociază câmpul GF(pⁿ) și se folosește polinomul de permutare:

yᵢ = aᵢ · xᵢ + bᵢ,   cu aᵢ ≠ 0

Parametrii aᵢ și bᵢ variază de la o literă la alta conform unor reguli de recurență, de exemplu:

a_{i+2} = a_{i+1} + aᵢ
b_{i+2} = b_{i+1} + bᵢ

cu valori inițiale a₁, a₂, b₁, b₂ stabilite.

Exemplu: cifrarea cuvântului SECRET pe GF(3³)

Fie GF(3³) cu N = 27 (cele 26 litere + spațiu). Polinomul primitiv: f(t) = t³ + 2t + 1.

Asocierea literelor: A=0, B=1, C=2, ..., Z=25, spațiu=26.

Parametrii inițiali:

a₁ = (0,2,1) = t¹⁶,  a₂ = (1,1,1) = t⁶
b₁ = (0,0,2) = t¹³,  b₂ = (1,1,0) = t¹⁰

Recurența: a_{i+2} = a_{i+1} + aᵢ și b_{i+2} = b_{i+1} + bᵢ (operații pe GF(3³)).

Cifrarea fiecărei litere yᵢ = aᵢ · xᵢ + bᵢ:

Text clar:          S    E    C    R    E    T
Valori numerice:    19   5    3    18   5    20
Repr. polinomială:  (2,0,1) (0,1,2) (0,1,0) (2,0,0) (0,1,2) (2,0,2)
Repr. exponenț.:    t²⁵  t³   t¹   t¹⁵  t²⁵  t⁸

Cifrare yᵢ = aᵢ·xᵢ + bᵢ:
y₁ = t¹⁶·t²⁵ + t¹³ = t⁴¹ + t¹³ = t¹⁵ + t¹³ → (0,0,2) → f = 2   → C?
...
(calcul complet prin operații pe GF(3³))

Valori numerice cifrate: 20  16  26  18  24  17
Criptograma:             T   P   Z   R   S   Q

Descifrarea: xᵢ = aᵢ⁻¹ · (yᵢ - bᵢ).

Metoda N = pⁿ + 1 (metoda Carmichael)

Când N = pⁿ + 1, Carmichael a propus utilizarea unei funcții raționale de permutare:

R(xᵢ) = yᵢ = (aᵢ · xᵢ + bᵢ) / (cᵢ · xᵢ + dᵢ)

cu condiția aᵢ · dᵢ - bᵢ · cᵢ ≠ 0 și aᵢ, bᵢ, cᵢ, dᵢ ∈ GF(pⁿ).

Se introduce un simbol suplimentar ∞ pentru a gestiona cazul cᵢ · xᵢ + dᵢ = 0:

R(∞) = aᵢ/cᵢ dacă cᵢ ≠ 0
R(-dᵢ/cᵢ) = ∞

Parametrii aᵢ, bᵢ, cᵢ, dᵢ se organizează în matrice Mᵢ cu reguli de recurență matriceale:

M_{i+2} = Mᵢ · M_{i+1}

Descifrarea: xᵢ = (dᵢ · yᵢ - bᵢ) / (-cᵢ · yᵢ + aᵢ).

Cifrarea poligrafică

Metoda se extinde la cifrarea simultană a mai multor litere (n-grame). Dacă alfabetul L are l litere și se cifrează câte n simultan:

Numărul total de n-grame: N = lⁿ
N se descompune: N = N₁ + N₂ + ... + Nₖ, cu Nᵢ = pᵢ^mᵢ sau Nᵢ = pᵢ^mᵢ + 1
Se creează k subalfabete, fiecare asociat unui câmp Galois și unei funcții de permutare distincte

Această abordare crește semnificativ complexitatea criptanalizei.

Puncte cheie pentru examen

GF(pⁿ) are pⁿ elemente; două reprezentări: polinomială (adunare) și exponențială (înmulțire)
Elementul primitiv t: t^(q-1) = 1, generează toate elementele nenule
Polinom de permutare: imaginile formează o permutare a elementelor câmpului
Metoda N = pⁿ: cifrare yᵢ = aᵢ·xᵢ + bᵢ cu recurență pe parametri
Metoda N = pⁿ + 1 (Carmichael): funcție rațională R(x) = (ax+b)/(cx+d) cu simbolul ∞
Cifrare poligrafică: cifrare simultană a n-grame, descompunere în subalfabete
Descifrarea se face cu funcția inversă a funcției de permutare
Exemplu GF(3³): cuvântul SECRET se cifrează ca TPZRSQ

Exemple practice suplimentare

Exemplu 1: Cifrul Caesar (substitut monoalfabetic)

Cifrul Caesar deplasează fiecare literă cu o valoare fixă k în alfabet.

Cifrare cu k = 3 (A → D, B → E, …):

Text clar:    S E C U R I T A T E
Deplasare:    +3 pentru fiecare literă
Text cifrat:  V H F X U L W D W H

Spargere: Doar 25 de chei posibile (încercare exhaustivă trivială).

Exemplu 2: Cifrul Vigenère (substitut polialfabetic)

Cheia: CHEIE, mesajul: SECURITATE.

Text clar:    S  E  C  U  R  I  T  A  T  E
Cheie rep.:   C  H  E  I  E  C  H  E  I  E
─────────────────────────────────────────────
Calcul:       (18+2) (4+7) (2+4) (20+8) (17+4)  ...
              mod 26  mod 26  ...
Text cifrat:  U  L  G  C  V  K  A  E  B  I

Pas detaliat (prima literă):

S = 18, C = 2
(18 + 2) mod 26 = 20 = U

Diferența față de Caesar: Aceeași literă din text clar (T apare de 2 ori) se cifrează diferit (A și B), deoarece cheia variază.

Exemplu 3: LFSR - Registru de deplasare cu reacție liniară

Un LFSR de 4 biți cu polinomul de feedback f(x) = x⁴ + x + 1 și starea inițială (1, 0, 0, 0):

Stare: (s₃, s₂, s₁, s₀)
Feedback: s₃ ⊕ s₀ → nou s₃

Pas   Stare        Ieșire (s₀)
───   ──────────   ──────
 0    1 0 0 0      0
 1    1 1 0 0      0
 2    1 1 1 0      0
 3    1 1 1 1      1
 4    0 1 1 1      1
 5    1 0 1 1      1
 6    0 1 0 1      1
 7    1 0 1 0      0
 8    1 1 0 1      1
 9    0 1 1 0      0
10    0 0 1 1      1
11    1 0 0 1      1
12    0 1 0 0      0
13    0 0 1 0      0
14    0 0 0 1      1
15    1 0 0 0      ← revine la starea inițială

Secvența de ieșire: 000111101011001 (perioadă 15 = 2⁴ - 1, maximă).

Proprietăți verificate:

Perioadă maximă: 2⁴ - 1 = 15 ✓ (polinomul este primitiv)
Nr. de 1: 8, Nr. de 0: 7 → diferență de exact 1 ✓ (proprietatea de echilibru)

Metode de cifrare pe câmpuri Galois