《Post-quantum RSA》閱讀報告

20152100123卓翔

一本姥、文章主要思想與工作

文章主要是提出了一種新型改進版的后量子RSA。這個后量子RSA比現(xiàn)在通行的RSA密碼體系更加能夠抵抗量子計算機的攻擊厂僧。但在理論層面扣草，這個進步只是把“完全不安全”（敵方破解幾乎跟合法用戶解密一樣快）提升到了“稍微有點安全可言”（破解的速度低于加密解密的速度），遠遠沒有達到正統(tǒng)的安全標準（破解的計算量指數(shù)增長）颜屠。該文結論是：目前版本的RSA在量子算法面前不堪一擊辰妙，因此該文章介紹了一種新的量子分解算法GEECM，它比Shor算法和所有預量子分解算法快得多甫窟。GEECM成為后量子RSA參數(shù)選擇的主要限制之一密浑，在某種意義上可以對抗已知的量子算法。

二粗井、討論相關技術

量子位提供了難以想象的海量數(shù)字存儲和運算能力尔破，但此處還需要能調動得起量子計算機這可怕性能的量子算法，才能讓量子計算具備實際用途浇衬。后量子密碼術是個活躍的研究領域懒构，但沒有在原理層面證明任何一個公鑰密碼體制可以抵抗量子計算機甚至經典計算機。一個公鑰密碼體制可以抵抗某種算法的攻擊（包括量子算法），不等于能從原理上證明其安全性醉冤，因為后者是要證明它可以抵抗任何已知和未知算法的攻擊铃绒。而至今唯一能從原理上嚴格證明安全性的密碼體制矮燎，就是量子密碼術浅乔。這是量子密碼術與所有的公鑰密碼體制之間的根本差別。

目前人類對于量子算法研究里已經形成公眾影響力的領域是信息安全——具體點說就是加密和解密贤壁，尤其是后者。其中最有名的是1994年的Shor算法名船，這個算法可指導量子計算機進行大數(shù)因子分解渠驼，而大數(shù)因子分解正是目前流行的公開密鑰體系RSA的核心。

Shor把因數(shù)分解的計算量減少到了多項式級別蜓席。由于合法用戶加密解密也是需要計算量的，而Shor的量子算法強大到了破解RSA跟合法用戶解密幾乎一樣快。所以為了對抗已知的量子算法的攻擊癣亚，該文章提出了一種改進的RSA版本。

在老派的安全性定義下玻孟，即面對多項式時間敵手時的漸近安全性的定義下面徽，后量子RSA沒有達到安全的標準趟紊。然而，后量子RSA看起來確實提供了一個合理水平的具體的安全性铛嘱。沒有任何公鑰密碼體系在多項式時間的量子敵手的面前是安全的；但是有公鑰密碼體系在比如說基本上是線性時間的量子敵手的面前是安全的肛真。后量子RSA就是其中一個候選者。

傳統(tǒng)的RSA是把兩個質數(shù)相乘历极。該文章提出，通過一系列數(shù)學技巧（快速的乘法以及隨機生成質數(shù)的方法等等）锄列，可以把加密解密的計算量都控制在正比于n邻邮，然后把非常多的質數(shù)相乘丹泉，使得n非常大，就可以讓破解的計算量顯著地超過加密解密的計算量晒哄。簡而言之，就是把加密解密的計算量（n）降低到了破解的計算量（n的平方）之下硫兰。該文章把這種改進版RSA稱為后量子RSA劫映。

三、后量子RSA算法

（親愛的斌頭老師祖今，很抱歉我水平有限，寫不出代碼徐绑，請海涵……）

1、后量子分解算法

新的量子分解算法GEECM盘榨，比Shor算法和所有預量子分解算法快得多捷犹。量子環(huán)算法：GEECM。更高效的方法是采用最好的預量子算法來尋找小素數(shù)枪孩，并使用量子技術來加速這些算法。

在標準猜想下攻询，ECM使用2^（（lgy）^（1/2+o（1）））環(huán)操作來找到素數(shù)p≤y。在對o（1）進行更詳細的分析的基礎上得出截斷值在2^30以下拯杠。

ECM的最新變體是EECM（使用Edwards曲線的ECM）。EECM選擇愛德華茲曲線（Edwards curve）x^2+y^2=1+d^2y^2超過Q依溯，或者選擇具有已知非扭轉點P的扭曲Edwards曲線;EECM也選擇一個較大的整數(shù)s誓沸，并使用Edwards加法定律來計算曲線上P的倍數(shù)，特別是用整數(shù)的一小部分表示的x坐標x（sP）洪添。環(huán)算法的輸出是這個分數(shù)的分子》蘧總的來說逛尚，計算需要（7+o（1））lgs乘法（其中一半以上是平方）和相當數(shù)量的加法和減法到逊。

如果s被選為lcm{1,2,...,z}觉壶，那么lgs≈1.4z，所以這個曲線計算使用大約10z的乘法旷坦。如果z∈L^（c+o（1））為y→∞，其中L=exp（logyloglogy）且c是一個常數(shù)捆蜀，那么標準猜想意味著每個素數(shù)p≤y是由概率1/L^（1/2c+o（1））得出。標準猜想也意味著曲線幾乎是獨立的锰茉，所以嘗試L^（1/2c+o（1））曲線。嘗試所有這些曲線的總成本是L^（c+1/2c+o（1））環(huán)操作协屡。對于c=1/√2，表達式c+1/2c取最小值1;那么總成本就是L^（√2+o（1））環(huán)操作漫萄。

使用量子計算機的GEECM（Grover plus EECM）卷胯，以加速相同的EECM計算葵孤。Grover的方法是加速搜索函數(shù)的根：如果函數(shù)f的輸入是概率為1/R的f的根尤仍，則經典搜索執(zhí)行R的R評估，而Grover的方法是執(zhí)行關于√R量子評估f饼拍±旄蹋考慮函數(shù)f，其輸入是EECM曲線的選擇結果锋玲，并且當該曲線選擇的EECM結果具有與n相同的非平凡因子時，其輸出恰好為0剿干。EECM通過經典搜索找到f的根;GEECM通過Grover的方法找到了f的根。如果選擇s和z榜轿，那么f的輸入就是f的概率為1/L^（1/2c+o（1））的根甸私，所以GEECM只使用L^（1/4c+o（1））量子估計的f，總的L^（c+1/4c+o（1））量子環(huán)運算。對于c=1/2唬格，表達式c+1/4c取其最小值1;那么總的成本就是L^（1+o（1））環(huán)操作。

總而言之喊积，GEECM將環(huán)操作從L^（√2+o（1））減少到L^（1+o（1）），其中L=exp（logyloglogy）溶弟。對于相同數(shù)量的操作，GEECM將logy增加了2+o（1）擒权，幾乎是可以找到的素數(shù)的兩倍。

2、RSA可擴展性

后量子RSA公鑰n需要相當大才能抵抗上述后量子分解算法中描述的攻擊咒林。RSA可擴展性分析了可用于RSA密鑰生成爷光、加密垫竞、解密、簽名生成和簽名驗證的最佳算法的可擴展性蛀序。

（1）選用小指數(shù)欢瞪。基本的RSA公鑰運算是計算一個n次方的模徐裸。這個模冪運算使用大約lge平方模n引有，并且由于標準的窗口技術健民，o（eg）需要額外的乘法模n。為簡單起見，該文章取e=3幔摸。計算n次模n，然后取n個模n和一個常數(shù)乘nn。每個步驟都使用標準的快速乘法技術來進行（lgn）^（1+o（1））位操作彰亥。

（2）多素數(shù)∨糠基本的RSA密鑰操作是計算eth根模n垛叨。對于e=3翰绊，選擇n作為與2模3一致的不同素數(shù)的乘積;那么x→x^3modn的倒數(shù)是x→x^d mod n麦撵，其中d=（1+2Πp|n（p-1））/3扼雏。但是d不是一個小指數(shù)涂佃，它大約有l(wèi)gn個位，所以需要以下情況做加速煤伟。

計算x^d mod n的一個經典加速是計算x^d mod p和x^d mod q矫俺，其中p和q是n的主要因數(shù)伊群，組合為x^d mod n中國剩余定理的適當?shù)娘@式形式凹联。費馬的同一性x^p mod p=x mod p進一步意味著x d d mod p=x^（d mod（p-1））mod p（因為d mod（p-1）≥1）并且類似地有x^d mod q=x^（d mod（q-1））mod q忽孽。指數(shù)d mod（p-1）和d mod（q-1）只有n的一半;指數(shù)x^d mod n因此被具有半尺寸指數(shù)和半尺寸模數(shù)的兩個指數(shù)代替成箫。

如果n是多素數(shù)的乘積，例如k≥3個素數(shù)狸膏，則使用（1/k）大小的指數(shù)和（1/k）大小的模數(shù)的k次取冪氏淑。由于素數(shù)較小体啰，計算也變得容易得多。如果素數(shù)太小哺呜，那么攻擊者就可以使用上述討論的環(huán)算法椭豫，特別是量子計算機之前的EECM和量子計算機之后的GEECM。

該文章的重點是多重RSA如何擴展到更大的模數(shù)n。在量子計算機之前，最主要的威脅是EECM和NFS讨便，平衡這些威脅意味著每個素數(shù)p有（lgn）^（2/3+o（1））位，即k∈（lgn）^（1/3+O（1））寸五。在量子計算機誕生之后梳凛，最主要的威脅是GEECM和Shor算法，平衡這些威脅意味著每個素數(shù)p只有（lglgn）^（2+o（1））個比特梳杏，即k∈（lgn）/lglgn）^（2+o（1））韧拒。RSA密鑰生成、解密和簽名生成十性，采扰岩纭（lgn）^（1+o（1））位操作。

（3）密鑰生成劲适。k-prime指數(shù)-3RSA公鑰n是k個與2模3相同的不同的素數(shù)p的乘積楷掉。特別地，后量子RSA公鑰n是k個不同的素數(shù)p與2相等的乘積模3霞势，其中每個素數(shù)p具有（lglgn）^（2+o（1））位烹植。標準的素數(shù)生成技術使用（lgp）^（3+o（1））位操作。

一個標準的加速是檢查p是否可以被任何通過某個極限的冪整除愕贡，比如y草雕。這個可分性測試中存在一個隨機整數(shù)的概率大約為1/logy，如果試算組不是原始的隨機數(shù)固以，則將原始的隨機數(shù)池減少到（logp）/logy隨機數(shù)促绵。傳統(tǒng)的觀點認為，控制審判的成本需要y被選為lgp中的一個多項式嘴纺，只保存一個因子（lglgp）败晴，因此仍然需要（1gp）^（3+o（1））位操作。

一個非標準的加速是通過分批試驗或分批光滑檢測來代替試驗分割（或篩分）栽渴。算法是讀取正整數(shù)的有限序列S和素數(shù)的有限集合P尖坤，并使用b（lgb）^（2+o（1）得到S中每個整數(shù)的最大P光滑除數(shù)，其中b是P和S中的總位數(shù)闲擦。特別地慢味，如果P是通過y的整數(shù)集合，并且S是每個具有Θ（y/lgp）的整數(shù)的序列墅冷，（lgp）比特纯路，則b是Θ（y），該算法僅使用y（lgy）^（2+o（1））比特運算寞忿，即（lgp）（lgy）^（2+o）位操作驰唬。較大的序列S可以平分為大小為Θ（y/lgp）的序列，每個元素S產生相同的性能。

為了做得更好叫编，假設S的原始大小至少為2^（2α）辖佣，并且y=2^（2^0），y=2^（2^1）搓逾，y=2^（2^）2卷谈，依此類推，直到y(tǒng)=2^（2^α）霞篡。每個步驟都將S中剩下的一半元素作為復合材料除去;下一步的成本大約是每個元素的四倍世蔗，但只適用于一半的元素。對于S的每個原始元素朗兵，總成本只是（lgp）（2^α）^（1+o（1））位操作凸郑。每個原始元素具有約1/2^α的存活概率并產生一個指數(shù)運算，其代價是（lgp）^（2+o（1））位操作矛市。選擇2^α∈（lgp）^（0.5+o（1））為S的每個原始元素（即（lgp））平衡這些代價為（lgp）^（2.5+o（1））為每個生成的素數(shù)芙沥。

在后量子RSA的情況下，滿足S的原始大小的假設：必須生成（lgn）^（1+o（1））素數(shù)浊吏，所以S的原始大小是（lgn）^1+o（1））而昨，對于2^α∈（1+o（1））lglgn，至少為2^（2^α）,由于lgp∈（lglg n）^（2+o（1））找田，所以α的選擇滿足2^α∈（lgp）^（0.5+o（1）素數(shù)也是平衡的歌憨，就每個p而言（lgn）/k∈（lgp）^（1+o（1）），所以用這種方式生成k個素數(shù)使用k（lgp）（2.5（1））=（lgn）（lgp）^（1.5+o（1））=（lgn）（lglgn）^（3+o（1））位運算墩衙。

（4）加密务嫡。Shoup的“RSA-KEM”等最新的機制簡單地使用RSA對隨機數(shù)據的n位進行加密，對隨機數(shù)據進行散列漆改，得到一個密鑰心铃，用密鑰對用戶的消息進行加密和認證，并且不需要任何填充挫剑。

真正的隨機數(shù)據可以通過流密碼產生的偽隨機數(shù)據來模擬一個更小的密鑰去扣。這包含幾個可伸縮密碼，其產生來自Θ（b）位密鑰的Θ（b）位輸出塊樊破，猜測每個輸出比特愉棱，使用b^（2+o（1））比特運算，即b^（1+o（1））比特運算哲戚。在后量子RSA的情況下奔滑，有一個b∈Θ（lglgn），所以產生lgn偽隨機比特成本（lgn）（lglgn）^（1+o（1））比特運算顺少。也可以將相同的密碼轉換成散列函數(shù)朋其，其效率只有一個常數(shù)因子的損失王浴，所以對這些比特進行散列也會導致比特操作的成本（lgn）（lglgn）^（1+o（1））。

乘法還需要（lgn）（lglgn）^（1+o（1））位操作令宿。平方、減模n腕窥、乘法和另一個減法模n一起攘Ｃ弧（lgn）（lglgn）^（1+o（1））位操作。因此簇爆，RSA加密的總體成本是（lgn）（lglgn）^（1+o（1））比特操作加上在產生的密鑰下加密和認證用戶消息的成本癞松。

（5）解密。首先減少密文模n的所有素因子入蛆。采用（lgn）（lglgn）^（2+o（1））位運算使用余數(shù)樹或縮放余數(shù)樹响蓉。然后計算每個素數(shù)模的立方根，立方根模p壬诨佟（lgp）^（2+o（1））位操作枫甲，所有立方體根都一起取(1gn)(2+o)。然后重建立方根n扼褪。使用快速插值技術來執(zhí)行（lgn）（lglgn）^（2+o（1））位操作想幻。最后散列立方根。RSA解密的總體成本是（lgn）（lglgn）^（2+o（1））位操作话浇，加上在得到的密鑰下驗證和解密用戶消息的成本脏毯。在后量子RSA的情況下，加密的速度比加速解密要慢得多幔崖。

（6）簽名生成和驗證食店。用于RSA簽名的標準填充方案涉及上面討論的相同操作，例如散列為短字符串并使用流密碼將短字符串擴展為長字符串赏寇。生成一個簽名和（lgn）（lglgn）^（1+o（1））以驗證簽名吉嫩，加上散列用戶消息的代價。

四嗅定、未來的研究方向率挣、未解決的難題

首先，大的秘密（big secret）可以防止惡意軟件限制數(shù)量的旁路攻擊和有限數(shù)量的漏洞露戒〗饭Γ基本思想是限制側通道和出口通道的時間和/或帶寬，而且這些限制可以阻止攻擊者提取所需的秘密智什。 分析后量子RSA中的秘密提供這種保護的程度是很有意思的动漾。 然而，系統(tǒng)的其他部分可能會損害正面的答案荠锭，而這些部分并沒有把重心放在擴展數(shù)據上旱眯。

我們的批量生成算法表明，為了幫助降低能耗，RSA的所有用戶（包括傳統(tǒng)的預量子RSA的用戶）都應該將他們的密鑰生成計算委托給NIST或另一個可信的第三方删豺。除了速度可以提高外共虑，還可以使用戶生成新的RSA密鑰的同時并更頻繁地刪除舊的RSA密鑰，從而限制了密鑰被盜用的危害呀页。然而妈拌，所有可信的第三方協(xié)議都引發(fā)了安全問題，并且所有已知技術安全地分配或委托RSA計算的成本都很高蓬蝶。這里面臨的挑戰(zhàn)是證明尘分，與一次一個用戶的RSA密鑰生成相比，如何更有效地執(zhí)行安全的多用戶RSA密鑰生成丸氛。

后續(xù)工作的另一個自然方向是將后量子RSA集成到標準互聯(lián)網協(xié)議（如TLS）中培愁。這種集成在概念上很簡單，但需要解決許多系統(tǒng)級的挑戰(zhàn)缓窜，例如對加密庫允許的RSA密鑰大小的各種限制定续。如果目的僅僅是為了防止過去的流量完全失竊（“前向保密”），則用戶可以通過預先生成許多RSA密鑰來獲得加速禾锤，并且在第一次使用之后不久就擦除每個密鑰香罐。在生成每個密鑰之后不久就會刪除每個密鑰，有時會被稱為幫助保護未來的流量免受有限類型的泄露时肿。

量子密碼術的還有一個最明顯的缺點就是慢庇茫。由于密鑰是通過單光子的發(fā)射和接收產生的，條件十分苛刻螃成，所以生成密鑰的速度目前都是在每秒多少k的量級旦签。在一次性便箋加密中，明文跟密鑰一樣長寸宏，所以傳輸信息的速度就等于生成密鑰的速度宁炫。如果用AES、DES之類不等長加密的對稱密碼算法氮凝，速度倒是上去了羔巢，但又有可能被數(shù)學破解了。此外罩阵，量子密碼術的成本應該也不低竿秆。

五、參考文章

【1】《Post-quantum RSA》

【2】《徐令予：炒作量子通信工程稿壁，連潘建偉都擔心》http://www.guancha.cn/XuLingyu/2017_10_31_432886_s.shtml

【3】《量子保密通信：了解科學和工程幽钢，認清李鬼與李逵（上）》http://p.baidu.com/daily/view?id=99279

【4】《量子保密通信：了解科學和工程，認清李鬼與李逵（下）》http://p.baidu.com/daily/view?id=99375