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

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

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