RSA暗号(秘密鍵と公開鍵)の仕組みを勉強してみた!

暗号化と複合化で異なる鍵を使う「公開鍵暗号方式」は、SSL通信などで用いられる重要かつ有名な技術である。

この公開鍵暗号方式で有名なものに「RSA暗号」があり、これは内緒で選んだ2つの素数から公開鍵と秘密鍵を作り、2つの素数の積を公開する。従って、もしも2つの素数の積を素因数分解できれば、暗号を解読が可能。

ただし大きな素数の積の場合、最新のコンピューターを用いても素因数分解は実用的な時間では終わらない。
素因数分解を効率的に行うアルゴリズムがまだ見つかっていないためである。


素因数分解の関数を作る

引数に指定された整数nを素因数分解し、その結果を表示するprimeFactorization関数を作成する。

この関数は、引数にnに100を指定すると、

100 = 2 * 2 * 5 * 5

と表示する。素因数分解のアルゴリズムには、高度な数学を使った技法も考案されているが、ここは単純な技法に工夫を加える手法とする。

下記の例は、まだ工夫を加える前のprimeFactorization関数とテスト用main関数。

main関数では、キーボードから1以上の整数入力を受け、それを引数nとしてprimeFactorization関数を呼び出す。

#include <stdio.h>

void primeFactorization(unsigned int n) {
    unsigned int, a, counter;

    printf("%u = ", n);
    counter = 0;
    a = 2;
    while (n >= a * a) {
        if (n % a == 0) {
            printf("%u * ", a);
            n /= a;
        }
        else
        {
            a++;
        }
        counter++;
    }
    printf("%u\n", n);
    printf("counter = %u\n", counter);
}

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

    printf("1以上の整数を入力してください:")
    scanf("%u", &n);
    primeFactorization(n);
    return 0;
}

primeFactorization関数では、aで繰り返しnを割って(割切れることを確認後)、nの値を更新。aの初期値は、最小の素数2である。nが、aで割切れる可能性があるのは、n ≧ aの2乗の時だけであるため、それをwhile分の繰り返し条件にする。

例えば、100を素因数分解する時、nの値が100, 50, 25, 5と更新された時点で、n ≧ 2の2乗という条件がfalseになり、繰り返しが終了となる。

while文を抜けてから、最後に残った5を付け足して表示する。

後で加える"工夫"の効果を確認できるように、while文の繰り返し回数をcounterという変数でカウントし、100および429467295(unsigned int型の最大値)を素因数分解結果は以下になる。

| 1以上の整数を入力してください:100
| 100 = 2 * 2 * 5 * 5
| counter = 6

| 1以上の整数を入力してください:429467295
| 429467295 = 3 * 5 * 17 * 257 * 65537
| counter = 259

繰り返し回数が減るように工夫する

100の素因数分解であれば実行時間は一瞬で、実行上問題ない。

しかし、数字が大きくなるほど時間がかかる。よって、primeFactorization関数の処理を工夫してみる。

気づいている方はいるかもしれないが、ポイントはwhile文の中で、aの値が2, 3, 4...と1ずつ増えていく部分である。例えば、100の場合、2と5で割切れるかを2回ずつチェックしただけでなく、3, 4でも割切れる事の確認をした。

素数である3はチェックする必要があるが、素数でない4をチェックすることは無駄になる。

するとaが素数であるか?否か?の確認を実施した上で、素数であることを確認してから割り算を実施すべきである。しかし、これでは「aの素数確認」に時間がかかってしまうことになる。

よって、ここでは処理に時間のかからない簡易的な素数確認方法を採ることとする。

具体的には、5以降の数では、2の倍数、3の倍数は素数でないとして繰り返しかた除外する。

aのインクリメント法を工夫して回数を減らせる。
5以上の整数を並べてみると、

| 5, 6, 7, 8, 9, 10...

となる。この並びは、「奇数⑸、偶数かつ3の倍数⑹、奇数⑺、偶数⑻、奇数かつ3の倍数⑼、偶数⑽」であり、11以降も同じパターンで繰り返される。よって、2の倍数と3の倍数をスキップするには5以降の1の増加分を+2, +4, +2, +4…とすればよい。

以下に改良したprimeFactorization関数を載せる。

まず、aを2および3の倍数でない数で割る。次にaの初期値を5として、2および3の倍数でない数で割る。
次にaに2と4を交互に加える

a += (inc ^ 6);

少し変わった書き方なので、解説すると以下の通りである。
"inc"は増分、"^"は排他的論理和(XOR)演算。2と4を2進数で表すと、"0010", "0100"になる。これらを交互に切り替えるには、"0110"つまり"6"とXOR演算を行えばよい。XOR演算は、1に対する桁を反転し、0に対する桁を変化させない。つまり、

0010 XOR 0110 = 0100
0100 XOR 0110 = 0010
0010 XOR 0110 = 0100

となり、1, 4の繰り返しを切り替えられる。

この方法を用いて、先ほどの4294967295を実行すると、繰り返し回数が259→130回に減っていることがわかる。
つまり120回は無駄な繰り返しだったことがわかる。