C++でRSA暗号アルゴリズムを実装する方法【サンプルコード付き】

RSAは、公開鍵（public key）と秘密鍵（private key）という2つの鍵を使い分ける非対称暗号アルゴリズムです。1977年にRivest、Shamir、Adlemanの3人によって考案され、現在でもSSL/TLSやデジタル署名など、幅広い分野で利用されている代表的な公開鍵暗号方式です。

この記事では、RSAの基本的な仕組みを理解するために、C++でシンプルなRSA暗号を実装する方法を手順とともに解説します。

RSAアルゴリズムの手順

RSAの鍵生成・暗号化・復号化は、以下の手順で行われます。

Begin
    1. 2つの素数 p と q を選ぶ。
    2. n = p × q を計算する。
    3. φ(n) = (p−1) × (q−1) を計算する。
    4. 1 < e < φ(n) かつ gcd(e, φ(n)) = 1 を満たす整数 e を選ぶ
       （つまり、e と φ(n) は互いに素）。
    5. d ≡ e⁻¹ (mod φ(n)) となる d を計算する。
       ここで d は、φ(n) を法とした e のモジュラ乗法逆元である。
    6. 暗号化：c = m^e mod n（m は元のメッセージ）。
    7. 復号化：m = c^d mod n。
End

C++での実装例

以下は、上記の手順をC++で実装したサンプルコードです。コメントも日本語で補足しています。

#include<iostream>
#include<math.h>
using namespace std;

// 最大公約数（gcd）を求める関数
int gcd(int a, int b) {
    int t;
    while(1) {
        t = a % b;
        if(t == 0)
            return b;
        a = b;
        b = t;
    }
}

int main() {
    // 2つの素数を選択
    double p = 13;
    double q = 11;
    double n = p * q;               // n を計算
    double track;
    double phi = (p - 1) * (q - 1); // φ(n) を計算

    // 公開鍵（e は encrypt の略）
    double e = 7;
    // 1 < e < φ(n) かつ gcd(e, φ(n)) = 1（互いに素）となることを確認
    while(e < phi) {
        track = gcd(e, phi);
        if(track == 1)
            break;
        else
            e++;
    }

    // 秘密鍵（d は decrypt の略）
    // d * e ≡ 1 (mod φ(n)) を満たす d を選択
    double d1 = 1 / e;
    double d = fmod(d1, phi);

    double message = 9;
    double c = pow(message, e);     // メッセージを暗号化
    double m = pow(c, d);           // 暗号文を復号化
    c = fmod(c, n);
    m = fmod(m, n);

    cout << "Original Message = " << message;
    cout << "\n" << "p = " << p;
    cout << "\n" << "q = " << q;
    cout << "\n" << "n = pq = " << n;
    cout << "\n" << "phi = " << phi;
    cout << "\n" << "e = " << e;
    cout << "\n" << "d = " << d;
    cout << "\n" << "Encrypted message = " << c;
    cout << "\n" << "Decrypted message = " << m;
    return 0;
}

実行結果

p = 13
q = 11
n = pq = 143
phi = 120
e = 7
d = 0.142857
Original Message = 9

Encrypted message = 48
Decrypted message = 9

コードのポイント

• gcd関数：ユークリッドの互除法により2つの整数の最大公約数を求めます。公開鍵 e と φ(n) が互いに素であることの確認に使用されます。
• 公開鍵 e の決定：e = 7 から開始し、gcd(e, φ(n)) = 1 となる値が見つかるまで増加させながら探索しています。
• 暗号化と復号化：pow() 関数でべき乗を計算し、fmod() 関数で n を法とした剰余を求めています。

実装時の注意点

このサンプルコードは学習用の簡易実装であり、そのまま実務で使用することはできません。実際の開発では以下の点に留意してください。

• 精度の問題：double 型は大きな数のべき乗演算でオーバーフローや丸め誤差が発生します。実運用では GMP や OpenSSL などの多倍長整数ライブラリを利用します。
• 鍵長：本番環境では、十分に大きな素数を使用し、2048ビット以上の鍵長が推奨されます。
• パディング：OAEPなどの適切なパディングを適用しないRSA暗号は、様々な攻撃に対して脆弱になります。