區塊鏈中的數學（四十二）---基于RSA的VRF（隨機可驗證函式）-有解無憂

文章來源區塊鏈技術公眾號“blocksight”，原文歡迎關注！

寫在前面

上一節說了VRF（隨機可驗證函式）概述，由于VRF是與公鑰密碼學相結合的，自然少不了最常見的公鑰密碼學體制RSA和橢圓曲線EC，

本文開始講基于RSA的VRF實作，關于RSA演算法的知識如果不熟悉，可先參考文末“相關閱讀”部分，

RSA-FDH-VRF

基于RSA實作的VRF記為RSA-FDH-VRF，滿足可信唯一性，可信抗碰撞性和全偽隨機性（trusted uniqueness", "trusted collision resistance", "full pseudorandomness"），關于些安全性要求，上一節均有所介紹，

VRF使用RSA簽名，在輸入alpha上計算證明P，RSA簽名驗證用于驗證證明的正確性，VRF哈希輸出R，只需使用所選哈希演算法對證明P進行散列即可得到，

符號約定

(n, e) - RSA 公鑰
K - RSA 私鑰
k - RSA 模 n位元組長度 (k < 2^32)
I2OSP - 非負整數轉成字串
OS2IP - 字串轉化為非負整數
RSASP1 - RSA 簽名演算法
RSAVP1 - RSA 驗證簽名演算法
MGF1 - 掩碼生成函式

這里著重說一下掩碼生成函式的邏輯，
MGF1是基于散列函式的掩碼生成函式，在RSA最優非對稱加密填充一文中，提到的公共單向函式G其實就是掩碼生成函式，這里詳細講一下其程序，
方法： MGF1 (mgfSeed, maskLen)

引數：
mgfSeed 掩碼生成操作的目標字串
maskLen 生成掩碼長度，最多 $2^{32}$
可選引數：
Hash 哈希方法

輸出: maskLen長度的掩碼

執行程序比較清晰，參照如下Python代碼：

  def mgf1(mgf_seed, mask_len, hash_type="SHA256"):
        '''
        Mask Generation Function based on a hash function as defined in Section B.2.1 of [RFC8017]
        @Input:
            mgs_seed - seed from which mask is generated, an octet string
            mask_len - intended length in octets of the mask, at most 2^32 hLen
            hash_type - the digest hash function to use, default is SHA1
        Outout:
            mask: an octet string of length mask_len
        '''
        hash_class = hashlib.new(hash_type)
        # get hash length given hash function
        h_len = hash_class.digest_size

        # If maskLen > 2^32 hLen, output "mask too long" and stop.
        if mask_len > 0x10000:
            raise ValueError('mask too long')

        # Let T be the empty octet string.
        T = b''
        hash_class.update(mgf_seed.encode(encoding='UTF-8'))

        # For counter i from 0 to \ceil (mask_len / h_len) - 1
        for i in range(0, integer_ceil(mask_len, h_len)):
            # Convert counter to an octet string C of length 4 octets
            C = RSA_FDH_VRF.i2osp(i, 4)

            # Concatenate the hash of the seed mgfSeed and C to the octet string T
            # T = T || Hash(mgfSeed || C)
            # temp = (mgf_seed + C.decode(encoding='UTF-8')).encode(encoding='UTF-8')
            # temp = b"".join([mgf_seed.encode(encoding='UTF-8'), C])
            hash_class.update(C)
            # T = T + hash_class.digest()
            T = b"".join([T, hash_class.digest()])

        # Output the leading maskLen octets of T as the octet string mask.
        return T[:mask_len]

其中i2osp方法參考符號約定說明，不再贅述，

證明生成程序

方法： RSAFDHVRF_prove(K, alpha_string)
引數：
K - RSA 私鑰 alpha_string - 原始訊息回傳值: pi_string - 長度為k的證明字串

執行主要程序:

one_string = 0x01 = I2OSP(1, 1)
EM = MGF1(one_string || I2OSP(k, 4) || I2OSP(n, k) || alpha_string, k - 1)
m = OS2IP(EM)
s = RSASP1(K, m)
pi_string = I2OSP(s, k)
回傳 pi_string

證明驗證程序

方法： RSAFDHVRF_verify((n, e), alpha_string, pi_string)
引數：
(n, e) - RSA 公鑰
alpha_string - 原始訊息
pi_string - 證明字串輸出：
合法如果驗證通過

執行主要程序:

s = OS2IP(pi_string)
m = RSAVP1((n, e), s)
EM = I2OSP(m, k - 1)
one_string = 0x01 = I2OSP(1, 1)
EM' = MGF1(one_string || I2OSP(k, 4) || I2OSP(n, k) || alpha_string, k - 1)
如果EM == EM' 則是合法證明，否則回傳非法，

所用到的方法，符號約定中有所說明，具體實作各編程語言略有不同，

小結

本文主要介紹了VRF基于RSA公鑰體制的實作，如果對RSA原理比較熟悉，那么就比較容易理解了，其中掩碼生成函式在密碼學中應用較多，后續還有可能提到，

完整的具體實作代碼可參照：https://github.com/DreamWuGit/RSA-VRF

最近（其實一直都有）有朋友說我數學不好，看起來困難，所以不能堅持看下去，對此我只能說：
春種秋收，播種和識訓不在同一個季節

我們很小的時候，什么都不會，各方面都不好，現在不也會了很多嗎？靠的就是不斷的學習，或者說，能否保持持續的學習狀態，是一個人后天發展程度一個重要因素，
想要怯懦退縮，理由有千萬個，想要前進，方法卻少的可憐，可能只有一兩個，這是嚴重不對稱的！

好了，之前說了有兩種VRF與公鑰體制實作的方式，下一篇繼續說另一種基于橢圓曲線公鑰體制的VRF演算法！

歡迎關注&在看，疑問請留言！
歡迎關注公眾號blocksight

區塊鏈中的數學（四十二）---基于RSA的VRF（隨機可驗證函式）

寫在前面

RSA-FDH-VRF

符號約定

證明生成程序

證明驗證程序

小結

相關閱讀：