Mnemonic Password Generation Algorithm for QWERTY Keyboards?

You may wanna take a look at the principles used in the Dvorak keyboard.

You may wanna take a look at the principles used in the Dvorak keyboard, Those principles applied in a password-generating algorithm would be: Letters should be typed by altering hands. Use easy to type combinations. Take a look at the Dvorak layout and see the common digraphs and the positions of their letters.

Use only one letter from the bottom row, or not. Make it random! You can make the ratio 2 to 1 (2 letters typed by the right hand to 1 letter typed by the left hand).

Since the ratio is 2 to 1, you're gonna have 2 consecutive letters typed by the same hand so you're gonna have to make sure they are typed from the outside of the keyboard to the inside. This principle is applied to the digraphs. I know you said it's a QWERTY keyboard but using these principles on a QWERTY keyboard can give you some very good results, like: ktrd,ogkdo ("typewriter" in dvorak) kjg;g;akd;k (using only the home row) pjedoildupsk (just a random password following the principles) All Dvorak haters, shush it!

I hope this helps.

You suggestion is similar to the suggestion provided by @superUntitled, the problem with alternating hands is that I can only use "ae" or "uio" in my even letters (see my original function). How would you solve this? – Alix Axel Feb 13 '10 at 17:58 @Alix Axel: Well, my method is more flexible than that of @superUntitled because I'm suggesting you use a 2 to 1 ratio instead of 1 to 1, and it doesn't have to be exactly RRLRRLRRL, look at the random password sample, that follows my principles (not the vowels, though).

It's RRLLRRLRRLR which makes it possible to use any of the 5 vowels. – Leo Jweda Feb 13 '10 at 19:23 pjedoildupsk doesn't follow your guidelines. You and p are typed from the inside out by the right hand, as are o and i.

– ErikE Sep 8 '10 at 20:47.

Carpalx has a lot of research on calculating typing effort, which incorporates: finger travel distance hand, finger and row penalties stroke path The outcome of their research is the Colemak keyboard layout, which claims to be better than Dvorak. However, it's written backward from what you want - their goal is to find a better keyboard layout based on input, but you're trying to find easy input based on the keyboard layout. So - even though you might not be able to use it directly, I thought you might find it interesting (and who knows, if your Perl-fu is strong, you might be able to extract and reverse the algorithm, since it's GPL'd).

My Perl'fu isn't that strong, but I really appreciate the link, thanks, – Alix Axel Feb 10 '10 at 1:02 1 This answer is the only relevant answer based on some research. All the rest is just guesswork. Without an objective measure, "harder to type" just makes no sense and is very subjective.

– Vinko Vrsalovic Feb 13 '10 at 13:53 @Vinko. What are you talking about? This is probably the most irrelevant answer.

This answer answers a totally different question. So what if they did 'objective research' and determined an optimal keyboard layout based on some corpus of words? How does that help the questioner figure out how to generate passwords for better typing on a QWERTY keyboard?

– Aryabhatta Feb 13 '10 at 17:47 @Moron: I'm talking about that everybody is inventing heuristics without any research whatsoever, that is as good as (or even worse than) the original algorithm, we can never know because it's just guesswork without a background or even consensus about terms. This answer provides a framework to build on an actual solution, see mkweb.bcgsc. Ca/carpalx/?

Model_parameters and mkweb.bcgsc. Ca/carpalx/? Typing_effort.

That the model was used to derive a new layout doesn't mean is useless to find letter combinations that are less stressful on a fixed layout. – Vinko Vrsalovic Feb 13 '10 at 18:04 @Vinko: If you look at the link you described, they have no supporting data for the heuristic they chose and in fact they themselves say that some of the parameters are subjective. Determining the best heuristic is subjective (to the problem at hand(no pun intended)).

Any research you do won't change that fact. In fact the more research you do, the more irrelevant it might be to the OP. That said, I agree that the typing effort page should be useful and so is not irrelevant, but I don't see how this is more relevant than any other suggestion of a heuristic model.

– Aryabhatta Feb 13 '10 at 18:43.

You could eliminate all characters that are typed with the ring and pinky finger (q,w,x,z,p), then spit the characters that are typed by the left and the right hands and alternate between these letters.

1, That's a pretty good and easy to implement suggestion, thanks! – Alix Axel Feb 5 '10 at 17:47 I tried implementing this but I realized that by switching between the left and right finger keys my mnemonic function kinda loses the point, because I will only have either "ae" or "(y)uio" as vowels. – Alix Axel Feb 10 '10 at 3:09 randomly, bit with Also ensure your generated password have a 50/50 chance of starting either side (and consonant/vowel).

This will significantly reduce your vulnerability to brute force attacks. – ShuggyCoUk Feb 13 '10 at 18:05.

Perhaps you can use some heuristic to measure the 'ease of typing'. For instance, consider the cost of moving a finger when going to the next character. This can be a function of how far the finger needs to move, which direction etc.You could also add extra costs, when it is required to switch fingers, or hands.

After playing around with the costs a bit, you will probably hit upon a satisfactory solution. Hope that helps.

That is my idea, but I'm having trouble figuring out how I would implement such heuristics. – Alix Axel Feb 5 '10 at 17:42 Is the problem figuring out the weights or you actually have a problem writing code to figure out costs of moving etc? – Aryabhatta Feb 5 '10 at 17:46 @Moron: Figuring out the cost of moving from char to char + 1 is my main concern... – Alix Axel Feb 5 '10 at 17:50 One easy way is for every pair of letters you compute a cost. For instance (j,k) = 1, (j,l) = 2, (m,y) = 3 etc store that in a table, and just lookup.

For simplicity, you could lay out the characters on a grid and compute the manhattan distance for instance. – Aryabhatta Feb 5 '10 at 17:54 For every 26 letters, computing a pair cost would be pretty tedious to do manually. Can I speed up the generation of the lookup table automatically?

– Alix Axel Feb 5 '10 at 18:05.

Great question - taking the above suggestions, here's a formulae for the distance from key I to key j: Weight = distance * a + switch * be + same * c + shift * d + weird * e + start * f Distance is a value, the others are 0/1 values. Distance - get by superimposing a fine grid over a QWERTY keyboard, lookup the x,y and calculate the distance. Distance has a positive weight.

If the letter combination is with the use of different hands (e. G aj, sk, wu...), the distance is zero. Switch - negative weight; switching is good Same - aq, qa, az, za use the same finger.

Same is positive Shift - anything with a shift is positive and real bad Weird - I dunno $ or ~ is bad because you have to look at the keyboard. Start - asdfjkl starting or ending. Probably negative & good since your fingers are there at rest.

Coefficients - just make 'em up to start as long as the relative values seem reasonable. If you REALLY want to get fancy - get someone to type in several dozen sets of numbers, use a stop watch and fit a regression model. Implementation - say we have a six character password.

Now I need the lowest value for six characters starting with each letter. Imagine an array of your N keys in a columns. Now imagine six columns.

Your shortest password is the shortest path through the six columns (with cycles allowed). You might need to add some logic to eliminate cycles, but this should be a good first pass. (I'm getting lazy here - there's probably a graph theoretic formulation that handles this problem.) I'll bet someone has done this before - especially the keystroke part.

Build a data structure that represents a keyboard and codes the row, column, hand, and finger used to type each character. Write a function that, when presented with a character, provides a list of "easy to type next" characters, based on flexible rules that you develop. It could rely on another function that calculates the distance between keys.

Personally, I don't find typing letters with the same hand twice to be slow: only if a previous letter used a finger that was too close is it difficult. For example, XQ is hard to type because my hand has to move upward to handle the adjacent fingers required to type them. But I don't find BQ hard to type at all, because while my forefinger is still working on the B, my pinkie finger can head for the Q.It is also much easier to type AW than QS, because the ring finger is longer and so naturally fits on the W while the pinkie is on A, in a near-resting position, while QS requires a stretch of the pinkie and a simultaneous, conflicting muscular crunch of the ring finger.

If you start to build up a map of each letter against each other letter, you will soon find a reasonable way to represent various aspects of ease or difficulty. Generalizing my XQ/BQ example, you could make one-row changes require a distance of 2 or more fingers, 2-row changes require a distance of 3 fingers, and 3-row changes (numbers, perhaps) require alternate hands. I'm also noticing that the slightly longer distance between WD and IL than SE and KO also alters difficulty, because of the slightly jagged placement of keys.

With some analysis (I recommend using Excel to "map out" typing difficulty) I'm sure you can come up with an algorithm that helps you construct easy-to-type words. If possible, try throwing in at least one number, and consider using spaces as well.

If you implement this, please take the user's locale into account when determining the "cost" of moving from one character to another. An easy-to-type password might become rather cumbersome if the user is using a different keyboard layout. Some keys that might be easy to access on one language's keyboard might not be available on another language's keyboard without requiring extra modifier keys (shift, meta, etc).

To keep this idea universal, I would recommend ignoring what character belongs to what key and instead treating the keys as an array with rows and columns. Each row is typically offset from the previous by roughly 1/3 of a key width. With this in mind, it shouldn't be difficult to calculate the distance between any two arbitrary keys: # 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) Generate a series of key positions meeting your length and "ease of typing" requirements, then use the user's current keymap to re-map those indices into characters.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.