なぜ6桁のパスワード設定で5種類の数を使うのが良いのか

皆さんはスマホの電源をつけてゾッとしたことはありませんか？

液晶を見てみると、うっすらと特定の場所に指紋がついているなんてことはありませんか？

その特定の場所というのは大抵、いつも使っているパスワードだったりします。

今回はパスワードの設定で、どのようなものが良いのかということについて考えてゆきたいと思います。

（このページを作ろうと考えたのは、Twitterで上載されていた謎解きが原因です）

実はスマホのロックによく使う6桁のパスワードは、「152349」のような6種類の数を使うよりも、「152345」のような5種類の数を使うほうが他人から当てられにくいということが数学的にわかっています。

それがなぜ良いのかということを、プログラムを書いたり、数式を書いたり、実際に列挙したりして説明してゆきます。

列挙してみる

説明しやすいので、まずは4桁のパスワードの設定について話します。

例えばクレジットカードの暗証番号はよく4桁のものが使われます。

試しに、店員が悪い人だとして、特殊な液体やらでクレジットカードを使う客が押下した番号がわかり、客は一度も間違えていないものだとします。

まず、4桁の場合で、店員が客の使っている番号が\(\{1,2,3,4\}\)​だということがわかった場合、考えられる番号は、

\(\begin{array}{l} 1234,1243,1324,1342,1423,1432, \\ 2134,2143,2314,2341,2413,2431, \\ 3124,3142,3214,3241,3412,3421, \\ 4123,4132,4213,4231,4312,4321 \end{array}\)

の24通りとなります。数式的に言えば​\(4!=24\)通りです。

ここで\(1213,4444\)​とかといった数字は、4種類の全ての数を使っていないので指紋が4箇所についているということに矛盾するので、省略できます。

では次に、客の使っている番号が​\(\{1,2,3\}\)だということがわかった場合では、

\( \begin{array}{l}1123,1132,1213,1223,1231,1232,\\1233,1312,1321,1322,1323,1332,\\2113,2123,2131,2132,2133,2213,\\2231,2311,2312,2313,2321,2331,\\3112,3121,3122,3123,3132,3211,\\3212,3213,3221,3231,3312,3321\end{array}\)

の36通りとなります。

実は3種類の数字を使ったほうが、満遍なく4種類を使うより、1.5倍も種類が多くなるのです。これで悪い店員を困らせる時間が少し増えます。

あまりありがたみを感じないかもしれませんが、これをスマホのパスワードなどで最近よく使われるようになった6桁でやってみれば、少しは納得具合が上がると思います。

6桁の場合は\(6!=720\)​通りであるのに対して、5桁の場合は

\(\begin{array}{l} 5^6\\-1^6\cdot{}_5{\rm C}_1\\-(2^6-1^6\cdot{}_2{\rm C}_1)\cdot{}_5{\rm C}_2\\-(3^6-1^6\cdot{}_3{\rm C}_1-(2^6-1^6\cdot{}_2{\rm C}_1)\cdot{}_3{\rm C}_2)\cdot{}_5{\rm C}_3\\-(4^6-1^6\cdot{}_4{\rm C}_1-(2^6-1^6\cdot{}_2{\rm C}_1)\cdot{}_4{\rm C}_2-(3^6-1^6\cdot{}_3{\rm C}_1-(2^6-1^6\cdot{}_2{\rm C}_1)\cdot{}_3{\rm C}_2)\cdot{}_4{\rm C}_3)\cdot{}_5{\rm C}_4)\\=1800\end{array}\)

通りとなり（この式の意味は後述）、今度は5種類の数を使ったほうが、満遍なく6種類を使うより、2.5倍も種類が多くなることがわかります。ただ列挙するとあまりにも多いので、書きません。

どうやって数え上げるか

先ほど読んでいただいた通り、6桁の場合は5種類の数を使うと1800通りというあまりにも多い数なので列挙して数えるなどということはできません。

正規表現で文字列置換を使う

私はvimを使っているのですが、便利な文字列置換という方法で数え上げることを最初に考えつきました。

まず、基本となるテーブルは面倒なのでPythonで作ります。この中には4種類以下しかないものがあったりするので後ほど消します。

with open('sample.txt', mode='w') as f:
    for i in range(5): # 最上桁
        for j in range(5):
            for k in range(5):
                for l in range(5):
                    for m in range(5):
                        for n in range(5): # 最下桁
                            f.write(f'{i}{j}{k}{l}{m}{n}\n')

これによって、以下のものが出来上がります。

000000
000001
000002
...
444443
444444

完成したsample.txtをvimで開いて次の文字列置換を行います。何気に面倒だった。

:%s/^1\+$//g
:%s/^2\+$//g
:%s/^3\+$//g
:%s/^4\+$//g
:%s/^5\+$//g




:%s/^[12]\+$//g
:%s/^[13]\+$//g
:%s/^[14]\+$//g
:%s/^[15]\+$//g
:%s/^[23]\+$//g
:%s/^[24]\+$//g
:%s/^[25]\+$//g
:%s/^[34]\+$//g
:%s/^[35]\+$//g
:%s/^[45]\+$//g




:%s/^[123]\+$//g
:%s/^[124]\+$//g
:%s/^[125]\+$//g
:%s/^[134]\+$//g
:%s/^[135]\+$//g
:%s/^[145]\+$//g
:%s/^[234]\+$//g
:%s/^[235]\+$//g
:%s/^[245]\+$//g
:%s/^[345]\+$//g




:%s/^[1234]\+$//g
:%s/^[1235]\+$//g
:%s/^[1245]\+$//g
:%s/^[1345]\+$//g
:%s/^[2345]\+$//g




:%s/^\n//g

これを実行するとsample.txtの行数が1800となり、確かに6桁で5種類の数を選ぶ場合では1800通りになることがわかります。

setの長さを使う

上記のプログラムを書いていたときに気づいたのですが、5種類しか使わないということをプログラム自体に書いてしまえば良いのでは？　ということになりました。

res = 0
for i in range(5): # 最上桁
    for j in range(5):
        for k in range(5):
            for l in range(5):
                for m in range(5):
                    for n in range(5): # 最下桁
                        if len({i,j,k,l,m,m}) == 5:
                            res += 1




print(res) # 1800

出力が汚くなるので、列挙はしません。

これを一般化すると、このようになります。

res = 0
p = 6 # パスワードの桁数
s = 5 # 種類数
query = '\n'.join([f'{" " * ix}for i{ix} in range(s):' for ix in range(p)])\
      +'\n'\
      + f'{" " * p}if len({{{",".join(map(lambda ix: f"i{ix}", range(p)))}}}) == s:'\
      + '\n'\
      + f'#{" " * (p + 1)}print({",".join(map(lambda ix: f"i{ix}", range(p)))})'\
      + '\n'\
      + f'{" " * (p + 1)}h += 1'
exec(query)
print(p, s, res)

これを見るととても気持ち悪いですが、for文を組み立てるにはこの方法しかないです……。

まあそれは嘘で、本当はitertoolsを使う方法があるけど（これに気づいたのは下にある数式を求めてからだった……）

import itertools
res = 0
p = 6
s = 5
for it in itertools.product(*[range(s) for _ in range(p)]):
     if len(set(it)) == s:
         #print(''.join(it)) # 候補となるパスワード
         res += 1
        
print(res) # 1800

数式を求める

上記は確かにちゃんと結果が出ますが、9桁（p=9）とかで試したい場合はめちゃくちゃ時間がかかるので嫌だ。

じゃあ、数式を求めてしまおう。そこからがすごく大変でした。

結果的には、このような数式で求められることがわかりました。

​\(p\)をパスワードの長さ、​\(s\)をパスワードの中で使われている文字の種類とすると

\(a_{p,s}= \begin{eqnarray} \left\{ \begin{array}{2} \displaystyle s^p-\sum_{i=1}^{s-1} {}_s{\rm C}_i a_{p,i} & (p\geq s\geq 2) \\ 1 & (p\geq s =1) \end{array} \right.\end{eqnarray}\)

これ自体は「正規表現で文字列置換を使う」を数式的に忠実に再現しています。

先ほどの例である、

\(\begin{array}{l} 5^6\\-1^6\cdot{}_5{\rm C}_1\\-(2^6-1^6\cdot{}_2{\rm C}_1)\cdot{}_5{\rm C}_2\\-(3^6-1^6\cdot{}_3{\rm C}_1-(2^6-1^6\cdot{}_2{\rm C}_1)\cdot{}_3{\rm C}_2)\cdot{}_5{\rm C}_3\\-(4^6-1^6\cdot{}_4{\rm C}_1-(2^6-1^6\cdot{}_2{\rm C}_1)\cdot{}_4{\rm C}_2-(3^6-1^6\cdot{}_3{\rm C}_1-(2^6-1^6\cdot{}_2{\rm C}_1)\cdot{}_3{\rm C}_2)\cdot{}_4{\rm C}_3)\cdot{}_5{\rm C}_4)\\=1800\end{array}\)

を掻い摘んで説明します。

まず、6桁のパスワードで1種類\(\{1\}\)の文字を使う場合のことを考えると、これは\(1\)通りということはすぐに出ると思います。

次に、6桁のパスワードで高々2種類​\(\{1,2\}\)の文字を使うことを考えます。この場合、すぐに​\(2^6\)通りであることがわかります。

しかしながら、求めたいのはちょうど2種類の文字を使う場合であり、ここには「111111」や「222222」が含まれているので、その分を引く必要があります。

ゆえに、\(2^6-1\cdot 2\)通りが答えになります。

次に、6種類のパスワードで高々3種類\(\{1,2,3\}\)​の文字を使うことを考えます。この場合、先ほどと同様に、​\(3^6\)通りであることがわかります。

しかしながら、求めたいのはちょうど3種類の文字を使う場合です。ここには「111111」「222222」「333333」ばかりでなく「111122」「212121」や「131113」「331333」、「233322」「323332」なども含まれています。

この場合、

\(\begin{array}{l}(ちょうど3種類の文字を使う場合)\\=(高々3種類の文字を使う場合)\\-(ちょうど2種類の文字\{1,2\}を使う場合)-(ちょうど2種類の文字\{1,3\}を使う場合)-(ちょうど2種類の文字\{2,3\}を使う場合)\\=(高々3種類の文字を使う場合)\\-(高々2種類の文字\{1,2\}を使う場合-高々1種類の文字\{1\}を使う場合-高々1種類の文字\{2\}を使う場合)\\-(高々2種類の文字\{1,3\}を使う場合-高々1種類の文字\{1\}を使う場合-高々1種類の文字\{3\}を使う場合)\\-(高々2種類の文字\{2,3\}を使う場合-高々1種類の文字\{2\}を使う場合-高々1種類の文字\{3\}を使う場合)\\=(高々3種類の文字を使う場合)-{}_3{\rm C}_2\cdot (高々2種類の文字を使う場合-{}_2{\rm C}_1\cdot 高々1種類の文字を使う場合)=3^6-{}_3{\rm C}_2\cdot (2^6-{}_2{\rm C}_1\cdot 1)\end{array}\)

となります。

これを4種類、5種類、6種類と繰り返し行ってゆくと、求めたい数式が出ます。

これをプログラムするとこのようになります。

from math import comb
def fn(p: int, s: int):
    return 1 if s == 1 else s ** p - sum(fn(p, _s) * comb(s, _s) for _s in range(1, s))

再帰的に書けばとても単純に表せました。

7桁以上の場合

他の桁数だとどうなるのか、プログラムを動かしてみればわかります。

この表を見てみると驚くことに、別に\((桁数-1)\)種類が最も多い組み合わせになるということではなさそうだということです。

例えば、7桁の場合は、最も多いのは5種類の数字を使う場合となっています。

私は数学科ではないので、別に証明するつもりはありませんが、ボリュームがどこになるのかというのはこの表を見たら少し気になりました（今回は割愛、あとで追記するかも）

結論

スマホのディスプレイはこまめにハンカチなどで拭きましょう。