guyblade.com #/


PSN
Gamercard


2011 Jan 08 emeralda


Guy Blade Guy Blade---23:11:00


Password Quality
Earlier this week, I did some calculations on the number of unique passcodes possible using Android's matrix login. In the comments to that post, I mentioned that I thought there were very, very few such passwords that were symmetric, but failed to quantify now few that was. locallunatic took a couple of stabs at it before giving up, but I spent some time this morning working my way through it.

So, what I'm looking for precisely are any passwords in which are symmetric about the center up-down axis. For instance, the password "1 8 3" would be symmetric.

To that end, there are several classes of such passwords that will make counting easier:

Trivial Passswords: the single digit passwords "2", "5", and "8". 3 Total

Passwords with 2+ digits all on the central axis:
Example "2, 5". There are 2 possible length 2 passwords and 2 possible directions (up to down and down to up) and 1 possible length 3 password with 2 possible directions.

2 * 2 * 2 + 1 * 2 = 10 Total

Passwords of form 'stuff in column 1, a digit in column 2, and the reverse of column 1 in column 3':

Passwords of this form are all odd in length and can further be subdivided based on total password length.

Length 3: Passwords with one digit on the left, a center digit, and the compliment.

There are three left digits to choose from, then three digits to choose from for the center and one for the final column. Also, since passwords going left to right and passwords going right to left are unique in the password quality, we double the total number of choices.

Therefore 3 * 3 * 2 = 18 Total .

Length 5: Passwords with a two-digit sequence in column one, a center digit and the inverse of the sequence in column three. Example: "1 4 9 6 3". There are two possible two digit cominations. Each combination can be oriented either up or down. There are still three choices for the center digit and two possible directions.

So, 2 * 2 * 3 * 2 = 24 Total

Length 7: Passwords with a three-digit sequence in column one, a center digit, and the inverse in the last column. There is one possible choice of numbers, but two up-down orderings and two left-right orderings.

Thus, 2 * 3 * 2 = 12 Total

Add up all of these and you get the total number of possible passwords: 67


===

Incidentally, I believe my earlier calculation is probably incorrect as it doesn't count passwords like "2 1 3" which is valid, but not envisioned by my previous program. This will increase the count somewhat, but I've not yet run the calculation.

Published by XPostGTK+


Permalink to this post     Com/0


2011 Jan 06 aya


Guy Blade Guy Blade---03:56:00


Password Quality
A while back, my old n900 was stolen, so I replaced it by getting a T-Mobile G2 phone. It is rather nice and so far I've been rather happy with it.

Like most Android phones, it allows the use of a 3 by 3 grid on which you can draw and connect symbols.

Someone else's phone showing the logon matrix:


This lets you pick any of the nine points as a start and then connect any number of points, no more than once each, to produce a sort of visual password.

Now, I was wondering this morning, while half awake, how many unique passwords this produces. The trick is that not all possible combinations are valid. For instance, if a password begins in the upper left hand corner, it cannot have the upper right hand corner as its next "digit". Instead, it must first pass through the upper center orb. With no more than 9 possible digits, it seemed like it would be easy to calculate the number of unique combinations recursively, so I did:


(define max-passwords
(lambda ()
(letrec
((in-list
(lambda (val lst)
(cond
((eq? lst '()) #f)
((eq? (car lst) val) #t)
(else (in-list val (cdr lst))))))
(ok-vals
(lambda (num)
(cond
((eq? num 1) (list 2 4 5 6 8))
((eq? num 2) (list 1 3 4 5 6 7 9))
((eq? num 3) (list 2 4 5 6 8))
((eq? num 4) (list 1 2 3 5 7 8 9))
((eq? num 5) (list 1 2 3 4 6 7 8 9))
((eq? num 6) (list 1 2 3 5 7 8 9))
((eq? num 7) (list 2 4 5 6 8))
((eq? num 8) (list 1 3 4 5 6 7 9))
((eq? num 9) (list 2 4 5 6 8)))))
(valid-sucs
(lambda (ok used)
(begin
;(display (reverse used))
;(newline)
(+ 1 (apply +
(map
(lambda (x)
(if (in-list x used) 0
(valid-sucs (ok-vals x) (cons x used))))
ok)))))))
(apply +
(map
(lambda (x)
(valid-sucs (ok-vals x) (list x)))
(list 1 2 3 4 5 6 7 8 9))))))



Turns out that if you run this, you end up with 140,249 unique passwords of any length (1 to 9 orbs).

I also calculated what it would be if you could go from (say) upper left to upper right without being forced to go through the center and found that it was 986,409 possible passwords of any length (1 to 9 orbs).

Published by XPostGTK+


Permalink to this post     Com/0

Archive
Copyright 2002-2024 Blade Libergnosis//Powered By Blogger