Сколько (или мало) энтропийных паролей, сгенерированных таким образом, имеют

Поэтому я знаю, что создание пароля следующим образом - плохая идея. Я бы сказал, что у него всего несколько (например, 5 или около того) битов энтропии, но я не могу правильно ее рассчитать.

Может ли кто-нибудь показать мне, как рассчитать среднее количество попыток, необходимых для угадывания пароля длины n, сгенерированного следующим образом с использованием Oracle JDK 7?

Я предполагаю, что релевантными факторами являются:

  • размер алфавита (62–5 для ограничения символов, выглядящих запутанными),
  • двухэтапный процесс для выбора класса персонажа, а затем персонажа,
  • округление до целого числа,
  • пробовать до успеха способ выборки символов,
  • внутренние свойства Math.random().

Но я не могу получить точные цифры.

char[] generate(int n) {
    char[] pw = new char[n];
    for (int i = 0; i < n; i++) {
        int c;
        while (true) {
            c = randomCharacter(c);
            if (c == '0' || c == 'O' || c == 'I' || c == '1' || c == 'l') 
                continue;
             else 
                break;
        }
        pw[i] = (char) c;
    }
    return pw;
}

int randomCharacter(int c) { 
    switch ((int) (Math.random() * 3)) {
    case 0:
        c = '0' + (int) (Math.random() * 10);
        break;
    case 1:
        c = 'a' + (int) (Math.random() * 26);
        break;
    case 2:
        c = 'A' + (int) (Math.random() * 26);
        break;
    }
    return c;
}

person Jakub Bochenski    schedule 05.03.2014    source источник
comment
Внутренние свойства Math.random зависят от его реализации. Вы не указали ни одного. Вы даже не указали язык (я думаю, Java).   -  person CodesInChaos    schedule 05.03.2014
comment
Хороший вопрос, я столкнулся с ограничением тегов и забыл упомянуть об этом в другом месте.   -  person Jakub Bochenski    schedule 05.03.2014


Ответы (1)


Предполагая, что Math.random() непредсказуемо, для функции randomCharacter вероятность возврата определенной цифры равна 1/3 * 1/10, а буквы - 1/3 * 1/52.

Для записей в массиве pw некоторые символы недействительны, поэтому вероятность остальных символов становится выше. Вам нужно перемасштабировать вероятности так, чтобы сумма снова стала равной 1, т. е. разделить на сумму оставшихся вероятностей. В результате цифра имеет вероятность 1/3 * 1/10 / (8 * 1/3 * 1/10 + 47 * 1/3 * 1/52), а буква 1/3 * 1/52 / (8 * 1/3 * 1/10 + 47 * 1/3 * 1/52).

Подстановка всех этих значений в формулу для энтропии Шеннона дает результат около 5,7 бит энтропии на символ.

Если бы вы использовали один массив из 57 допустимых символов и использовали бы одно случайное число для его индексации, вы бы получили энтропию около 5,8 бит на символ.

person CL.    schedule 07.03.2014
comment
Это все еще верно, если Math.random() - это всего лишь PRNG, а не идеально непредсказуемый? Я думал, что, как правило, для PRNG, вызывая его много раз, чтобы получить один символ, на самом деле уменьшится энтропия. - person Jakub Bochenski; 07.03.2014
comment
Если PRNG предсказуем, злоумышленник сможет предсказать ваш пароль, поэтому в этом случае энтропия равна нулю. - person CL.; 07.03.2014
comment
Я имею в виду, что вывод PRNG не полностью независим от предыдущих значений. В действительности, например. распределение второй буквы зависит от первой буквы (вот почему вы обычно хотите использовать криптографический PRNG). Очевидно, что это снижает энтропию, но как ее измерить? - person Jakub Bochenski; 07.03.2014
comment
Это зависит от 1) того, как вы количественно оцениваете энтропию ГПСЧ, и 2) насколько это влияет на выбор буквы (потому что вы берете случайное число от 0 до 1, но в конечном итоге используете только информацию, будь то, например, в интервалах 0..1/3, 1/3..2/3, 2/3..1). - person CL.; 08.03.2014
comment
Да, но это именно та часть, с которой у меня проблемы, какие-нибудь указатели? - person Jakub Bochenski; 08.03.2014