1凌节、文章思想與工作：

主要思想：文章假定將構(gòu)建令人驚訝的可擴(kuò)展的量子計(jì)算機(jī)洒擦，使得量子比特操作成本低廉。在這個(gè)假設(shè)下逾柿，Shor算法很容易破壞當(dāng)今互聯(lián)網(wǎng)上使用的RSA。主要研究的問(wèn)題是RSA參數(shù)是否可以調(diào)整宅此，以便所有已知的量子攻擊算法都是不可行的机错，而加密和解密仍然可行。本文的主要觀點(diǎn)是父腕，加速RSA的標(biāo)準(zhǔn)技術(shù)在被推到極限時(shí)弱匪，會(huì)在合法用戶成本和攻擊者成本之間造成更大的差距。文章提出RSA的參數(shù)（1）當(dāng)今計(jì)算機(jī)上的密鑰生成璧亮，加密萧诫，解密，簽名和驗(yàn)證是可行的;（2）所有已知的攻擊是不可行的枝嘶，即使是高度可擴(kuò)展的量子計(jì)算機(jī)帘饶。

工作：作為性能分析的一部分，文章介紹了一種新的算法來(lái)生成一批素?cái)?shù)群扶。作為攻擊分析的一部分及刻，該文章介紹了一種新的量子分解算法GEECM镀裤，它比Shor算法和所有預(yù)量子分解算法快得多。GEECM成為后量子RSA參數(shù)選擇的主要限制之一缴饭。這些極端情況還需要仔細(xì)分析基本RSA操作的算法暑劝。作為這個(gè)性能分析的一部分，導(dǎo)致了一種新的算法來(lái)比任何已知算法更有效地生成大批獨(dú)立的均勻隨機(jī)素?cái)?shù)颗搂，以一次一個(gè)地生成這樣的素?cái)?shù)担猛。本文提供了初始的pqRSA實(shí)施結(jié)果。

2丢氢、相關(guān)技術(shù)：

Shor算法：

主要包含兩大步驟：

（1）用傳統(tǒng)的計(jì)算機(jī)尋找大質(zhì)數(shù)的因子傅联，并轉(zhuǎn)換為求其周期。

（2）用量子算法卖丸，利用量子的并行性特點(diǎn)存儲(chǔ)數(shù)據(jù)纺且，并用傅里葉變換求解。

Grover算法：

Grover算法是基于無(wú)序數(shù)據(jù)庫(kù)的搜索算法.對(duì)于一個(gè)無(wú)結(jié)構(gòu)的數(shù)據(jù)庫(kù),最優(yōu)經(jīng)典算法的搜索復(fù)雜度為O(N),用概率圖靈機(jī)搜索的期望次數(shù)為N/2步.Grover算法的搜索復(fù)雜度為O(N),這一算法對(duì)經(jīng)典對(duì)稱密碼的攻擊非常有效稍浆。如果搜索的數(shù)據(jù)庫(kù)大小為N,即有N個(gè)元素,可以設(shè)N=2n,則所搜索的數(shù)據(jù)庫(kù)可以用nbit存儲(chǔ).在數(shù)學(xué)上一個(gè)數(shù)據(jù)庫(kù)文件可以表示為一個(gè)函數(shù)f(x),輸入x是一個(gè)記錄的關(guān)鍵字值,f(x)表示的就是對(duì)應(yīng)著關(guān)鍵字取值x的記錄.假設(shè)每個(gè)記錄a在文件中出現(xiàn)一次且僅出現(xiàn)一次,數(shù)據(jù)庫(kù)搜索問(wèn)題就是知道x的值,找出與x對(duì)應(yīng)的a.數(shù)據(jù)庫(kù)搜索問(wèn)題可以變?yōu)槿缦乱粋€(gè)判定問(wèn)題:給出一個(gè)量子Oracle,它可以計(jì)算f(x),并得到結(jié)果：

量子環(huán)算法GEECM：新的量子分解算法载碌，更高效的方法是采用最好的預(yù)量子算法來(lái)尋找小素?cái)?shù)，并使用量子技術(shù)來(lái)加速這些算法衅枫。

小指數(shù)：計(jì)算n次模n嫁艇，然后取n個(gè)模n和一個(gè)乘n。每個(gè)步驟都采用標(biāo)準(zhǔn)快速乘法技術(shù)進(jìn)行（lg n）1 + o（1）位操作;

加密解密：使用RSA對(duì)隨機(jī)數(shù)據(jù)的n位進(jìn)行加密弦撩，對(duì)隨機(jī)數(shù)據(jù)進(jìn)行散列步咪，得到一個(gè)秘密密鑰，然后用秘密密鑰對(duì)用戶的消息進(jìn)行加密和認(rèn)證益楼；

3猾漫、算法

shor算法：

轉(zhuǎn)換問(wèn)題，變求因子為求因子周期

（1）任取a<N感凤，利用轉(zhuǎn)出相除法計(jì)算gcd(a,N).

（2）若gcd(a,N)不等于1悯周，得到結(jié)果，結(jié)束陪竿。

（3）否則禽翼，利用下面函數(shù)，并找出函數(shù)周期

即找出a在整數(shù)里面的周期r族跛，令f(x+r)=f(x).

（4）如果r是奇數(shù)闰挡，則回到第一步。

（5）如果

則回到第一步礁哄。

（6）

是N的一個(gè)因子长酗，分解完成。

量子算法部分姐仅，運(yùn)用傅里葉變換求周期：

（1）對(duì)兩組有m個(gè)量子比特的存儲(chǔ)器進(jìn)行正變換得到糾纏狀態(tài)

f(x)為上一步中定義的函數(shù)花枫。

（2）對(duì)存儲(chǔ)器x進(jìn)行傅里葉變換

推導(dǎo)可得

（3）利用K滿足的公式求f(x)周期刻盐，得到周期后，即可推導(dǎo)出N的因子劳翰。

密鑰生成敦锌、加密解密：

（1）任意選取兩個(gè)不同的大質(zhì)數(shù)p和q，計(jì)算乘積r=p*q佳簸；

（2）任意選取一個(gè)大整數(shù)e乙墙，e與(p-1)*(q-1)互質(zhì)，整數(shù)e用做加密密鑰生均。注意：e的選取是很容易的听想，例如，所有大于p和q的質(zhì)數(shù)都可用马胧。

（3）確定解密密鑰d：

d * e = 1 mod（p - 1）*（q - 1）

根據(jù)e汉买、p和q可以容易地計(jì)算出d。

（4）公開(kāi)整數(shù)r和e佩脊，但是不公開(kāi)d蛙粘；

（5）將明文P (假設(shè)P是一個(gè)小于r的整數(shù))加密為密文C，計(jì)算方法為：

（6）將密文C解密為明文P威彰，計(jì)算方法為：

4出牧、未來(lái)的研究方向、未解決的難題：

未來(lái)的研究方向：一系列的工作表明歇盼，大規(guī)模的秘密可以防止惡意軟件限制數(shù)量的旁路攻擊和有限數(shù)量的漏洞舔痕，一個(gè)兆兆字節(jié)只需要幾個(gè)小時(shí)就可以通過(guò)千兆每秒的鏈路進(jìn)行傳輸，但是這一線工作的基本思想是豹缀，有時(shí)候?qū)r(shí)間和在旁邊通道和滲透通道中的帶寬有限制伯复，并且這些限制可以阻止攻擊者提取期望的秘密；分析后量子RSA秘密提供這種保護(hù)的程度邢笙；將后量子RSA集成到標(biāo)準(zhǔn)互聯(lián)網(wǎng)協(xié)議.

未解決的難題：需要解決許多系統(tǒng)級(jí)的挑戰(zhàn)边翼，例如對(duì)加密庫(kù)允許的RSA密鑰大小的各種限制。所有可信的第三方協(xié)議都引發(fā)了安全問(wèn)題鸣剪，并且所有已知技術(shù)安全地分配或委托RSA計(jì)算的成本都很高，這里面臨的挑戰(zhàn)和難題是證明與一次一個(gè)用戶的RSA密鑰生成相比丈积，可以更有效地執(zhí)行安全的多用戶RSA密鑰生成筐骇。大規(guī)模的GMP內(nèi)存消耗觸發(fā)了Linux內(nèi)核中已知的競(jìng)爭(zhēng)條件