RaSol: November 2005

Tuesday, November 29, 2005

Memento teoria numerelor

divizibilitate: d|n, d divide n (d este un divizor al lui n, d este un factor al lui n, n este un multiplu al lui d), d, n ∈ Z ⇔ ∃ k ∈ Z ai n = d * k
teorema impartirii: a ∈ Z, b ∈ Z^* at ∃ q, r ∈ Z, unici, ai a = b * q + r si 0 ≦ r < b; a ∈ Z, b ≠ 0 at ∃ q, r ∈ Z, unici, ai a = b * q + r si 0 ≦ r < | b |
modulo: a mod b = { b / a ∈ Z, b ∈ Z^*, a = b * q + r }
cmmdc: cmmdc(a, b) ⇔ a, b ∈ Z^*, D = {d | d|a ∧ d|b}, cmmdc(a, b) = sup D
proprietati: ∀ a, b ∈ Z^*, ∃ cmmdc(a, b) si 0 < cmmdc(a, b) ≦ min ( | a |, | b |)
∀ a ∈ Z^* at cmmmdc(a, 0) = 0
∀ a, b ∈ Z⁺, cmmdc(a, b) = cmmdc (b, r) unde a = b * q +r
Lema Bezout: ∀ a, b ∈ Z ∃ s, t ai cmmdc(a, b) = s * a + t * b
numar prim: p ∈ Z, p ≧ 2, se numeste prim ⇔ D = { d / d | p} contine numai pe 1 si pe p (altfel se numeste numar compozit)
T: n ∈ Z⁺ este compozit ⇔ ∃ a, b , 1 < a < n, 1 < b < n ai n = a * b
∀ n > 1, ∃ p, un numar prim, ai p | n
(Euclid) exista un numar infinit de numere prime
daca n > 1, este un numar compozit at. ∃ p, un numar prim, ai p | n si p ≦ n^1/2
π ( x ): reprezinta cardinalul multimiii numerelor prime mai mici decat x ∈ R⁺
T: π ( x ) ~ x / ln ( x ), x ∈ R⁺
Teorema fundamentala a aritmeticii (descompunerea in factori primi): ∀ n intreg, n > 1, poate fi scris sub forma n = p₁p₂...p_s unde s este un intreg pozitiv si p₁p₂...p_s sunt prime ce satisfac relatia p₁≦p₂≦...≦p_s
descompunerea in factori primi exista si este unica
daca a si b sunt doua numere supraunitare cu descompunerile in factori primi a = p₁^a₁p₂^a₂...p_k^a_k si b = p₁^b₁p₂^b₂...p_k^b_k at. cmmdc( a , b ) = p₁^{min ( a₁ , b₁ )}p₂^{min ( a₂ , b₂ )}...p_k^{min ( a_k , b_k )}
numere relativ prime: a, b sunt relativ prime ⇔ cmmdc ( a , b ) = 1
T: fie a > 1 si n > 1
aⁿ-1 este prim ⇒ a = 2 si n este prim
aⁿ+1 este prim ⇒ a este impar si ∃ k > 1 ai n = 2^k
numere Mersenne: Daca un numar este de forma M_n = 2ⁿ-1 se numeste numar Mersenne. Daca M_n este prim se numeste prim Mersenne
numere Fermat: Daca un numar este de forma F_n = 2^2ⁿ-1 se numeste numar Fermat. Daca F_n este prim se numeste prim Fermat
T: Daca M_n este prim at. n este prim
(Lucas-Lehmer)
functiile σ si τ: fie n > 0; se noteaza
τ ( n ) cardinalul multimii formate de divizorii pozitiv ai lui n
σ ( n ) suma divizorilor pozitiv ai lui n
T: fie descompunerea in factori a lui n = p₁^e₁p₂^e₂...p_r^e_r unde r ≧ 1 , p₁≦p₂≦...≦p_r sunt prime si e_i ≧ 0, ∀ i ∈ { 1 , 2, ... , r }. At.
τ ( n ) = ( e₁ + 1 )( e₂ + 1 ) ... ( e_r + 1 )
σ ( n ) = ( p₁^{e₁ + 1} - 1 ) / ( p₁ - 1) ( p₂^{e₂ + 1} - 1 ) / ( p₂ - 1) ... ( p_r^{e_r + 1} - 1 ) / ( p_r - 1)
numere perfecte: se noteaza σ^*( n ) suma divizorilor pozitivi mai mici ca n, ai lui n
ptr n ≧ 2, σ^*( n ) = σ( n ) -n
un numar este perfect daca σ^*( n ) = n
congruente: a congruent cu b modulo m
a ≡ b (mod m) ⇔ ptr m ≧ 0, m | a - b

m > 0, ∀ a, b : a ≡ b (mod m) ⇔ a mod m = b mod m ptr m ≧

proprietati relatie congruenta
(reflexivitate) a ≡ a ( mod m)
(simetrie) a ≡ b (mod m) ⇒ b ≡ a (mod m)
(tranzitivitate) a ≡ b (mod m) si b ≡ c (mod m) ⇒ a ≡ c (mod m)

element invers
daca cmmdc( a , m ) = 1 at ∃ a', 0 < a' < m , unic, ai aa' ≡ (mod m)

T operatii
a ≡ b ( mod m) si a ≡ b ( mod m) ⇒
a ± b ≡ c ± d ( mod m)
ac ≡ bd ( mod m)
aⁿ ≡ bⁿ ( mod m ) ∀ n ≧ 1
f ( a ) ≡ f ( b ) , ∀ f ( x) , polinom cu coeficienti intregi

T
ptr c > 0 , m > 0 : a ≡ b ( mod m) ⇔ ca ≡ cb ( mod cm)
ptr. m > 0 si d = cmmdc ( c , m) : ca ≡ cb ( mod m) ⇒ a ≡ b ( mod m/d)
m > 0 , a ≡ b ( mod m) ⇒ cmmdc ( a, m) = cmmdc ( b , m)
clase de resturi: clasa de resturi a modulo m
pt. m > o fixat si ptr a intreg se defineste [a] = { x / x ≡ a ( mod m) }
ptr. m > 0: [ a ] = { mq + a / q ∈ Z }
ptr. m > 0 : [ a ] = [ b ] ⇔ a ≡ b ( mod m)
ptr. m > 0, ∀ a, ∃ r, 0 ≦ r < m, unic, ai [ a ] = [ r ]
ptr. m > 0 sunt exact m clase distincte de resturi, [ 0 ] , [ 1 ] , ... , [ m - 1 ]
sisteme de resturi: m > 0
inelul intregilor modulo m
Z_m = { [ a ] / a ∈ Z}
sistem complet de resturi modulo m
multimea de intregi { a₁ , a₂ , ... , a_m } se numeste sistem complet de resturi modulo m daca Z_m = { [ a₁ ] , [ a₂ ] , ... , [ a_m ] }
daca m = 2k at. {0, 1, 2, ..., k-1, k, -(k-1), ..., -2, -1} este un sistem complet de resturi modulo m
daca m = 2k + 1 at. {0, 1, 2, ..., k, -k, ..., -2, -1} este un sistem complet de resturi modulo m
adunarea si inmultirea in Z_m
fie [ a ], [ b ] ∈ Z_m, se definesc: [ a ] + [ b ] = [ a + b } si [ a ][ b ] = [ ab ]
J_m = {0, 1, ... m - 1} cu operatiile a ⊕ b = ( a + b) mod m si a ⊙ b = ( ab ) mod m formeaza un inel izomorf cu Z_m
o clasa de resturi [ a ] ∈ Z_m este unitara daca nu este inversabila ⇔ cmmdc ( a , m) = 1
grupul unitatilor
U_m = { [ i ] / 1 ≦ i ≦ m si cmmmdc( i , m) = 1} impreuna cu inmultirea (din Z_m) formeaza un grup abelian
daca p este prim, at. ∃ a ∈ U_p ai U_p = <a>
daca n ≧ 2 , at. ∃ a ∈ U_p ai U_p = <a> ⇔ a este de froma 2, 4, p^k, 2 p ^k unde p ≧ 2, p este prim si k ∈ N
functia φ Euler
ordinul lui U_m
proprietati φ Euler
ptr. a > 0, b > 0 si cmmdc ( a , b ) = 1 : φ( ab ) = φ( a )φ( b )
ptr. p, prim, si n > 0 : φ( pⁿ ) = pⁿ - p^n-1
ptr. p₁, p₂, ..., p_k, prime distincte, si n₁, n₂, ..., n_k, intregi pozitivi : φ(p₁^n₁ p₂^n₂ ... p_k^n_k) = ( p₁^n₁ - p₁^n₁-1 ) ... ( p_k^n_k - p_k^n_k-1 )
T
fie a, b ∈ Z⁺, cmmdc( a , b ) = 1 si n = ab. Se defineste f ( [ x ]_n ) = ( [ x ]_a , [ x ]_b )
(teorema chineza a resturilor) f : Z_n → Z_a x Z_b este bijectiva
f : U_n → U_a x U_b este bijectiva
teste primalitate: mica teorma a lui Fermat
daca p este prim si a, cmmdc( a , p) = 1 at. a^p-1 ≡ 1 ( mod p)
teorema lui Euler
ptr. m > 0 si a, cmmdc( a , m ) = 1 : a^φ(m) ≡ 1 ( mod m )
a^p ≡ a ( mod p), ∀ a si p prim
ptr. m ≧ 2, ∀ a, 1 ≦ a ≦ m -1, a^m-1 ≡ 1 ( mod m) ⇒ m prim
reprezentarea lui n in baza b
ptr. b ≧ 2, n > 0 , n = [a_k, a_k-1, ..., a₁, a₀]_b este reprezentarea in baza b a lui n ⇔ ∃ k ≧ 0 ai n = a_kb^k + a_k-1b^k-1 + ... + a₁b + a₀ unde a_i ∈ {0, 1, ..., b-1}, i ∈ {0, 1, ..., k}
reprezentarea este unica
metoda binara pentru calculul lui xⁿ, x ∈ R, n ∈ Z⁺
se gaseste reprezentarea binara n = [ a_r , ... , a₁ ,a₀ ]₂
se calculeaza puterile x² , x^2² , ... , x^{2^r}
se calculeaza produsul xⁿ = x^{a_r2^r} x^{a_r-12^r-1} x^a₁2 x^a₀
metoda binara pentru calculul lui xⁿ ( mod m) , x ∈ R, n ∈ Z⁺
se gaseste reprezentarea binara n = [ a_r , ... , a₁ ,a₀ ]₂
se calculeaza redusele modulo m ale puterilor x² , x^2² , ... , x^{2^r} , m₁ = x² mod m , m₂ = x^2² mod m , ... , m_r = x^{2^r} mod m
se calculeaza produsul xⁿ mod m = m_rm_r-1 ... m₁ m₀

Introducere in teoria numerelor, Edwin Clark

# posted by Sorin Badescu @ 1:54 PM 1 comments

Monday, November 28, 2005

Functii cu trapa

functie cu trapa: f : N → R este o functie cu trapa ⇔
f este o functie cu sens unic
∃ p, o functie polinomiala, si ∃ A, un algoritm PTP ai
∀ k, ∃ t_k ∈ {0, 1}^* cu | t_k | ≦ p ( k )
∀ x ∈ {0, 1}^*, A( f ( x) , t_k) = y ai f ( y ) = f ( x)
familie de functii puternice cu trapa si cu sens unic: F = { f_i : D_i → D_i }_i∈I, unde i ∈ I, ,multimea indicilor, este o familie de functii puternice cu trapa si cu sens unic daca:
∃ S₁, o MTP, si p, o functie polinomiala, ai ( i , t_i ) ← S₁ ( x ∈ {0, 1}^k ), i ∈ {0, 1}^k ∩ I si | t_i | < p ( k ); t_i se numeste trapa pentru i
∃ S₂, o MTP, ai x ← S₂ ( i ∈ I ), x∈ D_i
∃ A₁, o MTP, ai A₁ ( i , x ) = f_i( x ), unde i ∈ I, x ∈ D_i
∀ A, un algoritm PTP, ∃ m_A, o functie neglijabila, ai P [ f_i ( z ) = y ; x ∈ D_i; i ∈ I ; y ← f_i ( x ) ; z ← A ( i , y ) ] ≦ m_A pentru k suficient de mare

# posted by Sorin Badescu @ 3:39 PM 0 comments

Friday, November 25, 2005

Functii cu sens unic

functie neglijabila: f : N → R este neglijabila ⇔ ∀ c > 0, ∃ k_c, ai f(k) < k^-c, ∀ k > k_c
functie puternica cu sens unic: f : {0, 1}^* → {0, 1}^* este puternica, cu sens unic ⇔:
∃ A, un algoritm PTP (probabilstic de timp polinomial), care obtine y = f(x), pentru x dat
∀ A, ∃ m_A, o functie neglijabila, ai P [ f ( z ) = y ; x ∈ {0, 1}^* ; y ← f ( x ) ; z ← A ( y ) ] ≦ m_A pentru k suficient de mare
Garantia este probilista, distributia de probabilitate este pe intreg domeniul lui f; nu se cere sa determine x ci sa se gaseasca o inversa ptr y; algoritmul primeste ca intrare f ( x ) si ruleaza in timp polinomial pe |x|
functie slaba cu sens unic: f : {0, 1}^* → {0, 1}^* este slaba, cu sens unic ⇔:
∃ A, un algoritm PTP, care obtine y = f(x), pentru x dat
∀ A, ∃ Q, o functie polinomiala, ai P [ f ( z ) ≠ y ; x ∈ {0, 1}^* ; y ← f ( x ) ; z ← A ( y ) ] ≧ m_A pentru k suficient de mare
Diferenta intre cele tipuri de functii este ca o functie slaba cu sens unic este greu de inversat pe o fractiune neglijabila a domeniului in timp ce o functie puternica cu sens unic este greu de inversat pe tot domeniul mai putin o fractiune neglijabila
∃ functii slabe ⇔ ∃ functii puternice
familie de functii puternice cu sens unic: F = { f_i : D_i → R_i }_i∈I, unde i ∈ I, ,multimea indicilor, este o familie de functii puternice cu sens unic daca:
∃ S₁, un algoritm PTP, ai i ← S₁ ( x ∈ {0, 1}^k ), i∈ {0, 1}^k ∩ I
∃ S₂, un algoritm PTP, ai x ← S₂ ( i ∈ I ), x∈ D_i
∃ A₁, un algoritm PTP, ai A₁ ( i , x ) = f_i( x ), unde i ∈ I, x ∈ D_i
∀ A, un algoritm PTP, ∃ m_A, o functie neglijabila, ai P [ f_i ( z ) = y ; x ∈ D_i; i ∈ I ; y ← f_i ( x ) ; z ← A ( i , y ) ] ≦ m_A pentru k suficient de mare

# posted by Sorin Badescu @ 4:46 PM 0 comments

Secvente pseudoaleatoare

Generator bit pseudo-aleator (GBPSA)

Este un algoritm determinist care porneste de la o secventa binara aleatoare de lungime k, numita cheie de generare, si produce o secventa binara de lungime l>>k, numita secventa de biti pseudo-aleatori
Un GBPSA este un program determinist de timp polinomial G:{0, 1}^k → {0, 1}^l care satisface:

l > k
distributia de probabilitate G_l se obtine din distributia normala U_k astfel: y=G(x), y ∈ G_l, x ∈ U_k

Teste in timp polinomial

Un generator bit pseudo-aleator trece toate testele statistice in timp polinomal daca un algoritm de timp polinomial nu poate face distinctia intre o secventa de la iesirea generatorului de bit pseudo-aleator si o secventa aleatoare de bit cu o probabilitate semnificativ mai mare ca 1/2
Fie X_n si Y_n doua distributii de probabilitate pe {0, 1}ⁿ. {X_n} este indistinctibila in timp polinomial de {Y_n} daca ∀ MTP, A, ∀ polinom Q, ∃ n>n₀ ai | Pr_{t∈X_n} (A(t)=1) - Pr_{t∈Y_n} (A(t)=1) | < 1/Q(n)
Pentru distributia uniforma de probabilitate U_n, ∀ a ∈ {0, 1}ⁿ, Pr_{x∈U_n} [x=a] = 1/ 2ⁿ

Testul bitului urmator

Un generator bit pseudo-aleator trece testul bitului urmator daca nu exista un algoritm de timp polinomial care sa poata prezice bitul "l+1" cu o probabilitate semnificativ mai mare ca 1/2, in baza primilor "l" biti ai unei secventa de la iesirea generatorului de bit pseudo-aleator
Un generator de bit pseudo-laeator trece testul bitului urmator ⇔ generatorul de bit pseudo-aleator trece testele de timp polinomial

Generator sigur criptografic de bit pseudo-aleator

Este un GBPSA care trece testul bitului urmator, posibil in niste ipoteze matematice plauzibile, dar nedemonstrate

# posted by Sorin Badescu @ 2:13 PM 0 comments

Thursday, November 17, 2005

Clase de complexitate

Limite
Clase
1. Limbaje
2. Functii

# posted by Sorin Badescu @ 2:57 PM 0 comments

Wednesday, November 16, 2005

Modele calcul - automate

Clasificare

Clasificarea Chomsky	Gramatica	Limbajul	Automatul minimal	Forma normala
tip 0	fara restrictie	recursiv enumerabil	MTN	-
-	fara restrictie	recursiv	decidor	-
tip 1	dependenta de context	dependent de context	marginit liniar	KURODA
tip 2	independenta de context	independent de context	push down	CHOMSKY, GREIBACH
tip 3	regulara	regular	finit	-

Gramatici si limbaje

O multime finita si nevida, Σ, se numeste alfabet iar elementele se numesc simboluri
O succesiune de simboluri se numeste secventa si o submultime ordonata a unei secvente se numeste subsecventa
Numarul de simboluri care formeaza o secventa s se numeste lungimea secventei si se noteaza |s|
Multimea secventelor peste un alfabet Σ se noteaza Σ^*
(Σ^*, +) este monoid unde "+" este concatenarea si elementul neutru este secventa vida ε
O submultime a lui Σ^* se numeste limbaj iar elementele limbajului se numesc cuvinte
Se numeste gramatica G un cvadruplu (N, Σ, P, s) unde
- N este un alfabet de simboluri neterminale
- Σ este un alfabet de simboluri terminale, N si Σ sunt disjuncte
- P este o multime finita de productii, P⊂ (N∪Σ)^*N(N∪Σ)^* X (N∪Σ)^*
- s este simbolul initial, s∈N
Pe multimea (N∪Σ)^* se definesc relatiile binare
Limbajul L(G) generat de o gramatica G=(N, Σ, P, s) este {v/ v∈ Σ^*, s ⇒^* v}
Clasificarea Chomsky
- Gramaticile de tip 0 nu au nici o restrictie referitoare la forma productiilor
- Gramaticile de tip 1, gramatici dependente de context, au productii de forma αAβ → αγβ unde αβγ ∈ (N∪Σ)^* si A ∈ N iar daca productia s → ε ∈ G atunci s nu apare in mebrul drept al nici unei productii (monotone, necontractante)
- Gramaticile de tip 2, gramatici independente de context, au productii de forma A → α unde A ∈ N si α ∈ (N∪Σ)^*
- Gramaticile de tip 3, gramatici regulare, au productii de forma A → aB sau A → b unde A, B ∈ N si a, b ∈ Σ

Automate

Automate finite
- Automat finit determinist
  Un cvintuplu AFD=(Q, Σ, δ, q₀, F) unde:
  - Q este o multime finita nevida; elementele sale se numesc stari
  - Σ este un alfabet de intrare
  - δ este functia de tranzitie, δ : Q X Σ → Q
  - q₀ este starea initiala, q₀ ∈ Q
  - F este multimea starilor finale, F ⊆ Q
  Daca δ este surjectiva, AFD este total definit
- Automat finit nedeterminist
  Un cvintuplu AFN=(Q, Σ, δ, q₀, F) unde:
  - Q este o multime finita nevida; elementele sale se numesc stari
  - Σ este un alfabet de intrare
  - δ este functia de tranzitie, δ : Q X Σ → P(Q)
  - q₀ este starea initiala, q₀ ∈ Q
  - F este multimea starilor finale, F ⊆ Q
- Tranzitii
  Multimea configuratiilor unui automat este Q X Σ. Pe multimea configuratiilor se definesc urmatoarele relatii binare
  - tranzitia directa, →
    (p, as) → (q, v) ⇔ q = δ(p,a) unde p, q ∈ Q, a ∈ Σ, s ∈ Σ^*
  - k tranzitia, →^k
    (p, s₁) → (q, s₂) ⇔ de la configuratia (p, s₁) se ajunge la configuratia (q, s₂) prin k tranzitii directe
  - + tranzitia, →⁺
    (p, s₁) →⁺ (q, s₂) ⇔ ∃ k > 0 ai (p, s₁) →^k (q, s₂)
  - * tranzitia, →^*
    (p, s₁) →^* (q, s₂) ⇔ p=q, s₁=s₂ sau (p, s₁) →⁺ (q, s₂)
- Limbaj acceptat
  Limbajul acceptat de un automat finit AF = (Q, Σ, δ, q₀, F) este L(AF) = {s / S ∈ Σ, (p, s) →^* (q, ε), q ∈ F }
- Automate echivalente
  - Doua AF sunt echivalente daca accepta acelasi limbaj
  - ∀ AFN, M1, ∃ AFD, M2 ai L(M1) = L(M2)
Automate push down
Un septuplu APD=(Q, Σ, Γ, δ, q₀, Z₀, F) unde:
- Q este o multime finita nevida; elementele sale se numesc stari
- Σ este un alfabet de intrare
- Γ este alfabetul memoriei stiva
- δ este functia de tranzitie, δ : Q x ( Σ ∪ {ε} ) x Γ → P(Q x Γ^*)
- q₀ este starea initiala, q₀ ∈ Q
- Z₀ este simbolul de start al memoriei stiva
- F este multimea starilor finale, F ⊆ Q
Masini Turing
- Masina Turing determinista
  Un septuplu MTD=(Q, Σ, Γ, δ, q₀, B, F) unde:
  - Q este o multime finita nevida; elementele sale se numesc stari
  - Σ este un alfabet de intrare, Σ ⊂ Γ - {B}
  - Γ este alfabetul benzii
  - δ este functia de tranzitie, δ : Q x Γ → Q x Γ x {miscareStanga, miscareDreapta}
  - q₀ este starea initiala, q₀ ∈ Q
  - B este simbolul spatiu, B ∈ Γ
  - F este multimea starilor finale, F ⊆ Q
- Masina Turing nedeterminista
  Un septuplu MTN=(Q, Σ, Γ, δ, q₀, B, F) unde:
  - Q este o multime finita nevida; elementele sale se numesc stari
  - Σ este un alfabet de intrare, Σ ⊂ Γ - {B}
  - Γ este alfabetul benzii
  - δ este functia de tranzitie, δ : Q x Γ → P( Q x Γ x {miscareStanga, miscareDreapta} )
  - q₀ este starea initiala, q₀ ∈ Q
  - B este simbolul spatiu, B ∈ Γ
  - F este multimea starilor finale, F ⊆ Q
- Masina Turing probibilista
  MTP este o MTN pentru care selectia intre valorile functiei de tranzitie se face probabilistic

# posted by Sorin Badescu @ 4:11 PM 0 comments

Tuesday, November 15, 2005

Secvente aleatoare

Generator de bit aleator

Dispozitiv sau algoritm care produce o secventa de cifre binare care sunt independente statistic si fara nici o preferinta pentru vreuna dintre cifre

Obs

Dispozitivele folosesc ca sursa de entropie fenomenele fizice. Generarea print-un algoritm presupune exploatarea unui proces specific platformei de calcul. Este indicata utilizarea mai multor surse naturale de etropie, esantionarea acestora, concatenarea si apoi mixarea (ex: printr-o functie dispersie)
Utilizarea in scopuri criptografice a unui generator aleator implica interzicerea accesului adversarului la generator

Teste statistice

Este imposibil sa se demonstreze matematic ca un generator este cu adevarat aleator. Se folosesc teste statistice pentru detectarea eventualelor slabiciuni dar rezultatul trebuie privit ca o dovada probabilistica ca generatorul produce secvente cu anumite proprietati

testul de frecventa (un bit)

se testeaza daca aparitiile cifrelor "0" si "1" sunt aproximativ egale. Variabila aleatoare X=(n₀-n₁)²/n trebuie sa prezinte o distributie de probabilitate χ² cu un grad de libertate daca n>10 (in practica n>>10000)
testul serial (doi biti)

se testeaza daca aparitiile secventelor "00", "01", "11" si "10" sunt aproximativ egale. Variabila aleatoare X=4/(n-1)(n₀₀²+n₀₁²+n₁₁²+n₁₀²)-2/n(n₀²+n₁²)+1 trebuie sa prezinte o distributie de probabilitate χ² cu doua de libertate daca n>21
testul poker (generalizare test frecventa)

fie m∈N^* ai [n/m] ≥ 5x2^m. Se imparte secventa in k=[n/m] intervale disjuncte, de lungime m. Se noteaza n_i numarul de aparitii ale secventei a i^a, i∈[1, 2^m]. Variabila aleatoare X=2^m/k (∑_i=1^{2^m}n_i²) -k trebuie sa prezinte o distributie de probabilitate χ² cu 2^m-1 grade de libertate
testul de serie

se determina aparitiile seriilor de "0" si "1" de diverse lungimi si se compara cu, aparitiile unei secvente de lungime i pentru o secventa aleatoare de lungime n, e_i=(n-i+3)/2ⁱ⁺². Fie k cea mai mare valoare a lui i pentru care e_i≥ 5. Z_i si U_i reprezinta numerele de secvente de "0" si "1" de lungime i unde i∈[1, k]. Variabila aleatoare X = ∑_i=1^k((Z_i-e_i)²/e_i) + ∑_i=1^k((U_i-e_i)²/e_i)trebuie sa prezinte o distributie de probabilitate χ² cu 2k-2 grade de libertate
testul de autocorelatie
se testeaza corelatia intre secventa si versiuni alunecate ale sale. Fie d ∈[1, [n/2]]. Numarul de biti din secventa, care nu sunt egali cu biti alunecati-d este A(d) = ∑_i=0^n-d-1 s_i ⊕ s_i+d. Variabila aleatoare X = 2 (A(d)-(n-d)/2)/ (n-d)^1/2 trebuie sa prezinte o distributie de probabilitate N(0,1) daca (n-d) ≧ 10
testul Maurer (test universal)

# posted by Sorin Badescu @ 5:05 PM 0 comments

Taxonomie semnaturi digitale

Alte notatii

spatiul mesajelor, P: multimea mesajelor
spatiul de semnare, P_s: multimea mesajelor ce pot fi semnate
functie redundanta, r: o functie injectiva r:P→P_r
spatiul valorilor de hash, P_h: codomeniul unei functii de dispersie, h:P→P_h
multimea index de semnare, I

Criterii

utilizarea mesajului original de catre algoritmul de verificare
numarul transformarilor

Clasificare

criteriul 1

scheme pentru semnatura digitala cu anexa
necesita mesajul original; fiecare entitate creeaza o cheie privata pentru semnare si o cheie publica pentru verificare
- utilizatorul U selecteaza o multime {sem_U,k; k∈I} care este cheia secreta a lui U; fiecare sem_U,k este o aplicatie injectiva de la P_h la S
- ∀ p∈P_h, s^*∈S, ver_A(p,s^*)=adevarat daca sem_U,k(p)=s^*, altfel ver_A(p,s^*)=fals; ver_A este cheia publica; transformarea se calculeaza fara a cunoaste cheia secreta
scheme pentru semnatura digitala cu recuperare de mesaj
mesajul original este recuperat din semnatura insasi
- utilizatorul U selecteaza o multime {sem_U,k; k∈I} care este cheia secreta a lui U; fiecare sem_U,k este o aplicatie injectiva de la P_s la S
- ∀k∈I, ver_A ○ sem_U,k=1_{P_s}, ver_A este cheia publica; transformarea se calculeaza fara a cunoaste cheia secreta

criteriul 2

schema aleatoare pentru semnatura digitala
Card(I)>1
schema determinista pentru semnatura digitala
Card(I)=1

# posted by Sorin Badescu @ 9:07 AM 0 comments

Monday, November 14, 2005

Semnatura digitala

Semnatura digitala

Este un mijloc prin care o entitate isi poate lega identitatea de o informatie. Procesul de semnare consta in transformarea unui mesaj si a unei informatii secrete intr-un marcaj care se numeste semnatura

P_s este multimea mesajelor care pot fi semnate
S este multimea elementelor numite semnaturi
sem_k este functia semnatura, sem_k:P_s→S

ver_k

P_s

Algoritm generare semnatura digitala

algoritm pentru producerea unei semnaturi digitale

Algoritm verificare semnatura digitala

algoritm pentru verificarea unei semnaturi digitale

Schema pentru semnatura digitala

Consta intr-un algoritm generare semnatura digitala si intr-un algoritm verificare semnatura digitala; exista o functie bijectiva de la multimea cheilor, K, la produsul SemxVer cu proprietatea ∀ p ∈ P_s, ∀ s ∈ S, ver_k(p,s)=adevarat ⇔ s=sem_k(p)

Procedura pentru semnare digitala

consta intr-un algoritm generare semnatura digitala si o metoda pentru transformarea datelor in mesaje ce pot fi semnate

Procedura pentru verificare semnatura digitala

consta intr-un algoritm pentru verificarea unei semnaturi digitale si o metoda pentru transformarea mesajului in date

# posted by Sorin Badescu @ 1:21 PM 0 comments

Thursday, November 10, 2005

Taxonomie functii hash

Criterii

rezistenta preimagine(sens unic, neinversabila): ∀ y nu este fezabila computational gasirea lui x ai h(x)=y
rezistenta preimagine ord. 2(rezistenta slaba la coliziune): ∀ x nu este fezabila computational gasirea lui x' ai x≠x' ∧ h(x)=h(x')
rezistenta la coliziune(rezistenta puternica la coliziune): nu este fezabila computational gasirea lui x si x' ai x≠x' ∧ h(x)=h(x')
rezistenta la calcul: nu este fezabila computational gasirea lui p_i si p' ai p_i≠p' ∧ h_k(p)=h_k(p') unde k este o cheie, avand la dispozitie mai multe perechi (p_i, h_k(p_i))

Clasificare

MDC(coduri detectoare modificare)
OWHF(functii hash cu sens unic, functie slaba hash cu sens unic): prezinta proprietatile de rezistenta preimagine si rezistenta preimagine ord.2
CRHF(functii hash rezistente la coliziune, functie puternica hash cu sens unic): prezinta proprietatile de rezistenta preimagine ord.2 si rezistenta la coliziune
alte aplicatii
MAC(coduri autentificare mesaj): prezinta proprietatea de rezistenta la calcul
alte aplicatii

Proprietati necesare in aplicatii specifice integritatii datelor

Aplicatia	rezistenta preimagine	rezistenta preimagine ord. 2	rezistenta la coliziune
MDC+semnatura asimetrica	da	da	da
MDC+canal autentic		da	da
MDC+criptare simetrica
fisier parole cu sens unic	da
MAC(cheia necunoscuta atacatorului)	da	da	da
MAC(cheia cunoscuta atacatorului)		da

# posted by Sorin Badescu @ 5:31 PM 0 comments

Functii hash

Functie hash (functie de dispersie): este o functie eficienta computational care pune in corespondenta siruri binare de lungime arbitrara cu siruri binare de lungime fixa. Sirul de lungime fixa se numeste valoare de hash

# posted by Sorin Badescu @ 11:01 AM 0 comments

Cifru flux

Cifruri flux (fluide)

Flux de chei (cheie fluida): Fie M= (P, C,K, E,D) un sistem de criptare. O secventa de simboluri k₁k₂k₃… ∈ K⁺ se numeste cheie flux (cheie fluida).
Cifru flux (cifru fluid): Fie A un alfabet cu Card(A)=q si M un cifru de substitutie simpla cu lungimea blocului egala cu 1. Daca k ∈ K⁺ este o cheie flux atunci mesajul criptat c se obtine din mesajul in clar p=p₁p₂p₃… astfel c=c₁c₂c₃ …=e_k₁(p₁)e_k₂(p₂)e_k₃(p₃)…
Cifru flux sincron: Fluxul de chei este generat independent de mesajul in clar si de mesajul criptat
Cifru flux aditiv binar: este un cifru flux sincron in care fluxul de chei, cifrele mesajului in clar si ale mesajululi criptat sunt cifre binare iar functia de criptare realizeaza un XOR intre cifra mesajului in clar si cifra fluxului de chei
Cifru flux asincron (autosincronizabil): Fluxul de chei este generat ca o functie de cheie si un numar fixat de cifre ale mesajului criptat anterior
Entropia: Fie X o variabila aleatoare care ia valorile x₁x₂…x_n cu probabilitatile P(X=x_i)=p_i
Se defineste entropia lui X ca fiind H(X)=∑_i=1ⁿp_ilg(1/p_i) unde prin conventie termenul pentru p_i=0 este 0
"One time pad": Shannon a demonstrat conditia necesara ca o schema de criptare simetrica sa fie sigura
H(k)≥H(p)
adica incertitudinea cheii secrete trebuie sa fie mai mare sau egala cu incertitudinea mesajului clar
Astfel, pentru o cheie de lungime (in biti) k, conditia devine k ≥H(p)

# posted by Sorin Badescu @ 10:26 AM 0 comments

Wednesday, November 09, 2005

Taxonomie cifruri bloc

Cifruri bloc: Un cifru bloc este o schema de criptare care sparge mesajul clar in subsiruri (blocuri) cu o lungime fixata peste un alfabet A si cripteaza un bloc o data.
Cifruri de substitutie: Cifrurile de substitutie inlocuiesc simbolurile/bloc de simboluri cu alte simboluri/blocuri de simboluri
monoalfabetice (substitutie simpla): Fie A un alfabet cu Card(A)=q, P multimea sirurilor de lungime t peste A si K multimea tututror permutarilor peste multimea A. Se defineste e_k(p)= (e_k(p₁)e_k(p₂)…e_k(p_t))=(c₁c₂…c_t)=c unde k ∈ K, p ∈ P, c ∈ P
homofonice: ∀ a ∈ P i se asociaza o multime H de subsiruri din C a.i. H(a) ∩ H(b) = ∅ ⇔ a ≠ b
polialfabetice: Fie A un alfabet cu Card(A)=q, P multimea sirurilor de lungime t peste A.
spatiul cheilor K este format din multimile ordonate cu t elemente, elementele fiind permutarile peste A
fie cheia k=(k₁, k₂, …, k_t). Se defineste e_k(p)= (e_k₁(p₁)e_k₂(p₂) …e_{k_t}(p_t))= (c₁c₂…c_t)=c unde k ∈ K, p ∈ P, c ∈ P
Cifru de transpozitie: Fie A un alfabet cu Card(A)=q, P multimea sirurilor de lungime t peste A si K multimea tututror permutarilor peste multimea {1,2,…,t}Se defineste e_k(p)= (e_k(p₁)e_k(p₂)…e_k(p_t))=(c₁c₂…c_t)=c unde k ∈ K, p ∈ P, c ∈ P
Cifru produs: Cifrurile de substitutie simpla si transpozitie nu asigura un nivel satisfacator de securitate. Combinandu-le se pot obtine cifruri puternice si in fapt sistemele de criptare practice sunt cifruri produs

# posted by Sorin Badescu @ 2:05 PM 0 comments

Tuesday, November 08, 2005

Cifru

Un sistem de criptare (cifru) este o structura (P, C, K, E, D), unde:

P= {w | w ∈ V*} este multimea ＂textelor clare＂, scrise peste un alfabet nevid V
C= {w | w ∈ W*} este multimea ＂textelor criptate＂, scrise peste un alfabet nevid W (uzual W = V ).
K este o multime de elemente numite chei.
Fiecare cheie K ∈ K determina o metoda de criptare e_K ∈ E si o metoda de decriptare d_K ∈ D . e_K : P → C si d_K : C → P sunt functii cu proprietatea d_K(e_K(w)) = w, ∀ w ∈ P.

Functia e_k este injectiva
Daca e_k este bijectiva, sistemul de criptare se numeste simetric.

# posted by Sorin Badescu @ 4:25 PM 0 comments

Monday, November 07, 2005

Primitive criptografice

Primitivele criptografice constituie caramizile utilizate la constructia sistemelor destinate a indeplini obiectivele criptografiei

Primitive generale

Permutari cu sens unic
Secvente aleatoare
Functii hash de lungime variabila

Primitive pentru criptografia cu chei simetrice

Cifruri cu chei simetrice

Cifruri bloc
Cifruri flux

Functii hash de lungime variabila
Semnaturi
Secvente pseudoalaeatoare
Primitive de identificare

Primitive pentru criptografia cu chei publice

Cifruri cu chei publice
Semnaturi
Primitive de identificare

# posted by Sorin Badescu @ 1:57 PM 1 comments

Obiectivele criptografiei

In contextul mai larg al obiectivelor securitatii informatiei, criptografia (cryptos+grafic) se ocupa de aspectele matematice ce privesc urmatoarele:

Confidentialitatea (privat, secret): informatia este disponibila numai entitatilor autorizate
Integritatea datelor (privat, secret): permite detectarea modificarilor aduse datelor de catre o terta parte; modificarile sunt: stergere, inserare, substitutie
Autentificarea: se refera atat la identificarea partilor cat si la informatia transmisa (autentificarea entitatii si autentificarea sursei)
Non-repudierea: prevenirea negarii unei actiuni savarsite de catre o entitate

# posted by Sorin Badescu @ 1:28 PM 0 comments

Plan de lectura

Introducere in criptografie cu exemple in extensia de criptografie Java

Sumar teoretic al criptografiei
1. Obiectivele criptografiei
2. Primitive criptografice
3. Criptografie cu chei secrete
4. Criptografie cu chei publice
5. Modele de securitate
6. Patente si standarde
Sumar JCE
1. Arhitectura JCE
2. Prezentarea cadrului de lucru in JCE
Exemple de utilizare pentru algoritmii implementati in Java

Surse Curs Timsoft Securitate si Platforma Java Handbook Of Applied Cryptography An Overview of Cryptography Curs criptografie de Adrian Atanasiu Lecture Notes on Cryptography Authors: S. Goldwasser and M. Bellare

# posted by Sorin Badescu @ 12:34 PM 0 comments

RaSol