CBC-MAC AES собственная реализация крайне медленно
Для проекта мне нужно реализовать функцию в Android (с Java), которая генерирует CBC-MAC (AES) из файла. Таким образом, в основном функция берет разные "блоки" из файла и вычисляет идентификатор для каждого блока и, наконец, объединяет его с идентификатором для всего файла.
Функция отлично работает, однако для больших файлов она чрезвычайно медленная (может занять минуты или часы) из-за реализованных циклов. Тем не менее, мои знания в области криптографии не очень далеко, поэтому я не уверен, как улучшить скорость или, если это вообще возможно. Вывод дает точно такой же CBC-MAC, как и другие библиотеки на разных языках программирования, так что все работает нормально.
К сожалению, я довольно ограничен в использовании внешних библиотек... хотя класс CBCBlockCipherMac из bouncycastle возможен, так как я смог включить его только с несколькими зависимостями, но так и не смог выдать тот же вывод, что и нижеупомянутая функция.
Все отзывы приветствуются, я пытался решить это в течение 3 дней, но не могу понять это. Спасибо!
* Обновление Похоже, что функция str_to_a32 в цикле for (с циклом каждые 16 байт) вызывает наибольшую проблему со скоростью. Так что, если бы эту функцию можно было сделать быстрее, это решило бы проблему в основном. Кроме того, к сожалению, необходимо выполнять цикл через каждые 16 байтов, так как я реализую ту же функцию CBC-MAC, которую также реализовал облачный провайдер Mega.
Код
//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();
}
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;
}
Также в методе main вы конвертируете байты в строку только для преобразования их обратно в byte[] в начале str_to_a32, вы должны просто использовать byte[] в качестве входных данных этого метода.
Я все еще верю, что вы должны прочитать весь блок сразу, а затем обработать его блоками по 16 байт.
В вашем коде есть потенциальная проблема: вы пытаетесь прочитать 16 байтов, но если вы получаете меньше, вы начинаете заполнять. Тем не менее, контракт на чтение: "Предпринята попытка прочитать столько же, сколько и байтов, но может быть прочитано меньшее число". Обычно меньшее число встречается в конце файла, но в принципе это может произойти в любое время. Если это так, вы начнете заполнение в середине потока и полностью испортите свои части.