RSA中國大會胡磊：以代碼為基礎的公開密鑰密碼系統的代數
【51CTO.com 綜合報道】2010年10月21日-22日，為期兩天的RSA 2010大會在京召開，其中很多經典的演講都值得我們進行深入思考。那么接下來，我們就一起回顧一下中國科學院研究生院信息安全國家重點實驗室教授，胡磊，所帶來的關于《以代碼為基礎的公開密鑰密碼系統的代數》的精彩演講。更多內容請參閱RSA 2010信息安全國際論壇專題報道。
胡磊：我是第一次參加RSA的會議。我剛才聽了第一個報告主要是關于密碼的應用。但我想RSA這個會總應該有一些是關于學術方面的報告，所以我的報告主要是密碼的理論方面的。是基于糾錯碼的公鑰的代數密碼分析。
這是和我的兩個學生合作的。我首先介紹一下什么是基于糾錯碼的公鑰密碼在現代密碼學中是一個重要的題目。然后再簡要地解釋一下什么是代數密碼分析。作為例子，我們給出對一個糾錯碼的公鑰密碼的分析和實際攻擊。
其實，基于糾錯碼的公鑰密碼和公鑰密碼都是同時問世的，是在30年前問世的。McEliece提出用糾錯碼來做公鑰密碼的加密。它的困難是，假設你去解一個隨機的線性碼是困難的。這個工作在80年代和90年代前半期有很多這方面的工作。但是后來慢慢就沉寂了，因為現實的密碼應用用的不是這個活動，而是RSA團曲線。這些系統在90年代中后期以后，應用的困難問題都解決。所以得到了廣泛的應用。這些密碼其他的非RSA、非ECC的密碼研究就比較少了。最近這十年由于量子計算的進展，發現有必要再來繼續研究基于糾錯碼的這些一些密碼。這里面有兩個因素，一個因素是因自分解算法。這個算法后來由別人來推廣到解離散問題上，這是量子計算方面的結果。
那么量子計算需要在量子計算機上來實施。那么量子計算機是不是真的能夠制造出來？這個問題最近5、6年有很多進展，但這個進展都是來自于物理學家，數學家是很難聽懂量子計算實際的進展。但有一部分專家認為量子計算機在若干年以后有可能被制造出來，如果這樣的話現有的RSA和橢圓曲線這樣的公鑰密碼將不再安全。
為了應對這樣的一個局面，實際上很多人就探討能夠在量子計算下安全的一些公鑰密碼。實際上在現有的密碼學和復雜度理論中找這樣的一些問題和方案，有一些方案在公鑰密碼問世的時候就已經被提出過了，但是在當時沒有得到充分的研究。比如說基于雜錯數（音）的公鑰密碼這只是做數字簽名，不能做加密的。這個系統德國的當師特（音）已經實施了。今天我們要講的基于糾錯碼的公鑰密碼，還有基于格（音），這在復雜度理論里是非常重要的問題，而且也是研究最多的問題之一。還有一個是多變量密碼，明天有一個報告是講多變量密碼的。目前找到有這樣四類這樣的公鑰密碼，現在有一群人把它稱之為后量子密碼，或者稱之為量子免疫公鑰密碼。
那么什么是一個基于糾錯碼的公鑰密碼，實際上它的思維很簡單就是一個可以碼的公鑰密碼通過線性樣把它偽裝成一個隨機的線性碼，而隨機的線性碼是沒有有效的算法的。具體的方案就是McEliece提出的。這個G'代表了可解的碼。然后選兩個矩陣一個叫P、一個叫S，將它們偽裝，這個就是線性變化的乘法，一個從里面乘、一個從外面乘，乘出來的矩陣集就是作為公鑰的深層矩陣（音）。加密就是將M編碼成密文，按照公開的碼來編碼。因為加密的時候知道的只是公開的信息G。那么解碼的時候，解碼的人是知道P和S這兩個矩陣，他先將C去乘上P，就等于括號里面的。這個就是一個錯誤項。原來是的編碼是加上一個噪聲一，下來就把它去掉，就可以得到M、S，這就是解碼，按照G'來解碼。知道了M乘上S就可以恢復出M，這就是最原始的McEliece方案。
這里面還有一個校驗矩陣同樣可做。對基于糾錯碼的密碼，攻擊可以大致上分成兩類。第一類是結構化的攻擊，給定一個公開的碼，這是公鑰信息，把私鑰的碼恢復出來。我們今天講的就是這樣一種攻擊，就是要利用偽裝的結構。另外一種攻擊就是非結構化的攻擊，我們用信息論的解碼方法，來直接去攻破公開的碼。就是你的加密是一個加噪的編碼的方式，那我現在就直接對這個碼進行解碼。這個問題可以等價于另外一個碼里面找小重量的碼。我就不贅述了。恢復信源信息就等于另外一個碼里找一個小重量的。在實際的基于糾錯碼的公鑰密碼的構造中，這兩個問題經常會被用到。有的是用信源恢復的譯碼，有的是找小重量的譯碼。
基于糾錯碼的公鑰密碼進來被用到其他的密碼構造里，比如說one time signature，用到證明，把以前用RSA用離散對素（音）來構造的所有的密碼的方案，現在換成用編碼來構造。那么它的安全基礎就是譯碼的困難性。而且，現在有一些方案已經被處理，引入了一些可證明安全的方法和工具。就是把可證明安全這套理論也用在這些方案的設計和分析上。雖然McEliece用到這個困難問題，而且解一般的線性碼是一個NP困難問題，這個是可以嚴格證明的。但對一些具體的參數，這個問題究竟有多困難，有沒有一些具體的復雜度？這個工作在80年代以后一直有人在做。在編碼理論里討論的都是一些參數比較小的碼的具體的解碼方法和工程應用。在密碼里面，它處理的是很大的一些參數的譯碼。現在比如說為了達到一個安全目標，為了達到2的80次方、100次方，你應該選擇多大規模的參數，碼長是多少？這就需要對解碼找到最后的方法，然后按照最好的方法來度量困難程度。這里面有很多工作要做。比如說最近的一個工作就是在后量子密碼學年會上，有人給出了提升的方法，這個方法實際上比較早是在80年代末和90年代中期就已經出現了。他的方法實際上就是例如了哈奇碰撞（音）的思想。
在基于糾錯碼的密碼系統中，一般用的碼是Goppa碼這個碼是可以有效解碼的。而且對他們的要求是有40多年的歷史了，研究得比較充分。而且這一類碼是比較大的一類碼，包含著很多常見的碼。所以在基于碼的密碼系統的設計中，通常選擇Goppa碼作為秘密的私鑰的糾錯碼。
但是，有一個問題，這個問題是跟應用相關的。這樣的一些系統他的缺陷就是說他的密鑰規模比較大。通常里面用到的參數、碼長都是幾百，編碼理論的話，碼長可能是10幾、20，這里面的參數這么大。私鑰是要除乘兩個矩陣。但一個可逆矩陣是有方塊的，所以你可以想象密鑰的規模可能就是一個兆，非常大。進來有一些工作是為了約減密鑰的規模，用了一些Goppa碼。我們的方法是代數攻擊，這個代數攻擊實際上思想最原始的是香農（音）1949年的論文就有了。他說，你要設計一個密碼就要使得密碼的破解相當于解一個很復雜的方程，這個方程可能包括明文的信息，可能包括密文的信息。但這個方法實際上并沒有在密碼學中得到研究。直到90年代中期研究多變量密碼的時候才被重新發現。明天可能會講到多變量密碼里有兩個日本人提出的方案，那個體制就是用代數攻擊來攻破的。它其實很簡單，就是用到了關于明文分降和密文分降的方程組，你去設法解方程組就可以把信息解出來。代數攻擊是一種思想，就是首先建立關于明文Bit（音）或者是包含密鑰的bit的代數方程組，然后去解它。如果多數方程組是線性的，那就很容易解了。但這個中間如果變量構素特別多的話，那實際中能不能解還是有一個界定。但如果是非線性的話一般來說就很難解了。這是代數攻擊的思想，這個思想后來被用到了序列密碼，基于前饋電路（音），也就是說序列密碼設計是兩部分，一個是線性驅動部分，另外一部分是講線性變成非線性的。對這樣序列密碼代數攻擊也可以使用。對于分組密碼代數攻擊只是用到了一些很簡單的密碼上，比如說K-Lock這個是汽車鎖加密的分子密碼算法。那個算法的明文分組和密鑰都比較短，所以也可以用代數攻擊來分析它。
實際上代數攻擊最成功的領域是關于多變量密碼的分析。近來基于糾錯碼的公鑰密碼現在也能夠應用它。下面我破解這個碼是去年發表的，在加拿大和非洲密碼會發表的。這些設計的人應該都是糾錯碼的專家，也是密碼的專家。這個細節我這兒應該快一點過，它用到兩個域，一個是8比特或者是10比特的，還用到二次破域。然后它用的碼的話我剛才說了是一個特殊的碼，是廣義的read serm碼的子域、子碼。這里面出現一個數，它就是用這樣一些元素來表示的，這些元素在二次擴域里面。這些元素還進一步地將它更短的元素來表示，就是C0、C1-1。這中間涉及到一個秘密值一個元素beta。#p#
這是它的具體提出的七組建議參數。你就可以看到維數（音）是L×B，這個就差不多是500了。比如說第一行的51×9差不多是500。這個碼差不多是長500維。這里面的2T就是維數，這是200維的。設計者假設的安全參數是2的80次方等等。這個工作發表了以后，去年9月份有一個工作對其中的三組場所進行了分析可以破解。余下的還有四種參數是不能破解的。按照它的方法來估計負責度是2的74次方，這不是實際可破的，但是理論可破的，已經把假設復雜度降低了。
公鑰是將私鑰矩陣偽裝，乘上隨機選擇的矩陣。對分析者來說，知道的就是公鑰矩陣。后面還有一個工作，就是今年的歐密會，一組法國的專家他們用高次方程來破解這個方案。我們是用二次方程來破解這個系統，而且這個工作是去年我們在廣州密碼會期間做的，我們當時在一個學生的手提電腦上做，大致上要幾分鐘可以恢復出一個密鑰。后來我們在臺式電腦上做時間更短，可以在1分鐘之內實現。
這個分析出發點是要利用私鑰矩陣的特殊結構，這里面它的矩陣元素是在一個小域上，但最后用的話我們都是在大域上來做的。因為大域里的表達式是很簡單的，是一個單項式。具體是用的什么結構呢？我們用的是張量級（音）結構。這個張量級是說比如說兩個矩陣一個叫A、一個叫B，把A的每一個元素變成跟B很像的一個矩陣，所以這個矩陣的維數可以擴大。那么現在我們的分析是倒過來，我們發現它的矩陣的每一行雖然維數很大，但我們可以把它寫成兩個矩陣的張量級就可以把維數縮小，這是它的系統設計的弱點。具體的就是這樣的，第二行可以寫成這樣兩個項量。上面那行的項量只是與A、M相關，下面的項量跟秘密的值沒有關系了。只是與S有關，這是一個很小的數。我們后面還有一個方法，就是S可以很簡單地找出來。
攻擊就是從中間選出四行四個特殊的行，其中兩行是相連的，就是標號2d和2d+1。這個張量分解第二個是一樣的。下面這個和這兩個之間有一個距離，這個距離是2a2，這樣的四行第二個項量是一樣的。第一個項量可以把它看成一個四行矩陣，這個矩陣很特殊。我們就可以在上面建立方程系統。四次矩陣有這樣一個結構，但你知道的只是公鑰矩陣，我們要從私鑰矩陣轉到公鑰矩陣。實際上我們看，我們把這兩個矩陣分別乘上，γ'，γS很特殊，你跟H做乘法的時候，只需要考慮這四個行，不需要考慮別的行。這四行就可以有這樣一個等式，就是γ乘上P，這個特殊矩陣又可以寫成張量級。也就是說，這樣的γ是特殊的。這樣的項是特殊的。它使得和公鑰矩陣相乘以后有特殊的結構，我們就可以把γ找出來。而且我們還可以說，如果γ具有剛才所說的張量結構的話，γS相乘的話也只有四個量。你怎么去找這個γ？就是編碼云的問題了，我們有一個線性子空間就是EU。這種γ可以把它找出來。用編碼的語言說的話很簡單。我們就不說了。
如果找出來的話，這樣的γ可以嚴格地證明本質上只有四個，γ1、γ2、γ3、γ4。找出以后對每一個γi和p相乘就可以寫成右邊一個張量結構。就是UIB×C。這時候就可以把UI分解出來。所以我們就可以把UIB給分解出來。UIB分解出來可以寫成矩陣A。但這里面γ對應的UI是哪一個我們并不清楚。但我們知道，這個B是一個特殊形式的矩陣，A=MB，A是一個可逆的矩陣，這個不提供任何信息。但B的話提供信息。這個B是包含著所有的密碼信息在里面的。我們現在就把M乘到左邊去。剛才我們的中間有一個參數B，這個B是可變的，通過不同的B可以得到不同的方程。當然MB是不一樣的，但總是存在的。
現在我們從大域過渡到小域，利用元素的表達式，對右邊的矩陣第一行、第二行做一個變化，同時對左邊的M的逆做變化。對右面矩陣第三行、第四行，和左邊的矩陣的M逆做變化，我們就可以得到這么一個方程組。這個方程組右邊就是單項式的。這里面的Ai、Yi就是秘密的信息。這個D是你選定的。這些Z、W也是未知的。我們現在建立方程組是關于Z的變量或者是關于W變量的方程組。我們把它解出來，解出來以后就可以把Ai、Yi恢復出來，這就是秘密信息。那么怎么去建立這個方程組？這個很簡單，就是說單項式我們知道比如說Ai、Yi的一次方。如果d取1、取0這個式子顯然是成立的。這是一個二次方程。現在我們這些Ai、Yi的矩陣元素都可以用左邊的Z和W這些變量來線性表示，因為我們這個A已經算出來的。總是從公鑰矩陣可以算出來。現在Ai、Yi的方冪可以從線性表示，所以我們可以左邊的方程組。這個方程組是關于Z的變量的二次方程組。我們選不同的E就可以得到不同的方程。而且這里面還有一個變，所以我們可以得到很多的方程組。這是一個二次方程組，如果說個數比較少的話，我們還是可以解的。實際上是關于符號計算的研究的話，對特殊的方程組還可以有更好的方法。那么同樣也可以用W變量，這都是可用的。還可以討論其他的一些問題。我們后來在臺式電腦上做的，我們選的就是小d。然后我們的實驗結果是這樣的，比如說第一行，我們想d1取0、1、2，a2是他給定的。二次方程我們可以得到8個，得到三個線性方程，總共的變量只有12個。我們可以去解，這個就是用現有的符號計算形式。這就可以完全把它破解。
剛剛還有一個秘密值S的確定也可以用維數來計算。我們可以定義一個維數，這個維數叫ES'這是一個張量空間，這有多少這樣的γ、有多少這樣的維。如果S'是正確的話，這個值是2。如果錯誤的話是4。在剩余的兩種情況下算出是2就可以對應正確的S值來，所以這么判斷就可以了。
我總結一下，基于糾錯碼的密碼系統，由于量子計算威脅，現在實際上是一個后選的后量子密碼的方案。它的研究是很有意義的。但目前為了約減密鑰的規模，很多方案并不是安全的。可以有別的攻擊方法，但是也有代數攻擊的方法。對一個具體例子我們可以完全、實際地破解它。而且我們的代數攻擊復雜度否定了一些設計理念。比如說中間有一個參數B，那么參數B增加的話攻擊難度會加大。但我們這里的B增加方程更多了，我們攻擊的復雜度實際是降低的。這個領域還是有很多問題可以研究。
【編輯推薦】
