Revisão do protocolo criptográfico do sistema de votação eletrônica remota

Neste artigo, analisaremos os detalhes da implementação do protocolo criptográfico do sistema de votação eletrônica remota.



A utilização de mecanismos e algoritmos criptográficos em várias fases do processo eleitoral confere ao sistema de votação à distância as propriedades necessárias. Vamos dar uma olhada mais de perto e considerar os estágios da votação descritos no artigo de visão geral .



Inicialização do sistema. No estágio de inicialização da votação, as seguintes operações criptográficas são realizadas:



  • Desenvolvimento de um par de chaves de um validador para emissão e verificação de assinatura cega, como a mais persistente e recomendada pela comunidade acadêmica para procedimento de anonimato em sistemas de votação eletrônica. No momento, o sistema suporta algoritmos de assinatura cega em curvas elípticas e com base no algoritmo de criptografia RSA. A votação foi realizada por meio de um algoritmo de emissão e verificação de assinatura cega baseado no algoritmo de criptografia RSA com comprimento de chave de 4096 bits.
  • Geração de uma chave de criptografia pública compartilhada. Para maior segurança no processo de geração de chaves, dois algoritmos criptográficos são usados ​​ao mesmo tempo: o protocolo de geração distribuída de chaves DKG Pedersen 91 e o protocolo de compartilhamento de chaves Shamir. A geração de chaves é realizada tanto por participantes que possuem os meios técnicos para controlar diretamente os nós da rede e o servidor de contagem, quanto por participantes que são os detentores das chaves gravadas em mídia externa. O resultado do trabalho desses dois algoritmos é uma chave pública comum para criptografar cédulas. A seguir, examinaremos mais de perto o procedimento para gerar essa chave.


Fornecimento de acesso ao boletim informativo . Nesta fase, funcionam os seguintes mecanismos:



  • Geração de um par de chaves de uma assinatura eletrônica em um dispositivo de eleitor de acordo com GOST R 34.10-2012
  • Geração de uma assinatura cega para a chave pública de um eleitor mascarado para certificação e posterior verificação de seu direito de voto. O mecanismo é atualmente baseado no algoritmo de criptografia RSA. O mecanismo de anonimato é discutido em detalhes em um artigo separado.


Preenchimento e envio da newsletter . Nesta fase, o seguinte conjunto de algoritmos criptográficos é usado:



  • Criptografia da curva elíptica do boletim informativo de acordo com o esquema ElGamal. Este esquema é utilizado no protocolo, pois possui a propriedade de ser homomórfico, o que permite obter o resultado da votação sem descriptografar cada cédula.
  • A prova de intervalo de Chaum-Pedersen disjuntiva é usada para provar a exatidão do conteúdo da cédula sem descriptografá-la. Analisaremos esse mecanismo em detalhes no próximo artigo.
  • Assinatura eletrônica do boletim criptografado de acordo com GOST R 34.10-2012.


Contando os totais. Na fase de conclusão, é executado o seguinte:



  • Adição homomórfica de cédulas criptografadas.
  • Decodificação parcial preliminar da cédula final resumida por partes da chave privada pelos participantes controlando nós individuais e contando servidores com recebimento de textos criptografados de cada participante;
  • Montagem da chave privada na Comissão Eleitoral e decodificação parcial da cédula final resumida com a chave recolhida.
  • O somatório final dos textos cifrados e o recebimento dos resultados da contagem.
  • Geração e verificação de uma prova de conhecimento zero Chaum-Pedersen. Usado para provar a correção da descriptografia da cédula final resumida. Analisaremos esse mecanismo em detalhes no próximo artigo.


Auditoria . Nesta fase, podem ser realizadas verificações de validação de todas as fases do protocolo e, neste artigo, veremos mais de perto as possíveis verificações.



Vamos dar uma olhada mais de perto nos mecanismos criptográficos.



Plataforma Blockchain



Antes de falar sobre o procedimento para geração de chaves, você precisa dar uma introdução à implementação da plataforma blockchain.



A figura abaixo mostra um layout de destino simplificado da plataforma blockchain.







A colocação e reserva de nós de blockchain ocorrem em data centers distribuídos geograficamente da PJSC Rostelecom. Nesse caso, a responsabilidade pelo conjunto "atômico" de componentes envolvidos no armazenamento de todos os dados de votação pode ser atribuída à comissão eleitoral ou a várias instituições de observação pública.



Isso é feito de forma a proporcionar aos participantes a oportunidade de controlar os principais componentes do sistema e nós da rede, e ao mesmo tempo não lidar com a solução de problemas de segurança da informação, implantação e operação de meios técnicos, bem como garantir a escalabilidade do sistema.



A lista de participantes pode mudar ao longo do tempo - de uma lista mínima na fase de lançamento do sistema para operação industrial, para uma bastante ampla e completamente descentralizada conforme o sistema se desenvolve. Além disso, sempre existe a possibilidade de colocar um conjunto de componentes fora do data center.



A solução doméstica Waves Enterprise é usada como uma plataforma de blockchain. As transações e blocos são assinados de acordo com GOST R 34.10-2012.



Gerando chaves de criptografia



A chave pública para a criptografia da cédula é gerada usando dois algoritmos criptográficos: o DKG Pedersen 91 Distributed Key Generation Protocol e o Shamir Key Sharing Protocol. Com base em cada um desses algoritmos, uma chave pública “intermediária” é gerada. Então, essas duas chaves são combinadas em uma única.



O diagrama de montagem da chave é mostrado abaixo na figura.







Em geral, esse esquema pode parecer redundante, mas é assim que podemos obter o máximo de confidencialidade do voto antes que ele termine. Isso se deve ao fato de que a chave privada gerada usando o protocolo DKG nunca está em um lugar na forma montada e não pode ser roubada maliciosamente antes ou depois da geração, e suas partes são de propriedade de partes independentes que interagem entre si apenas por meio do blockchain.



Mas se você não conseguir reunir um quorum de participantes independentes, a rotina da rede blokcheyn começa a separar a chave entre as partes independentes, que são os guardiões das partes individuais da chave a serem gravadas em mídia externa (a chave da Comissão). O



procedimento para uma chave pública comum criptografada começa na véspera da votação, tornando o procedimento aberto à Comissão a chave... Em um determinado momento antes do início da votação, na presença de observadores e jornalistas em um laptop seguro não conectado à rede local ou à Internet, usando um utilitário especial, um par de chaves é gerado, seguido pela divisão da chave privada em n1 partes e gravando-as em mídia especial. A comissão eleitoral, por sua decisão, determina os portadores das partes da chave privada. Na fase de criação e inicialização de uma votação, a chave pública da comissão será gravada no blockchain.



Em seguida, é iniciada a criação de votação na rede blockchain. Após criar uma votação nos servidores de contagem, o procedimento de geração da chave pública DKG é iniciado automaticamente .



Os participantes do procedimento de geração distribuída de chaves são n servidores de contagem de votos, sobre os quais escrevemos anteriormente no artigo de revisão . Todas as operações de interação entre servidores de contagem, tanto intermediários quanto finais, são registradas no blockchain, e, portanto, são transparentes e verificáveis. O sistema implementa o esquema de limite “k de n”, ou seja, ao descriptografar os dados, não é necessária a participação de todas as n partes que formaram a chave pública DKG, um número menor de participantes k é suficiente. Isso permite descriptografar os resultados da votação mesmo se os servidores de contagem nk não estiverem disponíveis ou suas chaves privadas forem perdidas.



Para gerar a chave pública, é utilizado o algoritmo DKG (Distributed Key Generation), descrito no artigo "Um criptosistema de limiar sem uma parte confiável" de Torben Pryds Pedersen, transferido para curvas elípticas. Presume-se que cada servidor tenha um par de chaves Diffie-Hellman constante (registrado pelo registrador na conta) usado para transmissão segura de dados para este servidor (exportação / importação de compartilhamentos de chaves).



Parâmetros de protocolo



  • Uma curva elíptica E e um gerador P de um subgrupo desta curva de grande ordem primo q. A implementação atual usa a curva secp256k1 .
  • Outro gerador Q do mesmo subgrupo para o qual o valor x:Q=xP desconhecido para ninguém.
  • (k, n), onde n é o número total de participantes que geraram pares de chaves, ek é o número mínimo de participantes necessário para restaurar o segredo compartilhado, enquanto k(n+1)/2... Ou seja, se k-1 participantes forem comprometidos ou suas chaves forem roubadas, isso não afetará a segurança do segredo compartilhado de forma alguma.




Em geral, o algoritmo para obter o ponto Q é o seguinte: qualquer sequência de bytes é tomada, por exemplo a string “Hello, World!”, E o hash h = Hash (“Hello, World!”) É calculado a partir dele, após o qual convertemos a sequência de bytes h em um número e considerar x0=hmodp, onde p é o módulo da curva, substituímos x0 na equação da curva: y2=x03+ax0+bmodpe tentando resolvê-lo em relação a y. Na ausência de uma solução, incrementamos x0 e tentamos novamente resolver a equação para um novo valor de x0, etc.



Etapa 0.

Cada um dos n servidores recebe um número de sequência exclusivo de 1 a n. Isso é necessário porque o coeficiente de Lagrange depende do número de série do servidor.



Etapa 1 - criar uma chave pública DKG.



Cada j -ésimo servidor, j = 1, ..., n:

1. Gera um par de chave privada 〖priv〗 _j e uma chave públicaPubj=privjP.

2. Assume um compromisso de Pedersen para a chave pública:

Gera um número aleatório r_j

Calcula um pontoCj=rjQ+Pubj

Cjé publicado usando o medidor

3. Após todos os servidores terem publicado seus valores C_i, o escalar r_j é publicado.



Usando escalares, qualquer pessoa pode recuperar as chaves públicas de cada servidorPubj=CjrjQ e calcular a chave pública DKG Pub=(j=1)nPubj...

A chave pública DKG é gravada no blockchain.



Etapa 2 - gerar polinômios e distribuir sombras.



Cada j -ésimo servidor, j = 1,…, n:



1. Gera um polinômio aleatoriamente de grau k-1:

fj(x)=f(j,0)+f(j,1)x++f(j,k1)x(k1),

onde o coeficiente f(j,0)=privj, e o resto são elementos aleatórios do campo GF (q).



2. Conta os valores do polinômiofj(i),i=1,,n,ij.



3. Criptografa o valor fj(i)usando a chave pública de exportação / importação, o i -ésimo servidor para cada i e publica os resultados da criptografia usando o medidor.



Etapa 3 - verificação dos coeficientes dos polinômios.



Cada j -ésimo servidor, j = 1, ..., n:



1. Publica cada coeficiente de seu polinômio multiplicado pelo gerador P.

F(j,0)=f(j,0)P,F(j,1)=f(j,1)P,,F(j,k1)=f(j,k1)P

2. Decodifica todos os significados fi(j),i=1,..,n,ije verifica sua correção:

CalculaA=fi(j)P

Calcula a soma

Se A = B, então o resultado é aceito, caso contrário, uma reclamação é publicada contra o servidor i, e o protocolo começa desde o início - vá para a etapa 0.

3. Se ninguém tiver reclamações, então ele calcula sua chave privada. A







chave pública DKG pode ser recuperada e verificado em relação aos dados que os servidores de contagem gravam no blockchain no estágio de iniciação da votação. É necessário pegar os pontos de chave pública de todas as descriptografias e adicioná-los. O resultado será o mesmo valor que é gravado no blockchain como a chave pública DKG.



Além disso, com base na chave pública da comissão, que é carregada no sistema, e nas chaves públicas dos servidores de contagem, uma chave de criptografia pública comum é gerada de acordo com a seguinte fórmula:



MainPubKey = Hash (PubDKG, PubCommission) * PubDKG + Hash (PubCommission, PubDKG) * PubCommission



Todas as chaves públicas são gravadas no blockchain junto com cálculos intermediários para fácil inspeção por observadores. A chave de criptografia pública compartilhada é lida no blockchain e transmitida para os dispositivos dos usuários quando o boletim informativo é exibido.



Descrição do esquema de criptografia do boletim



Abaixo está uma descrição do procedimento para criptografar cédulas usando o esquema El-Gamal em curvas elípticas.



O esquema de criptografia El-Gamal em curvas elípticas permite implementar uma criptografia homomórfica com relação à adição, na qual, como resultado da operação de adição sobre o texto cifrado, é obtida uma soma criptografada dos valores originais.



Criptografado (A) + Criptografado (B) = Criptografado (A + B).



Para usar essa propriedade do algoritmo, a cédula eletrônica concluída é representada como uma sequência de zeros e uns. O número de caracteres corresponde ao número de escolhas, enquanto o selecionado é representado por um, as demais escolhas são representadas por zeros.



O comprimento da chave privada ao usar o algoritmo ElGamal em curvas elípticas é escolhido para ser 256 bits, enquanto a chave pública é o ponto da curva elíptica. Isso corresponde a um nível de segurança de 128 bits (2 ^ 128 operações de ponto de curva são necessárias para crack). Este nível é considerado ideal para a maioria dos sistemas industriais e financeiros modernos, incluindo o padrão russo GOST 34.10-2018 “Tecnologia da informação. Proteção de informações criptográficas. Processos de Formação e Verificação de Assinaturas Digitais Eletrônicas ”(versão 256 bits).



Secp256k1 é usado como uma curva elíptica.



Digamos que temos um par de chaves priv, Pub:

Number priv: 0 <priv <q

Point Pub = priv * Base



Encryption:



  • Há uma mensagem m, um pequeno número que queremos criptografar na chave do pub.
  • Calcule o ponto M = m * Base
  • Gere um número aleatório r: 0 <r <q
  • Calcular ponto R = r * Base e ponto C = M + r * Pub
  • Texto cifrado: (R, C)


Descriptografar:



  • Possui chave privada privada e texto cifrado (R, C)
  • Calcule o ponto M = C - priv * Base
  • Reconstruindo m: resolvendo por ECDLP de força bruta para a proporção M = m * Base


Homomorfismo de esquema.



Vemos que se criptografarmos duas mensagensM1=m1Base e M2=m2Base na chave Pub:

(R1,C1)=(r1Base,M1+r1Pub)

(R2,C2)=(r2Base,M2+r2Pub)



Então a soma deles (R1+R2,C1+C2) corresponde à mensagem criptografada M1+M2...



Assim, todas as cédulas podem ser criptografadas e dobradas "candidato a candidato". Por exemplo, deixe um boletim aberto parecido com este:



Ivanov Petrov Sidorov



0 1 0




Então, transformando-o em pontos, obtemos:



Ivanov Petrov Sidorov



ZeroPoint Base ZeroPoint



onde ZeroPoint é um ponto no infinito.



E, finalmente, criptografamos o boletim informativo na chave Pub:



Ivanov Petrov Sidorov



(r1Base,r1Pub) (r2Base,Base+r2Pub) (r3Base,r3Pub)



Digamos que realizamos tal votação com N eleitores. Se para Ivanov, Petrov e Sidorov adicionarmos separadamente os textos cifrados de diferentes cédulas, obteremos uma cédula resumida, que contém valores criptografados para cada um dos candidatos. Esta cédula resumida pode ser descriptografada com uma chave de descriptografia e os resultados da votação para cada um dos candidatos podem ser encontrados.



A figura abaixo mostra um esquema de empilhamento e validação homomórfica de cédulas com base em provas de conhecimento zero.







Como podemos ver no diagrama, um invasor em potencial não tem como "adicionar" votos extras criptografando um número incorreto no nível do protocolo criptográfico. Isso é realizado com o uso de provas de conhecimento zero, que serão discutidas posteriormente neste artigo. Além disso, as verificações necessárias também são implementadas no aplicativo da web do eleitor.



Descrição do procedimento de descriptografia



Os votos são contados sem descriptografia devido à criptografia homomórfica segundo o esquema El-Gamal, que permite manter o sigilo de todo o processo de votação e de cada voto individual. Além disso, nenhum dos servidores tem a capacidade de descriptografar de forma independente e secreta os resultados da votação.



Para descriptografar o texto cifrado (R, C), é necessário que qualquer k de n servidores compute e publique o valorsjR e a prova da exatidão da descriptografia Chaum-Pedersen (prova de que o calculado sjR É precisamente o ponto R multiplicado por sjsem revelar o significado sj) Além disso, para isso, é necessário coletar a chave privada da comissão de pelo menos k1 das partes t1 e com sua ajuda também realizar o cálculosjRcom publicação no blockchain.







A descriptografia ocorre em vários estágios, os resultados de cada um deles são registrados no blockchain.



Primeiro passo- descriptografia parcial. Cada K dos N servidores do sistema adiciona os textos cifrados dos votos, recebe a cédula sumária e descriptografa a chave privada de votação de sua parte. O resultado desta operação será um texto cifrado, cuja combinação com os textos cifrados obtidos em resultado das mesmas operações realizadas em outros servidores de contagem, bem como com o texto cifrado obtido na chave privada da comissão, dará um resultado final desencriptado. É importante notar que, se não houver texto cifrado obtido por descriptografia na chave privada da comissão, todos os outros textos cifrados se tornam inúteis. É impossível obter qualquer resultado com eles.



Os resultados da operação são publicados no blockchain.



Segunda fase- montagem da chave privada da comissão e descriptografia parcial da cédula sumária. Esta operação é realizada em um PC especial sem conexão com a Internet. Após a coleta da chave, ocorre a operação descrita no parágrafo anterior para formar o texto cifrado na chave de comissão. Os resultados desta operação também são registrados no blockchain.



O terceiro estágio é a decodificação final. Os servidores de contagem de votação agregam os resultados K ​​de N servidores, o resultado da descriptografia na chave privada da comissão, produzem a descriptografia final e publicam os resultados da votação.



Observe que a presença do texto cifrado gerado na chave privada da comissão é um pré-requisito. Sem ele, a contagem não ocorrerá.



Com base nos resultados publicados da descriptografia parcial, qualquer parte interessada pode repetir o processo e verificar se os resultados foram contados corretamente.



Prova de conhecimento zero



Embora o sistema DEG seja protegido de intrusos e erros do usuário no nível do software e da infraestrutura, foram fornecidas provas e verificações matemáticas adicionais no nível do protocolo criptográfico, que não permitem a transferência de informações falsas para o sistema. Para isso, diversos mecanismos foram desenvolvidos com base na prova não interativa de conhecimento zero (NIZK).



O primeiro tipo de ZKP (prova de conhecimento zero) aplicado no sistema são as provas de alcance. Os dados do ZKP são usados ​​ao publicar uma cédula criptografada para que, na ausência de informações sobre como o eleitor votou, seja possível garantir que o eleitor não anule a cédula em seu dispositivo de uma das seguintes maneiras:



  • o participante não criptografou valor maior que um na cédula para opção de voto em separado, o que afetaria o resultado da votação em caso de “adição criptografada”;
  • o participante não escolheu mais de uma opção para cada questão da cédula, a menos que isso esteja previsto no procedimento de preenchimento da cédula.


Uma descrição mais detalhada da implementação do NIZK, bem como sua verificação, será discutida em um artigo separado.



Estrutura de registros no blockchain



Todas as informações no blockchain são registradas por três tipos de transações:



  • CreateContract - para criar um contrato inteligente para uma votação específica. Além disso, neste contrato inteligente, todas as informações sobre votação serão agregadas. Se duas (ou mais) votações forem realizadas simultaneamente, então duas (ou mais) cópias do contrato são criadas, respectivamente.
  • CallContract - para interagir com um contrato inteligente para várias operações, uma lista dos quais é fornecida abaixo.
  • Transação de dados - para registrar a lista de eleitores depois de criar uma instância do contrato inteligente de votação e antes de iniciar a própria votação.


A interação com um contrato inteligente é realizada de acordo com as seguintes operações:



  • Gravando dados básicos em um contrato inteligente. Ficam aqui guardadas as chaves públicas dos servidores de contagem que irão participar no protocolo criptográfico, o esquema de limiar, as chaves de verificação cega de assinatura e outros dados necessários à organização do protocolo e votação em geral.
  • dkgScalar, dkgCommit, dkgShadows - dados necessários para construir uma chave pública para criptografar as cédulas e implementar um limite k de n esquemas. Falaremos mais sobre isso posteriormente neste artigo.
  • addMainKey – .
  • blindSigIssue – .
  • vote – .
  • finishVoting – . .
  • Decryption – . .
  • ComissionDecryption – .
  • Results – . , .


Uma transação de votação de eleitor inclui um endereço de blockchain do eleitor e uma chave pública, uma cédula criptografada, uma assinatura cega e uma assinatura eletrônica gerada na chave privada anônima do eleitor (consulte o artigo publicado anteriormente sobre anonimato).



As figuras abaixo mostram a visualização de uma transação com voz no cliente blockchain.











Todas as informações sobre votação são agregadas em um contrato inteligente e estarão disponíveis por meio do cliente blockchain para observadores ou na forma de um arquivo csv para qualquer pessoa.



A figura abaixo mostra a exibição de informações agregadas em um contrato inteligente.





* Dados do servidor de teste.



Os recursos da plataforma Waves Enterprise permitem que você implemente uma lógica bastante complexa com um modelo de status, verificação de assinatura às cegas e contagem de votos válidos e anulados.



Protocolo criptográfico e verificações do processo de votação



A primeira verificação básica que pode ser feita usando a plataforma blockchain e o cliente blockchain é verificar se o número de eleitores na lista de eleitores corresponde ao número de cédulas emitidas e ao número de votos registrados.



A verificação da correção da contagem é realizada repetindo o trabalho do servidor de contagem pelo observador para resumir as cédulas criptografadas candidato a candidato. Isso é feito adicionando sequencialmente os pontos da curva elíptica correspondentes a cada candidato.



Em seguida, utilizando o boletim resumido criptografado recebido e a prova de descriptografia correta, que são publicados no blockchain, é possível verificar a exatidão da soma e descriptografia parcial realizada por cada servidor de contagem.



Nesta fase, fica claro se o valor criptografado recebido pelo observador corresponde ao que cada um dos servidores de contagem registrou.



Depois disso, você pode verificar a exatidão da descriptografia dos resultados da votação. Para fazer isso, você precisa pegar os textos cifrados das transações com o tipo de operações Decryption e CommissionDecryption e, por analogia com as cédulas, adicionar os pontos da curva elíptica para cada candidato.



O código-fonte para as operações criptográficas está disponível neste repositório GitHub.



All Articles