guyblade.com #/


PSN
Gamercard


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

Front Page

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