Firma múltiple

Firma múltiple (colectiva) ( English Aggregate signature ) - un esquema (protocolo) para la implementación de una firma electrónica (EDS), que permite que varios usuarios firmen un solo documento.

Una firma colectiva brinda la posibilidad de firma simultánea de un documento electrónico, ya que se forma como resultado de una única transformación indivisible y no puede dividirse en firmas individuales; además, no es prorrogable, es decir, se puede incrustar en él una firma adicional de una o más personas [1] .

Introducción

El término "firma colectiva" está en consonancia con el término " firma de grupo ", pero estos conceptos son diferentes. El protocolo de firma digital grupal resuelve el problema de permitir que cualquier usuario de un determinado grupo forme una firma en nombre de todo el grupo. El protocolo EDS del grupo también regula la presencia de personas concretas que pueden determinar la lista de personas que han formado una firma (así, estos últimos tienen una hipotética oportunidad de firmar por alguno de los miembros del grupo). En el caso de trabajos colectivos con documentos electrónicos, es necesario poder firmarlos por muchos usuarios [2] . La variante del esquema con la generación de un conjunto de EDS individuales de usuarios que firman un documento electrónico tiene varias desventajas pronunciadas: un aumento lineal en el tamaño del EDS colectivo (CEDS) con un aumento en el número de firmantes, así como la necesidad de verificaciones adicionales de la integridad y completitud de la firma digital colectiva para eliminar la posibilidad de sustituir el número y la composición del nombre de los participantes que firmaron el documento [1] .

El concepto de clave pública compartida

A partir de las claves públicas de los participantes se genera una clave pública colectiva, que permite desarrollar y verificar la autenticidad de una firma digital electrónica colectiva. La clave pública compartida está sujeta a una serie de restricciones de tamaño, integridad, independencia de los usuarios, generación simultánea de la clave pública compartida y continuidad. En otras palabras, es imposible calcular un CECP válido a partir del CECP para cualquier otro conjunto de participantes del conjunto actual, el CECP no está vinculado a la composición de los participantes: cualquier usuario puede formar un grupo y desarrollar su propio CECP. La clave pública colectiva, en función de las claves públicas de los usuarios, es la base sobre la que se construye todo el protocolo de firma colectiva [3] .

QECP se desarrolla de acuerdo con los requisitos anteriores utilizando algoritmos cuya estabilidad está garantizada por los siguientes problemas computacionalmente difíciles: logaritmo discreto en un grupo multiplicativo de gran orden primo , extracción de raíces de un gran grado primo módulo un gran primo, logaritmo discreto en el grupo de puntos de una curva elíptica de forma especial [3] .

Implementación de protocolos basados en estándares EDS

Estándar EDS - GOST R 34.10−94

Según el estándar GOST R 34.10−94 [4] , se imponen restricciones sobre el número primo p utilizado. La capacidad de un número primo p en representación binaria: bit o bit. El número debe contener un divisor primo grande tal que para o para . Para generar y verificar un EDS , se utiliza un número tal que , donde es el generador de un subgrupo de un orden primo suficientemente grande . $510\leq |p|\leq 512$ $1022\leq |p|\leq 1024$ $(p-1)$ $q$ $2^{255}\leq q\leq 2^{256}$ $510\leq |p|\leq 512$ $2^{511}\leq q\leq 2^{512}$ $1022\leq |p|\leq 1024$ ${\ estilo de visualización \ alfa \ neq 1}$ ${\ estilo de visualización \ alfa ^ {q} {\ bmod {p}} = 1}$ $\alfa$ $q$

Algoritmo de cálculo EDS 1. Se genera un número aleatorio .

k,1<k<q

2. Se calcula el valor , que es la primera parte de la firma.

R=(\alpha ^{k}{\bmod {p}}){\bmod {q}}

3. Según GOST R 34.11–94, se calcula una función hash a partir del mensaje que se firma.

H

4. La segunda parte de la firma se calcula: , donde es la clave secreta. Si , se repite el procedimiento de generación de firma.

S=kH+zR{\bmod {q))

z

{\ estilo de visualización S = 0}

Algoritmo de autenticación EDS 1. Se verifica el cumplimiento de las condiciones . Si no se cumplen las condiciones, la firma no es válida.

{\ estilo de visualización r <q}

{\ estilo de visualización s<q}

2. El valor se calcula

R'=(\alpha ^{S/H}y^{-R/H}{\bmod {p))){\bmod {q}}

, donde se encuentra la clave pública del usuario que generó la firma a verificar.

y

3. Los valores y se comparan . Si , entonces la firma es válida

R

{\ estilo de visualización R'}

R=R'

Implementación del protocolo CECP

Cada usuario genera una clave pública de la forma , donde es una clave privada (secreta), = , , … , . $i$ $y_{i}=\alfa ^{z_{i}}{\bmod {p}}$ $z_{yo}$ $i$ $una$ $2$ $metro$

La clave pública colectiva es el producto

y=y_{1}y_{2}y_{3}...y_{m}{\bmod {p)).

Cada usuario elige una clave secreta aleatoria , un número que se utiliza una sola vez. $k_i$

calculado

R_{i}=\left(\alpha ^{k_{i}}{\bmod {p}}\right){\bmod {q}}

R=R_{1}R_{2}R_{3}...R_{m}{\bmod {q))

Rhode Island

está disponible para todos los miembros del equipo que desarrollan CECP

Luego, cada uno de los miembros del equipo que desarrolla KECP, de acuerdo con el valor y resultado determinado por él, calcula $Rhode Island$ $H$

S_{i}=k_{i}H+z_{i}R{\bmod {q))

Si}

- parte de la firma.

La firma colectiva será un par de valores , donde es la suma de todos los módulos [3] . ${\ estilo de visualización (S, R)}$ $S$ $Si}$ $q$

Verificación de una firma digital electrónica colectiva

La verificación de la firma colectiva se realiza de acuerdo con la fórmula.

R'=\left(\alpha ^{S/H}y^{-R/H}{\bmod {p}}\right){\bmod {q}}

Si , entonces el CEC del conjunto de usuarios es genuino, ya que sólo podría formarse con la participación de cada usuario de este grupo, ya que su formación requiere el uso de la clave secreta de cada uno de ellos. Tenga en cuenta que los valores se autentican automáticamente cuando se autentica la firma digital colectiva. Si un intruso intenta reemplazar alguno de estos valores o reemplazarlos con valores utilizados anteriormente, entonces el hecho de la interferencia con el protocolo se detectará de inmediato al autenticar la firma digital , es decir, . Obviamente, el tamaño del QECP no depende de [3] . $R=R'$ $metro$ $Rhode Island$ $R'\neq R$ $metro$

Prueba de la corrección del algoritmo CECP propuesto

Sustituya la firma obtenida en la ecuación : un par (R,S), donde R es el producto de R i modulo q, S es la suma de S i modulo q : ecuación , regulada por el estándar EDS GOST R 34.10-94. $R=\left(\alpha ^{S/H}y^{-R/H}{\bmod {p}}\right){\bmod {q}}$ $R=\left[\alpha ^{\displaystyle \sum_{i=1}^{m}S_{i}/H}\left(\prod_{i=1}^{m}y_{ i}\right)^{-R/H}{\bmod {p}}\right]{\bmod {q}}=$ $\left(\prod_{i=1}^{m}\alpha ^{\displaystyle S_{i}/H}\prod_{i=1}^{m}y_{i}^{\ estilo de visualización -R/H}{\bmod {p}}\right){\bmod {q}}=$ $\left[\prod _{i=1}^{m}\left(\alpha ^{\displaystyle S_{i}/H}\alpha ^{\displaystyle -z_{i}R/H}{ \bmod {p}}\right)\right]{\bmod {q}}=$ $\left[\prod _{i=1}^{m}\left(\alpha ^{\displaystyle (k_{i}-z_{i}R)/H}\alpha ^{\displaystyle z_{ i}R/H}{\bmod {p}}\right)\right]{\bmod {q}}=$ $\left(\prod _{i=1}^{m}\alpha ^{\displaystyle k_{i}}{\bmod {p}}\right){\bmod {q}}=$ $\left[\prod _{i=1}^{m}\left(\alpha ^{\displaystyle k_{i}}{\bmod {p}}\right){\bmod {q}}\ derecha]{\bmod {q}}=$ $\left(\prod _{i=1}^{m}{\displaystyle R_{i}}\right){\bmod {q}}$ $R=\left(\alpha ^{S/H}y^{-R/H}{\bmod {p}}\right){\bmod {q}}$

Posibilidad de falsificar CECP

Obviamente, para los infractores, la complejidad de falsificar el CECP está determinada por la complejidad de falsificar la firma individual de un miembro individual del grupo. Se presentan oportunidades para los usuarios que unen sus esfuerzos para formar un CECP relacionado con un colectivo, que además de ellos incluye a uno o más usuarios que no son notificados al respecto (la prueba para ambos casos es similar). Deje que los usuarios de m-1 deseen formar un QEDP verificable mediante una clave pública compartida , donde , es decir, los usuarios combinan sus esfuerzos para formar un par de números tales que . Es decir, pueden falsificar una firma de clave pública , es decir, calcular los valores de y que satisfacen la ecuación . Esto implica la posibilidad de falsificar una firma digital en el esquema EDS básico, ya que tiene un valor aleatorio [3] . $y=y'y_{m}{\bmod {p))$ $y'=\prod _{i=1}^{m-1}y_{i}{\bmod {p}}$ $m-1$ ${\ estilo de visualización \ izquierda (R, S \ derecha)}$ $R=\left(\alpha ^{S/H}\left(y'y_{m}\right)^{-R/H}{\bmod {p}}\right){\bmod {q }}$ $y^{*}=y'y_{m}{\bmod {p))$ $R$ $S$ $R=\left(\alpha ^{S/H}\left(y^{*}\right)^{-R/H}{\bmod {p}}\right){\bmod {q} }$ $y^{*}$

Un ataque al cálculo de la clave secreta de otro copropietario de la CECP

Sea - la firma digital generada por el -ésimo usuario al documento correspondiente a la función hash (el ataque lo realizan los usuarios). Entonces lo siguiente es cierto: los atacantes generan valores aleatorios y calculan . para _ Luego se calculan los parámetros y que satisfacen las ecuaciones , donde . Al introducir la designación . Tenemos , donde y . Esto significa que los atacantes han obtenido el valor correcto de la firma colectiva en la que participan ellos y otro usuario que tiene la clave pública . Según la suposición, a partir de la firma colectiva recibida, los atacantes pueden calcular la clave secreta . Es fácil de obtener de la expresión para y la fórmula : . Los atacantes calcularon la clave secreta del usuario usando su EDS individual, generado en el marco del algoritmo EDS básico. Esto prueba la sugerencia de que el protocolo CECP propuesto no reduce la fuerza del algoritmo EDS subyacente. [3] ${\ estilo de visualización \ izquierda (R ^ {*}, S ^ {*} \ derecha)}$ $metro$ $H$ $m-1$ $R^{*}=\left(\alpha ^{S^{*}/H}\left(y_{m}\right)^{-R^{*}/H}{\bmod {p }}\right){\bmod {q}}}$ $t_{yo}$ $R_{i}=\left(\alpha ^{t_{i}}{\bmod {p}}\right){\bmod {q}}$ $i=1,2,...,m-1$ $R=\left(R^{*}\prod_{i=1}^{m-1}R_{i}{\bmod {p}}\right){\bmod {q}}$ $Si}$ $R_{i}=\left(\alpha ^{S_{i}/H}y_{i}^{-R/H}{\bmod {p}}\right){\bmod {q}}$ $i=1,2,...,m-1$ $y^{*}=y_{m}^{R^{*}/R}{\bmod {p))$ $R=\left(\alpha ^{S/H}\left(Y\right)^{-R/H}{\bmod {p}}\right){\bmod {q}}$ $S=\left(S^{*}+\displaystyle \sum_{i=1}^{m-1}S_{i}\right){\bmod {p))$ $Y=\left(y^{*}\displaystyle \prod_{i=1}^{m-1}y_{i}\right){\bmod {p))$ ${\ estilo de visualización \ izquierda (R, S \ derecha)}$ $y^{*}=a^{k^{*}}{\bmod {p}}$ $k^{*}$ $y^{*}$ $y=\alpha ^{k}{\bmod {p))$ $k=RK^{*}/R^{*}{\bmod {q))$ $metro$

Norma EDS - GOST R 34.10−2001

De acuerdo con el estándar GOST R 34.10−2001 [5] , se imponen restricciones sobre el número primo utilizado , el número primo y el punto . Un número primo es el módulo de una curva elíptica (EC), que viene dado en el sistema de coordenadas cartesianas por una ecuación con coeficientes y : ∈ ( es el campo de orden de Galois ). Un número primo es el orden de un subgrupo cíclico de puntos en una curva elíptica. Punto : un punto en una curva elíptica con coordenadas , que es diferente del origen, pero para el cual el punto coincide con el origen. La clave secreta es un número entero bastante grande . La clave pública es point . $pags$ $q$ $GRAMO$ $pags$ $y^{2}=x^{3}+ax+b{\bmod {p}}$ $a$ $b$ $a, b$ $GF_{p}$ $GF_{p}$ $pags$ $q$ $GRAMO$ ${\ estilo de visualización (x_ {G}, y_ {G})}$ ${\ estilo de visualización qG}$ $d$ ${\ estilo de visualización Q = dG}$

Formación de la firma 1. Se genera un entero aleatorio .

k,0<k<q

2. Calcular las coordenadas del punto EC y determinar el valor , donde es la coordenada del punto .

C=kP

R=x_{C}{\bmod {q))

x_{C}

C

3. Se calcula el valor , donde .

S=(Rd+ke){\bmod {q))

e=H{\bmod {q))

La firma es un par de números . [5]

{\ estilo de visualización (R, S)}

Verificación de firma

La verificación de firma consiste en calcular las coordenadas del punto EC:

C=\left(\left(Se^{-1}\right){\bmod {q}}\right)G+\left(\left(qR\right)e^{-1}{\bmod {q}}\derecho)Q

y también en la determinación del valor y la verificación de la igualdad . [5] $R'=x_{C}{\bmod {q))$ ${\ estilo de visualización R'=R}$

Implementación del protocolo CECP

Cada miembro del grupo genera una clave pública de la forma

Q=d_{i}G

, donde es una clave privada (secreta), .

d_{i}

{\ estilo de visualización i = 1,2,...,m}

La clave pública colectiva es la suma

{\displaystyle Q=Q_{1}+Q_{2}+...+Q_{m))

Cada miembro del grupo genera un número , una clave secreta aleatoria única. Usando esta clave aleatoria única, se calculan las coordenadas del punto . El resultado del cálculo se envía a todos los miembros del grupo para uso colectivo. La suma se calcula $k_i$ $C_{i}=k_{i}G$

{\displaystyle C=C_{1}+C_{2}+...+C_{m))

El valor se calcula a partir de la cantidad recibida . Cada miembro del grupo calcula su parte de la firma: $R$

S_{i}=\left(Rd_{i}+k_{i}e\right){\bmod {q}}

[3] Comprobación de CECP

Calcular

C'=\left(\left(Se^{-1}\right){\bmod {q))\right)G+\left(\left(qR\right)e^{-1}{\ bmod {q}}\derecho)Q

El resultado se calcula

R'=x_{C'}{\bmod {q))

Si , entonces el QEC del conjunto de m usuarios es genuino, ya que sólo podría formarse con la participación de cada usuario de este grupo, ya que la formación del QEC requiere la clave secreta de cada uno de los participantes [3] . ${\ estilo de visualización R'=R}$

Implementación de firma múltiple basada en RSA

Esquema de doble firma

El esquema de doble firma digital amplía el esquema RSA convencional . En el esquema de doble firma digital no se genera un par de claves (clave pública/privada), sino un triple (dos privadas y una pública). Por analogía con el esquema RSA habitual, los participantes eligen una unidad de cálculo : el producto de dos números largos simples. Se seleccionan 2 claves privadas aleatorias y en el rango de 1 a , que serán coprimos con , donde está la función de Euler . La clave pública se genera según la fórmula . El valor será la clave pública. Para firmar el valor , el primer participante calcula . El resultado del cálculo se pasa a la entrada del segundo miembro del grupo. El segundo participante tiene la oportunidad de ver lo que firmará. Para ello, obtiene el valor de value . Después de que el segundo participante esté listo para firmar el valor , deberá calcular . La verificación de la firma se realiza mediante . [6] $norte$ $r$ $s$ $norte$ $\varfi (n)$ $\varfi (n)$ $r*s*t=1{\bmod {\varphi}}(n)$ $t$ $C$ $S_{1}=C^{r}{\bmod {n))$ $C$ $S_{1}$ $C$ $S_{2}=S_{1}^{s}{\bmod {n))$ $C=S_{2}^{t}{\bmod {n))$

Extender el esquema de doble firma a los socios $norte$

Se generan claves privadas aleatorias . La clave pública se calculará mediante la fórmula . Cada -ésimo participante firma el mensaje M según la fórmula . Luego se calcula el valor . La verificación de la firma se realiza según la fórmula . [6] $norte$ ${\displaystyle k_{1},k_{2},...,k_{n))$ $\left(k_{1}+k_{2}+...+k_{n}\right)*t=1{\bmod {\varphi}}(n)$ $i$ $S_{i}=M_{k}i{\bmod {n))$ $S=S_{1}*S_{2}*S_{3}*...*S_{n}{\bmod {n))$ $S^{t}{\bmod {n}}=\left(S_{1}*S_{2}*S_{3}*...*S_{n}\right)^{t}{ \bmod {n}}$ $=M^{\left(k_{1}+k_{2}+k_{3}+...+k_{n}\right)*t}{\bmod {n))=M$

Notas

↑ 1 2 Moldovyan Nikolay Andreevich, Eremeev Mikhail Alekseevich, Galanov Alexey Igorevich. FIRMA MÚLTIPLE: NUEVAS SOLUCIONES BASADAS EN EL CONCEPTO DE CLAVE PÚBLICA COLECTIVA (rus.) // Revista "Sistemas de Información y Control". - 2008. - Edición. 1 .
↑ B. Schneier. Criptografía aplicada (ruso) // John Wiley & Sons. - 1996. - S. 98 . Archivado desde el original el 18 de diciembre de 2018.
↑ 1 2 3 4 5 6 7 8 9 Nikolay Andreevich Moldovyan, Andrey Alekseevich Kostin, Lidia Vyacheslavovna Gortinskaya, Mikhail Yurievich Ananiev. IMPLEMENTACIÓN DEL PROTOCOLO DE FIRMA COLECTIVA BASADO EN LOS ESTÁNDARES EDS (rus.) // Revista "Sistemas de Información y Control". - 2005. Archivado el 21 de noviembre de 2016.
↑ GOST R 34.10–94. Tecnologías de la información. Protección criptográfica de la información. Procesos de formación y verificación de firma digital electrónica (ruso) // Gosstandart de la Federación Rusa. - 1994. - 25 de mayo.
↑ 1 2 3 GOST R 34.10–2001. Tecnologías de la información. Protección criptográfica de la información. Procesos de formación y verificación de firma digital electrónica (ruso) // Gosstandart de la Federación Rusa. - 2001. - 12 de septiembre.
↑ 1 2 Mihir Bellare, Gregory Neven. Esquemas de firmas múltiples digitales (inglés) // Springer-Verlag Berlin Heidelberg. - 2007. - S. 145-162 . (enlace no disponible)

Criptosistemas de clave pública

Algoritmos

Factorización de números enteros	criptosistema Benalo Bluma - Goldwasser Cayley sobrecargo Damgorda - Eureka GMR Goldwasser-Micali Nakasha - popa paga Rabín RSA Okamoto-Uchiyama Schmidt-Samoa
logaritmo discreto	BLS Cramer - Shoup Protocolo de Diffie-Hellman DSA ECDH Curva25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Intercambio de claves cifradas Esquema de ElGamal esquema de firma MQV esquema de Schnorr HABLA PVP STS
Criptografía en celosías	NTRUEncriptar NTRUSign Intercambio de claves basado en el aprendizaje con errores Entrenamiento basado en firmas con errores en el ring FELICIDAD Nueva Esperanza
Otro	AE CEILIDH EPOC Ecuaciones de campo ocultas IES la firma de lamport McEliece Criptosistema de mochila Merkle-Hellman Criptosistema de mochila Naccache-Stern Protocolo de tres pasos XTR

Teoría

Logaritmo discreto en una curva elíptica
Criptografía elíptica
Criptografía basada en hash
Criptografía no conmutativa
problema RSA
Función unidireccional con entrada secreta

Estándares

CRYPTREC
IEEE P1363
NESSIE
Paquete B de la NSA
Criptografía post cuántica

Temas

Firma electronica
OAEP
Huella dactilar
PKI
red de confianza
Tamaño de clave
Criptografía basada en identidad
Criptografía poscuántica
Tarjeta OpenPGP