Javaで乱数を生成する(4)

Javaで乱数を生成する」というタイトルだが、生成できるのは疑似乱数。疑似乱数生成器の動作概要については「Javaで乱数を生成する(1)」に説明した。また、Javaでどのように実装するかについて「Javaで乱数を生成する(2)」に説明した。「Javaで乱数を生成する(3)」でTomcatのソースを読む準備をして、いよいよ疑似乱数の生成方法を教えてもらうことに。
なお、本エントリのソースコードは、全てApache Tomcat 7.0.5の“org.apache.catalina.session.ManagerBase”クラスと“org.apache.tomcat.jni.OS”クラスから引用*1している。


Tomcatでは、セッション管理を行うための“org.apache.catalina.Manager”インターフェースが用意されている。実際に、通常のセッション管理を行うマネージャや、クラスタ用のセッション管理を行うマネージャが実装されている。これらに共通の処理を“org.apache.catalina.session.ManagerBase”という抽象クラスに持たせている。よくあるパターン。疑似乱数(セッションID)の生成は、このManagerBaseクラスに実装されている。

セッションIDを生成するメソッドは、ずばりManagerBase#generateSessionIdメソッドだ。このメソッドでは、次のような3つの処理を実行している。

  1. getRandomBytesメソッドにより、疑似乱数を生成する
  2. 疑似乱数のメッセージダイジェストを取得する(一方向ハッシュ演算を行う)
  3. 得られたバイト列を、英数字の文字列に変換する

大事なのは、1つ目の処理。
2つ目の処理は、疑似乱数生成器としてSecureRandomクラスが使えず、Randomクラスを用いなければならない場合(後述する)のためにあるのではないか。3つ目の処理は、次のロジックで、バイト配列を文字列にしているだけだ。なるほど。

   for (int j = 0;
   j < random.length && resultLenBytes < this.sessionIdLength;
   j++) {
       byte b1 = (byte) ((random[j] & 0xf0) >> 4);
       byte b2 = (byte) (random[j] & 0x0f);
       if (b1 < 10)
           buffer.append((char) ('0' + b1));
       else
           buffer.append((char) ('A' + (b1 - 10)));
       if (b2 < 10)
           buffer.append((char) ('0' + b2));
       else
           buffer.append((char) ('A' + (b2 - 10)));
       resultLenBytes++;
   }

戻って、大事なのはgetRandomBytesメソッド。ここで疑似乱数を生成している。このメソッドでは、次のようにして疑似乱数を生成している。

  1. “ランダムインプットストリーム”が使えたら、そのストリームを用いて疑似乱数を生成する
  2. 使えなければ、疑似乱数生成器を用いて疑似乱数を生成する

ここで“ランダムインプットストリーム”の実体は、/dev/urandomファイルのFileInputStreamオブジェクトである。つまり、/dev/urandomファイルが使える場合には、そこから疑似乱数を用いるという寸法だ。/dev/urandomファイルについては、次を参照のこと。
http://linuxjm.sourceforge.jp/html/LDP_man-pages/man4/random.4.html


要は、デバイスドライバなど、OSレベルのノイズ*2をためておく特別なファイル(エントロピープール)から、そのままひっぱってくるということだ。そりゃJavaでやるよりノイズが大きいもんな。
Windows系のOSのように、/dev/urandomファイルが使えない場合は、(初回のみ)疑似乱数生成器をcreateRandomメソッドにて生成し、以降はその生成器を用いる。
おっ、どうやるんだ?
createRandomメソッドと、関連するインスタンス変数は、次のように実装されている(ログ出力のロジックを除いた)。

    /**
     * Random number generator used to see @{link {@link #randoms}.
     */
    protected SecureRandom randomSeed = null;

    /**
     * The Java class name of the random number generator class to be used
     * when generating session identifiers. The random number generator(s) will
     * always be seeded from a SecureRandom instance.
     */
    protected String randomClass = "java.security.SecureRandom";

    /**
     * Create a new random number generator instance we should use for
     * generating session identifiers.
     */
    protected Random createRandom() {
        if (randomSeed == null) {
            createRandomSeed();
        }
        
        Random result = null;
        
        try {
            // Construct and seed a new random number generator
            Class<?> clazz = Class.forName(randomClass);
            result = (Random) clazz.newInstance();
        } catch (Exception e) {
            // Fall back to the simple case
            result = new java.util.Random();
        }
        byte[] seedBytes = randomSeed.generateSeed(64);
        ByteArrayInputStream bais = new ByteArrayInputStream(seedBytes);
        DataInputStream dis = new DataInputStream(bais);
        for (int i = 0; i < 8; i++) {
            try {
                result.setSeed(dis.readLong());
            } catch (IOException e) {
                // Should never happen
            }
        }
        return result;
    }

メインの疑似乱数生成器(result)は、リフレクションを用いて、SecureRandomクラスをインスタンス化しようとしている。SecureRandomクラスが使えない場合には、Randomクラスを用いている。で、頭のcreateRandomSeedメソッドにて、シードを生成するための疑似乱数生成器(randomSeed)を作成し、シードを生成し、疑似乱数生成器(result)を初期化している。
では、どうやってシードを生成するための疑似乱数生成器(randomSeed)を作成するのか。いよいよ核心に。
createRandomSeedメソッドは次のように実装されている(ログ出力のロジックを除いた)。

    /**
     * Create the random number generator that will be used to seed the random
     * number generators that will create session IDs. 
     */
    protected synchronized void createRandomSeed() {
        if (randomSeed != null) {
            return;
        }

        long seed = System.currentTimeMillis();
        char entropy[] = getEntropy().toCharArray();
        for (int i = 0; i < entropy.length; i++) {
            long update = ((byte) entropy[i]) << ((i % 8) * 8);
            seed ^= update;
        }

        // Construct and seed a new random number generator
        SecureRandom result = new SecureRandom();
        result.setSeed(seed);

        randomSeed = result;
    }

おぉ。シードの元ネタは、現在時刻だ。これで確実に毎回違ったシードになる。そこに、getEntropyメソッドでエントロピー(ノイズ)を取得して、XOR演算している。なるほど。
では、どうやってエントロピーを取得しているのか。
getEntropyメソッドを見ると、org.apache.tomcat.jni.OS#randomメソッドを呼び出している。このメソッドは、次のようにJNIの仕組みを使って呼び出されている。

    /**
     * Generate random bytes.
     * @param buf Buffer to fill with random bytes
     * @param len Length of buffer in bytes
     */
    public static native int random(byte [] buf, int len);

APR(Apache Portable Runtime)を使っているのか。確かに、Tomcatのドキュメントに、次のようにある。

When APR is enabled, the following features are also enabled in Tomcat:

  • Secure session ID generation by default on all platforms (platforms other than Linux required random number generation using a configured entropy)
  • OS level statistics on memory usage and CPU usage by the Tomcat process are displayed by the status servlet
Apache Tomcat 7 (7.0.92) - Apache Portable Runtime (APR) based Native library for Tomcat

APRのソースを見てみると、エントロピー取得のロジックは、次の資料を参考にしているという。うーん、、また今度にしよう。しかし、Windows系OSのソースがないように見えるのだが。。
http://www.apache-ssl.org/randomness.pdf


これでもエントロピーが取得できない場合はどうするのか?いよいよ、最後の最後。
ソースコードを見ると、Managerインスタンスのハッシュコード(Object#hashCodeメソッドで得られる値)を用いている。。
言われてみれば、、そうだよな。Javaだけでは、この程度のエントロピーが精一杯ということか。


つまり、Tomcat先生によると、Javaだけを用いる場合には、次のように疑似乱数生成器をつくるということだ。

オブジェクトのハッシュコード”と“現在時刻”をXORした値をシードに、SecureRandomを初期化する。このSecureRandomから得られたバイト列をシードに、メインのSecureRandomを初期化する。

*1:一部、ログ出力のロジックを省略している箇所がある。

*2:割り込みの時間やプロセス切りかえの時間などかな?今日は調べられない。