generando un par de claves OpenPGP con restricciones

3

Pretendo generar un par de claves OpenPGP RSA donde una parte (~ la mitad) de la clave privada es lo que especifico, es decir, una cadena específica. ¿Existen herramientas para generar un par de claves con tales restricciones, o tendré que investigar el protocolo?

A pesar de algunas limitaciones criptográficas, esta estrategia podría usarse para ocultar claves a simple vista.

    
pregunta 12.03.2011 - 18:36
fuente

4 respuestas

4

Debe definir con cierta precisión lo que quiere decir con "clave privada RSA".

En RSA, hay un módulo , es decir, un entero grande n que es igual al producto de dos enteros primos de igual tamaño llamados p y q . Además, hay un exponente público e (generalmente pequeño, tradicionalmente igual a 65537 en el contexto de PGP) y un exponente privado correspondiente d . El tamaño de d es aproximadamente el mismo que el de n ; d es tal que e * d = 1 cuando se toma el módulo, ya sea p-1 o q-1 .

La clave pública consiste en n y e . La operación de clave pública implica elevar un número entero a la potencia e módulo n . La clave privada es cualquier cosa que permita el cálculo de la operación inversa (encontrar el e -th módulo raíz n ). Los siguientes conjuntos de información permiten extraer e -th root, y por lo tanto, todas pueden considerarse "la clave privada":

  • n y d
  • p , q y d
  • p , q , d mod p-1 , d mod q-1
  • p , q y e

Por lo tanto, debe decidir qué define como "clave privada RSA" y de qué "mitad" está hablando.

Veamos qué define OpenPGP . En la sección 5.5.3, vemos que hay un formato de almacenamiento estándar para claves privadas RSA, dentro del contexto de OpenPGP. Ese formato almacena la clave pública ( n y e ), y también d , p , q y un valor llamado u , que es el inverso de p módulo q (este valor ayuda a implementar RSA de manera eficiente; podría volver a calcularlo en el lugar, pero almacenarlo produce operaciones más rápidas). En realidad, todo lo que se puede configurar es p , q y e , ya que los otros valores se pueden calcular de forma determinista a partir de esos tres. Y e se establece tradicionalmente, y de todos modos debería ser pequeño (por eficiencia e interoperabilidad). Así que tienes p y q para "ocultar" tu valor preestablecido.

La generación de claves RSA funciona aproximadamente así:

  • Genere un entero aleatorio p del tamaño correcto (la mitad del tamaño del módulo objetivo).
  • Probar si p es primo. Si no, inténtalo de nuevo hasta que obtengas una prima.
  • Genera q de la misma manera. Asegúrese de que q esté en el rango correcto para que n = pq tenga el tamaño objetivo deseado. Además, OpenPGP indica que q es mayor que p (si obtienes un q más pequeño, siempre puedes intercambiarlos).

Entonces, teóricamente, podrías alterar el proceso de esta manera:

  • Divida el valor V que desea ocultar en dos mitades, V1 y V 2 . Supongamos que V1 y V2 tienen la longitud k (en bits) .
  • Genere valores aleatorios potenciales de p que "incluyen" V1 , es decir, p = 1 + 2 * V 1 + r * 2 k + 1 para valores enteros aleatorios r del "tamaño correcto" para que p la longitud es, digamos, 512 bits (si apunta a un módulo de 1024 bits). Inténtalo de nuevo hasta que llegues a un p .
  • Haga lo mismo para q , incrustando V2 .

Este proceso funcionará siempre que pueda tener valores de tamaño r al menos una docena de bits. De lo contrario, no podría haber ninguna prima con el formato deseado. El "* 2" y el "+1" están ahí para forzar a p a ser impar: un gran primo no puede ser parejo.

No conozco ningún software que implemente eso, pero no debería ser difícil juntarlo con una biblioteca de enteros grandes. Sugiero usar Java, que tiene java.math.BigInteger apropiado, y luego Bouncy Castle para la parte del formato de codificación en OpenPGP.

Ten en cuenta que un atacante que sepa que juegas esos trucos puede intentar atacar tu clave explotando cualquier estructura que tenga tu valor oculto. Además, la implementación de su propio criptografía es muy rara vez una buena idea. Y no dije nada sobre si su idea de "ocultar una llave a simple vista" tenía sentido; Solo muestro cómo se puede hacer.

    
respondido por el Thomas Pornin 15.09.2011 - 18:04
fuente
3

Claro, es posible. Incluso diría, es fácil. Si está utilizando RSA, una vez que elija p y q, entonces puede elegir d casi libremente (sujeto solo a la restricción de que gcd (d, (p-1) (q-1)) = 1, que no es muy restrictivo, especialmente si elige p, q para que (p-1) / 2 y (q-1) / 2 sean primos). Por lo tanto, puede elegir d para que contenga la cadena específica que eligió.

Sin embargo, no espero que existan herramientas para hacer esto por usted. Lo que está pidiendo es una funcionalidad extremadamente inusual y peculiar, así que no espere que alguien más ya lo haya codificado para usted. Probablemente deba aprender un poco sobre el algoritmo de generación de claves RSA y luego implementarlo usted mismo.

    
respondido por el D.W. 14.03.2011 - 07:20
fuente
0

Me recuerda el ataque del "módulo común". Tal vez no sea en lo que estás pensando, pero es un pensamiento: enlace

También me recuerda a enlace .

Por lo tanto, hay algunos pensamientos. Parece que realmente estás buscando algo, implementa el intercambio secreto de Shamir. Tenga cuidado con las advertencias sobre la elección de datos no aleatorios, también.

    
respondido por el Jeff Ferland 14.03.2011 - 19:54
fuente
-1

Cada mitad de la clave privada es un número primo. Como quiere que parte de la clave sea el código fuente, veo una forma simple terminando el código fuente con un token de comentario de una sola línea (por ejemplo, C ++ "//"), luego considere la cadena del programa como la representación binaria de un número, agregándole hasta que pase una prueba de Rabin-Miller (o haga trampa y use, por ejemplo, la función de próxima ejecución de Maple que lo hace por usted), el número resultante debe verse como un código fuente válido que también es un número primo. Es posible que necesite un poco de suerte para que no se agreguen caracteres de terminación de línea en el proceso o que hagan que el código fuente no sea válido.

Hay muchas variaciones alrededor de ese esquema, jugando con comentarios, espaciando ... hasta que el código fuente visto como un número es primo ...

    
respondido por el Bruno Rohée 07.04.2011 - 18:13
fuente

Lea otras preguntas en las etiquetas