乱数と暗号技術について

最近、乱数について学び、奥が深くて面白いなと感じたので、その内容を簡単にまとめてみました。

ざっくり今回の内容#

• 乱数と擬似乱数
• 暗号技術における乱数
• JavaScriptで乱数を予測してみる

難しい計算とか無理なので、専門的な内容とかはないです…

乱数とは？#

日常での使用例#

• サイコロ
• ゲームの確率系
• パスワード生成
• 音楽アプリのシャッフル再生

暗号技術での使用例#

• 鍵の生成
• 初期化ベクトル（IV）の生成
  • ブロック暗号の安全性を高めるために使用されるランダムな値
• ソルトの生成
  • パスワードのハッシュ化において、同じパスワードでも異なるハッシュ値を生成するためにパスワードの前後に追加されるランダムな値

乱数は、日常生活の中でもよく登場しますが、特に暗号技術においては、セキュリティを確保するために非常に重要な役割を果たしているっぽい。

乱数の性質#

乱数には3つの性質があり、下に行けばいくほど、より見破られにくい乱数になります。

以上の性質を踏まえると、セキュリティが無視できない暗号技術にとって、攻撃者に見破られないために、少なくとも「予測不可能性」が必要。

疑似乱数生成器#

ソフトウェアでは、「再現不可能性」を持った乱数を生成することはできませんが、「無作為性」「予測不可能性」を持った乱数を生成することは可能です。

そのために使われるのが疑似乱数生成器です。

真の乱数ではないので、「疑似」とついてる。

特徴#

• 外部から与えられたシード値（初期値）を元に乱数を生成する
  • ゲームのマイクラで使われてるシード値なんかもこれ
  • つまり、同じシード値を与えれば、同じ乱数列が生成される

擬似乱数生成器の種類#

• 一般的生成法
  • 方式と過去の出力が既知であれば、未来の出力を予測可能
    • 線形合同法
    • メルセンヌ・ツイスタ
• 暗号学的に安全な生成法
  • 方式と過去の出力から未来の出力が予測困難で、現在の状態から過去の出力が予測不可能
    • BBS（Blum-Blum-Shub）
    • Fortuna

「一般的生成法」は未来の出力を予測可能なので、暗号技術には向きません。

反対に、「暗号学的に安全な生成法」は未来の出力を予測できないため、暗号技術に向いています。

JavaScriptで体験#

JavaScriptでもMath.random()を使って手軽に疑似乱数を生成することができます。

• シード値は実装側によって決定される（ブラウザ、OSなどに左右される）
• 内部的にXorshiftというアルゴリズムを使用しているらしい

だたこれは、暗号技術には向いていません。

Math.random() - JavaScript | MDN

Math.random() は静的メソッドで、 0 以上 1 未満の範囲で浮動小数点の擬似乱数を返します。その範囲ではほぼ均一な分布で、ユーザーは必要なだけ範囲の拡大をすることができます。実装側で乱数生成アルゴリズムの初期シードを選択します。ユーザーが初期シードを選択、またはリセットすることは出来ません。

developer.mozilla.org

Math.random()の提供する乱数は、暗号に使用可能な安全性を備えていません。セキュリティに関連する目的では使用しないでください。代わりにウェブ暗号API(より具体的にはCrypto.getRandomValues()メソッド)を使用してください。

実際に予測してみる#

※実行にはNode.jsが必要です。

ChromeのDevToolsで以下のコードを実行してみてください。

console.log(
  `${Math.random()} ${Math.random()} ${Math.random()} ${Math.random()}`,
);

今回はjs-randomness-predictorというnpmパッケージを使って、4つの疑似乱数から今後出力される疑似乱数を予測してみます。

# パッケージインストール
npm i js-randomness-predictor

# 予測する
npx js-randomness-predictor --environment chrome --sequence { 先ほどChromeで取得した疑似乱数をコピー } --predictions 10

# ↓↓example
# npx js-randomness-predictor --environment chrome --sequence 0.8718005396476145 0.26303525384344595 0.3715591148468824 0.44276922059614887 --predictions 10

# output
{
  "sequence": [
    0.8718005396476145,
    0.26303525384344595,
    0.3715591148468824,
    0.44276922059614887
  ],
  "predictions": [
    0.8105094289543446,
    0.8860500291642275,
    0.25891941035157573,
    0.9230800032711288,
    0.6285448143870935,
    0.19971853472507917,
    0.8994670461609209,
    0.4106324596739902,
    0.236143314832427,
    0.6046395076652631
  ],
  "actual": "You'll need to get this yourself via the same way you generated the sequence"
}

そして、ChromeのDevToolsで先程の続きから、以下のコードを実行して、予測した乱数（predictions）と出力された乱数が一致するか確認してみてください。

Array.from({ length: 10 }, Math.random);

// => (10)[..., ..., ...]

10個の乱数が予測通りに出力されるはずです。

つまり、過去の出力（4個）から未来の出力（10個）を予測できてしまったというわけです😱

すごい…

公式にも記載がある通り、以下のようなセキュリティに関する乱数の生成や鍵の生成には暗号強度の強い専用のメソッドを使用するようにしましょう。

• getRandomValues()
• generateKey()

気をつけること#

シード値#

ここまで、乱数・擬似乱数、暗号技術に適した乱数の性質について解説してきましたが、実際に疑似乱数を使う際、シード値には特に注意が必要です。

暗号化の鍵などを生成するために乱数を使用するわけですが、シード値が攻撃者に知られてしまうと、生成される乱数も予測可能になってしまいます。

結局、疑似乱数を使っても守るべきものは、存在するというわけです…

ただ、このシード値を「再現不可能性」を持つ乱数にするなど、工夫することで、より安全に疑似乱数を使用することができます。

擬似乱数生成器は実装しない#

疑似乱数生成器の実装は、複雑な計算が必要です。

特にセキュリティに関わる乱数生成器には、単にでたらめな数列を作るだけでなく、攻撃者によるあらゆる予測を阻止するための数学的な厳密さが求められます。

もし、独自実装した場合、一見ランダムに見える数列でも、実はパターンや偏りがあるといった致命的な欠陥が隠れている可能性が大いにあります。

そのため、セキュリティに関する専門家でないのなら、先人たちの知恵と長年の研究によって開発され、世界中の専門家によって徹底的に検証された信頼性の高いライブラリを使用することが、最も賢明な選択です。