資源描述:
《置換多項式及rsa密碼體制的實現(xiàn)》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、置換多項式及RSA密碼體制的實現(xiàn)摘要:傳統(tǒng)的密碼編制體制有著較多的缺陷,得益于置換多項式的諸多優(yōu)點提出了RSA密碼體制,很好的保證了密碼體制的安全性。其中迪克遜多項式和有理置換函數(shù)在RSA系統(tǒng)中有重大的意義。關(guān)鍵字:置換多項式RSA系統(tǒng)迪克遜多項式置換多項式正文:第一章:置換多項式的簡單性質(zhì)數(shù)學(xué)王子高斯在1801年的著作《算術(shù)探討》首先提出了完全剩余系的問題。設(shè)m是一個正整數(shù),從模m的每一個剩余類中選取一個代表元組成的集,稱為模m的一個完全剩余系。例如,組成的模m的一個完全剩余系,也組成模m的一個完全剩余系。完全剩余系的最簡單的構(gòu)造是,這里a是與m互素的一個整數(shù)
2、。所以,可以用簡單的線性多項式表示。即當(dāng)x取值0,1,...,m-1時,剛好是所構(gòu)造的完全剩余系。于是,有了置換多項式的定義:定義:設(shè)是一整系數(shù)多項式,如果當(dāng)x為模m的一個完全剩余系時,也為模m的一個完全剩余系,則稱是模m的置換多項式。也即,導(dǎo)出的一個置換。不加證明的得到置換多項式的幾條簡單的性質(zhì):性質(zhì):從知,是模m的置換多項式相當(dāng)于是模m的一個完全剩余系。性質(zhì):設(shè),,是模m的兩個置換多項式,,則不是模m的置換多項式。需要注意的是,當(dāng)m為奇數(shù)時,性質(zhì)不成立。例如,取,,,則是模5的置換多項式,而11/11也是模5的置換多項式。性質(zhì):設(shè),是模m的兩個置換多項式,則
3、乘積不是模m的置換多項式。性質(zhì):設(shè)是m的標準分解式,則是模m的置換多項式當(dāng)且僅當(dāng)是模的置換多項式。第二章:迪克遜多項式有了置換多項式的這些基本的性質(zhì),我們著重的學(xué)習(xí)一類非常重要的置換多項式,即迪克遜多項式。定義迪克遜多項式如下:,其中,表示實數(shù)b的整數(shù)部分。易得等式=,特別的,當(dāng)a=0時有=。下面證明兩個非常重要的定理。定理:設(shè)。則由迪克遜多項式是的置換多項式當(dāng)且僅當(dāng),=1;是得正則置換多項式當(dāng)且僅當(dāng)=1。證明:首先證明定理的第一部分。設(shè)=1。若有b,c使得=,只需證明b=c在的某一個二次擴域中取一非零元使;同樣又在的另一個二次擴域中取一非零元使。又因為的所有二
4、次擴域都是同構(gòu)的,所以,和都可以在的同一個二次擴域中選取。11/11則有,===。因此,。由此有=或=。無論哪種情況都有。即是的置換多項式。反證法。設(shè)=d,若,則,p不能被2整除,則只含x的偶數(shù)次方冪,因此對所有有=。而,固不是的置換多項式。下設(shè)2不能被d整除,則有d的奇數(shù)因子r,,或。分兩種情況:當(dāng)時,方程在中有r個解,因此存在b,,,a。于是,則可以得到==,又,a。所以,這樣就不是的置換多項式。當(dāng)時,設(shè)是的二次擴域中的一元,使得。因為,在中有r個解,于是存在,=1,,。這樣就有,且=。因為,中的所有零點組成,故有,=。因為,,,所以則有,,因此不是的置換多
5、項式。下面證明定理的第二部分。我們有=,對x求導(dǎo),可得=-11/11,因此有==,。如果是的正則置換多項式,則有在中無零點。而從上式可以得到p不能被k整除。結(jié)合定理的第一部分得到=1。反過來,設(shè)=1。若有s,使得,在的某二次擴域中任取一元使得,代入式得=0。于是有=,從=1得,因此有,所以必有,得出矛盾。故是得正則置換多項式。定理(二)在多項式的合成運算下是封閉的當(dāng)且僅當(dāng),且此時還有關(guān)系,因此是由的置換多項式作成的一個交換群(阿貝爾群)。證設(shè),則由(1.6)得(1.10)如果在合成運算下是封閉的,則有在中,比較的次數(shù)得11/11再由(1.10)知因不是常數(shù),故又
6、有當(dāng)時,比較的系數(shù)得。如果,因,則,再從得。反過來,若,由上述過程驗證知在合成運算下是封閉的?!跎鲜龆ɡ肀砻鳎?dāng)時,作成一交換群。第三章:置換多項式及RSA密碼體制的實現(xiàn)置換多項式在公開密碼中有非常重要的應(yīng)用。通訊就是發(fā)送或接受信息。在發(fā)送信息時,需要先將被發(fā)送的信息轉(zhuǎn)換成數(shù)字。例如,在英文中有26個字母,設(shè)a=0,b=1,、、、,x=23,y=24,z=25。這樣,信息便可被轉(zhuǎn)換為一組數(shù)字。既然信息可看成一組數(shù)字,因此,對信息加密的問題就可轉(zhuǎn)化為對數(shù)字編碼的問題。最簡單的編碼方法是將26個字母放在圓周上,每一個字母經(jīng)編碼后變成它后面的一個字母。用對應(yīng)的數(shù)字來說
7、,編碼就是同余式(1)其中,對應(yīng)于要發(fā)送的字母,對應(yīng)于編碼后的字母。例如,假設(shè)需要發(fā)送的信息是secret第一步,將其轉(zhuǎn)換成對應(yīng)的數(shù)字得到184217419第二步,利用同余式(1)編碼得到195318520第三步,再轉(zhuǎn)換成對應(yīng)的字母得到tfdsfu11/11這就是secret的密文。同樣,接收方在收到密文時,可利用進行解碼。所以,可以看到密碼編制的基本原理。假設(shè)發(fā)送信息的一方為,接受信息的一方為,收方有密碼鑰匙,發(fā)方有加密鑰匙。這兩個密碼是互逆的。即有假設(shè)要發(fā)送一個密碼信息,發(fā)方將用加密得到,然后將此密文發(fā)出。收方得到密文后,用解密鑰匙作用于密文上即得這樣就獲得
8、了原始信息。然而這種傳統(tǒng)