【Python】AtCoder Beginner Contest 029 A,C問題 解答・解説

この記事は約2分で読めます。

A問題 複数形

 

C問題 Brute-force Attack

方針

パスワードの元となる文字列a,b,cがあります。

この3つの文字列を、1~8の数だけ組み合わせた文字列(パスワード)として、辞書順に出力する問題です。

itertools.productを使って直積を求めます。

iterttols.product(S,repeat=n)とすることで、S内の文字列を使った長さnのパスワードの組み合わせを作ることができます。

※S=[‘a’,’b’,’c’] Sにはパスワードの元なる文字列abcが入っています。

解答

 

(余談)

パスワードの全ての組み合わせを出力できたので、はじめから順番に試していけばパスワードを解除することができるのだと思います。

パスワードに使われる文字列の種類、パスワードの長さ等、パスワードの条件を全て知ることができれば、

私たちにもブルートフォースアタック(パスワードの総当たり攻撃)をするためのプログラムを作ることができるのかもしれません。

実際には桁数や文字列の種類が増えるほど解析に時間がかかるようですが。

今回はパスワードのもととなる文字列はabcの3つでした。

パスワードが8桁の場合、3の8乗の6561通りとなりますが、これはすぐに突破できてしまいそうです。

ためしにパスワードのもととなる文字列をabcdの4種類にしてみた場合、4の8乗の65536通りとなります。

文字列はabcのままで、パスワードの桁を9桁にした場合、3の9乗となるので19683通りとなりました。

パスワードのもととなる文字列と、桁数はどちらも多い方が良いに越したことはないと思います。その方が解析に時間がかかるので。

ただ、今回に限っては桁数を8から9に増やすよりも元の文字列を3種類から4種類に増やした方が組み合わせの数が増えました。

パスワードを決める際、アルファベット(小文字・大文字)、数字、記号を組み合わせて使用するのは、その方が組み合わせの数を大きく増やせるからなのかなと思いました。

参考

組み合わせ、順列、直積について

【Python】itertoolsモジュールを用いた組み合わせパターンの生成 | Hbk project (hibiki-press.tech)

直積の作り方(itertools.productの使い方)

Pythonで複数のリストの直積(デカルト積)を生成するitertools.product | note.nkmk.me

コメント