CBC-MAC AES 自己的实现非常慢
CBC-MAC AES own implementation extremely slow
对于一个项目，我需要在 Android（使用 java）中实现一个函数，该函数从文件生成 CBC-MAC (AES)。所以基本上这个函数从文件中获取不同的 'blocks' 并计算每个块的标识符，最后将它组合成整个文件的标识符。
该函数运行良好，但是，由于实现了循环，因此对于较大的文件它非常慢（可能需要几分钟到几小时）。但是，我对密码学的了解并不多，所以我不确定如何提高速度，或者是否有可能。输出给出了与不同编程语言的其他库完全相同的 CBC-MAC，所以它工作正常。
不幸的是，我在使用外部库方面非常有限..虽然来自 bouncycastle 的 class 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 = "[=11=][=11=][=11=][=11=][=11=][=11=][=11=][=11=][=11=][=11=][=11=][=11=][=11=][=11=][=11=][=11=]";
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)'[=11=]');
}
}
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();
}
我主要怀疑第一个循环中的查找操作只处理了 16 个字节。我不知道该算法，但您的代码表明可以阅读完整的 "chunk" 然后您可以处理它是否有必要部分。
此外，块似乎是连续的（除非我遗漏了什么）所以整个阅读可以在没有搜索的情况下按顺序完成。
您的辅助方法中不需要 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;
}
同样在 main 方法中，您将字节转换为字符串只是为了在 str_to_a32 的开头将它们转换回 byte[]，您应该只使用 byte[] 作为此方法的输入。
我仍然认为您应该一次读取整个块，然后以 16 字节为单位进行处理。
您的代码中可能存在问题：您尝试读取 16 个字节，但如果读取的字节数较少，则开始填充。但是，读取合同是 "An attempt is made to read as many as len bytes, but a smaller number may be read." 通常，较小的数字出现在文件末尾，但原则上它可能随时发生。如果是这样，您将开始在流的中间填充并完全弄乱您的部分。
对于一个项目，我需要在 Android（使用 java）中实现一个函数，该函数从文件生成 CBC-MAC (AES)。所以基本上这个函数从文件中获取不同的 'blocks' 并计算每个块的标识符，最后将它组合成整个文件的标识符。
该函数运行良好，但是，由于实现了循环，因此对于较大的文件它非常慢（可能需要几分钟到几小时）。但是，我对密码学的了解并不多，所以我不确定如何提高速度，或者是否有可能。输出给出了与不同编程语言的其他库完全相同的 CBC-MAC，所以它工作正常。
不幸的是，我在使用外部库方面非常有限..虽然来自 bouncycastle 的 class 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 = "[=11=][=11=][=11=][=11=][=11=][=11=][=11=][=11=][=11=][=11=][=11=][=11=][=11=][=11=][=11=][=11=]";
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)'[=11=]');
}
}
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();
}
我主要怀疑第一个循环中的查找操作只处理了 16 个字节。我不知道该算法，但您的代码表明可以阅读完整的 "chunk" 然后您可以处理它是否有必要部分。
此外，块似乎是连续的（除非我遗漏了什么）所以整个阅读可以在没有搜索的情况下按顺序完成。
您的辅助方法中不需要 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;
}
同样在 main 方法中，您将字节转换为字符串只是为了在 str_to_a32 的开头将它们转换回 byte[]，您应该只使用 byte[] 作为此方法的输入。
我仍然认为您应该一次读取整个块，然后以 16 字节为单位进行处理。
您的代码中可能存在问题：您尝试读取 16 个字节，但如果读取的字节数较少，则开始填充。但是，读取合同是 "An attempt is made to read as many as len bytes, but a smaller number may be read." 通常，较小的数字出现在文件末尾，但原则上它可能随时发生。如果是这样，您将开始在流的中间填充并完全弄乱您的部分。