動機
加密的目的是隱藏訊息。數碼簽名通常讓訊息保持公開,而是讓任何人都能驗證該訊息確實經密鑰持有者授權。把 RSA 的指數運算等式反過來使用,就得到一個候選的簽名規則,但安全目標必須改變:敵手可以要求對自己選定的訊息的簽名,然後嘗試授權一則新的訊息。
原始 RSA 因一個初等的代數攻擊而達不到這一目標。先對訊息做雜湊再簽名是一種可能的修補,但「雜湊」一詞本身並不是安全假設。我們分析一個理想的隨機函數,其取值遍及 RSA 置換的整個定義域。在該模型中,歸約可以把一個 RSA 求逆挑戰放在某個未知的預言機查詢處,並利用已知的根來回答其餘查詢。
證明包括選中該查詢的概率、重複查詢的一致性,以及有界的公平位元取樣。它給出的是理想模型中的條件性定理,並不認證某個固定的真實雜湊函數、某種標準化的簽名編碼或某個已部署的實現。
定義
假設給定一個可高效生成的 RSA 密鑰族,其安全參數為 ,並以 的形式公開提供。模數為 ,其中 是不同的奇質數,其位元長度是 的多項式,且 。指數 與 互質,秘密指數滿足 。記 。先前的 RSA 算術已證明 是 上的置換,其逆為 。
這裏使用的 RSA 單向性假設是:任何有界的概率多項式時間算法,在給定公鑰以及在 中均勻取值的 時,僅以可忽略的概率找到滿足 的單位 ,該概率同時對所生成的密鑰取平均。「可忽略」沿用先前以反多項式漸近方式給出的定義。密鑰族和該假設都是給定的前提;我們並不斷言 RSA 求逆與因數分解等價。
在選擇訊息偽造實驗中,敵手獲得公鑰,可以要求對多項式個訊息的簽名,最後輸出 。當驗證通過且 從未被要求簽名時,敵手獲勝。這就是選擇訊息攻擊下的存在性不可偽造性。重複一個已被簽名訊息的簽名在該實驗中不算獲勝。
對於原始 RSA,訊息屬於 ,簽名返回 。對於全域雜湊,訊息是多項式長度的位元串,一個理想的隨機預言機 把它們映射到 :
隨機預言機對每個新的字串給出獨立均勻的單位作為回答,並在之後的調用中重複其已儲存的回答。它是一個數學上的預言機模型,而不是普通的固定雜湊算法。敵手可以同時存取這個預言機和簽名預言機。
定理/命題
定理 4.3.1
(正確性並不能阻止原始 RSA 的偽造)
上述兩種簽名規則都能通過對其誠實生成的簽名的驗證。然而原始 RSA 允許在不做任何簽名查詢的情況下成功偽造:任選一個單位 ,構造 ,輸出 。它還允許把兩個簽名相乘,得到這兩則訊息之積的簽名。
定理 4.3.2
(全域雜湊的條件性安全)
固定可計算的多項式上界 ,分別界定敵手的雜湊查詢數和簽名查詢數。設它在理想實驗中以概率 偽造成功。令 ,並令 為不小於 的最小的 2 的冪。則存在一個有界的多項式時間 RSA 求逆算法,其成功概率至少為
因此,RSA 單向性假設蘊含該隨機預言機模型中的偽造概率可忽略。最後多出的一次查詢,使得對一則此前從未被雜湊過的偽造訊息也能進行驗證。
證明思路或證明
證明
(指數求逆,以及先選定根)
對每個單位 ,指數求逆給出 。取 或 ,即證明了正確性。但原始驗證等式也可以這樣滿足:先選定簽名,再計算其對應的訊息。存在性偽造讓敵手自行選擇偽造哪一則新訊息,因此它無需對預先給定的目標求逆。
同樣地,若 且 ,則 。當該乘積是一則新訊息時,這一對數據就是一次選擇訊息偽造。全域雜湊把所需的等式改為一個全新而獨立的預言機取值;兩個早先雜湊值之積,未必是任何所選新訊息的雜湊值。
全域雜湊的安全性證明分為三部分:以選定的根模擬雜湊預言機;把挑戰隱藏在被猜測的表項中;以及一個有界取樣器,其代價由耦合來計算。
證明
(模擬預言機、植入挑戰、限制取樣)
透過選擇根來模擬雜湊回答。 對於任何普通的新雜湊查詢,在 中均勻選取 ,返回 作為雜湊值,並儲存這兩個數。由於指數運算是置換,返回值在 中均勻分佈。不同的新選擇給出相互獨立的雜湊回答;與隨機函數完全一樣,容許出現碰撞。對該訊息的簽名查詢,可以用已儲存的 來回答,它正是簽名規則所要求的唯一的根。
如果某則訊息首先是透過簽名請求而出現的,則在返回根之前,以同樣方式為它建立雜湊表條目。重複的雜湊或簽名請求重用該條目。新條目的總數(包括對偽造訊息的最終驗證)至多為 。如果只計入敵手明確的雜湊調用,就會漏掉由簽名和驗證所產生的條目。
把求逆挑戰隱藏在一個隨機條目中。 給定一個 RSA 挑戰 ,歸約恰好使用 個公平位元,在 中均勻選取 。在第 個新表項處,它返回 ,而不是自己生成的 。其根是未知的。若該訊息被要求簽名,歸約報告失敗。所有其他條目與簽名按上述方式模擬。如果敵手最終對該特殊訊息偽造成功,那麼通過驗證的簽名就是 的一個 次根,從而解決了求逆挑戰。
要看出為甚麼即使查詢是自適應的,成功概率仍然含有 ,先分析一個假想的完美實驗,它知道秘密密鑰,甚至能回答特殊訊息的簽名查詢。挑戰 是均勻的,因此無論選中哪個位置,每個雜湊條目都具有正確的獨立均勻分佈。簽名是其條目的唯一的根。所以這個完美實驗中敵手的完整轉錄與 無關。
在任何一個成功偽造的轉錄中, 的第一個表項有某個下標 。由於 獨立且均勻,它等於該下標的概率為 。在此事件上,根據獲勝實驗中的新鮮性要求,該特殊訊息從未被簽名。因此,實際的歸約從不會遇到其特殊的中止情形,並且一直到偽造發生都沿著完全相同的轉錄進行。在理想的單位取樣下,其成功概率至少為 。完美實驗只是分析的工具;實際實現的歸約從不使用秘密指數。
使每一次模擬取樣的運行都有界。 要從 中精確均勻取樣,一般無法在沒有失敗分支的情況下使用固定數目的公平位元。令 。抽取一個均勻的 位元整數,若它小於 且與 互質則接受。每個被接受的整數都是均勻的單位。由於
每次嘗試成功的概率至少為 。互質性由多項式時間的歐幾里得(Euclid)算法檢驗,不需要對 做因數分解。
把每次求根取樣調用限制在 次獨立嘗試以內,若達到上限則報告求逆失敗。其失敗概率至多為 。這樣的調用至多有 次,所以某個上限改變了被模擬的實驗的概率至多為 。
為精確起見,把每次帶上限的調用與使用相同嘗試位元的理想的無上限取樣器耦合。在第一次觸及上限失敗之前,兩者的輸出一致。在以所有過去的轉錄為條件時,下一批新的嘗試具有同樣的成功界,所以並集界可以控制首次失敗的概率。從理想求逆的成功概率中減去耦合失敗的概率,即證明了該定理,並且所有取樣、建表和指數運算的工作量都有多項式最壞情況上界。
由於 且 有多項式上界,若在無窮多個長度上偽造概率不可忽略,則在減去可忽略的取樣項之後,這些長度上的求逆概率也不可忽略。這正是 RSA 單向性所要求排除的矛盾。
猜測的下標和耦合,是這個論證最容易悄悄出錯的兩處,值得單獨拆開來看。
證明透視
猜測、新鮮性規則與耦合在哪裏起作用
是置換這一性質用了一次:它使 均勻分佈,所以模擬的雜湊表恰好具有隨機預言機的分佈;它也使已儲存的 成為唯一有效的簽名。挑戰 同樣是均勻的,因此完美轉錄與 無關。只有先確立了這種獨立性,才能說 的概率為 ;先條件化、再斷言選擇無偏,就是循環論證。
新鮮性正是消除歸約唯一無法完成的那次模擬的假設。成功的偽造所用的訊息從未被簽名,所以在事件 上,特殊條目從不被要求簽名,歸約的中止分支永遠不會出現。若沒有新鮮性,重播的簽名就能獲勝,而被植入的條目也可能必須被簽名。
耦合取代了一個誘人但無效的步驟,即以每個帶上限取樣器都成功為條件:在自適應運行中,後來的調用依賴於先前的輸出,這種條件化可能重新加權各種歷史。在相同嘗試位元上比較帶上限與無上限的取樣器,只需並集界 。最後, 使損失因子保持多項式,這才把不等式變成與單向性的矛盾。
例題詳解
例題 4.3.3
(玩具群中先給簽名的偽造)
取 ,,則 ,秘密的逆指數為 ,因為 。選取單位 。其立方為 ,所以 不需任何簽名查詢就能通過原始 RSA 的驗證。攻擊者並沒有對指定的 RSA 挑戰 求逆;它先選定了一個根,從而選擇了訊息。這個小模數只是正確性的示例,可以立即被分解。
例題 4.3.4
(把兩個被要求的簽名相乘)
在同一個玩具密鑰下,訊息 和 的簽名分別為 和 ,因為 、。相乘得到簽名 ,對應新訊息 ,因為 。因此,要求兩個簽名就在沒有秘密指數的情況下授權了第三則訊息。
在全域雜湊中,把簽名相乘得到的是 的一個根。對於一個新鮮選定的字串 ,其獨立雜湊恰好等於這個特定單位的概率為 ,而不是由某個代數恆等式保證。這一觀察解釋了舊攻擊為何不再自動奏效;而完整的條件性定理是由歸約證明的,並非僅靠這一觀察。
例題 4.3.5
(一個挑戰槽位與一次較晚的雜湊查詢)
設想歸約選中了 。前兩個新字串得到模擬值 和 ,在玩具密鑰下儲存的根分別為 和 ,它們都能被一致地簽名。第三個不同的字串得到求逆挑戰 。對這個新字串的一個有效簽名 ,就會對該挑戰求逆。
如果敵手從未明確查詢該字串,則第三個條目可能直到最後驗證時才被建立。它仍然屬於被猜測的表項順序,這正是計數中要多算一次的原因。反過來,如果敵手要求歸約對這個特殊字串簽名,模擬就會中止;這樣的轉錄不可能是概率下界中所用的、與之匹配的新鮮訊息成功事件。
常見錯誤
常見錯誤
(隨機預言機證明並不是關於每個固定雜湊的定理)
模擬依賴於選擇獨立的雜湊輸出,並在其中一個輸出處植入挑戰。一個固定的、已公開的雜湊算法並不給歸約這種編程能力。該定理只在其明確的理想模型中、並在 RSA 單向性之下確立安全性。具體的編碼、標準與實現保證需要另行分析。
常見錯誤
(單向性關乎一個預先給定的隨機目標)
安全假設所涉及的是對一個隨機的、預先給定的群元素求逆,而不是不可能產生任何有效的簽名等式。原始方案先給簽名的攻擊不必求任何逆就產生有效的一對 ,因此並不與單向性矛盾。重複查詢、雜湊碰撞和新鮮訊息的驗證都屬於實驗本身;把它們從模型中刪去,會簡化掉證明中真正的義務。
常見錯誤
(只計算明確的雜湊查詢)
取 會忘記由簽名請求以及對 的最終驗證所建立的表項。若被偽造的訊息從未被明確雜湊,它的條目是最後建立的一個,下標可達 ;只按 選定的猜測範圍可能在該下標之前就結束,那麼猜測永遠不會命中。
總結
僅有正確的 RSA 指數運算,並不能給出不可偽造的簽名。全域雜湊為每個字串提供一個理想的獨立目標。被猜測的新表項嵌入求逆挑戰,而所選的根回答其餘的每個查詢。有界取樣和明確的耦合完成了這個條件性的隨機預言機證明,既沒有隱藏非二進制的隨機選擇,也沒有隱藏期望時間的假設。
練習
快速檢查
(為甚麼返回一則舊訊息及其已經得到的簽名,不能贏得所述實驗?)
重讀偽造實驗的獲勝條件。
解答
實驗要求被偽造的訊息從未被簽名。否則敵手總能透過重播一則已授權的訊息而獲勝,而這並不是該定義所要衡量的授權失敗。更強的安全概念可以進一步考慮舊訊息上的另一些簽名。
快速檢查
(為甚麼歸約要同時儲存模擬的雜湊值和它所選的根?)
考慮之後對同一字串的雜湊調用和簽名調用。
解答 · 答案
該值必須在之後的雜湊調用中被一致地重複。已儲存的根使歸約能夠在不知道秘密密鑰的情況下,對之後的簽名調用給出該值所要求的那個唯一的簽名。
快速檢查
(為甚麼猜測取自包含 的 2 的冪區間,而不是聲稱能從任意的 中以有界位元精確均勻取樣?)
數一數在 個位置中均勻選擇所需的公平位元。
解答
2 的冪區間恰好使用固定數目的公平位元。未被使用的位置只是把成功概率的下界降為 ,而 ,因此仍保持反多項式的成功概率。對下標而言,不需要未說明的變時間取樣器或有偏的取餘規則。
快速檢查
(如果簡單地以所有自適應的帶上限取樣器都成功為條件,並宣稱所得轉錄是理想的,會有甚麼問題?)
之後的查詢可能依賴於先前的輸出。
解答
在自適應過程中,之後的取樣行為可能依賴於先前的輸出,所以對全局成功的條件化可能會重新加權各種歷史。改為在相同的新嘗試位元上耦合帶上限與無上限的執行,就能界定二者出現分歧的概率,而無需這樣的分佈性斷言。
快速檢查
(在玩具密鑰 、、 下,計算訊息 的原始 RSA 簽名並加以驗證。)
用反覆平方計算 ,或直接尋找立方根。
解答
模 :,所以 ,因為 。於是 。驗證:,而 ,因為 。所以簽名為 ,並且如驗證所要求,。