CRC32 Столкновение
Для первой проблемы вы пытаетесь добавить String в экземпляр List. Вы можете использовать String для создания экземпляра CelebrityNamesFile и добавить этот экземпляр в ваш список:
CelebrityNamesFile celebrityNamesFile = new CelebrityNamesFile();
celebrityNamesFile.lastName = oneName;
myCelebrityList.add( celebrityNamesFile );
Для второй проблемы попробуйте
Collections.sort(myCelebrityList, new CompareLastName());
Как точки @alyu, класс CelebrityNamesFile должен реализовать интерфейс Comparable для работы с кодом, который вы публикуете, но вы также можете добавить экземпляр Comparator (и у вас уже есть класс CompareLastName, который его реализует).
Подробнее об этом:
5 ответов
Это полностью зависит от того, что вы подразумеваете под «сообщением». Если вы можете добавить четыре байта тарабарщины к одному из сообщений. (IE четыре байта, которые не имеют значения в контексте сообщения.) Тогда это становится тривиальным в прямом смысле слова.
Мыслить в терминах битов, проходящих через конечный автомат CRC32.
CRC32 основан на регистр сдвига с обратной связью с галуа, каждый бит в его состоянии будет заменен индукцией 32 бит из данных полезной нагрузки. При индукции каждого бита позиции, указанные полиномом, будут исключены с последовательностью, наблюдаемой с конца регистра сдвига. Эта последовательность не зависит от входных данных до тех пор, пока сдвиговый регистр не будет заполнен.
В качестве примера представьте, что у нас есть сдвиговый регистр, заполненный начальным состоянием 10101110, полиномом 10000011, Итак, чтобы сгенерировать сообщение с заранее определенной контрольной суммой, вы берете новое сообщение, генерируете его CRC и вычисляете следующие 32 бита обратной связи. Это можно сделать за 32 шага функции CRC. Затем вам нужно рассчитать влияние этой обратной связи на содержимое сдвигового регистра.
Для этого можно добавить в сообщение четыре нулевых байта, а затем посмотреть контрольную сумму. (Контрольная сумма - это состояние SR в конце, которое, если оно дополнено четырьмя нулевыми байтами, является влиянием обратной связи и пустых байтов.)
Исключающее ИЛИ, которое влияет на значение контрольной суммы, которое вы хотите, замените четырехбайтовый концевой с этим вычисленным значением и восстановить контрольную сумму. Вы можете сделать это с помощью любой программы, генерирующей CRC32, шестнадцатеричного редактора и калькулятора, который может обрабатывать шестнадцатеричный код.
Если вы хотите сгенерировать два сообщения, которые имеют полный смысл и не содержат завершающего мусора, все становится немного сложнее. Определите количество разделов, в которых вы можете написать правдоподобные альтернативы, с точно такой же длиной.
На примере английской прозы. «Я думаю, это может сработать» а также «Я верю в такой подход» Имеют в целом схожее значение и точно такую же длину.
Идентификация достаточного количества примеров в вашем сообщении - сложная задача (если вы не хотите обмануть пробелами!) CRC 32 является линейным, при условии, что данные имеют правильное смещение в сообщении. Итак, CRC ([messagea] [padding]) ^ CRC ([padding] [messageb]) = CRC ([messagea] [messageb]) Есть некоторые предостережения относительно выравнивания слов, с которыми вам нужно будет справиться. В качестве общего совета вы хотите расширить отрывки до «фиксированных» частей сообщения. Как правило, вы хотите иметь альтернативы для n * 1,5 отрывков, где n - размер CRC.
Теперь вы можете вычислить CRC, который имеет скелетное сообщение, и такое впечатление, что каждый альтернативный отрывок будет на нем, а затем составьте таблицу, сравнивая влияние каждой альтернативы для каждого отрывка. Затем вам нужно выбрать альтернативы, которые изменят скелетный CRC в соответствии с нужным CRC. Эту проблему на самом деле довольно интересно решить. Во-первых, найдите любые альтернативы, которые однозначно изменяют бит, если этот бит нужно изменить для вашего CRC, выберите эту альтернативу и сложите ее влияние в CRC, а затем повторите попытку. Это должно уменьшить пространство для решения, которое вам нужно искать.
Это довольно сложная вещь для программирования, но она приведет к вашим столкновениям за очень короткий промежуток времени.
Я предполагаю, что вы имеете в виду «сообщение», а не «ключ».
Если вам разрешено выбирать оба «ключа», тогда перебор все равно поторопитесь из-за парадокса дня рождения. Выберите случайные сообщения, вычислите их CRC, запомните все из них и связанный CRC, и каждое новое имеет все больше и больше шансов столкнуться с существующим по мере их накопления. Честно говоря, я ожидаю, что этот подход будет быстрее на современном компьютере, чем поиск известных подходов к конфликту CRC32.
Если не считать недостатка в моих расчетах, вероятность того, что не обнаружит одно столкновение после N попыток, приблизительно представлена в следующей таблице:
N Probability ------- ----------- 50,000 74.7% 77,000 50.1% 78,000 49.2% 102,000 29.8% 110,000 24.5% 128,000 14.8% 150,000 7.3% 200,000 0.95%
Другими словами, вероятность того, что потребуется вычислить более 200 000 значений CRC32 до обнаружения дубликата, составляет менее 1%, или вероятность обнаружения дубликата до 102 000 попыток составляет 70,2%
Кстати, это примечательно, потому что вероятность обнаружения одного столкновения, скажем, на самой 200000-й попытке все еще составляет порядка 1/1000 от 1% ((4M - 200,0000) / 4M), но вероятно обнаружение одного столкновения до 200000-й попытки - это квази определенность (ну, в любом случае, выше 99%). Это показывает интерес к ведению базы данных вычисленных CRC до сих пор .
Мы, безусловно, могли бы потратить некоторое время на изучение алгоритма CRC32 и лежащих в его основе математических выкладок, в попытке найти сообщения с большей вероятностью вызывают коллизии CRC32 , но относительно небольшое количество действительно случайных попыток, требуемых для нахождения хотя бы одной коллизии с квазиопределенностью, делает такой подход криптоанализа едва ли стоящим усилий. или, лучше, формальный интерфейс СУБД, такой как MySql или даже SqlLite.
Я считаю, что CRC линейны, поэтому, если вы изменяете (на месте, без изменения длины) две разные части файла, различия в CRC должны быть устранены вместе.
- поправка: кажется, не все так просто. Тем не менее, я все еще придерживаюсь такого подхода, пытаясь построить столкновение - вам нужно следовать математике более подробно, чем я склонен делать сегодня вечером ...
Буквально вчера был этот вопрос здесь, на SO , пара упомянутых там указателей может вам помочь.