Criptologia para dummies... Y retos!

Mighty-D · 27-May-2009, 15:31

Tengo diez minutos antes de irme a estudiar grafos, la idea es hacer un tema de cifras desde el principio.

Ok, básicamente la criptología es un arte que se divide en dos:

CRIPTOGRAFIA (del griego κρύπτω krypto, «oculto», y γράφω graphos, «escribir», literalmente «escritura oculta») es el arte o ciencia de cifrar y descifrar información mediante técnicas especiales y es empleada frecuentemente para permitir un intercambio de mensajes que sólo puedan ser leídos por personas a las que van dirigidos y que poseen los medios para descifrarlos. (tomado de wikipedia)

CRIPTOANÁLISIS: Si los criptógrafos crean sistemas para hacer que un mensaje no pueda ser leído, entonces los criptoanálistas son los "crackers" de las cifras. Básicamente, son quienes encuentran las debilidades en el algoritmo de cifrado y las aprovechan para descifrar la información.

.....

Muy bien, hay que decir entonces que la criptología data desde tiempos remotos, no recuerdo bien pero hay evidencias de los egipcios utilizando tecnicas de cifrado con papiros. (Si alguien me hiciera el favor de añadir algunas referencias bien antiguas de cifras... gracias) ...

Hace mucho tiempo, cuando todos los caminos conducían a Roma, el gran Çaesar utilizaba un algoritmo de cifrado conocido por su nombre.

Antes de continuar quiero hacer unas definiciones:

texto en claro: es el mensaje comprensible por todos.
texto cifrado: es el mensaje oculto, tal que sólo es entendible si se comparte una clave.
clave= un secreto que permite descifrar el texto cifrado.
algoritmo de cifrado: procedimientos para convertir el texto en claro en texto cifrado.
algoritmo de descrifrado: procedimientos para convertir el texto cifrado en texto en claro.

La cifra cesar consiste en un algoritmo de sustitución donde a cada letra del alfabeto se le asigna un número y posteriormente se sustituye por el valor de la letra + 3.

Si consideramos las letras del inglés, entonces:

A=0,B=1,C=2....Y=24,Z=25,ESPACIO=26

TEXTO EN CLARO: HOLA MUNDO
TEXTO CIFRADO: KROD PXQGR

acá hay un sitio para hacerlo on line: Julie's Caesar Cipher

Ahora bien, si analizamos esto, en la cifra cesar la clave sería el 3 y el algoritmo de cifrado intentaba mantenerse en secreto.

Esto es diferente a las cifras de la actualidad donde lo que se espera es contar con algoritmos de cifrado que aún conociendo el algoritmo de cifrado, no pueda recuperarse el mensaje si no se posee la clave. En realidad, las especificaciones de las cifras modernas son mas altas, la idea es que aún conociendo el texto cifrado producido por una clave desconocida para un texto claro conocido y el algoritmo de cifrado, esa información no sea suficiente para recuperar un texto cifrado si no se conoce la clave.

Ok, finalmente quiero agregar... Una generalización de la cifra cesar, conocida como la cifra affine tiene la siguiente forma:

Para cada letra del mensaje en claro p, sustituir al texto cifrado C:

con C=E([a,b],p)= (ap+b) mod 26 (note que no se considera el espacio, en realidad si el espacio se considerara, sería mod 27)

La notación anterior es utilizada por muchos autores,

E(k,p) es el algoritmo de cifrado, donde k es la clave y p el texto en claro.
D(k,c) es el algoritmo de descifrado donde k es la clave y c el texto cifrado.

Muy bien, aquí les tengo el reto...

Un requerimiento básico de cualquier algoritmo de cifrado es que sea uno a uno. Esto quiere decir, que si p! = q entonces E(k,p) != E(k,q).

Si lo anterior no se cumple, descifrar los mensajes es imposible, ya que mas de un caracter del texto en plano puede producir el mismo texto cifrado.

La cifra AFFINE no es uno-a-uno para todos los valores de a, por ejemplo, para a=2 y b=3, entonces E([a,b],0)=E([a,b],13) = 3

Hay limitaciones para el valor de b?

Existe una forma general para los valores de a, es decir, cuales valores de a son permitidos?

Si este post tiene exito, les doy la respuesta en unos días.

Saludos!

hecky · 27-May-2009, 16:18

Esto es lo que uno busca amigo Mighty-D que bueno que se a animado a compartirnos lo que sabe.

Cita:

Muy bien, hay que decir entonces que la criptología data desde tiempos remotos, no recuerdo bien pero hay evidencias de los egipcios utilizando tecnicas de cifrado con papiros. (Si alguien me hiciera el favor de añadir algunas referencias bien antiguas de cifras... gracias) ...

Asi es yo sabia algo asi, que en la antiguedad ya se habia usado algo como el cifrado de el cilindro de jefferson y que adentro ponian un papiro y si era incorrecta la "clave" se quemaba el papiro. (asi como en la pelicula el codigo da vinci, pero en la antiguedad y rudimentariamente)

No se tambien de la antiguedad podrian entrar lo que son los jeroglificos egipcios o incluso el sistema de numeracion que usaron los mayas.

Bueno mas entrado a lo que es el cifrado CEsar. Es muy parecido al sistema ROT13. aqui hice un post explicandolo

Muy bueno amigo Mighty-D.

Gracias

Dédalo · 27-May-2009, 18:15

wau es un gran aporte pero no hay que olvidarnos que este tipo de critografía ya no se usa o casi nunca maximo para retos informáticos maximo ahora existen otro tipo de encriptacion mucho mas dificiles de desencriptar que no se pueden desencriptar con una calculadora o con tu cabeza como las antiguas :S mm el mas popular de todos =) creo yo =)

Código PHP:


			
<? 
$pass = md5 ( $pass ); 
?>

dudo mucho que puedas desencriptar la pass sin Passwords recovery - MD5, SHA1, MySQL o algun programa que desencripte... mm por lo menos eso creo yo xD yo he analizado muchos tipos de criptografia de hecho tengo mis propios programas para encriptar y desencriptar que los tenemos amigos y yo para podernos entender cuando nos escribimos algunas cosas mm bueno esta excelente el post es muy cool pero repito un poco viejas las tecnicas ya que existen unas nuevas muy dificiles de desencriptar sin un crackeador de contraseñas...

Saludos
Dedalo(Dédalo)

hecky · 27-May-2009, 18:38

Dédalo por lo mismo que son viejas podemos explicarlas, imaginate si empezamos a explicar para dummies con un algoritmo IDEA,RC4,RC2,DES,SERPENT,etc....

Yo apoyo la causa de Mighty-D y tambien ire explicando algunos cifrados "viejos" pero muy interesante

Mighty-D · 27-May-2009, 22:58

Saludos!

Hola Dédalo, tienes razón, las cifras modernas son un poco más complicadas que esto, tenemos paradigmas simétricos y asimétricos. Lo que tu mencionas no se puede considerar un algoritmo de cifrado. MD5 y SHA son en realidad funciones hash que producen una salida fija para cualquier entrada de datos, son muy buenas para verificar que los datos son los correctos, la razón por la cual tu haz visto estos algoritmos para almacenar las contraseñas es que al tener una salida fija en longitud para cualquier entrada variable no son susceptibles a un ataque que intente adivinar la contraseña basándose en la longitud del texto cifrado.

De todas formas, MD5 y SHA-1 han demostrado ser débiles a colisiones, es decir, al no ser uno-a-uno, diferentes entradas pueden producir la misma salida (a esto se le podría llamar entropía de la función, o que creen ustedes? )

En fin, estudiar las cifras clásicas es bueno por que nos acerca a la teoría de números y de allí directamente a RSA y la criptografía de curvas elípticas... espero que podamos discutir de eso mas adelante.

Saludos nuevamente!

Mighty-D · 28-May-2009, 02:32

Ok, para comprender bien la criptografía es necesario darle una miradita a la teoría de números. (Yo penasría que el problema de la cifra AFFINE no puede solucionarse sin utilizar estos conceptos.)

La aritmética modular es tal vez una de las herramientas fundamentales para el estudio de la teoría de números. El primero en estudiar la aritmética modular fue el grandisimo Carl Friedrich Gauss (tal vez el mas grande matemático de todos los tiempos?).

Primera definición:

Dado un entero positivo n y cualquier entero no negativo a. SI DIVIDIMOS A POR N, tenemos un cociente q y un residuo entero r que obedece a la siguiente relación:

a = qn + r con 0 <= r < n;

Ok, espero que hasta aca nada sea nuevo, digamos que es la división que nos enseñan en 3ro.

Ok, con lo anterior podemos decir que si a es un entero y n es un entero positivo, se define a mod n como el residuo cuando a es divido por n. El entero n es llamado el módulo.

Algunos ejemplos:

a=11, n =7; 11=1*7 +4; a mod n = 4
a=-11,n=7; -11=(-2)*7+3; a mod n = 3

Note que:

11 mod 5 = 1 ; y -11 mod 5 = 4

Por que????? ...

Ok, ahora bien... se dice que dos enteros son congruentes si (a mod n ) = (b mod n). Esto se escribe como a <un signo de igual con tres barras> b (mod n).

Nosotros lo usaremos con el signo igual, pero para expresar que se trata de congruencias, especificaremos que se trata de aritmética modular al final entre paréntesis.

Es decir:

a = b (mod n)

Ok... lo que sigue es la teoría detrás de los divisores y los primos.... esto como dije es necesario para estudiar cifras.

Veremos como va el tema y entonces continuaremos con estas discusiones.

vit0y4 · 28-May-2009, 09:41

hola, creo que necesito su ayuda... quisiera saber si existe un algoritmo que a partir de dos o mas contraseñas ya descrifradas se pueda encontrar el metodo con el fueron cifradas??, es decir tengo una palabra en texto en claro y en texto cifrado..
y necesito hallar la clave o el algoritmo de cifrado o de descifrado...
Para disminuir ambiguedades tengo dos textos que han sido cifrados con la misma clave o algoritmo de cifrado.
Existe ya un programa que me ayude con esto... o si es posible me ayudarian a crearlo...?

GRacias de antemano por sus respuestas!!

Mighty-D · 28-May-2009, 11:44

Hola Vitoya04, en pocas palabras, no hay una forma general para detectar el tipo de cifra usada. Sin embargo, en algunos casos si es posible.

Por ejemplo, si son contraseñas las que componen el mensaje es probable que la cifra no sea un cifra, si no un algoritmo hash (como lo que le comentaba a dédalo). En el caso de que sea un mensaje codificado con un algoritmo hash, se puede observar la talla del texto cifrado y la naturaleza de los caracteres. Por otro lado la mayoría de los protocolos que usan cifras asimétricas acompañan el mensaje con información relativa a la cifra usada (es el caso de PGP y S/MIME, o por lo menos negocian la sesión de esa forma). Existen diferentes programas que usan la información relativa a cada cifra e intenta adivinar de que tipo de cifra se trata.

Bueno, esa es la idea principal. Ahora, en la realidad muchos hemos tenido ese problema. Se han creado algunos programas interesantes para intentar adivinar el algoritmo hash usado para cifrar contraseñas, este es sólo uno de ellos:

http://ha.ckers.org/hashmaster/

El funcionamiento del programa es cifrar el texto en claro con diferentes algoritmos, hasta tener una coincidencia. El programa inclusive añade algo llamado SALTS para que sea mas probable tener un exito.

Espero que esto te sirva,

Un saludo