🕚 🖥️ 💟 Revisión del protocolo criptográfico del sistema de votación electrónica remota 🚅 🥅 👩🏼‍✈️

En este artículo analizaremos los detalles de la implementación del protocolo criptográfico del sistema de votación electrónica remota.

El uso de algoritmos y mecanismos criptográficos en diversas etapas del proceso electoral confiere al sistema de votación a distancia las propiedades necesarias. Echemos un vistazo más de cerca y consideremos las etapas de la votación descritas en el artículo de descripción general .

Inicialización del sistema. En la etapa de inicialización de la votación, se realizan las siguientes operaciones criptográficas:

Desarrollo de un par de claves validador para la emisión y verificación de una firma ciega, como la más persistente y recomendada por la comunidad académica para el procedimiento de anonimización en los sistemas de votación electrónica. Por el momento, el sistema admite algoritmos de firma ciega en curvas elípticas y se basa en el algoritmo de cifrado RSA. La votación se realizó mediante un algoritmo de emisión y verificación de una firma ciega basado en el algoritmo de encriptación RSA con una longitud de clave de 4096 bits.
Generación de una clave de cifrado pública compartida. Para mayor seguridad, se utilizan dos algoritmos criptográficos en el proceso de generación de claves a la vez: el protocolo de generación de claves distribuidas DKG Pedersen 91 y el protocolo de intercambio de claves Shamir. La generación de claves la realizan tanto los participantes que tienen los medios técnicos para controlar directamente los nodos de la red y el servidor de conteo, como los participantes que son los custodios de las claves grabadas en medios externos. El resultado del trabajo de estos dos algoritmos es una clave pública común para cifrar las papeletas. A continuación, veremos más de cerca el procedimiento para generar esta clave.

Facilitar el acceso al boletín . En esta etapa, funcionan los siguientes mecanismos:

Generación de un par de claves de una firma electrónica en un dispositivo de votante de acuerdo con GOST R 34.10-2012
Generación de firma ciega de clave pública de votante enmascarado para certificación y posterior verificación de su derecho al voto. El mecanismo se basa actualmente en el algoritmo de cifrado RSA. El mecanismo de anonimización se analiza en detalle en un artículo separado.

Cumplimentación y envío de la newsletter . En esta etapa, se utiliza el siguiente conjunto de algoritmos criptográficos:

Cifrado de curva elíptica del boletín según el esquema ElGamal. Este esquema se utiliza en el protocolo, ya que tiene la propiedad de ser además homomórfico, lo que permite obtener resultados de votación sin descifrar cada boleta.
La prueba disyuntiva de rango Chaum-Pedersen se utiliza para demostrar la exactitud del contenido de la papeleta sin descifrarla. Analizaremos este mecanismo en detalle en el próximo artículo.
Firma electrónica del boletín cifrado de acuerdo con GOST R 34.10-2012.

Contando los totales. En la etapa de resumen, se realiza lo siguiente:

Adición homomórfica de papeletas encriptadas.
Descifrado parcial preliminar de la boleta resumida final por partes de la clave privada por parte de los participantes que controlan los nodos individuales y los servidores de conteo con la recepción de textos cifrados de cada participante;
Recopilación de la clave privada en la Comisión Electoral y descifrado parcial de la papeleta resumida final con la clave recopilada.
La suma final de los textos cifrados y la recepción de los resultados del recuento.
Generación y verificación de la prueba de conocimiento cero de Chaum-Pedersen. Se utiliza para demostrar la corrección del descifrado de la papeleta resumida final. Analizaremos este mecanismo en detalle en el próximo artículo.

Auditoría . En esta etapa, se pueden realizar comprobaciones de validación de todas las etapas del protocolo, y en este artículo analizaremos más de cerca las posibles comprobaciones.

Echemos un vistazo más de cerca a los mecanismos criptográficos.

Plataforma blockchain

Antes de hablar sobre el procedimiento para generar claves, debe dar una introducción a la implementación de la plataforma blockchain.

La siguiente figura muestra un diseño de destino simplificado de la plataforma blockchain.

La ubicación y reserva de los nodos de blockchain se lleva a cabo en centros de datos distribuidos geográficamente de PJSC Rostelecom. En este caso, la responsabilidad del conjunto "atómico" de componentes involucrados en el almacenamiento de todos los datos de la votación puede asignarse a la comisión electoral oa varias instituciones de observación pública.

Esto se hace con el fin de brindar a los participantes la capacidad de controlar los componentes principales del sistema y los nodos de la red, y al mismo tiempo no lidiar con problemas de seguridad de la información, despliegue y operación de medios técnicos, así como garantizar la escalabilidad del sistema.

La lista de participantes puede cambiar con el tiempo, desde una mínima en la etapa de lanzamiento del sistema a la operación industrial, hasta una bastante amplia y completamente descentralizada a medida que se desarrolla el sistema. En este caso, siempre existe la posibilidad de colocar un conjunto de componentes fuera del centro de datos.

La solución doméstica Waves Enterprise se utiliza como plataforma blockchain. Las transacciones y los bloques se firman de acuerdo con GOST R 34.10-2012.

Generando claves de cifrado

La clave pública compartida para el cifrado de las papeletas se genera mediante dos algoritmos criptográficos: el protocolo de generación de claves distribuidas DKG Pedersen 91 y el protocolo de intercambio de claves de Shamir. Sobre la base de cada uno de estos algoritmos, se genera una clave pública "intermedia". Entonces estas dos claves se combinan en una común.

El diagrama de ensamblaje de llaves se muestra a continuación en la figura.

En general, tal esquema puede parecer redundante, pero así es como podemos obtener la máxima confidencialidad del voto antes de que finalice. Esto se debe al hecho de que la clave privada generada mediante el protocolo DKG nunca está en un solo lugar en la forma ensamblada y no puede ser robada maliciosamente antes o después de la generación, y sus partes son propiedad de partes independientes que interactúan entre sí solo a través de la cadena de bloques.

Pero si no es posible reunir un quórum de participantes independientes en la red blockchain, se lanza un procedimiento de intercambio de claves entre participantes independientes que son custodios de partes separadas de la clave registrada en medios externos (clave de la Comisión)

El procedimiento para generar una clave de cifrado pública común comienza en la víspera de la votación con el procedimiento para generar la clave pública de la Comisión.... En un momento determinado antes del inicio de la votación, en presencia de observadores y periodistas en una computadora portátil segura no conectada a una red local o Internet, utilizando una utilidad especial, se genera un par de claves, seguido de dividir la clave privada en n1 partes y grabarlas en medios especiales. La comisión electoral, por su decisión, determina los portadores de las partes de la clave privada. En la etapa de creación e inicialización de un voto, la clave pública de la comisión se registrará en la cadena de bloques.

Luego se inicia la creación de votaciones en la red blockchain. Después de crear un voto en los servidores de conteo, se inicia automáticamente el procedimiento para generar la clave pública DKG.

Los participantes en el procedimiento de generación de claves distribuidas son n servidores de conteo de votos, sobre los que escribimos anteriormente en el artículo de revisión . Todas las operaciones de interacción entre servidores de conteo, tanto intermedios como finales, quedan registradas en la blockchain, y, por tanto, son transparentes y verificables. El sistema implementa el esquema de umbral "k de n", es decir, al descifrar los datos, no se requiere la participación de todas las n partes que formaron la clave pública DKG, un número menor de participantes k es suficiente. Esto permite descifrar los resultados de la votación incluso si nk servidores de conteo no están disponibles o sus claves privadas se han perdido.

Para generar la clave pública se utiliza el algoritmo DKG (Distributed Key Generation), descrito en el artículo "Un criptosistema de umbral sin una parte de confianza" de Torben Pryds Pedersen, transferido a curvas elípticas. Se supone que cada servidor tiene un par de claves Diffie-Hellman constante (registrado por el registrador en la cuenta) que se utiliza para la transmisión segura de datos a este servidor (exportación / importación de recursos compartidos de claves).

Parámetros de protocolo

Una curva elíptica E y un generador P de un subgrupo de esta curva de gran orden primo q. La implementación actual usa la curva secp256k1 .
Otro generador Q del mismo subgrupo para el que el valor $x: Q=x⋅P$ desconocido para nadie.
(k, n), donde n es el número total de participantes que generaron pares de claves y k es el número mínimo de participantes que es necesario para restaurar el secreto compartido, mientras que $k≤(n+1)/2$ ... Es decir, si los participantes k-1 se ven comprometidos o sus claves son robadas, esto no afectará la seguridad del secreto compartido de ninguna manera.

En general, el algoritmo para obtener el punto Q es el siguiente: se toma cualquier secuencia de bytes, por ejemplo la cadena “¡Hola, mundo!”, Y se calcula el hash h = Hash (“¡Hola, mundo!”), Luego de lo cual convertimos la secuencia de bytes h en un número y considerar

x 0 = h m o d p

$x0=h mod p$ , donde p es el módulo de la curva, sustituimos

x 0

$x0$ en la ecuación de la curva:

y^{2} = x 0^{3} + a * x 0 + b m o d p

$y^2= x0^3+ a*x0+b mod p$ y tratando de resolverlo con respecto ay. En ausencia de una solución, incrementamos x0 y nuevamente intentamos resolver la ecuación para un nuevo valor de x0, y así sucesivamente.

Paso 0. A

cada uno de los n servidores se le asigna un número de secuencia único de 1 a n. Esto es necesario porque el coeficiente de Lagrange depende del número de serie del servidor.

Paso 1: creación de una clave pública DKG.

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

1. Genera un par de clave privada 〖priv〗 _j y una clave pública

P u b_{j} = p r i v_{j} \cdot P .

$Pub_j=priv_j⋅P.$

2. Hace un compromiso de Pedersen para la clave pública:

genera un número aleatorio r_j

Calcula un punto

C_{j} = r_{j} \cdot Q + P u b_{j}

$C_j=r_j⋅Q+Pub_j$

C_{j}

$C_j$ se publica usando el medidor

3. Una vez que todos los servidores han publicado sus valores C_i, se publica el escalar r_j.

Usando escalares, cualquiera puede recuperar las claves públicas de cada servidor

P u b_{j} = C_{j} - r_{j} \cdot Q

$Pub_j=C_j-r_j⋅Q$ y calcular la clave pública DKG

P u b = \sum_{(} j = 1)^{n} P u b_{j}

$Pub=∑_(j=1)^n Pub_j$ ...

La clave pública DKG se escribe en la cadena de bloques.

Paso 2: generar polinomios y distribuir sombras.

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

1. Genera un polinomio aleatorio de grado k-1:

f_{j} (x) = f_{(} j, 0) + f_{(} j, 1) \cdot x + \dots + f_{(} j, k - 1) \cdot x^{(} k - 1),

$f_j (x)=f_(j,0)+f_(j,1)⋅x+⋯+f_(j,k-1)⋅x^(k-1),$

donde el coeficiente

f_{(} j, 0) = p r i v_{j}

$f_(j,0)=priv_j$ , y el resto son elementos aleatorios del campo GF (q).

2. Cuenta los valores del polinomio

f_{j} (i), i = 1, \dots, n, i \neq j .

$f_j (i),i=1,…,n,i≠j.$

3. Cifra el valor

f_{j} (i)

$f_j (i)$ utilizando la clave pública de exportación / importación, el i-ésimo servidor para cada i y publica los resultados de cifrado utilizando el medidor.

Paso 3: verificar los coeficientes de los polinomios.

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

1. Publica cada coeficiente de su polinomio multiplicado por el generador P.

F_{(} j, 0) = f_{(} j, 0) \cdot P, F_{(} j, 1) = f_{(} j, 1) \cdot P, \dots, F_{(} j, k - 1) = f_{(} j, k - 1) \cdot P

$F_(j,0)=f_(j,0)⋅P,F_(j,1)=f_(j,1)⋅P,…,F_(j,k-1)=f_(j,k-1)⋅P$

2. Decodifica todos los significados

f_{i} (j), i = 1, . ., n, i \neq j

$f_i (j),i=1,..,n,i≠j$ y comprueba su corrección:

Calcula

A = f_{i} (j) \cdot P

$A=f_i (j)⋅P$

Calcula la suma

Si A = B, entonces se acepta el resultado; de lo contrario, se publica una queja contra el servidor i, y el protocolo se inicia desde el principio; vaya al paso 0.

3. Si nadie tiene quejas, calcula su clave privada. La

clave pública DKG se puede recuperar y verificado con los datos que los servidores de conteo escriben en la cadena de bloques en la etapa de inicio de la votación. Es necesario tomar los puntos de clave pública de todos los descifrados y agregarlos. El resultado será el mismo valor que se registra en la cadena de bloques que la clave pública DKG.

Además, en función de la clave pública de la comisión, que se carga en el sistema, y las claves públicas de los servidores de conteo, se genera una clave pública de cifrado común de acuerdo con la siguiente fórmula:

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

Todas las claves públicas se escriben en la cadena de bloques junto con cálculos intermedios para una fácil inspección por parte de los observadores. La clave de cifrado pública compartida se lee de la cadena de bloques y se transmite a los dispositivos de los usuarios cuando se muestra el boletín.

Descripción del esquema de cifrado de boletines

A continuación se muestra una descripción del procedimiento para cifrar las papeletas usando el esquema El-Gamal en curvas elípticas.

El esquema de cifrado de El Gamal sobre curvas elípticas permite implementar un cifrado homomórfico con respecto a la suma, en el que, como resultado de la operación de suma sobre el texto cifrado, se obtiene una suma cifrada de los valores originales.

Encriptado (A) + Encriptado (B) = Encriptado (A + B).

Para utilizar esta propiedad del algoritmo, la boleta electrónica completa se representa como una cadena de ceros y unos. El número de caracteres corresponde al número de opciones, mientras que el seleccionado está representado por uno, las otras opciones están representadas por ceros.

La longitud de la clave privada cuando se usa el algoritmo ElGamal en curvas elípticas se selecciona para que sea de 256 bits, mientras que la clave pública es un punto en la curva elíptica. Esto corresponde a un nivel de seguridad de 128 bits (se requieren operaciones de 2 ^ 128 puntos de curva para romper). Este nivel se considera óptimo para la mayoría de los sistemas industriales y financieros modernos, incluida la norma rusa GOST 34.10-2018 “Tecnología de la información. Protección de la información criptográfica. Procesos de Formación y Verificación de Firmas Digitales Electrónicas ”(versión de 256 bits).

Secp256k1 se utiliza como curva elíptica.

Digamos que tenemos un par de claves priv, Pub:

Number priv: 0 <priv <q

Point Pub = priv * Base

Encryption:

Hay un mensaje m, un pequeño número que queremos cifrar en la clave Pub.
Calcule el punto M = m * Base
Genera un número aleatorio r: 0 <r <q
Calcular el punto R = r * Base y el punto C = M + r * Pub
Texto cifrado: (R, C)

Descifrado:

Hay una clave privada priv y un texto cifrado (R, C)
Calcular el punto M = C - priv * Base
Reconstrucción de m: resolución de ECDLP de fuerza bruta para la relación M = m * Base

Esquema de homomorfismo.

Vemos que si encriptamos dos mensajes

M 1 = m 1 * B a s e

$M1 = m1*Base$ y

M 2 = m 2 * B a s e

$M2 = m2*Base$ en la clave Pub:

(R 1, C 1) = (r 1 * B a s e, M 1 + r 1 * P u b)

$(R1, C1) = (r1*Base, M1 + r1*Pub)$

(R 2, C 2) = (r 2 * B a s e, M 2 + r 2 * P u b)

$(R2, C2) = (r2*Base, M2 + r2*Pub)$

Entonces su suma

(R 1 + R 2, C 1 + C 2)

$(R1 + R2, C1 + C2)$ coincide con el mensaje cifrado

M 1 + M 2

$M1 + M2$ ...

Por lo tanto, todas las papeletas se pueden cifrar y plegar "candidato por candidato". Por ejemplo, deje que un boletín abierto se vea así:

Ivanov Petrov Sidorov

0 1 0

Luego, transformándolo en puntos, obtenemos:

Ivanov Petrov Sidorov

ZeroPoint Base ZeroPoint

donde ZeroPoint es un punto en el infinito.

Y finalmente, encriptamos el boletín en la clave Pub:

Ivanov Petrov Sidorov

(r 1 * B a s e, r 1 * P u b)

$(r1*Base, r1*Pub)$

(r 2 * B a s e, B a s e + r 2 * P u b)

$(r2*Base, Base + r2*Pub)$

(r 3 * B a s e, r 3 * P u b)

$(r3*Base, r3*Pub)$

Digamos que hemos realizado tal votación con N votantes. Si para Ivanov, Petrov y Sidorov agregamos por separado los textos cifrados de diferentes papeletas, obtenemos una papeleta de resumen, que contiene cantidades cifradas para cada uno de los candidatos. Esta papeleta resumen se puede descifrar con una clave de descifrado y se pueden encontrar los resultados de la votación de cada uno de los candidatos.

La siguiente figura muestra un esquema de apilamiento y validación de boletas homomórficas basado en pruebas de conocimiento cero.

Como podemos ver en el diagrama, un atacante potencial no tiene forma de "arrojar" votos adicionales encriptando un número incorrecto al nivel del protocolo criptográfico. Esto se implementa utilizando pruebas de conocimiento cero, que se discutirán más adelante en el artículo. Además, las verificaciones necesarias también se implementan en la aplicación web del votante.

Descripción del procedimiento de descifrado

Los votos se cuentan sin descifrar por cifrado homomórfico según el esquema de El-Gamal, que permite mantener la confidencialidad de todo el procedimiento de votación y de cada voto individual. Además, ninguno de los servidores tiene la capacidad de descifrar de forma independiente y secreta los resultados de la votación.

Para descifrar el texto cifrado (R, C), es necesario que cualquier k de n servidores calculen y publiquen el valor

s_{j} \cdot R

$s_j⋅R$ y prueba de la exactitud del descifrado de Chaum-Pedersen (prueba de que el calculado

s_{j} \cdot R

$s_j⋅R$ ¿Es precisamente el punto R multiplicado por

s_{j}

$s_j$ sin revelar el significado

s_{j}

$s_j$ ). Además, para esto, es necesario recopilar la clave privada de la comisión de al menos k1 de las partes t1 y con su ayuda también realizar el cálculo.

s_{j} \cdot R

$s_j⋅R$ con publicación en blockchain.

El descifrado tiene lugar en varias etapas, los resultados de cada una de las cuales se registran en la cadena de bloques.

Primer paso- descifrado parcial. Cada K de los N servidores del sistema agrega los textos cifrados de los votos, recibe la boleta resumen y descifra la clave de votación privada por su parte. El resultado de esta operación será un texto cifrado, cuya combinación con los textos cifrados obtenidos como resultado de las mismas operaciones realizadas en los demás servidores de conteo, así como con el texto cifrado obtenido en la clave privada de la comisión, dará un resultado final descifrado. Es importante señalar que si no se obtiene un texto cifrado del descifrado en la clave privada de la comisión, todos los demás textos cifrados se vuelven inútiles. Es imposible obtener resultados de ellos.

Los resultados de la operación se publican en blockchain.

Segunda fase- montaje de la clave privada de la comisión y descifrado parcial de la papeleta sumaria. Esta operación se realiza en una PC especial sin conexión a Internet. Una vez recopilada la clave, se lleva a cabo la operación descrita en el párrafo anterior para formar el texto cifrado en la clave de comisión. Los resultados de esta operación también se registran en la cadena de bloques.

La tercera etapa es la decodificación final. Los servidores de conteo de votaciones agregan los resultados K de N servidores, el resultado del descifrado en la clave privada de la comisión, y producen el descifrado final, luego publican los resultados de la votación.

Tenga en cuenta que la presencia del texto cifrado generado en la clave privada de la comisión es un requisito previo. Sin él, no se realizará el cálculo de los resultados.

Con base en los resultados publicados del descifrado parcial, cualquier interesado puede repetir el proceso y verificar que los resultados se cuentan correctamente.

Prueba de conocimiento cero

Si bien el sistema DEG está protegido de intrusos y errores de usuario a nivel de software e infraestructura, a nivel del protocolo criptográfico se proporcionaron comprobaciones y verificaciones matemáticas adicionales que no permiten transferir información falsa al sistema. Para ello, se han desarrollado varios mecanismos basados en la prueba de conocimiento cero no interactiva (NIZK).

El primer tipo de ZKP (prueba de conocimiento cero) aplicado en el sistema son las pruebas de rango. Los datos de ZKP se utilizan al publicar una boleta encriptada para que, en ausencia de información sobre cómo votó el votante, sería posible asegurarse de que el votante no estropeó la boleta en su dispositivo de una de las siguientes maneras:

el participante no cifró un valor mayor que uno en la boleta para una opción de votación separada, lo que afectaría el resultado de la votación en caso de "adición cifrada";
el participante no eligió más de una opción para cada pregunta de la boleta, a menos que así lo disponga el procedimiento para completar la boleta.

Una descripción más detallada de la implementación de NIZK, así como su verificación, se discutirán en un artículo separado.

Estructura de registros en blockchain

Toda la información en la cadena de bloques se registra mediante tres tipos de transacciones:

CreateContract: para crear un contrato inteligente para una votación específica. Además, en este contrato inteligente se agregará toda la información sobre la votación. Si se realizan dos (o más) votaciones simultáneamente, se crean dos (o más) copias del contrato, respectivamente.
CallContract: para interactuar con un contrato inteligente para varias operaciones, una lista de las cuales se proporciona a continuación.
Transacción de datos: para registrar la lista de votantes después de crear una instancia del contrato inteligente de votación y antes de comenzar la votación en sí.

La interacción con un contrato inteligente se realiza mediante las siguientes operaciones:

Escribir datos básicos en un contrato inteligente. Aquí se almacenan las claves públicas de los servidores de conteo que participarán del protocolo criptográfico, el esquema de umbrales, claves de verificación de firma ciega y demás datos necesarios para la organización del protocolo y la votación en general.
dkgScalar, dkgCommit, dkgShadows: datos necesarios para crear una clave pública para el cifrado de papeletas e implementar un umbral k de n esquemas. Hablaremos más sobre esto más adelante en el artículo.
addMainKey – .
blindSigIssue – .
vote – .
finishVoting – . .
Decryption – . .
ComissionDecryption – .
Results – . , .

Una transacción de voto de votante incluye la dirección blockchain y la clave pública de un votante, una boleta encriptada, una firma ciega y una firma electrónica generada en la clave privada anónima del votante (ver artículo publicado anteriormente sobre anonimización).

Las siguientes figuras muestran la visualización de una transacción con una voz en el cliente blockchain.

Toda la información sobre la votación se agrega en un contrato inteligente y estará disponible a través del cliente blockchain para los observadores o como un archivo csv para cualquiera que lo desee.

La siguiente figura muestra la visualización de información agregada en un contrato inteligente.

* Datos del servidor de prueba.

Las características de la plataforma Waves Enterprise le permiten implementar una lógica bastante compleja con un modelo de estado, verificación de firma ciega y recuento de votos válidos y no válidos.

Comprobaciones del proceso de votación y del protocolo criptográfico

La primera verificación básica que se puede hacer usando la plataforma blockchain y el cliente blockchain es verificar si el número de votantes en la lista de votantes coincide con el número de boletas emitidas y el número de votos registrados.

La verificación de la exactitud del conteo se lleva a cabo repitiendo el trabajo del servidor de conteo por parte del observador para resumir las papeletas encriptadas candidato por candidato. Esto se hace sumando secuencialmente los puntos de la curva elíptica correspondientes a cada candidato.

Luego, utilizando el boletín resumen cifrado recibido y la prueba de descifrado, que se publican en la cadena de bloques, se puede verificar la exactitud de la suma y descifrado parcial realizado por cada servidor de conteo.

En esta etapa, puede ver si la cantidad encriptada recibida por el observador corresponde a lo que registró cada uno de los servidores de conteo.

Después de eso, puede verificar la corrección del descifrado de los resultados de la votación. Para hacer esto, es necesario tomar textos cifrados de transacciones con el tipo de operaciones Descifrado y Comisiones Descifrado y, por analogía con las papeletas, sumar los puntos de la curva elíptica para cada candidato.

El código fuente para las operaciones criptográficas está disponible en este repositorio de GitHub.

Revisión del protocolo criptográfico del sistema de votación electrónica remota