👨🏾‍✈️ 🍂 🏴󠁧󠁢󠁥󠁮󠁧󠁿 グラフィックパスワードの脆弱性 🏟️ 🌚 😩

背景：私の妻は常に何らかの形で私を台無しにしようとします：午前3時にアラームを設定し、着信音を変更し、同期設定を破棄し、SMSを削除して、それを言わなかったことを証明します。

冗談として冗談を言っていましたが、ある時点で「もう十分だ」と決めました。そして、Androidにグラフィックパスワードを入力しました。

妻はにやにやして、それを拾うと言った。私はそれに応じて笑い、彼らは別れました。今だけ、彼女はどのように拾うかという問題を心配していましたが、このイベントの可能性は私にとって何ですか？

最初の論理的な考えは、組み合わせを計算する数学的な方法を考え出すことです。

初期条件を設定する必要があります。

方向が重要
各ポイントに到達できるのは1回だけです。
2つのポイントを接続するには、それらが直接見通し内にある必要があります。つまり、最初の指は2本目の指で接続できますが、3本目の指では接続できません。
ポイント数：5〜9。1回のストローク、1回の接続-ホップと呼びましょう。つまり、4から8ホップまで使用できます。

オプションを数学的に計算する試みは失敗しました。課された条件は、ルールを明らかにすることを許可しませんでした。

次のステップ：つぶします。何万ものオプションをすべて試したいと思っていたわけではありません。主なアイデアは、パターンを見つけることでした。

数時間かけて図を描きました。ただし、すべての法則は対称性に基づいており、すべての中間点（中央の点を除く）と同様に、すべてのコーナーポイントが同等であるという事実に基づいています。

しかし、困難が私たちを怖がらせたのはいつですか？

私は1ホップですべて同じように始めました。

1ホップ-蒸しカブより簡単-56オプション、

2ホップ-複雑なし-320オプション

3ホップ-一生懸命働かなければなりませんでした-1624オプション

4ホップ-いや、疲れた-7152オプション

5ホップ-ママミアと引き裂かれた髪-結果は不明です。

それから私は私の脳をレイプしないことを決め、長い間忘れられていたプログラミングを覚えています。

彼はターボパスカルを明らかにし、変数から塵を払い落とし、アルゴリズムの開発を始めました。

4年間の一時停止とbashでの簡単なスクリプトの後、プログラムをデバッグするのに一晩かかりました。アルゴリズムは約20分で生まれましたが。

コード自体

Program First;
Uses Crt;

VAR
i,j,k,cur_i,cur_j,hop_count:byte;
A:array[1..3,1..3] of byte;
Bom:Array[1..10000,1..5] of byte;
path_num,total,m,n:longint;


Procedure PATH(cur_i,cur_j:byte; k:byte);
VAR
i,j:byte;
m,n:integer;

begin

{We will calclate only path amount, but not detailed paths, because of
limitation to array size.
Actually you can make detailed path up to 5 hops. You just should uncomment
calculating of array 'Bom'}

A[cur_i,cur_j]:=1;
for i:=1 to 3 do
begin
    for j:=1 to 3 do
    begin

{        Bom[path_num,k]:=cur_i*10+cur_j;}
        if k<hop_count then
        begin

        {Checking possibility of doing next-hop}

             if (A[i,j]=0)and

             not(

             ((i=cur_i)and(abs(j-cur_j)>1)and(A[i,2]=0))
             or
             ((j=cur_j)and(abs(i-cur_i)>1)and(A[2,j]=0))
             or
             ( (abs(i-cur_i)>1) and (abs(j-cur_j)>1) and (A[2,2]=0))

             )
             then
                begin

                     {We will enlarge path number if hop amount in path is
                     qual to actual hop amount only}
                     if k=hop_count then
                     begin
                          path_num:=path_num+1;
{                          Bom[path_num,k+1]:=i*10+j;}
                     end;
                     A[i,j]:=1;
                     {Recursive running of path calculation}
                     PATH(i,j,k+1);
                     A[i,j]:=0;
                end;
        end
        else
        begin
             if (A[i,j]=0)and

             not(

             ((i=cur_i)and(abs(j-cur_j)>1)and(A[i,2]=0))
             or
             ((j=cur_j)and(abs(i-cur_i)>1)and(A[2,j]=0))
             or
             ( (abs(i-cur_i)>1) and (abs(j-cur_j)>1) and (A[2,2]=0))

             )
             then
             begin
             {Enlarge path number after exit out of procedure}
{                     Bom[path_num,k+1]:=i*10+j;}
                     path_num:=path_num+1;
             end;

        end;
    end;
end;
end;



begin

{A[x,y] - Array of 0 and 1.
0 - this point isn't in path yet. You can move here.
1 - this point is in path already. You can't move here.
}
ClrScr;
writeln ('Hello, Habrahabr. Let','''','s count amount of Android Graphical passwords.');
writeln;

i:=1;
j:=1;
k:=1;

for hop_count:=4 to 8 do
begin

     path_num:=1;
     for i:=1 to 3 do
         for j:=1 to 3 do
         begin
{            Bom[path_num,k]:=10*i+j;}

            PATH(i,j,k);
            a[i,j]:=0;
         end;
     writeln('Hops: ',hop_count,'. Path amount: ',path_num-1);
     total:=total+path_num-1;


end;

writeln('===========================');
writeln('Total amount:         ',total);


{Output of full list of paths.}

{for m:=1 to path_num do
begin
    write('Path ', m,': (');
    for n:=1 to hop_count+1 do
    begin
         write(Bom[m,n],' ');
    end;
    writeln(')');

    readln;
end;{}
readln;
end.

. , 1 4 , 8 — , .

64 . Byte . , 4 :

UPD. .

.

11-22-31-32-12:

, 389488 .

50% , , , (, ), 194744

20 , .

, 20/194744=,0001. , 0,01%. !

“-” — , . “-” — , .

グラフィックパスワードの脆弱性

More articles: