a3VtYQ2e9uA1のブログ

特記事項はありません

簡易RSA計算器

計算器

素数$ p $
素数$ q $
平文$ M $

定義

2つの異なる素数$p,q$および平文$ M $を与える.ただし$0 \leq M \leq pq - 1$.

  • $N = pq$
  • $\phi (N) = (p - 1)(q - 1)$
  • $\gcd (e, \phi (N)) = 1$
  • $d = e^{-1} \mod \phi (N)$
  • $C = M^{e} \mod N$
  • $M_{d} = C^{d} \mod N$

なお,$e$は$\phi(N)$に対して互いに素となる数のうち最小のもの.

プログラム

JavaScriptです.

calc()

メインの関数です.見栄え重視のために入出力部分は省略しています.

function calc() {
    var p, q, M;

    // 入力値の検証
    if (isNaN(p) || isNaN(q) || isNaN(M)) return;
    if (!isPrime(p) || !isPrime(q)) return;
    if (p == q) return;
    if (M < 0 || (p * q - 1) < M) return;

    // NおよびΦ(N)の計算
    var N = p * q;
    var phi_N = (p - 1) * (q - 1);

    // eの計算
    var e = 2;
    while(gcd(phi_N, e) != 1) e++;

    // dの計算(拡張ユークリッド互除法)
    var d = 2;
    while(e * d % phi_N != 1) d++;

    // べき剰余の計算
    var C = powmod(M, e, N); // 暗号化
    var Md = powmod(C, d, N); // 復号
}

isPrime()

入力nが素数であるかを判定します.低効率.

function isPrime(n) {
    if (n < 2) return false; // 1以下なら素数でない
    if (n == 2) return true;  // 2は素数
    if (n % 2 == 0) return false; // 2以外の偶数は素数でない

    // √nまでの奇数についてnの剰余を求める
    var m = Math.sqrt(n);
    for (var i = 3; i <= m; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

gcd()

入力aとbの最大公約数を求めます.

function gcd(a, b) {
    if (a % b == 0) return b;
    else return gcd(b, a % b);
}

powmod()

繰り返し自乗法によって$M^{k} \mod N$を求めます.

function powmod(M, k, N) {
    var v = 1;
    for (var i = 0; i < k; i++) {
        v *= M;
        if (v >= N) v %= N;
    }
    return v;
}