I am working on a project that uses ElGamal cryptography using multiplicative notation. The project is an internet voting implementation that uses the cryptosystem to encrypt the received ballots, re-encrypt and shuffle them, and then finally decrypt them. I am basing the project on this paper (https://www.usenix.org/conference/evt-06/simple-verifiable-elections).
I know how to provide proof of correctness for the encryption and subsequent re-encryptions. But I am not sure how to do this for the decryption.
main function
async function testDecryptProof() {
// create instance
const instance = {
g: '578581162149404798490571324493050333821753231896276896347588934236801486075345228356031089034308080355169502516970783985992465797790164077579971312181422206518964809883668939849570386967992767051369301215310754209280449807411021102153029377771783635510279329651149063858558329423219030908013960533321414499048784570490530207084776596253913339841694321299265784157923029847261603752469185349628532689446592521898507856757944009320377006868172969323251633981722550110871375408446896988161342745052895534300357801608217690146321171241606375301572941706622980330319103629192157393821194824468143500823157190887876038021286294694041671207075207845465680928059613160518275520282872421869149103173333949258329687311303065379518852070463040315621848668909908323797263963006103095659510784649320024411908921807300979021343984882137053231099693459838679137130760178994756250748747915572916102102876710115689234104349836600282068293111526381083439422743411854769767922191654138690358405340374558063855405817898848980774741636240733553597229888674227126306560767485612428694999914792050501101312713302487481236334084764126207814284673857139915086576279907709746386734910200293561256639347096905974796093763848648123958776190861142984370193373964',
p: '677088805808970643479133732614124310412316623451218811091733045838654739392363246453577008799155078839179531842224968947275228243113309850038122844034206790202276653380214548364178679947759556696213093774565712592343240601574723204104637149412506691550790846672244951946792272265332057245338838114080139164225120755358666371656799563377820758711742540625164732489435107295380237174828977225345274146615784182060315544480619981291902484596100159217062987931193501343478984350495475702937235166238839021800138523942802532967536519581875286415594806347061067009294601218779715836970031767680879370919882661828875007748699870086971737821411346178288109455141870605199207659215196027250095379359566675689788259770429733392884433737152092042439686604640479912921568537010168396445693348455112670632809025917594376152255614259482541945870534263328423690524049145709753098095473739179196969320905245503058104512347909553056470869228505715399271424136417025630569603129329944058750767224129798692688740617502975582916178170805288244361290828581356312322935742661288429293532378052789528032585149311919895258686737427981082058024550795015310013119653546412823602194115506883191730229098656656148675288450465794412620701805411630849845729707087',
y: '382541894983964690600293162993526991869438173208527886500815850372727490490048311900486843636684693220001234051265912000458425655926678741851522719141293453368701940787634131131196427632614127446128495491905145044221633881520859645274995287215391978093575963895028167371694057070023147521911999684763356037257097673911792867527883096328386171907773038204485470204595657681201490660401688164906946299164190680760257500808669498582862986527118065188947831650737443443357097875097317920241765784522696708021513408487224769269973358382952580868567815159167359342442935603924778373322260032811171703657045034945915068180793534715218521799021830059817105632423337977835717430573381512994650158949119647731472744313095838197029087455544614839618193123218393274500113565190237969194540716381907787190591680894096348619987465944314839217090897633240118907708728353977025942702693106124970322110442607454542840275031105740666888044262170783637186395453664958521125875844465859389112205599987204310138768154921310117836693453278604471256064092734451809018012352357011096070124567848586327900704665937932950816991331801099649890210617795966726051925732113487988689469786194024598695027099070158275365734245304820270230893796520258396313809218890',
x: '616914029784684855584714763340231492426100908655598976178651791609234807056421053678974092428484049715977123677899097157098622080979041003927320362108200586714799090933761996208900770559381734321267815567110342197287576060025703739925849141675379598311434697933729313626192885380020685335329593523683609103215285169226770018382824725553812040702257335748147376326047305998867888770159365634562244725476650780424134398942488222401859993782573792903020198868770888683341512671917249668225729306370351732926629458171105560538191103043275872688888584466859088043099329411213275826825557043830486585129455864229382917640721073590402279057985247862312161789404732832442295228432080975219571242951411904049824485202437265338712435017168333411682666572416980738892698829498421760253857943632271593969328472288492330564021179434722617280763223039329943080029254943467229417289060396673943590493918852192675127990512256579717957084720198671301881651767516973189185729965027130349998299701037240197132700980314839484971221210667187937244266087926343180431454910347212397518641142169016005016264904729137249817095250718240286083681743398488217525519989102901338103699237904737924109523062555162939255331967791259668687674201147438796261750843089',
};
// generate random encryption key
const s =
'207967822958110442178778278109830447433503852402785414821328709330349706312359283387206955571124544392109210639606384509083067520738417890305269373324678620850457624398942613053579091229263806574714035427029619796357685651219711112936206300136236554121413686413214781615737095413615972501136982626464802727651907543106754703441441867970819395278183757983355179097731548906256832974088244956504713377024931955849691572802532244064111313910004860917884899557614954275881853133846262202050937167007131258789440000321676167668782902794234299192316157418176379233048725674797860563914779298033729896033445543648327892278530279961688960419952711651675214205857184412263089450401851071510115939315543359563890816581201118807559534493006019524452621986959292183026635598059041969421186679562738320841257692505660048481680152158187087105039570206133866131147519932162950362812031235948074911811982616011007001800625736370940681178846920490275589689820196930672465994980780481940620705475248697225767799033066552773631904422782173583218760970539001080545554938763429864207029045564378485380363928567848534012360219680344285059829947885084536196661274257662548943187519599088821053868299335512862744163973139401071913251452241673699504961828835';
// encrypt the message using the encryption key
const message = 'hello world';
const encryptedMessage = await encryptMessage(
instance.g,
instance.p,
instance.y,
s,
message
);
// decrypt the message using the private key
const decryptedMessage = await decryptMessage(
instance.g,
instance.p,
instance.y,
instance.x,
encryptedMessage.encryptedMessage
);
// print the decrypted message
console.log(decryptedMessage.decryptedMessage.toString());
// generate k (random value used for proof)
const k = '432205588646359998072224940064050935541369966394428484286606496274949773265492520159561676254097175019399709157761827095358022557958118413270468363999537167910755408187731997035127421700651768420439270321539448061683930331314698667799883223300188515362283888605617138025465786893693127823694045331580720227445485016920391306083193825633049758877989424584806625002701306010980195936677251435453631912177533802372502229011410348247984698429037652109117115017510165679937247526350721944318387659334771288992577782481631999650684825467430896338090307144064969030989050561636545005807648750202696561764939329124837105153531769100765427789554512954001081570213946427116617138629761442441009571626270063662767295832445315119859315970224916761383918383449721705662562881539201176051986369670294625303588746629219579160556167662688170268007426222479052568698031137000163790568401670991050564172462876076169476615726119917986801572616644842291881886106617171867062928319054287450035022520087446449208860329043240893517321165335791019471565786995296353746166068105298686142956437669545600524122590537823201925276349186461350793613350249464595214594694635689236568081217849150982922989123384819183607112825771749599283303037622596134255625592473';
// create proof
const proof = await createDecryptionProof(
k,
instance.g,
instance.p,
s,
encryptedMessage.encryptedMessage
);
// verify proof
const verification = await verifyDecryptionProof(
instance.g,
instance.p,
instance.y,
proof.proof.c,
proof.proof.r,
encryptedMessage.encryptedMessage,
decryptedMessage.decryptedMessage.toString()
);
}
create proof
async function createDecryptionProof(k, g, p, s, _encryptedMessage) {
try {
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);
// calculate c
const c1 = parsedG.modPow(parsedK, parsedP);
const c2 = parsedB.modPow(parsedK, parsedP);
// concatnate c1 and c2
const c = c1.toString() + c2.toString();
// hash c
const hashedC = await createHash(c);
// convert c to number
const cNum = Utils.parseBigInt(hashedC.hashedPassword);
const cReady = cNum.mod(parsedP);
// calculate r
const r = parsedK.subtract(cReady.multiply(parsedS));
return {
success: true,
proof: {
c: cReady.toString(),
r: r.toString(),
},
};
} catch (error) {
console.log(error);
return { success: false };
}
}
verify proof
async function verifyDecryptionProof(
g,
p,
y,
c,
r,
_encryptedMessage,
_decryptedMessage
) {
try {
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);
// derive P
const P = parsedA
.multiply(parsedMessage.modInverse(parsedP))
.mod(parsedP);
console.log(`P: ${P}`);
// creating 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);
// multiply the mods
const hash1 = mod1.multiply(mod2).mod(parsedP);
const hash2 = mod3.multiply(mod4).mod(parsedP);
// concatnate the mods
const hash = hash1.toString() + hash2.toString();
// hash the concatenated mods
const hashedProof = await createHash(hash);
// convert the hashed proof to a number
const proof = Utils.parseBigInt(hashedProof.hashedPassword);
const proofReady = proof.mod(parsedP);
// log the values
console.log(`proof: ${proofReady}`);
console.log(`c: ${parsedC}`);
} catch (error) {
console.log(error);
return { success: false };
}
}
GitHub Repo: https://github.com/Andrei-Florian/cryptosystem-public