Succesiuni pseudoaleatoare în criptografie

Succesiuni aleatoare și pseudoaleatoare

O succesiune finită este aleatoare dacă a fost obținută într-un mod care nu permite prevederea apariției elementelor sale. În practică, succesiunile aleatoare se generează determinist printr-un algoritm și se numesc succesiuni pseudoaleatoare.

Cerința fundamentală: cunoașterea mai multor secvențe din șir să nu permită stabilirea legii de generare. Se urmărește obținerea de succesiuni cu perioade lungi de repetiție, testate apoi asupra proprietăților lor aleatoare.

Utilizări ale succesiunilor aleatoare:

Simularea fenomenelor naturale
Generarea cheilor în criptografie
Analiza numerică (metode Monte Carlo)
Selectarea eșantioanelor aleatorii

Metoda congruențial-liniară

O metodă matematică clasică de generare pseudoaleatoare. Șirul {xₙ} se obține prin recurența:

x_{n+1} = (a · xₙ + c) mod m

unde:

m = modulul (m > 0)
a = multiplicatorul (0 ≤ a < m)
c = incrementul (0 ≤ c < m)
x₀ = termenul inițial (0 ≤ x₀ < m)

Condiții pentru perioadă maximă (egală cu m):

(c, m) = 1 (c și m relativ prime)
a ≡ 1 (mod p) pentru orice p prim care divide m

Dacă c = 0, generatorul se numește congruențial multiplicativ, iar a trebuie să fie element primitiv modulo m pentru a obține perioada maximă m - 1.

Registre de deplasare cu reacție liniară (LFSR)

Un LFSR (Linear Feedback Shift Register) este un circuit secvențial format din k celule de memorie cu un circuit de reacție liniară (sumator modulo 2).

Funcționarea este descrisă de relația de recurență liniară:

a_{i+k} = h₁·a_{i+k-1} ⊕ h₂·a_{i+k-2} ⊕ ... ⊕ hₖ·aᵢ

unde hⱼ ∈ {0, 1} definesc conexiunile de reacție.

Polinomul caracteristic

Structura LFSR este determinată de polinomul caracteristic:

h(x) = h₀ + h₁x + h₂x² + ... + hₖxᵏ

cu h₀ ≠ 0 și hₖ = 1.

Perioada de repetiție a succesiunii este cel mai mic n pentru care xⁿ - 1 se divide exact cu h(x).

Perioada maximă: un LFSR cu k celule poate genera o succesiune de perioadă maximă 2ᵏ - 1 (starea nulă trebuie evitată). Aceasta se obține dacă și numai dacă h(x) este polinom primitiv peste GF(2).

Exemplu: LFSR cu 3 celule

Fie un LFSR cu 3 celule și funcția de reacție: ieșirea = Q₃ ⊕ Q₁ (sumator modulo 2 pe celulele 1 și 3).

Polinomul caracteristic: h(x) = 1 + x² = x² + 1 (în notație cu hₖ = 1).

Starea inițială: (Q₁, Q₂, Q₃) = (1, 1, 1).

Evoluția registrului:

Pasul | Q₁  Q₂  Q₃ | Ieșire (Q₃) | Reacție (Q₃⊕Q₁)
  0   |  1   1   1  |      1       |     1⊕1 = 0
  1   |  0   1   1  |      1       |     1⊕0 = 1
  2   |  1   0   1  |      1       |     1⊕1 = 0
  3   |  0   1   0  |      0       |     0⊕0 = 0
  4   |  0   0   1  |      1       |     1⊕0 = 1
  5   |  1   0   0  |      0       |     0⊕1 = 1
  6   |  1   1   0  |      0       |     0⊕1 = 1
  7   |  1   1   1  |      1       |     (revine la starea inițială)

Succesiunea de ieșire: 1 1 1 0 1 0 0, cu perioada 2³ - 1 = 7 (maximă).

Criteriile lui Golomb

Golomb a propus trei criterii necesare (dar nu suficiente) pentru ca o secvență binară periodică să fie considerată „bună" din punct de vedere al aleatorismului:

Echilibrul 0/1: Într-o perioadă, numărul de zerouri și numărul de unu diferă prin cel mult o unitate
Distribuția seriilor: jumătate din serii au lungimea 1, un sfert au lungimea 2, 1/2ᵏ au lungimea k, cu proporții egale de serii de 0 și de 1
Autocorelaţia constantă: funcția de autocorelaţie defazată C(τ) este constantă pentru orice τ ≠ 0:

C(τ) = (A - D) / p

unde A = numărul de coincidențe, D = numărul de neconcordanțe, p = perioada.

Testele de aleatorism

Pe lângă criteriile lui Golomb, se utilizează teste statistice pentru validarea proprietăților aleatoare:

1. Testul de frecvență: verifică dacă n₀ ≈ n₁ prin statistica χ² = (n₀ - n₁)² / n

2. Testul serial: verifică independența biților consecutivi, analizând frecvențele perechilor (00, 01, 10, 11)

3. Testul poker: împarte secvența în blocuri de m biți și verifică distribuția uniformă a celor 2ᵐ combinații posibile

4. Testul de autocorelaţie: calculează A(d) = Σ aᵢ · a_{i+d} pentru diferite deplasări d și verifică slaba corelație

5. Testul spectral: bazat pe transformata Fourier, verifică absența componentelor periodice pronunțate; acceptă toate secvențele validate de celelalte teste

Generatoare neliniare

Pentru securitate sporită, LFSR-urile se completează cu logică neliniară:

Filtrare neliniară: ieșirea LFSR trece printr-o funcție booleană neliniară
Combinare neliniară: mai multe LFSR-uri sunt combinate printr-o funcție neliniară
Complexitate echivalentă: combinarea a r registre cu polinoame primitive de grade r, s, t poate produce complexitate rs + (s+1)t cu perioadă cmmmc(2ʳ-1, 2ˢ-1, 2ᵗ-1)

Puncte cheie pentru examen

Metoda congruențial-liniară: x_{n+1} = (a·xₙ + c) mod m, perioadă maximă m
LFSR: registru cu k celule, reacție liniară, polinom caracteristic h(x)
Perioadă maximă LFSR: 2ᵏ - 1, necesită polinom primitiv
Criteriile Golomb: echilibrul 0/1, distribuția seriilor, autocorelaţie constantă
Cele 5 teste: frecvență, serial, poker, autocorelaţie, spectral
Generatoarele neliniare cresc complexitatea și securitatea
Starea nulă (toate celulele = 0) trebuie evitată la LFSR