Краткий алгоритм «код прогресса»

Question

У кого-нибудь есть идеи для безопасного кодирования небольшого объема данных примерно в 8 символов?У меня есть проект (Flash и Flex (AS3), который не имеет особого значения), который должен быть развернут на CD / DVD-ROM (без локального хранилища или доступа к сети), но с требованием разрешить людям возвращаться туда, где они остановились.Следовательно, необходим код, который удобен для печати человеком (на «мертвом дереве» или в формате PDF) или для записи и ввода обратно в поле ввода, а также безопасен, чтобы не допустить мошенничества между разными учащимися.

Существует 14 предметов оценки, которые могут быть выполнены в любом порядке.На данный момент я CRC32 их "имя для входа" и беру 16 бит из этого результата, и объединить их с 14 оценочными битами в 30 бит, которые затем кодируются с использованием формы Base32, давая 6 символов, затем добавляя контрольный символ, затемиспользование замены символов для шифрования.После возврата в программу и ввода 7-значного кода выполнения, после дешифрования и извлечения, если в именных хэш-частях есть совпадение, предполагается, что биты завершения являются правильными.

Была выявлена ​​только одна проблема:два символа меняются при заполнении каждого элемента.Есть ли какой-нибудь алгоритм, который полностью изменит всю строку, если изменится хотя бы один бит?Или есть совершенно лучший способ?Я также хотел бы хранить больше данных (даты, больше битов для хэша, чтобы уменьшить коллизии, местоположение в курсе и т. Д.), Но не хочу, чтобы они превышали 8 или 10 символов.

Answer 1

Все хеш-функции криптографической стойкости (например, MD5) обладают свойством, что изменение одного входного бита будет изменять каждый выходной бит с вероятностью почти 50%.Я бы предложил простую двухэтапную процедуру при генерации кода прогресса:

1. Представлять завершенные элементы в виде 14-значной двоичной строки (например, выполненные пункты 1, 2 и 4 будут представлены строкой11010000000000).Возьмите первые 4 байта (8 шестнадцатеричных цифр) хэша MD5 этой строки.
2. Возьмите первые 4 байта хэша MD5 имени пользователя.
3. XOR это вместеи сообщите результат в виде 8-шестнадцатеричной строки.

Когда пользователь позже вернется к своей работе:

1. Возьмите первые 4 байта хэша MD5имени пользователя для входа в систему.
2. Запрашивает код прогресса.
3. XOR они вместе образуют первые 4 байта хеша MD5 14-значной двоичной строки.
4. Найдите это в предварительно вычисленной таблице, содержащей все 2 ^ 14 = 16384 возможных действительных результатов, чтобы точно определить, какая комбинация элементов была завершена.(Количество возможностей достаточно мало, чтобы было возможно линейное сканирование, хотя бинарный поиск будет еще быстрее.)

Существует небольшая вероятность того, что первые 4 байта MD5-хэшей всехэти 14-значные двоичные строки не будут различаться.В соответствии с приближением здесь , но при n = 2 ^ 14 и использовании 2 ^ 32 вместо 365, вероятность этого составляет около 3%.Если да, то я предлагаю добавить несколько фиксированных символов к каждому и повторить попытку, пока не будет достигнута четкость.Это не должно занять много попыток, учитывая низкую вероятность столкновения.Обратите внимание, что использование только 7 шестнадцатеричных цифр увеличивает вероятность столкновения примерно до 40%, так что не делайте этого!Нет необходимости использовать отдельную схему контрольных цифр, так как только 2 ^ 14 в 2 ^ 32 или 1 в 262144 случайно угаданных кодах прогресса будут действительны.

Если вы обеспокоены тем, что опытные пользователи могутчтобы подделать свои собственные коды прогресса, отменив XOR чужого кода прогресса и сохранив XOR хэш MD5 их собственного имени пользователя, вы всегда можете сначала «засолить» имена пользователей, добавив фиксированную строку (известную толькоВам) каждому имени пользователя.

Answer 2

Как и большинство шифрований, оно просто должно быть сильнее, чем ценность защищаемых данных.

Судя по всему, вы не против правительств или профессиональных криптографов ...

Если бы у меня было еще пара символов, вы могли бы использовать настоящий алгоритм шифрования с относительно небольшим размером блока (на ум приходит CAST-128 с размером блока 64 бита).Кодировка Base64 увеличит код до 12 символов.

т.е.Код = Base64 (CAST128 (имя пользователя + биты завершения)).Чтобы избежать случаев длинных имен пользователей, вы можете сначала его хешировать:

Код = Base64 (CAST128 (хэш (имя пользователя) + биты завершения))

Должно быть достаточно безопасным для программы оценки.(Одна вопиющая проблема заключается в том, что вам нужно встроить ключ в программное обеспечение ... но, опять же, если вы не против правительственных агентов ...)