PKZIP密钥推导优化思路的C代码实现问题排查

API 探路者

2026-4-14

我正在尝试优化针对PKZIP的攻击方式，减少计算量和资源需求。PKZIP使用以下逻辑更新其密钥流或内部状态：

key0[i] = key0[i-1]>>8 ^ crctab[key0[i-1]&0xFF ^ plaintext[i]];
key1[i] = (key1[i-1] + (key0[i]&0xFF))* Const + 1;
key2[i] = key2[i-1]>>8 ^ crctab[key2[i-1]&0xFF ^ (key1[i]>>24)];

而生成字节密钥key3并将明文加密为密文的逻辑如下：

tmp = (key2[i] |3)&0xFFFF; // 注意：将key2的最后16位设为奇数
key3[i] = ((tmp*(tmp ^ 1))>>8)&0xFF;// 注意：等价于 ((x²)-x)//256 mod 256 或 (x*(x±1))//256 mod 256
ciphertext[i] = plaintext[i] ^ key3[i];

像pkcrack这类工具会利用key3[i]和key3[i-1]推导位置i处的2**22种可能的key2值，这个计算量实在太大。于是我发现了一个优化方向：

如果我们有连续3组明文和密文，就能推导出3个连续的key3值。每个key3值对应256种可能的key2低16位值，但只要找到key3[i]和key3[i-1]对应的16位值之间的关联，就能大幅压缩候选数量。

基于这个思路，我写了一段Python代码验证理论：

import math
n= int(65536)

x = 0xc90b # 这是 key2[i-1] |3
y = 0x2f17# 这是 key2[i] | 3

a = ((x*x) - x) % n # 为了简化，暂时不除以256
b = ((y*y) - y) % n # 因此a ^ b的结果是16位，等价于 (e<<8)
e = (a ^ b)&0xFF00

# 核心等式
'''
sqrt( ((x² -x) %n) ^ (256*e) ) == sqrt( ((y² -y) %n) )
也就是说，已知key3[i]和key3[i-1]就能算出e，而且每个位置的key2低16位奇数候选只有64个，
通过等式可以直接找到对应的y值
'''

i = round(math.sqrt((((x*x) - x) %n ^ e)))
j = round(math.sqrt(((y*y) - y) %n))

print(hex(a))
print(hex(b))
print(hex(e))
print(hex(i))
print(hex(j))

这段Python代码完美验证了我的理论，但当我把它转化为C代码并尝试实际应用时，遇到了问题：当我用生成的key2候选值去匹配算法生成的真实值时，总是找不到正确结果。我不确定是代码实现有误，还是对算法的理解出了偏差。

首先是我用来生成测试密文的C代码：

#include <time.h>
#include <stdlib.h>
#include <assert.h>
#include <ctype.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>


#define CRCPOLY 0xedb88320
#define CONSTx      0x08088405U /* 134775813 */
#define MSB(x)          (((x)>>24)&0xFF)
#define MSBMASK         0xFF000000U
#define CRC32(x,c)  (((x)>>8)^crctab[((x)^(c))&0xff])
 
uint32_t    crctab[256];

const uint8_t plain[8]= {
    0x64, 0x14, 0x9A, 0xC7, 0xB2, 0x96, 0xC0, 0x15  
};
uint8_t cipher[8]= {
    
};

uint8_t key3[8]= {
    
};

uint32_t k0 = 0x12345678,t0;
uint32_t k1 = 0x23456789,t1;
uint32_t k2 = 0x34567890,t2;

  static void mkCrcTab( ){
    unsigned int i, j, c;
    for( i = 0; i < 256; i++ )
    {
        c = i;
        for( j = 0; j < 8; j++ )
            if( c&1 )
            c = (c>>1) ^ CRCPOLY;
            else
            c = (c>>1);
        crctab[i] = c;
    }
}


int main(){
    
    mkCrcTab( );
    
    uint8_t pw[10] = {
        0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x00
    };
    
    uint32_t ky0 = k0;  // FNV offset basis for 32-bit
    uint32_t ky1 = k1; // FNV prime for 32-bit
    uint32_t ky2 = k2;
    uint16_t tmp;
    uint8_t bt;

    for (int i = 0; i < 10; i++) {
        ky0 = CRC32( ky0, pw[i] );
        ky1 = (k1 + (ky0&0xff))*CONSTx + 1;
        ky2 = CRC32( ky2, MSB(ky1) );
        printf("%08X %08X %08X\n",ky0,ky1,ky2);
    }
    t0 =ky0;
    t1 = ky1;
    t2 = ky2;
    printf("===================================\n");
    for (int i = 0; i < 8; i++) {
        ky0 = CRC32( ky0, plain[i] );
        ky1 = (k1 + (ky0&0xff))*CONSTx + 1;
        ky2 = CRC32( ky2, MSB(ky1) );
        printf("%08X %08X %08X\n",ky0,ky1,ky2);
        tmp = ky2 | 3;
        bt = ((tmp*(tmp ^ 1))>>8)&0xFF;
        cipher[i] = plain[i] ^ bt;
        key3[i] = bt;
    }
    printf("===================================\n");
    printf("plain : ");
    for(int i =0; i <8; i++){
        printf("%02X ",plain[i]);
    }
    printf("\n");
    printf("cipher : ");
    for(int i =0; i <8; i++){
        printf("%02X ",cipher[i]);
    }
    printf("\n");
    printf("key3 : ");
    for(int i =0; i <8; i++){
        printf("%02X ",key3[i]);
    }
    printf("\n");
    printf("===================================\n");
    return 0;
}

我用密码1234567890加密了8字节明文，得到对应的密文。接着编写了以下代码来生成候选key2值：

#include <time.h>
#include <stdlib.h>
#include <assert.h>
#include <ctype.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>

#define CRCPOLY 0xedb88320
#define CONSTx      0x08088405U /* 134775813 */
#define KEY2SPACE   (1<<12)
#define KEY3(i) (plain[(i)]^cipher[(i)])
#define MSB(x)          (((x)>>24)&0xFF)
#define MAXDELTA        (0x00FFFFFFU+0xFFU)
#define MSBMASK         0xFF000000U
#define CRC32(x,c)  (((x)>>8)^crctab[((x)^(c))&0xff])


uint32_t    crctab[256],crcbymsb[256],crcbylsb[256];
uint32_t    *key2i;
uint16_t    tmptaba[256],tmptabb[256],tmptabc[256],lkpc[65536],lkpa[65536];
uint8_t     idxbylsb[256], idxbymsb[256];
int      numKey2s = 0;

const uint8_t plain[8]= {
    0x64, 0x14, 0x9A, 0xC7, 0xB2, 0x96, 0xC0, 0x15
};
const uint8_t cipher[8]= {
    0xEF, 0x20, 0xDC, 0x4C, 0x11, 0x9A, 0x78, 0xEB
    
};

static void mkCrcTab( ){
    unsigned int i, j, c;
    for( i = 0; i < 256; i++ )
    {
        c = i;
        for( j = 0; j < 8; j++ )
            if( c&1 )
            c = (c>>1) ^ CRCPOLY;
            else
            c = (c>>1);
        crctab[i] = c;
        crcbymsb[c>>24] = c;
        crcbylsb[c&0xFF] = c;
        idxbymsb[c>>24] = i;
        idxbylsb[c&0xFF] = i;
    }
}

void generate( int n ){
    int i,j, d;
    uint8_t e, ea;
    uint32_t    cr[4],cr1[4];
    uint16_t    ls16a,ls16b,ls16c,eq,eq1;   
    printf("Generating possible key2_%d values...", n );
    ea = KEY3(n-1) ^ KEY3(n);
    e = KEY3(n-2) ^ KEY3(n-1);
    for( i = 3; i < 256; i+=4 ){
        ls16b = tmptabb[i];
        eq =  (int) sqrt( (double) ((256*ea) ^ (ls16b*(ls16b ^ 1))&0xFFFF));
        ls16c = lkpc[eq];
        cr[0] = crcbylsb[(ls16b>>8) ^ (ls16c&0xFF)];
        cr[1] = crcbylsb[(ls16b>>8) ^ ((ls16c-1)&0xFF)];
        cr[2] = crcbylsb[(ls16b>>8) ^ ((ls16c-2)&0xFF)];
        cr[3] = crcbylsb[(ls16b>>8) ^ ((ls16c-3)&0xFF)];
        eq1 = (int) sqrt( (double) ((256*e) ^ (ls16b*(ls16b ^ 1))&0xFFFF));
        ls16a = lkpa[eq1];
        cr1[0] = crcbylsb[(ls16a>>8) ^ (ls16b&0xFF)];
        cr1[1] = crcbylsb[(ls16a>>8) ^ ((ls16b-1)&0xFF)];
        cr1[2] = crcbylsb[(ls16a>>8) ^ ((ls16b-2)&0xFF)];
        cr1[3] = crcbylsb[(ls16a>>8) ^ ((ls16b-3)&0xFF)];
        for(j=0; j <4; j++){
            for(d=0; d < 4; d++){
                key2i[numKey2s++] = (((cr1[j]>>8) ^ cr[d])&0xFFFF0000) | (ls16c-d);
            }
        }
        
    }

    printf("done.\nFound %d possible key2-values.\n", numKey2s );
}

int main(){
    uint16_t kt,bk,idx;
    uint8_t dt;
    int x=0, y=0, z=0;
    
    key2i = malloc(KEY2SPACE * sizeof(uint32_t));
    if (!key2i) {
        perror("Memory allocation failed");
        exit(EXIT_FAILURE);
    }
    //load tmptabb
    for(uint16_t i=0; i < 0xFFFF; i++){
        kt = i | 3;
        dt = ((kt*(kt ^ 1))>>8)&0xFF;
        if(dt == KEY3(2)){
            tmptabb[y++] = i;
        }
        if(dt == KEY3(3)){
            tmptabc[z++] = i;
        }
        if(dt == KEY3(1)){
            tmptaba[x++] = i;
        }
    }
    //load lookup tables
    for(int k =3; k < 256; k+=4){
        bk = tmptaba[k];
        idx = (int) sqrt( (bk*(bk ^ 1))&0xFFFF);
        lkpa[idx] = bk;
        bk = tmptabc[k];
        idx = (int) sqrt( (bk*(bk ^ 1))&0xFFFF);
        lkpc[idx] = bk;
    }
    mkCrcTab();
    generate(3);
    for(int w =0; w < numKey2s; w++){
        printf("%08X\n", key2i[w]);
    }
}

我找不到问题出在哪里，这导致我无法继续研究key2和key0之间的数学关联。希望能得到帮助排查问题。

备注：内容来源于stack exchange，提问作者Alexio puk2sefu