• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      RSA算法的研究與實(shí)現(xiàn)

      2018-11-20 11:54:08弋改珍
      現(xiàn)代計(jì)算機(jī) 2018年30期
      關(guān)鍵詞:互質(zhì)密碼學(xué)素?cái)?shù)

      弋改珍

      (咸陽(yáng)師范學(xué)院計(jì)算機(jī)學(xué)院,咸陽(yáng) 712000)

      0 引言

      RSA算法是一種迄今為止理論上比較成熟和完善的公鑰密碼體制,是非對(duì)稱(chēng)密碼體制的典型代表[1]。在網(wǎng)絡(luò)、信息安全等許多方面都使用RSA算法,特別是RSA算法典型應(yīng)用在通信中的數(shù)字簽名,可實(shí)現(xiàn)對(duì)手的身份、不可抵賴(lài)性驗(yàn)證。在身份認(rèn)證、信息安全、電子商務(wù)中有著廣泛的應(yīng)用前景。

      本文介紹了應(yīng)用于RSA算法中的密碼學(xué)基礎(chǔ)知識(shí),分析了RSA算法的原理與實(shí)現(xiàn)步驟,詳細(xì)分析了RSA實(shí)現(xiàn)過(guò)程中用到的算法,并在VC環(huán)境下,用C++開(kāi)發(fā)語(yǔ)言實(shí)現(xiàn)了RSA的加密和解密算法。

      1 RSA中的密碼學(xué)基礎(chǔ)知識(shí)

      密碼學(xué)實(shí)質(zhì)上體現(xiàn)了數(shù)論知識(shí)的應(yīng)用,每一個(gè)加密算法體現(xiàn)了不同加密理論,而加密理論又涉及了數(shù)論知識(shí)。所以,數(shù)論知識(shí)是加密算法的基礎(chǔ)。

      定義1(互質(zhì)關(guān)系)[2]:如果兩個(gè)正整數(shù),除了1以外,沒(méi)有其他公因子,則稱(chēng)這兩個(gè)數(shù)是互質(zhì)關(guān)系,即互素。

      性質(zhì)1兩個(gè)正整數(shù)互素的性質(zhì)[3]:

      ①任意兩個(gè)質(zhì)數(shù)構(gòu)成互質(zhì)關(guān)系;

      ②假設(shè)有個(gè)質(zhì)數(shù),后面找到一個(gè)數(shù)不和前面那個(gè)質(zhì)數(shù)成倍數(shù)關(guān)系,則它們就互質(zhì);

      ③所有的自然數(shù)和1都互質(zhì);

      ④p是大于 1的整數(shù),則p-1和p構(gòu)成互質(zhì)關(guān)系;

      ⑤p是大于 1的奇數(shù),則p和p-2構(gòu)成互質(zhì)關(guān)系。

      定義2(歐拉函數(shù))[3]:設(shè)n為正整數(shù),以φ()n表示不超過(guò)n且與n互素的正整數(shù)的個(gè)數(shù),φ()n稱(chēng)為n的歐拉函數(shù)值。

      定理1(歐拉定理)[4]:如果a和n兩個(gè)正整數(shù)是互質(zhì)關(guān)系,那么n的歐拉函數(shù)φ(n)滿(mǎn)足:

      上式說(shuō)明,a的φ(n)次方除n后的余數(shù)是1。

      定理2(中國(guó)剩余定理)[4]:若a與p1互質(zhì),a<p1;b與p2互質(zhì),b<p2;c與p1p2互質(zhì),c<p1p2。那么,c與數(shù)對(duì)(a,b)是一一對(duì)應(yīng)關(guān)系。由于a的值有φ(p1)種可能,b的值有φ(p2)種可能,那么數(shù)對(duì)(a,b)有φ(p1)φ(p2)種可能,而c的值有φ(p1p2)種可能。則φ(p1p2)=φ(p1)φ(p2)。

      定理3(費(fèi)馬小定理)[4]:若a是正整數(shù),n是質(zhì)數(shù),質(zhì)數(shù)n滿(mǎn)足φ(n)等于p-1,a和n互質(zhì),則:

      an-1≡1(modn)

      定義3(模反元素)[4]:如果兩個(gè)整數(shù)a和n互質(zhì),那么一定可找到整數(shù)b,使得ab-1被n整除,即:

      ab≡1(modn)

      2 RSA算法描述

      RSA算法由密鑰的產(chǎn)生、加密算法和解密算法3個(gè)部分組成[1]:

      (1)密鑰的產(chǎn)生

      ①產(chǎn)生兩個(gè)大素?cái)?shù)p和q;

      ②計(jì)算n=p×q,歐拉函數(shù)φ(n)=(p-1)(q-1)

      ③選擇整數(shù)e,使其滿(mǎn)足條件:1<e<φ(n),且gcd(e,φ(n) )=1(注:gcd()函數(shù)計(jì)算兩個(gè)數(shù)的最大公約數(shù));

      ④計(jì)算e的逆元d:d?e≡1 modφ(n)(注:由于gcd(e,φ(n) )=1,則d一定存在);

      ⑤取序?qū)?e,n)為公鑰,可公開(kāi);(d,n)為私鑰,對(duì)外保密。

      (2)加密算法

      將要發(fā)送的字符串分割為長(zhǎng)度為m<n的分組,然后對(duì)分組mi執(zhí)行加密運(yùn)算,得到密文ci:

      (3)解密算法

      收到密文ci后,接收者使用自己的私鑰執(zhí)行解密運(yùn)算,得到明文mi:

      3 RSA算法詳細(xì)設(shè)計(jì)

      3.1 大素?cái)?shù)的產(chǎn)生和測(cè)試

      Miller-Rabin算法是一種基于概率的素?cái)?shù)測(cè)試方法,在密碼學(xué)的素?cái)?shù)產(chǎn)生中,由于該算法的速度快、原理簡(jiǎn)單、易于實(shí)現(xiàn),成為進(jìn)行素?cái)?shù)檢測(cè)的最佳選擇[5]。

      Miller-Rabin算法[6]是對(duì)費(fèi)馬算法改進(jìn),它的操作步驟如下:

      (1)計(jì)算m,滿(mǎn)足n=(2r)m+1;

      (2)選擇隨機(jī)數(shù)a∈[1,n];

      (3)若ammodn=1,或滿(mǎn)足aimmodn=n-1,則n通過(guò)隨機(jī)數(shù)a的測(cè)試;

      (4)再取不同a要的值對(duì)n進(jìn)行t=5次測(cè)試,如果每次測(cè)試結(jié)果為n是素?cái)?shù),則以高概率判定n是素?cái)?shù)。假設(shè)n通過(guò)t次測(cè)試,則判定結(jié)果錯(cuò)誤的概率是1/4t;若只通過(guò)一次測(cè)試,素?cái)?shù)判定的錯(cuò)誤概率是25%。

      生成大素?cái)?shù)算法的實(shí)現(xiàn)流程圖,如圖1所示。

      圖1 大素?cái)?shù)生成流程圖

      3.2 密鑰e生成模塊

      通過(guò)3.1節(jié)的大素?cái)?shù)生成模塊,可以得到大素?cái)?shù)p和大素?cái)?shù)q,根據(jù)歐拉函數(shù)φ(n)=(p-1)(q-1),同時(shí)密鑰e與φ(n)互質(zhì),根據(jù)中國(guó)剩余定理可以計(jì)算密鑰e。生成密鑰e的算法流程圖如圖2所示。

      圖2 密鑰e生成流程圖

      3.3 密鑰d生成模塊

      通過(guò)大素?cái)?shù)生成模塊得到大素?cái)?shù)p和q,密鑰e生成模塊,根據(jù)1=edmod( )p-1(q-1)。利用中國(guó)剩余定理計(jì)算e的乘法逆元d。

      3.4 快速指數(shù)算法

      得到e后,就可以通過(guò)公鑰(e,n)進(jìn)行加密得到密文C。在RSA加密過(guò)程中,為了計(jì)算ci≡(mi)emodn,采用快速指數(shù)算法[7]。將快速指數(shù)算法描述為三元組(M,E,Y),其初始值為(M,E,Y)=(mi,e,1)。重復(fù)執(zhí)行以下操作:

      ①若E是奇數(shù),則Y=M*Ymodn,E=E-1;

      ②若E是偶數(shù),則X=X*Xmodn,E=E/2。

      最終,當(dāng)E=0時(shí),則Y=X^Emodn。

      3.5 RSA加密和解密算法設(shè)計(jì)

      根據(jù)2節(jié)的RSA算法描述和前面描述的大素?cái)?shù)產(chǎn)生算法、密鑰e生成算法、求乘法逆元算法、快速指數(shù)算法,實(shí)現(xiàn)RSA加密/解密算法流程圖如圖3所示。

      圖3 RSA算法的流程

      4 運(yùn)行結(jié)果與結(jié)論

      開(kāi)發(fā)環(huán)境是VC6.0,使用的語(yǔ)言是VC++,基于對(duì)話(huà)框應(yīng)用程序的前提下,完成了RSA算法的加密解密操作,先導(dǎo)入加密密鑰,也就是公鑰(e,n),然后選擇要加密的.txt文本文件,按下生成密文的按鈕后,就對(duì)文本進(jìn)行了加密,轉(zhuǎn)化成了另一種不能得知的信息,如4圖中生成密文后面文本框的信息是字母和數(shù)字的組合。再按下導(dǎo)入解密密鑰,即通過(guò)(d,n)進(jìn)行解密。從圖4中可以看出密文通過(guò)解密恢復(fù)了我們能夠看得懂的文本信息。

      圖4 RSA加密系統(tǒng)運(yùn)行結(jié)果圖

      5 結(jié)語(yǔ)

      本文研究RSA算法所涉及到的密碼學(xué)基礎(chǔ)概念,在此基礎(chǔ)上,分析了RSA算法的基本原理,詳細(xì)設(shè)計(jì)了RSA算法實(shí)現(xiàn)的各個(gè)子模塊,并在VC環(huán)境下,采用C++語(yǔ)言實(shí)現(xiàn)了RSA算法。結(jié)果表明,使用加密算法產(chǎn)生的密文,能夠被解密算法正確解密。

      RSA算法的設(shè)計(jì)與實(shí)現(xiàn)是基于RSA組件的基本算法,隨著通信速率不斷提高,對(duì)加密算法的運(yùn)行效率也有新的要求。只有有效地改進(jìn)RSA算法各個(gè)組成部分的效率,才能適應(yīng)通信需求,適應(yīng)新的網(wǎng)絡(luò)安全條件。因此,對(duì)于RSA算法各組成部分進(jìn)一步改進(jìn),成為今后研究的重要課題。

      猜你喜歡
      互質(zhì)密碼學(xué)素?cái)?shù)
      孿生素?cái)?shù)
      基于互質(zhì)陣列的信號(hào)波達(dá)方向估計(jì)算法
      航空兵器(2023年2期)2023-06-25 03:04:39
      兩個(gè)素?cái)?shù)平方、四個(gè)素?cái)?shù)立方和2的整數(shù)冪
      關(guān)于兩個(gè)素?cái)?shù)和一個(gè)素?cái)?shù)κ次冪的丟番圖不等式
      圖靈獎(jiǎng)獲得者、美國(guó)國(guó)家工程院院士馬丁·愛(ài)德華·海爾曼:我們正處于密鑰學(xué)革命前夕
      密碼學(xué)課程教學(xué)中的“破”與“立”
      Short-range Radar Detection with(M,N)-Coprime Array Configurations
      奇妙的素?cái)?shù)
      矩陣在密碼學(xué)中的應(yīng)用
      不定方程x2+y2+z2=2(xy+yz+xz)的解及其性質(zhì)
      博爱县| 井冈山市| 高州市| 保亭| 玛曲县| 眉山市| 休宁县| 淮北市| 铁岭县| 姚安县| 泰和县| 绥宁县| 铁岭市| 万山特区| 虞城县| 南雄市| 通道| 扬州市| 漳平市| 海阳市| 织金县| 泽库县| 凌源市| 郧西县| 特克斯县| 鞍山市| 中牟县| 内江市| 农安县| 乐昌市| 开鲁县| 江阴市| 台北县| 岐山县| 吕梁市| 佳木斯市| 颍上县| 沛县| 松潘县| 北辰区| 同德县|