Fundamente matematice ale criptografiei

Un număr natural p > 1 este număr prim dacă are exact doi divizori: 1 și pe el însuși. Conform teoremei fundamentale a aritmeticii, orice număr natural n > 1 se descompune unic ca produs de numere prime.

Mulțimea numerelor prime este infinită (teorema lui Euclid). Distribuția numerelor prime este aproximată de funcția π(x) ≈ x / ln(x).

Tipuri speciale de numere prime:

Numere prime Fermat: de forma 2^(2ⁿ) + 1
Numere prime Mersenne: de forma 2ᵖ - 1, unde p este prim

Algoritmul lui Euclid

Algoritmul lui Euclid determină cel mai mare divizor comun (a, b) prin împărțiri succesive. Algoritmul extins al lui Euclid găsește și coeficienții x, y astfel încât ax + by = (a, b), esențial pentru calculul inverselor modulare.

Funcția Euler φ(n)

Funcția Euler φ(n) reprezintă numărul de întregi pozitivi mai mici sau egali cu n care sunt relativ primi cu n.

Formula generală, pentru n = p₁^α₁ · p₂^α₂ · ... · pₖ^αₖ:

φ(n) = n · (1 - 1/p₁) · (1 - 1/p₂) · ... · (1 - 1/pₖ)

Cazuri particulare:

φ(p) = p - 1 pentru p prim
φ(p^α) = p^α - p^(α-1) pentru p prim

Congruențe

Definiție și proprietăți

Fie n un întreg pozitiv. Spunem că a ≡ b (mod n) dacă n | (a - b).

Relația de congruență este o relație de echivalență (reflexivă, simetrică, tranzitivă). Mulțimea claselor de resturi modulo n se notează Zₙ = {0, 1, ..., n-1} și formează un inel unitar comutativ.

Congruența ax ≡ b (mod m) are soluții dacă și numai dacă (a, m) | b. Dacă (a, m) = 1, soluția este unică.

Teorema lui Euler

Pentru orice a cu (a, n) = 1: a^φ(n) ≡ 1 (mod n).

Aceasta este fundamentul multor algoritmi criptografici, inclusiv RSA.

Teorema lui Fermat (caz particular)

Pentru p prim și (a, p) = 1: a^(p-1) ≡ 1 (mod p).

Teorema chineză a resturilor

Fie m₁, m₂, ..., mₛ întregi cu (mᵢ, mⱼ) = 1 pentru i ≠ j. Sistemul:

x ≡ b₁ (mod m₁)
x ≡ b₂ (mod m₂)
...
x ≡ bₛ (mod mₛ)

are o soluție unică modulo m = m₁ · m₂ · ... · mₛ.

Exemplu: calculul φ(n) și aplicarea teoremei Euler

Fie n = 120 = 2³ · 3 · 5. Calculăm:

φ(120) = 120 · (1 - 1/2) · (1 - 1/3) · (1 - 1/5)
       = 120 · 1/2 · 2/3 · 4/5
       = 32

Aplicăm teorema lui Euler: pentru a = 7 și n = 120, avem (7, 120) = 1, deci:

7^32 ≡ 1 (mod 120)

Aceasta înseamnă că 7^32 împărțit la 120 dă restul 1.

Logaritmul discret

Fie g un element al unui grup finit G și y ∈ G. Un întreg pozitiv x cu proprietatea gˣ = y se numește logaritmul discret al lui y în baza g.

Calculul logaritmului discret este extrem de dificil pentru grupuri mari, în contrast cu exponențierea modulară care este eficientă. Această asimetrie stă la baza securității multor sisteme criptografice (Diffie-Hellman, ElGamal, DSA).

Inele de polinoame

Un polinom f(x) = a₀ + a₁x + ... + aₙxⁿ cu coeficienți într-un inel R aparține inelului de polinoame R[x], care este și el inel comutativ unitar.

Dacă R este inel factorial (cu descompunere unică în factori ireductibili), atunci și R[x] este factorial.

Un polinom este ireductibil dacă nu poate fi scris ca produs de două polinoame de grad mai mic.

Criteriul de ireductibilitate al lui Eisenstein

Fie f = a₀ + a₁x + ... + aₙxⁿ ∈ R[x] și p un element prim din R cu proprietățile:

p | a₀, p | a₁, ..., p | aₙ₋₁

p ∤ aₙ

p² ∤ a₀

Atunci f este ireductibil.

Aplicație: Polinomul f(x) = xᵖ⁻¹ + xᵖ⁻² + ... + x + 1 (pentru p prim) este ireductibil în Q[x], ceea ce se demonstrează aplicând criteriul Eisenstein polinomului f(x+1) cu elementul prim p.

Puncte cheie pentru examen

φ(n) = n · Π(1 - 1/pᵢ) pentru descompunerea n = p₁^α₁ · ... · pₖ^αₖ
Teorema Euler: a^φ(n) ≡ 1 (mod n) pentru (a, n) = 1
Teorema Fermat: a^(p-1) ≡ 1 (mod p) pentru p prim
Teorema chineză a resturilor: soluție unică modulo produs pentru module coprime
Logaritmul discret: gˣ = y - calculul lui x este dificil (baza securității criptografice)
Criteriul Eisenstein: condiții suficiente pentru ireductibilitatea unui polinom
Algoritmul extins Euclid: calculul inverselor modulare

Exemple practice suplimentare

Exemplu 1: Aritmetica modulară

a) Exponențiere modulară — calculul 3⁵ mod 7:

Metoda directă:
3⁵ = 243
243 mod 7 = 243 - 34·7 = 243 - 238 = 5

Metoda pas cu pas (ridicare repetată la pătrat):
3¹ mod 7 = 3
3² mod 7 = 9 mod 7 = 2
3⁴ mod 7 = (3²)² mod 7 = 2² mod 7 = 4
3⁵ = 3⁴ · 3¹ → (4 · 3) mod 7 = 12 mod 7 = 5

b) Inversul modular — găsirea x astfel încât 5x ≡ 1 (mod 11):

Algoritmul Euclid extins:
11 = 2 · 5 + 1
 5 = 5 · 1 + 0

Înapoi:
1 = 11 - 2 · 5
Deci: (-2) · 5 ≡ 1 (mod 11)
-2 mod 11 = 9

Verificare: 5 · 9 = 45 = 4 · 11 + 1  ✓

Inversul lui 5 modulo 11 este 9.

Exemplu 2: Funcția Euler φ(n)

Funcția Euler φ(n) numără câte numere de la 1 la n sunt coprime cu n.

φ(12) = ?

Factorii primi ai lui 12: 12 = 2² · 3

φ(12) = 12 · (1 - 1/2) · (1 - 1/3) = 12 · 1/2 · 2/3 = 4

Verificare: numerele coprime cu 12 din {1,...,12}:
{1, 5, 7, 11} → 4 numere  ✓

Aplicație RSA: pentru n = p·q cu p, q prime:

φ(n) = (p-1)(q-1)

Exemplu: p = 5, q = 11 → n = 55
φ(55) = 4 · 10 = 40

Exemplu 3: Teorema lui Fermat și aplicația în RSA

Mica teoremă a lui Fermat: Dacă p este prim și gcd(a, p) = 1, atunci:

a^(p-1) ≡ 1 (mod p)

Exemplu: a = 3, p = 7:

3⁶ mod 7 = ?
3² = 9 ≡ 2 (mod 7)
3⁴ ≡ 2² = 4 (mod 7)
3⁶ ≡ 4 · 2 = 8 ≡ 1 (mod 7)  ✓

Fundamente matematice ale criptografiei