1、*本科生作業(yè)*蘭州理工大學(xué)計(jì)算機(jī)與通信學(xué)院2017年春季學(xué)期信息安全課程專(zhuān)業(yè)：物聯(lián)網(wǎng)工程姓名：學(xué)號(hào)：授課教師：郭顯成績(jī)：RSA加解密過(guò)程及其實(shí)現(xiàn)概述RSA算法RSA加密算法是一種最常用的非對(duì)稱(chēng)加密算法，CFCA在證書(shū)服務(wù)中離不了它。在公鑰加密標(biāo)準(zhǔn)和電子商業(yè)中，RSA被廣泛使用。RSA算法使用乘方運(yùn)算，明文以分組為單位進(jìn)行加密，每個(gè)分組的二進(jìn)制值均小于n，也就是說(shuō)，分組的大小必須小于或等于10g2(n)+1位，在實(shí)際應(yīng)用中，分組的大小i位，其中2yn2，+i。對(duì)明文分組M和密文分組C，加密和解密過(guò)程如下：C=MemodnM=Cdmodn=(Me)dmodn=Medmodn其中收發(fā)雙方均已知n，發(fā)

2、送方已知e，只有接收方已知d，因此公鑰加密算法的公鑰為PU二e,n，私鑰為PR二d,n。該算法要能做公鑰加密，必須滿(mǎn)足以下條件：(1)可以找到e,d,n,使得對(duì)所有的Mn,有Medmodn=M。(2)對(duì)所有的乂,計(jì)算Me和Cd是比較容易的。(3)由e和n確定d是不可行的。公鑰與私鑰(1)隨意選擇兩個(gè)大素?cái)?shù)P和q，P不等于q，計(jì)算n=pq。(2)根據(jù)歐拉函數(shù)，不大于n且與n互素的整數(shù)個(gè)數(shù)為(p-1)(q-1)(3)選擇一個(gè)整數(shù)e與(p-1)(q-1)互素，并且e小于(p-1)(q-1)(4)用以下這個(gè)公式計(jì)算d：de三1mod(p-1)(q-1)(5)將p和q的記錄銷(xiāo)毀。(n,e)是公鑰，(n,

3、d)是私鑰。(n,d)是秘密的。Alice將她的公鑰(n,e)傳給Bob，而將她的私鑰(n,d)藏起來(lái)。R5AMI暨胃法及加密過(guò)程同.管F:*主麻石publicityc-fliEli?whir=(p-1)(q-11I甫電的諾元一inMtrM的科通國(guó)1個(gè)數(shù)時(shí)舊.可生礎(chǔ)而pHvwtvKty圖1RSA加密過(guò)程2.實(shí)例描述(1)選擇兩個(gè)素?cái)?shù)，p=17,q=11。(2)計(jì)算n=pq=17x11=187。(3)計(jì)算。(n)=(p-1)(q1)=16x10=160。(4)選擇e使其與。(n)=160互素且小于。(n)，這里選擇e=7。(5)確定d使得de三1mod160且d160。因?yàn)?3x7=161=1x

4、160+1，所以d=23。d可利用擴(kuò)展的歐幾里得算法來(lái)計(jì)算。所得的公鑰PU=7,187、私鑰PR=23,187)。該例說(shuō)明了輸入明文M=177時(shí)這些密鑰的使用情況。加密時(shí)需計(jì)算C=1777mod187。利用模算術(shù)的性質(zhì)，我們?nèi)缦掠?jì)算：1777mod187=(1774mod187)x(1772mod187)x(177mod187)mod187177mod187=1771772mod187=31329mod187=1001774mod187=981506241mod187=891777mod187=(177x100x89)mod187=1575300mod187=12解密時(shí)，我們計(jì)算M=1223m

5、od1871223mod187=(12mod187)x(122mod187)x(124mod187)x(128mod187)x(128mod187)mod18712mod187=12122mod187=144124mod187=20736mod187=166128mod187=429981696mod187=671123mod187=(12義144*166*67*67)mod187=1287660672mod187=177算法的安全性在RSA密碼應(yīng)用中，公鑰尸U是被公開(kāi)的，即e和n的數(shù)值可以被第三方竊聽(tīng)者得到。破解RSA密碼的問(wèn)題就是從已知的e和n的數(shù)值(n等于pq)，想法求出d的數(shù)值，這樣就

6、可以得到私鑰來(lái)破解密文。從上文中的公式：d三e-1(mod(p-1)(q-1)或de三1mod(p-1)(q-1)我們可以看出。密碼破解的實(shí)質(zhì)問(wèn)題是：從pq的數(shù)值，去求出(p-1)和(q-1)。換句話(huà)說(shuō)，只要求出p和q的值，我們就能求出d的值而得到私鑰。當(dāng)p和q是一個(gè)大素?cái)?shù)的時(shí)候，從它們的積pq去分解因子p和q，這是一個(gè)公認(rèn)的數(shù)學(xué)難題。比如當(dāng)pq大到1024位時(shí)，迄今為止還沒(méi)有人能夠利用任何計(jì)算工具去完成分解因子的任務(wù)。然而，雖然RSA的安全性依賴(lài)于大數(shù)的因子分解，但并沒(méi)有從理論上證明破譯RSA的難度與大數(shù)分解難度等價(jià)。即RSA的重大缺陷是無(wú)法從理論上把握它的保密性能如何。此外，RSA的缺點(diǎn)還

7、有：A)產(chǎn)生密鑰很麻煩，受到素?cái)?shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密。B)分組長(zhǎng)度太大，為保證安全性，n至少也要600bits以上，使運(yùn)算代價(jià)很高，尤其是速度較慢，較對(duì)稱(chēng)密碼算法慢幾個(gè)數(shù)量級(jí)；且隨著大數(shù)分解技術(shù)的發(fā)展，這個(gè)長(zhǎng)度還在增加，不利于數(shù)據(jù)格式的標(biāo)準(zhǔn)化。因此，使用RSA只能加密少量數(shù)據(jù)，大量的數(shù)據(jù)加密還要靠對(duì)稱(chēng)加密算法。4.程序代碼#includeintrsa(inta,intb,intc)intr=1;b=b+1;while(b!=1)r=r*a;r=r%c;b-;)printf(%dn,r);returnr;)voidmain()intp,q,e,d,m,n,t,c,r;chars;printf(請(qǐng)輸入p,q:);scanf(%d%d”,&p,&q);n=p*q;printf(n的值是%4dn,n);t=(p-1)*(q-1);序測(cè)