基于哥德巴赫猜想的公鑰加密算法
admin 使用過公鑰加密算法的朋友們都知道，公鑰加密算法的核心是尋找陷門單向函數(shù)，利用該函數(shù)求逆的不可行性，對(duì)發(fā)送的消息進(jìn)行加密，從而實(shí)現(xiàn)通信的保密和網(wǎng)絡(luò)安全。鑒于上述原因，我們根據(jù)數(shù)學(xué)難題“哥德巴赫猜想”設(shè)計(jì)出了一種新的公鑰加密算法，下面我們就給大家介紹一下這種基于哥德巴赫猜想的公鑰加密算法。
基于哥德巴赫猜想的公鑰加密算法
一、基于哥德巴赫猜想的公鑰加密算法描述
一個(gè)函數(shù)，若計(jì)算函數(shù)值很容易，并且在缺少一些附加信息時(shí)計(jì)算函數(shù)的逆是不可行的，但是已知這些附加信息時(shí)，可在多項(xiàng)式時(shí)間內(nèi)計(jì)算出函數(shù)的逆，那么我們稱這樣的函數(shù)為陷門單向函數(shù)。
定義陷門單向函數(shù)是滿足下列條件的一類不可逆函數(shù)fk：
（1）若k和X已知，則容易計(jì)算Y=fk(X)
（2）若k和Y已知，則容易計(jì)算X=fk-1(Y)
（3）若Y已知但k未知，則計(jì)算出X=fk-1(Y)是不可行的。
哥德巴赫提出這個(gè)猜想至今,許多數(shù)學(xué)家都不斷努力想攻克它,但都沒有成功。哥德巴赫猜想由此成為數(shù)學(xué)皇冠上一顆可望不可及的明珠 。
本文設(shè)計(jì)的公鑰密碼算法是基于哥德巴赫猜想，即假設(shè)哥德巴赫猜想成立，任何一個(gè)大于等于6的偶數(shù)，都可以表示成兩個(gè)奇素?cái)?shù)之和。給定一個(gè)大偶數(shù)，要求該偶數(shù)是由哪兩個(gè)素?cái)?shù)組成的，是很困難的。利用該特性，設(shè)計(jì)該公鑰加密算法。
二、基于哥德巴赫猜想的公鑰加密算法如下
（1）隨機(jī)選擇大素?cái)?shù)p、大素?cái)?shù)q；
（2）求N=p+q，判斷p與N是否互質(zhì)，如果互質(zhì)則執(zhí)行第（3）步；否則返回第（1）步；
（3）由aN+bp=1得到整數(shù)a，b；其中一個(gè)為負(fù)數(shù)；
定理1：如果兩正整數(shù)p，q互質(zhì)，則可以找到兩個(gè)整數(shù)a，b，使得ap+bq=1。顯然，兩個(gè)素?cái)?shù)一定是互質(zhì)的。
（4）所得的公鑰PUb為{N,b}，私鑰PRb為{p}；
（5）發(fā)送端發(fā)送明文M時(shí)，利用公鑰{N,b}進(jìn)行加密，則加密可表示為：C=(b_M)modN，其中C為密文；
（6）接收端接收密文C時(shí)，利用私鑰{p}進(jìn)行解密，則解密可表示為：M=(p_C)modN。下面以具體示例介紹該算法的加密、解密過程。
三、基于哥德巴赫猜想的公鑰加密算法的加密、解密過程
（1）隨機(jī)選擇素?cái)?shù)p=3，q=5。
（2）則N=p+q=3+5=8；且滿足p與N互質(zhì)的條件；
（3）由aN+bp=1，求出a=2，b=-5；
（4）所得的公鑰PUb為{8,-5}，私鑰PRb為{3}；
（5）當(dāng)發(fā)送端發(fā)送明文M=7時(shí)，可利用公鑰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}對(duì)密文C進(jìn)行解密，解密過程為:M=(p_C)modN=(3_5)mod8=(3_5)mod8=7
這說明加密前的明文M和解密后的消息M是一致的。
四、基于哥德巴赫猜想的公鑰加密算法證明
設(shè)發(fā)送端發(fā)送的明文為M，加密后的密文為C。已知N=p+q，其中p、q為素?cái)?shù)，且p與N互質(zhì)。
證明:由M=(p_C)modN可得M#p_C(modN) （1）
因?yàn)镃=(b_M)modN，則可將上式轉(zhuǎn)化為如下形式：
M#(b_p_M(modN))(modN) （2）
因?yàn)閍N+bp=1，則將（2）轉(zhuǎn)化為如下形式：
M#((1-aN)_M(modN))(modN)M#((M-aNM)(modN))(modN) （3）
由模算術(shù)性質(zhì)，則可將（3）轉(zhuǎn)化為如下形式：
M#((MmodN)-(aNMmodN))(modN)M#(MmodN)(modN)
在實(shí)際加密過程中，可將消息M拆分為若干等分(如以字節(jié)為存儲(chǔ)單位)，則M必定遠(yuǎn)遠(yuǎn)小于N，所以解密后的M’和加密前明文M的一定是相同的。
小知識(shí)之哥德巴赫猜想：
在1742年給歐拉的信中哥德巴赫提出了以下猜想：任一大于2的整數(shù)都可寫成三個(gè)質(zhì)數(shù)之和。因現(xiàn)今數(shù)學(xué)界已經(jīng)不使用“1也是素?cái)?shù)”這個(gè)約定，原初猜想的現(xiàn)代陳述為：任一大于5的整數(shù)都可寫成三個(gè)質(zhì)數(shù)之和。歐拉在回信中也提出另一等價(jià)版本，即任一大于2的偶數(shù)都可寫成兩個(gè)質(zhì)數(shù)之和。今日常見的猜想陳述為歐拉的版本。把命題"任一充分大的偶數(shù)都可以表示成為一個(gè)素因子個(gè)數(shù)不超過a個(gè)的數(shù)與另一個(gè)素因子不超過b個(gè)的數(shù)之和"記作"a+b"。1966年陳景潤證明了"1+2"成立，即"任一充分大的偶數(shù)都可以表示成二個(gè)素?cái)?shù)的和，或是一個(gè)素?cái)?shù)和一個(gè)半素?cái)?shù)的和"。
