秀爾演算法破解比特幣

㈠ 量子計算機是什麼，相比傳統計算機有何厲害之處

自1946年第一台電腦發明至今，隨著半導體產業的數次飛躍，計算機性能得到了突飛猛進的發展，2016年美國勞倫斯伯克利國家實驗室將現有的計算機晶體管製程縮小到了1納米，打破了7納米的物理極限，雖然說這代表著在同等體積下晶元可以集成更多的電路，但是由於晶體管大小僅與幾個原子相當就會發生量子隧穿效應，而在量子領域傳統物理學將不再適用，傳統計算機也無法工作。

因此早在上世紀80年代科學家們就開始思考，能不能利用量子特性製造出一台量子計算機，在傳統計算機處理數據時，晶體管就像是一個開關，它允許或者阻止電流通過，由此形成的高低電信號就可以寫成0，1這兩個數，也就是計算機信息量的最小單位比特。

但是這台量子計算機只有53個量子位，僅破解加密系統就至少需要幾千個量子位，所以說實現量子霸權還遠遠不夠，想要將量子計算機真正應用大加密破譯，葯物研製，保密通信等領域仍有很長的路要走。

㈡ 清華大學量子計算機祖沖

量子計算機（quantum computer）是一類遵循量子力學規律進行高速數學和邏輯運算、納旁漏存儲及處理量子信息的物理裝置。當某個裝置處理和計算的是量子信息，運行的是量子演算法時，它就是量子計算機。量子計算機的概念源於對可逆計算機的研究。研究可逆計算機的目的是為了解決計算機中的能耗問題。量子計算機到底為何物

1982年，美國著名物理物學家理查德·費曼在一個公開的演講中提出利用量子體系實現通用計算的新奇想法。緊接其後，1985年，英國物理學家大衛·杜斯提出了量子圖靈機模型 。理查德·費曼當時就想到如果用量子系統所構成的計算機來模擬量子現象則運算時間可大幅度減少，從而量子計算機的洞爛概念誕生了。
量子計算機的原理更多
量子計算機是一類遵循量子力學規律進行高速數學和邏輯運算、存儲及處理量子信息的物理裝置。其基本規律包括不確定原理、對應原理和波爾理論等。它應用常見，如半導體材料為主的電子產品，激光刻錄光碟，核磁共振等。
量子計算機的優越性更多
量子計算機對每一個疊加分量實現的變換相當於一種經典計算，所有這些經典計算同時完成，並按一定的概率振幅疊加起來，給出量子計算機的輸出結果。這種計算稱為量子並行計算，也是量子計算機最重要的優越性。
有趣的量子理論
量子論的一些基本論點顯得並不「玄乎」，但它的推論顯得很「玄」。我們假設一個「量子」距離也就是最小距離的兩個端點A和B。按照量子論，物體從A不經過A和B中的任何一個點就能直接到達B。換句話說，物體在A點突然消失，與此同時在B點出現。除了神話，你無法在現實的宏觀世界找到一個這樣的例子。量子論把人們在宏觀世界裡建立起來的「常識」和「直覺」打了個七零八落。[1]
薛定諤之貓是關於量子理論的一個理想實驗。實驗內容是：這只貓十分可憐，它被封在一個密室里，密室里有食物有毒葯。毒葯瓶上有一個錘子，錘子由一個電子開關控制，電子開關由放射性原子控制。如果原子核衰變，則放出α粒子，觸動電子開關，錘子落下，砸碎毒葯瓶，釋放出裡面的氰化物氣體，貓必死無疑。這個殘忍的裝置由奧地利物理學家埃爾溫·薛定諤所設計，所以此貓便叫做薛定諤貓。量子理論認為：如果沒有揭開蓋子，進行觀察，我們永遠也不知道貓是死是活，它將永遠處於非死非活的疊加態，這與我們的日常經驗嚴重相違。[1]
瑞典皇家科學院2012年10月9日宣布，將2012年諾貝爾物理學獎授予法國物理學家塞爾日·阿羅什和美國物理學家戴維·瓦恩蘭，以表彰他們在量子物理學方面的卓越研究。他說，這兩位物理學家用突破性的實驗方法使單個粒子動態系統可被測量和操作。他們獨立發明並優化了測量與操作單個粒子的實驗方法，而實驗中還能保持單個粒子的量子物理性質，這一物理學研究的突破在之前是不可想像的。[2]
研究歷史編輯
量子計算機，早先由理查德·費曼提出，一開始是從物理現象的模擬而來的。可他發現當模擬量子現象時，因為龐大的希爾伯特空間使資料量也變得龐大，一個完好的模擬所需的運算時間變得相當可觀，甚至是不切實際的天文數字。理查德·費曼當時啟握就想到，如果用量子系統構成的計算機來模擬量子現象，則運算時間可大幅度減少。量子計算機的概念從此誕生。[1]
量子計算機，或推而廣之——量子資訊科學，在1980年代多處於理論推導等紙上談兵狀態。一直到1994年彼得·秀爾（Peter Shor）提出量子質因子分解演算法[3] 後，因其對通行於銀行及網路等處的RSA加密演算法破解而構成威脅後，量子計算機變成了熱門的話題。除了理論之外，也有不少學者著力於利用各種量子系統來實現量子計算機。[1]
20世紀60年代至70年代，人們發現能耗會導致計算機中的晶元發熱，極大地影響了晶元的集成度，從而限制了計算機的運行速度。研究發現，能耗來源於計算過程中的不可逆操作。那麼，是否計算過程必須要用不可逆操作才能完成呢？問題的答案是：所有經典計算機都可以找到一種對應的可逆計算機，而且不影響運算能力。既然計算機中的每一步操作都可以改造為可逆操作，那麼在量子力學中，它就可以用一個幺正變換來表示。早期量子計算機，實際上是用量子力學語言描述的經典計算機，並沒有用到量子力學的本質特性，如量子態的疊加性和相乾性。在經典計算機中，基本信息單位為比特，運算對象是各種比特序列。與此類似，在量子計算機中，基本信息單位是量子比特，運算對象是量子比特序列。所不同的是，量子比特序列不但可以處於各種正交態的疊加態上，而且還可以處於糾纏態上。這些特殊的量子態，不僅提供了量子並行計算的可能，而且還將帶來許多奇妙的性質。與經典計算機不同，量子計算機可以做任意的幺正變換，在得到輸出態後，進行測量得出計算結果。因此，量子計算對經典計算作了極大的擴充，在數學形式上，經典計算可看作是一類特殊的量子計算。量子計算機對每一個疊加分量進行變換，所有這些變換同時完成，並按一定的概率幅疊加起來，給出結果，這種計算稱作量子並行計算。除了進行並行計算外，量子計算機的另一重要用途是模擬量子系統，這項工作是經典計算機無法勝任的。[1]
1994年，貝爾實驗室的專家彼得·秀爾（Peter Shor）證明量子計算機能完成對數運算，[4] 而且速度遠勝傳統計算機。這是因為量子不像半導體只能記錄0與1，可以同時表示多種狀態。如果把半導體計算機比成單一樂器，量子計算機就像交響樂團，一次運算可以處理多種不同狀況，因此，一個40位元的量子計算機，就能解開1024位元的電子計算機花上數十年解決的問題。[1]
隨著計算機科學的發展，史蒂芬·威斯納在1969年最早提出「基於量子力學的計算設備」。而關於「基於量子力學的信息處理」的最早文章則是由亞歷山大·豪勒夫（1973）、帕帕拉維斯基（1975）、羅馬·印戈登（1976）和尤里·馬尼（1980）年發表。史蒂芬·威斯納的文章發表於1983年[8]。1980年代一系列的研究使得量子計算機的理論變得豐富起來。1982年，理查德·費曼在一個著名的演講中提出利用量子體系實現通用計算的想法。緊接著1985年大衛·杜斯提出了量子圖靈機模型 [9]。人們研究量子計算機最初很重要的一個出發點是探索通用計算機的計算極限。當使用計算機模擬量子現象時，因為龐大的希爾伯特空間而數據量也變得龐大。一個完好的模擬所需的運算時間則變得相當可觀，甚至是不切實際的天文數字。理查德·費曼當時就想到如果用量子系統所構成的計算機來模擬量子現象則運算時間可大幅度減少，從而量子計算機的概念誕生。[3]
演算法理論編輯
經典演算法
量子計算機在1980年代多處於理論推導狀態。1994年彼得·秀爾（Peter Shor）提出量子質因子分解演算法後，因其對於通行於銀行及網路等處的RSA加密演算法可以破解而構成威脅之後，量子計算機變成了熱門的話題，除了理論之外，也有不少學者著力於利用各種量子系統來實現量子計算機。[1]
半導體靠控制集成電路來記錄及運算信息，量子計算機則希望控制原子或小分子的狀態，記錄和運算信息。 1994年，貝爾實驗室的專家彼得·秀爾（Peter Shor）證明量子計算機能做出離散對數運算[11]，而且速度遠勝傳統計算機。因為量子不像半導體只能記錄0與1，可以同時表示多種狀態。如果把半導體比成單一樂器，量子計算機就像交響樂團，一次運算可以處理多種不同狀況，因此，一個40比特的量子計算機，就能在很短時間內解開1024位計算機花上數十年解決的問題。[4]
通用計算
量子計算機，顧名思義，就是實現量子計算的機器。是一種使用量子邏輯進行通用計算的設備。不同於電子計算機（或稱傳統電腦），量子計算用來存儲數據的對象是量子比特，它使用量子演算法來進行數據操作。[1]
要說清楚量子計算，首先看經典計算機。經典計算機從物理上可以被描述為對輸入信號序列按一定演算法進行變換的機器，其演算法由計算機的內部邏輯電路來實現。[1]
1.其輸入態和輸出態都是經典信號，用量子力學的語言來描述，也即是：其輸入態和輸出態都是某一力學量的本徵態。如輸入二進制序列0110110，用量子記號，即|0110110>。所有的輸入態均相互正交。對經典計算機不可能輸入如下疊加態：C1|0110110 >+ C2|1001001>。[1]
2.經典計算機內部的每一步變換都演化為正交態，而一般的量子變換沒有這個性質，因此，經典計算機中的變換（或計算）只對應一類特殊集。[1]
量子計算機
量子計算機(4張)
相應於經典計算機的以上兩個限制，量子計算機分別作了推廣。量子計算機的輸入用一個具有有限能級的量子系統來描述，如二能級系統（稱為量子比特（qubits）），量子計算機的變換（即量子計算）包括所有可能的幺正變換。[1]
1.量子計算機的輸入態和輸出態為一般的疊加態，其相互之間通常不正交；[1]
2量子計算機中的變換為所有可能的幺正變換。得出輸出態之後，量子計算機對輸出態進行一定的測量，給出計算結果。[1]
承載16個量子位的硅晶元
承載16個量子位的硅晶元
由此可見，量子計算對經典計算作了極大的擴充，經典計算是一類特殊的量子計算。量子計算最本質的特徵為量子疊加性和量子相乾性。量子計算機對每一個疊加分量實現的變換相當於一種經典計算，所有這些經典計算同時完成，量子並行計算。[1]
無論是量子並行計算還是量子模擬計算，本質上都是利用了量子相乾性。遺憾的是，在實際系統中量子相乾性很難保持。在量子計算機中，量子比特不是一個孤立的系統，它會與外部環境發生相互作用，導致量子相乾性的衰減，即消相干（也稱「退相干」）。因此，要使量子計算成為現實，一個核心問題就是克服消相干。而量子編碼是迄今發現的克服消相干最有效的方法。主要的幾種量子編碼方案是：量子糾錯碼、量子避錯碼和量子防錯碼。量子糾錯碼是經典糾錯碼的類比，是目前研究的最多的一類編碼，其優點為適用范圍廣，缺點是效率不高。[1]
正如大多數人所了解的，量子計算機在密碼破解上有著巨大潛力。當今主流的非對稱（公鑰）加密演算法，如RSA加密演算法，大多數都是基於於大整數的因式分解或者有限域上的離散指數的計算這兩個數學難題。他們的破解難度也就依賴於解決這些問題的效率。傳統計算機上，要求解這兩個數學難題，花費時間為指數時間（即破解時間隨著公鑰長度的增長以指數級增長），這在實際應用中是無法接受的。而為量子計算機量身定做的秀爾演算法可以在多項式時間內（即破解時間隨著公鑰長度的增長以k次方的速度增長，其中k為與公鑰長度無關的常數）進行整數因式分解或者離散對數計算，從而為RSA、離散對數加密演算法的破解提供可能。但其它不是基於這兩個數學問題的公鑰加密演算法，比如橢圓曲線加密演算法，量子計算機還無法進行有效破解[3] 。
針對對稱（私鑰）加密，如AES加密演算法，只能進行暴力破解，而傳統計算機的破解時間為指數時間，更准確地說，是 ，其中 為密鑰的長度。而量子計算機可以利用Grover演算法進行更優化的暴力破解，其效率為 ，也就是說，量子計算機暴力破解AES-256加密的效率跟傳統計算機暴力破解AES-128是一樣的。[1]
更廣泛而言，Grover演算法是一種量子資料庫搜索演算法，相比傳統的演算法，達到同樣的效果，它的請求次數要少得多。對稱加密演算法的暴力破解僅僅是Grover演算法的其中一個應用。[1]
在利用EPR對進行量子通訊的實驗中科學家發現，只有擁有EPR對的雙方才可能完成量子信息的傳遞，任何第三方的竊聽者都不能獲得完全的量子信息，正所謂解鈴還需系鈴人，這樣實現的量子通訊才是真正不會被破解的保密通訊。[1]
此外量子計算機還可以用來做量子系統的模擬，人們一旦有了量子模擬計算機，就無需求解薛定諤方程或者採用蒙特卡羅方法在經典計算機上做數值計算，便可精確地研究量子體系的特徵。

㈢ 秀爾演算法的簡介

比較不正式的說，它解決題目如下：給定一個整數N，找出他的質因子。
在一個量子計算機上面，要返握分解整數N, 秀爾演算法的運作需要多項式時間 (時間是log N的某個多項式這么長,log N在這里的意義是輸入的檔案長度)。 更精確的說，這個演算法花費O((log N))的時間，展示出質因子分解問題可以使用量子計算機以多項式時間解出，因此在復雜度類茄螞 BQP裡面。這比起傳統已知最快的因子分解演算法, 普通數域篩選法, 其花費次指數時間 -- 大約O(e (log log N))，還要快了一個指數的差異。
秀爾演算法非常重要，因為它代表使用量子計算機的話，我們可以用來破解已被廣泛使用的公開密鑰加密方法，也就是RSA加密演算法。RSA演算法的基礎在於假設了我們不能很有效率的分解一個已知的整數。就目前所知，這假設對傳統的(也就是非量子)電腦為真；沒有已知傳統的演算法可以在多項式時間內解決這個問題。然而，秀爾演算法展示了因子分解這問題在量子計算機上可以很有效率的解決，所以一個足夠大的量子計算機可以破解RSA。這對於鼓漏納慶吹我們去建立量子計算機和去研究新的量子計算機演算法，是一個非常大的動力。
在2001年，IBM的一個小組展示了秀爾演算法的實做, 使用NMR實做的量子計算機，以及7個量子位元，將15分解成3 × 5。 然而，對IBM的實驗的是否是量子計算的真實展示，則有一些疑慮出現，因為沒有纏結現象被發現。 在IBM的實做之後，有其他的團隊以光學量子位元實做秀爾演算法，並強調其纏結現象可被觀察到。

㈣ 量子計算機的演算法理論

量子計算機在1980年代多處於理論推導狀態。1994年彼得·秀爾（Peter Shor）提出量子質因子分解演算法後，因其對於通行於銀行及網路等處的RSA加密演算法可以破解而構成威脅之後，量子計算機變成了熱門的話題，除了理論之外，也有不少學者著力於利用各種量子系統來實現量子計算機。
半導體靠控制集成電路來記錄及運算信息，量子計算機則希望控制原子或小分子的狀態，記錄和運算信息。 1994年，貝爾實驗裂笑室的專家彼得·秀爾（Peter Shor）證明量子計算機能做出離散對數運算[11]，而且速度遠勝傳統計算機。因為量子不像半導體只能記錄0與1，可以同時表示多種狀態。如果把半導體比成單一樂器，量子計算機就像交響樂團，一次運算可以處理多種不同狀況，因此，一個40比特的量子計算機，就能在很短時間內解開1024位計算機花上數十年解決的問題。 量子計算機，顧名思義，就是實現量子計算的機器。是一種使用量子邏輯進行通用計算的設備。不同於電子計算機（或稱傳統電腦），量子計算用來存儲數據的對象是量子比特，它使用量子演算法來進行數據操作。
要說清楚量子計算，首先看經典計算機。經典計算機從物理上可以被描述為對輸入信號序列按一定演算法進行變換的機器，其演算法由計算機的內部邏輯電路來實現。
1.其輸入態和輸出態都是經典信號，用量子力學的語言來描述，也即是：其輸入態和輸出態都是某一力學量的本徵態。如輸入二進制序列0110110，用量子記號，即|0110110>。所有的輸入態均相互正交。對經典計算機不可能輸入如下疊加態：C1|0110110 >+ C2|1001001>。
2.經典計算機內部的每一步變換都演化為正交態，而一般的量子變換沒有這個性質，因此，經典計算機中的變換（或計算）只對應一類特殊集。
相應於經典計算機的以上兩個限制，量子計算機分別作了推廣。量子計算機的輸入用一個具有有限能級的量子系統來描述，如二能級系統（稱為量子比特（qubits）），量子計算機的變換（即量子計算）包括所有可能的幺正變換。
1.量子計算機的輸入態和輸出態為一般的疊加態，其相互之間通常不正交；
2量子計算機中的變換為所有可能的幺正變換。得出輸出態之後，量子計算機對輸出態進行一定的測量，給出計算結果。
由此可見，量子計算對經典計算作了極大的擴充，經典計算是一類特殊的量子計算。量子計算最本質的特徵為量子疊加性和量子相乾性。量子計算機對每一個疊加分量實現的變換相當於一種經典計算，所有這些經典計算同時完成，量子並行計算。
無論是量子並行計算還是量子模擬計算，本質上都是利用了量子相乾性。遺憾的是，在實際系統中量子相乾性很難保持。在量子計算機中，量子比孫源野特不是一個孤立的系統，它會與外部環境發生相互作用，導致量子相乾性的衰減，即消相干（也稱「退相干」）。因此，要使量子計算成為現實，一個核心問題就是克服消相干。而量子編碼是迄今發現的克服消相干最有效的方法。主要的幾種量子編碼方案是：量子糾錯碼、量子避錯碼和量子防錯碼。量子糾錯碼是經典糾錯碼的類比，是目前研究的最多的一類編碼，其優點為適用范圍廣，缺點是效率不高。
正如大多數人所了解的，量子計算機在密碼破解上有著巨大潛力。當今主流的非對稱（公鑰）加密演算法，如RSA加密演算法，大多數都是基於於大整數的因式分解或者有限域上的離散指數的計算這兩個數學難題。他們的破解難度也就依賴於解決這些問題的效率。傳統計算機上，要求解這兩個數學難題，花費時間為指數時間（即破則喊解時間隨著公鑰長度的增長以指數級增長），這在實際應用中是無法接受的。而為量子計算機量身定做的秀爾演算法可以在多項式時間內（即破解時間隨著公鑰長度的增長以k次方的速度增長，其中k為與公鑰長度無關的常數）進行整數因式分解或者離散對數計算，從而為RSA、離散對數加密演算法的破解提供可能。但其它不是基於這兩個數學問題的公鑰加密演算法，比如橢圓曲線加密演算法，量子計算機還無法進行有效破解 。
針對對稱（私鑰）加密，如AES加密演算法，只能進行暴力破解，而傳統計算機的破解時間為指數時間，更准確地說，是 ，其中 為密鑰的長度。而量子計算機可以利用Grover演算法進行更優化的暴力破解，其效率為 ，也就是說，量子計算機暴力破解AES-256加密的效率跟傳統計算機暴力破解AES-128是一樣的。
更廣泛而言，Grover演算法是一種量子資料庫搜索演算法，相比傳統的演算法，達到同樣的效果，它的請求次數要少得多。對稱加密演算法的暴力破解僅僅是Grover演算法的其中一個應用。
在利用EPR對進行量子通訊的實驗中科學家發現，只有擁有EPR對的雙方才可能完成量子信息的傳遞，任何第三方的竊聽者都不能獲得完全的量子信息，正所謂解鈴還需系鈴人，這樣實現的量子通訊才是真正不會被破解的保密通訊。
此外量子計算機還可以用來做量子系統的模擬，人們一旦有了量子模擬計算機，就無需求解薛定諤方程或者採用蒙特卡羅方法在經典計算機上做數值計算，便可精確地研究量子體系的特徵。

㈤ TLS過程（DH 非對稱加密）

TLS 的目的便是解決數據的
一、Record 記錄協議 （對稱加解密）

二、HandShake 握手，揮手
驗證通訊雙方身份
交換加解密的安全套件
協商加密解密參數

當一個TLS會話建立好之後，會使用對稱加密的密鑰去通信，那麼如何實現事先將對稱加密的密鑰傳遞給TLS會話的另一方呢。利用的就是非對稱加密。分對稱加密比對稱加密哪明慢數千倍，所以只是使用對稱加密傳遞之後加密使用的對稱加密的密鑰。之後的加密安全性靠的是對稱加密來解決。

非對稱加密是有一把公鑰和一把私鑰，公鑰可以公開，而私鑰不能。
用公鑰加密成密文，再將密文用私鑰解密就能實現加解密過程。
而用私鑰加密，公鑰解密就是簽名認證過程。
常見的非對稱加密方式分為兩大類

RSA 沒有向前安全性，也就是需要每次的對稱加密密鑰的傳遞都是基於 公姿緩高鑰加密，服務端私鑰解密。如果服務端的私鑰丟失了，那幾年前的通信數據都有可能被解密。所以這是極度不安全的，私鑰的地位太重了，如果每次的加解密都是臨時生成的密碼來解決安全性，才不會對私鑰的安全性有如此強的依賴。在2013年的棱鏡門事件中，某個CA機構迫於美國政府壓力向其提交了CA的私鑰，這就是十分危險的。如果向前不安全，那麼之前利用該CA私鑰都會全部遭殃。所以這里說的是更安全的 DH類非對稱加密。

下圖就是DH密鑰交換的TLS握手過程

DH 密鑰交換協議，Diffile-Hellman key Exchange，簡稱 DH 或 DHE 。它可以讓雙方在完全沒有對方任何預先信息的條件下通過一個不安全的信道創建一個密鑰。

1、客戶端瀏覽器隨機生成一個值Ra，計算Pa(x,y) = Ra*Q(x,y), Q(x,y)為全世界公認的某個橢圓曲線演算法的基點。將Pa(x,y)發送至伺服器。

2、伺服器隨機生成一個值Rb，計算 Pb(x,y) = Rb * Q(x,y)。將Pb(x,y)發送到客戶端瀏覽器。

3、客戶端計算Sa(x,y) = Ra * Pb(x,y)，伺服器計算Sb(x,y)=Rb*Pa(x,y)

4、演算法保證了Sa=Sb=S, 提取其中的S的x向量作為密鑰。

為了解決上述DH的問題，引入了ECC橢圓曲線，進而進化為 ECDHE 演算法，稱為 Elliptic Curve Diffie-Hellman Key Exchange。ECC和RSA 在288位元組的長度下，破解RSA需要煮沸一勺水的能量，而破解相同位數的ECC 就需要煮沸整個地球水的能量。RSA 為了提高安全性，只能靠增大密鑰位數。尷尬的是現在的超算越來越厲害。量子計算下秀爾演算法可8h內輕松破解2048位的RSA。RSA只能再增大密鑰位數，但是再增大位數，移動端設備就慘了，你增大的密鑰是運營商要收取流量費用的，而且加解密太費電。
ECC 的數學原理是橢圓曲線和離散對數。橢圓曲線很復雜。為了提升性能，還需要選擇一個橢圓曲線，但是它不是真正的橢圓形，下面有圖可以看到，只是運算上用到了橢圓演算法。
但是ECC也有很多問題，1、ECC 可能有後門，如NSA（美國國家安全局發布的一跡尺套演算法），這個演算法就是被懷疑被植入後門了。2、而且ECC很多的演算法都被注冊專利了，一不小心就要吃官司，其專利大部分都被黑莓注冊。

ECC 橢圓曲線的定義

ECC 的演算法原理過於復雜，這里表示我也看不懂。點到為止吧。（以後看懂了再來補充）

這里的抓包結果就是用的EC DH E 演算法來進行密鑰交換的。這里選擇的曲線是 secp256r1, 在這個曲線中，基點和參數已經給出了，PubKey 也給出了。
在 TLS1.3 中，一般使用的 X25519 曲線 （蒙哥馬利曲線）

㈥ 量子計算機的工作原理，為何計算能力如此強大

1947年，美國計算機工程師霍華德·艾肯說，只需要六個比特位的電腦將能夠滿足世界的所有計算需求。當然，霍華德沒有想到科學研究以及人們生活會產生如此大量數據，個人電腦的激增和互聯網的出現，這些都推動了我們對計算能力的需求。

如果按照摩爾定律的規定，微處理器上的晶體管數量每18個月繼續增加一倍，那麼2020年或2030年將發現微處理器上的電路在原子尺度上進行測量。而到達原子尺度則不可控，所以我們的下一步是創造量子計算機，它將利用原子和分子的力量來執行記憶和處理任務。

圖靈於20世紀30年代開發的 圖靈機 是一種理論設備，由無限長度的磁帶組成，分為小方塊，每個方塊可以包含符號（1或0）或留空。讀寫設備讀取這些符號和空白，從而為機器提供執行某個程序的指令。

這聽起來很熟悉吧？

那麼，在 量子圖靈機 中，區別在於磁帶存在於量子狀態，讀寫頭也是如此。這意味著磁帶上的符號可以是0或1或0和1的疊加態；換句話說，符號同時是0和1（以及其間的所有點）。普通的圖靈機一次只能執行一次計算，但量子圖靈機可以同時執行多次計算（2的n次方）。

今天的計算機，通過操縱存在於兩種狀態之一的位來工作：0或1。量子計算機不限於兩種狀態；它們將信息編碼為量子比特，它們可以疊加存在。量子點代表原子、離子、光子或電子以及它們各自的控制設備，它們一起工作以充當計算機的存儲器和處理器。因為量子計算機可以同時包含這些 多個態 ，所以它有可能比當今最強大的超級計算機強大數萬倍。（例如，一個500量子位的計算機，它每一步就可以實現多達2的500次方的運算）

舉個簡單的例子，拿我國的 天河二號 超級計算機來比較，一個需要 天河二號 運算100年的計算，換為量子計算機的話，理論上只需要0.02秒的時間。

量子比特的疊加使量子計算機具有固有的並行性。根據物理學家David Deutsch的說法，這種並行性允許量子計算機同時處理一百萬次計算。一個50量子比特位計算機將等同與傳統超級兆埋計算機的處理能力，該計算機可以以每秒數萬億次浮點運算運行。談猛今天通用的家庭台式計算機以每秒數十億次浮點運算的速度運行。

在量子計算機的研發過程中，有 兩大難題 需要突破，一是演算法的確定，二是要選擇合適的材料和製造條件，來製造出量子計算機。

首先在演算法方面，由於量子計算機完全不同於現有的計算機系統，因此，它的整個演算法都要重新研究確定，其中由貝爾實驗的美國科學家 彼得.秀爾 所提出的 秀爾演算法 被廣泛採用。

由於量子計算機系統環境的要求極為苛刻，環境的熱輻射、電磁輻射和材料缺陷都會引起計算錯誤，因此，人們一直在尋求最適合的材料。 1 超導材料鈮，這個材料需要主機被液態氦冷凍到0.005K，即零下273.145攝氏度（比較成熟）， 2 稀土金屬，例如鐠（探究中）。

計算機科學家通過使用控制設備控制在量子計算機中充當量子位的微觀粒子。

離子阱使用光學或磁場（或兩者的組合）來捕獲離子。

光阱使用光波來捕獲和控制粒子。

量子點由半導體材料製成，用於包含和操縱電子。

半導體雜質通過使用半導體材料中的"不需要的"原子來包含電子。

超導電路允許電子在非常低的溫度下幾乎沒有電阻地流動。

下面，將介紹量子計算領域的一些最新進展

2001年來自IBM和斯坦福大學的科學家在量子計算機上成功演示了Shor演算法。Shor演算法是一種尋找數字含猜橋素數因子的方法（在密碼學中起著固有的作用）。他們使用7比特的計算機來找出15的因子，計算機正確地推斷出素因子是3和5。

2005年因斯布魯克大學的量子光學和量子信息研究所宣布他們使用離子阱創造了第一個8量子比特位的計算機。

2006年滑鐵盧和馬薩諸塞州的科學家們設計了一種12比特系統的量子控制方法。

2007年加拿大初創公司D-Wave展示了一款商用16量子比特位的計算機（獵戶座）。計算機解決了數獨謎題和其他模式匹配問題。該公司聲稱它將在2008年之前已生產出了實用的系統。

2015年3月 谷歌發布了首款達到 9量子位的晶元 ，該產品基於量子糾纏協議和線性結構進行設計，並利用名為"基偶校驗"的檢查方法，通過測量每個量子位的相互作用來追溯計算過程，從而降低因量子糾纏現象導致的計算錯誤率。

但量子計算仍處於早期發展階段，許多計算機科學家認為創建實用的量子計算機所需的技術還需要數年時間，量子計算機必須有50量子比特才能解決現實問題。

㈦ 秀爾演算法的介紹

秀爾演算法（Shor's Algorithm），以數學家彼得·秀爾命名，是一個罩襲在1994年發現的，針對整數分解這賣悶斗題目的的量子算中磨法 (在量子計算機上面運作的演算法 )。

㈧ 非對稱加密演算法 (RSA、DSA、ECC、DH)

非對稱加密需要兩個密鑰：公鑰(publickey) 和私鑰 (privatekey)。公鑰和私鑰是一對，如果用公鑰對數據加密，那麼只能用對應的私鑰解密。如果用私鑰對數據加密，只能用對應的公鑰進行解密。因為加密和解密用的是不同的密鑰，所以稱為非對稱加密。

非對稱加密演算法的保密性好，它消除了最終用戶交換密鑰的需要。但是加解密速度要遠遠慢於對稱加密，在某些極端情況下，甚至能比對稱加密慢上1000倍。

演算法強度復雜、安全性依賴於演算法與密鑰但是由於其演算法復雜，而使得加密解密速度沒有對稱加密解密的速度快。對稱密碼體制中只有一種密鑰，並且是非公開的，如果要解密就得讓對方知道密鑰。所以保證其安全性就是保證密鑰的安全，而非對稱密鑰體制有兩種密鑰，其中一個是公開的，這樣就可以不需要像對稱密碼那樣傳輸對方的密鑰了。這樣安全性就大了很多。

RSA、Elgamal、背包演算法、Rabin、D-H、ECC (橢圓曲線加密演算法)。使用最廣泛的是 RSA 演算法，Elgamal 是另一種常用的非對稱加密演算法。

收信者是唯一能夠解開加密信息的人，因此收信者手裡的必須是私鑰。發信者手裡的是公鑰，其它人知道公鑰沒有關系，因為其它人發來的信息對收信者沒有意義。

客戶端需要將認證標識傳送給伺服器，此認證標識 (可能是一個隨機數) 其它客戶端可以知道，因此需要用私鑰加密，客戶端保存的是私鑰。伺服器端保存的是公鑰，其它伺服器知道公鑰沒有關系，因為客戶端不需要登錄其它伺服器。

數字簽名是為了表明信息沒有受到偽造，確實是信息擁有者發出來的，附在信息原文的後面。就像手寫的簽名一樣，具有不可抵賴性和簡潔性。

簡潔性：對信息原文做哈希運算，得到消息摘要，信息越短加密的耗時越少。

不可抵賴性：信息擁有者要保證簽名的唯一性，必須是唯一能夠加密消息摘要的人，因此必須用私鑰加密 (就像字跡他人無法學會一樣)，得到簽名。如果用公鑰，那每個人都可以偽造簽名了。

問題起源：對1和3，發信者怎麼知道從網上獲取的公鑰就是真的？沒有遭受中間人攻擊？

這樣就需要第三方機構來保證公鑰的合法性，這個第三方機構就是 CA (Certificate Authority)，證書中心。

CA 用自己的私鑰對信息原文所有者發布的公鑰和相關信息進行加密，得出的內容就是數字證書。

信息原文的所有者以後發布信息時，除了帶上自己的簽名，還帶上數字證書，就可以保證信息不被篡改了。信息的接收者先用 CA給的公鑰解出信息所有者的公鑰，這樣可以保證信息所有者的公鑰是真正的公鑰，然後就能通過該公鑰證明數字簽名是否真實了。

RSA 是目前最有影響力的公鑰加密演算法，該演算法基於一個十分簡單的數論事實：將兩個大素數相乘十分容易，但想要對其乘積進行因式分解卻極其困難，因此可以將乘積公開作為加密密鑰，即公鑰，而兩個大素數組合成私鑰。公鑰是可發布的供任何人使用，私鑰則為自己所有，供解密之用。

A 要把信息發給 B 為例，確定角色：A 為加密者，B 為解密者。首先由 B 隨機確定一個 KEY，稱之為私鑰，將這個 KEY 始終保存在機器 B 中而不發出來；然後，由這個 KEY 計算出另一個 KEY，稱之為公鑰。這個公鑰的特性是幾乎不可能通過它自身計算出生成它的私鑰。接下來通過網路把這個公鑰傳給 A，A 收到公鑰後，利用公鑰對信息加密，並把密文通過網路發送到 B，最後 B 利用已知的私鑰，就能對密文進行解碼了。以上就是 RSA 演算法的工作流程。

由於進行的都是大數計算，使得 RSA 最快的情況也比 DES 慢上好幾倍，無論是軟體還是硬體實現。速度一直是 RSA 的缺陷。一般來說只用於少量數據加密。RSA 的速度是對應同樣安全級別的對稱密碼演算法的1/1000左右。

比起 DES 和其它對稱演算法來說，RSA 要慢得多。實際上一般使用一種對稱演算法來加密信息，然後用 RSA 來加密比較短的公鑰，然後將用 RSA 加密的公鑰和用對稱演算法加密的消息發送給接收方。

這樣一來對隨機數的要求就更高了，尤其對產生對稱密碼的要求非常高，否則的話可以越過 RSA 來直接攻擊對稱密碼。

和其它加密過程一樣，對 RSA 來說分配公鑰的過程是非常重要的。分配公鑰的過程必須能夠抵擋中間人攻擊。假設 A 交給 B 一個公鑰，並使 B 相信這是A 的公鑰，並且 C 可以截下 A 和 B 之間的信息傳遞，那麼 C 可以將自己的公鑰傳給 B，B 以為這是 A 的公鑰。C 可以將所有 B 傳遞給 A 的消息截下來，將這個消息用自己的密鑰解密，讀這個消息，然後將這個消息再用 A 的公鑰加密後傳給 A。理論上 A 和 B 都不會發現 C 在偷聽它們的消息，今天人們一般用數字認證來防止這樣的攻擊。

(1) 針對 RSA 最流行的攻擊一般是基於大數因數分解。1999年，RSA-155 (512 bits) 被成功分解，花了五個月時間（約8000 MIPS 年）和224 CPU hours 在一台有3.2G 中央內存的 Cray C916計算機上完成。

RSA-158 表示如下：

2009年12月12日，編號為 RSA-768 (768 bits, 232 digits) 數也被成功分解。這一事件威脅了現通行的1024-bit 密鑰的安全性，普遍認為用戶應盡快升級到2048-bit 或以上。

RSA-768表示如下：

(2) 秀爾演算法
量子計算里的秀爾演算法能使窮舉的效率大大的提高。由於 RSA 演算法是基於大數分解 (無法抵抗窮舉攻擊)，因此在未來量子計算能對 RSA 演算法構成較大的威脅。一個擁有 N 量子位的量子計算機，每次可進行2^N 次運算，理論上講，密鑰為1024位長的 RSA 演算法，用一台512量子比特位的量子計算機在1秒內即可破解。

DSA (Digital Signature Algorithm) 是 Schnorr 和 ElGamal 簽名演算法的變種，被美國 NIST 作為 DSS (DigitalSignature Standard)。 DSA 是基於整數有限域離散對數難題的。

簡單的說，這是一種更高級的驗證方式，用作數字簽名。不單單只有公鑰、私鑰，還有數字簽名。私鑰加密生成數字簽名，公鑰驗證數據及簽名，如果數據和簽名不匹配則認為驗證失敗。數字簽名的作用就是校驗數據在傳輸過程中不被修改，數字簽名，是單向加密的升級。

橢圓加密演算法（ECC）是一種公鑰加密演算法，最初由 Koblitz 和 Miller 兩人於1985年提出，其數學基礎是利用橢圓曲線上的有理點構成 Abel 加法群上橢圓離散對數的計算困難性。公鑰密碼體制根據其所依據的難題一般分為三類：大整數分解問題類、離散對數問題類、橢圓曲線類。有時也把橢圓曲線類歸為離散對數類。

ECC 的主要優勢是在某些情況下它比其他的方法使用更小的密鑰 (比如 RSA)，提供相當的或更高等級的安全。ECC 的另一個優勢是可以定義群之間的雙線性映射，基於 Weil 對或是 Tate 對；雙線性映射已經在密碼學中發現了大量的應用，例如基於身份的加密。不過一個缺點是加密和解密操作的實現比其他機制花費的時間長。

ECC 被廣泛認為是在給定密鑰長度的情況下，最強大的非對稱演算法，因此在對帶寬要求十分緊的連接中會十分有用。

比特幣錢包公鑰的生成使用了橢圓曲線演算法，通過橢圓曲線乘法可以從私鑰計算得到公鑰， 這是不可逆轉的過程。

https://github.com/esxgx/easy-ecc

Java 中 Chipher、Signature、KeyPairGenerator、KeyAgreement、SecretKey 均不支持 ECC 演算法。

https://www.jianshu.com/p/58c1750c6f22

DH，全稱為"Diffie-Hellman"，它是一種確保共享 KEY 安全穿越不安全網路的方法，也就是常說的密鑰一致協議。由公開密鑰密碼體制的奠基人 Diffie 和 Hellman 所提出的一種思想。簡單的說就是允許兩名用戶在公開媒體上交換信息以生成"一致"的、可以共享的密鑰。也就是由甲方產出一對密鑰 (公鑰、私鑰)，乙方依照甲方公鑰產生乙方密鑰對 (公鑰、私鑰)。

以此為基線，作為數據傳輸保密基礎，同時雙方使用同一種對稱加密演算法構建本地密鑰 (SecretKey) 對數據加密。這樣，在互通了本地密鑰 (SecretKey) 演算法後，甲乙雙方公開自己的公鑰，使用對方的公鑰和剛才產生的私鑰加密數據，同時可以使用對方的公鑰和自己的私鑰對數據解密。不單單是甲乙雙方兩方，可以擴展為多方共享數據通訊，這樣就完成了網路交互數據的安全通訊。

具體例子可以移步到這篇文章： 非對稱密碼之DH密鑰交換演算法

參考：
https://blog.csdn.net/u014294681/article/details/86705999

https://www.cnblogs.com/wangzxblog/p/13667634.html

https://www.cnblogs.com/taoxw/p/15837729.html

https://www.cnblogs.com/fangfan/p/4086662.html

https://www.cnblogs.com/utank/p/7877761.html

https://blog.csdn.net/m0_59133441/article/details/122686815

https://www.cnblogs.com/muliu/p/10875633.html

https://www.cnblogs.com/wf-zhang/p/14923279.html

https://www.jianshu.com/p/7a927db713e4

https://blog.csdn.net/ljx1400052550/article/details/79587133

https://blog.csdn.net/yuanjian0814/article/details/109815473

㈨ 量子計算機有什麼技術難點

量子計算機的技術難點有：

1、量子消相干

量子計算的相乾性是量子並行運算的精髓，但在實際情況下，量子比特會受到外界環境的作用與影響，從而產生量子糾纏。量子相乾性極易受到量子糾纏的干擾，導致量子相乾性降低，也就是所謂的消相干現象。實際的應用中，無法避免量子比特與外界的接觸，量子的相乾性也就不易得到保持。所以，量子消相干問題是目前需要解決的重要問題之一，它的解決將在一定程度上影響著量子計算機未來的發展道路。

2、量子糾纏

量子作為最小的顆粒，遵守量子糾纏規律。即使在空間上，量子之間可能是分開的，但是量子間的相互影響是無法避免的。介於此，量子糾纏技術被聯想到量子信息的傳遞領域。在一定意義上，利用量子之間飛快的交流速度從而實現信息的傳遞。

3、量子並行計算

量子計算機獨特的並行計算是經典計算機無法比擬的重要的一點。同樣是一個n位的存儲器，經典計算機存儲的結果只有一個。但是量子計算機存儲的結果可達2n。其並行計算不僅在存儲容量上遠超越了後者，而且讀取速度快，多個讀取和計算可同時進行。正是量子並行計算的重要性，它的有效應用也成為了量子計算機發展的關鍵之一。

4、量子不可克隆

量子不可克隆性，是指任何未知的量子態不存在復制的過程，既然要保持量子態不變，則不存在量子的測量，也就無法實現復制。對於量子計算機來說，無法實現經典計算機的糾錯應用以及復制功能。

(9)秀爾演算法破解比特幣擴展閱讀：

量子計算機的原理：

1、量子比特

經典計算機信息的基本單元是比特，比特是一種有兩個狀態的物理系統，用0與1表示。在量子計算機中，基本信息單位是量子比特（qubit），用兩個量子態│0>和│1>代替經典比特狀態0和1。量子比特相較於比特來說，有著獨一無二的存在特點，它以兩個邏輯態的疊加態的形式存在，這表示的是兩個狀態是0和1的相應量子態疊加。

2、態疊加原理

現代量子計算機模型的核心技術便是態疊加原理，屬於量子力學的一個基本原理。一個體系中，每一種可能的運動方式就被稱作態。在微觀體系中，量子的運動狀態無法確定，呈現統計性，與宏觀體系確定的運動狀態相反。量子態就是微觀體系的態。

3、量子糾纏

量子糾纏：當兩個粒子互相糾纏時，一個粒子的行為會影響另一個粒子的狀態，此現象與距離無關，理論上即使相隔足夠遠，量子糾纏現象依舊能被檢測到。因此，當兩粒子中的一個粒子狀態發生變化，即此粒子被操作時，另一個粒子的狀態也會相應的隨之改變。

4、量子並行原理

量子並行計算是量子計算機能夠超越經典計算機的最引人注目的先進技術。量子計算機以指數形式儲存數字，通過將量子位增至300個量子位就能儲存比宇宙中所有原子還多的數字，並能同時進行運算。函數計算不通過經典循環方法，可直接通過幺正變換得到，大大縮短工作損耗能量，真正實現可逆計算。