Protocoale de vot electronic

Studenti: Manole Cristian Ionut

Albu Alexandru Alin

Protocoale de vot electronic

Guvernele i organiza iile democratice au nevoie de anumite mecanisme pentru aș ț permite alegătorilor să voteze. În mod tradi ional, alegerile reprezintă pentru persoaneleț cu drept de vot mecanismele oficiale prin care acestea î i pot exprimă op iunile în modș ț democratic, în timp ce sondajele constituie una din cele mai bune metode neoficiale de aflare a op iunilor electoratului. Atât în alegeri cât i în sondaje intimitatea i securitateaț ș ș sunt deziderate obligatorii dar al căror cost poate cre te substan ial. Mecanismele careș ț asigură securitatea i intimitatea alegătorilor pot fi scumpe i/sau consumatoare de timpș ș pentru administratorii acestora i neconvenabile pentru alegători. Organizarea de alegeriș sigure devine i mai dificilă atunci când alegătorii sunt distribui i pe o mare zonăș ț geografică. Acestea sunt câteva motive pentru care poate fi propusă cu succes modalitatea de vot electronic. Primele idei apar în anii 80, iar ideile dezvoltate în acest interval de timp îl fac din ce în ce mai credibil pentru utilizarea sa într-un mediu informatizat.

Caracteristici ale unui sistem de vot electronic

De i există numeroase protocoale i sisteme de votare, procedura de bază pentruș ș organizarea de alegeri democratice este standard. Această procedură - indiferent dacă este vorba de o votare clasică sau una electronică - implică în general îndeplinirea a patru sarcini:

1. Înregistrarea: crearea unei liste de persoane care au dreptul să voteze;

2. Validarea: verificarea datelor personale ale celor care doresc să voteze. Se permite votarea numai pentru cei care au drept să voteze i nu au votat deja.ș

3. Colectarea voturilor de la centrele de votare.

4. Numărarea voturilor.

Pentru a avea încredere în rezultatul alegerilor, oamenii trebuie să aibă dovezi că aceste sarcini au fost îndeplinite în mod corect. Există însă numeroase posibilită i deț corupere a sistemului în timpul îndeplinirii fiecăreia din aceste sarcini. De exemplu:

Autorită ile electorale pot tri a permi ând alegătorilor fără drept de vot să seț ș ț înregistreze la vot, iar alegătorilor înregistra i să voteze de mai multe ori. Deț asemenea se pot pierde sau adăuga voturi suplimentare.

Alegătorii fără drept de vot se pot înregistra (cel mai frecvent folosind numele unei persoane decedate) sau cei cu drept de vot se pot înregistra sub mai multe nume.

Se poate încerca participarea la vot sub o identitate falsă. Cutiile cu voturi, voturile sau ma inile de numărat pot fi compromise.ș

Atunci când se proiectează un sistem electronic de vot este esen ial să se implementezeț modalită i prin care cele patru condi ii men ionate mai sus să fie îndeplinite fără a sacrificaț ț ț intimitatea alegătorilor sau a oferi posibilită i de fraudă. În plus, mai trebuie îndepliniteț câteva condi ii specifice unui astfel de sistem. Un sistem de vot electronic trebuie săț satisfacă următoarele cerin e:ț

1. Anonimitatea votan ilor: ț Nu există nici o modalitate prin care poate fi dezvăluită identitatea unei persoane care votează.

2. Acurate e: ț Oricine poate verifica validitatea voturilor i se poate asigura că voturileș nu au fost schimbate, multiplicate sau eliminate de cineva (inclusiv de autorită i).ț

3. Corectitudine de număr: Suma voturilor repartizate pe candida i este egală cuț numărul de voturi valide.

4. Verificabilitate: Orice votant poate controla dacă votul sau a fost numărat iș repartizat candidatului pe care l-a votat.

5. Detectarea dublei votări: Dacă apare un vot dublu, organizatorii pot identifica persoana care a votat de mai multe ori.

Protocolul independent de vot

Cele mai simple protocoale de vot nu folosesc nici o autoritate, bazându-se numai pe alegători. Sunt primele protocoale concepute pentru votare, bazate pe aplicări succesive de criptări i/sau semnări digitale de mesaje. Anonimitatea se ob ine prin aplicarea deș ț permutări în diverse faze. Pentru exemplificare, se va prezenta protocolul lui Michael Merritt: Sunt N alegători, fiecare alegător i având cheia publica de criptare ei i cheiaș privată di precum i o semnătura electronică sigș i. Protocolul este următorul;

1. Fiecare alegător i ata ează un număr aleator rș i la votul său mi.2. Criptează perechea (mi; ri) cu cheile publice ale tuturor alegătorilor în ordinea 1,

….,N, ob inând secven a eț ț N(eN-1(…(e1(mi; ri))…).3. Repetă pasul anterior adăugând după fiecare criptare câte un număr aleator Ri

distinct (pe care-l trimite lui i). Se ob ine eț N(RN, eN-1(…(R2, e1(R1, eN(eN-1(…(e1(mi; ri))…).

4. Toate aceste voturi sunt strânse de alegătorul N. Fiecare alegător i:

(a) Decriptează mesajul cu cheia sa secretă di, scoate numărul Ri i se asigură că esteș pe lista numerelor aleatoare primite.

(b) Amestecă cele N voturi i le trimite lui ș i -1 (alegătorul 1 le trimite lui N). După efectuarea acestui pas, alegătorul N dispune de N mesaje de forma eN(eN-1(…(e1(mi; ri))…) pe care le semnează cu semnătura sa sigN.

5. Procedeul se reia, fiecare alegător i:

(a) Verifică validitatea semnaturii alegătorului i + 1;

(b) Decriptează mesajele primite;

(c) Aplică propria sa semnatură sigi i trimite lui ș i -1 cele N mesaje de forma sigi(ei(…(e1(mi; r + i)…).

6. În timpul procesului de votare numărul de voturi este constant, deci pierderea sau adăugarea unui vot este u or de detectat.ș

Amestecul voturilor asigură anonimitatea. De asemenea, voturile nu pot fi înlocuite; o astfel de încercare pe parcursul primei runde este depistată prin numărul aleator introdus incorect. Dacă alegătorul înlocuie te votul alegătorului j (j > i), atunci alegătorul jș va detecta acest lucru la începutul celei de-a două runde de decriptări (pasul 5). O încercare de înlocuire pe parcursul celei de-a două runde este depistată la decriptarea finală când fiecare alegător î i verifică propriul său număr rș i. Un defect major al acestui protocol constă în implementarea dificilă datorată numărului mare de calcule, dependent de numărul de votan i ț N.

Protocolul Mu-Varadharajan

După 1986 au fost publicate diverse protocoale de vot, fiecare având avantajele iș dezavantajele sale. În continuare va fi prezentat un protocol de vot electronic pentru o re ea informatică bazat pe schemele de semnătură electronică ElGamal i RSA) propus deț ș Mu i Varadharajan în 1998. Ulterior vor fi demonstrate i corectate câteva slăbiciuni. ș ș

Componentele protocolului Mu-Varadharajan sunt:

V – mul ime finită nevinda de votan i;ț ț AS – un server de autentificare a votan ilor.ț VS – o mul ime finită de servere de votare;ț TCS – un server de numărare a buletinelor de vot; CA – un certificat de autenticitate.

Protocolul con ine trei etape:ț

1. Ob inerea buletinului de vot;ț2. Votarea (si colectarea buletinelor de vot);3. Numărarea buletinelor de vot.

Ini ializarea ț

Vom nota cu p un număr prim mare i cu ș t tampila de timp. De asemenea, || vaș α β reprezenta concatenarea secven elor si . Inainte de a incepe protocolul de vot:ț α β

Fiecare participant V prime te o pereche de chei RSA: (eș v, dv) si un modul nv ob inutț prin inmul irea a două numere prime mari. ț

AS de ine un modul nț AS si o pereche de chei RSA (eAS, dAS). nAS si eAS sunt publice, cunoscute de to i votan ii.ț ț

Orice vontant valid V are un certificat de vo anti Certț v eliberat pe termen lung de CA. Acesta este semnat de cheia secretă a lui CA, iar con inutul lui include:ț- Un număr serial

- Identitatea votantului V,- Identitatea CA,- Cheia publică ev si modulul nv,

- Intervalul de valabilitate,- O tampilă de timp.ș

Etapa I. Ob inerea buletinului de votț

Etapa II: Votarea (si colectarea buletinelor de vot)

În această fază V poate trimite prin re ea buletinul său de vot spre un server deț votare VS. Scopul principal al unui VS este de a garanta validitatea buletinului de vot. Protocolul con ine doi pa i:ț ș

1. V trimite T spre VS;2. VS decriptează T i verfica validitatea lui a, yș 1, y2 folosind semnătura s si cheia

publică eAS. Apoi VS determină corectitudinea semnăturii (s1, s2) pentru m, folosind rela iile: ț

Dacă rezultatul acestei verificări este pozitiv, atunci VS are certitudinea că buletinul T este valid.

Etapa III: Numărarea buletinelor de vot

Toate VS-urile trimit buletinele către TCS. Scopul acestuia este de a număra voturile i de a depista pe cei care au votat de mai multe ori.ș

Să presupunem că V folose te parametrii a, g, kș 1, k2 pentru a semna i un alt vot m’ș i să trimită un al doilea buletin T = a || g || yș 1 || y2 || s || s’1 || s’2 || m’ spre alt VS. Pentru a

detecta o dublă votare, VS verifică parametrii a, g, y1, y2 din toate buletinele T pentru a vedea dacă ei se repetă. În caz afirmativ, el rezolvă sistemul liniar:

si afla k2 . Folosind baza de date a lui AS, se identifică in mod unic votantul V.

Slăbiciuni ale protocolului Mu-Varadharajan

La (3) se arată că totu i există două modalită i prin care cineva poate vota de maiș ț multe ori fără să fie depistat. Să presupunem că V a ob inut buletinul valid de vot T = a || gț || y1 || y2 || s || s1 || s2 || m. Pe baza lui poate genera un alt buletin valid T’ astfel:

Atacul 1.

Atacul 2.

Protocolul Mu-Varadharajan modificat

Pentru a evita slăbiciunile în fa a atacurilor prezentate anterior, este construită oț variantă îmbunătă ită a protoculului de vot Mu-Varadharajan. Noua schema are tot treiț etape; acestea sunt (s-au folosit acelea i nota ii):ș ț

Etapa I: Obtinerea buletinului de vot

1. V alege doi factori blind b1, b2 i două numere aleatoare kș 1, r. Cu ace ti parametriș calculează w1 i wș 2 dupa formulele

Unde g ∈Zp* este un parametru public al sistemului.

2. VS verifică validitatea certificatului i validează semnatura (wș 1 || w2 || t)dv (mod nv). Dacă rezultatul verificării este pozitiv, AS poate fi sigur că parametrii primi i suntț corec i. El continuă alegând un număr aleator kț 2 diferit pentru fiecare votant iș calculează.

3. V ob ine kț 2 prin decriptarea lui w3, iar pe baza lui poate determina y1 i yș 2. Mai departe, V determină semnătura (s1, s2, s3 ) (eliminând factorii blind) conform rela iilorț

4. V aplică o schemă de semnătura ElGamal pentru a semna votul m. Fie y1, y2 cheile publice ale sistemului de criptare ElGamal i xș 1 = k1 + k2, x2 = 2k1 + k2 cheile secrete corespunzătoare; deci y1 = gk1 +k2(mod p) si y2 = g2k1+k2(mod p). Semnătura ((a, s4), (a, s5)) pentru votul m este generată de ecua iileț

Etapa II: Votarea (si colectarea buletinelor de vot)

1. V trimite buletinul de vot T lui VS.2. VS verifică validitatea lui a, y1, y2 folosind ecua iileț

Dacă toate sunt verificate, VS trece la verificarea corectitudinii semnăturii ((a, S4), (a, s5)) folosind rela iile:ț

Dacă ele se verifică, VS acceptă T ca valid. În final, VS formează o bază de date cu toate buletinele de vot valide, pe care o trimite prin re ea lui TCS.ț

Etapa III: Numărarea buletinelor de vot

După ce prime te buletinele de vot de la toate VS-urile, TCS face public con inutulș ț lor i le numără. În plus, el este responsabil cu detectarea dublei votări. Să presupunem căș un votant V folose te aceea i parametri yș ș 1, y2, a pentru a semna un vot diferit m’ i trimiteș acest buletin unui alt VS. Atunci:

1. TCS verifică y1, y2, a pentru toate buletinele T pentru a vedea dacă apar de mai multe ori.

2. Dacă aceste valori au apărut de doua ori si m=m’ se ia in considerare un singur buletin. Dacă m ≠ m’ rezultă că este un caz de dublă votare i TCS află identitateaș acestuia, calculând

Securitatea protocolului Mu-Varadharajan modificat

În ipoteza că serverul de autentificare SA este sigur i deci nu va genera nici unș buletin de vot fără consim ământul votantului, sistemul construit verifică toate restric iileț ț unui sistem de vot electronic.

Să presupunem că doi votan i Vț 1, V2 cu semnăturile valide (s11, s12, s13) respectiv (s21,

s22, s23) colaborează pentru ob inerea unei noi semnături (s’ț 1, s’2, s’3) definită prin s’I =s1i * s2i

(mod nAS), i= 1,2,3,4. Totu i ei nu vor putea calcula parametrii r’, x’ș 1, x’2 din cauza dificultă iiț de rezolvare a problemei logaritmului discret.