15級網(wǎng)絡(luò)工程6班 趙雪婷 20152100213?
閱讀Martin Eker?a ，Johan H?astad在17年二月份發(fā)表的Quantum algorithms for?computing short discrete logarithms and factoring RSA integers的文章，有所收獲。
文章基于量子計算機上主要描述了計算短離散對數(shù)的量子算法和分解RSA大整數(shù)量子算法。
一、歸納文章主要思想與工作：
? 計算機通常被認為是一個通用的計算設(shè)備；即，它被認為能夠在至多一個多項式系數(shù)計算時間成本模擬任何物理計算設(shè)備：目前尚不清楚這是否是真的在考慮量子力學(xué)。一些研究人員，從David Deutsch開始，已經(jīng)發(fā)展了量子力學(xué)的計算機模型，研究了它們的計算性能。本文給出了拉斯維加斯算法尋找因數(shù)分解和離散對數(shù)的整數(shù)的量子計算機上，采取一系列步驟中輸入的大小，是多項式如被分解的整數(shù)位數(shù)。這兩個問題通常被認為是難在經(jīng)典計算機上已使用的幾個提議的密碼系統(tǒng)為基礎(chǔ)。因此我們給出量子密碼分析的第一個例子。
? 在本文中，我們概括為計算短的離散對數(shù)先前推出的以{ \\ AA }以便為次，算法需要一方面執(zhí)行的數(shù)量不同的權(quán)衡之間的量子算法，以及算法的復(fù)雜性，要求它對另一方面量子計算機。此外，我們還描述了計算短離散對數(shù)的算法的應(yīng)用。特別是，我們展示了其他重要的問題，如分解RSA整數(shù)和尋找邊信息下的群的次序的問題，可以改寫為短離散對數(shù)問題。這立即引起一個算法分解RSA的整數(shù)比短的一般分解算法在某種意義上說，它對較小的要求對量子計算機那么復(fù)雜。在我們的算法和Shor算法，主要的障礙是計算疊加模冪運算。當(dāng)保理n位整數(shù)，指數(shù)是長度在Shor算法2n位，相比略超過n / 2位在我們的算法。
二、討論相關(guān)技術(shù):
量子計算算法：
? 量子計算機利用量子力學(xué)原理進行計算，具有量子并行計算的優(yōu)勢，能夠超越經(jīng)典計算1990年中期，量子算法取得突破，舒爾(Shor)構(gòu)造了大數(shù)質(zhì)因子的量子算法，葛洛沃(Grover)構(gòu)造了無序數(shù)據(jù)庫的量子搜索算法，引起了人們對量子計算的重視，極大地推動了量子計算的研究.文章簡單介紹了幾個典型的量子算法以及量子算法研究的一些新進展.
離散對數(shù)：
? 是在整數(shù)中，一種基于同余運算和原根的一種對數(shù)運算：當(dāng)模m有原根時，設(shè)L為模m的一個原根，則當(dāng)？x≡L^k(mod m)時： IndLx≡?k (mod Φ(m))，此處的IndLx為 x以整數(shù)L為底，模Φ(m)時的離散對數(shù)值。或者簡單描述離散對數(shù)問題為：給定一個質(zhì)數(shù)p，和有限域Zp上的一個本原元a，對Zp上整數(shù)b，尋找唯一的整數(shù)c，使得a^c≡b(mod p)。一般的，如果仔細選擇p，則認為該問題是難解的，且目前還沒有找到計算離散對數(shù)問題的多項式時間算法。為了抵抗已知的攻擊，p至少應(yīng)該是150位的十進制整數(shù)，且p-1至少有一個大的素數(shù)因子。
? 離散對數(shù)公鑰加密算法是目前最為熱門的公鑰加密算法 ，其安全性要遠遠高于基于大數(shù)分解的RSA算法。
首先說明一下上述三位科學(xué)家公鑰密碼體制的運作過程（假定A和B兩個人要在一個不安全通道如因特網(wǎng)上形成密鑰以備日后加密解密所用）。
首先，A、B兩人要共同公開約定一個素數(shù)q和有限域Fq中的一個生成元g；
A選定一個隨機數(shù)a∈{1，2，…，q-1}（a可以認為是A之私鑰），并將g a(modq)傳送給B；
B選定一個隨機數(shù)b∈{1，2，…，q-1}（b可以認為是B之私鑰），并將gb(modq)傳送給A；
此時A可以算出(g b)a(modq)，B也可以算出(g a)b(modq)，由于(gb)a(modq) = (g a)b(modq) = g ab(modq)，因此，A和B就形成了一個公共的密鑰g ab(modq)，日后便可以此鑰來進行傳統(tǒng)的加密解密計算，從而達到在不安全的通道上進行保密通訊的目的。
顯然，敵方可以截獲到g，q，g a(modq)，g b(modq)。因此，如果敵方有快速的求解離散對數(shù)的算法，就能從已截獲的上述信息中迅速求出a或b，從而算出g ab(modq)。遺憾的是，目前世界上根本就沒有快速的求解離散對數(shù)的算法，因此當(dāng)所選的有限域Fq很大時，a或b就很難算出。
3.量子計算機：
? 量子計算機（quantum computer）是一類遵循量子力學(xué)規(guī)律進行高速數(shù)學(xué)和邏輯運算、存儲及處理量子信息的物理裝置。當(dāng)某個裝置處理和計算的是量子信息，運行的是量子算法時，它就是量子計算機。量子計算機的概念源于對可逆計算機的研究。研究可逆計算機的目的是為了解決計算機中的能耗問題。
4.RSA數(shù)分解：
? RSA算法是一種用數(shù)論構(gòu)造的、被認為理論上相當(dāng)成熟的公鑰密碼體制，并廣泛地應(yīng)用于密鑰管理、數(shù)字簽名等方面?；跀?shù)論中2個大素數(shù)乘積所得整數(shù)n和選取滿足一定條件的整數(shù)e組成公開密鑰(e,?n)，并選取特定私鑰d組成私有密鑰對(d,?n)。RSA算法的安全性是基于數(shù)論中大整數(shù)分解的困難性。對RSA加密體制的攻擊來自多方面，主要有因式分解和旁路攻擊方法等，而對加密算法的攻擊是檢驗算法安全性的標志。在對n的因式分解方法中，在給定e和n的情況下，確定d的計算量至少等價于整數(shù)分解問題。目前，比較常用的因式分解方法有試除法、Fermat分解法、Pollard’s?rho分解法、Pollard’s?P-1分解法、Dixon分解法、連分數(shù)分解法、二次篩法、多多項式二次篩法、數(shù)域篩法(NFS)和橢圓曲線分解法等。其中，數(shù)域篩法被認為是當(dāng)前最有效的大數(shù)分解算法。在這些算法中，大多是基于求同余式
22(mod)xyn≡且(mod)xyn≠±所構(gòu)成的完全平方數(shù)x和y，只要求出x和y，即可通過求gcd(x+y,?n)和gcd(x–y,?n)達到分
解n的目的。它們的分解效率取決于構(gòu)造的算法技巧。而隨著密鑰n增大到1?024位以上，分解難度大大地增大。
（一）量子計算
? 量子計算是一種遵循量子力學(xué)規(guī)律調(diào)控量子信息單元進行計算的新型計算模式。對照于傳統(tǒng)的通用計算機，其理論模型是通用圖靈機；通用的量子計算機，其理論模型是用量子力學(xué)規(guī)律重新詮釋的通用圖靈機。從可計算的問題來看，量子計算機只能解決傳統(tǒng)計算機所能解決的問題，但是從計算的效率上，由于量子力學(xué)疊加性的存在，目前某些已知的量子算法在處理問題時速度要快于傳統(tǒng)的通用計算機。
1）首先，先了解量子系統(tǒng)。每個狀態(tài)位用|j>表示（0≤ j< 2n），狀態(tài)的疊加即為量子系統(tǒng)。系統(tǒng)表達式函數(shù)如下：
（其中復(fù)振幅
aj?∈?R是一個非負實波，相位
）故而，系統(tǒng)表達函數(shù)亦可表示為：
2）通過建設(shè)性干預(yù)手段，離散量子傅里葉變換算法（QFT）放大一系列所需要的狀態(tài)的幅度，所需狀態(tài)的的折疊概率會增大。如果量子比特形成了最大程度的糾纏，他們的波函數(shù)坍縮結(jié)果就完全相關(guān)。
QFT將每個狀態(tài)映射到n個量子位寄存器中
所以，QFT映射下的量子系統(tǒng)函數(shù)為
系統(tǒng)疊加到k的概率為
在和的運算中術(shù)語用向量C表示。如果向量C幾乎指向相同一個方向，那么它們的規(guī)范總和有很大可能概率。那么我們就說，對于k，建立了建設(shè)性干預(yù)。
主張一：
（二）計算短離散對數(shù)
計算離散對數(shù)可用于攻擊一些非對稱加密算法，例如DH加密，選擇和比較非對稱密碼參數(shù)。計算短離散對數(shù)的生成算法包括兩個階段：初始化量子階段和經(jīng)典后處理階段。
初始化量子階段：輸入生成元g和x = [d] g得到一對（j,k）。
經(jīng)典后處理階段：用一個經(jīng)典的算法來描述，基于lattice-based技術(shù)，經(jīng)典算法輸入一系列s對（j,k），計算輸出d。
具體算法如下：
令：
int d（0
固定int s>=1;
int l close to m/s；
g為階數(shù)r>=2^(l+m)+2^ld的一個有限循環(huán)群的生成元；
g疊加到長度為l + m位的指數(shù)上的指數(shù)運算
input g，x = [d] g；
output （j,k）;
when s>=1
calculate （j,k）;
return d。
（解決離散對數(shù)問題d = log?g?x）
Tips1
良好對的定義:
當(dāng)j為整數(shù)（0<=j<2^(l+m)），如果
（j決定k,dj mod 2^(l+m)，最高階為l）
至少有2^(l+m-1)個不同的j，才會有一個k，使得（j,k）為良好對。
Tips2
為了降低產(chǎn)生一個良好對的概率，我們首先需要對（a,b）數(shù)量的下界產(chǎn)生具體確定的e
定義：Te表示對（a,b）的數(shù)量，e=a-bd
（其中，a,b均為整數(shù)并且0<=a<2^(l+m),0<=b<2^l）
文章主張二：
文章主張三：
文章主張四：
從算法的單個執(zhí)行中，獲得特別良好對（j,k）的概率至少為2^(-m-l-2)
算法單次運行結(jié)果產(chǎn)生一副良好對的概率至少為2^(-3)
Tips3
基于lattice-based技術(shù)，經(jīng)典算法輸入一系列s對（j,k），計算輸出d
Lattice格子定義：（L由下列行跨度產(chǎn)生的整數(shù)）
（三）分解大整數(shù)
首先，我們通過將分解因式的問題作為解短離散對數(shù)問題對待，來獲得兩個因子。一個方法就是N近似φ（N），這使得我們解決短的離散對數(shù)問題時不需要事先知道順序。其次，我們通過執(zhí)行量子算法產(chǎn)生一系列的部分結(jié)果來獲得兩個因素。我們可以基于lattice-based技術(shù)在經(jīng)典后期處理中恢復(fù)離散對數(shù)d。它從產(chǎn)生的一系列部分結(jié)果中構(gòu)造格L和向量v，通過L趨近于V恢復(fù)d。
具體算法如下：
任意素數(shù)p,q（p>2^(n-1),q<2^n）;
?N=p*q;
φ（N）=(p-1)(q-1);
t>=gcd(p-1,q-1);
φ（N）/t>(p+q-2)/2;
G的生成元為g(1
根據(jù)g和x計算短離散對數(shù)d=（p+q-2）/2;
when(0
m=n+1;
階數(shù)φ（N）/t>=2^(l+m+1));
if s>=1，l=m/s=(n+1)/s;
t<2^(n-l-4)概率很高;
φ（N）=(p-1)(q-1)>=2^(2(n-1))'
N=(2d-q+2)q? （其中2d+2=p+q）
if c=d+1，
return p,q；
四、指出未來的研究方向、未解決的難題等：
? 自上世紀20年代以來，隨著薛定諤、愛因斯坦、海森伯格、狄拉克等人所建立起的量子力學(xué)不斷發(fā)展，以及實驗水平的不斷提高，人們對于量子力學(xué)有了更加深刻但仍不完善的理解與認知。量子計算機，作為站在巨人肩膀上的產(chǎn)物，因其強大的并行計算能力，受到各國政府、學(xué)者、企業(yè)的重視和追逐，也正是因此，量子計算機的發(fā)展勢如破竹。
? 就現(xiàn)階段而言，量子計算機的發(fā)展方向即為從理論階段轉(zhuǎn)為可使用的狀態(tài)。隨著目前各國實業(yè)界巨擘如Google、微軟的巨額投入，以及學(xué)術(shù)界、政府部門的鼎力支持，未來10年內(nèi)實現(xiàn)“小”而可用的量子計算機指日可待。
