Criptografie 2

1.1 Considerat¸ii generale

Vom lua ˆ1n discut¸ie ˆ1n aceastØa sect¸iune not¸iunea de semnØaturØa electronicØa (ˆ1ntr-un mediu de

calcul) precum ¸si diverse modalitØat¸i de utilizare ale ei.

Orice semnØaturØa pe un document autentificØa acest document dar ¸si angajeazØa ˆ1n mod normal

responsabilitatea semnatarului. Probleme practice legate de rapiditatea transmiterii unor

documente care sØa fie certificate ca autentice prin semnØaturØa au condus la necesitatea creerii

de semnØaturi electronice.

De exemplu, se ¸stie cØa majoritatea operat¸iunilor ¸si tranzact¸iilor bancare devin legal valide

numai dupØa ce ambele pØart¸i au semnat formularele respective. Totu¸si, dacØa pØart¸ile sunt legate

ˆ1ntr-o ret¸ea de calculatoare, ele vor adesea sØa faciliteze aceastØa operat¸ie care provoacØa un mare

consum de timp; solicitØa de aceea posibilitatea de a semna documentele folosind terminalele ¸si

ret¸eaua aflatØa la dispozit¸ie.

Deci, apare urmØatoarea problemØa:

Cum se poate crea o semnØaturØa ˆ1ntr-un mediu de calcul ?

Deoarece calculatoarele acceptØa informat¸ia numai ˆ1n formØa digitalØa, orice semnØaturØa pusØa

ˆ1n discut¸ie trebuie sØa aibØa aceastØa formØa. O semnØaturØa (electronicØa sau olografØa) trebuie sØa

satisfacØa urmØatoarele condit¸ii:

² UnicØa: o anumitØa semnØaturØa trebuie sØa poatØa fi generatØa numai de o singurØa persoanØa;

² NeimitabilØa: nici o altØa persoanØa nu va putea genera semnØatura utilizatorului indicat;

altfel spus, utilizatorii ilegali trebuie sØa rezolve probleme NP ¡ complete dacØa vor sØa

foloseascØa o semnØaturØa care nu le apart¸ine;

² U¸sor de autentificat: orice destinatar legal ¸si orice arbitru (ˆ1n cazul unor eventuale

dispute) sØa poatØa stabili autenticitatea semnØaturii (indiferent dupØa ce interval de timp);

² Imposibil de negat: nici un utilizator legal sØa nu-¸si poatØa nega propria semnØaturØa, sub

afirmat¸ia cØa nu este autenticØa;

² U¸sor de generat.

Trebuie fØacutØa totu¸si distinct¸ie ˆ1ntre semnØatura olografØa ¸si cea digitalØa.

IatØa cˆateva diferent¸e notabile ˆ1ntre cele douØa tipuri de semnØaturi:

1

2 PRELEGEREA 1. SEMNØ ATURI ELECTRONICE

² O semnØaturØa scrisØa de mˆanØa este o confirmare fizicØa a unui document, cu ajutorul unei foi

de hˆartie care cont¸ine douØa elemente: un mesaj (textul docu-mentului) ¸si o semnØaturØa.

O astfel de legØaturØa ˆ1ntre mesaje ¸si semnØaturi nu este posibilØa ˆ1ntr-un mediu de calcul;

² O semnØaturØa olografØa este aceea¸si indiferent de document. Pentru semnØaturile digitale

ˆ1nsØa, este esent¸ial ca ele sØa depindØa atˆat de semnatar cˆat ¸si de cont¸inu-tul documentului;

² Orice copie a unui document electronic (inclusiv semnØatura) este identicØa cu originalul.

ˆIn schimb copia unui document pe hˆartie este diferitØa ca valoare de original. Aceasta

conduce la ideea cØa un document electronic nu este reutili-zabil. De exemplu, dacØa Bob

trimite lui Alice un cec ˆ1n valoare de 10 milioane lei, banca nu va accepta onorarea sa

decˆat o singurØa datØa.

1.2 Protocoale de semnØaturØa

Orice protocol de semnØaturØa este format dintr-un algoritm de semnØaturØa ¸si un algoritm de

verificare. Bob semneazØa un mesaj x bazat pe un algoritm (secret) de semnØaturØa sig. Rezultatul

sig(x) este apoi verificat de un algoritm public de verificare ver. Pentru orice pereche (x; y),

algoritmul de verificare oferØa un rØaspuns dicotomic (adevØarat sau fals), dupØa cum y este o

semnØaturØa autenticØa a lui x sau nu. Formal ([8]):

Definit¸ia 1.1 Un protocol de semnØaturØa este un cvintuplu (P;A;K; S; V) unde:

1. P;A;K sunt mult¸imi finite, nevide, ale cØaror elemente se numesc mesaje, semnØaturi

¸si respectiv chei;

2. ExistØa o aplicat¸ie biunivocØa ˆ1ntre K¸si S£V; anume, pentru fiecare K 2 K existØa o pereche

unicØa (sigK; verK) unde sigK : P ! A, verK : P £ A ! fT; Fg au proprietatea:

8x 2 P, 8y 2 A, verK(x; y) = T () y = sigK(x)

Pentru fiecare K 2 K, funct¸iile sigK ¸si verK trebuie sØa fie calculabile ˆ1n timp polinomial;

verK este publicØa iar sigK este secretØa. Pentru Oscar, imitarea unei semnØaturi a lui Bob pentru

un mesaj x trebuie sØa fie imposibilØa (din punct de vedere al complexitØat ii calculului). Altfel

spus, pentru un x dat, numai Bob este capabil sØa calculeze o semnØaturØa y astfel ca ver(x; y) = T.

Bineˆ1nt¸eles, nici un protocol de semnØaturØa nu este absolut sigur, deoarece Oscar poate

ˆ1ncerca – folosind funct¸ia publicØa de verificare ver – toate semnØaturile y posibile ale unui mesaj

x, pˆanØa va gØasi semnØatura corectØa.

Deci, dacØa ar dispune de suficient timp, Oscar poate totdeauna sØa contrafacØa semnØatura

lui Bob.

Curs de criptografie semestrul 2, profesor Adrian Atanasiu -Universitatea Bucuresti