Puncte:1

Cum se dovedește decriptarea corectă în ElGamal Cryptosystem

drapel br

Lucrez la un proiect care folosește criptografia ElGamal folosind notația multiplicativă. Proiectul este o implementare a votului pe internet care folosește criptosistemul pentru a cripta buletinele de vot primite, a le recripta și a le amesteca, iar apoi, în cele din urmă, le decriptează. Eu bazez proiectul pe această hârtie (https://www.usenix.org/conference/evt-06/simple-verifiable-elections).

Știu cum să ofer dovada corectitudinii criptării și re-criptărilor ulterioare. Dar nu sunt sigur cum să fac asta pentru decriptare.

functie principala

funcția asincronă testDecryptProof() {
    // creează o instanță
    const instance = {
        g: '578581162149404798490571324493050333821753231896276896347588934236801486075345228356031089034308080355169502516970783985992465797790164077579971312181422206518964809883668939849570386967992767051369301215310754209280449807411021102153029377771783635510279329651149063858558329423219030908013960533321414499048784570490530207084776596253913339841694321299265784157923029847261603752469185349628532689446592521898507856757944009320377006868172969323251633981722550110871375408446896988161342745052895534300357801608217690146321171241606375301572941706622980330319103629192157393821194824468143500823157190887876038021286294694041671207075207845465680928059613160518275520282872421869149103173333949258329687311303065379518852070463040315621848668909908323797263963006103095659510784649320024411908921807300979021343984882137053231099693459838679137130760178994756250748747915572916102102876710115689234104349836600282068293111526381083439422743411854769767922191654138690358405340374558063855405817 898848980774741636240733553597229888674227126306560767485612428694999914792050501101312713302487481236334084764126207814284673857139915086576279907709746386734910200293561256639347096905974796093763848648123958776190861142984370193373964',
        p: '677088805808970643479133732614124310412316623451218811091733045838654739392363246453577008799155078839179531842224968947275228243113309850038122844034206790202276653380214548364178679947759556696213093774565712592343240601574723204104637149412506691550790846672244951946792272265332057245338838114080139164225120755358666371656799563377820758711742540625164732489435107295380237174828977225345274146615784182060315544480619981291902484596100159217062987931193501343478984350495475702937235166238839021800138523942802532967536519581875286415594806347061067009294601218779715836970031767680879370919882661828875007748699870086971737821411346178288109455141870605199207659215196027250095379359566675689788259770429733392884433737152092042439686604640479912921568537010168396445693348455112670632809025917594376152255614259482541945870534263328423690524049145709753098095473739179196969320905245503058104512347909553056470869228505715399271424136417025630569603129329944058750767224129798692688740617 502975582916178170805288244361290828581356312322935742661288429293532378052789528032585149311919895258686737427981082058024550795015310013119653546412823602194115506883191730229098656656148675288450465794412620701805411630849845729707087',
        y: '382541894983964690600293162993526991869438173208527886500815850372727490490048311900486843636684693220001234051265912000458425655926678741851522719141293453368701940787634131131196427632614127446128495491905145044221633881520859645274995287215391978093575963895028167371694057070023147521911999684763356037257097673911792867527883096328386171907773038204485470204595657681201490660401688164906946299164190680760257500808669498582862986527118065188947831650737443443357097875097317920241765784522696708021513408487224769269973358382952580868567815159167359342442935603924778373322260032811171703657045034945915068180793534715218521799021830059817105632423337977835717430573381512994650158949119647731472744313095838197029087455544614839618193123218393274500113565190237969194540716381907787190591680894096348619987465944314839217090897633240118907708728353977025942702693106124970322110442607454542840275031105740666888044262170783637186395453664958521125875844465859389112205599987204310138768154 921310117836693453278604471256064092734451809018012352357011096070124567848586327900704665937932950816991331801099649890210617795966726051925732113487988689469786194024598695027099070158275365734245304820270230893796520258396313809218890',
        x: '616914029784684855584714763340231492426100908655598976178651791609234807056421053678974092428484049715977123677899097157098622080979041003927320362108200586714799090933761996208900770559381734321267815567110342197287576060025703739925849141675379598311434697933729313626192885380020685335329593523683609103215285169226770018382824725553812040702257335748147376326047305998867888770159365634562244725476650780424134398942488222401859993782573792903020198868770888683341512671917249668225729306370351732926629458171105560538191103043275872688888584466859088043099329411213275826825557043830486585129455864229382917640721073590402279057985247862312161789404732832442295228432080975219571242951411904049824485202437265338712435017168333411682666572416980738892698829498421760253857943632271593969328472288492330564021179434722617280763223039329943080029254943467229417289060396673943590493918852192675127990512256579717957084720198671301881651767516973189185729965027130349998299701037240197132700980 314839484971221210667187937244266087926343180431454910347212397518641142169016005016264904729137249817095250718240286083681743398488217525519989102901338103699237904737924109523062555162939255331967791259668687674201147438796261750843089',
    };

    // generează cheia de criptare aleatorie
    const s =
        '207967822958110442178778278109830447433503852402785414821328709330349706312359283387206955571124544392109210639606384509083067520738417890305269373324678620850457624398942613053579091229263806574714035427029619796357685651219711112936206300136236554121413686413214781615737095413615972501136982626464802727651907543106754703441441867970819395278183757983355179097731548906256832974088244956504713377024931955849691572802532244064111313910004860917884899557614954275881853133846262202050937167007131258789440000321676167668782902794234299192316157418176379233048725674797860563914779298033729896033445543648327892278530279961688960419952711651675214205857184412263089450401851071510115939315543359563890816581201118807559534493006019524452621986959292183026635598059041969421186679562738320841257692505660048481680152158187087105039570206133866131147519932162950362812031235948074911811982616011007001800625736370940681178846920490275589689820196930672465994980780481940620705475248697225767799033066 552773631904422782173583218760970539001080545554938763429864207029045564378485380363928567848534012360219680344285059829947885084536196661274257662548943187519599088821053868299335512862744163973139401071913251452241673699504961828835';

    // criptează mesajul folosind cheia de criptare
    const message = 'bună lume';

    const encryptedMessage = așteptați encryptedMessage(
        exemplu.g,
        instance.p,
        instance.y,
        s,
        mesaj
    );

    // decriptează mesajul folosind cheia privată
    const decryptedMessage = așteaptă decryptMessage(
        exemplu.g,
        instance.p,
        instance.y,
        instance.x,
        encryptedMessage.encryptedMessage
    );

    // imprimă mesajul decriptat
    console.log(decryptedMessage.decryptedMessage.toString());

    // generează k (valoare aleatorie folosită pentru demonstrație)
    const k = '43220558864635999807222494006405093554136996639442848428660649627494977326549252015956167625409717501939970915776182709535802255795811841327046836399953716791075540818773199703512742170065176842043927032153944806168393033131469866779988322330018851536228388860561713802546578689369312782369404533158072022744548501692039130608319382563304975887798942458480662500270130601098019593667725143545363191217753380237250222901141034824798469842903765210911711501751016567993724752635072194431838765933477128899257778248163199965068482546743089633809030714406496903098905056163654500580764875020269656176493932912483710515353176910076542778955451295400108157021394642711661713862976144244100957162627006366276729583244531511985931597022491676138391838344972170566256288153920117605198636967029462530358874662921957916055616766268817026800742622247905256869803113700016379056840167099105056417246287607616947661572611991798680157261664484229188188610661717186706292831905428745003502252008744644920 8860329043240893517321165335791019471565786995296353746166068105298686142956437669545600524122590537823201925276349186461350793613350249464595214594694635689236568081217849150982922989123384819183607112825771749599283303037622596134255625592473';

    // creează dovada
    const proof = așteptați createDecryptionProof(
        k,
        exemplu.g,
        instance.p,
        s,
        encryptedMessage.encryptedMessage
    );

    // verifică dovada
    const verificare = așteaptă verifyDecryptionProof(
        exemplu.g,
        instance.p,
        instance.y,
        proof.proof.c,
        proof.proof.r,
        encryptedMessage.encryptedMessage,
        decryptedMessage.decryptedMessage.toString()
    );
}

crea dovada

funcția asincronă createDecryptionProof(k, g, p, s, _encryptedMessage) {
    încerca {
        const parsedK = Utils.parseBigInt(k);
        const parsedG = Utils.parseBigInt(g);
        const parsedP = Utils.parseBigInt(p);
        const parsedS = Utils.parseBigInt(s);

        const parsedA = Utils.parseBigInt(_encryptedMessage.a);
        const parsedB = Utils.parseBigInt(_encryptedMessage.b);

        // calculează c
        const c1 = parsedG.modPow(parsedK, parsedP);
        const c2 = parsedB.modPow(parsedK, parsedP);

        // concatnează c1 și c2
        const c = c1.toString() + c2.toString();

        // hash c
        const hashedC = await createHash(c);

        // convertesc c în număr
        const cNum = Utils.parseBigInt(hashedC.hashedPassword);
        const cReady = cNum.mod(parsedP);

        // calculează r
        const r = parsedK.subtract(cReady.multiply(parsedS));

        întoarcere {
            succes: adevărat,
            dovada: {
                c: cReady.toString(),
                r: r.toString(),
            },
        };
    } captură (eroare) {
        console.log(eroare);
        return { succes: false };
    }
}

verifica dovada

funcția asincronă verifyDecryptionProof(
    g,
    p,
    y,
    c,
    r,
    _encryptedMessage,
    _decryptedMessage
) {
    încerca {
        const parsedG = Utils.parseBigInt(g);
        const parsedP = Utils.parseBigInt(p);
        const parsedY = Utils.parseBigInt(y);
        const parsedC = Utils.parseBigInt(c);
        const parsedR = Utils.parseBigInt(r);

        const parsedA = Utils.parseBigInt(_encryptedMessage.a);
        const parsedB = Utils.parseBigInt(_encryptedMessage.b);
        const parsedMessage = Utils.parseBigInt(_decryptedMessage);

        // derivă P
        const P = analizatA
            .multiply(parsedMessage.modInverse(parsedP))
            .mod(parsedP);
        console.log(`P: ${P}`);

        // creând hash
        const mod1 = parsedG.modPow(parsedR, parsedP);
        const mod2 = parsedY.modPow(parsedC, parsedP);
        const mod3 = parsedB.modPow(parsedR, parsedP);
        const mod4 = P.modPow(parsedC, parsedP);

        // înmulțim modurile
        const hash1 = mod1.multiply(mod2).mod(parsedP);
        const hash2 = mod3.multiply(mod4).mod(parsedP);

        // concatnează modurile
        const hash = hash1.toString() + hash2.toString();

        // hash modurile concatenate
        const hashedProof = await createHash(hash);

        // convertește dovada hashed într-un număr
        const proof = Utils.parseBigInt(hashedProof.hashedPassword);
        const proofReady = proof.mod(parsedP);

        // înregistrează valorile
        console.log(`dovada: ${proofReady}`);
        console.log(`c: ${parsedC}`);
    } captură (eroare) {
        console.log(eroare);
        return { succes: false };
    }
}

GitHub Repo: https://github.com/Andrei-Florian/cryptosystem-public

kelalaka avatar
drapel in
Trimiteți mesajul înainte de criptare, apoi testați angajamentul (hash-commit este suficient) după decriptare?
Andrei Florian avatar
drapel br
Mulțumesc pentru răspuns @kelalaka, nu cred că acest lucru va funcționa pentru implementarea mea, deoarece aplicația nu are acces la buletinele de vot decriptate emise de alegător. Aplicația este concepută pentru alegeri cu reprezentare proporțională (poate vota mai mulți candidați). La introducerea selecției candidaților, alegătorul nu introduce direct candidații, ci textele lor cifrate (criptate anterior de aplicație). Ca urmare, aplicația nu are niciodată selecția candidatului în text clar a unui alegător din care să se angajeze. Ar exista o altă modalitate de a dovedi decriptarea?
Puncte:2
drapel es

Buletinele de vot recriptate amestecate, conform schemei de criptare El Gamal la care se face referire în anexa lucrării, vor fi sub forma $(X', Y')$. Trebuie să dovedim că mesajul de vot declarat $M$ este cu adevărat calculată ca $M = X'-sY'$, Unde $s$ este aceeași cheie privată legată de cheia publică $Z = sG$ pe care alegătorul la folosit inițial pentru a cripta buletinul de vot.

Verificatorul calculează mai întâi $P=(X'-M)$. Trebuie să dovedim verificatorului că $ P \overset{?}{=} sY'$.

Pentru a face acest lucru, trebuie să oferim o dovadă a Equivalenței logaritmului discret (DLEQ), care să demonstreze că cheia privată pentru cheia publică $Z$ pe punctul de bază $G$ este aceeași cheie privată pentru cheia publică $P$ pe punctul de bază $Y'$.

Dovada DLEQ $(c,r)$ se calculează după cum urmează:

Dovatorul

  • selectează un scalar uniform aleatoriu $k$

  • calculează $c=H_s(kG\mathbin\|kY')$

    Aici $H_s$ înseamnă un hash sigur din punct de vedere criptografic care produce o valoare scalară) și

  • $r = k - cs$.

    Toate operațiile scalare sunt modificate în ordinea punctului de bază.

Verificatorul (c,r,G,P,Z,Y')

  • Dovada DLEQ este verificată prin verificare $c\overset{?}{=}H_s(rG+cZ \mathbin\| rY'+cP)$.

\begin{align} H_s(kG - csG + cZ \mathbin\| kY' - csY' + cP)\ & =H_s(kG \color{red}{- cZ + cZ} \mathbin\| kY' \color{red}{ - cP' + cP})\ & = H_s(kG \mathbin\| kY')\ & = c\ \end{align}

Pentru a converti acest lucru din notație aditivă în notație multiplicativă, trebuie doar să înlocuiți adunarea/scăderea punctelor cu înmulțirea/împărțirea și înlocuiți înmulțirea punctelor cu exponențiația cu scalarul ca exponent.

Prin urmare, în notație multiplicativă: Dacă primul tău este $p$ iar dimensiunea grupului dvs. ciclic este $\ell$, apoi calculezi $P=X' \cdot (M^{-1}\ mod\ p)\ mod\ p$ (Unde $M^{-1}\ mod\ p$ înseamnă invers modular multiplicativ), $c=H_s(G^k\ mod\ p \mathbin\| Y'^k\ mod\ p)$, $r=k-cs\ mod\ \ell$, apoi verificați $c\overset{?}{=}H_s((G^r\ mod\ p) \cdot (Z^c\ mod\ p) \ mod\ p \mathbin\| (Y'^r \ mod\ p) \cdot (P^c\ mod\ p)\ mod\ p)$.

kelalaka avatar
drapel in
După cum puteți vedea, am editat în mare măsură răspunsul pentru a fi mai clar. Puteți folosi $\overset{?}{=}$ (`\overset{?}{=}`) în loc de $==$
knaccc avatar
drapel es
@kelalaka mulțumesc
Andrei Florian avatar
drapel br
Bună, mulțumesc pentru răspuns. Am câteva întrebări. În primul rând, nu sunt obișnuit să citesc această notație și nu sunt sigur ce || denotă, cum ar fi tradus acest simbol în cod? Pot folosi SHA256 ca funcție hash? Și, în sfârșit, asigurându-vă că G reprezintă generatorul de grup.
knaccc avatar
drapel es
@AndreiFlorian || înseamnă concatenare. De exemplu. dacă utilizați curve25519, atunci punctele EC sunt de 32 de octeți, iar dacă le concatenați înainte de hashing, aveți 64 de octeți în curs de hashing. Da, G este generatorul de grup. SHA256 este bine în acest exemplu particular, dar apoi modificați-l cu ordinea punctului de bază pentru a vă asigura că rezultatul este un scalar valid. Btw, aș greși întotdeauna din partea precauției și aș folosi un hash care nu este vulnerabil la atacurile de extensie de lungime, cum ar fi SHA512 trunchiat la 256 de biți.
Andrei Florian avatar
drapel br
Mulțumesc pentru asta, se pare că mă lupt cu conversia la notație multiplicativă, nu sunt 100% sigur ce semne să schimb și pe care să păstrez aceleași. Am dreptate când spun că: c=H((G^k)modp || (Y'^k)modp)modp, r=(k-cs)modp (la fel), P=(X'-M)modp (la fel), c=(([G^r]modp) * ([Z^c]modp)modp || ([Y'^r]modp) * ([P^c]modp)modp)modp? Vă mulțumesc din nou pentru timpul acordat și scuze pentru notația slabă.
knaccc avatar
drapel es
@AndreiFlorian este X'/M în loc de X'-M când se convertește la notație multiplicativă.
Andrei Florian avatar
drapel br
@knaccc, sunt destul de sigur că fac ceva greșit. Ați avea timp să scrieți demonstrația în notație multiplicativă? Am încercat să schimb semnele de câteva ore și încă nu pot obține dovada pentru a verifica. Mulţumesc mult.
knaccc avatar
drapel es
@AndreiFlorian Când se fac implementări EC, operațiile scalare sunt modificate în ordinea punctului de bază. Dar dacă utilizați exponențiarea normală și nu folosiți scalari EC, atunci nu faceți $mod$ pe partea $k-cs$ atunci când calculați $r$ (nu în scădere și nu în înmulțire). Acest lucru ar trebui să o rezolve. În rezumat, nu utilizați $mod$ și nu modificați niciun operator atunci când calculați $r = k-cs$, dar peste tot utilizați $mod p$ și convertiți adunarea în înmulțire, scăderea în împărțire și înmulțirea în exponențiere. Anunță-mă dacă asta se rezolvă.
Andrei Florian avatar
drapel br
@knaccc, am încercat schimbarea, dar tot nu funcționează. Mă întreb dacă ar fi mai ușor dacă aș împărtăși codul cu tine. L-am atasat postarii. Lucrez în JavaScript, codul pe care l-am atașat la întrebare are 3 metode (cu unele metode gestionând anumite operații). Am adăugat un link către depozitul GitHub unde am incluse toate metodele de ajutor. Mulțumesc încă o dată pentru timpul acordat, apreciez foarte mult :).
knaccc avatar
drapel es
@AndreiFlorian sunt multe de lucrat și de depanat acolo. Vă recomand să începeți prin a verifica dacă puteți găsi două numere aleatoare $b$ și $c$, să calculați $a = b + c$ și apoi să verificați dacă puteți calcula cu succes acel $g^a mod p == (g^b mod p * g^c mod p) mod p$. Dacă puteți ajunge atât de departe, atunci începeți să verificați dacă subcomponentele algebrei de mai sus funcționează corect, de ex. că $G^k mod p == (G^r mod p * Z^c mod p) mod p$. Probabil că aveți o eroare simplă de codare undeva.
knaccc avatar
drapel es
Ah, cred că știu ce e în neregulă. Două lucruri: în primul rând, asigurați-vă că „diviziunea” folosește modul invers, și nu diviziunea obișnuită. În al doilea rând, deși exponențiațiile trebuie să fie $mod p$, operațiile scalare trebuie și ele modificate, dar nu cu $p$. Acestea trebuie modificate cu dimensiunea grupului de $g$. Mărimea acestui grup va depinde de primul pe care l-ați ales. Uneori este doar $p-1$, dar ar putea exista multe grupuri ciclice mari, deci ar putea lua forma $(p-1)/n$, unde n este un cofactor pe care ar trebui să-l cunoașteți pentru primul. Fac rar astfel de implementări mai mari decât EC, așa că sunt puțin ruginit.
Andrei Florian avatar
drapel br
Bună, sunt destul de sigur că fac diviziunile corect (înmulțire prin inversul modului). În ceea ce privește modificările, pot confirma că dimensiunea grupului este p-1, totuși nu sunt sigur unde să folosesc asta și unde să folosesc p. Ați putea include unde sunt utilizate acestea în formulele din răspuns. Cred că asta ar rezolva problema. Iti multumesc din nou.
knaccc avatar
drapel es
L-am adăugat. Asigurați-vă că aveți disponibilă o bibliotecă de multiplicare inversă modulară adecvată pentru a face $M^{-1}\ mod\ p$. Btw pentru a face acest lucru mai puțin predispus la erori, vă recomand să aveți clase de elemente scalare și de grup, cu metode care vor aplica automat $mod\ p$ sau $mod\ \ell$ pentru dvs., astfel încât să nu aveți cod plin de $mod$ peste tot și astfel încât să clasificați întotdeauna corect ce este un element de grup și ce este un scalar.
Andrei Florian avatar
drapel br
Mulțumesc mult! M-am uitat peste el și am făcut câteva modificări și a verificat. Ești un salvator!

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.