CBC-MAC AES自己的实现非常慢。

Question

对于一个项目，我需要用Android (用java)实现一个函数，它从一个文件中生成一个CBC (AES)。因此，基本上，该函数从文件中提取不同的“块”，并计算每个块的标识符，最后将其合并为整个文件的标识符。

但是，这个函数工作得很好，但是对于较大的文件，由于循环的实现，它非常慢(可能需要几分钟到几个小时)。然而，我对密码学的了解并不多，所以我不知道如何提高速度，甚至可能。输出所提供的CBC-MAC与其他不同编程语言中的库完全相同，因此工作正常。

不幸的是，我在使用外部库方面非常有限。尽管来自赏金城堡的类CBCBlockCipherMac是可能的，因为我能够将它包含在一些依赖项中，但从未得到它提供与下面提到的函数相同的输出。

所有的反馈都是受欢迎的，我已经试着解决它3天了，但无法解决它。谢谢!

*更新似乎是for循环中的函数str_to_a32 (每16字节循环一次)导致了最大的速度问题。因此，如果这个功能能够更快地发挥作用，它将主要解决这个问题。另外，不幸的是，每16字节循环一次是必要的，因为我正在实现云提供商Mega也实现的相同的CBC-MAC功能。

密码

        //TEST IMPLEMENTATION

    String _path_to_file = "";

    Random _random = new Random();
    long[] _key_file = new long[4];
    _key_file[0] = _random.nextInt(Integer.MAX_VALUE);
    _key_file[1] = _random.nextInt(Integer.MAX_VALUE);
    _key_file[2] = _random.nextInt(Integer.MAX_VALUE);
    _key_file[3] = _random.nextInt(Integer.MAX_VALUE);

    long[] _iv_file = new long[4];
    _iv_file[0] = _random.nextInt(Integer.MAX_VALUE);
    _iv_file[1] = _random.nextInt(Integer.MAX_VALUE);
    _iv_file[2] = 0;
    _iv_file[3] = 0;

    long[] _returned = cbc_mac(_path_to_file, _key_file, _iv_file);


//FUNCTIONS

//this function loops over the parts of the file to calculate the cbc-mac and is the problem
public static long[] cbc_mac(String _path, long[] k, long[] n) throws Exception {
    File _file = new File(_path);
    long _file_length = _file.length();
    RandomAccessFile _raf = new RandomAccessFile(_file, "r");

    //This works fine and fast
    ArrayList<chunksData> chunks = get_chunks(_file_length);

    long[] file_mac = new long[4];
    file_mac[0] = 0;
    file_mac[1] = 0;
    file_mac[2] = 0;
    file_mac[3] = 0;

    //prepare encrypt
    String iv = "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0";
    IvParameterSpec ivSpec = new IvParameterSpec(iv.getBytes());
    SecretKeySpec keySpec = new SecretKeySpec(a32_to_str(k).getBytes("ISO-8859-1"), "AES");
    Cipher cipher = Cipher.getInstance("AES/CBC/NOPADDING");
    cipher.init(Cipher.ENCRYPT_MODE, keySpec, ivSpec);
    //end prepare encrypt

    for(chunksData _chunksData : chunks) {

        int pos = (int)_chunksData._key;
        int size = (int)_chunksData._value;

        long[] chunk_mac = new long[4];
        chunk_mac[0] = n[0];
        chunk_mac[1] = n[1];
        chunk_mac[2] = n[0];
        chunk_mac[3] = n[1];

        byte[] bytes = new byte[16];

        //this loop is the really slow part since it loops over every 16 bytes
        for (int i = pos; i < pos + size; i += 16) {
            _raf.seek(i);
            int _did_read = _raf.read(bytes, 0, 16);
            if(_did_read != 16) {
                for(int o = _did_read;o<16;o++) {
                    bytes[o] = (byte)((char)'\0');
                }
            }

            long[] block = str_to_a32(new String(bytes, "ISO-8859-1"));

            chunk_mac[0] = chunk_mac[0] ^ block[0];
            chunk_mac[1] = chunk_mac[1] ^ block[1];
            chunk_mac[2] = chunk_mac[2] ^ block[2];
            chunk_mac[3] = chunk_mac[3] ^ block[3];

            chunk_mac = str_to_a32(new String(cipher.doFinal(a32_to_str(chunk_mac).getBytes("ISO-8859-1")), "ISO-8859-1"));

        }

        file_mac[0] = file_mac[0] ^ chunk_mac[0];
        file_mac[1] = file_mac[1] ^ chunk_mac[1];
        file_mac[2] = file_mac[2] ^ chunk_mac[2];
        file_mac[3] = file_mac[3] ^ chunk_mac[3];
        file_mac = str_to_a32(new String(cipher.doFinal(a32_to_str(file_mac).getBytes("ISO-8859-1")), "ISO-8859-1"));

    }

    _raf.close();

    return file_mac;

}

//this function works fine and fast
public static ArrayList<chunksData> get_chunks(long size) {

    ArrayList<chunksData> chunks = new ArrayList<chunksData>();

    long p = 0;
    long pp = 0;

    for (int i = 1; i <= 8 && p < size - i * 0x20000; i++) {
        chunksData chunks_temp = new chunksData(p, i*0x20000);
        chunks.add(chunks_temp);
        pp = p;
        p += chunks_temp._value;
    }

    while(p < size) {
        chunksData chunks_temp = new chunksData(p, 0x100000);
        chunks.add(chunks_temp);
        pp = p;
        p += chunks_temp._value;            
    }

    chunks.get(chunks.size()-1)._value = size-pp;
    if((int)chunks.get(chunks.size()-1)._value == 0) {
        chunks.remove(chunks.size()-1);
    }

    return chunks;

}

public static class chunksData {
    public long _key = 0;
    public long _value = 0;
    public chunksData(long _keyT, long _valueT){
        this._key = _keyT;
        this._value = _valueT;
    }
}

//helper function which also contains a loop and is used in the problematic loop, so might be a problem though I don't know how to speed it up
public static long[] str_to_a32(String string) {
    if (string.length() % 4 != 0) {
        string += new String(new char[4 - string.length() % 4]);
    }
    long[] data = new long[string.length() / 4];

    byte[] part = new byte[8];
    for (int k = 0, i = 0; i < string.length(); i += 4, k++) {
        String sequence = string.substring(i, i + 4);
        ByteArrayOutputStream baos = new ByteArrayOutputStream();
        try {
            baos.write(sequence.getBytes("ISO-8859-1"));
            System.arraycopy(baos.toByteArray(), 0, part, 4, 4);
            ByteBuffer bb = ByteBuffer.wrap(part);
            data[k] = bb.getLong();
        } catch (IOException e) {
            data[k] = 0;
        }
    }
    return data;
}

//helper function which also contains a loop and is used in the problematic loop, so might be a problem though I don't know how to speed it up
public static String a32_to_str(long[] data) {
    byte[] part = null;
    StringBuilder builder = new StringBuilder();
    ByteBuffer bb = ByteBuffer.allocate(8);
    for (int i = 0; i < data.length; i++) {
        bb.putLong(data[i]);
        part = copyOfRange(bb.array(), 4, 8);
        bb.clear();
        ByteArrayInputStream bais = new ByteArrayInputStream(part);
        while (bais.available() > 0) {
            builder.append((char) bais.read());
        }
    }
    return builder.toString();
}

Answer 1

我的主要怀疑是第一个循环中的搜索操作，并且只处理16个字节。我不知道算法，但您的代码表明，读取完整的“块”是可能的，然后您可以处理它的部分是否是必要的。

此外，块似乎是顺序的(除非我错过了什么)，所以整个阅读可以顺序完成而不需要寻找。

您不需要助手方法中的ByteArrayOutput流。此外，生成子字符串也会产生影响，因此对整个字符串调用toBytes，然后提取字节数组的各个部分将更有效。

下面的代码大约比原始代码快两倍。

public long[] fast_str_to_a32(String string) throws UnsupportedEncodingException {
    if (string.length() % 4 != 0) {
        string += new String(new char[4 - string.length() % 4]);
    }
    long[] data = new long[string.length() / 4];

    byte[] bytes = string.getBytes("ISO-8859-1");

    byte[] part = new byte[8];
    ByteBuffer bb = ByteBuffer.wrap(part); 
    for (int k = 0, i = 0; i < bytes.length; i += 4, k++) {
        System.arraycopy(bytes, i, part, 4, 4);
        bb.rewind();
        data[k] = bb.getLong();
    }
    return data;
}

另外，在主方法中，您将字节转换为字符串，只为了在byte[]开始时将它们转换回str_to_a32，您应该只使用byte[]作为该方法的输入。

我仍然认为，您应该一次读取整个块，然后以16字节的块进行处理。

代码中有一个潜在的问题:尝试读取16个字节，但如果得到的较少，则开始填充。然而，read的契约是“尝试读取尽可能多的len字节，但可能读取的数目较少。”通常，较小的数目发生在文件的末尾，但它的原则是，它可以在任何时候发生。如果是这样的话，你将开始填充在中间的流和混乱你的部分完全。