?? rsa.txt
字號:
《淺談利用RSA算法防止非法注冊機的制作》
天津 趙春生
一：RSA簡介。
RSA公開密鑰密碼系統是由R.Rivest，A.Shamir，L.Adleman提出的，不僅僅可用于數據的加密，也可用于數字簽名，其算法如下：
1，取兩個相近的大素數p、q；
2，計算n=p*q，z=(p-1)*(q-1)；
3，任取一個與z互素的整數e；
4，計算滿足e*d=1 mod z 的整數d；
5，將明文m分成字符塊s加密，每個塊s小于n。現設明文m小于n，加密后形成密文c。 加密、解密過程如下:
加密：c=m^e mod n
解密：m=c^d mod n
6，(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)進行計算，得出代表乙身份的編碼：
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等加密算法……
三：具體實踐。
/* RSA Demo 1.0 版
* 版權所有 (C) 2004 趙春生
* 2004.04.25
* http://timw.yeah.net
* http://timw.126.com
* 本程序調用Miracl ver 4.82大數運算庫，詳見其附帶手冊。
* P,Q,N,D,E使用RSATool2生成。
*/
1，注冊機的關鍵代碼：
void CKeyGenDlg::OnGen()
{
// TODO: Add your control notification handler code here
/* KeyGen 1.0 版
* 版權所有 (C) 2004 趙春生
* 2004.04.25
* http://timw.yeah.net
* http://timw.126.com
* 本程序調用Miracl ver 4.82大數運算庫，詳見其附帶手冊。
*/
//////////////////////////////////////////////////////////////////////////
//P(HEX)=E34436F5F48A227B
//Q(HEX)=A92FA24467C4E3E3
//N(HEX)=963251DC5A9C90D9F203A03C363BA411
//D(HEX)=56157D29A89D77BF2F669A8F0B123CC9
//E(HEX)=10001
//Keysize(Bits)=128
UpdateData(TRUE);
int namelen=m_name.GetWindowTextLength (); //獲取Name的長度
//務必滿足：Name的長度<=(Keysize/8)，使M<N成立。
if (namelen!=0&&namelen<=16) //如果不為空且<=128/8則開始計算SN
{
miracl *mip=mirsys(100,0);
mip->IOBASE=16; //16進制模式
//定義并初始化變量
big m=mirvar(0); //m 放明文：注冊碼SN
big c=mirvar(0); //c 放密文：用戶名Name
big n=mirvar(0); //n 模數
big d=mirvar(0); //d 私鑰
TCHAR Name[256]={0};
TCHAR SN[256]={0};
m_name.GetWindowText (Name,namelen+1); //獲取Name
bytes_to_big(namelen,Name,c); //轉換成16進制
cinstr(n,"963251DC5A9C90D9F203A03C363BA411"); //初始化模數n
cinstr(d,"56157D29A89D77BF2F669A8F0B123CC9"); //初始化私鑰d
powmod(c,d,n,m); //計算m=c^d mod n
cotstr(m,SN); //將m以16進制串寫入SN
m_sn.SetWindowText (SN); //輸出16進制SN
//釋放內存
mirkill(m);
mirkill(c);
mirkill(n);
mirkill(d);
mirexit();
}
else
m_sn.SetWindowText ("Error: Invalid registration name.");
UpdateData(FALSE);
}
2，軟件中注冊程序的關鍵代碼：
void CRSAApplicationDlg::OnReg()
{
// TODO: Add your control notification handler code here
/* RSA Application 1.0 版
* 版權所有 (C) 2004 趙春生
* 2004.04.25
* http://timw.yeah.net
* http://timw.126.com
* 本程序調用Miracl ver 4.82大數運算庫，詳見其附帶手冊。
*/
//////////////////////////////////////////////////////////////////////////
//P(HEX)=E34436F5F48A227B
//Q(HEX)=A92FA24467C4E3E3
//N(HEX)=963251DC5A9C90D9F203A03C363BA411
//D(HEX)=56157D29A89D77BF2F669A8F0B123CC9
//E(HEX)=10001
//Keysize(Bits)=128
UpdateData(TRUE);
miracl *mip=mirsys(100,0);
mip->IOBASE=16; //16進制模式
//定義并初始化變量
big m=mirvar(0); //m 放明文：注冊碼SN
big c=mirvar(0); //c 放密文：用戶名Name
big n=mirvar(0); //n 模數
big e=mirvar(0); //e 公鑰
TCHAR Name[256]={0};
TCHAR SN[256]={0};
TCHAR temp[256]={0};
int len=0;
int i,j;
//獲取Name
len=m_name.GetWindowTextLength ();
m_name.GetWindowText (Name,len+1);
//獲取SN
len=m_sn.GetWindowTextLength ();
m_sn.GetWindowText (SN,len+1);
//檢查SN是否為16進制
for (i=0,j=0;i<len;i++)
{
if(isxdigit(SN[i])==0)
{
j=1;
break;
}
}
//如果輸入的SN為16進制且長度不為0
if (j!=1&&len!=0)
{
cinstr(m,SN); //初始化明文m
cinstr(n,"963251DC5A9C90D9F203A03C363BA411"); //初始化模數n
cinstr(e,"10001"); //初始化公鑰e
//當m<n時
if(compare(m,n)==-1)
{
powmod(m,e,n,c);//計算c=m^e mod n
big_to_bytes(256,c,temp,FALSE);//將c轉換成數組寫入temp
//釋放內存
mirkill(m);
mirkill(c);
mirkill(n);
mirkill(e);
mirexit();
}
else
j=1;
}
//對Name、temp， m、n， SN的長度進行檢查
if(lstrcmp(Name,temp)!=0||j==1||len==0)
MessageBox("Please check your NAME and SN, then try again.","RSA Application");
else
MessageBox("Congratulate!!!","Registration complete!");
UpdateData(FALSE);
}
//////////////////////////////////////////////////////////////////////////////////
編譯提示：
1：將Project-Settings-Settings For(All Configuration)-C/C++中Category項的
Precompiled Headers設置成：Automatic use of precompiled headers（圖1）。
2：將ms32.lib添加到工程中（圖2）。
3：MIRACL是C庫。
extern "C"
{
#include "miracl.h"
#include "mirdef.h"
}
#pragma comment( lib, "ms32.lib" )
四：以上代碼在Win2000P+SP4 + VC6+SP5測試通過。
RSA Demo 1.0源碼可從我的個人主頁下載。
http://timw.yeah.net
http://timw.126.com
14:15 2004-4-26
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -