關(guān)于Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers閱讀報(bào)告
關(guān)于《用于計(jì)算短離散對(duì)數(shù)和因式分解RSA整數(shù)的量子算法》閱讀報(bào)告
一、文章主要思想與工作
? ? ? ?文章主要思想是通過(guò)概括量子算法和描述用于計(jì)算短離散對(duì)數(shù)的算法的應(yīng)用米死，從而改進(jìn)了用于計(jì)算短離散對(duì)數(shù)和因式分解RSA整數(shù)的量子算法沿腰，使算法更為簡(jiǎn)單及方便停士。
? ? ? ?本文作者主要工作是推廣本文中的量子算法來(lái)計(jì)算短離散對(duì)數(shù)，進(jìn)一步將指數(shù)的大小減少到略大于m位循捺。此外文章根據(jù)對(duì)短離散對(duì)數(shù)的算法，RSA整數(shù)的因式分解，以及在邊信息下尋找組的順序奕翔，可能會(huì)被重建為短離散對(duì)數(shù)問(wèn)題產(chǎn)生一個(gè)算法來(lái)分解RSA整數(shù)，比shor算法在量子計(jì)算機(jī)上要求簡(jiǎn)單更多浩蓉。
二派继、相關(guān)技術(shù)
1、計(jì)算離散對(duì)數(shù)問(wèn)題
? ? ? ?所謂離散對(duì)數(shù)捻艳，就是給定正整數(shù)x驾窟，y，n认轨，求出正整數(shù)k（如果存在的話）绅络，使y≡xk(mod n)。就目前而言，人們還沒有找到計(jì)算離散對(duì)數(shù)的快速算法（所謂快速算法恩急，是指其計(jì)算復(fù)雜性在多項(xiàng)式范圍內(nèi)的算法杉畜，即O(logn)k，其中k為常數(shù)）衷恭。雖然有快速計(jì)算離散對(duì)數(shù)的量子算法此叠，其計(jì)算復(fù)雜性為O(logn)2+?著，但現(xiàn)在并沒有量子計(jì)算機(jī)（實(shí)用的量子計(jì)算機(jī)也許根本就建造不出來(lái)）匾荆。
? ? ? ?而離散對(duì)數(shù)的應(yīng)用是離散對(duì)數(shù)公鑰加密算法拌蜘，其安全性要遠(yuǎn)遠(yuǎn)高于基于大數(shù)分解的RSA算法。方法如下：
? ? ? ?公鑰密碼體制的運(yùn)作過(guò)程（假定A和B兩個(gè)人要在一個(gè)不安全通道如因特網(wǎng)上形成密鑰以備日后加密解密所用）牙丽。首先简卧，A、B兩人要共同公開約定一個(gè)素?cái)?shù)q和有限域Fq中的一個(gè)生成元g烤芦；A選定一個(gè)隨機(jī)數(shù)a∈{1举娩，2，…构罗，q-1}（a可以認(rèn)為是A之私鑰）铜涉，并將g a(modq)傳送給B；B選定一個(gè)隨機(jī)數(shù)b∈{1遂唧，2芙代，…，q-1}（b可以認(rèn)為是B之私鑰）盖彭，并將gb(modq)傳送給A纹烹；此時(shí)A可以算出(g b)a(modq)，B也可以算出(g a)b(modq)召边，由于(gb)a(modq) = (g a)b(modq) = g ab(modq)铺呵，因此，A和B就形成了一個(gè)公共的密鑰g ab(modq)隧熙，日后便可以此鑰來(lái)進(jìn)行傳統(tǒng)的加密解密計(jì)算片挂，從而達(dá)到在不安全的通道上進(jìn)行保密通訊的目的。
? ? ? ?顯然贞盯，敵方可以截獲到g音念，q，g a(modq)躏敢，g b(modq)闷愤。因此，如果敵方有快速的求解離散對(duì)數(shù)的算法父丰，就能從已截獲的上述信息中迅速求出a或b，從而算出g ab(modq)。遺憾的是蛾扇，目前世界上根本就沒有快速的求解離散對(duì)數(shù)的算法攘烛，因此當(dāng)所選的有限域Fq很大時(shí)，a或b就很難算出镀首。
? ? ? ?離散對(duì)數(shù)形式相對(duì)比較靈活坟漱，每個(gè)發(fā)送端可以在發(fā)送每條消息是指定自己的公鑰，但接收端回復(fù)的消息也只有發(fā)送端才能解密更哄；也可通信握手階段協(xié)商密鑰芋齿，接下來(lái)根據(jù)協(xié)商的密鑰走對(duì)稱加密。
? ? ? ?資料來(lái)源：https://en.wikipedia.org/wiki/Discrete_logarithm
? ? ? ? ? ? ? ? ? ? ? ??http://blog.csdn.net/chen77716/article/details/7106485
2成翩、因式分解RSA整數(shù)
? ? ? ?所謂因式分解觅捆，即給出兩個(gè)大約數(shù)，很容易就能將它們兩個(gè)相乘麻敌。但是栅炒，給出它們的乘積，找出它們的因子就顯得不是那么容易了术羔。這就是許多現(xiàn)代密碼系統(tǒng)的關(guān)鍵所在赢赊。如果能夠找到解決整數(shù)分解問(wèn)題的快速方法，幾個(gè)重要的密碼系統(tǒng)將會(huì)被攻破级历，包括RSA公鑰算法和Blum Blum Shub隨機(jī)數(shù)發(fā)生器释移。
? ? ? ?盡管快速分解是攻破這些系統(tǒng)的方法之一，仍然會(huì)有其它的不涉及到分解的其它方法寥殖。所以情形完全可能變成這樣：整數(shù)分解問(wèn)題仍然是非常困難玩讳，這些密碼系統(tǒng)卻是能夠很快攻破。有的密碼系統(tǒng)則能提供更強(qiáng)的保證：如果這些密碼系統(tǒng)被快速破解（即能夠以多項(xiàng)式時(shí)間復(fù)雜度破解）扛禽，則可以利用破解這些系統(tǒng)的算法來(lái)快速地（以多項(xiàng)式時(shí)間復(fù)雜度）分解整數(shù)锋边。換句話說(shuō)，破解這樣的密碼系統(tǒng)不會(huì)比整數(shù)分解更容易编曼。這樣的密碼系統(tǒng)包括Rabin密碼系統(tǒng)（RSA的一個(gè)變體）以及Blum Blum Shub隨機(jī)數(shù)發(fā)生器豆巨。
? ? ? ?而RSA的安全性依賴于大數(shù)分解，但是否等同于大數(shù)分解一直未能得到理論上的證明掐场，因?yàn)闆]有證明破解RSA就一定需要作大數(shù)分解往扔。假設(shè)存在一種無(wú)須分解大數(shù)的算法，那它肯定可以修改成為大數(shù)分解算法熊户。RSA的一些變種算法已被證明等價(jià)于大數(shù)分解萍膛。不管怎樣，分解n是最顯然的攻擊方法嚷堡。人們已能分解多個(gè)十進(jìn)制位的大素?cái)?shù)蝗罗。因此艇棕，模數(shù)n必須選大一些，因具體適用情況而定串塑。
? ? ? ?RSA算法是一種非對(duì)稱密碼算法沼琉，所謂非對(duì)稱，就是指該算法需要一對(duì)密鑰桩匪，使用其中一個(gè)加密打瘪，則需要用另一個(gè)才能解密。RSA的算法涉及三個(gè)參數(shù)傻昙，n闺骚、e1、e2妆档。其中僻爽，n是兩個(gè)大質(zhì)數(shù)p、q的積过吻，n的二進(jìn)制表示時(shí)所占用的位數(shù)进泼，就是所謂的密鑰長(zhǎng)度。e1和e2是一對(duì)相關(guān)的值纤虽，e1可以任意取乳绕，但要求e1與(p-1)*(q-1)互質(zhì)；再選擇e2逼纸，要求(e2×e1)≡1(mod(p-1)×(q-1))洋措。n，e1),(n杰刽，e2)就是密鑰對(duì)菠发。其中(n，e1)為公鑰贺嫂，(n滓鸠，e2)為私鑰。RSA加解密的算法完全相同第喳，設(shè)A為明文糜俗，B為密文，則：A≡B^e2( mod n)曲饱；B≡A^e1 (mod n)悠抹；（公鑰加密體制中，一般用公鑰加密扩淀，私鑰解密）楔敌，e1和e2可以互換使用，即：A≡B^e1 (mod n)驻谆；B≡A^e2( mod n)卵凑。
? ? ? ?RSA的公鑰庆聘、私鑰均有接收端（比如Server）簽發(fā)，非常適合互聯(lián)網(wǎng)上的證書服務(wù)：服務(wù)端簽發(fā)證書勺卢，客戶端使用該證書掏觉，保證客戶端到服務(wù)端之間的通信安全。如果雙端都需要非對(duì)稱加密值漫，則雙方都必須發(fā)布公鑰，并且公鑰不能頻繁變更织盼，做不到每個(gè)端點(diǎn)一個(gè)公鑰杨何，因此，任何一個(gè)接收端都可以查看發(fā)送端的消息（公鑰解密）沥邻。
? ? ? ?資料來(lái)源：https://en.wikipedia.org/wiki/RSA_Factoring_Challenge
? ? ? ? ? ? ? ? ? ? ? ??https://en.wikipedia.org/wiki/RSA_(cryptosystem)
? ? ? ? ? ? ? ? ? ? ? ??https://en.wikipedia.org/wiki/Integer_factorization
3危虱、量子算法及量子計(jì)算機(jī)
? ? ? ?量子分解算法利用量子計(jì)算的并行性，可以快速分解出大數(shù)的質(zhì)因子唐全，將使量子計(jì)算機(jī)很容易破解目前廣泛使用的密碼如RSA公鑰加密系統(tǒng)埃跷，嚴(yán)重威脅到銀行、網(wǎng)絡(luò)和電子商務(wù)等的信息安全以及國(guó)家安全邮利。因此弥雹，Shor算法的提出迅速引起了世界各國(guó)對(duì)量子計(jì)算研究的高度關(guān)注。
? ? ? ?而量子計(jì)算機(jī)（quantum computer）是一類遵循量子力學(xué)規(guī)律進(jìn)行高速數(shù)學(xué)和邏輯運(yùn)算延届、存儲(chǔ)及處理量子信息的物理裝置剪勿。當(dāng)某個(gè)裝置處理和計(jì)算的是量子信息，運(yùn)行的是量子算法時(shí)方庭，它就是量子計(jì)算機(jī)厕吉。
? ? ? ?量子計(jì)算機(jī)在密碼破解上有著巨大潛力，當(dāng)今主流的非對(duì)稱（公鑰）加密算法械念，如RSA加密算法头朱，大多數(shù)都是基于于大整數(shù)的因式分解或者有限域上的離散指數(shù)的計(jì)算這兩個(gè)數(shù)學(xué)難題。他們的破解難度也就依賴于解決這些問(wèn)題的效率龄减。傳統(tǒng)計(jì)算機(jī)上项钮，要求解這兩個(gè)數(shù)學(xué)難題，花費(fèi)時(shí)間為指數(shù)時(shí)間（即破解時(shí)間隨著公鑰長(zhǎng)度的增長(zhǎng)以指數(shù)級(jí)增長(zhǎng)）欺殿，這在實(shí)際應(yīng)用中是無(wú)法接受的寄纵。而為量子計(jì)算機(jī)量身定做的秀爾算法可以在多項(xiàng)式時(shí)間內(nèi)（即破解時(shí)間隨著公鑰長(zhǎng)度的增長(zhǎng)以k次方的速度增長(zhǎng)，其中k為與公鑰長(zhǎng)度無(wú)關(guān)的常數(shù)）進(jìn)行整數(shù)因式分解或者離散對(duì)數(shù)計(jì)算脖苏，從而為RSA程拭、離散對(duì)數(shù)加密算法的破解提供可能。但其它不是基于這兩個(gè)數(shù)學(xué)問(wèn)題的公鑰加密算法棍潘，比如橢圓曲線加密算法恃鞋，量子計(jì)算機(jī)還無(wú)法進(jìn)行有效破解 崖媚。
? ? ? ?資料來(lái)源：https://en.wikipedia.org/wiki/Quantum_computing
三、文章的算法
sage代碼
RSA加密解密過(guò)程：
# randomly select some prime numbers
p = random_prime ( 1000 ) ; p 191
q = random_prime ( 1000 ) ; q 601
# compute the modulus
N = p * q
R = IntegerModRing ( N )
Phi_N = ( p-1 ) * ( q-1 )
# we can choose the encrypt key to be anything
# relatively prime to Phi_N
e = 17
gcd ( d , phi_N ) 1
# the decrypt key is the multiplicative inverse
# of d mod phi_N
d = xgcd ( d , phi_N ) [1] % phi_N
d 60353
# now we will encrypt/decrypt some random 7 digit numbers
P = randint ( 1 , 127 ) ; P 97
# encrypt
C = R ( P ) ^ e ; C 46685
# decrypt
R ( C ) ^ d 97
P = randint ( 1 , 127 ) ; P 46
# encrypt
C = R ( P ) ^ e ; C 75843
# decrypt
R ( C ) ^ d 46
P = randint ( 1 , 127 ) ; P 3
# encrypt
C = R ( P ) ^ e ; C 288
# decrypt
R ( C ) ^ d 3
對(duì)大整數(shù)進(jìn)行運(yùn)算：
p = random_prime ( 1000000000 ) ; p 114750751
q = random_prime ( 1000000000 ) ; q 8916569
N = p * q
R = IntegerModRing ( N )
Phi_N = ( p-1 ) * ( q-1 )
e = 2 ^ 16 + 1
d = xgcd ( d , phi_N ) [1] % phi_N
d 237510735093473
P = randint ( 1 , 1000000 ) ; P 955802
C = R ( P ) ^ e
R ( C ) ^ d 955802
四恤浪、未來(lái)的研究方向畅哑、未解決的難題等
? ? ? ?目前的難題是量子算法不夠精良，不夠方便應(yīng)用水由。未來(lái)的研究方向還要繼續(xù)優(yōu)化量子算法荠呐，例如用于分解一般整數(shù)的shor算法，把一個(gè)隨機(jī)群元素取冪到一個(gè)長(zhǎng)度為l+ m位的指數(shù)砂客，其中元素的階數(shù)r范圍或限制條件是r <2m和l = m / s泥张，量子算法被執(zhí)行多次后，以整數(shù)j1鞠值，j2媚创，...的形式產(chǎn)生部分結(jié)果，最后就像
類似彤恶。也要在L里面尋求一個(gè)非0的整數(shù)r钞钙，可以使算法更為方便和簡(jiǎn)單的運(yùn)行。
? ? ? ?最重要的方向還是在優(yōu)化算法后声离，制造出真正意義上的量子計(jì)算機(jī)芒炼，破解算法，量子數(shù)值計(jì)算术徊，量子系統(tǒng)的模擬等等好多復(fù)雜的問(wèn)題將會(huì)迎刃而解焕议。
