📘

RSA暗号の仕組みとRustの実装

2024/07/21に公開

Rust

cryptography

rsa

tech

RSA暗号について

RSA暗号のセキュリティは、非常に大きな数を2つの素数に分解することが難しいという数学的な性質に基づいています。この記事ではRSA暗号の鍵生成、暗号化、復号化についての仕組みを理解し、その上でRSA暗号をRustで実装していきます。
流れは下記の通りです。

鍵生成について
暗号化と復号化のプロセス
復号化の数学的な説明
RustによるRSA暗号の実装

1. 鍵生成

RSA暗号の鍵生成プロセスは次のステップで行います：

1. 大きな素数の選択

セキュリティパラメータ k が与えられたとき、それに対応するサイズの2つの素数2 ( p ) と ( q ) をランダムに選ぶ

2. n の計算

$n = p * q$

3. $\phi(n)$ の計算

$\phi(n) = (p-1) * (q-1)$

4. 公開鍵 e の選択

1 < e < L の範囲で、e と L の最大公約数が1になるような e を選ぶ（素数を選ぶ）
上記 $n$ も同様に公開鍵になる。

5. 秘密鍵 d の計算

(実質的な秘密鍵は p と q だが復号には d があれば十分)

e \times d = 1 (\text{mod} \ L)

となる ( d ) を計算する。(d は e の逆元といえる。)

これは、 $e \times d = 1 + k \times \phi(n)$

となるような整数 ( k ) が存在することを意味する。なぜそのような k が存在するかというと、もし $11 ≡ 1 (\text{mod}5)$ だとすると
$11 = 1 + k \times 5$ といえる（この場合の k は2）。

鍵生成の例（通常はもっと大きい素数を使用します）

大きな素数の選択

$p = 61$
$q = 53$

n の計算
$n = 61 * 53 = 3233$
$\phi(n)$ の計算
$\phi(n) = (61-1) * (53-1) = 60 * 52 = 3120$
公開鍵 e の選択
$e = 17$
秘密鍵 d の計算
$d = 2753$

2. 暗号化と復号化のプロセス

暗号化

公開鍵 $(e, n)$ を使用してメッセージ $m$ を暗号化します。

メッセージ $m$ を $m \in \mathbb{Z}_n^*$ とします。
暗号化: $c = m^e \ (\text{mod} \ n)$

例：
- $m = 65$
- $e = 17$
- $n = 3233$
- 計算: $c = 65^{17} \ (\text{mod} \ 3233) = 2790$

復号化

秘密鍵 $(d, n)$ を使用して暗号文 $c$ を復号化します。

復号化: $m = c^d \ (\text{mod} \ n)$

例：
- $c = 2790$
- $d = 2753$
- $n = 3233$
- 計算: $m = 2790^{2753} \ (\text{mod} \ 3233) = 65$

3. 復号化の数学的な説明

復号化の式:
- $c = m^e \ (\text{mod} \ n)$
- $m = c^d \ (\text{mod} \ n)$
- $m = (m^e)^d \ (\text{mod} \ n)$
詳細な計算:
- $ed = 1 + k \times \phi(n)$ であるため(1.鍵生成の5.秘密鍵参照)、
- $m^{ed} \equiv m^{1 + k \times \phi(n)} \ (\text{mod} \ n)$
展開:
- これを展開すると、
  - $m^{1 + k \times \phi(n)} = m \times (m^{\phi(n)})^k$
オイラーの定理の利用:
- オイラーの定理によれば、 $m^{\phi(n)} \equiv 1 \ (\text{mod} \ n)$
- したがって、 $(m^{\phi(n)})^k \equiv 1^k \equiv 1 \ (\text{mod} \ n)$
最終的な復号化:
- $m \times 1 \equiv m \ (\text{mod} \ n)$

これにより、復号化後のメッセージは元のメッセージ $m$ と一致することが証明される

4. RustによるRSA暗号の実装

この例では、rsaクレートを使用してRSA暗号を実装します。

実装例
https://github.com/Mameta29/cryptography_learning/blob/main/src/main_encrypt.rs

1. プロジェクトの設定

まず、新しいRustプロジェクトを作成します。

cargo new rsa_example
cd rsa_example

次に、Cargo.tomlファイルに必要な依存関係を追加します。

[dependencies]
rsa = "0.5.0"
rand = "0.8.3"
base64 = "0.13.0"

2. 実装コード

src/main.rsファイルに以下のコードを追加します。

extern crate rsa;
extern crate rand;
extern crate base64;

use rsa::{PublicKey, RsaPrivateKey, RsaPublicKey, PaddingScheme};
use rand::rngs::OsRng;
use base64::{encode, decode};

fn main() {
    // 1. 鍵の生成
    let mut rng = OsRng;
    let bits = 2048;
    let private_key = RsaPrivateKey::new(&mut rng, bits).expect("Failed to generate a key");
    let public_key = RsaPublicKey::from(&private_key);

    // 公開鍵と秘密鍵を表示
    println!("Private Key: {:?}", private_key);
    println!("Public Key: {:?}", public_key);

    // 2. メッセージの暗号化
    let message = "Hello, RSA!";
    let encrypted_data = public_key.encrypt(
        &mut rng,
        PaddingScheme::new_pkcs1v15_encrypt(),
        &message.as_bytes(),
    ).expect("Failed to encrypt");
    
    // 暗号文をBase64でエンコードして表示
    let encoded_encrypted_data = encode(&encrypted_data);
    println!("Encrypted message: {}", encoded_encrypted_data);

    // 3. 暗号文の復号化
    let decoded_encrypted_data = decode(&encoded_encrypted_data).expect("Failed to decode base64");
    let decrypted_data = private_key.decrypt(
        PaddingScheme::new_pkcs1v15_encrypt(),
        &decoded_encrypted_data,
    ).expect("Failed to decrypt");
    
    // 復号化されたメッセージを表示
    let decrypted_message = String::from_utf8(decrypted_data).expect("Failed to convert to string");
    println!("Decrypted message: {}", decrypted_message);
}

コードの説明

1. 鍵の生成

RsaPrivateKey::newメソッドを使用して2048ビットのRSA鍵ペアを生成します。生成された公開鍵と秘密鍵を表示します。

let mut rng = OsRng;
let bits = 2048;
let private_key = RsaPrivateKey::new(&mut rng, bits).expect("Failed to generate a key");
let public_key = RsaPublicKey::from(&private_key);

2. メッセージの暗号化

公開鍵を使用してメッセージを暗号化します。暗号化されたデータはバイト配列として返されます。これをBase64エンコードして表示します。

let message = "Hello, RSA!";
let encrypted_data = public_key.encrypt(
    &mut rng,
    PaddingScheme::new_pkcs1v15_encrypt(),
    &message.as_bytes(),
).expect("Failed to encrypt");

let encoded_encrypted_data = encode(&encrypted_data);
println!("Encrypted message: {}", encoded_encrypted_data);

3. 暗号文の復号化

暗号文をBase64デコードし、秘密鍵を使用して復号化します。復号化されたデータはバイト配列として返されます。これを文字列に変換して表示します。

let decoded_encrypted_data = decode(&encoded_encrypted_data).expect("Failed to decode base64");
let decrypted_data = private_key.decrypt(
    PaddingScheme::new_pkcs1v15_encrypt(),
    &decoded_encrypted_data,
).expect("Failed to decrypt");

let decrypted_message = String::from_utf8(decrypted_data).expect("Failed to convert to string");
println!("Decrypted message: {}", decrypted_message);

実行方法

プロジェクトのディレクトリで以下のコマンドを実行して、プログラムをビルドおよび実行します。

cargo run

RSA鍵ペアの生成からメッセージを暗号化、復号化までrsaクレートを使用してサンプル実装しました。手元で動かしてみてください！

まとめ

最近暗号学に強くなりたいな〜と思い勉強のし直しです。コードはアルゴリズムを実装しているわけではないですが、やはり動かして実行結果をみるだけでも肌感理解できるのは大きいと思います。