algorithm - tres - ¿Cómo encontrar una suma de comprobación de la misma suma de comprobación?(pregunta de entrevista de trabajo)

cómo se realiza la prueba de una suma

Question

Diseñe un algoritmo simple que cree un archivo que no contenga nada más que su propia suma de comprobación.

Digamos que es CRC-32, por lo que este archivo debe tener 4 bytes de longitud.

Answer 1

Aparte de las buenas respuestas de Jerry Coffin y Esko Luontola a un problema inusual, me gustaría agregar:

Matemáticamente, buscamos 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. Dado que la salida de la suma de comprobación es de tamaño fijo, y la entrada que buscamos es del mismo tamaño, ¡ no hay garantía de que exista una X de este tipo! Podría muy bien 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 se formateó la suma de comprobación dentro del archivo, por lo que asumí que se refiere a la representación en bytes de la suma de comprobación. Cuando las cadenas y las codificaciones y las cadenas con formato vienen a jugar, las cosas se vuelven más complejas.

Answer 2

Bruta lo fuerza. CRC-32 le proporciona una cadena de longitud 8 que contiene dígitos y letras de AF (en otras palabras, es un número hexadecimal). Prueba cada combinación, dándote 16 ⁸ = muchas posibilidades. Luego hash cada posibilidad y ve si te da la cadena original.

Puede intentar optimizarlo asumiendo que la solución utilizará 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 de 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 haría esto.

Answer 3

Fuerza bruta. Este es Adler32, que no he implementado antes y no me molestó en realizar pruebas, por lo que es muy probable que lo haya estropeado. Sin embargo, no esperaría que una versión corregida se ejecute significativamente más lento, a menos que haya hecho algo colosalmente incorrecto.

Esto supone que el valor de suma de comprobación de 32 bits se escribe en el archivo little-endian (no encontré un punto fijo con el 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

[Edición: ya se han solucionado varios errores, no tengo ninguna confianza en la exactitud de este código ;-) De todos modos, se entiende la idea: una suma de comprobación de 32 bits que utiliza cada byte de entrada solo una vez es muy barata para la fuerza bruta. Las sumas de control generalmente están diseñadas para ser rápidas de calcular, mientras que los hash son generalmente mucho más lentos, aunque tengan efectos similares en la superficie. Si su suma de control fuera "2 rondas de Adler32" (lo que significa que la suma de control objetivo fue el resultado de calcular la suma de control y luego calcular la suma de comprobación de esa suma de control), 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.]

Answer 4

Puede haber alguna forma matemática inteligente de averiguarlo (o probar que no existe), si sabe cómo funciona el algoritmo.

Pero como soy perezoso y CRC32 solo tiene valores de 2 ^ 32, lo forzaría brutalmente. Mientras esperaba que el algoritmo pasara por todos los valores de 2 ^ 32, usaría Google y para encontrar si alguien tiene una solución para ello.

En el caso de SHA-1, MD5 y otros algoritmos criptográficamente más o menos seguros, me intimidarían los matemáticos que diseñaron esos algoritmos y simplemente se dieron por vencidos.

EDIT 1: Bruto forzando ... Hasta aquí he encontrado uno; CC4FBB6A en codificación big-endian. Todavía podría haber más. Estoy comprobando 4 codificaciones diferentes: ASCII mayúscula y minúscula, y big-endian y little-endian binarios.

EDIT 2: fuerza bruta hecha. Aquí están los resultados:

CC4FBB6A (big-endian)
FFFFFFFF (big-endian y little-endian)
32F3B737 (ASCII en mayúsculas)

El código está here . En mi C2Q6600 overclockeado que tarda aproximadamente 1,5 horas en ejecutarse. Ahora ese programa es de un solo hilo, pero sería fácil hacerlo de múltiples hilos, lo que daría una buena escalabilidad lineal.

Answer 5

Sin una orientación específica al contrario, definiría la suma de comprobación de los 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 que los datos escriben 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.