使用過公鑰加密算法的朋友們都知道，公鑰加密算法的核心是尋找陷門單向函數(shù)，利用該函數(shù)求逆的不可行性，對發(fā)送的消息進行加密，從而實現(xiàn)通信的保密和網(wǎng)絡安全。鑒于上述原因，我們根據(jù)數(shù)學難題“哥德巴赫猜想”設計出了一種新的公鑰加密算法，下面我們就給大家介紹一下這種基于哥德巴赫猜想的公鑰加密算法。

基于哥德巴赫猜想的公鑰加密算法

一、基于哥德巴赫猜想的公鑰加密算法描述

一個函數(shù)，若計算函數(shù)值很容易，并且在缺少一些附加信息時計算函數(shù)的逆是不可行的，但是已知這些附加信息時，可在多項式時間內(nèi)計算出函數(shù)的逆，那么我們稱這樣的函數(shù)為陷門單向函數(shù)。

定義陷門單向函數(shù)是滿足下列條件的一類不可逆函數(shù)f_k：

（1）若k和X已知，則容易計算Y=f_k(X)

（2）若k和Y已知，則容易計算X=f_k^-1(Y)

（3）若Y已知但k未知，則計算出X=f_k^-1(Y)是不可行的。

哥德巴赫提出這個猜想至今,許多數(shù)學家都不斷努力想攻克它,但都沒有成功。哥德巴赫猜想由此成為數(shù)學皇冠上一顆可望不可及的明珠 。

本文設計的公鑰密碼算法是基于哥德巴赫猜想，即假設哥德巴赫猜想成立，任何一個大于等于6的偶數(shù)，都可以表示成兩個奇素數(shù)之和。給定一個大偶數(shù)，要求該偶數(shù)是由哪兩個素數(shù)組成的，是很困難的。利用該特性，設計該公鑰加密算法。

二、基于哥德巴赫猜想的公鑰加密算法如下

（1）隨機選擇大素數(shù)p、大素數(shù)q；

（2）求N=p+q，判斷p與N是否互質，如果互質則執(zhí)行第（3）步；否則返回第（1）步；

（3）由aN+bp=1得到整數(shù)a，b；其中一個為負數(shù)；

定理1：如果兩正整數(shù)p，q互質，則可以找到兩個整數(shù)a，b，使得ap+bq=1。顯然，兩個素數(shù)一定是互質的。

（4）所得的公鑰PUb為{N,b}，私鑰PRb為{p}；

（5）發(fā)送端發(fā)送明文M時，利用公鑰{N,b}進行加密，則加密可表示為：C=(b_M)modN，其中C為密文；

（6）接收端接收密文C時，利用私鑰{p}進行解密，則解密可表示為：M=(p_C)modN。下面以具體示例介紹該算法的加密、解密過程。

三、基于哥德巴赫猜想的公鑰加密算法的加密、解密過程

（1）隨機選擇素數(shù)p=3，q=5。

（2）則N=p+q=3+5=8；且滿足p與N互質的條件；

（3）由aN+bp=1，求出a=2，b=-5；

（4）所得的公鑰PUb為{8,-5}，私鑰PRb為{3}；

（5）當發(fā)送端發(fā)送明文M=7時，可利用公鑰PUb={8,-5}加密，則加密過程為：C=(b_M)modN=(-5_7)mod8=-35mod8=5

說明：定義整數(shù)x除以正整數(shù)n所得的余數(shù)為x模n，則可以寫出x=x/n_n+(xmodn)。

（6）接收端利用PRb={3}對密文C進行解密，解密過程為:M=(p_C)modN=(3_5)mod8=(3_5)mod8=7

這說明加密前的明文M和解密后的消息M是一致的。

四、基于哥德巴赫猜想的公鑰加密算法證明

設發(fā)送端發(fā)送的明文為M，加密后的密文為C。已知N=p+q，其中p、q為素數(shù)，且p與N互質。

證明:由M=(p_C)modN可得M#p_C(modN) （1）

因為C=(b_M)modN，則可將上式轉化為如下形式：

M#(b_p_M(modN))(modN) （2）

因為aN+bp=1，則將（2）轉化為如下形式：

M#((1-aN)_M(modN))(modN)M#((M-aNM)(modN))(modN) （3）

由模算術性質，則可將（3）轉化為如下形式：

M#((MmodN)-(aNMmodN))(modN)M#(MmodN)(modN)

在實際加密過程中，可將消息M拆分為若干等分(如以字節(jié)為存儲單位)，則M必定遠遠小于N，所以解密后的M’和加密前明文M的一定是相同的。

admin

收藏 海報分享