Algoritm Asimetric de Criptare - Algoritmul EG

7/27/2019 Algoritm Asimetric de Criptare - Algoritmul EG

1/6

1. Noiuni generale

Algoritmi criptografici cu chei publice (asimetrici)

O nou privire asupra sistemelor criptografice au adus-o algoritmii de criptare asimetrici (cu chei

publice). Aceti algoritmi se caracterizeaz prin aceea, c la criptare i decriptare se folosesc chei diferite,

legate ntre ele printr-o relaie matematic. Acest tip de relaie este de o aa natur, c cunoscnd o cheie,s o determini pe cealalt, din punct de vedere computaional, este foarte greu. Astfel dac criptm cu

prima cheie vom putea decripta doar cu cea de adoua i invers. n acest fel pentru transmitere de

informaii secrete una dintre chei (de exemplu cea de criptare) poate fi fcut public, pe cnd cealalt s

fie inut n secret (cheie privat). Dac de fcut cheia de descifrare public, atunci pe baza acestui sistem

se poate de creat un sistem de autentificare.

Figura 1. Schema de aplicare a algoritmului asimetric de criptare

Din cele expuse aici se pot evidenia dou direcii de utilizare a criptosistemelor asimetrice:

de confidenialitate - se face public cheia public i astfel cel care dorete s trimit date

confideniale proprietarului cheii publice va cripta aceste date cu aceast cheie, tiind c doar proprietarul

le va putea decripta;

de autentificare att a emitorului ct i a datelor - emitorul cripteaz datele cu cheia sa

secret (privat), iar cel ce va dori s autentifice datele va folosi la decriptare cheia pereche (cea fcut

public).

Chiar dac criptosistemul asimetric este destul de puternic, vom avea nevoie ca lungimea cheii s

fie de minimum 2304 bii pentru a oferi un nivel de securitate comparabil cu cel oferit de o cheie de 128

bii n criptosistemul simetric. Criptosistemele asimetrice sunt cu mult mai lente la criptare/decriptare i

sunt nepractice la criptarea volumelor mari de informaii. Criptosistemele simetrice sunt de aproximativ

1000 de ori mai rapide ca cele asimetrice, deaceea criptosistemele asimetrice cel mai des se folosesc n

urmtoarele scopuri de baz:

la distribuia cheilor, care se folosesc la algoritmii simetrici de criptare

semntura digital, un atribut al unui utilizator, folosit pentru recunoaterea acestuia.


2/6

Tehnica cheilor publice poate fi folosit i pentru autentificarea mesajelor, prin aa numita

semnatur digital, fapt care i-a sporit popularitatea. Folosind algoritmi cu cheie public (asimetrici), se

creaz criptosisteme cu dou chei, n cadrul crora doi utilizatori (procese) pot comunica cunoscnd

fiecare doar cheia public a celuilalt.

n criptosistemele cu chei publice fiecare utilizator A, deine o transformare de cifrare public, EA, care

poate fi memorat ntr-un registru (fiier) public i o transformare de descifrare secret, DA , ce nu este

posibil s fie obinut din EA. Cheia de descifrare (secret) este derivat din cheia de cifrare (public)

printr-o transformare greu inversabila (one-way). n sistemele cu chei publice, protecia i autentificarea

sunt realizate prin transformari distincte. S presupunem ca utilizatorul (procesul) A doreste s emit un

mesaj, M, unui alt utilizator (proces) B. Dac A cunoate transformarea public E B, atunci A poate

transmite M la B sub forma C=EB(M), asigurndu-se astfel funcia de confidenialitate.

La recepie, B, va descifra criptograma C utiliznd transformarea secret D B, cunoscut doar de el:

DB(C) = DB(EB(M)) = M.

Schema nu furnizeaz faciliti de autentificare, deoarece orice utilizator (proces) are acces la

transformarea public EB a lui B i i poate trimite mesaje false M' sub forma C'=E B(M').

Pentru autentificare se aplic lui M transformarea secret DA a lui A. Ignornd protecia pentru

moment, A va emite C=DA(M) la B, care la recepie va aplica transformarea publica, E A a lui A:

EA(C)=EA(DA(M))=M (a se vedea Crearea i Verificarea Semnturii Digitale).

Autentificarea este realizat deoarece numai A poate aplica transformarea D A. Acest concept

poart numele de semnatu digital, fiind folosit pentru recunoaterea sigur a utilizatorilor sau

proceselor. Fie B un receptor de mesaj semnat de A. Semntura lui A trebuie s satisfac urmtoareleproprieti:

B s fie capabil sa valideze semnatura lui A;

sa fie imposibil pentru oricine, inclusiv B, s falsifice semnatura lui A;

n cazul n care A nu recunoate semnarea unui mesaj M, trebuie s existe un judector" care s

poat rezolva disputa dintre A i B.

Protecia nu este asigurata, intrucit este posibil ca mesajul M sa fie obtinut de oricine, aplicind

transformarea publica EA. Pentru a se realiza simultan protectia si autentificarea informatiilor spatiului

{M} trebuie sa fie echivalent spatiului {C}, asa incit orice pereche (E A, DA) sa fie in masura sa opereze

atit asupra textului clar, cit si asupra textului cifrat; n plus se cere ca EA i DA s fie mutual inverse,

adic:

EA(DA(M)) = DA(EA(M)) = M.

Emitorul de mesaj A va aplica mai nti transformarea secret a sa, D A, mesajului M, semnndu-

l. Apoi A va cifra rezultatul - utilizind transformarea public a lui B, E B i va emite ctre receptor

criptograma: C=EB(DA(M)).

Receptorul B l obine pe M aplicnd la nceput propria-i funcie de descifrare, DB, iar apoi

transformare public a lui A, EA, cea care furnizeaza autentificarea :

EA(DB(C))=EA(DB(EB(DA(M)))) = EA(DA(M)) =M.


3/6

Cele mai ntrebuinate criptosisteme asimetrice sunt urmtoarele:

RSA(Rivest-Shamir-Adleman)

EG (ElGamal)

ECC (Elliptical Curve Cryptography).

2. Criptosistemul ElGamal

Criptosistemul ElGamal a fost propus n anul 1985, de catre Taher ElGamal. Algoritmul ElGamal

poate fi folosit att pentru criptare ct i pentru semnturi digitale. Securitatea acestui criptosistem se

bazeaz pe intractabilitatea problemei logaritmului discret. Este un sistem de criptare probabilist, n

sensul c unui plaintext i pot corespunde mai multe criptotexte (relaie `one-to-many'). Un dezavantaj al

criptosistemului ElGamal este expansiunea mesajului cu un factor 2. Cu alte cuvinte, criptotextul este de

dou ori mai mare fa de textul clar. Criptosistemul ElGamal este folosit n programul gratuit GNU

Privacy Guard i n versiuni recente ale programului PGP.Avnd n vedere ultimele progrese ce s-au fcut n domeniul problemei logaritmului discret, un

parametru p de dimensiune 512 bii furnizeaz o securitate marginal. Pentru securitate pe termen lung

este recomandat s alegem p cu o dimensiune de minim 1024 biti. De asemenea, pentru a evita calcularea

logaritmului discret cu ajutorul algoritmului Pohlig-Hellman, se alege p astfel nct p1 sa aib cel puin

un divizor prim `mare'.

Este esenial s alegem valori diferite pentru parametrul k n cazul n care dorim s criptm

mesaje diferite. S presupunem c acelai k este folosit pentru a cripta mesajele m1 si m2, rezultatul fiind

criptotextele (1, 1) si (2, 2). Atunci 1/2 = m1/m2, iar m2 poate fi calculat uor dac m1 este cunoscut.

Mai mult, n acest caz se poate determina cheia privat a.

El Gamal propune n o nou metod de semntur bazat pe schema de distribuie a cheilor a lui

Diffie i Hellman. Schema presupune c A i B doreau stabilirea unei chei secrete kAB, A folosind

informaia secret xA, iar B pe xB. De asemenea exist un ntreg prim mare p i un element a primitiv

modulo p. A va calcula yA=axA mod p i va emite la B pe yA. Similar B va emite la A: yB=axB mod p. Ca

urmare fiecare poate acum calcula cheia secret comun:

kAB=(axA)xB mod p = (yA)xB mod p = (axB)xA mod p = (yB)xA mod p.

Pentru ca A s transmit un mesaj m cifrat la B, 0mp-1, A va putea alege un k [0, p-1] care

va servi drept cheie secret xA. El va calcula apoi cheia: kAB=yBk mod p, unde yB a fost obinut direct de la

B sau dintr-un fiier cu chei publice. A va putea emite la B perechea (c1, c2), unde: c 1=ak mod p, i c2=kAB

m mod p.

Descifrarea se face i ea n dou etape. Mai nti se obine kAB:

kAB = (ak)xB = (c1)xB mod p.

Apoi se va obine mesajul clar prin mprirea lui c 2 la kAB. El Gamal propune pe baza acestei

scheme o nou metod de semntur. Fie m un document semnat, 0mp-1. Fiierul public va conine

cheia y=ax mod p pentru fiecare utilizator. Pentru a semna un document, A va folosi cheia sa secret x A


4/6

ntr-o astfel de manier nct semntura s poat fi verificat de orice alt utilizator pe baza cheii publice

yA.

2.1 Procedura de semnare

a) Se alege aleator un ntreg k, k [0, p-1], astfel ca c.m.m.d.c.(k, p-1) = 1;

b) Se calculeaz: r = ak mod p. Semntura lui m este perechea (r,s), 0r, sp-1, care satisface condiia:

m=yrrs (mod p) (*);

c) acum condiia (*) poate fi scris: am=axraks mod p, prin rezolvarea ecuaiei m=xr+ks mod p, care are

soluie dac se respect procedura a).

2.2 Verificarea semnturii

Fiind dai m, r, s, este uor s se verifice autenticitatea semnturii calculnd am (mod p), yrrs

(mod p) i verificnd apoi dac sunt egale. Este indicat ca valoarea lui k, aleas aleator, s fie folosit o

singur dat. Se poate folosi n acest scop un generator de k bazat pe un model DES (generator cucontor).

2.3 Schema succint ElGamal:

- cheia public: EA = aDA (mod n), unde a este o constant a sistemului cunoscut de ctre toi

parametrii; n = este un numr prim;

- cheia secret: DA, un numr natural.

(1) Semnarea unui mesaj M se face dup urmtorul algoritm:

pentru i=1, p-1 execut

generez aleator ki n [0, n-1] astfel nctc.m.m.d.c. (ki, n-1)=1

calculez ai = aki (mod n) din ecuaia:

M=DAa1+k1a2+...+kp-1ap (mod n-1)

sfrit

Ca urmare semntura lui M realizat cu nivelul de securitate p este reprezentat de:

S=(a1,a2,...,ap).

(2) Verificarea semnturii se face calculnd separat:

Valoarea 1 = aM mod n i Valoarea 2 = eAa1a1a2...ap-1ap mod n i comparndu-le dac sunt egale.Aceast schem introduce un factor de complexitate suplimentar prin nivelul p de securitate,

ceea ce sporete rezistena schemei la atac criptanalitic. Criptanalistul este confruntat cu necesitatea

inversrii tuturor funciilor exponeniale a i=aki (mod n) n cmp finit, ceea ce reprezint o problem grea

computaional dac n este mare (128, 256, 512 bii).

2.4 Generalizarea algoritmului de criptare asimetric ElGamal (EG)

Schema de semntur ElGamal:

Generarea semnturii

Entitatea A semneaz un mesaj binar m de o lungime arbitrar.

Pentru aceasta, entitatea A execut urmtoarele:


5/6

Selecteaz aleator un nr. ntreg secret k, 1 k p-2, astfel nct cmmdc (k, p-1) =

Calculeaz r = kmod p i k-1 mod (p-1)

Calculeaz s = k-1(H(m)-a*r) mod (p-1), unde H este o funcie Hash

Semntura mesajului m este perechea (r,s).

Verificarea semnturii

Pentru a verifica semntura (r,s) a mesajului m, entitatea B execut urmtoarele:

Obine cheia public autentic (p, , y) a entitii A

Verific dac 1 r p-1. Dac aceast inegalitate nu are loc, semntura (r, s) nu e valid.

Calculeaz v1 = yr rs mod p.

Calculeaz H(m) i v2 = H(m) mod p, unde H este o funcie Hash.

Semntura (r,s) este acceptat dac i numai dac v1 = v2.

Shema de semntur ElGamal

Exemplu: A genereaz nr. prim p = 2357 i generatorul = 2 al gr. Z*2357.

A alege cheia privat a =1751 i calculeaz y=a mod p=21751 mod 2357 = 1185.

Cheia public a lui A este (p=2357, =2, y=1185), iar cheia sa privat este a =

1751.

Pentru a semna mesajul m=1463, A selecteaz aleator un ntreg k=1529,

calculeaz r=k mod p=21529 mod 2357=1490 i k-1 mod (p-1)=245.

A calculeaz S=245*(1463-1751*1490) mod 2356 = 1777. Semntura mesajului

m=1463 este perechea (r=1490, s=1777). Pentru verificarea semnturii, B calculeaz v1=11851490 *14901777 mod 2357=1072,

H(m)=1463 i v2=21463 mod 2357=1072.

Entitatea B accept semntura deoarece v1 = v2.

3. Avantajele criptrii cu chei publice

Avantajele criptografiei cu chei publice sunt extraordinare, cu condiia ca

aceasta s poat fi realizat practic fr nici un fel de urmri secundare negative. O

inovaie adus de cheile publice privete gestiunea cheilor: cum se pot mnui i

transmite chei. S considerm un criptosistem clasic (simetric). Cheia de criptare o

furnizeaz i pe cea de decriptare i, prin urmare, prima nu poate fi fcut public.

Aceasta nseamn c cele dou pri legale (emitorul i receptorul) trebuie s

cad de acord n avans asupra metodei de criptare. Aceasta poate avea loc fie prin

ntlnirea dintre cele dou pri, fie prin transmiterea cheii de criptare pe un anumit

canal sigur.

Dac se folosete un criptosistem cu chei publice, nu este obligatoriu ca cele

dou pri s se fi ntlnit ele pot chiar s nu se cunoasc una cu alta sau chiar s

nu fi comunicat ntre ele vreodat. Aceasta este un avantaj uria, de exemplu, n


6/6

cazul unei mari bnci de date, unde exist numeroi utilizatori i unul dintre ei vrea

s comunice numai cu anumit utilizator. Atunci el poate realiza acest lucru

introducnd informaii n nsi baza de date. Criptosistemele cu chei publice i cele

clasice se pot compara i n ce privete lungimea cheii. Deoarece fiecare cheie

trebuie descris ntr-un fel sau altul, descrierea fiind o secven de litere ale unui

anumit alfabet (adic un cuvnt), pare foarte natural s vorbim despre lungimea

unei chei. Exist o diferen considerabil ntre criptosistemele cu chei publice i

cele clasice.

S considerm la nceput un criptosistem clasic. Dac cheia este mai lung

dect textul clar, realmente nu s-a obinut nimic. Deoarece cheia trebuie transmis

pe un canal sigur am putea transmite textul clar n locul cheii pe acelai canal sigur.

Evident, n anumite situaii cheia se transmite n avans n ateptarea unui moment

crucial. S considerm acum i criptosistemul cu chei publice. Lungimea cheii decriptare este n mare msur irelevant. Cheia este oricum public. Aceasta

nseamn c i lungimea cheii de decriptare este irelevant, receptorul trebuind s

o stocheze ntr-un singur loc.

Uurina gestiunii cheilor poate fi privit cu ndreptire ca avantajul esenial

al criptografiei cu chei publice.

4. Concluzii

Criptosistemul ElGamal are proprieti homomorfice, nsemnnd faptul c are loc relaia E(m0,k0) E(m1, k1) = E(m0 m1, k0+k1), unde E(m, k) reprezint criptarea mesajului m folosind numrul aleator

k. Aceast proprietate l face potrivit pentru aplicaii de vot electronic sau licitaie electronic, ceea ce l

face utilizabil n aceste domenii. nc de la inventarea sa, schema ElGamal a generat un interes continuu

n comunitatea criptologilor. Cercetri asupra sistemului ct i aplicaii reale ale acestui criptosistem,

continu i astzi. n plus, ideile ce stau la baza acestei scheme de criptare formeaz baza unor scheme de

semnturi digitale ca DSS (Digital Standard Signature) sau Schnorr.

Algoritm Asimetric de Criptare - Algoritmul EG

Documents

Transcript of Algoritm Asimetric de Criptare - Algoritmul EG