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