[[400577]]

AS(5)：RSA-PSS 算法簡(jiǎn)介

2018年發(fā)布的 TLS v1.3(TLS：Transport Layer Security，傳輸安全層協(xié)議，TLS v1.3 對(duì)應(yīng) RFC 8446)中，其支持的數(shù)字簽名算法有：RSASSA-PKCS1-v1_5、RSASSA-PSS、ECDSA(Elliptic Curve Digital Signature Algorithm，橢圓曲線簽名算法)、EdDSA(Edwards-Curve Digital Signature Algorithm，愛(ài)德華曲線簽名算法)。

這些算法已經(jīng)是標(biāo)準(zhǔn)(或者是事實(shí)上的標(biāo)準(zhǔn))，不過(guò)從某種意義上說(shuō)，這些算法也代表著美國(guó)簽名算法流派。

除美國(guó)外，俄羅斯在1994年發(fā)布數(shù)字簽名算法標(biāo)準(zhǔn) GOST R 34.10-94，并在2001年發(fā)布橢圓曲線數(shù)字簽名算法標(biāo)準(zhǔn)GOST R34.10- 2001。GOST R34.10-2001在2012年更新為 GOST R34.10-2012。韓國(guó)在1998年發(fā)表韓國(guó)基于證書(shū)的數(shù)字簽名算法 KCDSA 和 EC- KCDA，對(duì)應(yīng)標(biāo)準(zhǔn)發(fā)布于[88,89]。德國(guó)在 2005 年發(fā)布德國(guó)橢圓曲線數(shù)字簽名算法標(biāo)準(zhǔn) EC- GDSA。中國(guó)在 2012 年發(fā)布 SM2 橢圓曲線數(shù)字簽名算法標(biāo)準(zhǔn)，在 2016 年發(fā)布 SM9 標(biāo)識(shí)密碼數(shù)字簽名算法標(biāo)準(zhǔn)。

作為重要的國(guó)際標(biāo)準(zhǔn)化組織，ISO/IEC 同樣也發(fā)布了一系列的數(shù)字簽名算法標(biāo)準(zhǔn)：ISO/IEC 9796、ISO/ IEC 14888、ISO/IEC 20008、ISO/IEC 18370、ISO/IEC 23264 等等。

弱水三千，只取一瓢。由于文章主題和篇幅的關(guān)系，本文只介紹 RSASA-PSS 算法。

PSS (Probabilistic Signature Scheme，概率簽名方案)是私鑰簽名的一種填充方式。RSASA(RSA Signature Algorithm，RSA 數(shù)字簽名算法)目前支持兩種算法：RSASSA-PKCS1-v1_5、RSASSA-PSS。由于安全的原因，RSASSA-PKCS1-v1_5 現(xiàn)在的使用場(chǎng)景僅僅是為了兼容(可以參考《童話里都是騙人的》、《夢(mèng)被批得離離散散》、《蜀道難，難于上青天》)，當(dāng)前主流推薦使用 RSASSA-PSS 算法。

PSS 方案首先由 Bellare和Rogaway 首先提出，PSS 與 OAEP(Optimal Asymmetric Encryption Padding，最優(yōu)非對(duì)稱加密填充)非常相像，當(dāng)然 OAEP也是由這兩位大神提出的(OAEP 請(qǐng)參見(jiàn)《蜀道難，難于上青天》)。

Mihir Bellare是加州大學(xué)圣地亞哥分校(UCSD，University of California, San Diego)計(jì)算機(jī)科學(xué)與工程系的教授。Bellare 于1986年在加州理工學(xué)院獲得學(xué)士學(xué)位，1991年在麻省理工學(xué)院獲得博士學(xué)位。1991年至1995年，Bellare 在IBM擔(dān)任研究員 Bellare 是HMAC、RSA-OAEP、RSA-PSS和OCB的聯(lián)合開(kāi)發(fā)者。Bellare 是 ACM 和 IACR 的研究員。他曾獲得 ACM 巴黎Kanellakis 理論與實(shí)踐獎(jiǎng)，RSA 會(huì)議數(shù)學(xué)獎(jiǎng)，David 和 Lucille Packard基金會(huì)科學(xué)與工程獎(jiǎng)學(xué)金，以及NSF職業(yè)獎(jiǎng)( He has received an ACM Paris Kanellakis Theory and Practice Award, an RSA Conference Award in Mathematics, a David and Lucille Packard Foundation Fellowship in Science and Engineering, and an NSF Career award)。

Phillip Rogaway 是美國(guó)加州大學(xué)戴維斯分校(UCD，University of California, Davis)計(jì)算機(jī)科學(xué)系的教授。Rogaway 本科畢業(yè)于加州大學(xué)伯克利分校(UCB，University of California, Berkeley)，并于1991年到麻省理工計(jì)算理論小組攻讀博士學(xué)位(MIT s Theory of Computation group )。博士畢業(yè)之后，Rogaway 到 IBM 擔(dān)任安全架構(gòu)師，然后于1994年到 UCD 工作。Rogaway 獲得過(guò) Levchin 獎(jiǎng)(2016)，PET 獎(jiǎng)(2015)，IACR 研究員(2012)，ACM巴黎 Kanellakis 獎(jiǎng)(2009)，RSA 數(shù)學(xué)獎(jiǎng)(2003)(Levchin prize (2016), PET Award (2015), IACR Fellow (2012), ACM Paris Kanellakis Award (2009), RSA Award in Mathematics (2003))。

[[400578]]

圖1 Bellare(左)和 Rogaway(右)

RSA 數(shù)字簽名算法(RSASA)的本質(zhì)，仍然是 RSA 加密/解密算法，如圖2所示。

圖2 RSA 數(shù)字簽名算法示意

從圖2可以看到，RSSSA 分為兩步。

1)將待簽名的 M 進(jìn)行 Hash，從而得到 H

2)將 H 進(jìn)行 RSA 私鑰加密

既然是 RSA 加密，就繞不開(kāi) RSA 那個(gè)致命問(wèn)題——能夠非常簡(jiǎn)單地被選擇密文攻擊所破解(具體請(qǐng)參見(jiàn)《童話里都是騙人的》)，于是也就引發(fā)了 RSA 填充算法。

RSASSA-PKCS1-v1_5 采用的就是 RSA_PKCS1_PADDING_v1_5 填充算法，而 RSASSA-PSS 的填充算法則與 RSA_PKCS1_OAEP_PADDING 填充算法比較相像。下面我們就介紹 RSASSA-PSS 算法。

一、RSASSA-PSS 的填充算法

RSASSA-PSS 算法本質(zhì)就是在 RSA 算法的基礎(chǔ)上疊加上一種填充算法(為了便于表述，這種填充算法也可以稱為 RSA-PSS 填充算法，或者 RSA-PSS 編碼)，如圖3所示。

圖3 RSA-PSS 數(shù)字簽名算法示意

圖3中，在 Hash 之后，在 RSA 之前，RSASA-PSS 算法插入了一個(gè) RSA-PSS 填充算法。RSA-PSS 的具體算法，如圖4所示。

圖4 RSA-PSS 填充算法示意

圖4中，RSA-PSS 填充算法，分為四步。下面我們分別講述這四步。

1.1 M 轉(zhuǎn)換成 M1

通過(guò)圖4可以看到，

M1 = p1 || mHash || salt

p1 就是8字節(jié)的0。

mHash = Hash(M)，M 是待簽名的消息，Hash 算法當(dāng)前的選擇是 SHA-1。SHA-1 的輸出是20個(gè)字節(jié)，所以 mHash 的長(zhǎng)度

hLen = 20

salt(鹽值)就是一個(gè)偽隨機(jī)數(shù)，它的長(zhǎng)度(記為 sLen)一般等于 hLen，當(dāng)前的選擇就是

sLen = hLen

1.2 構(gòu)建 DB

DB(Data Block)的構(gòu)建方式為，

DB = p2 || salt

p2 的值等于若干個(gè)字節(jié)的 0x00 后面跟著1字節(jié)的 0x01。這若干個(gè)字節(jié)記為 xLen，則 xLen 等于，

xLen = emLen - sLen - hLen - 2

其中，emLen 是圖4中 EM 的長(zhǎng)度

salt 的值等于1.1節(jié)所描述的 salt 的值。特別強(qiáng)調(diào)，兩者必須相等，否則無(wú)法驗(yàn)證數(shù)字簽名(具體請(qǐng)參見(jiàn)下面第三節(jié)：RSASSA-PSS 的數(shù)字簽名驗(yàn)證)

1.3 MGF

MGF(Mask Generation Function，掩碼生成函數(shù))的相關(guān)介紹，請(qǐng)參見(jiàn)《蜀道難，難于上青天》，這里就不再重復(fù)。另外，RSA-PSS 所采用的 MGF 函數(shù)的輸出，也是 MGF1。

對(duì)于圖4而言，MGF 所對(duì)應(yīng)的輸入和輸出分別是

mask = MGF1(mgfSeed, maskLen, hash)

其中，

mgfSeed = Hash(M1)，Hash 函數(shù)選擇 SHA-1

maskLen = emLen - hLen - 1

hash 函數(shù)選擇 SHA-1

1.4 構(gòu)建 EM

EM(Encoded Message)的值等于，

EM = maskedDB || H || bc

其中，

maskedDB = DB xor mask

H = Hash(M1)

bc = 0xBC

其中，bc 的長(zhǎng)度是1個(gè)字節(jié)，H 的長(zhǎng)度是 hLen，maskedDB 的長(zhǎng)度(記為 mdbLen)為

mdbLen = emLen - hLen - 1

其中，emLen 的長(zhǎng)度就是 EM 的長(zhǎng)度。由于接下來(lái)要對(duì) EM 進(jìn)行 RSA 加密計(jì)算，所以 EM 的長(zhǎng)度滿足 RSA 的要求即可。

二、RSASA-PSS 的簽名算法

經(jīng)過(guò) RSA-PSS 填充以后，接下來(lái)的簽名算法，就比較簡(jiǎn)單了，

EM = RSA-PSS(M)

S = RSAEP(EM)

RSA 算法，請(qǐng)參見(jiàn)《RSA 基本算法》、《RSA 的計(jì)算方法》，這里不再重復(fù)。

三、RSASA-PSS 的簽名驗(yàn)證

RSASA-PSS 簽名驗(yàn)證，分為如下幾個(gè)步驟。

3.1 解密

RSASA-PSS 的簽名驗(yàn)證，首先是解密，

EM = RSADP(S)

也即，拿到簽名 S 以后，運(yùn)行 RSA 解密算法，得到解密后的信息 EM。

3.2 分割 EM

得到 EM 以后，接下來(lái)就是分割和驗(yàn)證，

maskedDB, H, bc = Split(EM)

最右一個(gè)字節(jié)是 bc，然后從 bc 往左數(shù) hLen 個(gè)字節(jié)是 H，然后剩下的是 maskedDB。

如果最右一個(gè)字節(jié)不是 0xBC，則簽名驗(yàn)證停止(該數(shù)字簽名是非法的)。

3.3 計(jì)算 salt

得到 H 以后，就可以計(jì)算 mask，

mask = MGF1(H, maskLen, hash)

因?yàn)椋?/p>

maskedDB = DB xor mask

所以，

DB = maskedDB xor mask

得到 DB 以后，就可以對(duì)其分割

p2, salt = Split(DB)

其中，salt 是 DB 的最右 sLen 個(gè)字節(jié)，剩下的是 p2。

如果 p2 的值不等于若干個(gè)字節(jié)的 0x00 后面跟著1字節(jié)的 0x01，那么驗(yàn)證停止(該數(shù)字簽名是非法的)。

3.4 校驗(yàn) Hash

通過(guò)所接收到的 M，計(jì)算 Hash

mHash = Hash(M)

然后構(gòu)建 M1

M1 = p1 || mHash || salt

其中，salt 就是 3.3 步所計(jì)算出的 salt

再然后，計(jì)算 M1 的 Hash

H1 = Hash(M1)

比較 H1 與 H，如果兩者相等，則簽名驗(yàn)證通過(guò)。如果不相等，則簽名非法。

其中，H 就是3.2步所得到的哈希值。

經(jīng)過(guò)以上四步以后，就完成了 RSASA-PSS 的數(shù)字簽名驗(yàn)證。