rsa與大系數(shù)的數(shù)字簽名

rsa與大系數(shù)的數(shù)字簽名

0rsa公開密鑰體制1976年，迪夫和赫爾曼在《新雇員理論》（新雇員理論）一書中首次提出了公鑰密碼系統(tǒng)的概念。1978年，r.r.r.a.shamor和l.adleman首次實(shí)施了公鑰密碼系統(tǒng)，現(xiàn)在被稱為sra公鑰系統(tǒng)。迄今為止,它在理論上被稱為最為成熟完善的公鑰密碼體制,在安全領(lǐng)域中得到廣泛的應(yīng)用。1r算法的原理1.1cvdjn①選取兩個(gè)未曾公開的的較大質(zhì)數(shù)p和q。②給定n=p?q,j(n)=(p-1)(q-1),其中j(n)是n的歐拉函數(shù)值。③選一整數(shù)e,滿足1<e<j(n),且gcd(j(n),e)=1。④計(jì)算d,滿足d?e°1modj(n),即在模j(n)下,d與e互為乘法逆元,由于e與j(n)互素,我們可以得知,一定存在e的乘法逆元d。⑤設(shè)定公鑰是{e,n},私鑰是{d,n}。1.2應(yīng)的十進(jìn)制數(shù)首先將明文二進(jìn)制代碼分組,使得每個(gè)分組的二進(jìn)制代碼對(duì)應(yīng)的十進(jìn)制數(shù)小于n,即分組長(zhǎng)度小于log2n。然后對(duì)每個(gè)明文分組m,對(duì)它進(jìn)行加密運(yùn)算而得到密文c:c°memodn,解密對(duì)密文分組的解密運(yùn)算為:m°cdmodn。2ra算法解密過程的準(zhǔn)確性的證明和示例2.1RSA的證明由加密過程知c°memodn,所以cdmodn漢medmodnn1modj(n)modn?mkj(n)+1modncdmodn漢medmodnn1modj(n)modn?mkj(n)+1modn下面分兩種情況討論:①m與n互素,則由歐拉定理得mj(n)°1modn,mkj(n)°1modn,mkj(n)+1°mmodnmj(n)°1modn,mkj(n)°1modn,mkj(n)+1°mmodn即cdmodn°m。②gcd(m,n)11,由于n+p?q,且gcd(p,q)=1,因此gcd(m,n)11說明了m含有p或q的質(zhì)因數(shù),假設(shè)m=cp,其中c為一正整數(shù)。我們可以推算到gcd(m,q)=1,否則m也是q的倍數(shù),因此m含有pq的因數(shù),與m<n=pq的結(jié)論相矛盾。由gcd(m,q)=1及歐拉定理得mj(q)°1modq,所以mkj(q)°1mod?mkj(q)j(p)°1modq,mkj(n)°1modqmkj(q)°1mod?mkj(q)j(p)°1modq,mkj(n)°1modq因此存在一整數(shù)r,使得mkj(n)=1+rq,兩邊同乘以m=cp得mkj(n)+1=m+rcpq=m+rcn即mkj(n)+1=m+rcpq=m+rcn2.2e2mod98選取p=7,q=17。求得n=p,q119,j(n)=(p-1)(q-1)=96。取e=5,滿足1<e<j(n),且gcd(j(n),e)=1。下面再確定d,使得且d?e°1mod96且d<96,因?yàn)?75385=4961,所以取d=77,因此公鑰為{5,119},秘鑰為{77,119}。設(shè)明文m=19,則由加密過程而得密文c為c=195mod119=2476099mod119?66c=195mod119=2476099mod119?66解密為6677mod119°196677mod119°193nin次運(yùn)算運(yùn)算從上面所述可知公鑰e要推導(dǎo)出密鑰d只要用到j(luò)(n)。我們把{e,n}公開,一旦某攻擊者在嘗試中成功地把模數(shù)n分解為p′q,就能獲得式子j(n)=(p-1)(q-1),進(jìn)而能夠推算出e模j(n)的乘法逆元d,即d°e-1modj(n),因而攻擊成功。這就要求選取的素?cái)?shù)p、q足夠大,這樣的n=p?q是難于分解的。這就是RSA的安全性所在——大整數(shù)分解的困難性。大整數(shù)分解是一個(gè)NP問題,目前已知最好的算法需要進(jìn)行e√ΙnnΙn(Ιnn)eInnIn(Inn)√次算術(shù)運(yùn)算。假設(shè)我們用一臺(tái)每秒運(yùn)算108(即一億)次的計(jì)算機(jī)來分解一個(gè)200位十進(jìn)制的數(shù),則有如下的計(jì)算:n=200√1nn1n(1nn)?53.1418一年為∶365′24′60′60=3153600?e17.2666(秒)e√ΙnnΙn(Ιnn)/108//3153600?e17.4525?3.8′107(年)n=2001nn1n(1nn)??????????√?53.1418一年為∶365′24′60′60=3153600?e17.2666(秒)eInnIn(Inn)√/108//3153600?e17.4525?3.8′107(年)即,要分解一個(gè)200位十進(jìn)制的數(shù),需要3.8′107年,類似地,可算出要分解一個(gè)300位的十進(jìn)制的整數(shù),則需要4.86′1013年。所以,n的位數(shù)越大,安全性越高。因此直接分解一個(gè)大整數(shù)來破譯RSA在計(jì)算上是不可能的。直接分解一個(gè)大整數(shù)的強(qiáng)力攻擊的實(shí)例:1994年4月分解的RSA密鑰RSA-129,即分解一個(gè)129位十進(jìn)制,425比特的大數(shù)。分解時(shí)啟用了1600臺(tái)計(jì)算機(jī),耗時(shí)8個(gè)月,處理了4600MIPS年的數(shù)據(jù)(1MIPS為每秒可執(zhí)行一百萬條指令的機(jī)器一年所能處理的數(shù)據(jù)量)。除人類的計(jì)算能力是越來越強(qiáng)外,所以大整數(shù)的安全性的威脅還有來處分解算法的越來越先進(jìn)。過去常用二次篩法,主要是對(duì)RSA-129的分解,對(duì)于RSA-130的算法采用的是推廣的數(shù)域篩法,這個(gè)算法更為先進(jìn),計(jì)算能力較前種算法所做的計(jì)算多。將來可能還有更好的分解算法,所以我們對(duì)密鑰的選取特別要注意大小。4ra的攻擊4.1積的物這種對(duì)RSA的攻擊是攻擊者利用網(wǎng)絡(luò)偽裝某一信息,騙取私鑰的擁有者簽名,經(jīng)過推算后可得到它想要的信息。事實(shí)上,RSA有一個(gè)致命缺點(diǎn),即積的冪保留了輸入的運(yùn)算結(jié)構(gòu):(xm)d捍xdmdsmodn(xm)d捍xdmdsmodn因?yàn)樗杏脩舳寄苁褂霉€,無法在算法上解決這一個(gè)問題。防御措施:一是采用保密性更好公鑰協(xié)議,保證不對(duì)其它實(shí)體任意產(chǎn)生的信息解密,不對(duì)自己一無所知的信息簽名;二是決不對(duì)陌生人的隨機(jī)文檔簽名,如要簽名,首先對(duì)文檔作HASH處理,或同時(shí)使用不同的簽名算法。4.2比較c、c1和2在實(shí)現(xiàn)RSA時(shí),常常會(huì)給每一個(gè)用戶以相同的模數(shù)n,只是變更它們的加密、解密密鑰而已,這樣也給攻擊者有可乘之機(jī)。假設(shè)給兩個(gè)用戶的公鑰分別為e1和e2,且它們互素(一般情形都成立),明文是m,加密后所得的密文分別是c1°me1modn和c2°me2modnc1°me1modn和c2°me2modn敵人截獲c1與c2后,可以這樣恢復(fù)明文m。因?yàn)閑1和e2互素,所以一定存在兩個(gè)整數(shù)r和s,滿足re1+re2=1(其中一個(gè)必為負(fù)數(shù),不妨設(shè)r為負(fù))此時(shí)可用推廣的Euclid算法求出r和s。再用推廣的Euclid算法求出c-11?11,從而所以對(duì)于公共模數(shù)攻擊的辦法只有一個(gè),那就是不要共享模數(shù)n。4.3模型數(shù)的不同如果不同用戶的模不同,但公鑰都很小,這樣也容易受攻擊。為討論方便,假定3個(gè)用戶,它們的公鑰(即加密指數(shù))都是3,它們的模數(shù)分別為n1,n2,n3,且兩兩互素,否則能過它們的公因數(shù)可能得出它們的分解。設(shè)明文為m,密文分別是c1°m3modn1c2°m3modn2c3°m3modn3c1°m3modn1c2°m3modn2c3°m3modn3由中國(guó)剩余定理可求出m3mod(n1,n2,n3),由于m3<n1n2n3,可以直接由m3開立方根求出m.5對(duì)稱加密慢RSA即可以用來加密,又可以用來數(shù)字簽名。雖加密的安