Diseñe un algoritmo simple que crea un archivo que contiene nada más que su propia suma de comprobación.¿Cómo encontrar una suma de comprobación de la misma suma de comprobación? (pregunta de entrevista de trabajo)
Digamos que es CRC-32, por lo que este archivo debe tener 4 bytes de longitud.
Puede haber alguna manera matemática inteligente de averiguarlo (o probar que no existe), si usted sabe cómo funciona el algoritmo.
Pero como soy perezoso y CRC32 solo tiene 2^32 valores, lo forzaría brutalmente. Mientras esperaba que el algoritmo revisara todos los valores de 2^32, usaría Google y Stack Overflow para ver si alguien tenía una solución.
En el caso de los algoritmos SHA-1, MD5 y otros algoritmos más o menos seguros criptográficamente, me dejaría intimidar por los matemáticos que diseñaron esos algoritmos y simplemente se dan por vencidos.
EDITAR 1: Brute forcing ... Hasta aquí he encontrado uno; CC4FBB6A en la codificación big-endian. Aún puede haber más. Estoy comprobando 4 codificaciones diferentes: mayúsculas y minúsculas ASCII y binary big-endian y little-endian.
EDITAR 2: Brute force done. Aquí están los resultados:
CC4FBB6A (big-endian)
FFFFFFFF (big endian & little-endian)
32F3B737 (ASCII en mayúsculas)
el código es here. En mi C2Q6600 overclockeado que tarda aproximadamente 1,5 horas en ejecutarse. Ahora que el programa es de un solo subproceso, sería fácil hacerlo de subprocesos múltiples, lo que daría una buena escalabilidad lineal.
Entonces eres inteligente, ¿eh? Pensé que tu cabeza sería más grande. :) – psihodelia
+1 CC4FBB6A :-) –
bueno, parece que nadie ha presentado ninguna respuesta adecuada (ofreciendo algo mejor que una fuerza bruta), pero te daré mi voz porque tienes el mayor número de votos positivos; de todos modos, ¡gracias por tus esfuerzos! – psihodelia
Al carecer de orientación específica en contrario, definiría la suma de comprobación de datos inexistentes como una suma de comprobación inexistente, por lo que la creación de un archivo vacío cumpliría el requisito.
Otro método típico es una suma de comprobación negativa, es decir, después de los datos se escribe un valor que hace que la suma de comprobación de todo el archivo (incluida la suma de comprobación) salga a cero. En este caso, escribe una suma de comprobación de 0, y todo funciona.
He especificado CRC-32 – psihodelia
La suma de comprobación exacta que usa es (en su mayoría) irrelevante, se trata principalmente de cómo la aplica. –
Aparte de Jerry ataúd y las buenas respuestas de Esko Luontola a un problema poco común, me gustaría añadir:
Matemáticamente, estamos buscando a X tal que f (x) = X, donde F es la función de suma de comprobación, y X es la información en sí misma. Como la salida de la suma de verificación es de tamaño fijo, y la entrada que estamos buscando tiene el mismo tamaño, ¡no existe garantía de que tal X exista! Podría ser que cada valor de entrada del tamaño fijo esté correlacionado con un valor diferente de ese tamaño.
EDIT: Su pregunta no especificó la forma exacta en que se supone que la suma de comprobación debe formatearse dentro del archivo, por lo que asumí que quiere decir la representación en bytes de la suma de comprobación. Cuando las cadenas y las codificaciones y las cadenas formateadas entran en juego, las cosas se vuelven más complejas.
De hecho, para una buena algoritmo de suma de comprobación no querría asegurarse de que X! = F (X) para detener un montón de colisión alcance –
No, si asumió que en realidad es más vulnerable. Esta fue, con mucho, la mayor debilidad en el famoso Enigma. Al menos puedo decir que es algo malo si puedes probar esa propiedad. –
@ralu: supongamos que tomo la función MD5 y defino una nueva función hash que consiste en la suma MD5 de su entrada, precedida por el bit 0 si el primer bit de entrada es 1 y 1 si es 0. Esta nueva es probable que la función hash no tenga un punto fijo, y probablemente sea "casi" tan fuerte como MD5 (si conocer el primer bit de un mensaje te permite descifrar MD5 en el tiempo X, puedes descifrarlo sin el primer bit en el tiempo 2X). Entonces, no creo que la no existencia de un punto fijo sea un problema. Enigma tenía una propiedad bastante más fuerte que no tener un punto fijo: nunca cifró ni un solo carácter para sí mismo. –
Brute force it. CRC-32 te da una cadena de longitud 8 que contiene dígitos y letras de A a F (en otras palabras, es un número hexadecimal). Pruebe cada combinación, dándole 16 = muchas posibilidades.Luego revise cada posibilidad y vea si le da la cadena original.
Puede intentar optimizarlo suponiendo que la solución usará cada carácter no más de dos o tres veces, esto podría hacer que termine más rápido.
Si tiene acceso a una implementación CRC32, también puede intentar romper el algoritmo y encontrar una solución mucho más rápido, pero no tengo idea de cómo lo haría.
"CRC-32 le da una cadena de longitud 8 que contiene dígitos y letras de A-F" - no, CRC32 devuelve un entero de 32 bits. Muchos programas simplemente lo representan en hexadecimal. –
puede probar cksum somefile.bin en su terminal, imprimirá una cadena, que representa un entero decimal de tipo entero32 – psihodelia
Fuerza bruta. Esto es Adler32, que no he implementado antes, y no me molesté en las pruebas, así que es bastante probable que lo haya estropeado. Sin embargo, no esperaría que una versión corregida corriera significativamente más lenta, a menos que haya hecho algo colosalmente errado.
Esto supone que el valor de 32 bits suma de comprobación se escribe en el archivo ascendente hacia la izquierda (no he encontrado un punto fijo con ella big endian):
#include <iostream>
#include <stdint.h>
#include <iomanip>
const int modulus = 65521;
void checkAllAdlers(uint32_t sofar, int depth, uint32_t a, uint32_t b) {
if (depth == 4) {
if ((b << 16) + a == sofar) {
std::cout << "Got a fixed point: 0x" <<
std::hex << std::setw(8) << std::setfill('0') <<
sofar << "\n";
}
return;
}
for (uint32_t i = 0; i < 256; ++i) {
uint32_t newa = a + i;
if (newa >= modulus) newa -= modulus;
uint32_t newb = b + a;
if (newb >= modulus) newb -= modulus;
checkAllAdlers(sofar + (i << (depth*8)), depth + 1, newa, newb);
}
return;
}
int main() {
checkAllAdlers(0, 0, 1, 0);
}
Salida:
$ g++ adler32fp.cpp -o adler32fp -O3 && time ./adler32fp
Got a fixed point: 0x03fb01fe
real 0m31.215s
user 0m30.326s
sys 0m0.015s
[Editar: varios errores solucionados, no tengo ninguna confianza en la exactitud de este código ;-) De todos modos, tienes la idea: una suma de control de 32 bits que utiliza cada byte de entrada solo una vez es muy barato para la fuerza bruta. Los checksums generalmente están diseñados para ser rápidos de computar, mientras que los hashes son usualmente mucho más lentos, a pesar de que tienen efectos superficialmente similares. Si su suma de comprobación fue "2 rondas de Adler32" (lo que significa que la suma de comprobación objetivo fue el resultado de calcular la suma de comprobación y luego calcular la suma de comprobación de esa suma de comprobación) entonces mi enfoque recursivo no ayudaría tanto, habría proporcionalmente menos en común entre las entradas con un prefijo común. MD5 tiene 4 rondas, SHA-512 tiene 80.]
Hay muchas formas de calcular las sumas de comprobación, y ciertamente no existe un algoritmo universal para hacer que este tipo de archivo sea independiente del algoritmo de cálculo de la suma de comprobación (además de ridículamente bruto) forzar prueba y error). ¿Se ha especificado el algoritmo CS? –
¿Cómo se debe calcular la suma de comprobación? SHA1, MD5, o cualquier cosa que elija, porque si puedo seleccionar el algoritmo de suma de comprobación, esto es bastante trivial. –
básicamente está buscando una función de punto fijo, donde f (x) = x. –