初学者向け！RSA 暗号の基礎とシミュレーションの実装

#include <iostream>
using namespace std;

/*
    冪剰余計算 : b^e mod m
*/

long long powmod( long long b, long long e, long long m ) {

    long long result = 1; // 結果
    
    // 0 乗の場合、結果は 1
    if( e == 0 ) return result;
    
    // 指数が 0 になるまで法を取りながら積を計算
    while( e > 0 ) {
    
        // 奇数の場合: 最下位ビットが 1 = 求める解の因数として利用される
        if( e & 1 ) {
            e--; // 偶数にする
            result = result * b % m; // 解の更新
        }
        // 偶数の場合: 最下位ビットが 0 = 求める解の因数として利用されない
        else {
            e >>= 1; // 右に 1 ビットシフト
            b = b * b % m; // 部分計算
        }
    }
    
    return result;
}

/*
    冪剰余計算の結果を標準出力
*/

int main( int argc, char *argv[] ) {

    // 引数を忘れた場合の Segmentation fault 対策
    if( argc < 4 ) {
        cout << "Please input (b, e, m)" << endl;
        exit( 1 );
    }

    // 文字列型の引数を整数型に変換
    int b = atoi( argv[ 1 ] );
    int e = atoi( argv[ 2 ] );
    int m = atoi( argv[ 3 ] );

    // 冪剰余計算
    long long result = powmod( b, e, m );

    // 標準出力
    cout << b << " ^ " << e << " mod " << m << " = " << result << endl;

    return 0;
}

#include <iostream>
using namespace std;

/*
    最大公約数の算出
*/

int gcd( int a, int b ) {
    
    // gcd(a,b) = gcd(b,a mod b) の法則を利用
    while( b > 0 ) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

/*
    マンドライン引数に与えられた自然数の最大公約数を標準出力
*/

int main( int argc, char *argv[] ) {

    // 引数を忘れた場合の Segmentation fault 対策
    if( argc < 3 ) {
        cout << "Please input (a,b)" << endl;
        exit( 1 );
    }

    // 文字列型の引数を整数型に変換
    int a = atoi( argv[ 1 ] );
    int b = atoi( argv[ 2 ] );

    // 最大公約数の取得
    int result = gcd( a, b );

    // 標準出力
    cout << "GCD(" << a << "," << b << ") = " << result << endl;

    return 0;
}

#include <iostream>
using namespace std;

int gcd( int a, int b ); // プロトタイプ宣言

/*
    最小公倍数の算出
*/

int lcm( int a, int b ) {
    
    // a * b = gcd(a,b) * lcm(a,b) の法則を利用
    return ( a * b ) / gcd( a, b );
}

/*
    コマンドライン引数に与えられた自然数の最小公倍数を標準出力
*/

int main( int argc, char *argv[] ) {

    // 引数を忘れた場合の Segmentation fault 対策
    if( argc < 3 ) {
        cout << "Please input (a,b)" << endl;
        exit( 1 );
    }

    // 文字列型の引数を整数型に変換
    int a = atoi( argv[ 1 ] );
    int b = atoi( argv[ 2 ] );

    // 最大公約数の取得
    int result = lcm( a, b );

    // 標準出力
    cout << "LCM(" << a << "," << b << ") = " << result << endl;

    return 0;
}

/*
    最大公約数の算出
*/

int gcd( int a, int b ) {
    
    // gcd(a,b) = gcd(b,a mod b) の法則を利用
    while( b > 0 ) {
        int t = a % b;
        a = b;
        b = t;
    }

    return a;
}

#include <iostream>
using namespace std;

/*
    単純法による素数判定
*/

// 引数に与えられた自然数の素数判定結果をリターン
bool simple( int n ) {
    
    if( n < 2 ) return false; // 2 未満は排除
    if( n == 2 ) return true; // 2 は素数
    if( n % 2 == 0 ) return false; // 2 以外の偶数は合成数（除算による偶数判定）
    
    // 3 以上の奇数でチェック
    for( int k = 3; k * k <= n; k += 2 ) { 
        if( n % k == 0 ) {
            return false; // 割り切れる場合は合成数
        }
    }

    return true; // 素数
}

/*
    コマンドライン引数に与えられた自然数以下の素数を標準出力
*/

int main( int argc, char *argv[] ) {

    // 引数を忘れた場合の Segmentation fault 対策
    if( argc < 2 ) {
        cout << "Please input N" << endl;
        exit( 1 );
    }

    // 文字列型の引数を整数型に変換
    int N = atoi( argv[ 1 ] );

    // 標準出力
    for( int n = 0; n <= N; n++ ) {
        if( simple( n ) ) {
            cout << n << " ";
        }
    }
    cout << endl;

    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

/*
    エラトステネスの篩による素数判定
*/

// 引数に与えられた自然数以下の素数判定結果の配列をリターン
vector<bool> eratosthenes( int n ) {
    
    // 配列のインデックスに自然数値が対応
    vector<bool> result( n + 1, true );
    
    result[ 0 ] = false; // 0 は非素数
    result[ 1 ] = false; // 1 は非素数
    for ( int k = 2; k <= n; k++ ) {
        
        // 合成数であることが判明している場合はスキップ
        if ( !result[ k ] ) continue;

        // k は素数であるが、k の倍数は合成数
        for ( int mk = 2 * k; mk <= n; mk += k ) {
            result[ mk ] = false;
        }
    }

    return result;
}

/*
    コマンドライン引数に与えられた自然数以下の素数を標準出力
*/

int main( int argc, char *argv[] ) {

    // 引数を忘れた場合の Segmentation fault 対策
    if( argc < 2 ) {
        cout << "Please input N" << endl;
        exit( 1 );
    }

    // 文字列型の引数を整数型に変換
    int N = atoi( argv[ 1 ] );

    // N 以下の自然数における素数判定結果の取得
    vector<bool> result = eratosthenes( N );

    // 素数を標準出力
    for( int n = 0; n <= N; n++ ) {
        if( result[ n ] ) {
            cout << n << " ";
        }
    }
    cout << endl;

    return 0;
}

#include <iostream>
#include <ctime>
using namespace std;

long long powmod( long long b, long long e, long long m ); // プロトタイプ宣言

/*
    ミラーラビン法による素数判定
*/

// 引数に与えられた自然数の素数判定結果をリターン
bool rabin( int n ) {
    srand( ( unsigned int )time( NULL ) );
    
    if( n < 2 ) return false; // 2 未満は非素数
    if( n == 2 ) return true; // 2 は素数
    if( !( n & 1 ) ) return false; // 2 以外の偶数は合成数（論理演算による偶数判定）

    /* n-1 = (2^k)*m を満たす (k,m) を算出 */

    // この時点で n は奇数であるため、n-1 は偶数であり、m は奇数
    int k = 0;
    int m = n - 1;
    while( !( m & 1 ) ) {
        m >>= 1; // 右に 1 ビットシフト = m を 1/2
        k++;
    }

    /* [2, n-1] を満たす乱数の生成 */
    int a = rand( ) % ( n - 2 ) + 2;

    /* 判定式 y = a^m mod n に基づくチェック */ 
    
    long long y = powmod( a, m, n );
    if( y == 1 || y == n - 1 ) {
        return true; // 素数
    }

    /* 判定式 y = y^2 mod n (0 <= i <= k-1) に基づくチェック */

    int i = 0;
    while( i < k ) {
        y = powmod( y, 2, n );
        if( y == n - 1 ) return true; // 素数
        if( y == 1 ) return false; // 合成数
        i++;
    }

    /* 判定式に基づくチェック終了 */
    return false; // 合成数
}

/*
    コマンドライン引数に与えられた自然数以下の素数を標準出力
*/
int main( int argc, char *argv[] ) {

    // 引数を忘れた場合の Segmentation fault 対策
    if( argc < 2 ) {
        cout << "Please input n" << endl;
        exit( 1 );
    }

    // 文字列型の引数を整数型に変換
    int N = atoi( argv[ 1 ] );

    // 標準出力
    for( int n = 0; n <= N; n++ ) {
        if( rabin( n ) ) {
            cout << n << " ";
        }
    }
    cout << endl;

    return 0;
}

/*
    冪剰余計算 : b^e mod m
*/

long long powmod( long long b, long long e, long long m ) {

    long long result = 1; // 結果

    // 0 乗の場合、結果は 1
    if( e == 0 ) return result;

    // 指数が 0 になるまで法を取りながら積を計算
    while( e > 0 ) {

        // 奇数の場合: 最下位ビットが 1 = 求める解の因数として利用される
        if( e & 1 ) {
            e--; // 偶数にする
            result = result * b % m; // 解の更新
        }

        // 偶数の場合: 最下位ビットが 0 = 求める解の因数として利用されない
        else {
            e >>= 1; // 右に 1 ビットシフト
            b = b * b % m; // 部分計算
        }
    }

    return result;
}

#include <iostream>
#include <ctime>
using namespace std;

// プロトタイプ宣言
int gcd( int a, int b );
long long powmod( long long b, long long e, long long m );

/*
    フェルマーテストによる素数判定
*/

// 引数に与えられた自然数の素数判定結果をリターン
// trial: 素数判定の試行回数

bool fermat( int n, int trial ) { 
    srand( ( unsigned int )time( NULL ) );
    
    if( n < 2 ) return false; // 2 未満は排除
    if( n == 2 ) return true; // 2 は素数
    
    // trial の回数だけ素数判定を試行
    for( int i = 0; i < trial; i++ ) {
        
        // [2, n-1] の乱数を生成
        int a = rand( ) % ( n - 2 ) + 2;
        // 最大公約数が 1 以外の場合は合成数
        if( gcd( a, n ) != 1 ) {
            return false;
        }
        // 判定式 y = a^(n-1) mod n の値が 1 以外の場合は合成数
        if( powmod( a, n - 1, n ) != 1 ) {
            return false;
        }
    }

    return true;
}

/*
    コマンドライン引数に与えられた自然数以下の素数を標準出力
*/

int main( int argc, char *argv[] ) {

    // 引数を忘れた場合の Segmentation fault 対策
    if( argc < 3 ) {
        cout << "Please input (N, trial)" << endl;
        exit( 1 );
    }

    // 文字列型の引数を整数型に変換
    int N = atoi( argv[ 1 ] );
    int trial = atoi( argv[ 2 ] );

    // 標準出力
    for( int n = 0; n <= N; n++ ) {
        if( fermat( n , trial ) ) {
            cout << n << " ";
        }
    }
    cout << endl;

    return 0;
}

/*
    最大公約数の算出
*/

int gcd( int a, int b ) {
    
    // gcd(a,b) = gcd(b,a mod b) の法則を利用
    while( b > 0 ) {
        int t = a % b;
        a = b;
        b = t;
    }

    return a;
}

/*
    冪剰余計算 : b^e mod m
*/

long long powmod( long long b, long long e, long long m ) {

    long long result = 1; // 結果

    // 0 乗の場合、結果は 1
    if( e == 0 ) return result;

    // 指数が 0 になるまで法を取りながら積を計算
    while( e > 0 ) {

        // 奇数の場合: 最下位ビットが 1 = 求める解の因数として利用される
        if( e & 1 ) {
            e--; // 偶数にする
            result = result * b % m; // 解の更新
        }

        // 偶数の場合: 最下位ビットが 0 = 求める解の因数として利用されない
        else {
            e >>= 1; // 右に 1 ビットシフト
            b = b * b % m; // 部分計算
        }
    }

    return result;
}

#include <iostream>
using namespace std;

/*
    拡張ユークリッド互除法を応用した逆数の算出
*/

// ax + by = 1 を満たす (x,y) の算出
// RSA 暗号における関係式: ed + my = 1 | a=e, b=m, x=d
// d: RSA 暗号における秘密鍵

void exgcd( int a, int b, int *px, int *py ) {
    
    // 初期の関係式
    int x1 = 0, y1 = 1, r1 = b;
    int x2 = 1, y2 = 0, r2 = a;
    
    // 最終的な解
    int x, y;
    // 計算過程における商と剰余
    int qq, rr;
    // 計算過程において新たに立式される関係式の係数
    int xx, yy;
    
    while( true ) {
        // 商と剰余の計算
        qq = r1 / r2;
        rr = r1 % r2;
        
        // 新たな式の係数を計算
        xx = x1 - qq * x2;
        yy = y1 - qq * y2;
        // 余りが 0 のときの係数が求める解であるため処理終了
        if( rr == 0 ) {
            x = x2;
            y = y2;
            break;
        }
        // 関係式の更新
        x1 = x2; y1 = y2; r1 = r2;
        x2 = xx; y2 = yy; r2 = rr;
    }
    
    // x が 0 以下の場合は変換
    // ax + by = 1 のとき a(x+b) + b(y-a) = 1
    while( x <= 0 ) {
        x += b;
        y -= a;
    }
    // 引数が指定するアドレスに結果を格納
    *px = x;
    *py = y;
}

/*
    コマンドライン引数に与えられた自然数の最大公約数を標準出力
*/

int main( int argc, char *argv[] ) {

    // 引数を忘れた場合の Segmentation fault 対策
    if( argc < 3 ) {
        cout << "Please input (a,b)" << endl;
        exit( 1 );
    }

    // 文字列型の引数を整数型に変換
    int a = atoi( argv[ 1 ] );
    int b = atoi( argv[ 2 ] );

    // 結果格納先のアドレス
    int px, py;

    // 拡張ユークリッド互除法の実行
    exgcd( a, b, &px, &py );

    // 標準出力
    cout << a << "x + " << b << "y = 1 -> (x,y) = (" << px << "," << py << ")" << endl;

    return 0;
}

#include <iostream>
#include <vector>
#include "rsa.hpp"
using namespace std;

/*
	RSA 暗号で利用する鍵の作成
*/

int main( int argc, char *argv[] ) {

	// 引数を忘れた場合の Segmentation fault 対策
	if( argc < 2 ) {
		cout << "Please input N" << endl;
		exit( 1 );
	}
	
	// コマンドライン引数に与えられた整数 N 以下の素数を利用
	int N = atoi( argv[ 1 ] );

	// 乱数の種に現在時刻を設定
	srand( ( unsigned int )time( NULL ) );

	// 素数リスト
	vector<int> primeNum;
	int size = 0;

	// 単純法による素数判定により素数リストを作成
	for( int n = 0; n <= N; n++ ) {
		if( simple( n ) ) {
			primeNum.push_back( n );
		}
	}
	size = primeNum.size( );
	
	// 異なる素数 p, q を用意
	int p, q;
	p = primeNum[ rand( ) % size ];
	do {
		q = primeNum[ rand( ) % size ];
	} while( p == q );
	
	// 公開鍵（1）の作成
	int n = p * q;

	// 最小公倍数の算出
	int m = lcm( p - 1, q - 1 );

	// 公開鍵（2）
	int e = m; // 初期値に m を利用
	if( !( e & 1 ) ) e++; // 奇数に調整

	// 秘密鍵
	int d;
	do {
		// 公開鍵（2）の作成
		e += 2;
		while( gcd( e, m ) != 1 ) e += 2; // m と e は互いに素
		// 秘密鍵の作成
		d = exgcd( e, m );
	} while( e == d );

	// 鍵の標準出力
	cout << "e: " << e << endl;
	cout << "d: " << d << endl;
	cout << "n: " << n << endl;
	
	return 0;
}

#include <iostream>
#include "rsa.hpp"
using namespace std;

/*
	暗号化
*/

int main( void ) {
	int M, e, n;
	cout << "M: "; cin >> M;
	cout << "e: "; cin >> e;
	cout << "n: "; cin >> n;
	cout << M << " ^ " << e << " mod " << n << " = C = " << powmod( M, e, n ) << endl;
	return 0;
}

#include <iostream>
#include "rsa.hpp"
using namespace std;

/*
	復号化
*/

int main( void ) {
	int C, d, n;
	cout << "C: "; cin >> C;
	cout << "d: "; cin >> d;
	cout << "n: "; cin >> n;
	cout << C << " ^ " << d << " mod " << n << " = M = " << powmod( C, d, n ) << endl;
	return 0;
}