【文章內容簡介】 驗證過程：接收方使用發(fā)送方的公鑰 e 對收到的消息 y 進行數字簽名驗證變換 x’ =ye mod N，并使用發(fā)送方的密鑰解密恢復消息 x，比較 x’與 x，如果 x’=x 則證實發(fā)送方的身份合法。 這樣，用戶 A 若想用 RSA 簽名方案對消息 x 簽名，他只需公開他的公鑰 N和 e，由于簽名算法是保密的，因此 A 是唯一能產生簽名的人，任何要驗證用戶A 簽名的用 戶只需查到 A 的公鑰即可驗證簽名。 對于實現簽名和公鑰加密的組合，常用方法是：假定通信雙方為 A 和 B。對于明文 x， A 計算他的簽名 y=x d mod N，然后利用 B 的公開加密函數 EB對信息對 (x, y)加密得到 Z，將密文 Z 傳送給 B，當 B 收到密文 Z 后，他首先用他的解密函數 DB來解密得到 (x， y)=DB (Z)= DB (EB(x， y))，然后利用 A 的驗證算 法來檢查 x’ =x=y e mod N 是否成立。 大數運算處理． RSA 依賴大數運算，目前主流 RSA 算法都建立在 1024 位的大數運算之上。而大多數的編譯器 只能支持到 64 位的整數運算，即我們在運算中所使用的整數必須小于等于 64 位，即： 0xffffffffffffffff 也就是 18446744073709551615，這遠遠達不到 RSA 的需要，于是需要專門建立大數運算庫來解決這一問題。最簡單的辦法是將大數當作數組進行處理，數組的各元素也就是大數每一位上的數字，通常采用最容易理解的十進制數字 0~9。然后對“數字數組”編寫加減乘除函數。但是這樣做效率很低，因為二進制為 1024 位的大數在十進制下也有三百多位，對于任何一種運算，都需要在兩個有數百個元素的數組空間上多次重 循環(huán)，還需要許多額外的空間存放計算的進退位標志及中間結果。另外，對于某些特殊的運算而言， 采用二進制會使計算過程大大簡化，而這種大數表示方法轉化成二進制顯然非常麻煩，所以在某些實例中則干脆采用了二進制數組的方法來記錄大數，當然這樣效率就更低了。一個有效的改進方法是將大數表示為一個 n 進制數組，對于目前的 32 位系統(tǒng)而言 n 可以取值為 2 的 32 次方，即 0x100000000，假如將一個二進制為 1024 位的大數轉化成 0x10000000 進制，就變成了 32 位，而每一位的取值范圍不再是二進制的 0~ 1 或十進制的 0~9，而是 0~0xffffffff 我們正好可以用一個 32 位的 DWORD(如：無符號長整數， unsigned long)類型來表示該值。所以 1024 位的大數就變成一個含有 32 個元素的 DWORD 數組，而針對DWORD 數組進行各種運算所需的循環(huán)規(guī)模至多 32 次而已。 例如大數 1 8446744073709551 61 5，等于 0Xffffffff ffffffff 其表示方式就相當于十進制的 99：有兩位，只是每位上的元素不是 9 而都是 0xffffffff。而18446744073709551616 等于 0x00000001 00000000 00000000，就相當于十進制的100：有三位，第一位是 l，其它兩位都是 0，如此等等。在實際應用中，“數字數組 的排列順序采用低位在前高位在后的方式，這樣，大數 A 就可以方便地用 數學表達式來表示其值： X=Σ Xi r i (r=0x100000000， 0Xi r) 任何整數運算最終都能分解成數字與數字之間的運算，在 Oxl00000000 進制下其“數字 最大達到 Ox 靦筒，其數字與數字之間的運算，結果也必然超出了目前 32 位系統(tǒng)的字長。在 VC++中，存在一個 int64 類型可以處理 64 位的整 數，所以不用擔心這一問題，而在其它編譯系統(tǒng)中如果不存在 64 位整形，就需要采用更小的進制方式來存儲大數，例如 16 位的 WORD 類型可以用來表示 0x10000進制。但效率更高的辦法還是采用 32 位的 DWORD 類型。 大素數的產生 根據 RSA 算法的加解密變換，需要產生兩個保密的大素數作為基礎運算。在 2021 年前歐幾里德證明了素數有無窮多個，這自然的就引出一個問題：既然素數有無窮個，那么是否有一個計算素數的通項公式 ?兩千年來，數論學的一個重要任務，就是尋找一個可以表示全體素數的素數普遍公式。為此，人類耗費了巨大的心血。希爾伯特認為，如果有了素數統(tǒng)一的素數普遍公式，那么這些哥德巴赫猜想和孿生素數猜想都可以得到解決。“研究各種各樣的素數分布狀況，一直是數論中最重要和最有吸引力的中心問題之一。關于素數分布性質的許多著名猜想是通過數值觀察計算和 初步研究提出的，大多數至今仍未解決”。因此，欲得到素數，必須另尋出路。 大素數的產生應是現代密碼學應用中最重要的步驟。幾乎所有的公開密鑰系統(tǒng)均需要用到大的素數，若此素數選用不當，則此公開密鑰系統(tǒng)的安全性就岌岌可危。一般而言，素數的產生通常有兩種方法，一為確定性素數產生方法，一為概率性素數產生方法，目前后者是當今生成素數的主要方法。所謂概率性素數產生法，是指一種算法，其輸入為一奇數，輸出為兩種狀態(tài) YES 或 NO 之一。若輸入一奇數 n，輸出為 NO，則表示 11 為合數，若輸出為 YES，則表示 n 為素數的概率為 1r，其中 r 為此素數產生法中可控制的任意小數，但不能為 0。此類方法中較著名的有 SolovayStrassen 算法、 Lehmann 算法、 MillerRabin 算法等。在實際應用中，一般做法是先生成大的隨機整數，然后通過素性檢測來測試其是否為素數。數論學家利用費爾馬定理研究出了多種素數測試方法，目前最快的算法是MillerRabin(拉賓米勒 )測試算法 (也稱為偽素數檢測 )，其過程如下：首先選擇一個待測的隨機數 N 計算 r， 2r是能夠整除 N1 的 2 的最大冪數。 1．計算 M，使得 N=2r M+1。 2．選擇隨機數 AN。 3．若 AM mod N =l，則 N 通過隨機數 A 的測試。 4．讓 A 取不同的值對 N 進行 5 次測試，若全部通過則判定 N 為素數。 若 N 通過一次測試，則 N 為合數 (非素數 )的概率為 25％，若 N 通過 t 次測試，則為合數 (非素數 )的概率為 1／ 4t。事實上取 t 為 5 時， N 為合數的概率為 1／ 128， N 為素數的概率已經大于 99． 99％。 5. RSA 的安全性 密碼學所討論的系統(tǒng)，其安全性是最高的評價準則。再好的密碼系統(tǒng)，若安全性不足則一文不值，同時，密碼系統(tǒng)的安全性很難用理論證明 (事實上證明一個安全系統(tǒng)是安全的很難，但若該系統(tǒng)不安 全，證明它是不安全的則很容易 ). RSA 從提出到現在已近二十年，經歷了各種攻擊的考驗，逐漸為人們接受，普遍認為是目前最優(yōu)秀的公鑰方案之一。但是在特定的條件下， RSA 實現細節(jié)的疏忽會導致對 RSA 算法的有效攻擊。因此，對 RSA 體制實現的各個環(huán)節(jié)進 行充分考慮，避免安全性缺陷是非常有必要的。 RSA 的安全性分析 : 理論上， RSA 的安全性取決于因式分解模數 N 的困難性。從嚴格的技術角度上來說這是不正確的，在數學上至今還未證明分解模數就是攻擊 RSA 的最佳方法， 也未證明分解大整數就是 NP 問題 (表示那些能在多項式時間內 利