Tarea 8 Algoritmo de cifrado de flujo A5

Introducción

El algoritmo de cifrado de flujo es muy utilizado para la protección de datos dentro de redes inalámbricas, éste radica su importancia en la seguridad de que el envío bit por bit se encuentre activo y cifrado dentro del flujo de información.

El cifrado A5/1, es muy utilizado en la telefonía móvil, ya que el paso de los datos que se hace por GSM también necesita seguridad, y es el A5/1 quién se lo brinda.

Descripción del funcionamiento

El algoritmo de cifrado de flujo A5/1 consta de un generador binario de secuencia cifrante, que se utiliza para cifrar la comunicación entre el teléfono y la estación base en el sistema de telefonía móvil GSM.

La conversación entre emisor y receptor (A-B), se transmite como una sucesión de tramas. Cada trama consta 228 bits, de éstos los 114 primeros representan la comunicación digital de A a B, mientras que los 114 que restan se utilizan para la comunicación en sentido contrario. Cada 4.6 mili-segundos se envía una nueva trama.

Previamente a la transmisión se realiza un proceso de sincronización que incluye también una criptosincronización entre A y B en los dos sentidos.

El generador produce 228 bits pseudoaleatorios de cada trama, que se sumarán bit a bit, mediante un XOR , dejando como resultado 228 bits de comunicación cifrada.

El A5/1 consiste de 3 LFSR's, las longitudes de los registros son 19, 22 y 23, todos los polinomios de reacción son dispersos, la salida es el XOR de los tres LFSR's.

En la comunicación se usan variables de control de reloj.

Explicación gráfica del cifrado A5/1:

Código A5/1:

	//Codigo obtenido de la siguiente URL: http://delta.cs.cinvestav.mx/~francisco/arith/Flujo.pdf
	void a5_key(a5_ctx *c, char *k) //Funcion donde se definen las longitudes de los registros
	{
	c->r1 = k[0]<<11|k[1]<<3 | k[2]>>5; /* 19 */
	c->r2 = k[2]<<17|k[3]<<9 | k[4]<<1 | k[5]>>7; /* 22 */
	c->r3 = k[5]<<15|k[6]<<8 | k[7]; /* 23 */
	}
	int a5_step(a5_ctx *c) //Funcion donde se obtiene el valor de las variables de control de tiempo
	{
	int control;
	control = threshold(c->r1,c->r2,c->r3);
	c->r1 = clock_r1(control,c->r1);
	c->r2 = clock_r2(control,c->r2);
	c->r3 = clock_r3(control,c->r3);
	return((c->r1^c->r2^c->r3)&1);
	}
	/* cifra un bufer de longitud len */
	void a5_encrypt(a5_ctx *c, char *data, int len) //Funcion de encriptacion
	{
	int i,j;
	char t;
	for(i=0;i<len;i++)
	{
	for(j=0;j<8;j++)
	t = t << 1 | a5_step(c);
	data[i]^=t;
	}
	}

view raw A5.c hosted with ❤ by GitHub

Vulnerabilidad

Se encontró información importante sobre la vulnerabilidad del cifrado A5/1, dentro de un artículo, que habla de un Ingeniero Alemán que descifró el algoritmo.

El ingeniero Karsten Nohl, quien es experto en criptografía, hizo público su descubrimiento para obligar a las operadoras a utilizar otros métodos de cifrado para proteger la comunicación.

Después se publicó que este descifrado se había realizado de forma ilegal y se negaba la necesidad de cambiar la seguridad para el sistema GSM.

En 2007, se cambiaron algunos sistemas al algoritmo A5/3, pero muchos todavía siguen utilizando el A5/1.

Con un ataque semi-activo, como comenta Nohl en su presentación, interceptando una comunicación cifrada y pidiéndole a través de una estación base falsa que reutilice la clave, si damos con dos RAND iguales tendremos dos claves idénticas.

La vulnerabilidad recae en que es teóricamente posible utilizar el cifrado para realizar un ataque a la comunicación, pero se considera prácticamente imposible, razón por la cual el cifrado A5/1 sigue siendo usado.

Conclusiones

Es importante conocer cómo está constituida la seguridad de la información que a diario utilizamos, ya sea de las páginas de Internet o de los dispositivos de telefonía móvil, entre otros. Ya que como informáticos, la seguridad es uno de los temas que más nos debe preocupar. Al manejar grandes cantidades de importante información en algún sistema, programa o dispositivo.

Referencias
Silvana Bravo Hernández
 "Estudio comparativo de los algoritmos de cifrado de flujo RC4, A5 y SEAL."      
6 de agosto del 2002
http://delta.cs.cinvestav.mx/~francisco/arith/Flujo.pdf

Antonio José Galisteo Cantero
"Ingeniero Alemán descifra el algoritmo A5/1"
30 diciembre 2009
http://agalisteo.blogspot.mx/2009/12/ingeniero-aleman-descifra-el-algoritmo.html

Tarea 7 Cifrados de bloque (RC5)

Introducción

Existe una gran variedad de métodos de codificación o encriptación, utilizados en la criptografía, un tipo de ellos son los cifrados de bloque, los cuales se encuentran muy efectivos.

En ésta entrada se describirá el funcionamiento del algoritmo de cifrado RC5.

Descripción

Algoritmos de cifrado de Bloque

Criptografía Simétrica:

Para empezar con la explicación de nuestro algoritmo de cifrado RC5, es necesario saber cómo está compuesta la criptografía simétrica.

La diferencia principal de la criptografía clásica con ésta es que el algoritmo se hace público y su fortaleza se basa en la imposibilidad computacional de romper una clave secreta, tomando como valor agregado la robustez de las funciones matemáticas involucradas.

Imagen obtenida de:  http://lapaginademarcos.quijost.com/blog/wp-content/uploads/criptografia.png

Todos los sistemas de criptografía simétrica se basan en el protocolo que se muestra en la imagen, ya que son aquellos en los que la clave de cifrado es la misma que la clave de descifrado, por lo tanto es necesario que la clave sea conocida sólo por el emisor y el receptor.

Ya que se utiliza la misma clave para cifrar y descifrar, adquiere la propiedad de un algoritmo simétrico.

Los algoritmos simétricos pueden ser desarrollados utilizando métodos de cifrado en bloque o métodos de cifrado en flujo

Los métodos de cifrado en bloque se caracterizan por que la forma en la que su mensaje es cifrado, se forman grupos, tomando bloques de datos del mensaje, de manera que se cifra uno por uno los bloques de datos de tamaño constante. La clave a utilizar debe ser del mismo tamaño del bloque, por lo tanto el texto cifrado es una colección de bloques que requieren el mismo tratamiento para ser descifrados.

Todos los cifrados de bloque se componen de 4 elementos:

Transformación lineal: Consta de una o dos funciones que pueden o no depender de la clave.

Transformacion intermedia mediante iteraciones o vueltas:
Repeticion n veces de una función no lineal sobre la clave.

Transformacion final:
Operación inversa de las dos transformaciones anteriores.

Algoritmo de expansión de clave:
Consiste en convertir la clave en un conjunto de sub-claves, por si se descubre alguna, no se sepa la clave completamente.

Cifrado RC5

Se encuentra dentro de la clasificación de los criptosistemas con clave secreta.

Es un sistema de cifrado el cual fue diseñado por Ronald Rivest en 1994.

Éste algoritmo salió en sustitución del esquema RC4, el cual había sido publicado anónimamente en internet.

Es un algoritmo que opera por bloques y éstas son sus principales características:

 Tamaño variable de bloques: 32, 64 o 128 bits.

 Palabra clave entre 0 y 2040 bits.

 vueltas entre 0 y 255.

 bloques de 64 bits (2 palabras de 32 bits), en 12 rondas o vueltas y con una clave de 128 bits (16 bytes).

 RC5 hace uso de rotaciones dependientes.

 En su estructura contiene algunas operaciones como sumas modulares y operaciones XOR.

Funciona básicamente así:

Opera con palabras de tamaño variable(w), número de vueltas variable(r) y clave secreta de longitud variable (b, en bytes).

Consta de tres operaciones primitivas, lo cual favorece mucho a la portabilidad de éste algoritmo de cifrado:

Suma módulo 2w (+)
Or exclusivo bit a bit((+))
Rotación, donde la rotación de x un número y de bits a la izquierda se denota por x <<y.

Antes del cifrado la clave secreta se expande para llenar un array S de 2r + 2 palabras.

Denotando (A, B) las dos palabras del bloque de entrada (32 bits cada una), el algoritmo es el siguiente: 

A=A+S[0]
B=B+S[1]
i=1
for i in r:

     A=((A(+)B)<<B)+S[2*i] 

     B=((B(+)A)<<A)+S[2*i+1]

S[0], S[1],...,S[2]+1    Subclaves

(A. B)     Bloque en claro

(A[r], B[r])     Bloque cifrado

Para el descifrado deben realizarse las operaciones inversas en orden inverso.

*Observación: Como nos habremos dado cuenta el método de cifrado cumple con los 4 elementos de un algoritmo de cifrado, mencionado más arriba a cada uno de ellos descriptivamente.

Ataques o posibles vulnerabilidades:

RC5 (Rivest Cypher 5, en honor a su autor) no tiene una longitud determinada de clave, sino que permite gran flexibilidad a la hora de fijar los parámetros.

El problema es que el gobierno EE.UU. declara ilegal la exportación de 

criptosistemas con una clave mayor de 40/56/64 bits, según las circunstancias. 

El objetivo de los retos RC5, es demostrar que esas longitudes de claves son insuficientes para cualquier aplicación seria, como comercio electrónico, por ejemplo.

El RC5-40 bits cayó en unas 3 horas y media.

El RC5-56 cayó en unos pocos meses de esfuerzo.

El RC5-64 es el que está siendo "forzado" en estos momentos, a buen ritmo.

Conclusiones

El Cifrado RC5 es uno de los algoritmos de cifrado menos vulnerables y más portables que existen, ya que además de que es simétrico, uno de los ataques a los que no está completamente protegido es el ataque con fuerza-bruta, pero éste se ve limitado cuando se utilizan más de 64 bits.

Referencias

Autor: UNAM Facultad de Ingeniería  Título: "CR5= River Cipher"  Fecha: Mayo 2010
URL: http://www.openboxer.260mb.com/asignaturas/criptografia/CSimetrica/RC5.php

Autor:  Alarcos  Fecha: 2010
URL: http://alarcos.inf-cr.uclm.es/doc/psi/tema4.pdf

Autor: Jesús Cea Avión Título: "Ayuda Periodística (RC5-64)"  Fecha: 25 mayo 1998
URL: http://www.jcea.es/artic/rc5-6403.htm

Tarea 6 Esteganografía

Introducción

La esteganografía es la rama de la criptología que se encarga de ocultar mensajes. Para marcar la diferencia entre Seguridad y Oscuridad, es importante saber que la criptografía tiene como objetivo principal, el hacer que un mensaje sea indescifrable para terceras personas dentro de una comunicación, la esteganografía se encarga de ocultar la existencia de dicho mensaje.

Es muy importante dentro de la informática conocer ésta importante técnica, ya que ha sido muy utilizada en los sitios web, para buenos o malos fines, pero que se requiere un amplio conocimiento de ella para implementarla, ya sea para ocultar mensajes en imágenes o en sonido, entre otros tipos de archivos.

Planteamiento

Para la tarea a realizar de hoy se va a implementar una técnica que oculta mensajes en un archivo ".png", haciendo referencia a una imagen. Cabe recalcar que no utilicé imágenes con formato ".jpg" ya que el mensaje se obtiene con menor claridad, por el tipo de compresión que se le hace al archivo.

Al abrir el programa el usuario elige si desea enviar un mensaje, lo cual le permite guardarlo en la imagen deseada, después dentro del mismo programa existe la opción de "recibir", la cual permite al usuario recuperar el mensaje oculto en la imagen que se generó por el emisor, y como 3 era opción se permite al usuario salir del programa.

esteganografia.py

	#Esteganofragia en python
	from PIL import Image
	from sys import argv
	import random
	def transformar(original): #Funcion que transforma valores ascii a su valor original
	mensaje = list()
	for i in original:
	mensaje.append(chr((i[0])))
	#mensaje.reverse()
	sms = "".join(str(x) for x in mensaje)
	return sms
	def obtenermen(nombreimagen): #Funcion que obtiene el mensaje
	original = list()
	imag=nombreimagen
	imag2="nuevaimg.png"
	data=Image.open(imag).convert("RGB")
	data2=Image.open(imag2).convert("RGB")
	(w, h) = data.size
	pix=data.load()
	nuevo=data2.load()
	for x in xrange(w):
	for y in xrange(h):
	if not nuevo[x, y]==pix[x, y]:
	original.append(nuevo[x, y])
	message = transformar(original)
	return message
	def rangox(weight, men): #Funcion que fija los rangos en x
	rangosx=list()
	tope=(len(men))+1
	for x in range(tope):
	rangosx.append((weight/len(men))*x)
	return rangosx
	def rangoy(height, men): #Funcion que fija los rangos en y
	rangosy=list()
	tope= (len(men))+1
	for y in range(tope):
	rangosy.append((height/len(men))*y)
	return rangosy
	def imagen(men, z, nombreimagen): #Funcion que en base a una imagen crea una nueva con el mensaje oculto
	imag = nombreimagen
	data = Image.open(imag).convert("RGB")
	(w,h) = data.size
	res = Image.new("RGB", (w,h))
	nuevo = res.load()
	pix = data.load()
	for x in xrange(w):
	for y in xrange(h):
	r, g, b = pix[x, y]
	if x % 2 == 0:
	nuevo[x, y] =r, g, b
	rangosx=list()
	rangosy=list()
	rangosx=rangox(w, men)
	rangosy=rangoy(h, men)
	for i in range(len(men)):
	x = random.randint(rangosx[i],rangosx[i+1])
	y = random.randint(rangosy[i],rangosy[i+1])
	nuevo[x,y] = int(z[i],2), int(z[i],2), int(z[i],2)
	#print nuevo[x, y]
	res.save("nuevaimg.png")
	res.show("nuevaimg.png")
	return
	def main(): #Funcion principal donde se ingresan todos los datos
	nombreimagen= argv[1]
	opcion=0
	while not opcion == 3:
	opcion = int(raw_input("1. Enviar 2. Recibir 3. Salir "))
	if opcion == 1:
	mensaje = raw_input("Mensaje: ")
	mensaje.lower()
	men = list(mensaje)
	bina = list()
	for i in range(len(men)):
	bina.append(bin(ord(men[i])))
	imagen (mensaje,bina, nombreimagen)
	if opcion == 2:
	resultado = obtenermen(nombreimagen)
	print resultado
	main()

view raw esteganografia.py hosted with ❤ by GitHub

*Para correr el programa es necesario agregar el nombre de la imagen original después de el nombre del archivo de Python, ejemplo:  python programa.py imagen.png, para descifrar es necesario tener la imagen con el mensaje oculto con el nombre de "nuevaimg.png" y la imagen original.

ejecución del programa

1. Enviar  2. Recibir  3. Salir 1

Mensaje: Este es el primer mensaje

1. Enviar  2. Recibir  3. Salir 2       

Este es el primer mensaje

1. Enviar  2. Recibir  3. Salir 3 

Imágenes utilizadas

*Sólo tres de éstas imágenes tienen un mensaje oculto, utiliza el programa para descubrir la existencia de un mensaje y cuál es su contenido.

1. Imagen original:

 

2. Imagen original:

3. Imagen original: 

4. Imagen original:

5.  Imagen original:

6. Imagen original:

Conclusión

La estenografía es una técnica muy útil en la seguridad de la información, ya que vuelve a los mensajes muy poco vulnerables a ataques de terceros, como programadores es indispensable conocer y dominar ésta técnica, para ayudar reducir el número de ataques a sitios web importantes.

Referencias

Autor:  Carlos Jumbo G. Título: "Introducción a la Estenografía"    Fecha: --  URL:  http://www.slideshare.net/cjumbo/introduccin-a-la-esteganografa 

Autor: Javier Montero Título: "Funciones que devuelven varios valores" Fecha: 26/04/2012 URL: http://elclubdelautodidacta.es/wp/2012/04/python-capitulo-32-funciones-que-devuelven-varios-valores/

URL: http://stackoverflow.com/questions/5618878/how-to-convert-list-to-string 

Tarea 5 Algoritmo RSA en aplicación web

Tarea a realizar:

La implementación de un algoritmo RSA en una aplicación web, para evaluar la autentificación del ingreso de un id de usuario, el módulo con el que se trabaja y la llave o clave privada.

Implementación

Se utilizó la herramienta Apache, para utilizar Python cgi, en aplicaciones web, dentro de nuestra aplicación hacen un papel fundamental el programa en python que interactúa con la página html principal, nuestro algoritmo RSA, utilizado para la tarea anterior y la página escrita con html y javascript.

Autentificador en python:

	#!/usr/bin/python2.7
	# enable debugging
	#El programa es producto de varias recopilaciones de rsa y ejemplos de cgi
	#URLS: http://blog.hackxcrack.es/2011/11/introduccion-la-criptografia-moderna_09.html
	#http://code.activestate.com/recipes/572196-rsa/
	#http://cic.puj.edu.co/wiki/doku.php?id=materias:laboratorio_de_lenguajes_ii:lableng2:ejemplos1
	from rsa_math import * #importamos algunas funciones para el algoritmo rsa como la generacion de primos
	import cgi, cgitb #importamos las librerias para cgi
	import random #importamos random
	def generarclaves(bitn): #genera las claves dependiendo el numero de bits
	p = genprime(bitn)
	q = genprime(bitn)
	n = p * q
	phi = (p - 1) * (q - 1)
	e=65537
	while (phi%e) == 0:
	e=genprime(17)
	d = inverse_mod(e, phi)
	public = (n, e)
	private = (n, d)
	return public, private
	# Convierte un string en un numero
	def integear(s):
	n = 0
	for c in s:
	n <<= 8
	n += ord(c)
	return n
	def cifrar(s, public):
	n = integear(s)
	c = modex(n, public[1], public[0])
	return c
	# Convierte un numero en un string
	def stringear(n):
	s = []
	while n > 0:
	s.insert(0, chr(n & 255))
	n >>= 8
	return ''.join(s)
	#descifra el mensaje con la llave privada
	def descifrar(n, private):
	p = modex(n, private[1], private[0])
	s = stringear(p)
	return s
	try:
	import hashlib
	except:
	print >> sys.stderr, "No se ha encontrado el modulo Hashlib, no podras firmar ni comprobar firmas"
	#funciones que realizan los signos del cifrado
	def signo(msg,private):
	s = int(hashlib.sha1(msg).hexdigest(), 16)
	return modex(s,private[1],private[0])
	def checksigno(msg,sign,pub):
	s = modex(sign,pub[1],pub[0])
	h = int(hashlib.sha1(msg).hexdigest(), 16)
	return s == h
	#algoritmo rsa
	def guardarvalor(archivo, valor): #funcion que guarda un valor en un archivo
	f1 = open(archivo, "w") #funcion que abre el archivo con permisos de escritura
	f1.write(str(valor)) #se escribe el archivo como string
	f1.close() #se cierra el archivo
	def Abrirllaves(archivo, usuario): #funcion para leer llaves o claves
	f1 = open(archivo, "r") #Se abre el archivo de solo lectura
	for element in f1:
	element = i.split(",") #se separa por comas entre cada valor en i
	if element[0].lower() == usuario.lower() : #el usuario se pasa a minusculas
	fl.close() #cerramos archivo
	return int(element[1]), int(element[2]) #se devuelve el modulo y la llave privada
	fl.close()
	return False
	def cambio(x):
	return x*3+20; #Se ajusta un cambio en el valor de x.
	def verificar(usuario, y): #funcion que checa los datos ingresados
	valororiginal = cargarvalores("valores.dat")
	if valororiginal == y: #los compara con los valores originales
	return True #si se cumple retorna verdadero
	else:
	return False #si no, retorna falso
	def cargarvalores(archivo): #Funcion utilizada para guardar valores en un archivo
	f1 = open(archivo, "r") #abrimos el archivo con sólo lectura
	valor = f1.read() #se obtiene todo el contenido del archivo
	f1.close() #cerramos
	return int(valor) #devuelve el valor entero del archivo
	def probarRSA(bitn,s):
	pub,priv=generarclaves(bitn)
	c=cifrar(s,pub)
	descifrar(c,priv)
	f=signo(s,priv)
	print "Comprobando firma...",checarsigno(s,f,pub)
	def main():
	entrada = cgi.FieldStorage() #hacemos uso del cgi para interactuar con el formulario
	if entrada.has_key("x") and entrada.has_key("usuario"): #Se verifica que se hayan llenado los campos de texto
	lonx=int(entrada["x"].value)
	probarRSA(lonx,str(entrada["usuario"].value))
	else: #si no se encuentran entradas
	x = random.randint(1, 1000) #se generan aleatoriamente
	guardarvalor("valores.dat", cambio(x)) #se guardan en el archivo valores y se hace un cambio en x para poder usarlo en el algoritmo
	print x #imprimimos x
	main()

view raw test-script.py hosted with ❤ by GitHub

Página HTML:

	<html>
	<head>
	<title>Login</title>
	</head>
	<body>
	<h1>Ingreso al Sistema</h1>
	<p>Ingrese los siguientes datos:
	</p>
	<form name="datos" id="datos">
	<table>
	<tr>
	<th><code>Usuario</code></th>
	<td><input type="text" size="10" name="usuario" id="usuario" value=""></td>
	</tr>
	<tr>
	<th>Valor del modulo</th>
	<td><input type="text" size="10" name="modulo" id="modulo" value=""></td>
	</tr>
	<tr>
	<th>Valor de llave privada</th>
	<td><input type="text" size="10" name="llave" id="llave" value=""></td>
	</tr>
	</table>
	</form>
	<h3>Estado del autentificador:</h3>
	<div id="res"></div>
	<script language="javascript">
	function potmod(x, pot, mod)
	{
	if(n==1)
	{
	return x;
	}
	else if(pot%2 ==0)
	{
	return Math.pow(potmod(x, pot/2, mod), 2)%mod;
	}
	else
	{
	return (x*potmod(x, pot-1, mod))%mod;
	}
	}
	function evalua(form)
	{
	$.post( "http://127.0.0.1/usr/lib/cgi-bin/test-script.py", {},
	function(datos)
	y= cambio(parseInt(datos));
	n= parseInt(document.forms[form].elements["modulo"].value)
	d= parseInt(document.forms[form].elements["llave"].value)
	usuario= String(document.forms[form].elements["usuario"].value)
	num = potmod(y, d, n).toPrecision(100);
	num.substring(0, num.indexOf("."));
	$post("http://127.0.0.1/usr/lib/cgi-bin/test_script.py"), {"x":num, "usuario":usuario},
	function(datos)
	{
	if(datos.indexOf("True")!=-1)
	{
	document.getElementById("res").innerHTML=("<h2> El usuario:'"+usuario+"' esta autenticado.<h2>");
	}
	else if(datos.indexOf("False")!=-1)
	{
	document.getElementById("res").innerHTML=("<h2> El usuario:'"+usuario+"' no esta autenticado.<h2>");
	}
	else
	{
	document.getElementById("res").innerHTML=("<h2> Vuelva a llenar el formulario <h2>");
	}
	}
	);
	}
	</script>
	<p>
	<button onClick="evalua()">Evaluar</button>
	</p>
	</body>
	</html>

view raw index.html hosted with ❤ by GitHub

rsa_math.py

	#librería para funciones matematicas en el algoritmo rsa.
	#código obtenido de la URL: http://pastebin.com/ziaUdaw8
	import random
	import sys
	#Exponenciacion modular
	def modex(base, exponente, modulo):
	r = 1
	while exponente > 0:
	if exponente & 1:
	r = (r * base) % modulo
	exponente >>= 1
	base = (base * base) % modulo
	return r
	# Generacion/Comprobacion de numeros primos
	# Genera una lista de primos
	def genprimelist(t):
	l = [2]
	i = 3
	while i < t :
	prime = True
	for c in l:
	if i % c == 0 :
	prime = False
	break
	if prime:
	l.append(i)
	i += 2
	return l
	# Lista de primos precomputada con genprimelist(5000)
	primelist=[
	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
	103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
	211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
	331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
	449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577,
	587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
	709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839,
	853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983,
	991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093,
	1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223,
	1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327,
	1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481,
	1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597,
	1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721,
	1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867,
	1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997,
	1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113,
	2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267,
	2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381,
	2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531,
	2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671,
	2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777,
	2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909,
	2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061,
	3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217,
	3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347,
	3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499,
	3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617,
	3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761,
	3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907,
	3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027,
	4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177,
	4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327,
	4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481,
	4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637,
	4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783,
	4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933,
	4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999]
	# Comprobacion preliminar contra la lista precomputada
	def firstcheck(n):
	for p in primelist:
	if n%p==0:
	if n==p:
	return True
	else:
	return False
	return True
	# Comprobacion con un test de primalidad de Fermat
	# http://en.wikipedia.org/wiki/Fermat_primality_test
	def fermattest(n,k=100):
	for i in range (0,k):
	a=random.randint(1,n-1)
	if modex(a,n-1,n) != 1:
	return False
	return True
	# Divide el numero en digitos binarios
	def toBin(n):
	l = []
	while (n > 0):
	l.append(n % 2)
	n /= 2
	return l
	# Comprobacion con el algoritmo de Miller-Rabin
	# http://snippets.dzone.com/posts/show/4200
	def miller_rabin(a, n):
	b = toBin(n - 1)
	d = 1
	for i in xrange(len(b) - 1, -1, -1):
	x = d
	d = (d * d) % n
	if d == 1 and x != 1 and x != n - 1:
	return True # Complex
	if b[i] == 1:
	d = (d * a) % n
	if d != 1:
	return True # Complex
	return False # Prime
	#Comprueba si es primo con una lista de primos hasta 5000, un test de Fermat
	# y un test de Miller-Rabin
	def checkprime(n,k=100):
	if (not firstcheck(n)):
	return False
	if (not fermattest(n,k)):
	return False
	for iteration in range(0,k):
	i=random.randint(1,n-1)
	if miller_rabin(i,n):
	return False
	return True
	# Multiplicacion modular inversa
	# [ http://en.wikipedia.org/wiki/Modular_multiplicative_inverse ]
	def extended_gcd(a, b):
	x, last_x = 0, 1
	y, last_y = 1, 0
	while b:
	quotient = a // b
	a, b = b, a % b
	x, last_x = last_x - quotient*x, x
	y, last_y = last_y - quotient*y, y
	return (last_x, last_y, a)
	# Multiplicacion modular inversa
	# [ http://en.wikipedia.org/wiki/Modular_multiplicative_inverse ]
	def inverse_mod(a, m):
	x, q, gcd = extended_gcd(a, m)
	if gcd == 1:
	# x is the inverse, but we want to be sure a positive number is returned.
	return (x + m) % m
	else:
	# if gcd != 1 then a and m are not coprime and the inverse does not exist.
	return None
	# Generacion de numeros primos
	#Generar un numero primo de "bitn" bits y con una precision de "prec"
	def genprime(bitn,k=100):
	#Esto se puede sustituir por una lectura a /dev/random, por ejemplo
	prime = random.randint(2**(bitn-1),2**bitn)
	prime |= 1 # Hacemos que sea impar
	while not checkprime(prime,k):
	prime += 2
	return prime
	# Con psyco puede ir mas rapido
	try:
	import psyco
	psyco.full()
	except ImportError:
	pass
	#fin del codigo

view raw rsa_math.py hosted with ❤ by GitHub

Interfaz:

A terminar:

La implementación no está completa, ya que nuestro código javascript no hace enlace con nuestro programa en python y lo debo a un problema de configuración.
El algoritmo RSA se mejoró respecto a la tarea anterior, pero se obtienen ciertas funciones de un programa llamado rsa_math.py obtenido de pastebin.

Conclusiones

utilizado no se encuentra completo, pero en teoría sí debería funcionar para las funciones que ocupamos en ésta implementación. Cada día se encuentran más utilidades para Python y ésta es una de las más importantes dentro de la Seguridad de la información, así es como podemos observar el trabajo de el algoritmo RSA, en pleno funcionamiento ya que se considera muy poco vulnerable, al menos para ataques estadísticos, ya que si no se conoce nuestra llave privada, tenemos nuestra seguridad al 100%.

Referencias

URL: http://cic.puj.edu.co/wiki/doku.php?id=materias:laboratorio_de_lenguajes_ii:lableng2:ejemplos1

Fecha: 2010 URL: http://elisa.dyndns-web.com/~elisa/teaching/prog/web/2010/progweb6.pdf

URL: http://www.tutorialspoint.com/python/python_cgi_programming.htm

Fecha: 9 Noviembre del 2011 URL: http://pastebin.com/ziaUdaw8

Tarea 4 Algoritmo RSA

Introducción

El algoritmo RSA, es famoso por ser el más usado en el mundo para encriptar con clave pública.

Y se refiere con clave o llave pública a que por lo menos una clave que actúa como codificadora se encuentra visible para todos los participantes de la comunicación y los que intentan descifrarla. 

El meollo de nuestro algoritmo es utilizar una clave privada, sólo conocida por la persona quien escribe el mensaje, para encriptar con clave pública y clave privada y así sea muy difícil encontrar el mensaje original, para personas quienes no sean emisor o receptor.

Planteamiento del problema:

Implementar un algoritmo RSA, entro de una comunicación cliente-servidor, a manera de observar el comportamiento que se tiene de las llaves públicas y privadas sobre el mensaje que viaja en valores enteros.

Procedimiento del Algoritmo:

Éste asume que hay alguna forma de convertir las letras y símbolos en números y viceversa. Esto lo podemos hacer usando una tabla de conversión ASCII, donde A corresponde a 11, B a 12, etc. Por ejemplo la palabra Attack! Sería transformada en 115656373947.

Tabla de conversión ASCII:

	0	1	2	3	4	5	6	7	8	9
0	XX	xx	xx	xx	xx	xx	xx	xx	xx	xx
1	SP	A	B	C	D	E	F	G	H	I
2	J	K	L	M	N	O	P	Q	R	S
3	T	U	V	W	X	Y	Z	a	b	c
4	d	e	f	g	h	i	j	k	l	m
5	n	o	p	q	r	s	t	u	v	w
6	x	y	z	.	,	:	;	´	“
7	!	@	#	$	%	^	&	*	'-	'+
8	(	)	[	]	{	}	?	'/	<	>
9	0	1	2	3	4	5	6	7	8	9

Luego de convertir la palabra en un número entero, encriptar y desencriptar se convierte en un asunto de cálculo simple entre grandes números enteros. 

Sean p y q dos números primos muy grandes, se multiplican obteniendo 

N = pq. 

Sea e un entero positivo que no tenga factores en común con (p-1)(q-1). 

Sea d un entero positivo tal que ed - 1 es divisible por (p-1)(q-1).

Y en definición sea:

f(x) = x^e mod N (esto significa "divida N por x^e y tome el resto") 

g(x) = x^d mod N (i de m)

Use f(x) para encriptar y g(x) para desencriptar.

e es el mensaje encriptado, N es la clave pública que cualquiera puede conocer y puede usarse para encriptar un mensaje, en cambio d es el mensaje desencriptado. p y q son la clave privada que solo conoce el destinatario y le sirve para desencriptar el mensaje.

¿Por que el RSA es tan difícil de romper? Pensemos que hace Alice para recibir mensajes secretos. Primero genera los grandes números primos p y q, luego escoge e. Finalmente resuelve la ecuación para encontrar d: 

ed + (p-1)(q-1)y = 1

Donde todas estas variables son números enteros. Alice publica e y N. Es todo lo que necesita para que cualquiera le envíe mensajes secretos.

Ahora veamos a Bob que conoce N y quiere desencriptar los mensajes de Alice. Para esto necesita conocer los factores de N, p y q de modo de resolver la ecuación. Luego resuelve la ecuación para encontrar d, lo que equivale a desencriptar el mensaje de Alice. El problema es que para factorizar (o sea encontrar p y q que multiplicados hacen N) le tomaría una enorme cantidad de tiempo computacional -para valores de p y q suficientemente grandes- podría tomar millones de años con el conocimiento y tecnologías actuales.

Implementación:

Se tuvo problemas al intentar implementar el algoritmo en un programa, primeramente utilizando los sockets, ya que no se obtenía comunicación ambidireccional.

	#Algunas funciones fueron obtenidas de la siguiente URL: http://blog.hackxcrack.es/2011/11/introduccion-la-criptografia-moderna_09.html
	import hashlib
	import random
	def hacerentero(s): #Se utiliza una funcion para hacer el mensaje a enteros
	n = 0
	for c in s:
	n <<= 8 #evaluando los digitos ingresados por el usuario
	n += ord(c) #se obtiene el orden de c
	return n
	def esPrimo(n): #Funcion que checa si el numero es primo
	raiz=int(sqrt(n)); #Se obtiene su raiz para evaluar en una condicion
	for i in range(2,raiz+1):
	if n%i==0:
	return False;
	return True;
	def cifrado(mensaje, public): #Funcion que cifra el texto
	n = hacerentero(s) #Se guarda el mensaje hecho entero en n
	c = modex(n, public[1], public[0]) #Se guarda en c el mensaje cifrado por la clave publica
	return
	def descifrado(n, private): #Funcion que descifra con clave privada
	p = modex(n, private[1], private[0]) #Se almacena en p el numero coprimo de q
	s = hacerentero(p)
	return
	def entrando(mensaje,private):
	s = int(hashlib.sha1(me).hexdigest(), 16) #Se almacena en un entero la representación de bits
	return modex(s,private[1],private[0])
	def checandoentrada(mensaje,sign,pub): #Funcion que checa las entradas a nuestro sistema
	s = modex(sign,pub[1],pub[0])
	h = int(hashlib.sha1(msg).hexdigest(), 16)
	return s == h
	def Alice(publico, privado): #Funcion que modifica el mensaje original conoce la llave publica y privada
	mensaje= raw_input("Ingrese el mensaje: ")
	smsint=int(hacerentero(mensaje))
	return mensaje
	def main():
	primo= False #Se rellenan los valores necesarios o por default
	primo2= False
	while primo == False || primo2==False: #Sale de la condicion hasta que se ingresa un numero primo
	p= int(raw_input("primo1: "))
	primo=esprimo(p)
	q= int(raw_input("primo2: ")) #Cuando son 2 numeros primos, termina el while
	primo2=esprimo(q)
	N=p*q #Empiezan calculos del algoritmo
	phi = (p - 1) * (q - 1) #Se obtiene el valor de phi
	e=65537
	while (phi%e) == 0:
	e=generadorprimo(17)
	d = inverse_mod(e, phi) #Se señalaa d como el inverso modular tomando a e, phi
	public = (n, e)
	private = (n, d)
	Alice(public, private) #Se calculan las supuestas claves publicas y las mandas a alice para que proceda a encriptar.
	main()

view raw rsa.py hosted with ❤ by GitHub

El programa está incompleto, tiene algo de lógica pero le falta funcionalidad a la hora de la implementación, se necesita comprender más a fondo el algortimo.
Se necesita implementar comunicación cliente servidor donde la información viaje en dos direcciones, para poder simular correctamente el funcionamiento del algoritmo.

Conclusiones:

Se puede concluir que el algoritmo RSA es muy seguro, y no vulnerable, ya que aunque parezca que se da mucha información a las otras partes de la comunicación, la clave privada nunca se comparte, ni se muestra, lo cual no permite la obtención del mensaje original.

Referencias:

Autor: "Javiyu" Título: "Generadores en python" Fecha: 13 de mayo del 2008 URL: http://javiyu.blogspot.mx/2008/05/generadores-en-python.html

Autor: Tomas Bradanovic Título: "El algoritmo RSA para dummies" Fecha: Jueves 22 de noviembre del 2012 URL: http://bradanovic.blogspot.mx/2012/11/el-algoritmo-rsa-para-dummies.html

Autor: "Raúl González Duque" Título: "Sockets en Python" Fecha: URL: http://mundogeek.net/archivos/2008/04/12/sockets-en-python/

Tarea 3 Hack del algoritmo de Diffie-Hellman

Introducción

El algoritmo de Diffie-Hellman nos permite acordar una clave secreta entre dos máquinas através de un canal inseguro y enviando únicamente dos mensajes.

La clave secreta resultante no puede ser descubierta por un atacante, aunque éste obtenga los dos mensajes enviados por el protocolo. La principal aplicación de éste protocolo es acordar una clave simétrica con la que posteriormente cifrar las comunicaciones entre dos máquinas.

Procedimiento

Alice y Bob desean ponerse de acuerdo sobre una clave para comunicarse criptográficamente, y sólo disponen de un canal al que tiene acceso Eve. Eve tiene interceptadas las comunicaciones entre Alice y Bob.

Alice---------------------------------------(Eve)----------------------------------------Bob

Alice y Bob deciden que la clave será una potencia modular y lo primero es ponerse de acuerdo sobre la base de la potencia y el módulo. Éstos números serán g(un número generador) y p(un número primo). Eve toma nota de éstos números.

Alice y Bob eligen dos números x y y que mantienen en secreto, éstos números serán sus claves privadas, Eve no conoce éstos números. Tampoco Alice conoce el de Bob ni Bob conoce el de Alice.

Alice calcula la potencia (g^a)mod p  y se la envía a Bob, a lo que también Eve toma nota de éste número.

Bob hace lo mismo con Alice; calcula la potencia (g^b)mod p la envía a Alice, también Eve toma nota de éste número.

Y ahora podemos analizar la situación apuntando qué es lo que conoce cada quién.

Alice: Conoce el valor de su número "x" y el número que le ha enviado Bob "Y".

Bob: Conoce el valor de su número "y" y el número que le ha enviado Alice "X".

Eve: Conoce los valores de "X" y "Y" que interceptó dentro de la comunicación.

Alice eleva su clave privada "x" al número que ha recibido de Bob y obtiene Y^x que es lo mismo que (g^y)^x = g^xy.

Bob eleva su clave privada "y" al número que ha recibido de Alice y obtiene X^y que es lo mismo que (g^x)^y = g^yx.

Y como g^xy  = g^yx , Alice y Bob tienen el mismo número.

Eve no puede calcular éste número ya que sólo tiene el valor de  "X" y "Y"

Aquí se muestra la descripción muy gráfica del protocolo de Diffie-Hellman, en el programa se toman los valores de éste ejemplo para verificar su correcta funcionalidad.

Imagen obtenida de: http://www.javiercampos.es/blog/2011/07/22/el-algoritmo-de-diffie-hellman/

En el programa se intenta hackear el algoritmo, averiguando el valor de "x" y "y" desde Eve, de quién estamos seguros que no los conoce, ni tiene acceso a ellos.

	def AliceDescifrar(Y, x): #Funcion que descifra el mensaje de Bob
	resultado=Y**x #Se eleva el mensaje de Bob al exponente del x de Alice
	Bob = Y
	print "Alice recibe: "+str(Bob) #Se imprime lo que recibe alice
	print "Bob cifrado= "+str(resultado) #Se imprime el texto cifrado
	return
	def BobDescifrar(X, y): #Funcion que desicra el mensaje de Alice
	resultado=X**y #se eleva el mensaje de Alice al exponente del y de Bob
	Alice= X
	print "Bob recibe: "+str(Alice) #Se imprime lo que recibe Bob
	print "Alice cifrada= "+str(resultado) #Se imprime el texto cifrado
	return
	def AliceCifrar(primo, generador, turno, Y): #Funcion utilizada para cifrar el valor x de alice
	x=primo
	#if turno==0:
	print "Turno de Alice"
	while x>=primo:
	x=int(raw_input("x: ")) #se pide el valor de x y no sale del ciclo hasta que sea menor que el numero primo
	Y=((generador**x)%primo) #se hace la operacion de cifrado
	if turno==1:
	AliceDescifrar(Y, x) #en el turno 1 se descifra el mensaje
	return Y #devolvemos Y para Bob
	def BobCifrar(primo, generador, turno, X): #Funcion utilizada para cifrar el valor y de Bob
	y=primo
	#if turno==0:
	print "Turno de Bob"
	while y>=primo:
	y=int(raw_input("y: ")) #se pide el valor de y y no sale del ciclo hasta que sea menor que el numero primo
	X=((generador**y)%primo) #se hace la operacion de cifrado
	if turno==1:
	BobDescifrar(X, y) #en el turno 1 se descifra el mensaje
	return X #devolvemos X para Alice
	def Eve(X, Y, g, p): #Hackeo de Eve algoritmo basado en el siguiente URL: https://gist.github.com/ramonesteban/3617622
	print "Eve conoce: X, Y, g, p" #se muestra todo lo que intercepto Eve
	x = y = 0
	A = B = 0
	f1 = f2 =0 #se igualan a 0 todos los valores para que el algoritmo comience
	while A!= X or B != Y or r1 != r2: #mientras que cada uno sea diferente con su pareja se hace el ciclo
	if A!=X: #si la pareja A y X son diferentes
	x+=1 #se aumenta el supuesto valor de x en uno
	A = g**x%p #se obtiene la A a partir de la formula de cifrado con el supuesto x
	if B != Y: #si la pareja B y Y son diferentes
	y+=1 #se aumenta el supuesto valor de y en uno
	B= g**y%p #se obtiene la B a partir de la formula de cifrado con el supuesto y
	r1= Y**x%p #se obtiene r1 con la misma formula utilizando el mensaje de Alice en lugar del generador
	r2= X**y%p #se optiene r2 con la misma formula utilizando el mensaje de Bob en lugar del generador
	print "Se encontro que x de Alice= "+str(x) #cuando sale del ciclo ya habra encontrado x y lo imprime
	print "Se encontro que y de Bob= "+str(y) #cuando sale del ciclo ya habra encontrado y y lo imprime
	return #termina el Hackeo de Eve
	def main():
	p= int(raw_input("primo: ")) #se pide un numero primo
	g= int(raw_input("generador: ")) #se pide un generador
	turno=0 #se igualan los valores iniciales a 0
	Y=0
	X=0
	while turno<=1: #se utiliza un ciclo para controlar los turnos entre Alice y Bob
	X=AliceCifrar(p, g, turno, Y)
	Y=BobCifrar(p, g, turno, X)
	turno+=1
	Eve(X, Y, g, p) #se llama la funcion de alice despues de realizar la comunicacion
	main()

view raw Diffie.py hosted with ❤ by GitHub

En el código observamos cómo Eve hackea el algoritmo, utilizando al inicio supuestos x y y hasta encontrar los que son congruentes con el resultado de las operaciones de (X^y)%p y (Y^x)%p sustituyendo el valor del generador por X y Y.

En la ejecución del programa se muestra que Eve realmente logra Hackear el algoritmo.

ramsmunoz@ramsmunoz-Lenovo-B470:~/Escritorio$ python Diffie.py
primo: 23
generador: 5
Turno de Alice
x: 6
Turno de Bob
y: 15
Turno de Alice
x: 6
Alice recibe: 8
Bob cifrado= 262144
Turno de Bob
y: 15
Bob recibe: 19
Alice cifrada= 15181127029874798299
Eve conoce: X, Y, g, p
Se encontro que x de Alice= 6
Se encontro que y de Bob= 15

Dentro del programa, se le tiene que recordar el valor de x a Alice y el valor de y a Bob, al momento del segundo turno en la función de Alice y Bob, fue importante que se quedara así para cumplir realmente que sólo se tenga acceso a "x" y a "y" dentro de sus respectivas funciones.

No existe el modo automático dentro del programa, para la generación de números primos y los generadores, pidiendo al usuario la cantidad de dígitos. Lo cual se puede hacer, generando en una función números primos aleatoriamente, según un mínimo y un máximo estipulado, tomando el que concuerde con el número de cifras ingresado por el usuario, y después encontrar nuestro g, para próximamente pasar a nuestro algoritmo de Diffie-Hellman.

Conclusiones

Se puede observar que el algoritmo de Diffie-Hellman no es completamente seguro, ya que con el programa estamos mostrando su vulnerabilidad, pero se sabe que cuando se trata de números primos muy grandes, éste desafía la capacidad de procesamiento de las computadoras o sistemas distribuidos que intenten atacarlo.

Referencias

Autor: Javier Campos Título: "El algoritmo de Diffie-Hellman" Fecha: 22 de julio del 2011 URL: http://www.javiercampos.es/blog/2011/07/22/el-algoritmo-de-diffie-hellman/
Autor: Jesús García de Jalón de la Fuente Campos Título: "Protocolo Diffie-Hellman" Fecha: 02 de noviembre del 2009 URL: http://www.slideshare.net/fivefingers/protocolo-de-diffiehellman
URL de github: https://gist.github.com/ramonesteban/3617622

Tarea 2 Generación Pseudo-aleatoria Segura

INTRODUCCIÓN
Dentro de la Seguridad de la información, existe actualmente una necesidad de usar algoritmos de encriptación, seguros, confiables y más que todo, cero vulnerables a ataques del tipo estadístico, encontrando áreas de oportunidad en la plataforma en la que son construidos éstos algoritmos.

Es importante conocer las capacidades de cada lenguaje o plataforma, ya que puede que uno esté mejor preparado para éste tipo de procedimientos, ya sea con funciones ya construidas dentro de alguna librería, o con un sistema optimizado, para que al momento de usar números aleatorios, como herramienta algorítmica el nivel de vulnerabilidad a ataques, sea el mínimo.

PLANTEAMIENTO DEL CASO DE ESTUDIO
Se decidió evaluar la generación pseudo-aleatoria de números, en 4 lenguajes; C, Java, Ruby y Python, de los cuales por el prestigio, antigüedad y utilidad son llamados por grandes comunidades de programadores, como lenguajes muy estables y útiles para diferentes tipos de tareas.

Por lo tanto decidí construir un algoritmo en éstas 4 plataformas con pequeñas variantes respecto a las funciones disponibles que se pueden utilizar en cada lenguaje para al final realizar una comparativa.

HIPÓTESIS
Se piensa que se obtendrá un mejor resultado en el lenguaje Python, debido a que ha sido desarrollado para éste tipo de experimentaciones y se han encontrado más funciones que ayudan a facilitar la construcción del algoritmo, después de éste le seguirá Ruby, ya que es de los lenguajes más modernos, muy utilizados para el desarrollo web, que es en dónde más se necesita la seguridad informática y compartiendo muchas características con Python, no sólo de sintaxis.

Siguiente a éste es posible que sea C, ya que se puede observar cómo las funciones para aleatorizar nuestros números  utilizan herramientas cómo el tiempo del sistema, para poder generar números aleatorios uniformemente distribuidos y por último ponemos a Java, ya que se sabe que está muy orientado a negocios, software empresarial, bases de datos y otro tipo de implementaciones, por lo tanto supongo que al momento de querer hacer éste tipo de experimentos es el último lenguaje de éstos 4 que escogería.

EXPERIMENTACIÓN

Ruby
Programa: 

	class Generacion
	attr_accessor :arreglo, :aunico, :arepeticion, :numero, :repeticiones #funcion utilizada para el acceso a objetos
	arreglo=[]
	arepeticion=[]
	repeticiones = 0
	aunic=[] #se declaran arreglos y variables a utilizar
	puts "Ingrese la cantidad de numeros a generar: " #pide el numero de elementos
	numero = gets
	numero.to_i.times.map do |num| #Generacion de numeros aleatorios
	arreglo << 10000 + Random.rand(99999)
	end
	arreglo.each do |elemento| #Entontrar repeticiones
	if arreglo.count(elemento) > 1
	arepeticion << elemento.to_i
	end
	end
	arepeticion.each do |indice| #Eliminar repetidos
	arreglo.delete_if do |elemento|
	elemento == indice
	end
	end
	puts "Numeros repetidos por lo menos una vez: #{arepeticion.uniq}"
	puts "Repeticiones totales #{arepeticion.count}"
	end

view raw generador.rb hosted with ❤ by GitHub

Ejecución:

Ingrese la cantidad de numeros a procesar: 1000
Números repetidos por lo menos una vez: [10188, 35911, 106562, 28056, 64932]
Repeticiones totales 10


Python
Programa:

	def repeticiones(todos): #funcion que checa si hay repeticiones
	for i in range(len(todos)):
	for j in range(len(todos)):
	if j!=i:
	if todos[i]==todos[j]: #conficion que decide cuando hay una repeticion
	print "repetido encontrado: "+str(todos[i]) #Se agrega el valor del numero repetido
	return
	def random():
	import random
	x = int(raw_input("Cantidad de numeros a generar: ")) #se piden los numeros a generar
	array=list()
	todos=list()
	b = ''
	for i in range(x):
	array.append(random.randint(10000, 99999)) #Se generan numeros segun un rango
	todos.append(int(array[i])) #Se agregan en la lista todos
	repeticiones(todos)
	return
	def main():
	random()
	main()

view raw generador.py hosted with ❤ by GitHub

Ejecución:
Cantidad de numeros a generar: 1000
repetido encontrado: 77871
repetido encontrado: 77871
repetido encontrado: 61916
repetido encontrado: 78394
repetido encontrado: 13602
repetido encontrado: 78394
repetido encontrado: 36968
repetido encontrado: 13602
repetido encontrado: 36968
repetido encontrado: 88086
repetido encontrado: 61916
repetido encontrado: 88086

C
Programa:

	#include <stdio.h>
	#include <stdlib.h>
	int main(int argc, char* argv[])
	{
	int n, i, j;
	srand(time(NULL)); //Se inicializa la semilla con el tiempo del sistema
	n = atoi(argv[1]); //Se obtiene el valor de n
	int array[n];
	for(i=0;i<n;i++)
	{
	array[i]=(rand()%((99999+1)-10000))+10000; //Se asignan numeros aleatorios en el arreglo, por un ciclo
	}
	for (i=0;i<n;i++)
	{
	for (j=0;j<n;j++)
	{
	if(j!=i)
	{
	if(array[i]== array[j]) //checa si existen repeticiones, para después imprimirlas
	{
	printf("Repetido encontrado: %d\n", array[i]);
	}
	}
	}
	}
	return 0;
	}

view raw generador.c hosted with ❤ by GitHub

Ejecución:
Repetido encontrado: 84679
Repetido encontrado: 50850
Repetido encontrado: 29411
Repetido encontrado: 50850
Repetido encontrado: 29414
Repetido encontrado: 84679
Repetido encontrado: 11652
Repetido encontrado: 11652

Java
Programa:

	import java.util.Random;
	public class Generador{
	public static void main(String[] args){
	int i, j; //declaracion de variables
	int n = Integer.parseInt(args[0]); //se obtiene valor de n
	int array[] = new int[n]; //se declara el arreglo contenedor
	for(i=0;i<n;i++){
	array[i]= (int)(Math.random()*99999+10000); //En el ciclo se generan numeros aleatorios de 5 cifras
	}
	for (i=0;i<n;i++)
	{
	for (j=0;j<n;j++)
	{
	if(j!=i)
	{
	if(array[i]== array[j]) //se checa si existe una repeticion
	{
	System.out.print("Repetido encontrado: "); //imprime un mensaje y el numero encontrado
	System.out.println(array[i]);
	}
	}
	}
	}
	}
	}

view raw Generador.java hosted with ❤ by GitHub

Ejecución:
Repetido encontrado: 95887
Repetido encontrado: 74726
Repetido encontrado: 95887
Repetido encontrado: 70404
Repetido encontrado: 49909
Repetido encontrado: 43968
Repetido encontrado: 75409
Repetido encontrado: 49909
Repetido encontrado: 43968
Repetido encontrado: 59876
Repetido encontrado: 75409
Repetido encontrado: 59876
Repetido encontrado: 70404
Repetido encontrado: 74726


EVALUACIÓN DE RESULTADOS
Gráficas de los lenguajes en 1000, 500 y 250 números aleatorios:

Aquí observamos cómo en algunos lenguajes se tiene menos repeticiones en algunas ocasiones, pero hay que probar en un ejemplo más grande, generaremos 5000 y veremos quién tiene en promedio, menores repeticiones.
Gráfica comparativa de todos los lenguajes final

CONCLUSIONES
Se llegó a la conclusión de que nuestra hipótesis, no se cumple del todo, pero sí tiene ciertas similitudes con los resultados.
Ya que acertamos en que Ruby y Python son los mejores y más podernos lenguajes para éste tipo de experimentos, ya que unas de sus aplicaciones es el desarrollo web, en donde se necesita más que en otros lenguajes, la seguridad informática.
Y que Java y C son más vulnerables, en caso de ataques informáticos que se aprovechen de la generación pseudoaleatoria de números en éstos lenguajes.
Así que a la hora de hacer una aplicación de un algoritmo, si se tiene el conocimiento, hay que optar por Ruby y por Python, que según nuestro experimento, son los menos vulnerables.

REFERENCIAS
Autor: Víctor Cuervo Título: "Número Aleatorio en Java" Fecha: 07 de abril del 2007 URL: http://lineadecodigo.com/java/numero-aleatorio-en-java/
Autor: -- Título: "OverAPI" Fecha: -- URL: http://overapi.com/
Autor: Brian Schröder. Título: "Ruby en 15 minutos" Fecha: 15 de septiembre del 2006 URL: http://rubytutorial.wikidot.com/ruby-15-minutos