一：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