「パスワードを作る」(1993/12/22)
今回はどこに利用価値があるかわからないパスワード発生プログラムである。
実は某社内で開発要請されたが、開発終了前に中止を言い渡されたという
悲しいプログラムであった。(わずか20分で撤回するなよ。)
しかし、私はめげずにここに利用するのであった。
転んでもただでは起きないのである。
アルファベットだけで、その中に文字の重複のない5桁のパスワードを
250個発生する。
このプログラムには特に注目すべきような技術はない。
しかし、そこはかとなく有用かも知れない技術が入っているので、
それなりの人はそれなりに見ておくと勉強になるかも知れない。
今までのC言語講座では、ほとんどプログラムの紹介だけで済ませていたが、
今回はまじめにコメントを入れて説明している。
ということなので読むよろし。
なお、動作確認はDynaBook&MS−C(V5)で行っている。
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
/* 5桁英字パスワード発生プログラム */
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
#include <stdio.h>
#include <time.h>
#define rand2(seed) (rand()%(seed)) /* 0〜seed-1の乱数発生 */
#define AL 26 /* アルファベットの数:これを返ればAから
どこまで使うかを設定できるが、あまり意味はない */
#define PSMAX 250 /* 全件数:発生個数はここで調節する */
#define KETA 5 /* パスワード桁数:AL以下なら大丈夫 */
/* ハッシュ表ワークエリア */
#define HSIZE 1024
unsigned phash[HSIZE];
/* このあたりのハッシュ処理はちょっと技術の香りがしている。
ハッシュとは、高速検索に使われる、一種のポイントを高速に決める方法である。
ある引数に対してチェックサムを計算し、それを一定の大きさに調節して、
それを添え字とするハッシュテーブルにその引数の番号を入れる。
別の引数を与えたとき、そのチェックサムの示すテーブルの位置が
未使用の場合、重複するものはない。使用されている場合、重複する可能性がある
ので、そこに記録されている番号から以降で順次比較チェックをする必要がある。
結局、毎回全部チェックする必要がなくなるのと、比較するのが先頭からではなく、
途中からになるのでチェックが少なく高速化できる。
・・・というのは理想論である。
実際には要素数が少ないときは、ハッシュ計算による負担の方が大きくなって、
かえって遅くなるかもしれない。それに大きなワークエリアを必要とするのも
問題である。(今回のハッシュテーブルははっきりいってかなり無駄である。)
それに、250個程度では重複はほぼ0である。2500くらいにしても2つくらい
である。本来、もっともっと要素数が大きいときで、確実に速度負担が考えられる
ときに使うのがこのハッシュである。しかし、今回はあえて難しくするため、
じゃなくて、こういう簡単なときに使っておいて、技術を思い出しておこうという
ことで使ったのであった。
*/
init_hash()
/* ハッシュ初期化 */
/* ハッシュ表は使用前にいったん初期化しなければならない。
とはいえ、このプログラムは1回切り実行だし、グローバル変数でワークを
とっているので、自動的に0で初期化されているはずである。
従ってこの初期化は縁起ものということになる。
*/
{
int i;
for (i=0;i<HSIZE;i++) phash[i]=0;
}
unsigned set_hash(char pass[],int keta,int no)
/* ハッシュ表に登録 */
{
unsigned h;
/* calc hash */
/* ここでハッシュ値=チェックサムを計算する。
できるだけ重複がない値を発生するハッシュ計算式=ハッシュ関数が
望ましい。ここでは*11というオーソドックスなものを使った。
*/
do {
h+=((pass[--keta]-'A')*11);
} while (keta>0);
/* set hash */
h%=HSIZE; /* ハッシュテーブルに納まるように大きさを揃える */
/* ここでハッシュテーブルに登録する。
登録と同時に重複まである程度わかるという優れものである。*/
if (phash[h]==0) {
phash[h]=no;
return(0); /* 登録された=重複無し */
}
/* 登録されなかった=重複可能性あり */
return(phash[h]);
}
pass1(char pass[],int keta)
/* パスワード1つ作成 */
/* pass[]はketa+1用意すること */
{
int i;
char ms[AL];
/* まずアルファベットを順番に並べたものを作る */
for (i=0;i<AL;i++) ms[i]=i+'A';
/* それを入れ換える */
cshuffle(ms,AL,AL*2);
/* 入れ換えたものの先頭から必要個数を取り出す */
for (i=0;i<keta;i++) pass[i]=ms[i];
/* EOS = end of stringも忘れずに */
pass[i]=0;
}
srand2()
/* rand()乱数を初期化する */
{
time_t tm;
/* パソコン上の乱数というものはほとんど疑似乱数なので、
初期値が決まるとその系列が確定してしまう。すなわち、再現性のある
乱数なのである。(疑似でない乱数を得るにはハードの力が必要である。)
それはそれでしかたないのだが、ならば、その初期値をできるだけ
再現性なく与えてやりたい。そこでここでは時計の秒を使って
初期値を決めているのである。
*/
time(&tm); /* ここで秒を得ている */
tm&=0x0fff; /* それを一定の大きさにする */
tm*=16; /* それを16倍する。これは、初期値として1しか
違わないものは乱数系列も似てくる(らしい)ので、
1秒の違いを16の違いにしているのである。
なぜ16倍なのかというと、これは2の皆乗倍の方が
効率がいいというコンピューター的都合による */
srand(tm); /* その値を初期値として与える */
}
/* この関数は、その要素の内容をシャッフル=入れ替えするものである。
乱数によって適当な2つの要素を選び、それを入れ換える。
これを一定回数以上行えば十分に混ざったものが出来る。
この方法は無駄がなく、乱数で直接A〜Zを発生させるよりいい。
(乱数で直接発生させるとここでも重複の可能性がある。)
入れ換える回数は要素の数以上であればいいとされている。
*/
cshuffle(char ms[],int kazu,int times)
{
int i,a,b;
char c;
for (i=0;i<times;i++) { /* times=かき混ぜる回数 */
a=rand2(kazu); /* 2つの要素を乱数で決める */
b=rand2(kazu);
/* ここで要素を入れ換える */
c=ms[a];
ms[a]=ms[b];
ms[b]=c;
}
}
/* パスワード記録ワークエリア */
char ps[PSMAX][KETA+1]; /* +1 for EOS */
/* ここからがメインルーチン */
/* メインルーチンが一番終わりにあるというのは、
ハッシュ関数がint関数でないので、プロトタイプ宣言を兼ねているのである。 */
main()
{
int i,chou=0;
unsigned j;
char pass[KETA+1];
srand2(); /* 乱数初期化 */
init_hash(); /* ハッシュ初期化 */
for (i=0;i<PSMAX;i++) {
RE:;
/* パスワード1つ作成 */
pass1(pass,KETA);
/* ハッシュに登録 */
/* ハッシュ表は0で初期化している。
これに対し、番号は0から存在するので、番号+1として
記録するのである。 */
j=set_hash(pass,KETA,i+1);
/* 関数が0以外を返してきたときには重複の可能性がある */
if (j) { /* 重複の可能性あり */
/* 重複をチェック */
/* 重複してたら再発生 */
/* ハッシュに記録されている番号は+1されているので、
−1の位置から直前までの中で比較する。*/
for (--j;j<i;j++) {
if (strcmp(&ps[j][0],pass)==0) {
/* 一致するものがあれば再発生させる */
chou++; /* 一応重複回数も記録しておく*/
goto RE;
}
}
}
/* 重複がなければ記録 */
strcpy(&ps[i][0],pass);
/* ここでは結果は表示しかしないので、ファイルに落とす場合は
リダイレクトを使うこと */
printf("%s¥n",pass);
}
/* 重複回数はほとんど0のはず。1以上を見られたらラッキー! */
printf("重複回数:%d¥n",chou);
}
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
なぜこのようなプログラムが必要になったかと言えば、
某社ではパスワードをユーザーに決定させるのではなく、
情報システム部が作ってユーザーに渡す、という変なことをしていたからである。
その変更を定期的に行っていたわけであるが、考えてみればおかしな話である。
ユーザーがパスワードを忘れてもわかるという利点(?)はあったが、
悪用すれば情報システムが全員の何を読めると言うことであり、怖い。
まあ、全員分のパスワード変更をやってたというのは、それはそれで大変な手間
なので(全員分のIDと旧パスワードでログインし、変更するのだ)、
良くやっていたと言うべきか。
その後親会社からの通達で中止されたが、それまで数年やっていたということで、
そんな方法を考えた情報システム部長は、なかなかの大馬鹿者であった。
今はほされたけど。