RSA - qunxingw的博客

作者在 2018-06-17 12:49:59 发布以下内容

1,求模的运算：

(m1.m2)%n=(m1%n.m2%n)%n

2,幂运算优化：M^e%n

如果 e偶数,就变为: ((M^e/2)%n. (M^e/2)%n)%n

其他：(M^(e-1)%n.M%n)%n


<html>
<head>
<meta charset="utf-8"/>
<title>
RSA 加密,解密
</title>

</head>
<body>
<script>
//e.d=(p-1)(q-1)K+1;
//求密钥d；
function pri_key(e,p,q){
var k=0;
while((e*k)%((p-1)*(q-1))!=1){
k++;
}
return k;
}


//蒙哥马利 幂降指数取模
function mengemali(i,j,n){ //i 指数  j 底  n=p.q;

	if(i==1){
	return j%n;
	}

	if(i==2) return (j*j)%n;
	else{
	if(i%2==0){
	return (mengemali(i/2,j,n)*mengemali(i/2,j,n))%n;
	}
	return ((j%n)*mengemali(i-1,j,n))%n;
}

}
//幂转换成乘积 递归加密  
function test(i,j,n){
 if(i==1)
	return j%n;
 else{
return (j%n*test(i-1,j,n))%n;
}
}




</script>


  <script>
  
var  p=101;//素数
var  q=103;//素数
var n=p*q;//模
var e=1337;//公钥
var m=779;//明文
var  d=pri_key(e,p,q);//私钥
var t=test(e,m,n);//幂转换成乘积 递归加密
var tt=test(d,t,n);//解密

 c=mengemali(e,m,n);//幂转换成乘积 优化递归加密
 M_e=mengemali(d,c,n);//优化递归加密解密
 
  alert("素数p: "+ p); 
  alert("素数q: "+ q); 
  alert("公钥e: "+ e);
  alert("私钥d: "+ d); 
  alert("明文m: "+ m);
  alert("密文c: "+ c);
  alert("解密后明文M_e: "+ M_e);
  alert("密文t: "+ t);
 alert("解密后明文tt: "+ tt);
  
  
  </script>
	

</body>
</html>

作者在 2018-06-26 00:10:18 补充以下内容

def private_key(e, ol):
    k = 0
    while (ol * k + 1) % e:
        k = k + 1
    d = int((ol * k + 1) / e)
    return d

def mengemali(i,j,k):
	if(i==1):
		return j%k
	if(i==2):
		return j*j%k
	else:
		if(i%2==0):
			return (mengemali(i/2,j,k)*mengemali(i/2,j,k))%k
		else:
			return (j%k*mengemali(i-1,j,k))%k

		

def deal_test():
	p=9967
	q=9973
	e=9949
	n=p*q
	m=25
	c=mengemali(e,m,n)
	d=private_key(e,(p-1)*(q-1))
	M=mengemali(d,c,n)
	print('me' ,m)
	print('e' ,e)
	print('d' ,d)
	print('c' ,c)
	print('M' ,M)