Buenas a todos,

Voy a meterme un poco en lo referente a PKI. El artículo probablemente sea un poco coñazo de leer, aunque tampoco me he metido en profundidad, pero la gente que ya controla también tiene derecho a leer algo no?

Empezaré con un poco de teoría.

Algoritmos asimétricos.
Los algoritmos de llave pública o asimétricos han demostrado su eficacia en entornos de comunicación inseguros como Internet. Su novedad fundamental respecto a la criptografía simétrica (misma clave para cifrar y descifrar) es que constan de una pareja de claves únicas, de la que una de ellas se hace pública, y la otra es privada para nosotros. Lo que se cifra con una, se descifra únicamente con la otra, y con este simple concepto jugamos.

Si A quiere mandarle algo cifrado a B, A le solicita su clave pública a B y cifra el mensaje con ella. De ésta forma sólo B podrá tener acceso al contenido descifrándolo con su clave privada.
Si A quiere mandarle un mensaje m a B, pero B necesita asegurarse de que realmente viene de A, y que nadie a modificado su contenido, procedemos de la siguiente forma. A genera un hash del mensaje m, H(m), y lo cifra con su privada H(m)Ka. Esto es lo que se conoce como firma digital. Luego A manda el mensaje m, la firma H(m)Ka y su clave pública a B. B descifra H(m)Ka con la pública de A, genera un hash del mensaje original H2(m) y lo compara con el H(m). Si coincide es que todo está bien.

Hasta la fecha han aparecido multitud de algoritmos asimétricos, pero en la práctica muy pocos son útiles, y su fuerza radica en la imposibilidad computacional de factorizar números primos grandes.

Los algoritmos asimétricos emplean longitudes de clave mucho mayores que los simétricos. Para los algoritmos simétricos se consideran seguros 128 bits, mientras que en los asimétricos se recomiendan al menos 1024. Además, la complejidad de calculo de estos algoritmos les hace unas 1000 veces mas lentos que los algoritmos simétricos, por lo que generalmente se utiliza un modelo mixto, consistente en cifrar los datos con un algoritmo simétrico, y luego cifrar la clave de cifrado simétrica con un algoritmo asimétrico.

Hay algoritmos como ElGamal y Rabin, pero el más popular es el RSA, que se mantiene todavía a salvo de ataques (con longitudes de claves grandes).

RSA
Este es el algoritmo más popular y seguramente el más sencillo de implementar. Desde su nacimiento nadie ha conseguido probar o rebatir su seguridad, y se le considera como uno de los algoritmos asimétricos mas seguros del mundo.

Sus claves se calculan a partir de un número que se obtiene como producto de dos primos grandes. Para recuperar el texto en plano a partir del criptograma y de la clave pública, hay que enfrentarse a un problema de factorización.

Para generar un par de claves (KP, Kp) primero se escogen aleatoriamente dos números primos grandes, p y q, y se calcula el producto n = pq.
Luego escogemos un número e primo relativo con (p-1)(q-1), por lo que existirá un número d tal que de ­­= 1 (mod (p - 1)(q - 1)).
Es decir, la inversa (d,n) es la clave privada, que puede calcularse fácilmente por el Algoritmo Extendido de Euclides.

Ciframos según la expresión c = m^e (mod n) y desciframos mediante m = c^d (mod n).

En la práctica, si el atacante quiere recuperar la clave privada a partir de la pública, debe conocer los factores p y q de n, lo cual presenta un problema computacionalmente intratable siempre que n, p y q sean lo suficientemente grandes.

Encontrar dos números primos.
Para que la solución sea única, se impone la condición de que los factores de n sean primos. Ya hemos visto que factorizando sería imposible calcularlos, pero afortunadamente existen algortimos probabilísticos para determinar si un número es primo o compuesto, como el método Lehmann y Rabin-Miller.
¿Hay realmente suficientes números primos para no tener que repetirlos?. El total estimado de números primos de 512 bits o menos es de 10^151. Si los almacenaramos en un disco duro que pesara un gramo por cada GB, el peso de ese disco duro le haría colapsar en un agujero negro.


Seguridad del RSA.
En realidad, el hecho de tener que factorizar el módulo n para descifrar un mensaje sin la clave privada es una suposición, aunque aún no se ha podido demostrar. Lo mismo en un futuro es posible.
También podríamos tratar de calcular Þ(n) directamente o probar por fuerza bruta, pero ambos ataques son mas costosos.
También cabría preguntarse que pasaría si los números primos p y q fueran compuestos. Si aplicamos 30 veces el método Rabin-Miller, las probabilidades de error son de una contra 2^60. Además, el algoritmo RSA no funcionaría.

Ataques contra RSA.
Man in the middle.
Por ejemplo A quiere establecer una comunicación con B, y C quiere espiarla. Cuando A le solicite a B su clave pública Kb, C se interpone obteniendo la clave de B y enviando una falsa Kc a A. Cuando A codifique el mensaje, C lo interceptará descifrándolo con su clave KC, y se lo enviará a B recodificado con su propia clave Kb.
Evidentemente esto se evita asegurando a A que la clave pública de B es verdadera, mediante el uso de certificados o firmas de confianza.

Texto escogido.
Para falsificar una firma sobre un mensaje m, se pueden calcular dos mensajes m1 y m2 tales que m1m2 = m, y enviárselos a la víctima para que los firme.
Entonces obtendríamos un m1^d y un m2^d. Aunque desconozcamos d, si calculamos m1^dm2^d = m^d mod n obtendríamos el mensaje m firmado.

Módulo Común.
Si una vez generado p y q, nos ponemos a generar tantas llaves como queramos sin emplear dos números primos diferentes, un atacante podría descodificar nuestros mensajes sin necesidad de la clave privada.
Sea m el texto en plano, y e1 y e2  dos claves de cifrado diferentes. Tenemos que:
c1 = m^e1 (mod n)
c2 = m^e2 (mod n)
El atacante conoce c1, c2, e1, e2 y n. Lo más probable es que e1 y e2 sean primos relativos, así que le Algortimo Extendido de Euclides nos permitirá encontrar r y s tal que:
re1 + se2 = 1,
con lo que c1^rc2^s = m^(e1r)m^(e2s) = m (mod n).


PKI X.509
Bien, vamos a ver como se explota este conglomerado matemático.

Como hemos visto anteriormente, si firmo un documento antes de enviarlo, estoy diciéndole a los demás que lo he enviado yo, pero, quien soy yo? Que algoritmos uso?

Aquí entran en juego los certificados. Un certificado, además de tener una serie de datos como número de serie, entidad emisora, algoritmos usados, etc., es esencialmente una clave pública y un identificador, firmados digitalmente por una autoridad certificadora, y su utilidad es demostrar que una clave pública pertenece a un usuario concreto.
El mecanismo que debe emplearse para conseguir un certificado es generar una pareja de claves asimétricas, pública y privada, y un identificador con nuestros datos. Enviar nuestra clave pública --¡Nunca la privada!-- junto con nuestro identificador a la autoridad certificadora, después de habernos identificado positivamente frente a ella, nos enviará nuestro certificado que no es otra cosa que nuestra clave pública y nuestro identificador, firmados con la clave privada de la Autoridad certificadora

Las claves asimétricas para los certificados se generan en el equipo del usuario ya que toda la infraestructura PKIX se basa en que sólo el propietario de la pareja de claves posee la clave privada. El encargado de generar dichas claves es el "CSP" (Proveedor de servicios criptográficos) de cada usuario. Cuando accedemos a las páginas de emisión de certificados (online) de una autoridad certificadora, se "llama" al registro de su sistema en busca de los "CSPs" disponibles, para que el usuario seleccione uno. Es en este momento cuando podemos escoger si el certificado se almacenara en nuestro disco duro o en un soporte criptográfico externo, llaves USB (iKey), lectores de tarjetas criptográficas, etc.
El formato de certificado X.509 es el más común y extendido en la actualidad, y es del que voy a hablar. Sé que sois amantes del software libre y del PGP, pero estos sistemas generalmente se basan en el concepto de "los amigos de mis amigos son mis amigos" para los niveles de confianza, y con esa filosofía, que queréis que os diga.

Los certificados PKIX se estructuran de forma jerárquica, de tal forma que nosotros podemos verificar la autenticidad de un certificado comprobando la firma de la autoridad que lo emitió, que a su vez tendrá otro certificado expedido por otra autoridad de rango superior. De esta forma vamos subiendo en la jerarquía hasta llegar al nivel mas alto, que deberá estar ocupado por un certificado que goce de la confianza de toda la comunidad.

Si nos sacamos un certificado de la Fábrica Nacional de Moneda y Timbre, previa confirmación de nuestra identidad, y que está avalado por la administración pública, nuestras firmas digitales pasan a tener el mismo valor legal que las manuscritas, con lo que podemos firmar contratos, etc.

Bueno, esto así por encima. Ya otro día hablaré de las posibilidades de esto, que son más de las que os imaginais.

Salu2.

Ya platique de esto contigo en privado unravel, pero quiero darlo a conocer un poco

hace poco leí un articulo sobre un nuevo método para factorizar numero grandes (que bueno nunca dijeron la fecha xD)

en este aseguraban que era una tonteria tratar de dividir un numero entre uno que se sabe que no es divisible (15/2 :S), pero en numeros muy grandes mi cabeza no ve como saberlo

26382571685468127963281657184568 es divisible entre 28512875541?

(en los algoritmos los numeros son muchisisisisisisisisisisimo mas grandes, esto es un ejemplo)

bueno, esto se explica asi:

la multiplicación, tomando en cuenta que es de solo 2 numeros, es algo asi:
siendo x el producto de ab

a>=2 y a<=(x)^(1/2)
b>=(x)^(1/2) y b<=x/2

si ven todos los numeros compuestos cumplen esa regla.

15,36,85 por ejemplo

15 = 3*5
3>=2 (true)
3<=3.~ (true)
5>=3.~ (true)
5<=7.5 (true)

36=6*6
6>=2 (true)
6<=6 (true)
6>=6 (true)
6<=18 (true)

85=5*17
5>=2 (true)
5<=9.~ (true)
17>=9.~ (true)
17<=42.5 (true)

bueno eso es un poco obvio xD

en fin, si vemos entre mas grande es un numero, su raiz cuadrada, aumenta en menor cantidad..
es decir.. la diferencia entre la raiz cuadrada de 81 y 144 (144-81=63) es de 3 (9 y 12), sinembargo la diferencia entre la raiz cuadrada de 9801 y 10404 (10404-9801=603) es de 3 (99 y 102) tambien.

esto es obvio tambien

entonces a donde voy? que debes de factorizar solo de la raiz cuadrada de x hasta 2, y no desde x-1
bueno.. eso no es ningun descubrimiento xD, solo es para que lo tengan en cuenta.

este articulo decia, que era tonto tratar de dividir entre tantos numeros, si sabemos que por sus propiedades, no puede ser divisible en una gran cantidad, y el metodo que proponia era el siguiente.

tenemos un número.
26382571685468127963281657184568
y vamos a factorizarlo.
para eso hacemos varias cosas, primero
vemos ese 8, que numeros de una cifra al multiplicarse me pueden dar 8 en la ultima cifra?
1 y 8
2 y 4
3 y 6
4 y 7
6 y 8
9 y 2

bueno, entonces un número tiene los de la primera columna y el otro los de la otra..
parecen muchos, pero poco a poco se van haciendo menos.

ahora hacemos lo mismo pero con la primera cifra.
aqui tenemos que considerar 2 numeros, que nos den ese numero y que nos den ese numero menos 1
es 2
factorizamos 2 (siempre es una cifra xD)
1 y 2
factorizamos 1
1 y 1

entonces ya tenemos el primer digito de los 2 numeros, uno es 1 y el otro es 2 (o 1)

el segundo número es 6, lo factorizamos (este numero y ese numero mas 10)

6
3*2

16
8*2
4*4

y menos 1
5
5*1

15
3*5

ahora tenemos:
si los numeros en la segunda posición son 3 y 5 , 8 y 2 ó 4 y 4
los primeros son 1 y 1
si los numeros en la segunda posición son 5 y 1 ó 3 y 2
los primeros son 1 y 2

ahora, para saber si es la primera opcion o la segunda, hacemos el mismo procedimiento pero con los numeros en la tercera posición, luego la cuarta, etc.. hasta que lleguemos a la ultima cifra, y los numeros que coincidan con los que sacamos en el primer paso (1 y 8 - 2 y 4 - 3 y 6 - 4 y 7 - 6 y 8 - 9 y 2) son los que establecen cuales son los numeros de la penultima, y esos lo de la antepenultima, etc.. hasta llegar a la primera.
Siempre eliminas si el numero del factor es mayor a 18.
estas te daran varios resultados, y todos los que te den son factores de el numero dadl al principio.
del numero de ejemplo (26382571685468127963281657184568) saco 32 factores (el programa tardo 1.28 segundos en sacarlos, y lo hize yo asi que un prog de alguien mas (!) talvez lo haga mas rapido):

1 y 26382571685468127963281657184568
2 y 13191285842734063981640828592284
4 y 6595642921367031990820414296142
8 y 3297821460683515995410207148071
245789 y 107338292948293568724725912
491578 y 53669146474146784362362956
983156 y 26834573237073392181181478
1018931 y 25892402611627409474519528
1966312 y 13417286618536696090590739
2037862 y 12946201305813704737259764
4075724 y 6473100652906852368629882
8151448 y 3236550326453426184314941
250442031559 y 105344025207097996552
500884063118 y 52672012603548998276
1001768126236 y 26336006301774499138
2003536252472 y 13168003150887249569

quiero aclarar que la factorización con curvas elipticas (muy muy muy rapida  tardo 1.69 segundos) asi que este metodo en si, ya comprobo que es mas rapido.. (y al estar hecho por mi, novato a comparación)

voy a hacer una prueba de concepto con un numero de 4 cifras para no hacer muy largo este documento.

1827


numeros de 7 en ultima cifra:
7*1
3*9

y de  1 y 0

factorizo 1
1*1

factorizo 0
0*0

PASO 2

factorizo 8
4*2
8*1

factorizo 7
7*1

----------
factorizo 18
9*2
6*3
//18*1

factorizo 17
//17*1

PASO 3

factorizo 2
2*1

factorizo 1
1*1

----------
factorizo 12
6*2
3*4
//12*1

factorizo 11
//11*1

PASO 4

(el // es que ese numero no aplica)

ahora con los numeros de el primer paso:
7*1
3*9

se hace un arbol con todas las combinaciones Y SE LE SUMA EL NUMERO DE CADA CASO ANTERIOR

de esta forma con una tabla, nunca se hace una division, solo sumas y multiplicaciones, lo que hace muchisimo mas rápida la factorización.

Unravel dice que miles de veces mas rápido es nada a comparación de lo que enfrenta contra un numero de millones de dígitos, y tiene razón, pero yo digo, que no es necesario miles de veces mas rapido, con ser 3 veces mas rápido es un GRAN GRAN avanze.

Saludos!! y espero me hallan entendido

Unra, pero lo que tienes que factorizar es K, y es la multiplicación de un número primo -1 por otro menos 1 y estos no son primos, de hecho es imposible que lo sean, porque de por si, son divisibles entre 4.

como lo veo, el reto real es K/4 o incluso entre 6.. y despues debes hacer coincidir los 2 factores en donde A+1 sea primo y B+1 tambien lo sea, es por eso que es tan seguro este algoritmo.. in numero de muchos factores es extremadamente complicado de hacer coincidir el a+1, b+1

Sobre los algoritmos cuanticos, es otra cosa, estos prometen vulnerar totalemtne RSA, y si es verdad que IBM y HP tienen maquinas cuanticas, es cuestion de tiempo, que todaslas universidades, y gobiernos tengan control sobre una, lo que nos dejaria a los mortales, lejos de la criptografia moderna.. ya que los nuevos algoritmos estan basados en algoritmos cuanticos, y la teoria del caos, que tambien es muy interesante.

por ejemplo, estaba leyendo de cierta encriptación, que era un tipo lenguaje ensamblador, que al correr, el mismo programa, se recompilaba, y usaba valores del mismo codigo, lo que hacia que si tratabas de monitorearlo, los valores que obtiene varien, y sea imposible su desencriptación, es algo tipo algoritmos cuantica (y teoria de incertidumbre sin serlo realmente), mucho menos segura, pero que almenos nos puede acercar a ese mundo que nos depara el futuro, hemos vivido el 11-9 el inicio del nuevo milenio, y el desarrollo de la teoria y aplicación cuantica, bienvenidos al siglo 21.

Saludos!!!

bueno unra, el tiempo depende de la computadora donde lo tratas xD, lo use como comparación, si contigo tardo 0.26 segs (por ej.), solo hay que hacer una regla de 3, el programa te lo paso por privado, pq estoy teniendo problemas con el foro.

sobre el metodo de SNFS, no encontre ningun programa que lo use, y me dio flojera hacerlo yo , por eso use el de curvas elipticas..

el numero: 66024717357306257987, me tardo 0.21 segundos xD
4142118787 x 15939841601
con curvas elípticas 0.25

el programa de curvas elipticas que estoy usando es:
http://alpertron.com.ar/ecmc.java
con muy ligeras modificaciones, para el tiempo, y 2 que 3 errores que me salieron.

el único numero que no he logrado factorizar es este:
20404106545895102906154128522206995414761716518871165973
pero tenle paciencia a mi Pentium III, con 256 xD
haber quien puede

sabes que me gustaria empezar a hablar aqui?, como encontrar numeros primos muy grandes

digo, se que en la suceción de fibo cuando es primo relativo de otro numero fibonacci es primo abs, y aunque existen multiples métodos, ese tema me encanta.

aparte, la conjetura de goldbach y el ultimo teo. de fermat, han sido mis adicciones desde hace mucho xD, aunque tiene poco que ver el teorema de fermat con criptorafia, este señor, creo otro pequeño teorema que aveces encuentra primos, el de 2^(2^x)-1, o tambien con x!+/-1.

ya me desvié del tema xD, pero bno, termino de explicar, lo de la conjetura de goldbach:

x=p+q, donde p y q son numeros primos
aveces no se cumple asi sino:
x=p+q+r+s
que es lo máximo que se ha descubierto, pero aun no se sabe porque, se ha comprobado hasta 10^14

que bien, hace mucho que no hablaba de esto xD.

Saludos!!