RSA算法和RSA數字簽名算法的實作

RSA算法和RSA數字簽名算法的實作*

顧婷婷    李濤

（四川大學計算機系(西區) 成都 610065）

摘要 RSA算法是一種公鑰密碼算法.實作RSA算法包括生成RSA密鑰，用RSA加密規則和解密規則處理資料。RSA數字簽名算法利用RSA算法實作數字簽名。本文詳述了RSA算法的基本原理, RSA加密算法的實作以及如何利用RSA實作數字簽名. 關鍵字 RSA算法, 數字簽名, 公開密鑰, 私人密鑰, 加密, 解密 中圖分類号 TP301 一、引言

随着網絡技術的飛速發展，資訊安全性已成為亟待解決的問題。公鑰密碼體制中，解密和加密密鑰不同，解密和加密可分離，通信雙方無須事先交換密鑰就可建立起保密通信，較好地解決了傳統密碼體制在網絡通信中出現的問題。另外，随着電子商務的發展，網絡上資金的電子交換日益頻繁，如何防止資訊的僞造和欺騙也成為非常重要的問題。數字簽名可以起到身份認證、核準資料完整性的作用。目前關于數字簽名的研究主要集中基于公鑰密碼體制的數字簽名。

公鑰密碼體制的特點是：為每個使用者産生一對密鑰（PK和ＳＫ）；ＰＫ公開，ＳＫ保密；從ＰＫ推出ＳＫ是很困難的；Ａ、Ｂ雙方通信時，Ａ通過任何途徑取得Ｂ的公鑰，用Ｂ的公鑰加密資訊。加密後的資訊可通過任何不安全信道發送。Ｂ收到密文資訊後，用自己私鑰解密恢複出明文。

公鑰密碼體制已成為確定資訊的安全性的關鍵技術。RSA公鑰密碼體制到目前為止還是一種認可為安全的體制。本文詳述了RSA算法和用RSA算法實作數字簽名的理論，以及它們在實際應用中的實作。

二、RSA算法和RSA數字簽名算法的理論描述 1  RSA 算法

   RSA算法的理論基礎是一種特殊的可逆模幂運算。

   設n是兩個不同奇素數p和q的積，即：n=pq, j(n)=(p-1)(q-1)。

   定義密鑰空間

 k

={(n,p,q,d,e)|n=pq,p和q是素數，deº1 mod j(n),e為随機整數},

   對每一個

k

=(n,p,q,d,e),

   定義加密變換為   Ek(x)=xb mod n，xÎZn;

   解密變換為       Dk(x)=ya mod n,yÎZn，Zn為整數集合。

   公開n和b，保密p,q和a.

   為證明加密變換Ek和解密變換 Dk滿足Dk(Ek(x))=x,這裡不加證明的引用下面兩個定理：

定理1（Euler）對任意的a Î Zn*,有a j (n) º 1 mod n,其中Zn*={x Zn|gcd(x,n)=1}, (·)表示Euler函數。 定理2  設p和q是兩個不同的素數，n=pq, (n)=(p-1)(q-1)，對任意的x Zn及任意的非負整數k,有 xk (n)+1 x mod n.

現在來證明RSA算法的加密變換和解密變換的正确性。

證明：  對于加密變換Ek和解密變換Dk。因為abº1 mod j(n)，是以可設ab=tj(n)+1,t是整數且t³1。對于任意的xÎZn，有Dk(Ek(x))ºDk(xb) º(xb)aºxtj(n)+1ºx mod n.是以解密過程是正确的。

2 RSA數字簽名算法

   RSA數字簽名算法的過程為：A對明文m用解密變換作: sº Dk (m)=md mod n,其中d，n為A的私人密鑰，隻有A才知道它；B收到Ａ的簽名後，用A的公鑰和加密變換得到明文，因: Ek(s)= Ek(Dk (m))= (md)e mod n,又 deº1 mod j(n)即de=lj(n)+1,根據歐拉定理mj(n)=1 mod n，是以Ek(s)=mlj(n)+1=[mj(n)]em=m mod n。若明文m和簽名s一起送給使用者B,B可以确信資訊确實是A發送的。同時A也不能否認送給這個資訊，因為除了A本人外，其他任何人都無法由明文m産生s.是以RSA數字簽名方案是可行的。

   但是RSA數字簽名算法存在着因計算方法本身同構造成簽名易被僞造和計算時間長的弱點,是以實際對檔案簽名前，需要對消息做MD5變換。

   MD5函數是一種單向散列函數，它将任意長度的消息壓縮成128位的消息摘要。應用MD5的單向性（即給定散列值,計算消息很難）和抗碰撞性(即給定消息M，要找到另一消息M’ 并滿足兩者的散列值很難)，可以實作資訊的完整性檢驗。另外該函數的設計不基于任何假設和密碼體制而直接構造，執行的速度快，是一種被廣泛認可的單向雜湊演算法。

三、RSA算法的實作 RSA算法的實作分為：生成密鑰，加密，解密。 1 資料結構 RSA密碼系統的安全性依賴于大數分解的難度，一般建議使用者選擇的素數p和q至少為100位，則n=pq是至少為200位的十進制數。是以實作RSA算法有必要定義大數的資料結構如圖一所示。

typedef struct {   unsigned long int bn[MAX_LENGTH];   unsigned int size; }BigNum              圖２ 大數的資料結構

密鑰生成，加密和解密涉及到一些大數的基本運算。定義大數的基本運算庫，包括加、減、乘、除、取模運算等，其中最重要的模乘運算和模幂運算。

模幂算法是加密解密的核心算法。計算模幂的一種有效算法是“平方-乘”方法，通過對指數的二進制化來實作。8

過程如圖1：

Procedure modmult

　 begin

typedef struct {   unsigned int bits; /* 公鑰n的位數  */   unsigned char modulus[MAX_RSA_ LEN] ;/*公鑰n*/             unsigned char exponent[MAX_RSA_LEN]; /*公鑰e*/ }  RSA_PUBLIC_KEY;                   圖３ RSA公鑰

Z=1

for i=l-1 downto 0 do:

      begin

             　  Z=Z 2 mod n;

     　　 if bi=1 then Z=Z*x mod n;

          end

    end

　　　 

圖一

2 密鑰的生成 2.1 RSA 公鑰和私鑰的結構定義

   根據文檔PKCS#1定義RSA公鑰和私鑰分别如圖2和圖3。理論上講，RSA私鑰隻需包括解密模數和解密指數。但是為加快RSA解密計算的效率，采用中國剩餘定理算法，是以RSA私鑰包含p,q,d mod (p-1),d mod (q-1),q-1 mod p,其中p,q為大素數, d mod (p-1),   d mod (q-1),q-1 mod p由計算過程生成。

2.2 生成密鑰步驟

unsigned int bits; /*公鑰n的長度*/   unsigned char modulus[MAX_RSA_LEN];  /*公鑰n */              unsigned char publicExponent[MAX_RSA_ LEN]; /*公鑰e */   unsigned char exponent[MAX_RSA_LEN];  /*私鑰d*/   unsigned char prime[2][MAX_RSA_ LEN]; /*兩個素數因子*/        unsigned char primeExponent[2][MAX_RSA_PRIME_LEN];   unsigned char coefficient[MAX_RSA_PRIME_LEN];  } RSA_PRIVATE_KEY;                 圖4  RSA私鑰

生成RSA密鑰需完成下列步驟：

  (1) 選擇e的值為3或者25537;

  (2) 随機生成大素數p，直到gcd (e,p-1)=1;

     其中gcd(a,b)表示a,b取最大公約數

  (3) 随機生成不同于p的大素數q，直到

     gcd (e,q-1)=1;

  (4) 計算n=pq , j(n)=(p-1)(q-1);

  (5) 計算d,滿足deº1 (mod j(n));

  (6) 計算d mod (p-1), d mod (q-1);

  (7) 計算q-1 mod p;

  (8) 将n,e放入RSA公鑰；将n,e,d mod (p-1),d mod (q-1) q-1 mod p放入RSA私鑰。

   随機素數的産生可分為兩個子產品：

2.2.1 随機數的産生

    随機數不僅用于密鑰生成,也用作公鑰加密時的填充字元。它必須具有足夠的随機性，以防止破譯者掌握随機數的規律性後重制密鑰的配制過程或者探測到加密塊中的明文。因為在計算機上不可能産生真正的随機數，實際采用周期大于2256位的僞随機序列發生器。

實作過程為：

    (1) 記錄相鄰兩次敲擊鍵盤的時間間隔，直到不再需要随機事件。

    (2) 做MD5計算，直到不再需要僞随機數。

2.2.2 素數的産生

    對随機數作素性檢測，若通過則為素數；否則增加一個步長後再做素性檢測，直到找出素數。素性檢測采用Fermat測試。這個算法的理論依據是費爾馬小定理：如果m是一個素數，且a不是m的倍數，那麼根據費爾馬小定理有：a m-1=1 ( mod m)。 實際應用時：a m-1 = 1 ( mod m)Û a m = a ( mod m) Ûa= a m ( mod m)， 是以對于整數m，隻需計算a m ( mod m)，再将結果與a比較，如果兩者相同，則m為素數。選取a=2，則a一定不會是任何素數的倍數。

3 加密過程

加密規則為：Ek(x)=xb mod n，xÎZn

加密過程的輸入為：明文資料D，模數n, 加密指數e（公鑰加密）或解密指數d（私鑰加密）。輸出為密文。D的長度不超過[log2n]-11，以確定轉換為PKCS格式時，填充串的數目不為0。

(1)    格式化明文。  采用PKCS格式： EB = 00 || BT || PS || 00 || D   其中BT表示塊的類型，PS為填充串，D為明文資料。開頭為0確定EB長度大于k。對公鑰加密BT=02，對私鑰解密BT=01。當BT=02時，PS為非0随機數；當BT=01，PS值為FF。

    (2) 明文由字元型資料轉換成整型資料。

    (3) RSA計算。  　為整數加密塊x作模幂運算：y = x^c mod n，0 <= y <n，其中y

       為密文，公鑰加密時，c為公鑰加密指數e；私鑰加密時，c為私鑰加密指數d。

    (4) 密文由整型資料轉換成字元型資料。

4 解密過程

  解密規則為      Dk(x)=yc mod n,yÎZn，Zn為整數集合,x為密文。

  解密過程的輸入為：密文ED；模數n；加密指數e（公鑰解密）或解密指數d（私鑰解密），結果為明文。

     (1) 密文整型化。

     (2) RSA計算。  對密文做模幂運算：x = y^c mod n,  0 <= x < n .，其中x為明文。

     (3) 此時明文為整型資料，轉換為ASCII型資料，得到PKCS格式的明文。

 (4) 從PKCS格式明文中分離出原明文。 從PKCS格式分離明文的過程也是檢查

    資料完整性的過程。若出現以下問題則解密失敗：不能清楚的分割；填充字元

    少于64位或與ＢＴ所注明的類型不比對;ＢＴ與實際操作類型不符。

四、           RSA 數字簽名算法的實作

RSA數字簽名算法，包括簽名算法和驗證簽名算法。首先用MD5算法對資訊作散列計算。簽名的過程需使用者的私鑰，驗證過程需使用者的公鑰。A用簽名算法将字元串形式的消息處理成簽名；B用驗證簽名算法驗證簽名是否是A對消息的簽名，确認是A發送的消息；消息沒有被攥改過；A一定發送過消息。

簽名算法

  簽名算法包括三步：消息摘要計算，RSA加密。

(1)    消息摘要計算。  消息在簽名前首先通過MD5計算，生成128位的消息摘要

      digest。

(2)    對摘要作RSA計算。  用加密算法，采用簽名者的私鑰加密消息摘要，得到加密後的字元串。加密算法中使用的加密塊為01類型。

驗證簽名算法

   驗證簽名算法包括兩步：RSA解密得簽名者的消息摘要，驗證者對原消息計算摘要，比較兩個消息摘要。驗證簽名的過程輸入為消息，簽名者的公鑰，簽名；輸出為驗證的結果，即是否是正确的簽名。

(1)    RSA解密。  簽名實際是加密的字元串。用3.5所述的解密算法，采用簽名者的公鑰對這個加密的字元串解密。解密的結果應為128位的消息摘要。在解密過程中，若出現得到的加密塊的類型不是01，則解密失敗。簽名不正确。

(2)    消息摘要計算和比較。  驗證者對消息用MD5算法重新計算，得到驗證者自己的消息摘要。驗證者比較解密得到的消息摘要和自己的消息摘要，如果兩者相同，則驗證成功，可以确認消息的完整性及簽名确實為簽名者的；否則，驗證失敗。

五、RSA算法的時間複雜性

   RSA算法的時間複雜性取決于它所設計的幾個基本運算的時間複雜性。

   密鑰生成過程時間主要是生成随機素數的時間及計算公鑰和私鑰的模乘法的時間。生成随機素數的時間在于完成對随機大數的Fermat測試的時間，Fermat測試的時間複雜度為O((log2n)3)，n所測試的整數。模乘法的計算方法采取先計算兩個數的乘積，再取模n，時間複雜性為O((log2n)2)。

   RSA加密解密計算的時間主要是模幂運算的時間，即形式為xc mod n的函數的運算時間。模幂算法采取平方乘算法，設l是c的長度，則計算xc mod n至多需要2l次模乘法，因為l£[log2n]+1,是以模幂運算能在時間O((log2n)3)内完成。是以，RSA的加密和解密均可在多項式時間内完成。

六、結束語

   本文讨論了RSA算法的基本原理和基本實作。RSA算法是一種安全技術，但是RSA算法的安全性隻是一種計算安全性，絕不是無條件的安全性，這是由它的理論基礎決定的。是以，在實作RSA算法的過程中，每一步都應盡量從安全性考慮。本文采取的一些主要算法是目前在數學上被認可的安全的算法之一。

    本文所提到的算法及實作原理已在作為設計的安全電子郵件系統中完全實作并獲得滿意的效果。

參   考   文   獻

[1]     盧開澄，清華大學出版社，《計算機密碼學》，1998

[2]     馮登國，裴定一，科學出版社，《密碼學導引》，1999

[3]    Burt Kaliski, Rfc 2313,  PKCS#1

The implement of RSA public-key algorithm and RSA signature algorithm

GU ting-ting     LI Tao

(Department of Computer,

Sichuan

University

Chengdu

610065)

Abstract

   The implement tenique of RSA public-key algorithm and RSA signature algorithm has been presented. RSA cryptosystem is a public-key cryptosystem .The key components of the implement are keys generation ,encryption and decryption. Therefore, the big number structure and its operations, then generation of the big prime, as well as the details of the implemention of encryption and decryption have thus been presented.

Key words

  RSA algorithm; digital signature; public key; secret key; encryption; decryption

*本文受國家自然科學基金以及四川省學術帶頭人基金的資助。

顧婷婷，碩士生，李濤，教授，主要研究領域：人工智能與神經網絡。