RSA 暗号の基本原理 (旧)

ユークリッドの互除法メニュー【合同式・modの演算・modの逆元・高速な累乗の計算・RSA暗号の基本原理】

問題【STEP: 1】合同式
Task
1 〜 10万 のうち N を法として A と合同なものを 小さい順に全て出力してね。

【STEP: 1】コード

reader.on('close', () => {
    const [N, A] = lines[0].split(' ').map(Number);
    const surplus = A % N;
    for (let i = 1; i <= 100000; i++) {  // 1〜100000まで 順番に…
      if (i % N === surplus) {  // i÷N の剰余と A÷N の剰余が同じなら
         console.log(i);  // iを表示
      }
   }
});
hogeちゃんの画像

剰余が一致するかどうか 順番に演算しています。

top
問題【STEP: 2】mod の演算
Task
演算子 cal と自然数 N , 整数 A , B が与えられるので A[cal]B (mod N) を計算してね。

【STEP: 2】コード

reader.on('close', () => {
   const N = Number(lines[0]);
   const [a, cal, b] = lines[1].split(' ');
   const [A, B] = [a, b].map(Number);  // a, b を数値に変換して A, B に代入
   let ans;  // A[cal]B (mod N)
   switch (cal) {
   case '+':
      ans = (A % N + B % N) % N;
      break;
   case '-':
      ans = (A % N - B % N + N) % N;
      break;
   case '*':
      ans = (A % N * B % N) % N;
      break;
   case '^':
      ans = (A % N ** B % N) % N;
      break;
   }
   console.log(ans);
});
hogeちゃんの画像

A[cal]B (mod N) の計算でした。C++の実装例を参照しました。

cal が ‘-‘ の場合 A % N – B % N が負の数になると演算結果がマイナスになるので N 加算してから剰余を計算しないとダメみたいね。

top
問題【STEP: 3】mod の逆元
Task
mod M での A の mod 逆元の値を 1 行で出力してね。

【STEP: 3】コード《拡張ユークリッドの互除法》

reader.on('close', () => {
   const [M, A] = lines[0].split(' ').map(Number);
   Extend_Euclid_Algorithm(M, A);
　// 拡張ユークリッドの互除法
   function Extend_Euclid_Algorithm(X, Y) {
      let [m, a] = [X, Y];
      let [x, y] = [1, 0];
      let [nx, ny] = [0, 1];
      while (a % m) {
         const q = parseInt(a / m);
         const r = a % m;
         const tmpx = x - q * nx;
         const tmpy = y - q * ny;
         [a, m, x, y] = [m, r, nx, ny];
        [nx, ny] = [tmpx, tmpy];
      }
      console.log((nx + M) % M);
   }
});
hogeちゃんの画像

A × N = 1(mod M) となる 1 以上 M 未満の整数 N を 「mod M での A の mod 逆元」といい A^{-1} (mod M) と書く…そうです。前出の 拡張ユークリッドの互除法  を用いて求めています。

top
問題【STEP: 4】高速な累乗の計算
Task
整数 A , B , M が与えられるので A^B(mod M) を求めね。

【STEP: 4】コード《繰り返し二乗法》

// A^B(mod M)
reader.on('close', () => {
   const [A, B, M] = lines[0].split(' ').map(Number);
   let a = A;
   const b = B.toString(2).split('').map(Number);
   ans = 1;
   while (b[0]) {
      b[b.length - 1] ? ans = (ans * a) % M : ans = ans;
      a = (a * a) % M;
     b.pop();
   }
   console.log(ans);
});
hogeちゃんの画像
とりあえずup。
top
問題【FINAL】RSA 暗号の基本原理
Task
[1] d = e^{-1} (mod n‘)・[2] E = M^e (mod n)・[3] E^d (mod n) の値を出力してね。

【FINAL】コード

reader.on('close', () => {
   const [p, q, e, M] = lines[0].split(' ').map(Number);
   const n = p * q;
   const ndash = (p - 1) * (q - 1);
 //console.log(n,m);//3995747143 3995620720
   function mod(a, b, m) {
      let ans = BigInt(1);
      while (b > 0) {
         if (b & 1) {
            ans = ans * a % m;
         }
         a *= a;
         a %= m;
         b >>= 1;
      }
      return Number(ans);
   }

   function extgcd(a, b) {
      if (b === 0) {
         return [a, 1, 0];
      } else {
         [gcd, x, y] = extgcd(b, a % b);
         return [gcd, y, x - Math.floor(a / b) * y];
      }
   }
  let d = extgcd(e, ndash);
   while (d[1] < 0) {
      d[1] += ndash;
   }
   const E = mod(BigInt(M), e, BigInt(n));
   const M2 = mod(BigInt(E), d[1], BigInt(n));
   console.log(d[1]);
   console.log(E);
   console.log(M2);
});
hogeちゃんの画像

頑張ったけど解けなかったので とりあえずこれで。改めてチャレンジします。

top

コメント