paiza 問題集 RSA 暗号の作成 js

ユークリッドの互除法メニュー【RSA 暗号の解読・RSA 暗号の作成】

Task

RSA暗号の復号に必要な整数 p,q,e,E が与えられるので暗号化前の文字を出力してね。

【RSA 暗号の解読（1文字）】コード

reader.on('close', () => {
   const Ext_Euclid = (a, b, x, y, nx, ny) => {
      if (a % b === 0) {
         return nx;
      }
      x -= Math.floor(a / b) * nx;
      y -= Math.floor(a / b) * ny;
      return Ext_Euclid(b, a % b, nx, ny, x, y);
   };
   const pow = (a, b, m, re = BigInt(1)) => {
      if (!b) {
         return Number(re);
      }
      return (b & 1) ? pow((a * a) % m, b >> 1, m, (re * a) % m) :
                       pow((a * a) % m, b >> 1, m, re);
   };
   const [p, q, e, E] = lines[0].split(' ').map(Number);
   const [n, nd] = [p * q, (p - 1) * (q - 1)];
   const d = (Ext_Euclid(e, nd, 1, 0, 0, 1) + nd) % nd;　// d * e ≡ 1 (mod nd)
   const code = pow(BigInt(E), d, BigInt(n));
   console.log(String.fromCodePoint(code));  // E ^ d mod n
});

拡張ユークリッドの互除法と繰り返し２乗法でRSA暗号（一文字）を解読。聞き慣れない用語が盛り沢山…。

top

問題【STEP: 2】RSA 暗号の解読（文字列）

Task

RSA暗号復号に必要な整数 n, e, E が与えられるので復号して得られる文字列を出力してくね。

【RSA 暗号の解読（文字列）】コード

reader.on('close', () => {
   const Ext_Euclid = (a, b, x, y, nx, ny) => {
      if (a % b === 0) {
         return nx;
      }
      x -= Math.floor(a / b) * nx;
      y -= Math.floor(a / b) * ny;
      return Ext_Euclid(b, a % b, nx, ny, x, y);
   };
   const pow = (a, b, m, re = BigInt(1)) => {
      if (!b) {
         return Number(re);
      }
      return (b & 1) ? pow((a * a) % m, b >> 1, m, (re * a) % m) :
                       pow((a * a) % m, b >> 1, m, re);
   };
   const [n, e, E] = lines[0].split(' ').map(Number);
   let [p, q] = [0, 0];
   for (let i = 2; i < Math.sqrt(n); i++) {
      if (n % i === 0) {
         p = i;
         q = n / i;
         break;
      }
   }
   const nd = (p - 1) * (q - 1);
   const d = (Ext_Euclid(e, nd, 1, 0, 0, 1) + nd) % nd;　 // de ≡ 1 (mod n')
   const M = pow(BigInt(E), d, BigInt(n));
   const Str = [];
   M2 = M.toString(2).padStart(28,'0').split('');

   for (let i = 1; i <= 4; i++) {
      const code = parseInt(M2.splice(0, 7).join(''), 2);
      if (code) {
         Str.push(String.fromCodePoint(code));
      }
   }
   console.log(Str.join(''));
});

暗号化前の数値を2進数に変換して28桁になるように先頭を0で埋めてから 7桁毎に区切って10進数に変換…。

top

問題【FINAL】RSA 暗号の作成（文字列）

Task

RSA暗号を作成し復号に必要な数値 n , e と暗号化後の数値 E , 暗号化前の文字列 S を出力してね。

【RSA 暗号の作成（文字列）】コード

const Ext_Euclid = (a, b, x, y, nx, ny) => {
   if (a % b === 0) {
      return nx;
   }
   x -= Math.floor(a / b) * nx;
   y -= Math.floor(a / b) * ny;
   return Ext_Euclid(b, a % b, nx, ny, x, y);
};
const pow = (a, b, m, re = BigInt(1)) => {
   if (!b) {
      return Number(re);
   }
   return (b & 1) ? pow((a * a) % m, b >> 1, m, (re * a) % m) :
                    pow((a * a) % m, b >> 1, m, re);
};
const Send = 'ABC';  // 送信したい文字列
const [p, q] = [19433, 63311];  // 適当な素数 p , q を用意
const [n, nd] = [p * q, (p - 1) * (q - 1)];  // n = p * q , nd = (p - 1) * (q - 1)
const e = 5449;  // e は gcd(e , n') = 1 を満たす適当な整数
const d = (Ext_Euclid(e, nd, 1, 0, 0, 1) + nd) % nd;  // d は d * e ≡ 1 (mod n') を満たす自然数
const Sr2 = new Array(4).fill('0000000');  // 4 文字の文字コード(2進数)
for (let i = 0; i < Send.length; i++) {
   Sr2[i] = (Send.charCodeAt(i).toString(2).padStart(7, '0'));  // Send ('ABCD')のi番目の文字の文字コード(2進数)でSr2[i]を上書き
}
const M = parseInt(Sr2.join(''), 2);  // Sr2 を連結して整数に変換(暗号化前の数字)(28 ビット)d
const E = pow(BigInt(M), e, BigInt(n));  // E = M^e mod n とすると
const M2 = pow(BigInt(E), d, BigInt(n));  // E^d mod n は M になる
//  console.log(M,M2);
const M2r2 = M2.toString(2).split('');  // M2 を2進数(文字列)に変換して 一文字ごとの配列を生成
const Receive = [];  // 解読した文字列
for (let i = 0; i < 4; i++) {
   const code = parseInt(M2r2.splice(0, 7).join(''), 2);  // M2r2 の先頭から7文字を切り取って連結し 10進数に変換
   if (code) {  // code が0じゃなければ…
      Receive.push(String.fromCodePoint(code));  // 解読した文字を Receive に保存
   }
}
console.log(n, e, E);
console.log(Receive.join(''));

暗号の作成と解読。実際はもっと桁数が多い素数を使って暗号化するみたいね。’ABC’ を暗号化しています。

top