摘 要：文獻(xiàn)[1]給出了一個(gè)新的密碼建構(gòu)ESC，但其未給出ESC的RO區(qū)分有利條件上界的詳細(xì)證明，本文給出了當(dāng)對(duì)ESC的一系列詢問(wèn)沒(méi)有導(dǎo)致內(nèi)部碰撞時(shí)其輸出位是均勻和獨(dú)立的，并由此進(jìn)而再得到：當(dāng)f是一個(gè)隨機(jī)變換函數(shù)時(shí)，ESC的RO區(qū)分有利條件的上界是：；當(dāng)f是一個(gè)隨機(jī)置換函數(shù)時(shí)，ESC的RO區(qū)分有利條件上界是：。

關(guān)鍵詞：密碼建構(gòu)；隨機(jī)預(yù)言機(jī)；RO區(qū)分有利條件；隨機(jī)變換函數(shù)；隨機(jī)置換函數(shù)

DOI：10.16640/j.cnki.37-1222/t.2016.08.200

1 ESC的RO區(qū)分有利條件

1.1 基本概念

定義1：一個(gè)超級(jí)節(jié)點(diǎn)指內(nèi)部狀態(tài)相同的節(jié)點(diǎn)集。

定義2：ESC吸收字符串P后的前狀態(tài)是指那個(gè)對(duì)字符串P的最后一塊消息只進(jìn)行了一次異或后得到的整體狀態(tài)，我們將用來(lái)表示。

定義3：ESC吸收字符串P后的后首狀態(tài)是指的是那個(gè)用變換（或置換）處理相應(yīng)前狀態(tài)后得到的整體狀態(tài)，我們將用表示。

定義4：ESC吸收字符串P后的后尾狀態(tài)指的是那個(gè)對(duì)相應(yīng)后首狀態(tài)進(jìn)行了消息反饋異或后得到的整體狀態(tài)，我們將用來(lái)表示。

我們將用，，和來(lái)分別表示ESC吸收字符串P后后首狀態(tài)的內(nèi)部狀態(tài)，外部狀態(tài)和整體狀態(tài)；將用，，和來(lái)分別表示ESC吸收字符串P后后尾狀態(tài)的內(nèi)部狀態(tài)，外部狀態(tài)和整體狀態(tài)，我們知道ESC吸收同一個(gè)字符串P后后首狀態(tài)和相應(yīng)的后尾狀態(tài)的內(nèi)部狀態(tài)相同，而且擠壓階段可視為吸收零塊消息，因此后首狀態(tài)和相應(yīng)的后尾狀態(tài)相同（調(diào)用變換（或置換）函數(shù)后）；將用、和來(lái)分別表示吸收過(guò)程中相鄰的且內(nèi)部狀態(tài)相同的后首狀態(tài)、后尾狀態(tài)和前狀態(tài)，由此可知ESC吸收字符串過(guò)程中的整體狀態(tài)由這三種整體狀態(tài)組成。

定義5：ESC的一對(duì)內(nèi)部碰撞指的是一對(duì)不同的字符串P和P，它們被吸收后后尾狀態(tài)的內(nèi)部狀態(tài)相等，即。

定義6：一個(gè)隨機(jī)預(yù)言機(jī)RO是指接受任意長(zhǎng)度的二進(jìn)制字符串作為輸入然后對(duì)每個(gè)輸入返回一個(gè)無(wú)限長(zhǎng)度的二進(jìn)制字符串，即它是一個(gè)從到的映射，通過(guò)對(duì)每個(gè)輸入M，均勻和獨(dú)立地選取返回值RO（M）中的每個(gè)比特值來(lái)產(chǎn)生。

我們將用來(lái)表示一次調(diào)用RO后被截成比特的輸出。ESC對(duì)一個(gè)輸入消息M的輸出的第j塊為，其中。上面的基礎(chǔ)性質(zhì)暗示著填充規(guī)則必須是海綿遵從[2]的。

1.2 ESC輸出的均勻性和獨(dú)立性

定理 1. 若f表示一個(gè)隨機(jī)變換（或置換）函數(shù)和pad表示一個(gè)海綿遵從的填充規(guī)則，當(dāng)沒(méi)有發(fā)生內(nèi)部碰撞時(shí)由對(duì)一系列詢問(wèn)返回的輸出比特是均勻和獨(dú)立分布的。

證明. 我們用Q來(lái)表示向系統(tǒng)的一系列詢問(wèn)，用來(lái)表示系統(tǒng)對(duì)Q的一系列回復(fù)。在這情況下，Q是一系列對(duì)，并且是一個(gè)正整數(shù)，（Q）是一系列對(duì) 。對(duì)于給定的一系列詢問(wèn)Q，隨機(jī)ESC當(dāng)吸收輸入串和被擠壓時(shí)經(jīng)歷過(guò)一些整體狀態(tài) 。 我們用表示到實(shí)驗(yàn)過(guò)程中的路徑集，即有={X是的一個(gè)前綴且X的長(zhǎng)度是r的整數(shù)倍}，其中。詢問(wèn)過(guò)程不發(fā)生內(nèi)部碰撞意味著 ?？紤]第i次詢問(wèn)的第j塊輸出塊，我們將用來(lái)表示從第一次詢問(wèn)到第i-1次詢問(wèn)和當(dāng)次詢問(wèn)先前經(jīng)歷過(guò)（除掉和）的整體狀態(tài)集，將用，， 和來(lái)分別表示關(guān)于的前狀態(tài)集合，后首狀態(tài)集合，后尾狀態(tài)集合和內(nèi)部狀態(tài)集合，要求在輸出塊的產(chǎn)生過(guò)程中不發(fā)生內(nèi)部碰撞意味著限制內(nèi)部狀態(tài)的值與內(nèi)部狀態(tài)集合里的值都不相同。當(dāng)f是一個(gè)隨機(jī)變換函數(shù)時(shí)，輸出塊的值必須在狀態(tài)集合里，這些值是等概率的。當(dāng)f是一個(gè)隨機(jī)置換函數(shù)時(shí)，由f的可逆性要求必須與所有先前經(jīng)歷過(guò)的后首狀態(tài)不同 （除了），即要求是從整體狀態(tài)集中來(lái)選擇。又因?yàn)?，所以可以?jiǎn)化為。因此在兩種情況下對(duì)輸出塊在中所有可能的值都是等概率的而且獨(dú)立于先前經(jīng)歷過(guò)的外部狀態(tài)（消息塊的反饋異或并不影響輸出塊的均勻和獨(dú)立分布），所以輸出比特也是均勻和獨(dú)立分布的。

1.3 攻擊者的情況

我們考慮一個(gè)將區(qū)分兩個(gè)系統(tǒng)的攻擊者，如圖1所示，左邊的系統(tǒng)是隨機(jī)變換（或置換）函數(shù)f與ESC E的組合，攻擊者不能直接詢問(wèn)f但可以詢問(wèn)E，E將會(huì)調(diào)用f來(lái)構(gòu)造它的回復(fù)，這表示為E[f]，我們用H來(lái)表示E[f]的交互交互界面，交互界面H取一個(gè)二進(jìn)制字符串串和一個(gè)整數(shù)作為輸入，返回一個(gè)二進(jìn)制串， 就是ESC被截成比特的輸出。右邊的系統(tǒng)由一個(gè)隨機(jī)預(yù)言機(jī)組成，隨機(jī)預(yù)言機(jī)提供與E[f]相同的交互界面H。當(dāng)接受輸入后，它返回被截成比特的輸出 。攻擊者交互界面背后的系統(tǒng)不是E[f]就是RO，系統(tǒng)是E[f]還是RO的優(yōu)先概率均為1/2，攻擊者會(huì)向的交互界面H發(fā)送詢問(wèn)，甚至是適應(yīng)性的，通過(guò)連續(xù)的詢問(wèn)的輸出的前比特，在發(fā)送完所有詢問(wèn)后，攻擊者使用系統(tǒng)對(duì)詢問(wèn)的回復(fù)來(lái)猜測(cè)是E[f]還是RO。我們假設(shè)攻擊者的計(jì)算能力無(wú)界限，她可以最大限度的挖掘呈現(xiàn)在詢問(wèn)回復(fù)中的信息。然后我們來(lái)限定作為總詢問(wèn)成本[2]的函數(shù)的ESC RO區(qū)分有利條件的上界。

1.4 ESC的RO區(qū)分有利條件

又由于ESC與文獻(xiàn)[2]中海綿建構(gòu)不同的是在每次調(diào)用完變換（或置換）函數(shù)后對(duì)外部狀態(tài)進(jìn)行的消息反饋異或，相應(yīng)后尾狀態(tài)和后首狀態(tài)的內(nèi)部狀態(tài)相同，屬于同一個(gè)超級(jí)節(jié)點(diǎn)，因此通過(guò)最優(yōu)策略時(shí)ESC產(chǎn)生內(nèi)部碰撞的概率與海綿建構(gòu)的相同，所以再根據(jù)文獻(xiàn)[2]中產(chǎn)生內(nèi)部碰撞的概率就可推導(dǎo)出以下兩個(gè)定理。

參考文獻(xiàn)：

[1]陳偉彬.一個(gè)阻止內(nèi)部碰撞轉(zhuǎn)狀態(tài)碰撞的海綿建構(gòu)變體[J].科技傳播，2014（06）：149-150.

[2]G.Bertoni，J.Daemen，M.Peeters，and G.Van Assche，Cryptographic sponge functions[OL]，（2012/02/15）[2013/11/30]http：//sponge.noekeon.org/.

[3]Gauravaram，P.，Kelsey，J.，Knudsen，L.R.， Thomsen，S.S.：On hash functions using checksums[J].Int.J.Inf.Secur.vol.9（2），pp.137-151（2010）.

[4]U.Maurer.Indistinguishability of random systems. In Advances in Cryptology—EUROCRYPT 02， volume 2332 of Lecture Notes in Computer Science， pages 110-132. Springer-Verlag，2002.

作者簡(jiǎn)介：陳偉彬（1987—），男，廣東汕頭人，碩士研究生，助教，研究方向：密碼學(xué)和數(shù)論等。