Помогите пожалуйста найти (или придумать) такую пару криптоалгоритмов: 1. На входе - набор N штук строк X (если это упростит задачу то можно считать что они все одинаковой длины) и соответствующих чисел P. На выходе - блок данных R. 2. На входе - R и случайное число t. на выходе - одно из чисел X с вероятностью P. При этом имея R должно быть невозможно вычислить N быстрее чем перебором всех t.
Позволю попытаться уточнить : 1. Так ? Или именно "выяснить N" ? 2. Теперь вопрос о порядках величин : N, длина X(i) (пусть называется L) ? Если подразумевается хранить их все "замешанными" в один блок R, то очевидно что N*L не может быть больше скажем 2^32 (4 Гигабайта), а само log2(N), соответственно, больше чем 28-30 бит ? 3. Какая связь между t и выданным на алгоритмом №2 числом ? При подаче одинакового t должно появляться на выходе одно и то же число X(i) ? Что есть "t" ? Вещественное или целое ? Если целое, то какого порядка его разрядность ?
1. имея только R должно быть невозможно выяснить точное количество исходных строк (N) (понятно что можно оценить максимум исходя из размера R). То есть сколько бы t не перебиралось не может быть уверенности что все X найдены, т.к. могут быть X с низкой вероятностью. 2. X - блоки кода программы (или ключи для их расшифровки). Можно предположить что N порядка от нескольких десятков до нескольких тысяч. 3. t - целое достаточно большой разрядности (128-256 бит). Понятно что при одинаковом R и t будет вычислено одинаковое X Общий смысл такой что кто угодно имея R может вычислить лишь некоторые X (с высокой вероятностью) но не может гарантировать что найдены ВСЕ X.
Подскажите хотя бы стоит ли искать это в умных книжках или лучше пытаться придумать самому ? И поскольку пока ничего похожего не найдено то либо я плохо искал либо такой алгоритм невозможен ( тогда наверно должно найтись доказательство ?).
4ept Пока задача содержит явные противоречия - например вы пишите в #3: а в #1: - и как такое может быть? "при одинаковом R и t будет вычислено одинаковое X" - значит вероятность вычисления определенног X по заданным R и t будет равна 1... тогда - упомянутая вероятность P вообще непричем-?
Кажется формулировка должна звучать так: Дано - вектор [o]X[/o] и [o]P[/o]. Надо придумать 2 функции E и D такие, что 1) R = E([o]X[/o],[o]P[/o]) 2) Для любого целого t из некоторого (достаточно большого диапазона K) определена функция D(R,t)=X', где X' принадлежит [o]X[/o] 3) Пусть T множество из t, таких, что D(R,t) = X. Тогда |T| / |K| = P
Изложу 3 сырых соображения : 1. С вероятностями проще всего работать, являющимися отрицательными степенями "2"-ки. То есть по факту формируется двоичное дерево с узкими глубокими "маловероятными" ветвями, структуру которого нам нужно скрыть в R. Скрывать нужно обязательно, т.к. иначе факт наличия маловероятной веточки будет сразу же виден. 2. Поскольку ключа как такового нет, следовательно, размещаемые данные должны быть статистически неотличимы от мусора, которым будет заполнен остаток R. Для этого либо необходимо доводить их до состояния L=E (размер равен энтропии), либо например, фрагментировать на блоки очень малого размера (2-4 байта) дабы эффективно перемешивать с другими "мусорными" блоками, обладающими теми же статистическими характеристиками. 3. Вроде бы можно использовать t как "алгоритм" передвижения (сборки) по массиву R с последующей проверкой контрольной суммы длины H бит, что дает нам вероятность 2^(-H), но тогда необходимо считать, что существует некоторое выделенное значение X[0], которое алгоритм D должен выдавать на выход при условии несовпадения контрольной суммы. Вероятность P[0] будет равна 1 - SUM(X[1]..X[N-1]). 4ept Готовых подобных алгоритмов лично я не встречал.
100gold Да, эта формулировка точнее. gorodon Видимо термин 'вероятность' несовсем точен в данном случае. Речь идет о том что множество t разбито на подмножества разного размера. OLS Мой вариант пока такой: добавить в X некоторое количество блоков с нулевой вероятностью. тогда не придется в алгоритме предусматривать разделение R на данные и мусор.
Хотя у меня осталось ощущение, что я всё равно не до конца понял задачу (т.е. модель угроз, которой должен противостоять криптопротокол), попытаюсь предложить черновой вариант. Все конкретные цифры далее по тексту - просто для обозначения порядка величины (мне так проще). Блок R составляется из двух частей : "каталога" и собственно зашифрованных строк - "файлов". Раздел "файлов" представляет собой скажем примерно от 2N до 8N записей равной длины, возможно содержащих строки X, возможно - нет. Каждый "файл" зашифрован симметричным алгоритмом в режиме CBC уникальным сессионным ключом Kf[j]. Каталог представляет собой 65536 записей, зашифрованных симметричным алгоритмом в режиме CBC каждая своим ключом Kd[m]. Каждая запись каталога имеет следующую структуру: - 32-битный ИД файла - "j", - 128-битный сессионный ключ Kf[j], - контрольная сумма 128+32 бит (проще всего - инверсия первых 32+128 бит записи) - нужна для того, чтобы алгоритм на любое t выдавал корректную строку X из начального набора - если этого требования нет и можно выдавать абсолютно незначащий мусор, то контрольную сумму можно сократить до 32 бит (от случайной ошибки это защитит вполне достаточно, а если кто-то будет умышленно искать верное t, то пусть получает бред). Извлечение строки X по известному 144-битному t производится следующим образом : - первые 16 бит используются как идентификатор "m" записи в каталоге; - следующие 128 бит используются для дешифрования m-ой записи в каталоге. Если после дешифрования контрольная сумма валидна, то алгоритм переходит, отталкиваясь от расшифрованной информации, к файлу "j", расшифровывает его ключом Kf[j] и выдает на выход. Если контрольная сумма не валидна, на выход подается особое значение X[0]. Различные вероятности появления строк X, заложенные в условии задачи, реализуются как раз посредством особой организации каталога - сразу несколько его записей могут хранить ИД и сессионные ключи одного и того же файла "j" (множественные ссылки на один и тот же файл), при этом они зашифрованы они каждый раз разным ключом Kd[m], а, следовательно, сохраняют в секрете информацию об общем кол-ве N и вероятностях массива P. По факту получившаяся схема является системой симметричного депонирования ключей, только с непривычно большим количеством депонирующих агентов. Допустимый системой порядок разброса вероятностей (отношение самой большой вероятности к самой маленькой, не считая, конечно X[0]) определяется только величиной каталога (размером первой части блока R) и не влияет на размер второй части R. Например, в каталоге указанного выше размера 65536 Вы можете по 1000 раз упомянуть 60 уникальных шифруемых строк + по 10 раз упомянуть 500 других уникальных строк + 536 упомянуть другие уникальные строки единожды.
Спасибо. Подход к решению интересный (и не похож ни на один из моих вариантов). Только непонятно вот что: берем случайное t (144 бит), выбираем строку каталога по первым 16 битам и пытаемся расшифровать используя оставшуюся часть t в качестве ключа. вероятность получить валидный результат 2^-128. то есть для получения одной из строк X придется выполнить ~2^64 попыток? На самом деле это может оказаться приемлемым подходом (в моем случае) если уменьшить разрядность (до примерно 2^20 - 2^30). В общем похоже что может получиться. В моих вариантах любое t выдает результат, но ценой катастрофического увеличения размера R. Если я правильно понимаю придется искать компромисный вариант между размером R и количеством вычислений требуемых для получения одного X ? Добавление: похоже что всё таки не подойдет. Т.к. в такой реализации решение задачи 'найти ВСЕ X' сводится к задаче 'найти какое нибудь X' повторённой 2^16 раз.
Про катастрофическое увеличение R - я тоже пришел к этому выводу (если только не придумать что-то древовидное). А по поводу перебора 2^127 - на мой взгляд Ваша задача в вероятностях порядка 2^-20 ... 2^-30 вообще лишена практического смысла, т.к. противодействующее Вам лицо просто выполнит полный перебор 2^32 за неделю-две и вскроет все внесенные в систему X. Если Вы действительно оперируете в этом диапазоне вероятностей, то на мой взгляд эта задача не имеет отношения к криптографии, максимум к теории вероятностей в части оценки того, сколько вариантов t необходимо проверить, чтобы получить заданный уровень достоверности того факта, что вскрыты все X. В любом случае получившаяся величина будет в пределах, доступных для полного перебора. Неважно, что Ваше t имеет длину 128 бит. Если оно должно открывать самую маловероятную строку с вероятностью 2^-30, то перебрав 2^34 вариантов мы обязательно попадем на эту строку, а этот перебор вполне по силам современной ЭВТ.
В моих вариантах как раз были деревья, а t определяло выбор пути в нём. Ну да с выбором разрядности придется подумать. И вероятно добавить ещё один слой т.к.
Типа черновик одного из моих вариантов: Пусть даны строки S и соответствующие вероятности P (P - целые от 1 до 2^16) 1 Алгоритм E: 1. Зашифруем каждую строку S -> S' случайно выбранным ключом Ks. 2. Создадим файл R. 3. Запишем в R по случайно выбранным смещениям S' (без пересечений) 4. Сформируем блоки Y состояшие из: смещения в файле строки S, длинны этой строки, ключа Ks и HASH(S). 5. Зашифруем каждый блок Y -> Y'[i,P] случайными ключами Ky[i,P] (каждый блок Y преобразуется в много блоков Y', пропорционально их вероятностям.) 6. Запишем в R по случайным смещениям Y'. 7. Оставшееся свободное место заполнить мусором. Алгоритм D: 1. Выберем случайное t. 2. Выполнить действия 3-5 для каждого смещения в файле R: 3. Расшифровать Y (используя t в качестве ключа) 4. Расшифровать S, получив ключ Ks из Y. 5. Проверить HASH(S). Если совпадает - то результат получен, иначе продолжаем. 6. если на шагах 3-5 результат не получен то выбрать другое t и на шаг 1.
Я не вижу принципиальных отличий от озвученного мной. Вы предлагаете при несовпадении хеша - идти к следующему t - при |T|=2^128 это будет очень жестоко по отношению к исполняющему процесс. Я предлагал, чтобы избежать этого выдавать сразу при неверном значении особое X[0]. В любом случае, чтобы получить идеальный ответ под Вашу задачу мы должны оперировать R размером порядка |T|, а это нереально, если Вы хотите защититься от полного перебора по T то есть выйти хотя бы на 2^80 вариантов.
Похоже что алгоритм без катастрофического роста R существует. Один из вариантов основан на дополнительном алгоритме F: 1: на входе строка X и число N, на выходе строка Y. 2: на входе строка Y, на выходе число X. при этом количество вычислений для преобразования 2 в N раз больше чем для преобразования 1, и имея Y невозможно заранее вычислить N Алгоритм E: 1. Имеющиеся строки S преобразовать алгоритмом F S2=F(S,Z) Z зависят от P 2. Из получившихся блоков S2 (N штук ) собрать N2 групп (в каждой группе случайное количество блоков + мусор) 3.Каждую группу преобразовать алгоритмом F аналогично п.1 4. Из получившихся блоков S3 (N2 штук ) собрать N3 групп 5. Повторить 2-4 ннесколько раз. 6. Затем всё это раскидать рандомом по файлу R, кроме последней группы, которую записать в начало файла. Алгоритм D: в качестве параметра t используется генератор случайных чисел. 1. Выбрать некоторое случайное время T, сколько мы готовы потратить на одну попытку получения строки S 2. Выбрать один из блоков SX, находящихся в начале файла (их точное количество неизвестно, поэтому возможно будет выбран мусор вместо правильного блока) 3. Попытаться расшифровать блок алгоритмом F (не дольше чем T) 4. Если результат не был получен, то либо T мало либо мы пытались расшифровать мусор. В обоих случаях на п.1 5. Если результат получен - то у насть есть либо новая группа (тогда на п.3), либо строка S (тогда готово) Собсвенно вопросы: 1. Хорошо бы найти правильный алгоритм F, применимый в данном случае. 2. Как вычислить Z, N2,N3 .... так чтобы обеспечить требуемые вероятности P ?
