Algoritmi semnatura digitala

Algoritmi semnatura digitala

majoritatea schemelor cu recuperarea mesajului sunt aplicate mesajelor de lungime fixa, in timp ce schemele cu anexa se aplica mesajelor de lungimi variabile

• scheme cu anexa

algoritmul de verificare primeste ca intrare mesajul

• algoritmi generali

generarea cheii

fiecare entitate creeaza o cheie privata pentru semnarea mesajelor si o cheie publica pentru verificare

o entitatea A selecteaza o cheie privata ce defineste o multime a transformarilor de semnare S_A = unde fiecare S_A,k este o functie injectiva de la P_s la S

S_A defineste o transformare de verificare V_A :P_sx S → ai

∀ p ∈ P_h, s^* ∈ S, p = h(p) cu p ∈ P
V_A poate fi calculata fara a cunoaste semnatura privata a emitentului

cheia publica a lui A este V_A si cheia privata este multimea S_A

semnarea/verificarea

o entitatea A produce o semnatura s ∈ S pentru un mesaj p ∈ P ce mai tarziu poate fi verificata de o alta entitate B

semnarea

entitatea A executa

a.               selecteaza un element k ∈ I

b.              calculeaza p = h(p) si s^* = S_A,k(p)

c.               semnatura lui A pentru p este s^*; atat p cat si s^* sunt puse la dispozitia entitatilor care doresc sa verifice semnatura

verificarea

entitatea B executa

a.               obtine cheia publica autentica, V_A a lui A

b.              calculeaza p = h(p) si v = V_A(p, s^*)

c.               accepta semnatura daca si numai daca v = adevarat

• ElGamal
• DSA

este o varianta a semnaturii ElGamal

generarea cheilor

selecteaza un numar prim q ai 2¹⁵⁹ < q < 2¹⁶⁰

alege t ai 0 ≦ t ≦ 8 si un numar prim p, 2^511+64t < p < 2^511+64t cu proprietatea q|(p-1)

selecteaza un generator α al grupului ciclic de ord q din Z_p^*

selecteaza un element g ∈ Z_p^* si calculeaza α = g^(p-1)/q mod p

daca α = 1 at reia de la pasul anterior

selecteaza aleator un intreg a ai 1 ≦ a ≦ q-1

calculeaza y = α^a mod p

cheia publica a lui A este (p, q, α, y) si cheia privata este a

semnarea/verificarea

semnarea

entitatea A semneaza un mesaj, p, de lungime arbitrara

selecteaza aleator un intreg k, 0 < k < q, k va ramane secret

calculeaza r = (α^k mod p) mod q

calculeaza k^-1 mod q

calculeaza s = (k^-1(h(p)+ar)) mod q

semnatura lui A este (r, s)

in standardul DSS functia h este SHA-1

verificarea

entitatea B verifica semnatura lui A, (r, s) pentru mesajul p

obtine cheia publica autentica a lui A, (p, q, α, y)

verifica ca 0 < r < q si 0 < s < q, altfel respinge semnatura

calculeaza w = s^-1 mod q si h(p)

calculeaza u₁ = (wh(m)) mod q si u₂ = (rw) mod q

calculeaza v = ( (a^u₁ y^u₂) ) mod q

accepta semnatura daca v = r

• PKCS#1

aceasta schema nu utilizeaza caracteristica de recuperare a mesajului a schemei RSA si foloseste o functie de dispersie (MD-2 sau MD-5)

• Schnorr
• Feige-Fiat-Shamir
• scheme cu recuperarea mesajului

algoritmul de verificare nu necesita mesajul

• algoritmi generali

generarea cheii

fiecare entitate creeaza o cheie privata pentru semnarea mesajelor si o cheie publica pentru verificare

o entitatea A selecteaza o cheie privata ce defineste o multime a transformarilor de semnare S_A = unde fiecare S_A,k este o functie injectiva de la P_s la S

S_A defineste o transformare de verificare V_A :S → P_s ai ∀ p ∈ P_s, ∀ k ∈ I, V_A s S_A,k = 1_Ps
V_A poate fi calculata fara a cunoaste semnatura privata a emitentului

cheia publica a lui A este V_A si cheia privata este multimea S_A

semnarea/verificarea

o entitatea A produce o semnatura s ∈ S pentru un mesaj p ∈ P ce mai tarziu poate fi verificata de o alta entitate B; mesajul p este recuperat din s

semnarea

entitatea A executa

. selecteaza un element k ∈ I

a.       calculeaza p = r(p) si s^* = S_A,k(p)

b.      semnatura lui A este s^*; s^* este pus la dispozitia entitatilor care doresc sa verifice semnatura

verificarea

entitatea B executa

. obtine cheia publica autentica, V_A a lui A

a.       calculeaza p = V_A(s^*)

b.      verifica ca p ∈ P_r si in acest caz accepta semnatura

c.       recupereaza mesajul p din p calculand r^-1(p)

functia redundanta r si inversa sa sunt cunoscute public; selectia lui r este critica pentru securitatea sistemului

• RSA

atat spatiul de semnare P_s cat si spatiul semnaturilor S sunt reprezentate de Z_n

generarea cheilor

fiecare entitate creeaza o cheie publica RSA si o cheie privata corespondenta; o entitate A executa

genereaza doua numere prime distincte, p si q, de acceasi marime

calculeaza n = pq si φ = (p-1)(q-1)

selecteaza aleator in intreg e, 1 < e < φ ai cmmdc(e, φ) = 1

calculeaza intregul (Euclid extins) d, 1 < d < φ ai ed ≡ 1 mod φ

cheia publica a lui A este (n, e) si cheia privata este d

semnarea/verificarea

entitatea A semneaza un mesaj p ∈ P si oricare alta entitate B poate verifica smenatura lui A si recupera mesajul p din semnatura

semnarea

o entitate A executa

calculeaza p = r(p) ca un intreg in intervalul [0, n-1]

calculeaza s = p^d mod n

semnatura lui A pentru p este s

verificarea

o alta entitate B executa

obtine cheia publica autentica a lui A, (n, e)

calculeaza p = s^e mod n

verifica ca p ∈ P_r si daca nu rejecteaza semnatura

recupereaza mesajul p = r^-1(p)

• Rabin
• Nyberg-Rueppel