メモ / 2010-02-04

■ Pentium III 800 MHz はちょっと遅い: [D言語]

ブルートフォースで暗号化されている zip の
キーを捜すコードを書いた。

オプションなしでコンパイルしたものを、
Pentium III 800 MHz で実行してみた。

40万キー／秒 の処理速度だった。
2^32 個の範囲だと 3時間かかる。
2^96 個の範囲だと 6.31318894 × 10^15 年

import std.stdio;
import std.perf;
import std.random;
import std.zlib;

uint key0,key1,key2;

uint[] makeCRCTable()
{
    uint[] table;
    uint r;

    for (int i = 0; i < 256; i++)
    {
        r = i;
        for (int j = 0; j < 8; j++)
        {
            if (r & 1)
            {
                r = (r >> 1) ^ 0xEDB88320U;
            }else{
                r >>= 1;
            }
        }
        table ~= r;
    }
    return table;
}

invariant uint[] crctable = makeCRCTable();

uint crc32(uint crc, ubyte b)
{
    return ((crc >> 8) ^ crctable[(crc & 0xFF) ^ b]);
}

void initializeKeys(in ubyte[] password)
{
    key0 = 305419896;
    key1 = 591751049;
    key2 = 878082192;
    foreach(c;password) updateKeys(c);
}

void updateKeys(in ubyte c)
{
    key0 = crc32(key0,c);
    key1 += key0 & 0xff;
    key1  = key1 * 134775813 + 1;
    key2 = crc32(key2,key1 >> 24);
}

ubyte decryptByte()
{
    uint temp =  key2 | 2;
    return (((temp * (temp ^ 1)) >> 8) & 0xFF);
}

ubyte[] encrypt(in ubyte[] password, in ubyte[] planetext, in uint crc)
{
    initializeKeys(password);

    Random gen;
    ubyte[12] header;

    foreach(ref c;header[0 .. 10])
    {
        gen.seed(unpredictableSeed);
        c = cast(ubyte)gen.front;
    }
    header[11] = crc >> 24 & 0xff;

    ubyte[] ciphertext;

    foreach(c;header ~ planetext)
    {
        ubyte temp = decryptByte();
        updateKeys(c);
        ciphertext ~= c ^ temp;
    }

    return ciphertext;
}

bool check(in ubyte[] ciphertext, in uint crc)
    in
    {
        assert(ciphertext.length > 12);
    }
    body
    {
        ubyte[12] header = ciphertext[0 .. 12];

        for(int i = 0;i<12;i++)
        {
            ubyte temp = header[i] ^ decryptByte();
            updateKeys(temp);
            header[i] = temp;
        }
        if(header[11] != (crc >> 24)) return false;

        ubyte[] planetext;
        foreach(c;ciphertext[12 .. $])
        {
            ubyte temp = c ^ decryptByte();
            updateKeys(temp);
            planetext ~= temp;
        }
        if(std.zlib.crc32(0,planetext) != crc) return false;

        return true;
    }

void main()
{
    ubyte[] planetext = cast(ubyte[])("Hello world!!");
    uint crc = std.zlib.crc32(0,planetext);
    ubyte[] password  = cast(ubyte[])("password");
    ubyte[] ciphertext = encrypt(password,planetext,crc);

    //initializeKeys(password); 0x5ff8707d 0xba789085 0xea9b4e4d
    //writefln("key2 = %08x  key1 = %08x  key0 = %08x", key2, key1, key0);

    alias PerformanceCounter.interval_t interval_t;
    auto timer = new PerformanceCounter;
    timer.start();

    for(ulong i = 0xE92442F3; i < 0x100000000U; i++) // 2400万件 ぐらい
    {
        key2 = 0x5ff8707d;
        key1 = 0xba789085;
        key0 = cast(uint)i;
        if(check(ciphertext,crc)) break;
    }

    timer.stop();
    interval_t elapsedMsec = timer.milliseconds;
    writefln("Time elapsed: %s msec", elapsedMsec);
}

-O -inline つけてコンパイルしたら処理時間が半分になった。
半分になっても終わりそうも無い。

Opteron 246 x2 で192万キー／秒か
2^32 個の範囲だと 37分

[ 固定リンク ]  [ トラックバック(955) ]