Criptografía: Cifrado de clave pública I

¿Qué es el cifrado de clave pública?

Un cifrado de clave pública (o asimétrica), es aquel cifrado que se basa en el uso de una pareja de claves, pública y privada, de las cuales una se usa para cifrar y la otra para descifrar.

Ambas claves están relacionadas por una función trampa, suele ser una función matemática. Las claves se calculan usando la función y la inversa de ésta, siendo la función inversa la función trampa al ser muy difícil o imposible de calcular.

  • Función irreversible
    x ∈ A, f(x) fácil de calcular
    y ∈ f(A), x = f-1(y) difícil de calcular

  • Función trampa
    x = f-1(y) Es calculable conociendo la trampa de la función. Pero sin conocer dicha trampa, y = f(x) es unidireccional.
    Además la trampa sólo se puede calcular con la clave privada.

Algoritmo de Diffie-Hellman

Desarrollado por Whitfiled Diffie y Martín Hellman en 1976. Este algoritmo es, básicamente, un protocolo para realizar el intercambio de claves. En realidad no es un cifrado, se creó para solucionar el problema de los cifrados de clave privada (o simétricos) en el intercambio de claves. El algoritmo consiste en los siguientes pasos:

  1. Se establecen un primo “p” y un generador g ∈ Z*p. Estos dos valores (“g” y “p”) son públicos. Siendo Z* el conjunto de los enteros menores que “p”, que son primos relativos de éste y además es un grupo bajo la multiplicación módulo “p”.
  2. A escoge x ∈ Zp-1 al azar, calcula X = gx (mod p), y envía X a B.
  3. B escoge y ∈ Zp-1 al azar, calcula Y = gy (mod p), y encía Y a A.
  4. A calcula K = (gy mod p)x mod p
  5. B calcula K = (gx mod p)y mod p
  6. Siendo la clave “K”.

Diffie-Hellman
Imagen sacada de la wikipedia

Si alguién intercerptara nuestra conversación, por ejemplo un usuario malintencionado “E” que poseyera p, g, X e Y, podría calcular el secreto compartido si tuviera también uno de los valores privados (x o y) o lograse invertir la función, pero como se menciona anteriormente estos algoritmos usan funciones trampa, ya que para calcular x dado X tenemos que el problema del logaritmo discreto en Zp* es un problema que se cree intratable computacionalmente.

(Más información en Wikipedia)

Este algoritmo se usa(ba) para compartir una clave privada usando unos valores públicos, como veremos en próximos posts los cifrados de clave pública se basan básicamente en métodos semejantes.

Post anterior: Cifrado de clave privada

Autor: fran

11 Comentarios

  1. Lo único que tiene de difícil entender esto es el concepto de aritmética modular (mod p) que se puede resumir en “calcular el resto de dividir un número entre p. Entendiendo de qué va esto, el resto es sencillo de entender.

    Al fin y al cabo lo que hace cada parte es elegir un número (x e y) y elevar otro número elegido por ambas partes, g, a dichos números. Al final ambos obtienen g^(xy). El módulo p lo que hace es, por una parte, mantener la clave en un rango de valores aceptable y, por otra, como dice neok, proteger los valores intermedios.

    Por otro lado, para calcular la x a partir de la X sería necesario calcular todos los valores g^m mod p con m=0,1,…,p-1, lo cual es más costoso cuanto más grande es p. (para quien dude, que intente calcular 100000^56232 mod 531441 y piense en cuanto tardaria en calcular por fuerza bruta el x de un X concreto en esas condiciones)

    Aun recuerdo mi tierna infancia calculando con lapiz y papel operaciones modulares absurdamente grandes….

    En fin, espero que sirva de complemento a lo expuesto tan correctamente por neok.

    Salud

    Publica una respuesta
  2. Se entiende que cuando dije para calcular la x a partir de la X sería necesario calcular todos los valores g^m mod p con m=0,1,…,p-1 me referia a calcular todos hasta hallar el número k tal que g^k mod p sea nuestro X. En ese caso k será el x buscado.

    Publica una respuesta
  3. Que son los enteros (Z) “sup *” “sub p”?
    Los positivos hasta p? oo…? o qué?

    Lo de que “que son primos relativos de éste” es un dato innecesario porque todos los numeros enteros son primos relativos respecto a cualquier primo, o es que aún no estoy pillando algo?

    Publica una respuesta
  4. A ver que contesto:

    Ferni buenos comentarios explicativos, aunque en Gaussianos ya hemos explicado teoría de números anteriormente y hemos hablado de todo lo que has dicho. 😉

    Oleg Z “sub p”, podríamos decir que son los enteros desde 0 hasta “p-1”, aunque realmente es el conjunto cociente de la relación de Z con “mod p”.

    Z* es el conjunto que definía en el post, el de los primos relativos respecto a “p”, y para ponerte un ejemplo en que no todos los enteros son primos relativos frente a un primo tienes que 4 no es primo relativo de 2.

    Así, Z* “sub p” es el conjunto de enteros desde 0 a “p-1” que son primos relativos respecto a “p”.

    Creo que me he explicado bien.

    Publica una respuesta
  5. ehm… pero el 4 es mayor que 2, si estamos hablando de 0 a p-1 se supone que no hay ningun multiplo de p…

    conjunto cociente de la relacion de Z con “mod p”, ahm, ya sé a lo que te refieres, es que asi escrito no me quedaba muy claro.

    Publica una respuesta
  6. Oleg tienes razón mi ejemplo no vale, y pensandolo bien tienes razón en un Z “sub p”, con “p” primo, todos los elementos son primos relativos respecto a “p”.

    Publica una respuesta
  7. Ya neok, pero era para los que descubren gaussianos con posterioridad y no se leen todo el archivo. Algunos nacimos vagos. jajajaja.

    Aquí hay verdaderas perlas, pero como las reales, no todo el mundo le apetece bucear a buscarlas, así que por eso saqué una. (La próxima prometo buscarla y poner el enlace. Así ahorro tiempo y cometer errores 😉 )

    Publica una respuesta
  8. quisiera que me orientaran un poco de como puedo calcular estos archivos y resolverlos y que me den una clave de cuatro digitos..ej:

    Wed Nov 08 06:05:42 2006
    > 11\1c000\1c\1c\1c19\1c;6036440000822981185=08101200087100?\1c\1cAA \1c000000080000\1c>?>;8?734>36\1c\1c66\1c\1c29195100000000000000000000
    Wed Nov 08 06:05:44 2006
    UNELLEZ fGA2> FARMACIA LA TRINfHA3> OF.BARINAS 4 fIA4> E/S LA CARDENERAfJA5> E/S LAS COLINAS fKA6> E/S VISTA HERMOS\1c900
    Wed Nov 08 06:05:44 2006
    > 22\1c000\1c\1cB
    Wed Nov 08 06:23:34 2006
    > 11\1c000\1c\1c\1c1:\1c;6012889453858713=11101200000000129307?\1c;0000000000000000?\1cAA \1c000000060000\1c>414:84?075;:753\1c\1c81\1c\1c29195100000000000000000000
    Wed Nov 08 06:23:35 2006
    UNELLEZ fGA2> FARMACIA LA TRINfHA3> OF.BARINAS 4 fIA4> E/S LA CARDENERAfJA5> E/S LAS COLINAS fKA6> E/S VISTA HERMOS\1c:00
    Wed Nov 08 06:23:35 2006
    > 22\1c000\1c\1cB
    Wed Nov 08 06:23:41 2006
    > 11\1c000\1c\1c\1c1;\1c\1c\1cDDDDDDDD\1c\1c\1c\1c\1c\1c29195100000000000000000000
    Wed Nov 08 06:23:43 2006
    UNELLEZ fGA2> FARMACIA LA TRINfHA3> OF.BARINAS 4 fIA4> E/S LA CARDENERAfJA5> E/S LAS COLINAS fKA6> E/S VISTA HERMOS\1c;00
    Wed Nov 08 06:23:43 2006
    > 22\1c000\1c\1cB
    Wed Nov 08 06:24:41 2006

    me seria de gran utilidad si alguno de ustedes me explicara como hacerlo.. angelfiguera_29@hotmail.com

    Publica una respuesta

Trackbacks/Pingbacks

  1. A dorfunteca » Anotacións da Bitácora » Quick News Flagged Articles - [...] Criptografía: Cifrado de clave pública I https://gaussianos.com/criptografia-cifrado-de-clave-publica-i/ [...]
  2. Gaussianos » Criptografía: Cifrado de clave pública II - [...] Este algoritmo está basado en el algoritmo de Diffie-Hellman para el intercambio de claves, fue descrito en 1984 por…

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *