¿Qué esquema asimétrico proporciona la firma más corta, a la vez que seguro?

No puede tener un esquema de firma seguro en menos de 50 bits. Demostración: el atacante puede simplemente enumerar todas las secuencias de 50 bits hasta que se encuentre una coincidencia. De hecho, un punto de las firmas digitales es que el algoritmo de verificación puede ser calculado por todos, ya que usa solo la clave pública (que, por definición, es pública).

Lo mejor que puedes esperar, teóricamente, es una firma de n bits para una seguridad de 2ⁿ . El umbral tradicional de inviabilidad era de bits n = 80 , pero el avance implacable de la tecnología tiende a elevarlo. Los criptógrafos modernos tienden a saltar a 128 bits, porque esa es una potencia de dos, por lo tanto hermosa (a pesar de Kant, la mayoría de los juicios estéticos son relativos). Sin embargo, 100 bits deberían ser seguros durante bastante tiempo.

Entre los algoritmos de firma conocidos que se consideran seguros, BLS es en este momento el mejor de su clase ; producirá firmas de tamaño 2n para un nivel de seguridad de 2ⁿ , por lo que está contemplando firmas de tamaño de 160 a 200 bits por lo menos . Hay algoritmos que pueden ir por debajo (hasta aproximadamente 1.4 * n ) pero tienen una historia bastante larga de roturas, reparaciones y roturas de nuevo (estoy hablando de SFLASH y su ilk), por lo que su uso Realmente no se recomienda, y no hay un estándar directamente utilizable.

Otra posibilidad es usar RSA con relleno ISO / IEC 9796-2 . Como muestra el artículo vinculado, hay algunas sutilezas con respecto a su uso. Este esquema de firma es un esquema "con recuperación", lo que significa que si bien la firma es bastante voluminosa (1024 bits si usa una clave RSA de 1024 bits), también puede incrustar algunos de los datos que se firman; Por lo tanto, si su problema es agregar una firma a un mensaje, este esquema generará una sobrecarga relativamente baja. Como lo explica el artículo, obtiene la protección 2⁶¹ para una sobrecarga de firma de 22 bytes, también conocida como 176 bits; para obtener una buena seguridad, tendría que usar una función hash con un tamaño de salida de, digamos, 224 bits, lo que lleva a una sobrecarga de firma de 240 bits, no tan buena como la de 200 bits de un BLS de potencia equivalente, pero mejor que los 400 bits de DSA o ECDSA (para aún el mismo nivel de potencia).

El problema con una firma corta es que facilita la colisión. Tampoco puede hacer que su ejecución sea prohibitivamente tan larga (utilizando un hash lento o incrementando las iteraciones), ya que el tamaño del archivo puede diferir en órdenes de magnitud. Si lo hace lo suficientemente lento como para firmar de forma segura "hola", entonces será muy difícil firmar un lanzamiento de 50 gigabytes de bluray. Por lo tanto, la opción más fácil que nos queda es aumentar el número de bits y, por lo tanto, aumentar el número de intentos necesarios para obtener una colisión si el algoritmo no se rompe de otra manera.

También vale la pena señalar que el tamaño de la clave no tiene nada que ver con el tamaño de la firma. El tamaño del hash es lo que determina el tamaño de la firma, ya que una firma es un hash del archivo que luego se cifra con la clave privada, de modo que la clave pública puede descifrarla y compararla con su propio cálculo del hash. Siempre que no utilice un esquema de cifrado que requiera relleno, la longitud de la firma es completamente independiente del tamaño de la clave.

Edit: Ok, para la pregunta actualizada parece que no estás buscando una firma. Una firma toma un hash de un archivo y luego lo cifra con la clave privada, por lo que a) otros pueden verificar que el archivo no ha cambiado yb) otros pueden verificar que usted atestigua el archivo. Esto funciona porque alguien no puede crear otro archivo que se ajuste al mismo valor hash.

Lo que está buscando es un desafío / respuesta que pueda verificar que la persona que está tratando de ingresar posee la clave. Esto generalmente se realiza con una clave simétrica en lugar de una clave asimétrica, y se encripta una marca de tiempo. Hash para reducir la longitud. El problema es que el hash para reducir la longitud eliminará un sistema público / privado porque ambas partes tienen que poder realizar la acción. Supongo que un resultado corto podría derivarse de una firma de clave privada, pero tengo la sensación de que sería significativamente más débil (sin ninguna razón demostrable, pero no se ha hecho, según mi conocimiento) que utilizar una clave simétrica.

El resultado más reciente en esta dirección es el documento titulado " Las firmas más cortas de la historia " (ePrint: 2016 / 911), que utiliza criptografía multivariada. Pretende lograr firmas de 110 bits en el nivel de seguridad de 80 bits. Sin embargo, el esquema tiene los siguientes inconvenientes:

• Supuesto de seguridad relativamente no probado (comparado con (EC) DSA / BLS)
• Los rendimientos decrecientes en niveles de seguridad más altos (por ejemplo, la seguridad de 100 bits requiere 171 bits)
• Tiempo de verificación lento para las firmas más pequeñas (~ 1 segundo)
• Clave pública relativamente grande (25 a 100 kilobytes)

Una ventaja potencial, aparte de los tamaños de firmas cortas, es:

• Se cree que la criptografía multivariable es más resistente a los ataques cuánticos que (EC) DSA / BLS

Si realmente necesita firmas muy cortas y puede vivir con los inconvenientes, entonces podría intentarlo. Tenga en cuenta sin embargo que la criptografía, por naturaleza, es un tema conservador; es mejor que te limites a seguir un esquema comprobado a menos que realmente necesites lo contrario.

Una alternativa a DSA (EC) es el esquema de firma de Schnoor, que en su forma original reduce el tamaño de la firma de 4t-bit a 3t-bit para conjeturas 2 ^t -bit security y como máximo 2 ^{t / 2} firmas por clave. Por ejemplo, en el nivel de seguridad de 96 bits, una firma requiere 36 bytes.

La descripción de referencia es: Claus-Peter Schnorr, Efficient Signature Generation por tarjetas inteligentes , en Journal of cryptology, 1991 . Se considera que el esquema es aplicable a cualquier grupo de orden $ q $ donde el problema de DL sea difícil.

Analizo algunas posibles variantes en esta pregunta :

• deshacerse del RNG utilizado para la firma, que es una debilidad probada y comprobada de DSA (EC) y similares, reemplazándolo por un MAC determinista, como en Ed25519 ;
• utilizando hashes salted con la clave pública / ID de usuario;
• volver a aplicar hash al hash t-bit a 2t-bit antes de usarlo.

Los dos últimos cambios apuntan a argumentos de seguridad más fuertes (el hash público estrecho de t-bit se encuentra entre dos hashes salados); no pretenden eliminar una debilidad en una configuración específica.