Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

動的保証（全3回中2回）

あらゆるストリーム暗号と同様に、RC4はキーストリームを生成し、それを平文とビット単位でXORして暗号文を作成する必要があります。これが暗号化の仕組みです。

  • キーストリーム - 再現可能だがランダムと区別できないデータ。

  • 平文 - 暗号化されていないデータ。

  • 暗号文 - 暗号化されたデータ。

キーストリーム生成は、暗号状態を表すバッファを使って実装されます。 機械的には、RC4の暗号状態はsという名前の256バイト配列であり、iとjという2つの変数でインデックス付けされます。 最初のステップは、この絶えず変化する状態と、そのインデックスの現在値を格納する構造体を作成することです。 crypto_tool/rc4/src/lib.rsの先頭に以下を追加します。

#![cfg_attr(not(test), no_std)]
#![forbid(unsafe_code)]

#[derive(Debug)]
pub struct Rc4 {
    s: [u8; 256],
    i: u8,
    j: u8,
}

  • 最初の2行は属性です。これらはコンパイラとやり取りし、プロジェクトを設定します。

  • #![cfg_attr(not(test), no_std)]は条件付き属性です。クレート全体に適用され、testビルドでない限り、このライブラリは実行されるシステムについて何も仮定しないことをコンパイラに知らせます。

    • no_stdは、おおまかに「標準ライブラリやランタイムサポートが利用可能であることに依存しない」という意味です。これにより利用できるのはRustのコア機能の集合に制限されますが、ファームウェア、ブートローダー、カーネルなどの組み込みユースケース向けにコードをポータブルにできます。#![no_std]については第4章でより詳しく説明します。

  • #![forbid(unsafe_code)]は無条件属性です。これもクレート全体に適用され、ライブラリにunsafeコードブロックがないことを保証するようコンパイラに指示します。これにより、後でリファクタリングしたり新機能を追加したりしても、コードはRustのメモリ安全性保証を最大限に活用できます。

    • 本書全体を通じてunsafeについて説明しますが、メインプロジェクトではこのキーワードを使用しません。

  • #[derive(Debug)]は、トレイト（共有される振る舞いの定義。第3章で説明します）と呼ばれるもののためのderiveマクロです。マクロは追加のコードを生成します。マクロを書くことは高度なトピックですが、初心者でも既存のマクロを活用できます1。

    • #[derive(Debug)]がRc4構造体の上に置かれていることに注目してください。これはこの構造体にのみ適用され、その内容をコンソールにきれいに表示する方法をコンパイラに伝えます2。このマクロを使うことで、テストビルドでストリーム暗号を視覚的にデバッグしやすくなります。

  • Rc4構造体は、上記コードで最も重要な部分です。伝統的な意味でのオブジェクトではありませんが3、この構造体はプライベートデータをカプセル化し、次にそのデータを操作するメソッドを定義します。Rc4の3つのフィールドは次のとおりです。

    • s: 暗号状態。256バイトの配列（符号なし8ビット整数、したがってu8）。

    • i: キーストリーム生成のための「インクリメントされる」インデックス。

    • j: キーストリーム生成のための「ジャンプする」インデックス。

これで、RC4のロジックの2つの部分、KSAとPRGAを実装する準備が整いました。

警告！RC4は安全ではありません。

実際のプロジェクトでは、よく監査された、モダンで十分にテストされた暗号の実装を選択する必要があります。 この章の例としてRC4を選んだのは、実装が比較的簡単だからだということを忘れないでください。 RC4はプロフェッショナルなプロジェクトには適していません。

1. 鍵スケジューリングアルゴリズム（KSA）

RC4のKSAステップの目的は、可変長（40〜2,048ビット）の秘密鍵の影響を受ける置換を計算して、暗号状態配列を初期化することです。

このロジックはRc4のコンストラクタに置くのが最善です。 そうすれば、ライブラリのユーザーはデータを暗号化する前に特別な初期化関数を呼び出すことを覚えておく必要がありません。 コンストラクタから返される暗号インスタンスは、すでに初期化されています。

関数関連の用語

このセクションでは2つの専門用語を使用します。 これらの概念はRustに固有のものではありませんが、Rustプログラムでは用語に特定の意味があります:4

  • 関連関数: 構造体に定義されているが、最初のパラメータとして&self（構造体のインスタンスへの参照）を取らない関数です。構造体のフィールドを読み書きしません。

  • メソッド: 構造体に定義され、最初のパラメータとして&selfまたは&mut selfを取る関数です。構造体の特定のインスタンス上のフィールドを読み書きします。

慣例として、Rustのコンストラクタは、構築される構造体のインスタンスを返す、newという名前の関連関数（selfパラメータなし）です。

Rc4構造体定義のすぐ下に、KSAを実行するものを追加しましょう。 同じ名前の構造体に結び付けるために、impl Rc4ブロックの中でnewを定義していることに注目してください。

impl Rc4 {
    /// Init a new Rc4 stream cipher instance
    pub fn new(key: &[u8]) -> Self {
        // Verify valid key length (40 to 2048 bits)
        assert!(5 <= key.len() && key.len() <= 256);

        // Zero-init our struct
        let mut rc4 = Rc4 {
            s: [0; 256],
            i: 0,
            j: 0,
        };

        // Cipher state identity permutation
        for (i, b) in rc4.s.iter_mut().enumerate() {
            // s[i] = i
            *b = i as u8;
        }

        // Process for 256 iterations, get starting cipher state permutation
        let mut j: u8 = 0;
        for i in 0..256 {
            // j = (j + s[i] + key[i % key_len]) % 256
            j = j.wrapping_add(rc4.s[i]).wrapping_add(key[i % key.len()]);

            // Swap values of s[i] and s[j]
            rc4.s.swap(i, j as usize);
        }

        // Return our initialized Rc4
        rc4
    }
}

上記のコードを見ると、少し不安になるかもしれません。 それで大丈夫です。 新しい言語を学ぶということは、完全には理解していないコードに目を凝らすことを伴います。 そして、それはたいていあまり良い気分ではありません。

さらに悪いことに、暗号コードは、実装言語にかかわらず、それ自体が独特なものです。 踏み込んで、理解を試みましょう。

  • new は単一のパラメータ key を取ります。これはバイトスライスへの参照です。このシグネチャにより、鍵データの受け渡しが効率的5かつ柔軟6になります。スライスについては第3章で扱います。

  • 別のマクロである assert! 文は、API のユーザーが有効な長さの鍵を提供することを保証します。そうでない場合、プログラムはこの行で終了します。これはエラーを処理するには強硬な方法です。他の選択肢については後で説明します。

  • let mut rc4 = ... は、すべてのフィールドがゼロ初期化された Rc4 構造体の可変インスタンスを作成します。Rust では、変数はデフォルトで不変です。しかし、ここでは暗号の状態（s 配列）をセットアップするため、mut キーワードが必要です。

  • 次のコード片である for ループの恒等置換7は、s[0] = 0, s[1] = 1, s[2] = 2, ..., s[255] = 255 を設定する凝った書き方にすぎません。これはイテレータを使用しています。第10章で独自のイテレータを実装するので、今はこの構文について詳しく立ち入らないことにしましょう。

  • 続く for ループは、暗号状態 s をさらに置換します。指摘しておく価値のある詳細が3つあります。

    • 暗号コードでは、加算演算子（+）ではなく wrapping_add 関数を使用する必要があります。これは、整数オーバーフロー（第3章で説明します）によって剰余算術8を模倣したいからです。

    • 3つ目の変数（おそらく temp という名前）を使って2つの変数を入れ替えたことはありますか？答えが「うわ、何百回もあるよ」なら、Rust では swap が配列の組み込みメソッドであることのありがたみが分かるでしょう。

    • Rust では、インデックスは常にレジスタ幅の符号なし整数です。そのため、swap の呼び出しでは、as キーワードを使って j（取るに足らない u8）を usize に昇格させます。このちょっとした詳細は「安全なキャスト」9だと考えてください。

  • new 関数の最後の行は、初期化済みの Rc4 構造体インスタンスを返します。Rust の関数では、何らかの理由で早期に返したい場合（たとえば関数本体の途中）を除き、return キーワードは不要です。

    • 関数の戻り値の型（-> の直後に指定されているもの）は Self です。new は impl Rc4 ブロック内にあるため、これは Rc4 構造体のインスタンスを返すことの省略形です。

置換の1ラウンドを可視化すると、この概念がより具体的になるかもしれません。 各ループ反復で i と j が変化し（j は鍵の影響を受けます）、rc4.s.swap(i, j as usize) は s 内の2つの値を入れ替えるだけです。

s[i] と s[j] の入れ替えの可視化

2. 疑似乱数生成アルゴリズム（PRGA）

new 関数は Rc4 暗号のインスタンスを作成して初期化します。 キーストリームを生成するには、Rc4 インスタンスを使用する別の関数が必要です。 キーストリームが得られれば、それを使ってデータを暗号化できます。

prga_next はキーストリーム生成関数であり、呼び出されるたびに1バイトのキーストリームを出力します。 これを new 関数の直後、同じ impl Rc4 ブロック内に追加します。

new 関連関数とは異なり、prga_next はメソッドです。 メソッドは常に、呼び出し対象である構造体のインスタンス self への参照を第1パラメータとして取ります。

impl Rc4 {
    // ..new() の定義は省略..

    /// Output the next byte of the keystream
    pub fn prga_next(&mut self) -> u8 {
        // i = (i + 1) mod 256
        self.i = self.i.wrapping_add(1);

        // j = (j + s[i]) mod 256
        self.j = self.j.wrapping_add(self.s[self.i as usize]);

        // Swap values of s[i] and s[j]
        self.s.swap(self.i as usize, self.j as usize);

        // k = s[(s[i] + s[j]) mod 256]
        self.s[(self.s[self.i as usize].wrapping_add(self.s[self.j as usize])) as usize]
    }
}

この関数は new 関数と似た操作を行うため、詳細に見ていく必要はありません。 私たちが関心を持っているのは Rust の雰囲気をつかむことであり、RC4 の設計が要求する具体的な操作ではありません。 ただし、指摘しておく価値のある詳細が1つあります。

  • prga_next の唯一のパラメータは &mut self で、これは呼び出し対象となる Rc4 構造体への可変参照です。この関数は Rc4 構造体に変更を加えるため、ここでも mut キーワードが必要です。具体的には、インデックス i と j に書き込み、暗号状態バッファ s 内のバイトを入れ替えます。

余談ですが、k を出力するその行は、次のように可視化できます。10


k = s[(s[i] + s[j]) mod 256] の可視化

3. 暗号化/復号

古典的な柔軟なインターフェイス

各 prga_next 出力バイト（キーストリーム）を平文の各バイトと XOR することで、暗号化を実装します。 XOR は可逆なので、同じ関数は復号にも使えます！

impl Rc4 {
    // ..new() の定義は省略..

    /// Stateful, in-place en/decryption (current keystream XORed with data).
    /// Use if plaintext/ciphertext is transmitted in chunks.
    pub fn apply_keystream(&mut self, data: &mut [u8]) {
        for b_ptr in data {
            *b_ptr ^= self.prga_next();
        }
    }

    // ..prga_next() の定義は省略..
}

メソッド内で暗号化を実装すると、柔軟性が最大化されます。データを［長さが可変かもしれない］チャンクとして受け取る場合、Rc4 の単一インスタンスで、次のように複数のチャンクにまたがる「継続的な」暗号化を実行できます（以下は API 使用例であり、Rc4 実装の一部ではありません）。

let key = [0x1, 0x2, 0x3, 0x4, 0x5];

let msg_1 = [0x48, 0x65, 0x6c, 0x6c, 0x6f]; // "Hello"
let msg_2 = [0x20, 0x57, 0x6f, 0x72, 0x6c, 0x64, 0x21]; // " World!"

// インプレースで暗号化
let mut rc4 = Rc4::new(&key);
rc4.apply_keystream(&mut msg_1);
rc4.apply_keystream(&mut msg_2);

// インプレースで復号
let mut rc4 = Rc4::new(&key);
rc4.apply_keystream(&mut msg_1);
rc4.apply_keystream(&mut msg_2);

現実世界のストリーム暗号ライブラリの多くは、このような API を使用しています。 しかし、これには微妙な複雑さが伴います。rc4 は状態を持っており、復号の前に new で再構築しなければなりません。 さらに、apply_keystream へのパラメータの順序も重要です。上記で誤って rc4.apply_keystream(&mut msg_1) より前に rc4.apply_keystream(&mut msg_2) を呼び出すと、復号結果は不正になります。

一般的なケースをより簡単にする

すべてのデータが一度にメモリ上にある限り、関連関数内で暗号化を実装すると、より単純なインターフェイスを提供できます。 これはかなり頻繁に当てはまるかもしれません。 これは実際には、呼び出し元から状態を隠す単なるラッパーであることに注目してください。

impl Rc4 {
    // ..new() の定義は省略..

    // ..apply_keystream() の定義は省略..

    /// Stateless, in-place en/decryption (keystream XORed with data).
    /// Use if entire plaintext/ciphertext is in-memory at once.
    pub fn apply_keystream_static(key: &[u8], data: &mut [u8]) {
        let mut rc4 = Rc4::new(key);
        rc4.apply_keystream(data);
    }

    // ..prga_next() の定義は省略..
}

これで、Rc4 インスタンスの状態を気にすることなく、単一のメソッド呼び出しで暗号化/復号できます（API 使用例は以下のとおりです）。

let key = [0x1, 0x2, 0x3, 0x4, 0x5];

let msg = [
    0x48, 0x65, 0x6c, 0x6c, 0x6f, 0x20, 0x57, 0x6f,
    0x72, 0x6c, 0x64, 0x21,
]; // "Hello World!"

// インプレースで暗号化
Rc4::apply_keystream_static(&key, &mut msg);

// インプレースで復号
Rc4::apply_keystream_static(&key, &mut msg);

2つの暗号化/復号関数が完成したので、実装は完了しました。 検証の時間です。 暗号ソフトウェアは本当に正しくなければならないため、ここで止まることはできません。 このコードを徹底的に試してみましょう！

暗号化と復号は、どうして同じ操作になり得るのでしょうか？

要するに、XOR は可逆であり、かつキーストリームの性質により予測不能だからです。

  • まず、cipher_text = plain_text ^ key_stream（暗号化）です。

  • 次に、plain_text = cipher_text ^ key_stream（復号）です。

  • キーストリームは、平文内の任意のビットを、あたかも 50/50 のランダムな確率であるかのように反転できます。

より数学的に原理に基づいた扱いについては、Paar と Pelzl の Understanding Cryptography11 の 32 ページにある証明をおすすめします。 大学の教科書ではありますが、形式的な記述は軽量で正確です。 暗号学の分野への優れた入門書です。 さらに、この本には無料の動画講義12も付属しています。

  1. C のマクロとは異なり、Rust のマクロは衛生的です。つまり、識別子を捕捉して微妙な問題を引き起こすことはありません。これが、Rust のマクロが非常に使いやすい理由の一部です。実際、println! はマクロです。したがって、第1章の終わりで「Hello world!」プログラムを実行したとき、あなたはすでにマクロを使っていたことになります。 ↩

  2. トレイト std::fmt::Debug。The Rust Team（2022年アクセス）。 ↩

  3. Rust では、共有される振る舞いはオブジェクト指向の継承ではなく、トレイト合成によって定義されます。C++ や Java のような「クラス階層」はありません。トレイトについては第3章で扱います。 ↩

  4. 技術的には、Rust リファレンス13によると、「関連関数は型に関連付けられた関数」であり、「最初のパラメーターの名前が self である関連関数はメソッドと呼ばれます…」。しかし、それはかなり細部に踏み込んだ話です。このセクションでは明確さのために、関連関数とメソッドを別個のものとして扱います。 ↩

  5. スライス参照は「ファットポインター」（ポインターと要素数のタプル）であり、データをコピーせずに可変長データを渡すことを可能にします（ポインターについて最初に話したときの「参照渡し」を思い出してください）。 ↩

  6. スライスは柔軟です。なぜなら、異なる種類のコレクション（たとえば、固定長配列や動的サイズのベクター）をスライスを通して「見る」ことができるからです。そのため、慣用的な Rust コードではスライスによく出会うことになります。 ↩

  7. 単位元と逆元。Wikipedia（2022年アクセス）。 ↩

  8. 剰余算術。Wikipedia（2022年アクセス）。 ↩

  9. Rust のキャストにはベストプラクティスがあります。具体的には、型間の失敗しない変換にはトレイト From と Into を使い、失敗する可能性のある変換には TryFrom と TryInto を使います。このトピックについては後で詳しく説明します。 ↩

  10. RC4。Wikipedia（2022年アクセス）。 ↩

  11. [個人的なお気に入り] Understanding Cryptography。Christof Paar、Jan Pelzl（2009）。 ↩

  12. オンライン暗号学コース。Christof Paar、Jan Pelzl（2009）。 ↩

  13. The Rust Reference: 関連項目。The Rust Team（2021）。 ↩