El futuro de la criptografía
kub0x:
Por ejemplo, si trabajamos con permutaciones en el grupo de enteros multiplicativos modulo 19 (primo), en vez de hacer g^x mod 19 vamos a hacer s^x donde s es una permutacion. ¿Pero cómo? Bueno, cada elemento de este grupo finito y cíclico es a su vez una permutación, por lo tanto este grupo es isomorfo (o equivalente) a un grupo de permutaciones. EN CRISTIANO vamos a intentar romper un ejemplo sencillo de Diffie-Hellman de una manera diferente aprovechando el tema de las permutaciones y teoría de grupos.
Si mi valor privado x=13 y g=2 (el generador, este grupo tiene 6 en concreto), entonces el valor público es 2^13 mod 19 = 3. Vale, vamos a buscar el exponente x sabiendo sólo el 3.
Alguien ajeno a la criptografía podría iterar desde 2 hasta 17, para determinar el valor, fuerza bruta con 16 posibles valores.
Alguien más avispado puede hacer uso de las simetrías del exponente y computar 8 posibles valores.
Un matemático podría aplicar el cálculo de índices (index calc) que es lo recomendable para módulos con bit size grandes.
Otro enfoque matemático es hacer el cálculo de permutaciones como os voy a mostrar (teorema de cayley en teoría de grupos. Todo grupo es representable mediante permutaciones si la accion G x G es faithful):
Empezamos sacando la tabla del 2 mod 19 : 2 4 6 8 10 12 14 16 18 1 3 5 7 9 11 13 15 17 (pares-impares no tiene misterio, multiplicar 2*i es hacer sumas de dos "i" veces)
De aquí sacamos el ciclo de permutación. Es una permutación porque los símbolos del 1 al 18 no se repiten en la secuencia. Dicho ciclo es:
(1,2,4,8,16,13,7,14,9,18,17,15,11,3,6,12,5,10) y se lee en 2^0 es 1, 2^1 es 2 2^ 2 es 4, 2^3 es 8 ... WOPS SI SON las exponenciales de 2^x mod 19. Y sólo haciendo sumas y sacando el ciclo, vemos como el valor público 3 está en la posicion 14, le restamos 1 porque empezamos por 2^0 si recordaís, entonces nos da 13, el valor x que buscabamos. Para sacar el ciclo (no me lo he inventado je je) debeís coger la permutacion que empieza por 2 4 6 8 ... y pensar, posición 1 está el 2, posición 2 el 4, en la 4 el 8, en la 8 la 16 etc y os sale el susodicho.
Podemos ir más allá, y sacar ciclos exponenciales como expliqué por aquí: https://crypto.stackexchange.com/questions/71258/what-can-be-said-about-the-self-power-map-on-groups-based-on-dlp
En ese post podemos ver que no hay que computar toda la permutación, y está garantizado que se recupera "x" pero su coste operacional debe estar por la raiz de la longitud media de un ciclo, cuya longitud depende del número de ciclos de la permutación (concepto contenido en random permutation statistics).
Saludos >:D
Usuario887:
A los sistemas critpograficos lo que pinturas han hecho los pintores. A pesar de las limitaciones para con las herramientas que se utilizan para emular matematicamente lo que se imagina como una forma de transformar informacion, lo unico que permanece omnipotente es la imaginacion. Para mi el critpoanalisis es fundamentalmente lo mismo que observar una pintura hasta ver las manos del pintor, y seguira siendo asi hasta que pueda expresarse (de la misma forma) el azar en una ecuacion.
B€T€B€:
No estoy muy puesto en la materia, pero lo que si se es que los ordenadores cuánticos lo único nuevo que aportan es una gran capacidad de cálculo.
Por un lado se podría intentar volver más complejo el cifrado; intentando dejar "no funcional" la capacidad de cálculo de los ordenadores cuánticos.
Otra opción sería tirar de imaginación (no me preguntéis cómo) volver inútil esa inmensa capacidad de cálculo.
@XSStringManolo:
Cita de: B€T€B€ en 26 Abril 2020, 21:46 pm
No estoy muy puesto en la materia, pero lo que si se es que los ordenadores cuánticos lo único nuevo que aportan es una gran capacidad de cálculo.
Por un lado se podría intentar volver más complejo el cifrado; intentando dejar "no funcional" la capacidad de cálculo de los ordenadores cuánticos.
Otra opción sería tirar de imaginación (no me preguntéis cómo) volver inútil esa inmensa capacidad de cálculo.
Si no sabes lo que tienes que encontrar da igual lo bueno que seas buscando no?
Cifrados por obscuridad. Ahora mismo son todo lo contrario al camina al seguir, pero si nos ponemos en el hipotético caso de super computadores...
kub0x:
Vaya, si que va tomando forma el tema. Publicad lo que veaís conveniente, si conoceis alguna historia asociada a la criptografía o cualquier tema asociado, pues sed libres de comentar.
Cita de: B€T€B€ en 26 Abril 2020, 21:46 pm
Por un lado se podría intentar volver más complejo el cifrado; intentando dejar "no funcional" la capacidad de cálculo de los ordenadores cuánticos.
Otra opción sería tirar de imaginación (no me preguntéis cómo) volver inútil esa inmensa capacidad de cálculo.
Por ahí van los tiros. Por ejemplo, esquemas basados en lattices se basan en el problema del vector más cercano (SVP), en cripto multivariada se basan en el MQ problem (multivariate quadratic polys) y el IP (Isomorphism of Polynomials). En las curvas supersingulares, tenemos el claw finding problem (el mejor ataque tiene coste operacional bajado a la raiz cuarta sobre el primo p, not bad).
Un ordenador cuántico no sabe interpretar estos problemas, al igual que el clásico, lo que se pretende para "romper" estos criptosistemas es puramente rebajar la seguridad unos bits, o bien, encontrar vulnerabilidades de DISEÑO. De aquí deducimos que un ordenador clásico y un cuántico están en las mismas condiciones, hasta que alguien consiga diseñar un circuito especial para estos problemas. Ya veremos lo que dicta el tiempo, probablemente esta década me toque estudiar física y computación cuántica para programar algoritmos.
Cita de: @XSStringManolo en 26 Abril 2020, 22:40 pm
Si no sabes lo que tienes que encontrar da igual lo bueno que seas buscando no?
Hay una frase para ilustrar esto: Cuando el ingenío se queda pequeño, no basta con poner empeño, sólo el talento consigue el diseño. Y lo que quiere decir, es da igual cuanto te esfuerces, sino eres creativo, jamás llegarás a tu meta. Teniendo ingenio + empeño, tampoco llegas a nada, necesitas el talento y eso son años de estudio en el ámbito de la criptografía. Los antiguos filósofos ya debetían sobre si el genio era talentoso o iba más alla. Buscad por docta ignorancia en YT.
Cita de: @XSStringManolo en 26 Abril 2020, 22:40 pm
Cifrados por obscuridad. Ahora mismo son todo lo contrario al camina al seguir, pero si nos ponemos en el hipotético caso de super computadores...
Como bien recalcas, ahora es todo lo contrario a la oscuridad. Es una de las normas del principio de Kerchoff: se conoce el diseño y la funcionalidad del criptosistema. Por lo tanto el atacante tiene todos los detalles, pero no tiene los valores privados, él ha de buscarlos. La oscuridad es un término neandertal que ya no vale en lo profesional. Puede valer para ciertas aplicaciones, pero en criptografía es considerado un pecado, así como implementar tu propia criptografía o implementar criptografía ya existente, en fin hay tantos pitfalls.
CONSEJO PERSONAL: Cuando empecé a intersarme por las matemáticas de la criptografía (año 2014), ví que me faltaba una base abrumadora, ya no sólo es teoría de números, sino de grupos, de cómputo operacional, de algebra combinatorial, lineal, algebra geométrica, teoría rep, simetrías, matemática discreta, finita, no lineal y a eso sumarle ser experto (o casi) en el manejo de Wolfram Mathematica y C++ para poder hacer tangible mi estudio. Tienes que estar al día con una decena de campos (matemáticos y el state of art en crypto), sino, te pasará lo mismo que a mí hace 5 años, harás criptoanálisis muy básico y "descubrirás" propiedades y métodos ya existentes en literatura. Por el momento, no he ganado un duro con esto y supongo que seguirá siendo así hasta que "yo lo pete", sin prisas.
Saludos.
Navegación
[*] Página Anterior