¿Serias capaz de deducir la funcion inversa de un algoritmo de cifrado?

[Usuario887]

No soy matematico, pero entiendo que los numeros se definen en un contexto logico. Incluso diria que el concepto de "numero irracional" esta mal nombrado. Es casi costumbre pensar en descifrar (nunca nos enfocamos en descifrar el algoritmo, sino en descifrar el mensaje, lo cual, aunque es el objetivo final, no es precisamente el caso) un mensaje a traves de todo menos el mismo algoritmo. Creo que es totalmente posible descifrar un mensaje utilizando el mismo algoritmo, es decir, aplicando su misma logica. Lo que digo lo aplico a algoritmos de reduccion como hashes (por ejemplo, MD5), y otros que no dependen directamente de un valor indeterminado (una clave), aunque, si bien digo esto, creo que el mismo concepto podria utilizarse, si bien no para propiamente descifrar un resultado de un algoritmo como RSA, simplificar de una forma impresionante su resolucion sin la necesidad de la potencia de procesamiento de una maquina como las basadas en tecnologia cuantica.

En fin, basta de verborreas. En este post pretendo presentar un algoritmo, si bien simple, simetrico en terminos logicos con los algoritmos mencionados. Luego, no pretendo que este auditorio resuelva un contenido de un mensaje, sino, resuelva el algoritmo. No todo son formulas, no todo puede tener un nombre y puede ser escrito. El conocimiento intuitivo es a traves del cual puede lograrse concluirse tal cosa. Y es de hecho el conocimiento intuitivo lo que representan tales simbolos (operaciones, formulas, etcetera), sin embargo los nombres y los mismos simbolos terminan oscureciendo con la costumbre sus verdaderos significados.

El algoritmo se define como sigue:

E(m x)=m x+(m x+1)
E(m n)=m n+1

Como puedes ver, bastante simple; cada elemento se suma al siguiente y, por ultimo, al ultimo elemento se le suma 1.

Por ejemplo: 1,2,3,4 -> 3,5,7,5

El objetivo es concluir una formula igual de simple e inversa. Para ser exactos, incluso que cuente con la misma cantidad de operaciones.

Saludos.

[Serapis]

No soy matematico...

Lo que digo lo aplico a algoritmos de reduccion como hashes (por ejemplo, MD5), y

Con la primera afirmación y rematando con la segunda se entiende que sigas ese camino, pero es erróneo....

Los algoritmos de resumen a diferencia del cifrado son irreversibles.

Te voy a poner un simple ejemplo de una función diseñada solo para esta explicación:

funcion resumen nombre: B0B0
Descripción: Suma todos sus dígitos y lo modula con 10.
Ejemplo: sea el contenido a tratar esto: 12345678903648327523634954
- Aplicando la primera parte del algoritmo descrito...: 1+2+3+4+ ...9+5+4 =119 (si no he sumado mal)
- Aplicando la segunda parte del algoritmo descrito: hash = 109 modulo 10
- Hash obtenido: = 9

Bien, ahora explícame como obtienes el contenido original solo con el hash ("9") y la descripción del algoritmo... será interesante saber qué pasa por tu mente, a ver como haces una formula igual de simple e inversa (pués más simple que este algoritmo B0B0, no te lo vas a encontrar). Si solucionas éste, te garantizo que el resto también tienen solución.

p.d.:

Creo que es totalmente posible descifrar un mensaje utilizando el mismo algoritmo

Las matemáticas, se pueden permitir el lujo de 'creer' durante un tiempo, pero al final (para convencer al resto) exige demostración sí o sí.

[Usuario887]

el lujo de 'creer'

¿Qué es entonces el la verdad? Una hueste en movimiento de metáforas, metonimias, antropomorfismos, en resumidas cuentas, una suma de relaciones humanas que han sido realzadas, extrapoladas y adornadas poética y retóricamente y que después de un prolongado uso, un pueblo considera firmes, canónicas y vinculantes.

http://serbal.pntic.mec.es/~cmunoz11/nietdomingo.html

Bien, ahora explícame como obtienes el contenido original solo con el hash ("9")

Es imposible deducir con certeza cual fue, entre las posibles entradas que resultan en el hash 9, la que lo produjo en ese instante, pero, ¿A quien le importa ese instante?

99999999999992 produce el mismo hash que 12345678903648327523634954. ¿Que importa, entonces, 12345678903648327523634954?

Curiosamente, 99999999999992, es la menor cantidad posible que resulta en un hash "9".
Me pregunto quienes en la escuela se aprendieron el minimo comun multiplo, me pregunto tambien quienes entendieron el minimo comun multiplo.

Gracias por tu respuesta.
Saludos.

Una de las propiedades deseables de las funciones de hash criptográficas es que sea computacionalmente imposible que se produzca una colisión.

https://es.wikipedia.org/wiki/Colisi%C3%B3n_(hash)

se pueden permitir el lujo de 'creer' 'desear' durante un tiempo, pero al final (para convencer al resto) exige demostración sí o sí.

[kub0x]

@Serapis: Como es una función de resumen lo interesante no es encontrar el input "123456789...." sino una colisión y es trivial encontrarla modulo 10, cosa que ya sabeís ambos usuarios del post.

Preguntaban ahí cual es la inversa de cualquier función [latex]f(x)[/latex]? Bueno, la inversa composicional por izquierda y por derecha (left- right inverse) garantiza que [latex]f(x)[/latex] tiene inversa sobre el dominio especificado, normalmente un finite field [latex]F_q[/latex] o bien el anillo de los enteros modulos n, [latex]Z_n[/latex], ya que en el hipotético caso [latex]f^{-1} \circ f(X) = X[/latex] además de [latex]f \circ f^{-1}(X) = X[/latex].

Es decir, [latex]f(x)[/latex] ha de permutar el dominio completamente, por lo tanto es bijectiva (injectiva y surjectiva) y su inversa EXISTE. Ahora, encontrarla no es trivial. Y como he reflejado, primero has de responder la pregunta de si [latex]f(x)[/latex] es una permutación del dominio (un automorfismo).

A día de hoy, los matemáticos siguen rompiéndose la cabeza para encontrar un MÉTODO GENERAL, cuya existencia podría ser plausible, sin embargo, las condiciones de las inversas de dichas funciones son increíblemente díficiles de comprender, manipular y variar.

Como este es el subforo de Criptografía, los números Racionales, Reales y Complejos son nuestros enemigos   por lo tanto trabajamos con los enteros, o bien, grupos, anillos y/o fields así mismo polynomial (quotient) rings o algebras asociativas.

Digamos que quiero cifrar un plaintext, por aquí los que sabeís, podrías decirme utiliza trapdoors basadas en el logaritmo discreto, por lo tanto utilizamos El-Gamal, Three-pass Diffie-hellman, RSA, ECIES etc. Otra persona te diría, utiliza algoritmos post cuanticos como los basados en isogenies (SIDH/SIKE), lattices o multivariated. Otra persona puede decirme, utiliza crypto no-conmutativa, basada en teoría de grupos, cuya representación es matricial por lo tanto podríamos usar matrices

Finalmente, otra persona me díria, utiliza Criptografía Simétrica como AES, Blowfish, Chacha, Salsa20 con modo de bloque X y algoritmo MAC Y ó bien utiliza algoritmos AEAD...

Lo que quiero decir que este campo es amplio, y cualquiera puede introducirse y crear algoritmos y primitivas, pero lo realmente importante es: que tan desarrollada está la teoría, si existen ataques notorios que complican la construcción de la clave y/o el cifrado/descifrado y la construcción/verificación de firmas digitales (AQUI entra el criptoanalisis), si un sistema embebido es capaz de reproducir el algoritmo (Portability, cross-platform), si su implementación es tediosa (leaks, side channels, error-prone...), si la clave toma demasiada memoria (incrementan latencias en el sistema y en la red además de consumir más RAM) ...

Saludos.

[Usuario887]

los matemáticos siguen rompiéndose la cabeza para encontrar un MÉTODO GENERAL

Nunca podran lograrlo con la matematica convencional. Intentar deducir el prodecimiento inverso de un conjunto de operaciones de suma, resta, multiplicacion y division a traves de sumas, restas, multiplicaciones y divisiones es... como ver un trozo de metal ardiendo e intentar apagarlo con un soplete solo porque 'sopla'.

Gracias por tu respuesta. Voy a usar tus terminos para investigarlos.

Una solucion a esto seria una total revolucion...

[kub0x]

Nunca podran lograrlo con la matematica convencional. Intentar deducir el prodecimiento inverso de un conjunto de operaciones de suma, resta, multiplicacion y division a traves de sumas, restas, multiplicaciones y divisiones es... como ver un trozo de metal ardiendo e intentar apagarlo con un soplete solo porque 'sopla'.

Gracias por tu respuesta. Voy a usar tus terminos para investigarlos.

Una solucion a esto seria una total revolucion...

Mayormente es así, no puedes reglar y clasificar todas las funciones de la misma manera. En el campo del álgebra abstracta, concretamente en Finite Fields, se conocen inversas composicionales. AES por ejemplo utiliza una función cuya inversa composicional es obtenible. El criptosistema de Matsumoto-Imai utiliza otra inversa composicional basado en un monomio X^e, cuya inversa es X^d ya que [latex]X^{ed} =X[/latex]. Otro ejemplo serían los Dickson Polynomials son permutaciones de [latex]F_q[/latex] y su inversa composicional es obtenible. Pero estas resoluciones no se aplican a la teoría en otros cuerpos o dominios. Desde luego, que si se encontrara una forma general para sólo los Finite Fields ya sería una gran revolución...

Enlaces de interés: http://www.math.udel.edu/~coulter/papers/doinverse.pdf

Saludos.

[Usuario887]

Enlaces de interés: http://www.math.udel.edu/~coulter/papers/doinverse.pdf

Interesante apunte... lo guardare en mi carpeta de "late-night reading", jajaja...

Gracias por la informacion.
Saludos.

[Serapis]

Es imposible deducir con certeza cual fue, entre las posibles entradas que resultan en el hash 9, la que lo produjo en ese instante, pero, ¿A quien le importa ese instante?

Justamente importa a quien debe procesar que el resultado generado/recibido en ese instante coincide con el almacenado. Luego claro que importa.

... de todos modos, eres tu el que dijo eso de: "Creo que totalmente es posible descifrar un mensaje utilizando el mismo algoritmo ... lo aplico a algoritmos de reduccion como hashes (por ejemplo, MD5)"

Curiosamente, 99999999999992, es la menor cantidad posible que resulta en un hash "9".

No. El menor es simplemente 9.
Una cualidad intrínseca a los hashes, es que no se sabe el tamaño de origen, podría ser 1 byte, 100 millones o cualquier tamaño intermedio...

99999999999992 produce el mismo hash que 12345678903648327523634954. ¿Que importa, entonces, 12345678903648327523634954?

Cualquier múltiplo de 9 genera el mismo hash... era importante hacerte notar la infinitud de colisiones para que entiendas que el problema radica en la indecibilidad de reconocer cual fue el origen. Si te pongo de ejemplo un algoritmo cuya dificultad en hallar colisiones es complicado, flaco favor haría al caso...

En principio hablas de un modo genérico al señalar los algoritmos de hashes, sin embargo al llegar a este punto, parece más bien que te ciñas (en exclusivo) a los referidos específicamente a los algoritmos de hashes sobre criptografía. Hay muchas cosas que se podrían decir, pero no pretendo extenderme demasiado, tan solo unos puntos.

A - Utilizar hashes en crudo, no es buena idea, precisamente porque pueden ser alterados mediante las técnicas Mitm. Si no que suelen llevar otras alteraciones/añadidos, por ejemplo aplicando un simple algoritmo de Luhn al hash (que añade un simple byte al final), no te bastaría incluso en el supuesto caso de que pudieras generar colisiones para un hash, un simple byte podría suponer que tendrías que generar entre 1 y 256 colisiones idénticas (128 de promedio). Como dicho hash se aplica calculando el texto de origen (también es un hash, de hecho es el primer algoritmo de Hash, pues fue Peter Luhn recisamente el que inicialmente sugirió tales técnicas), no vendrá a coincidir con lo tuyo, con tu dato ficticio para generar la colisión al aplicársele el algoritmo (o si, 1 entre 256 posibilidades).

B - Aunque un programa calcule un hash más o menos simple, se supone que será cifrado antes del envío, luego técnicamente tampoco tienes modo de saber (a priori) dicho hash. Luego sin tal conocimiento un intento de hallar colisiones carece de sentido.

C - Cuando se diseña un algoritmo para hashes, una de las principlaes cualidades buscadas es intentar evitar colisiones todo lo posible, ahora bien, dado que el caso trata del campo de Galois, reducirlo a otro más pequeño, sí o sí tiene que haber colisiones, entonces se miran algunas cualidades:
---- Que la dispersión sea lo mas uniforme posible.
---- Que no haya acumulaciones.
---- Que el tamaño de reducción contenga todavía el mayor amplio abanico de posibilidades (si el rango M-N tiene que ser reducido a uno más pequeño X-Y, cuanto más grande sea el rango X-Y, tanto más difícil será que se produzcan colisiones si las dos propiedades previas se dan.
Por eso mismo, los algoritmos de hashes con el tiempo se deshechan y/o modifican (evolucionan) (ejemplo: MD2, Md3, MD4, Md5...)para cubrir posibles fallos o simplemente para aumentar el rango de valores que generan 128 bits (16 bytes), 256, 384, 512, etc...

D - Cuando diseñas una tabla Hash (por ejemplo), una de las cosas que debes hacer obligadamente (si eres celoso de tu trabajo), es verificar precisamente las cualidades del hash, para asegurarte que es óptimo en todos los sentidos. La eficiencia de una tabla Hash se vería comprometida si las colisiones estuvieran fuera de control. Además cuando por ejemplo añades o buscan un ítem, no basta con calcular su hash, para identificarlo unívocamente (y no ser confundido con otra coslisión), debe luego ser comparado byte a byte el valor entrado con el almacenado (si ya existe). Lueg no creas que simplemente 'viaja' un hash sin el resto de datos (cifrados convenientemente), en tales casos el hash hace más bien una doble labor de servir para la búsqueda y verificar que los datos son los que son (y no otros).

E - En ciertos algoritmos, tampoco las colisiones son deseables, solo restan eficiencia en cuanto al tiempo de operación, peor no hay afectacion alguna en cuanto a 'seguridad'. Por ejemplo el algoritmo KarpRabin, es un algortimo de búsqueda que utiliza hashes incrementales. Los hashes se crean, consumen y destruyen internamente basado en los datos recibidos para la búsqueda (por ejemplo una sección de una imagen o de un texto), luego no hay materia de seguridad que vaya a quedar comprometida.

Z - Por último, señalarte que tu afirmacion dubitativa de: "Creo que totalmente es posible descifrar un mensaje utilizando el mismo algoritmo ... lo aplico a algoritmos de reduccion como hashes (por ejemplo, MD5)", está en oposición directa a uno de los pilares básicos de la criptografía, que reza que la fuerza de un algoritmo criptográfico no debe recaer en el propio algoritmo (esa es la razón primera y principal por la que no hay necesidad de ocultar el funcionamiento del algoritmo), si no basado en las propias matemáticas.

...y con lo de "...lo aplico a algoritmos...", no me queda claro si esa 'aplicacion', se refiere a tu creencia (supongo que sí, porque de lo contrario el 'creo' sobraría), con lo que quiero decir es que no conviene usar la palabra aplicación (así en presente), cuando no pasa del terreno de las ideas, déajlo para cuando hagas algo tangible.

http://serbal.pntic.mec.es/~cmunoz11/nietdomingo.html
https://es.wikipedia.org/wiki/Colisi%C3%B3n_(hash)
Me pregunto quienes en la escuela se aprendieron el minimo comun multiplo, me pregunto tambien quienes entendieron el minimo comun multiplo.

Creo que el foro donde uno puede expresar su opinión básicamente es el 'foro libre', en el resto de secciones, la opinión importa poco y el peso recáe en el conocimiento, no en el creo, me parece, me dijeron, leí... Es decir si la intención es aprender, es mejor abstenerse de ciertos comentarios que no aportan nada.

[Usuario887]

1 entre 256 posibilidades

Bueno, supongo que no fui demasiado conciso pero intentare serlo ahora: no hablo de una busqueda exhaustiva. Hablo de una deduccion. En una deduccion ya no se habla de posibilidades/probabilidad, se habla de resultados.

Creo que ... no en el creo, ...

Para mostrar una personalidad tan ortodoxa, no deberias permitirte contradicciones...

Lo que pretendia con el post era encontrar alguien que pudiese desarrollar un algoritmo inverso del ejemplo que plantee, no encontrar discusiones con doctos. El unico argumento que tengo para darte es que los estandares tal vez duren toda la vida, pero no duraran todo el tiempo.

Saludos.

[Serapis]

No. no hay contradicción alguna.
Se puede decir:
A - "Me gusta el vino"
y
B - "No me gusta el vino".
Ambas frases son afirmaciones, pues afirman, definen mi gusto, la negacion hace referencia exclusiva al gusto por el vino. Si no fuera así, entonces frases como: "Me gusta mucho el vino", o "Me gusta a veces tomar un vaso de vino", tampoco terminarían de ser afirmativas, y como tampoco termina de ser negativas, estariamos en un limbo...

Si te interesa el tema de la filosofía (íntimamente en relacion a la informática y las matemáticas a través d ela lógica), se refleja el asunto en la Parádoja de Russell...