Plurk paste

// 這是展現 RSA 原理的簡易實作
// 請參考
// https://zh.wikipedia.org/wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95

//隨意選擇兩個質數p和q，p不等於 q
var p=13;
var q=73;

console.log(`p=${p} q=${q}`);

//計算 N=pq。
var N=p*q; 
console.log(`N=${N}`);


//根據歐拉函數，求得r=f(N)=f(p)f(q)=(p-1)(q-1)
var r= (p-1)*(q-1); 
console.log(`r=${r}`);

//擇一個小於r的整數e，使e與r互質。
function isInterprime(a,b) { //求互質
  for(var i=2;i<=a&&i<=b;i++){ //因為a,b的數字很小，直接算
    if(a%i==0&&b%i==0) return false;
  }
  return true;
}

var e_list=[];
for(var i=2;i<r;i++){
  if(isInterprime(i,r)) e_list.push(i);
}
console.log(`e_list=[${e_list}]`);

//隨機選一個 e
var e=e_list[Math.floor(Math.random() * e_list.length)];
console.log(`e=${e}`);

//並求得e關於r的模反元素，命名為d（求d令ed ≡ 1  (mod r))
//等同於，求d 使得 (e*d)%r=1
var d=-1;
for(var i=2;i<=r;i++){
  if((e*i)%r==1){
    d=i;
    break;
  }
}

//避免公鑰等於私鑰，當 (e*d)%r=1 成立時，(e*(d+r))%r=1 也會成立
if(d==e)d+=r; 
console.log(`d=${d}`);
//第二組私鑰
var d2=d+r;
console.log(`d2=${d2}`);

console.log(`(N)=${N} 公鑰(e)=${e} 私鑰(d)=${d} 私鑰(d2)=${d2}`);

//加密
//將需要加密的訊息轉為N範圍內的數字，舉例來說，令a=1,b=2等等，這部分略過
//轉為數字後的明文為 n，轉出來的密文為 c 
// c ≡ n^d (mod N)
var n=5; //假設要加密的密文

// 依照公式寫出程式碼
// var c=Math.pow(n,e)%N;
// 當數字太大時，javascript 會把數字轉為浮點數，導致計算餘數出錯，因此要使用模算術的特性去做運算
// https://ithelp.ithome.com.tw/articles/10205727
function mod_pow(n,key,N){
  var result=1;
  for(var i=0;i<key;i++){
    result*=n;
    result%=N;
  }
  return result;
}
var c=mod_pow(n,e,N);
console.log(`加密: ${n} => ${c}`);

//解密
//var nd=Math.pow(c,d)%N;
var nd=mod_pow(c,d,N);
console.log(`解密(第一組私鑰): ${c} => ${nd}`);

var nd2=mod_pow(c,d2,N);
console.log(`解密(第二組私鑰): ${c} => ${nd2}`);