pwgen のアルゴリズム

最近、パスワードを決める場面が増えています。パスワードを決めるというのはなかなか面倒な作業で、簡単でわかりやすくすれば他人に破られるし、かといって本当にランダムにすると自分が忘れてしまったりします。

そこで便利なのが pwgen です。 pwgen は Theodore Ts'o 氏が書いた「覚えやすい」パスワードを生成するプログラムです。しかし、覚えやすいパスワードなんてどうやって生成してるんでしょうか。

まずは行儀良く manpage を読んでみます。

NAME
       pwgen - generate pronounceable passwords

発音出来るものは覚えやすいというわけです。では、発音出来るパスワードをどう作るのでしょう。早速、ソースコードを読んでいきます。

ここでは pwgen-2.03 を対象にします。

pwgen のソースは 1 ファイルにほぼ 1 関数という、非常にこじんまりとした構造になっています。まずは pwgen.c の main 関数からたどっていきましょう。

int main(int argc, char **argv)
{
        int     term_width = 80;
        int     c, i;
        int     num_cols = -1;
        char    *buf, *tmp;
        void    (*pwgen)(char *inbuf, int size, int pw_flags);

        pwgen = pw_phonemes;

(中略)

        for (i=0; i < num_pw; i++) {
                pwgen(buf, pw_length, case_flag | numeric_flag);
                if (!do_columns || ((i % num_cols) == (num_cols-1)))
                        printf("%s\n", buf);
                else
                        printf("%s ", buf);
        }
        if ((num_cols > 1) && ((i % num_cols) != 0))
                fputc('\n', stdout);
        free(buf);
        return 0;
}

最後のループで関数ポインタが呼び出され、しかも初期値が pw_phonemes です。 phoneme(音素) といわれれば、これを読むしかないでしょう。

/*
 * pw_phonemes.c --- generate secure passwords using phoneme rules
 *
 * Copyright (C) 2001,2002 by Theodore Ts'o
 *
 * This file may be distributed under the terms of the GNU Public
 * License.
 */

#include <ctype.h>
#include <string.h>
#include "pwgen.h"

struct pw_element elements[] = {
        { "a",  VOWEL },
        { "ae", VOWEL | DIPTHONG },
        { "ah", VOWEL | DIPTHONG },
        { "ai", VOWEL | DIPTHONG },
        { "b",  CONSONANT },
        { "c",  CONSONANT },
        { "ch", CONSONANT | DIPTHONG },
        { "d",  CONSONANT },
        { "e",  VOWEL },
        { "ee", VOWEL | DIPTHONG },
        { "ei", VOWEL | DIPTHONG },
        { "f",  CONSONANT },
        { "g",  CONSONANT },
        { "gh", CONSONANT | DIPTHONG | NOT_FIRST },
        { "h",  CONSONANT },

(以下略)

テーブルを定義していますね。アルファベット1,2文字と、 VOWEL(母音)、 DIPTHONG(二重母音)、 CONSONANT(子音)、 NOT_FIRST といったフラグが延々と並んでいます。もうおおかた予測はつきますが、一応関数も読みます。

void pw_phonemes(char *buf, int size, int pw_flags)
{
        int             c, i, len, flags, feature_flags;
        int             prev, should_be, first;
        const char      *str;

try_again:
        feature_flags = pw_flags;
        c = 0;
        prev = 0;
        should_be = 0;
        first = 1;

        should_be = pw_random_number(2) ? VOWEL : CONSONANT;

        while (c < size) {
                i = pw_random_number(NUM_ELEMENTS);
                str = elements[i].str;
                len = strlen(str);
                flags = elements[i].flags;
                /* Filter on the basic type of the next element */
                if ((flags & should_be) == 0)
                        continue;
                /* Handle the NOT_FIRST flag */
                if (first && (flags & NOT_FIRST))
                        continue;
                /* Don't allow VOWEL followed a Vowel/Dipthong pair */
                if ((prev & VOWEL) && (flags & VOWEL) &&
                    (flags & DIPTHONG))
                        continue;
                /* Don't allow us to overflow the buffer */
                if (len > size-c)
                        continue;
                /*
                 * OK, we found an element which matches our criteria,
                 * let's do it!
                 */
                strcpy(buf+c, str);
		
                /* Handle PW_ONE_CASE */
                if (feature_flags & PW_ONE_CASE) {
                        if ((first || flags & CONSONANT) &&
                            (pw_random_number(10) < 3)) {
                                buf[c] = toupper(buf[c]);
                                feature_flags &= ~PW_ONE_CASE;
                        }
                }

                c += len;

                /* Time to stop? */
                if (c >= size)
                        break;

                /*
                 * Handle PW_ONE_NUMBER
                 */
                if (feature_flags & PW_ONE_NUMBER) {
                        if (!first && (pw_random_number(10) < 3)) {
                                buf[c++] = pw_random_number(10)+'0';
                                buf[c] = 0;
                                feature_flags &= ~PW_ONE_NUMBER;

                                first = 1;
                                prev = 0;
                                should_be = pw_random_number(2) ?
                                        VOWEL : CONSONANT;
                                continue;
                        }
                }

                /*
                 * OK, figure out what the next element should be
                 */
                if (should_be == CONSONANT) {
                        should_be = VOWEL;
                } else { /* should_be == VOWEL */
                        if ((prev & VOWEL) ||
                            (flags & DIPTHONG) ||
                            (pw_random_number(10) > 3))
                                should_be = CONSONANT;
                        else
                                should_be = VOWEL;
                }
                prev = flags;
                first = 0;
        }
        if (feature_flags & (PW_ONE_CASE | PW_ONE_NUMBER))
                goto try_again;
}

要求された文字数になるまで、struct pw_element elements[] から音節を選択し、つないでいくわけですね。音節の選択時にはフラグを参考に以下のような処理をしています。

いくつかの特定の音節(NOT_FIRST がたっているもの)は最初には選ばない。
母音のあとに、母音かつ二重母音は選ばない。
子音のあとは、母音を選ぶ。
母音のあとは、前回も母音か、今回が二重母音なら母音を選ぶ。それ以外では、ランダム 70% で子音、30% で母音を選ぶ。

あと、気になる goto 文は、ランダムにまぜるつもりだった大文字や数字をいれるまえに、文字数がいっぱいになったときに、やり直すのに使っています。