Сжатие подписи
Предположим, у меня есть 64-байтовая подпись (из ed25519), которую создает одна сторона. Эта сторона должна дополнительно сжать подпись, чтобы она составляла 4-8 цифр в базе 2048. Затем вторая сторона должна иметь возможность воссоздать подпись из данных.
Вот пример десятичной подписи:5670805304946899675614751184947294808143702505785021095830828785725573127924144977212837580418240432902375737987653828318622222068237988634991262293689098
Как я могу сжать эту подпись примерно до 4 цифр в базе 2048? Возможно ли это с помощью сжатия Судоку?
2 ответа
Я бы сказал, что это невозможно. По крайней мере, та часть, где вы говорите: "вторая сторона должна иметь возможность воссоздать подпись на основе данных"
Простая причина этого - энтропия, или количество информации, содержащейся в каждой подписи. Во-первых, давайте посмотрим, сколько информации может храниться максимально в каждом из "форматов", которые вы описываете.
- сигнатура ed25519: 64 байта, то есть 512 бит (таким образом, 2^512 возможностей, около 1.34e154)
- 4 цифры в базе 2048, то есть 2048^4 возможностей, и log2 ((2 ^ 11) ^ 4) = 44
- 8 цифр (так как вы сказали 4-8), то же самое рассуждение, 88 бит
Так что это уже намного меньше (максимально возможная) информация из цифр на основе 2048. Чтобы ваша функция существовала, это означало бы, что каким-то образом среди 2^512 возможностей достаточно избыточной информации (т. Е. Если вы знаете биты a и b, у вас есть высокая вероятность узнать бит c или, возможно, некоторую конфигурацию значений совершенно невозможно и т. д.) чтобы вы могли охарактеризовать все возможные выходы с 44 (или 88) битами.
Давайте посмотрим на теорему Шеннона об исходном кодировании:
N iid случайных величин, каждая из которых имеет энтропию H(X), может быть сжата в более чем N H(X) битов с незначительным риском потери информации, при N → ∞; но, наоборот, если они сжаты в меньше, чем N H(X) битов, то практически наверняка информация будет потеряна.
Здесь случайными величинами являются сигнатуры ed25519. Вы спрашиваете две вещи
- Если H (<случайные ed25519 подписи>) может быть 44 или 88.
- Если этот предел может быть достигнут с N=1 вместо N→∞, потому что вы хотите, чтобы каждая сигнатура была закодирована с 44 или 88 битами, а не среднее число битов для N подписей должно быть ниже 44 или 88. Это намного более сильное требование
В сигнатуре ed25519 определенно больше энтропии, чем когда-либо в 44 или 88 битах. С сайта Введение в Ed25519:
Высокий уровень безопасности. Эта система имеет цель безопасности 2^128; взломать его аналогично трудностям взлома NIST P-256, RSA с ~3000-битными ключами, надежных 128-битных блочных шифров и т. д. Лучшие известные атаки на самом деле стоят в среднем более 2^140-битных операций и квадратично ухудшаются в случае успеха вероятность как количество битовых операций падает.
Но если бы ваша функция существовала, вероятно, было бы намного проще, потому что вам достаточно иметь 2^44 (или 2^88) попыток, каждый раз применяя "обратную" функцию, чтобы исчерпывающе найти все коллизии. Конечно, мы не знаем, сколько битовых операций стоит гипотетическая обратная функция, но, по крайней мере, она дает вам представление. Кроме того, если вы выполняете эту атаку грубой силой с помощью атаки на день рождения, вам понадобится только квадратный корень из этого числа попыток (таким образом, 2^22 или 2^44).
И наоборот, если вы читаете статью, в которой эта атака выполняется в среднем из 2^140 операций, с 2^i итерациями по 2^o операций в каждой (таким образом, i+o=140), вы можете надеяться найти формат, который разумно перечисляет все возможные 64-байтовые подписи с 2*i битами. Однако это применимо только к первому вопросу, поскольку атака может использовать такие свойства, как некоторые значения сигнатур, которые встречаются чаще, чем другие. Тогда ваша оптимальная длина хранилища 2*i будет достигнута только в среднем, а не для каждого значения, путем кодирования некоторых значений, которые встречаются чаще с меньшим количеством битов, чем значения, встречающиеся чаще.
В дополнение к этому мы читаем:
Маленькие подписи. Подписи умещаются в 64 байта. Эти подписи на самом деле являются сжатыми версиями более длинных подписей; время сжатия и распаковки включено в число циклов, указанное выше.
Это означает, что даже если в большем ключе были некоторые избыточности, они уже сделали дополнительный проход сжатия, и мы можем разумно предположить, что должна быть такая же, если не более высокая плотность информации в меньшем ключе. Т.е. шансы найти избыточность еще меньше.
Таким образом, это означает, что если вы примените преобразование из подписи к 44-88 битам, вы потеряете информацию, в значительной степени взяв хэш из ваших 64 байтов. Столь же верно, как невозможно воссоздать файл, который вы скачали из его контрольной суммы, это сделало бы невозможным воссоздание сигнатуры ed25519 из вычисленного вами хэша.
Подпись имеет размер 64 байта, поэтому возможно 256^64 или 2^512 возможных подписей. Эта степень сжатия будет возможна, только если будет использовано не более 2048^8 = 2^88 из 2 512 возможных подписей. Это кажется маловероятным, чтобы иметь место с Ed25519.
Изменить: Вопрос был изменен и уточнен, чтобы спросить, возможно ли здесь сжатие судоку. Существует 6670903752021072936960 = 2^72,49... способов заполнения сетки Судоку, намного меньших, чем 9^81 = 2^256,7... способов маркировки каждой ячейки. Но то же самое не должно быть в случае с алгоритмом подписи, поэтому такое сжатие теоретически невозможно.