RSA暗号方式をC言語で実装

RSAとは

RSA暗号とは、桁数が大きい合成数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号の一つ。1977年に発明された。発明したロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマンの頭文字をとって「RSA」。

暗号方式

• p , q：素数
• n：公開鍵

n = p * q

• l：最小公倍数

l = lcm( p-1 , q-1 )

• e：公開鍵

gcd(l , e) = 1

• d：秘密鍵

e * d \; mod \; l = 1

• M：平文、C：暗号文
• 暗号化

C = M ^ e \; mod \; n

• 復号化

M = C ^ d = M ^ {ed} \; mod \; n

コード

実装できそうだなーと思ったので実装してみた。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

unsigned int primeNum();
unsigned int gcd(unsigned int a, unsigned int b);
unsigned int lcm(unsigned int a, unsigned int b);
unsigned int extEuqlid(unsigned int a, unsigned int b);
unsigned int power(unsigned int a, unsigned int k, unsigned int n);
unsigned int extpower(unsigned int a, unsigned int k, unsigned int n);

int main() {

    srand((unsigned int)time(NULL));

    //異なる素数 p,q
    int p,q;
    do {
        p = primeNum();
        q = primeNum();
    } while(p == q);

    if(p < q) {
        int tmp = p;
        p = q;
        q = tmp;
    }

    printf("P : %d   Q : %d\n",p,q);

    //公開鍵 n
    int n = p * q;

    //最小公倍数 l
    int l = lcm(p-1, q-1);

    //公開鍵 e
    int e = 2;
    while(gcd(l, e) != 1) {
        e++;
    }

    //秘密鍵 d
    //int d = extEuqlid(e, l);
    int d = 2;
    while(e * d % l != 1) {
        d++;
    }

    printf("N : %d   L : %d   E : %d   D : %d\n",n,l,e,d);

    //平文
    unsigned int plain_num;
    printf("plain_num : ");
    scanf("%u", &plain_num);

    //暗号化
    unsigned int encrypted_num = extpower(plain_num, e, n);
    printf("encrypted_num: %u\n", encrypted_num);

    //復号化
    unsigned int decrypted_num = extpower(encrypted_num, d, n);
    printf("decrypted_num: %u\n", decrypted_num);

    return 0;
}

//素数判定
unsigned int primeNum() {

    int num,i,flg = 0;
    while(flg == 0) {
        num = rand() % 100;
        for(i = 2; i <= sqrt(num); i++) {
            if(num % i == 0) {
                flg = 0;
                break;
            }
            flg = 1;
        }
    }
    return num;

}

//最大公約数 Greatest Common Divisor
unsigned int gcd(unsigned int a, unsigned int b) {
    if(b == 0){
        return a;
    } else {
        return gcd(b, a % b);
    }
}

//最小公倍数 Least Common Multiple
unsigned int lcm(unsigned int a, unsigned int b) {
    return a * b / gcd(a, b);
}

//拡張ユークリッド互除法
unsigned int extEuqlid(unsigned int a, unsigned int b) {

    int x1 = 1, y1 = 0, r1 = b;
    int x2 = 0, y2 = 1, r2 = a;
    int d;

    while(1) {

        int q = r1 / r2;
        int r = r1 % r2;
        int x = x1 - x2 * q;
        int y = y1 - y2 * q;

        if(r == 0) {
            d = x2;
            break;
        }

        x1 = x2; y1 = y2; r1 = r2;
        x2 = x;  y2 = y;  r2 = r;

    }

    while(d <= 0) {
        d += b;
    }

    return d;
}

/*
 * 繰り返し自乗法を使った法nのべき乗計算（aのk乗をnで割った余りを求める）
 * 
 * unsigned int a : 底
 * unsigned int k : 指数
 * unsigned int n : 法
*/
unsigned int extpower(unsigned int a, unsigned int k, unsigned int n) {

    a %= n;

    if(a == 0 || n == 0){
        return 0;
    }
    if(k == 0){
        return 1 % n;
    }

    int i;
    unsigned int value = 1;
    for(i = 0; i < k; i++) {
        value *= a;
        if(value >= n) {
            value %= n;
        }
    }
    return value;
}

$ ./rsaInt
P : 41   Q : 13
N : 533   L : 120   E : 7   D : 103
plain_num : 317
encrypted_num: 47
decrypted_num: 317

$ ./rsaInt
P : 89   Q : 71
N : 6319   L : 3080   E : 3   D : 1027
plain_num : 2081
encrypted_num: 5039
decrypted_num: 2081

$ ./rsaInt
P : 73   Q : 71
N : 5183   L : 2520   E : 11   D : 2291
plain_num : 754
encrypted_num: 2406
decrypted_num: 754

$ ./rsaInt
P : 73   Q : 67
N : 4891   L : 792   E : 5   D : 317
plain_num : 5082
encrypted_num: 1572
decrypted_num: 191

平文がnより大きくなると復号化の際に割りすぎて失敗する。