浅谈利用RSA算法防止非法注册机的制作
作者:赵春生
下载源代码
一、RSA简介
RSA公开密钥密码系统是由R.Rivest,A.Shamir,L.Adleman提出的,不仅仅可用于数据的加密,也可用于数字签名,其算法如下:
加密:c=m^e mod n 解密:m=c^d mod n6、(n,e)和(n,d)分别称为“公开密钥”和“秘密密钥”。根据Euler定理可得:
m=c^d mod n=(m^e mod n)^d mod n=m
现举例说明其工作过程:取两个素数p=11,q=13,n=p*q=11*13=143,z=(p-1)*(q-1)=(11-1)*(13-1)=120,再选取与z=120互素的整数e,如e=7,现可计算出满足7*d=1 mod 120的整数d=103,即:7*103=1 mod 120,7*103/120余1,整理如下:
p=11 q=13 n=143 e=7 d=103 (n,e)=(143,7) (n,d)=(143,103)
以数据加密为例:
甲向乙发送机密数据信息m=85,并已知乙的公钥(n,e)=(143,7),于是可计算出:
c=m^e mod n=85^7 mod 143=123
甲将c发送至乙,乙利用私钥(n,d)=(143,103)对c进行计算:
m=c^d mod n=123^103 mod 143=85
现乙已经得到甲向其要发送的机密数据信息。在这里,甲向乙发送信息,甲所拥有的仅仅是乙的公钥。
以数字签名为例:
乙要向甲发送信息,并要让甲确信此信息是由乙本人所发出的,于是,乙将能代表自己身份的编码值(如:123),利用私钥(n,d)=(143,103)进行计算,并将结果发送给甲:
m=c^d mod n=123^103 mod 143=85
甲接受到乙的数字签名后利用乙的公钥(n,e)=(143,7)进行计算,得出代表乙身份的编码:
(本文来源于图老师网站,更多请访问http://m.tulaoshi.com/cyuyanjiaocheng/)c=m^e mod n=85^7 mod 143=123
现甲经过验证已确信信息的发送方为乙。因为只有乙拥有私钥(n,d),来对代表自己身份的编码123进行计算。在不知道乙私钥(n,d)的情况下,任何人都不会算出85这一签名来冒充乙。在这里,乙向甲发送信息并进行签名,甲所拥有的也仅仅是乙的公钥来验证乙的签名。
从上面两个例子中我们可以更好得理解这一结论,即:由(n,e)加密的数据只能用(n,d)解密,反之亦然。
二、在基于序列号保护的共享软件中应用RSA
结合数字签名的实例能更好得理解这一应用:在某一共享软件中,甲想用123为注册名进行软件注册,他现在拥有的仅仅是存在于共享软件程序中的公钥(n,e)=(143,7)。甲现将123为注册名向乙提出注册申请,乙得知此申请并通过此申请后,便利用所拥有的私钥(n,d)对注册名123进行计算:
m=c^d mod n=123^103 mod 143=85
甲得到计算后的结果85(序列号),提供给共享软件的注册程序进行计算:
c=m^e mod n=85^7 mod 143=123
然后注册程序将判断计算结果c是否为123(注册名),以决定注册是否通过。
如果甲随意输入一组序列号利用公钥(n,e)进行计算,那他得到的结果将不是123,注册也就失败了。注意,在这里,共享软件的注册程序比较的是注册名,而不是序列号。如果甲跟踪注册程序得到了他所随意输入的序列号所产生的注册名,将其提供给注册程序,那注册程序也能够通过注册,但他由于没有(n,d),所以他无法用自己的注册名进行软件注册,也就防止了非法注册机的制作。
将RSA应用于此的目的仅仅是防止非法注册机的制作,在以上描述中,n=143,包括以下Demo中的n(HEX)=963251DC5A9C90D9F203A03C363BA411,以现在的计算机处理速度,能很快地将其因式分解得到相应的p,q,再结合暴露在共享软件注册程序中的e,从而计算出d,那么这个共享软件的保护就完全被破解了。解决的方法是要避免n过短,以及结合MD5等加密算法……
三、具体实践
/* R