Алгоритм генерации паролей Mnemonic для QWERTY-клавиатур

У меня есть " mnemonic" функция генерации пароля, которая выглядит примерно так:

function Mnemonic($mnemonic)
{
    $result = null;
    $charset = array(str_split('aeiou', 1), str_split('bcdfghjklmnpqrstvwxyz', 1));

    for ($i = 1; $i <= $mnemonic; $i++)
    {
        $result .= $charset[$i % 2][array_rand($charset[$i % 2])];
    }

    return $result;
}

В основном это генерирует строку с длиной $mnemonic, где каждый нечетный символ является согласным, а каждый четный символ является гласным. Хотя я понимаю, что это снижает сложность пароля, обычно гораздо легче запоминать. Теперь я хочу улучшить его, создав строки, которые легко набирать.

Например, в то время как новичок * nix я всегда предпочитаю RHEL-дистрибутивы над Debian, основная причина заключается в легкости ввода yum по сравнению с легкостью ввода apt[-get], просто попробуйте это для себя.

Как мне реализовать логику для генерации строк, которые легко набирать на клавиатурах QWERTY?

Ответ 1

Вы можете взглянуть на принципы используемые в клавиатуре Dvorak,

Эти принципы, применяемые в алгоритме генерации паролей, будут такими:

Буквы должны быть напечатаны путем изменения рук.
Используйте простые комбинации. Взгляните на макет Дворжака и посмотрите общие орграфы и позиции их букв.
Используйте только одну букву из нижней строки или нет. Сделайте это случайным!
Вы можете сделать соотношение 2 к 1 (2 буквы, напечатанные правой рукой, до 1 буквы, введенной левой рукой).
Поскольку отношение равно 2 к 1, у вас будет 2 последовательных буквы, введенных одной рукой, поэтому вам нужно будет убедиться, что они напечатаны снаружи клавиатуры внутри. Этот принцип применяется к орграфам.

Я знаю, что вы сказали, что это QWERTY-клавиатура, но использование этих принципов на клавиатуре QWERTY может дать вам очень хорошие результаты, например:

ktrd, ogkdo ( "пишущая машинка" в двораке)

kjg; g; akd; k (используя только домашнюю строку)

pjedoildupsk (просто случайный пароль, следуя принципам)

Все Дворжаки ненавистники, шушайте!

Надеюсь, это поможет.

Ответ 2

Carpalx имеет много исследований по вычислению ввода усилие, которое включает:

расстояние перемещения пальца

штрафы за руки, пальцы и ряды.

путь хода

Результатом их исследования является раскладка клавиатуры Colemak, которая утверждает, что он лучше, чем Дворжак.

Однако, он написан назад от того, что вы хотите - их цель - найти лучшую раскладку клавиатуры на основе ввода, но вы пытаетесь найти легкий ввод на основе раскладки клавиатуры.

Итак, даже если вы не можете использовать его напрямую, я подумал, что вам может показаться интересным (и кто знает, если ваш Perl-fu сильный, вы можете извлечь и отменить алгоритм, поскольку он GPL'd).

Ответ 3

Вы можете удалить все символы, набранные с кольцом и мизинец (q, w, x, z, p), а затем наполнить символы, которые набираются левой и правой руками, и чередовать их между символами.

Ответ 4

Возможно, вы можете использовать некоторую эвристику для измерения "легкости ввода".

Например, рассмотрите стоимость перемещения пальца при переходе к следующему символу. Это может быть функцией того, как далеко двигаться пальцем, в каком направлении и т.д.

Вы также можете добавить дополнительные затраты, когда требуется переключение пальцев или рук.

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

Надеюсь, что это поможет.

Ответ 5

Отличный вопрос - взяв приведенные выше предложения, здесь формулы для расстояния от ключа я до ключа j:

Вес = расстояние * a + переключатель * b + тот же * c + shift * d + weird * e + start * f

Расстояние - это значение, остальные значения - 0/1.

Расстояние - получить, наложив тонкую сетку на QWERTY-клавиатуру, найдите x, y и вычислить расстояние. Расстояние имеет положительный вес. Если комбинация букв используется с использованием разных рук (например, aj, sk, wu...), расстояние равно нулю.

Переключатель - отрицательный вес; переключение хорошее

То же самое - aq, qa, az, za используют один и тот же палец. То же самое положительное

Сдвиг - все с сдвигом положительно и реально плохо

Странно - я не знаю, или это плохо, потому что вы должны смотреть на клавиатуру.

Начало - asdfjkl начиная или заканчивая. Вероятно, отрицательный и хороший, так как ваши пальцы находятся в состоянии покоя.

Коэффициенты - просто запустите их, чтобы начать, пока относительные значения кажутся разумными. Если вы ДЕЙСТВИТЕЛЬНО хотите получить фантазию - попросите кого-нибудь ввести несколько десятков наборов чисел, используйте секундомер и установите модель регрессии.

Реализация - скажем, у нас есть пароль с шестью символами.

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

Готов поспорить, что кто-то сделал это раньше - особенно часть нажатия клавиши.

Ответ 6

Я разбил следующее. Это взломанная работа, но, похоже, она работает очень хорошо.

<?
function Mnemonic($mnemonic)
{
    $result = null;
    $charset = array(str_split('@a3e!1i0ou', 1), str_split('#$*bcdfghjklmnpqrstvwxyz', 1));

    $lastchar = ' ';
    for ($i = 1; $i <= $mnemonic; $i++)
    {
      do {
        $char = $charset[$i % 2][array_rand($charset[$i % 2])];
      } while (!nextkey($lastchar, $char));
      $result .= $char;
    }

    return $result;
}

function nextkey($lastchar, $requestchar)
{
  $map = array();
  $map[] = '!qaz'; // ll
  $map[] = @#wsx1'; // lr
  $map[] = 'ed23'; // lm
  $map[] = '$%^rtfgcvb456'; // li
  $map[] = '&yhnujm7'; // ri
  $map[] = '*()ik89'; // rm
  $map[] = 'olp,.'; // rr
  $map[] = ';[]'; // rl
  $map[] = '[email protected]#$%^&*()[]'; // special chars, don't follow
  $map[] = 'pbvcnmq'; // consonant clusters, don't follwo

  if($lastchar == $requestchar) return true;
  foreach($map as $string)
    if(strpos($string, $requestchar) && strpos($string, $lastchar)) return false;
  return true;
}

printf("%s\n", Mnemonic(8));
?>

Ответ 7

Создайте структуру данных, которая представляет собой клавиатуру и кодирует строку, столбец, руку и палец, используемые для ввода каждого символа. Напишите функцию, которая при представлении символа предоставляет список "простых для ввода следующих" символов на основе гибких правил, которые вы разрабатываете. Он может полагаться на другую функцию, которая вычисляет расстояние между клавишами.

Лично я не нахожу, что печатать буквы одной рукой вдвое медленнее: только если предыдущее письмо использовало палец, который был слишком близок, сложно. Например, XQ трудно напечатать, потому что моя рука должна двигаться вверх, чтобы обрабатывать соседние пальцы, необходимые для их ввода. Но я не нахожу BQ трудно набирать вообще, потому что, пока мой указательный палец все еще работает над B, мой мизинец может отправиться в Q.

Также намного проще печатать AW, чем QS, потому что безымянный палец длиннее и поэтому естественно вписывается в W, в то время как мизинец находится на A, находясь в положении покоя, в то время как QS требует растяжки розового и одновременный, конфликтный мускульный хруст безымянного пальца.

Если вы начнете создавать карту каждой буквы друг против друга, вы скоро найдете разумный способ представить различные аспекты легкости или сложности. Обобщая мой пример XQ/BQ, вы можете сделать однострочные изменения, требующие расстояния в 2 или более пальцев, для двухстрочных изменений требуется расстояние в 3 пальца, а 3-рядные изменения (цифры, возможно) требуют альтернативных рук.

Я также замечаю, что немного более длинное расстояние между WD и IL, чем SE и KO, также меняет сложность из-за слегка зазубренного размещения ключей.

С некоторым анализом (я рекомендую использовать Excel для "наброски" сложности ввода). Я уверен, что вы можете придумать алгоритм, который поможет вам создавать простые слова.

Если возможно, попробуйте указать хотя бы одно число и подумайте об использовании пробелов.

Ответ 8

Если вы реализуете это, учитывайте учетную запись пользователя при определении "стоимости" перехода от одного символа к другому. Простой в использовании пароль может стать довольно громоздким, если пользователь использует разную раскладку клавиатуры. Некоторые клавиши, которые могут быть легко доступны на одной языковой клавиатуре, могут быть недоступны на другой языковой клавиатуре, не требуя дополнительных клавиш модификатора (shift, meta и т.д.).

Чтобы сохранить эту идею универсальной, я бы рекомендовал игнорировать, какой символ принадлежит какому ключу, и вместо этого рассматривать ключи как массив со строками и столбцами. Каждая строка обычно смещается от предыдущего примерно на 1/3 ширины ключа. Имея это в виду, нетрудно вычислить расстояние между любыми двумя произвольными клавишами:

# Key at top left corner is {0, 0}
key1 @ {x1, y1}
key2 @ {x2, y2}

xdistance = absolute_value(x2 - x1)
ydistance = absolute_value(y2 - y1)

if y1 > y2
  xdistance += (1/3 * ydistance)
else
  xdistance -= (1/3 * ydistance)

total_distance = square_root(xdistance^2 + ydistance^2)

Создайте серию ключевых позиций, соответствующих вашей длине и требованиям "простоты ввода", затем используйте текущую раскладку для пользователя, чтобы перекрасить эти индексы в символы.