Регистрация Войти
Рейтинг:1
Andrei Florian avatar Crypto

Как доказать правильность расшифровки в криптосистеме Эль-Гамаля

флаг br
Andrei Florian

Я работаю над проектом, в котором используется криптография Эль-Гамаля с использованием мультипликативной записи. Проект представляет собой реализацию интернет-голосования, которая использует криптосистему для шифрования полученных бюллетеней, повторного шифрования и перемешивания их, а затем, наконец, их расшифровки. Я основываю проект на этой бумаге (https://www.usenix.org/conference/evt-06/simple-проверяемые-выборы).

Я знаю, как предоставить доказательство правильности шифрования и последующего повторного шифрования. Но я не уверен, как это сделать для расшифровки.

основная функция

асинхронная функция testDecryptProof() {
    // создать экземпляр
    константный экземпляр = {
        g: '578581162149404798490571324493050333821753231896276896347588934236801486075345228356031089034308080355169502516970783985992465797790164077579971312181422206518964809883668939849570386967992767051369301215310754209280449807411021102153029377771783635510279329651149063858558329423219030908013960533321414499048784570490530207084776596253913339841694321299265784157923029847261603752469185349628532689446592521898507856757944009320377006868172969323251633981722550110871375408446896988161342745052895534300357801608217690146321171241606375301572941706622980330319103629192157393821194824468143500823157190887876038021286294694041671207075207845465680928059613160518275520282872421869149103173333949258329687311303065379518852070463040315621848668909908323797263963006103095659510784649320024411908921807300979021343984882137053231099693459838679137130760178994756250748747915572916102102876710115689234104349836600282068293111526381083439422743411854769767922191654138690358405340374558063855405817 898848980774741636240733553597229888674227126306560767485612428694999914792050501101312713302487481236334084764126207814284673857139915086576279907709746386734910200293561256639347096905974796093763848648123958776190861142984370193373964',
        p: '677088805808970643479133732614124310412316623451218811091733045838654739392363246453577008799155078839179531842224968947275228243113309850038122844034206790202276653380214548364178679947759556696213093774565712592343240601574723204104637149412506691550790846672244951946792272265332057245338838114080139164225120755358666371656799563377820758711742540625164732489435107295380237174828977225345274146615784182060315544480619981291902484596100159217062987931193501343478984350495475702937235166238839021800138523942802532967536519581875286415594806347061067009294601218779715836970031767680879370919882661828875007748699870086971737821411346178288109455141870605199207659215196027250095379359566675689788259770429733392884433737152092042439686604640479912921568537010168396445693348455112670632809025917594376152255614259482541945870534263328423690524049145709753098095473739179196969320905245503058104512347909553056470869228505715399271424136417025630569603129329944058750767224129798692688740617 502975582916178170805288244361290828581356312322935742661288429293532378052789528032585149311919895258686737427981082058024550795015310013119653546412823602194115506883191730229098656656148675288450465794412620701805411630849845729707087',
        y: '382541894983964690600293162993526991869438173208527886500815850372727490490048311900486843636684693220001234051265912000458425655926678741851522719141293453368701940787634131131196427632614127446128495491905145044221633881520859645274995287215391978093575963895028167371694057070023147521911999684763356037257097673911792867527883096328386171907773038204485470204595657681201490660401688164906946299164190680760257500808669498582862986527118065188947831650737443443357097875097317920241765784522696708021513408487224769269973358382952580868567815159167359342442935603924778373322260032811171703657045034945915068180793534715218521799021830059817105632423337977835717430573381512994650158949119647731472744313095838197029087455544614839618193123218393274500113565190237969194540716381907787190591680894096348619987465944314839217090897633240118907708728353977025942702693106124970322110442607454542840275031105740666888044262170783637186395453664958521125875844465859389112205599987204310138768154 921310117836693453278604471256064092734451809018012352357011096070124567848586327900704665937932950816991331801099649890210617795966726051925732113487988689469786194024598695027099070158275365734245304820270230893796520258396313809218890',
        x: '616914029784684855584714763340231492426100908655598976178651791609234807056421053678974092428484049715977123677899097157098622080979041003927320362108200586714799090933761996208900770559381734321267815567110342197287576060025703739925849141675379598311434697933729313626192885380020685335329593523683609103215285169226770018382824725553812040702257335748147376326047305998867888770159365634562244725476650780424134398942488222401859993782573792903020198868770888683341512671917249668225729306370351732926629458171105560538191103043275872688888584466859088043099329411213275826825557043830486585129455864229382917640721073590402279057985247862312161789404732832442295228432080975219571242951411904049824485202437265338712435017168333411682666572416980738892698829498421760253857943632271593969328472288492330564021179434722617280763223039329943080029254943467229417289060396673943590493918852192675127990512256579717957084720198671301881651767516973189185729965027130349998299701037240197132700980 314839484971221210667187937244266087926343180431454910347212397518641142169016005016264904729137249817095250718240286083681743398488217525519989102901338103699237904737924109523062555162939255331967791259668687674201147438796261750843089',
    };

    // генерируем случайный ключ шифрования
    константа с =
        '207967822958110442178778278109830447433503852402785414821328709330349706312359283387206955571124544392109210639606384509083067520738417890305269373324678620850457624398942613053579091229263806574714035427029619796357685651219711112936206300136236554121413686413214781615737095413615972501136982626464802727651907543106754703441441867970819395278183757983355179097731548906256832974088244956504713377024931955849691572802532244064111313910004860917884899557614954275881853133846262202050937167007131258789440000321676167668782902794234299192316157418176379233048725674797860563914779298033729896033445543648327892278530279961688960419952711651675214205857184412263089450401851071510115939315543359563890816581201118807559534493006019524452621986959292183026635598059041969421186679562738320841257692505660048481680152158187087105039570206133866131147519932162950362812031235948074911811982616011007001800625736370940681178846920490275589689820196930672465994980780481940620705475248697225767799033066 552773631904422782173583218760970539001080545554938763429864207029045564378485380363928567848534012360219680344285059829947885084536196661274257662548943187519599088821053868299335512862744163973139401071913251452241673699504961828835';

    // зашифровать сообщение с помощью ключа шифрования
    const message = 'привет, мир';

    const зашифрованное сообщение = ожидание зашифрованного сообщения (
        экземпляр.г,
        экземпляр.p,
        экземпляр.у,
        с,
        сообщение
    );

    // расшифровать сообщение с помощью закрытого ключа
    const decryptedMessage = ожидание расшифровки сообщения (
        экземпляр.г,
        экземпляр.p,
        экземпляр.у,
        экземпляр.x,
        зашифрованное сообщение. зашифрованное сообщение
    );

    // вывести расшифрованное сообщение
    console.log(decryptedMessage.decryptedMessage.toString());

    // сгенерировать k (случайное значение, используемое для доказательства)
    const k = '43220558864635999807222494006405093554136996639442848428660649627494977326549252015956167625409717501939970915776182709535802255795811841327046836399953716791075540818773199703512742170065176842043927032153944806168393033131469866779988322330018851536228388860561713802546578689369312782369404533158072022744548501692039130608319382563304975887798942458480662500270130601098019593667725143545363191217753380237250222901141034824798469842903765210911711501751016567993724752635072194431838765933477128899257778248163199965068482546743089633809030714406496903098905056163654500580764875020269656176493932912483710515353176910076542778955451295400108157021394642711661713862976144244100957162627006366276729583244531511985931597022491676138391838344972170566256288153920117605198636967029462530358874662921957916055616766268817026800742622247905256869803113700016379056840167099105056417246287607616947661572611991798680157261664484229188188610661717186706292831905428745003502252008744644920 8860329043240893517321165335791019471565786995296353746166068105298686142956437669545600524122590537823201925276349186461350793613350249464595214594694635689236568081217849150982922989123384819183607112825771749599283303037622596134255625592473';

    // создать доказательство
    const proof = await createDecryptionProof(
        к,
        экземпляр.г,
        экземпляр.p,
        с,
        зашифрованное сообщение. зашифрованное сообщение
    );

    // проверить доказательство
    константная проверка = ожидание проверкиDecryptionProof(
        экземпляр.г,
        экземпляр.p,
        экземпляр.у,
        доказательство.доказательство.с,
        пруф.пруф.р,
        зашифрованное сообщение. зашифрованное сообщение,
        decryptedMessage.decryptedMessage.toString()
    );
}

создать доказательство

асинхронная функция createDecryptionProof (k, g, p, s, _encryptedMessage) {
    пытаться {
        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);

        // вычислить с
        const c1 = parsedG.modPow(parsedK, parsedP);
        const c2 = parsedB.modPow(parsedK, parsedP);

        // конкатенировать c1 и c2
        const c = c1.toString() + c2.toString();

        // хэш с
        const hashedC = await createHash(c);

        // преобразовать c в число
        const cNum = Utils.parseBigInt(hashedC.hashedPassword);
        const cReady = cNum.mod(parsedP);

        // вычислить r
        const r = parsedK.subtract(cReady.multiply(parsedS));

        возвращаться {
            успех: правда,
            доказательство: {
                c: cReady.toString(),
                р: r.toString(),
            },
        };
    } поймать (ошибка) {
        console.log(ошибка);
        вернуть {успех: ложь};
    }
}

проверить доказательство

асинхронная функция VerifyDecryptionProof(
    г,
    п,
    у,
    в,
    р,
    _зашифрованное сообщение,
    _decryptedMessage
) {
    пытаться {
        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);

        // вывести P
        const P = проанализированоA
            .multiply(parsedMessage.modInverse(parsedP))
            .mod(разобранныйP);
        console.log(`P: ${P}`);

        // создание хеша
        const mod1 = parsedG.modPow(parsedR, parsedP);
        const mod2 = parsedY.modPow(parsedC, parsedP);
        const mod3 = parsedB.modPow(parsedR, parsedP);
        const mod4 = P.modPow(parsedC, parsedP);

        // умножить моды
        const hash1 = mod1.multiply(mod2).mod(parsedP);
        const hash2 = mod3.multiply(mod4).mod(parsedP);

        // объединяем моды
        const hash = hash1.toString() + hash2.toString();

        // хешируем соединенные моды
        const hashedProof = await createHash(хеш);

        // преобразовать хешированное доказательство в число
        const proof = Utils.parseBigInt(hashedProof.hashedPassword);
        const proofReady = proof.mod(parsedP);

        // регистрируем значения
        console.log(`доказательство: ${proofReady}`);
        console.log(`c: ${parsedC}`);
    } поймать (ошибка) {
        console.log(ошибка);
        вернуть {успех: ложь};
    }
}

Репозиторий GitHub: https://github.com/Andrei-Florian/cryptosystem-public

211
0 + 0
kelalaka avatar
флаг in
kelalaka
Зафиксировать сообщение перед шифрованием, а затем проверить фиксацию (достаточно хэш-фиксации) после расшифровки?
0
Ответить
Andrei Florian avatar
флаг br
Andrei Florian
Спасибо за ответ @kelalaka, я не думаю, что это сработает для моей реализации, так как приложение не имеет доступа к расшифрованным бюллетеням, поданным избирателем. Приложение предназначено для выборов по пропорциональному представительству (можно голосовать за нескольких кандидатов). Вводя свой выбор кандидатов, избиратель вводит не кандидатов напрямую, а их зашифрованные зашифрованные тексты (ранее зашифрованные приложением). В результате приложение никогда не имеет выбор кандидата в виде открытого текста избирателя, на основе которого можно создать обязательство. Есть ли другой способ доказать расшифровку?
0
Ответить
Рейтинг:2
knaccc avatar Crypto
флаг es
knaccc

Перетасованные повторно зашифрованные бюллетени в соответствии со схемой шифрования Эль-Гамаля, упомянутой в приложении к статье, будут иметь вид $(Х', Y')$. Нам нужно доказать, что объявленное бюллетенем сообщение $ млн $ действительно рассчитывается как $M = X'-sY'$, куда $s$ тот же закрытый ключ, связанный с открытым ключом $Z = sG$ который избиратель первоначально использовал для шифрования бюллетеня.

Проверяющий сначала вычисляет $P=(X'-M)$. Нам нужно доказать верификатору, что $ P \overset{?}{=} sY'$.

Для этого нам нужно предоставить доказательство эквивалентности дискретного логарифма (DLEQ), демонстрирующее, что закрытый ключ для открытого ключа $Z$ на базовой точке $G$ это тот же закрытый ключ для открытого ключа $P$ на базовой точке $Y'$.

Доказательство DLEQ $(с,г)$ рассчитывается следующим образом:

Доказательство

  • выбирает равномерный случайный скаляр $к$

  • вычисляет $c=H_s(kG\mathbin\|kY')$

    Здесь $H_s$ означает криптографически безопасный хэш, который создает скалярное значение), и

  • $r = k - cs$.

    Все скалярные операции выполняются в порядке базовой точки.

Верификатор (c,r,G,P,Z,Y')

  • Доказательство DLEQ проверяется проверкой $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{выравнивание}

Чтобы преобразовать это из аддитивной записи в мультипликативную запись, просто замените сложение/вычитание точек на умножение/деление и замените умножение точек на возведение в степень со скаляром в качестве показателя степени.

Следовательно, в мультипликативной записи: если ваше простое число равно $р$ и размер вашей циклической группы $\ell$, то вы вычисляете $P=X' \cdot (M^{-1}\ mod\ p)\ mod\ p$ (куда $M^{-1}\ mod\ p$ означает мультипликативную модулярную инверсию), $c=H_s(G^k\ mod\ p \mathbin\| Y'^k\ mod\ p)$, $r=k-cs\мод\ell$, затем проверьте $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)$.

0 + 0
kelalaka avatar
флаг in
kelalaka
Как видите, я сильно отредактировал ответ, чтобы сделать его более понятным. Вы можете использовать $\overset{?}{=}$ (`\overset{?}{=}`) вместо $==$
1
Ответить
knaccc avatar
флаг es
knaccc
@kelalaka спасибо
0
Ответить
Andrei Florian avatar
флаг br
Andrei Florian
Привет, спасибо за ответ. У меня есть несколько вопросов. Во-первых, я не привык читать эту нотацию и не уверен, что || обозначает, как этот символ будет переведен в код? Могу ли я использовать SHA256 в качестве хеш-функции? И, наконец, просто убедитесь, что G представляет собой генератор группы.
0
Ответить
knaccc avatar
флаг es
knaccc
@АндрейФлориан || означает конкатенацию. Например. если вы использовали curve25519, то точки EC составляют 32 байта, и если вы объедините их до хеширования, у вас будет хешировано 64 байта. Да, G — генератор группы. SHA256 хорош в этом конкретном примере, но затем измените его с порядком базовой точки, чтобы гарантировать, что результат является допустимым скаляром. Кстати, я бы всегда ошибался из-за осторожности и использовал хеш, который не уязвим для атак с расширением длины, таких как SHA512, усеченный до 256 бит.
0
Ответить
Andrei Florian avatar
флаг br
Andrei Florian
Спасибо за это, я, кажется, борюсь с преобразованием в мультипликативную запись, я не уверен на 100%, какие знаки изменить, а какие оставить прежними. Правильно ли я говорю, что: c=H((G^k)modp || (Y'^k)modp)modp, r=(k-cs)modp (то же самое), P=(X'-M)modp (то же самое), c=(([G^r]modp) * ([Z^c]modp)modp || ([Y'^r]modp) * ([P^c]modp)modp)modp? Еще раз спасибо за потраченное время и извините за плохую запись.
0
Ответить
knaccc avatar
флаг es
knaccc
@AndreiFlorian это X '/ M вместо X'-M при преобразовании в мультипликативную запись.
0
Ответить
Andrei Florian avatar
флаг br
Andrei Florian
@knaccc, я совершенно уверен, что делаю что-то не так. Найдется ли у вас время написать доказательство в мультипликативной записи? Я пытался переключить знаки в течение нескольких часов и до сих пор не могу получить доказательство, чтобы проверить. Большое спасибо.
0
Ответить
knaccc avatar
флаг es
knaccc
@AndreiFlorian При реализации EC скалярные операции изменяются в порядке базовой точки. Но если вы используете нормальное возведение в степень и не используете скаляры EC, то вы не делаете $mod$ на части $k-cs$ при вычислении $r$ (ни при вычитании, ни при умножении). Это должно исправить это. Таким образом, не используйте $mod$ и не изменяйте никакие операторы при вычислении $r = k-cs$, но везде используйте $mod p$ и преобразуйте сложение в умножение, вычитание в деление и умножение в возведение в степень. Дайте мне знать, если это исправит это.
0
Ответить
Andrei Florian avatar
флаг br
Andrei Florian
@knaccc, я попробовал это изменение, но оно все еще не работает. Мне интересно, было бы проще, если бы я поделюсь с вами кодом. Я прикрепил его к сообщению. Я работаю в JavaScript, код, который я прикрепил к вопросу, имеет 3 метода (с некоторыми методами, обрабатывающими определенные операции). Я добавил ссылку на репозиторий GitHub, в который включены все вспомогательные методы. Еще раз спасибо за время, я действительно ценю это :).
0
Ответить
knaccc avatar
флаг es
knaccc
@AndreiFlorian, там есть над чем поработать и отладить. Я бы рекомендовал вам начать с проверки того, что вы можете подобрать два случайных числа $b$ и $c$, вычислить $a = b + c$, а затем проверить, что вы можете успешно вычислить, что $g^a mod p == (g^b по модулю p * g^c по модулю p) по модулю p$. Если вы можете зайти так далеко, начните проверять, правильно ли работают подкомпоненты вышеприведенной алгебры, например. что $G^k mod p == (G^r mod p * Z^c mod p) mod p$. Вероятно, у вас где-то есть простая ошибка кодирования.
0
Ответить
knaccc avatar
флаг es
knaccc
Ах, кажется, я знаю, что не так. Две вещи: во-первых, убедитесь, что «деление» использует модинверсное, а не обычное деление. Во-вторых, хотя возведение в степень должно быть $mod p$, скалярные операции также должны модифицироваться, но не с $p$. Они должны быть модифицированы с размером группы $g$. Размер этой группы будет зависеть от выбранного вами прайма. Иногда это просто $p-1$, но может быть и много больших циклических групп, поэтому он может иметь вид $(p-1)/n$, где n — это сомножитель, который вам нужно знать для простого числа. Я редко делаю такие реализации, превышающие размер EC, поэтому я немного заржавел.
1
Ответить
Andrei Florian avatar
флаг br
Andrei Florian
Привет, я совершенно уверен, что правильно делаю деления (умножаю на обратный модуль). Что касается модов, я могу подтвердить, что размер группы равен p-1, однако я не уверен, где это использовать и где использовать p. Не могли бы вы указать, где они используются в формулах в ответе. Думаю, это решит проблему. Еще раз спасибо.
0
Ответить
knaccc avatar
флаг es
knaccc
Я добавил его. Убедитесь, что у вас есть подходящая модульная библиотека обратного умножения для выполнения $M^{-1}\ mod\ p$. Кстати, чтобы сделать это менее подверженным ошибкам, я рекомендую вам иметь скалярные и групповые классы элементов с методами, которые будут автоматически применять $mod\p$ или $mod\ell$ для вас, чтобы у вас не было кода, замусоренного $mod$ везде и чтобы вы всегда правильно классифицировали, что является групповым элементом, а что скаляром.
1
Ответить
Andrei Florian avatar
флаг br
Andrei Florian
Спасибо огромное! Я просмотрел его и внес некоторые изменения, и он проверяется. Ты спаситель!
1
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.