解密经rand()加密的TeX文件：暴力破解种子实现咨询

Alright, let's tackle this problem head-on. You need to brute-force every possible seed for the ISO/IEC 9899:1990 C standard's rand() function to decrypt a TeX file, stopping as soon as the decrypted output matches the known starting characters of the original file. Here's a step-by-step guide to make this work:

1. Replicate the Exact rand() Implementation #

First, you must mirror the original C90 rand() and srand() functions perfectly—any deviation will generate incorrect random sequences, making your brute-force useless. The full standard implementation is:

// Exact ISO/IEC 9899:1990 rand() and srand()
static unsigned long int next = 1;

void srand(unsigned int seed) {
    next = seed;
}

int rand(void) {
    next = next * 1103515245 + 12345;
    return (unsigned int)(next / 65536) % 32768;
}

This uses a linear congruential generator (LCG) with the standard constants specified in the C90 standard.

2. Define the Decryption Logic #

Assuming the encryption was done by XORing each byte of the TeX file with the 8-bit value of rand() output (i.e., rand() % 256—the most common simple encryption method for this scenario), the decryption will reverse this: for each encrypted byte, XOR it with the corresponding rand() byte from the sequence generated by a given seed.

If your encryption uses a different method (like addition modulo 256), adjust the decryption step accordingly, but XOR is the safe default assumption here.

3. Brute-Force Seed Check #

The core idea is to iterate over every possible unsigned integer seed (0 to UINT_MAX, which is 4294967295 for 32-bit systems), initialize the RNG with each seed, generate the required number of random bytes, decrypt the start of the encrypted file, and check if it matches your known original header.

Here's a complete C program example that does this:

#include <stdio.h>
#include <stdint.h>
#include <string.h>

// Exact C90 rand()/srand() implementation
static unsigned long int next = 1;

void srand(unsigned int seed) {
    next = seed;
}

int rand(void) {
    next = next * 1103515245 + 12345;
    return (unsigned int)(next / 65536) % 32768;
}

int main(int argc, char *argv[]) {
    if (argc != 4) {
        fprintf(stderr, "Usage: %s <encrypted_tex_file> <known_header> <header_length>\n", argv[0]);
        return 1;
    }

    const char *encrypted_file = argv[1];
    const char *known_header = argv[2];
    const size_t header_len = atoi(argv[3]);

    // Read the start of the encrypted file
    FILE *f = fopen(encrypted_file, "rb");
    if (!f) {
        perror("Failed to open encrypted file");
        return 1;
    }
    uint8_t encrypted_header[256];
    size_t bytes_read = fread(encrypted_header, 1, header_len, f);
    fclose(f);
    if (bytes_read != header_len) {
        fprintf(stderr, "Failed to read enough bytes from encrypted file\n");
        return 1;
    }

    // Brute-force every possible seed
    for (uint32_t seed = 0;; seed++) {
        srand(seed);
        uint8_t decrypted[256];
        int match = 1;

        for (size_t i = 0; i < header_len; i++) {
            uint8_t rand_byte = rand() % 256;
            decrypted[i] = encrypted_header[i] ^ rand_byte;
            if (decrypted[i] != known_header[i]) {
                match = 0;
                break;
            }
        }

        if (match) {
            printf("Found matching seed: %u\n", seed);
            // Optional: Verify full decryption here
            return 0;
        }

        // Wrap around at UINT_MAX to avoid infinite loop (though 32-bit seeds will take time)
        if (seed == UINT32_MAX) {
            fprintf(stderr, "No matching seed found\n");
            return 1;
        }
    }
}

4. Key Notes for Success #

• Header Length: Use the longest possible known header (e.g., 10+ characters) to avoid false positives—shorter headers might match multiple seeds by chance.
• Performance: Brute-forcing 4 billion seeds can take time. To speed this up:
  • Use multi-threading to split the seed range across multiple cores.
  • If you suspect the seed was derived from a timestamp (e.g., srand(time(NULL))), narrow the range to plausible timestamps (e.g., the year the file was created).
• Encryption Verification: If you're unsure about the encryption method, test a small sample: encrypt a known string with a test seed, then see if your decryption logic recovers it.

内容的提问来源于stack exchange，提问作者Mitch