Здравствуйте, Sharowarsheg, Вы писали:
vsb>>Некая энтропия (не уверен, что правильно пользуюсь этим термином) для x1 очевидно равна 64 бита. Т.е. имеется 2^64 вариантов.
S>Какая энтропия? Вовсе не очевидно, что она равна 64 бита. Зависит, например, от псевдорандомного генератора. Вообще, определений разных куча, так что определяй.
Генератор будем считать рандомным.
Ну можно так определить. Пусть есть злоумышленник, который хочет подобрать это число. Если это x1, то ему надо перебрать числа и в среднем ему понадобится 2^63 попыток. Для xn очевидно перебирать нужно с конца (можно переформулировать задачу зеркально отразив для упрощения рассуждений). То бишь надо определить, сколько в среднем понадобится попыток злуомышленнику, чтобы найти число xn.
Если заменить формулировку задачи с 64 на 8 битов, n = 2, x2 < x1. Получается, что x1 генерируется от 1 до 255 (0 опускаем, чтобы не было ситуации с невозможным x2). Для каждого равновероятного x1 от 1 до 255 рассматриваем равновероятные x2 от 0 до (x1 — 1). Далее находим среднее арифметическое всех таких x2 и это кажется будет тем самым числом попыток (минус один), с которых в среднем злоумышленник будет угадывать x2, перебирая с 0. Получается [(0) + (0 + 1) + (0 + 1 + 2) + ... + (0 + ... + 254)] / (1 + 2 + ... + 255) = [0 * 1 / 2 + 1 * 2 / 2 + 2 * 3 / 2 + ... + 254 * 255 / 2] / [(1 + 255) * 255 / 2] = [\sum_{i = 0}^{254} i * (i + 1) / 2] / (256 * 255 / 2)
Как это посчитать я не знаю. Если просто посчитать — получится 84.(6). То бишь на подбор первого числа в среднем нужно 128 попыток, на подбор второго — 85.(6) попытки. Если я нигде не напутал. Ну да — явно не минус один бит.
Для n = 3 и 8 битов получается 63.25, для 4 битов получается 50.4. Это я просто перебором сделал. В принципе формула очевидная — (256 — n) / (n + 1). Хм. Сам решил что-ли, методом подбора. Если так, то выходит, что от исходного числа битов "энтропии" отнимается примерно log2(n) битов (ну там +-1, лень думать). То бишь если вернуться к исходной постановке задачи, то можно сгенерировать 1024 таких чисел и отнимется всего 10 битов энтропии. Неплохо.
