《RSA 數(shù)學(xué)基礎(chǔ)分析》2100字

RSA數(shù)學(xué)基礎(chǔ)分析目錄TOC\o"1-2"\h\u21475RSA數(shù)學(xué)基礎(chǔ)分析 1105191.1數(shù)論的基礎(chǔ)知識(shí) 189031.1.2素?cái)?shù)與合數(shù) 2325161.1.3互質(zhì)數(shù) 2119871.2模算術(shù)運(yùn)算 3124151.2.1模運(yùn)算的概念 372011.2.2模運(yùn)算的性質(zhì) 3234141.3歐拉定理及相關(guān)概念 4迄今為止,大部分的公鑰密碼體制算法都是一套由一些數(shù)學(xué)難題作為其理論基礎(chǔ)的加解密機(jī)制,其中,大整數(shù)的分解困難等問(wèn)題也就是RSA加密算法研究的基礎(chǔ)。和其他大部分公鑰密碼體制一樣,其加密算法的逆元問(wèn)題決定了RSA加密算法安全性的強(qiáng)弱。換句話說(shuō),求把任意的兩個(gè)大的素?cái)?shù)相乘所得的結(jié)果相對(duì)還是可以很容易得的,但是如果把每一個(gè)正大數(shù)都拆分成這兩個(gè)大素?cái)?shù)的話還是有非常多困難的。所以說(shuō),我們要把這樣類型的密碼函數(shù)取名叫為單向密碼函數(shù)。在當(dāng)今我們每天所必須接觸用到的各種密碼學(xué)工具中,單向密函數(shù)在它們其中也占比量很大,構(gòu)建這樣一個(gè)公鑰密碼體制,單向函數(shù)也是非常重要的。在此部分,為了更好地了解RSA加密算法,我將對(duì)數(shù)論中與之相關(guān)的部分做一下基本的介紹。1.1數(shù)論的基礎(chǔ)知識(shí)定義1:假設(shè)m和n為兩個(gè)任意的整數(shù),n不等于0,如果存在一個(gè)整數(shù)r,讓m等于nr,那么就把n叫做m的公因數(shù),m也是n的倍數(shù),m可被n整除,可記作n|m。定義2:假設(shè)m和n為兩個(gè)整數(shù),如果存在一個(gè)整數(shù)r,使m可被r整除,n也可被r整除,那么r就是m和n的公因數(shù),其中,在公因數(shù)里最大的那個(gè)公因數(shù)叫做最大公因數(shù)。定理1:假設(shè)m和n是兩個(gè)整數(shù),如果m等于q乘以n加r,那么q為商,r為其余數(shù),r小于n,則m和n的最大公因數(shù)等于n和r的最大公因數(shù)。證明:假設(shè)d為m和n的最大公因數(shù),d1為n和r的最大公因數(shù)由m等于q乘n加r,m減q乘n等于r,已知r可被d整除,由n可被d整除及r可被d整除,故d1可被d整除。反過(guò)來(lái),d1是n和r的最大公因數(shù),m等于q乘n加r,所以m可被d1整除,由m可被d1整除及n可被d1整除,故d可被d1整除。由d1可被d整除和d可被d1整除,可知d等于d1,所以m和n的最大公因數(shù)等于n和r的最大公因數(shù)。1.1.2素?cái)?shù)與合數(shù)取一個(gè)大于一的整數(shù)p,如果1和它本身為p僅有的兩個(gè)因子,那么我們就把p叫做質(zhì)數(shù),如果p不僅僅有1和它本身兩個(gè)因子,那么我們就把p叫做合數(shù)。既不是只有一個(gè)正質(zhì)數(shù)也就不是負(fù)整合正數(shù)負(fù)的負(fù)質(zhì)數(shù)中也有很多個(gè)負(fù)數(shù),0之和才是正負(fù)1,素?cái)?shù)的個(gè)數(shù)也是有無(wú)限窮高的,而且是對(duì)其中任意數(shù)的任意一個(gè)的負(fù)正質(zhì)整數(shù),把將其分解成乘積的形式,此乘積中的所有乘數(shù)都可以是質(zhì)數(shù)。公式1:整數(shù)n的標(biāo)準(zhǔn)分解式:n等于p1的e1次方乘p2的e2次方乘p3的e3次方乘p4的e4次方乘一直乘到pm的em次方。其中p1小于p2小于p3小于p4直到小于pm,ei為零或正整數(shù)。在這個(gè)公式中,如果n的取值到達(dá)非常大的時(shí)候,那么如果想要求出n的標(biāo)準(zhǔn)分解式是十分困難的,也正因?yàn)檫@樣的困難的公式,才使得RSA算法的安全性得到了強(qiáng)有力的保證,這也是RSA算法中較為突出的優(yōu)點(diǎn),也是RSA算法中非常重要的特質(zhì),所以RSA算法適合于大數(shù)方面的運(yùn)算。1.1.3互質(zhì)數(shù)m,n為兩個(gè)正整數(shù),如果1是m和n唯一的公因數(shù),那我們把這種特質(zhì)叫做m和n互質(zhì)。m1,m2,m3,m4.,mk為k的個(gè)正整數(shù),如果對(duì)于其中任意一點(diǎn)的i不等于j,且其中i大于或等于1,j都小于和等于k,ni和nj都是互質(zhì),那么現(xiàn)在我們便把這點(diǎn)k為個(gè)的正整數(shù)就叫做兩兩互質(zhì)。如果存在了一個(gè)同質(zhì)數(shù)p并使得另外兩個(gè)的正整數(shù)都可以與其互質(zhì),那么和這另外兩個(gè)的正整數(shù)相乘得的數(shù)值就也稱為和這個(gè)p的互質(zhì)。1.2模算術(shù)運(yùn)算1.2.1模運(yùn)算的概念A(yù)可以為一對(duì)任意一個(gè)整數(shù),n可為另一對(duì)正整數(shù),存在對(duì)應(yīng)著對(duì)唯一的對(duì)整數(shù)的q和的r,滿足設(shè)r大于或等于為零且n大于為r,a等于為q和與對(duì)n和的乘積再加為r,則可以稱作r是一個(gè)a的對(duì)數(shù)n和的模運(yùn)算。A如果除以所有n次方的算術(shù)商記為q,那么[x]就應(yīng)該表示為一個(gè)小于或至少等于這個(gè)x數(shù)的算術(shù)最大的整數(shù),所以,對(duì)其中任意的一個(gè)大整數(shù)的a都應(yīng)該可以這樣表示即為a=[a/n次方]n+amodn1.2.2模運(yùn)算的性質(zhì)數(shù)學(xué)中包含著模運(yùn)算的一些概念,我們可以通過(guò)這些概念發(fā)現(xiàn),幾乎是所有的整數(shù)的集合可以通過(guò)模運(yùn)算和n次模的運(yùn)算把他們直接的映射到另一個(gè)充滿了整數(shù)的集合中{0,1.,(n-1)}中,這種運(yùn)算的方式我們又習(xí)慣上稱他為模n運(yùn)算。模數(shù)運(yùn)算形式也是可以說(shuō)和許多其它的普通數(shù)學(xué)的數(shù)學(xué)運(yùn)算的形式極為相似,他這種形式同時(shí)也很特別地適用于分配律,交換律,結(jié)合律。交換律(x+y)modn=(y+x)modn(x*y)modn=(y*x)modn結(jié)合律((x+y)+z)modn=(x+(y+z))modn((x*y)*z)modn=(x*(y*z))modn(xmodn+ymodn)modn=(x+y)modn(xmodn*ymodn)modn=(x*y)modn分配律(x+y)modn=(xmodn+ymodn)modn(x*y)modn=(xmodn*ymodn)modn(x*(y+z))modn=(x*y+x*z)modn恒等式(0+x)modn=xmodn(1*x)modn=xmodn冪模運(yùn)算可以把其看成對(duì)應(yīng)次數(shù)的模成運(yùn)算例如15^7mod11=(15mod11)^7mod11=4^7mod11=×((4^2mod11)^3*4mod11)mod11=×(4mod114mod11)mod11=16mod11=51.3歐拉定理及相關(guān)概念數(shù)論領(lǐng)域中著名的歐拉定理也是建立RSA密碼體制必需的一個(gè)基礎(chǔ)理論。定理1:取一個(gè)正整數(shù)m,把正整數(shù)1到m中與m互為素?cái)?shù)的數(shù)的個(gè)數(shù)稱為?(m)此函數(shù)就叫做歐拉函數(shù)。定理2:如果整數(shù)a與m互為質(zhì)數(shù),那么a^?(m)≡1modm。證明:設(shè)?(m)=k,r1,r2,r3,r4...rk為1,2,...,m?1中和m互為素?cái)?shù)的數(shù)。因?yàn)閍與m互為素?cái)?shù),所以ari和m互為素?cái)?shù)。那么我們還需要證明ar1,ar2,...ark的模m互不相同。如果ari≡arjmodm,那么m|a(ri-rj),因?yàn)檎麛?shù)a和m互為素?cái)?shù),那么m|(ri-rj),就使得ri=rj,任意的i大于等于1,i小于等于k,ari和m互為素?cái)?shù),所以存在ari≡rjmodm,當(dāng)ri取遍r1,r2,...rk時(shí),rj也恰好取遍r1,r2,...rk,通過(guò)模運(yùn)算的結(jié)合律可知,a^kr1r2.rk≡r1r2.rkmodm,又因?yàn)閞1,r2,.rk和m互為素?cái)?shù),那么a^k≡1modm。證畢。定義1:如果對(duì)于我們而