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

Question

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

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?

Answer 1

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

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

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

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

ktrd, ogkdo ("машинка" в дворак)

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

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

Все двораки ненавистники, замолчи!

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

Answer 2

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

• расстояние перемещения пальца
• штрафы за руки, пальцы и ряды
• Путь инсульта

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

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

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

Answer 3

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

Answer 4

Возможно, вы можете использовать эвристику, чтобы измерить "простоту набора текста".

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

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

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

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

Answer 5

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

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

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

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

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

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

Сдвиг - все, что смещается, положительно и очень плохо

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

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

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

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

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

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

Answer 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[] = '!@#$%^&*()[]'; // 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));
?>

Answer 7

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

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

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

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

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

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

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

Answer 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)

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