区块链中的数学-VRF基于RSA公钥体制的实现

本文主要介绍了VRF基于RSA公钥体制的实现,如果对RSA原理比较熟悉,那么就比较容易理解了。其中掩码生成函数在密码学中应用较多,后续还有可能提到。

## 写在前面 上一节说了[VRF(随机可验证函数)概述](https://learnblockchain.cn/article/1543),由于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最优非对称加密填充](https://learnblockchain.cn/article/1562)一文中,提到的公共单向函数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的证明字符串 执行主要过程: 1. one_string = 0x01 = I2OSP(1, 1) 2. EM = MGF1(one_string || I2OSP(k, 4) || I2OSP(n, k) || alpha_string, k – 1) 3. m = OS2IP(EM) 4. s = RSASP1(K, m) 5. pi_string = I2OSP(s, k) 6. 返回 pi_string ### 证明验证过程 方法:RSAFDHVRF_verify((n, e), alpha_string, pi_string) 参数: (n, e) – RSA 公钥 alpha_string – 原始消息 pi_string – 证明字符串 输出: 合法如果验证通过 执行主要过程: 1. s = OS2IP(pi_string) 2. m = RSAVP1((n, e), s) 3. EM = I2OSP(m, k – 1) 4. one_string = 0x01 = I2OSP(1, 1) 5. EM’ = MGF1(one_string || I2OSP(k, 4) || I2OSP(n, k) || alpha_string, k – 1) 6. 如果EM == EM’ 则是合法证明,否则返回非法。 所用到的方法,符号约定中有所说明,具体实现各编程语言略有不同。 ## 小结 本文主要介绍了VRF基于RSA公钥体制的实现,如果对RSA原理比较熟悉,那么就比较容易理解了。其中掩码生成函数在密码学中应用较多,后续还有可能提到。 完整的具体实现代码可参照:https://github.com/DreamWuGit/RSA-VRF 最近(其实一直都有)有朋友说我数学不好,看起来困难,所以不能坚持看下去,对此我只能说: **春种秋收,播种和收获不在同一个季节** 我们很小的时候,什么都不会,各方面都不好,现在不也会了很多吗?靠的就是不断的学习,或者说,能否保持持续的学习状态,是一个人后天发展程度一个重要因素。 想要怯懦退缩,理由有千万个,想要前进,方法却少的可怜,可能只有一两个, 这是**严重不对称**的! 好了, 之前说了有两种VRF与公钥体制实现的方式,下一篇继续说另一种基于椭圆曲线公钥体制的VRF算法! 欢迎关注公众号:blocksight ### 相关阅读: [区块链中的数学-RSA签名过程!](https://learnblockchain.cn/article/1546) [区块链中的数学-RSA加解密原理](https://learnblockchain.cn/article/1548) [区块链中的数学-VRF(随机可验证函数)概述](https://learnblockchain.cn/article/1543) [区块链中的数学-Uniwap核心算法解析-完结篇](https://learnblockchain.cn/article/1522) [区块链中的数学-Uniwap核心算法解析(下)](https://learnblockchain.cn/article/1521) [区块链中的数学-Uniwap核心算法解析(中)](https://learnblockchain.cn/article/1492) [区块链中的数学-Uniwap自动化做市商核心算法解析(上)](https://learnblockchain.cn/article/1494)

写在前面

上一节说了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的证明字符串

执行主要过程:

  1. one_string = 0x01 = I2OSP(1, 1)

  2. EM = MGF1(one_string || I2OSP(k, 4) || I2OSP(n, k) || alpha_string, k – 1)

  3. m = OS2IP(EM)

  4. s = RSASP1(K, m)

  5. pi_string = I2OSP(s, k)

  6. 返回 pi_string

证明验证过程

方法:RSAFDHVRF_verify((n, e), alpha_string, pi_string)

参数: (n, e) – RSA 公钥 alpha_string – 原始消息 pi_string – 证明字符串 输出: 合法如果验证通过

执行主要过程:

  1. s = OS2IP(pi_string)

  2. m = RSAVP1((n, e), s)

  3. EM = I2OSP(m, k – 1)

  4. one_string = 0x01 = I2OSP(1, 1)

  5. EM’ = MGF1(one_string || I2OSP(k, 4) || I2OSP(n, k) || alpha_string, k – 1)

  6. 如果EM == EM’ 则是合法证明,否则返回非法。

所用到的方法,符号约定中有所说明,具体实现各编程语言略有不同。

小结

本文主要介绍了VRF基于RSA公钥体制的实现,如果对RSA原理比较熟悉,那么就比较容易理解了。其中掩码生成函数在密码学中应用较多,后续还有可能提到。

完整的具体实现代码可参照:https://github.com/DreamWuGit/RSA-VRF

最近(其实一直都有)有朋友说我数学不好,看起来困难,所以不能坚持看下去,对此我只能说: 春种秋收,播种和收获不在同一个季节

我们很小的时候,什么都不会,各方面都不好,现在不也会了很多吗?靠的就是不断的学习,或者说,能否保持持续的学习状态,是一个人后天发展程度一个重要因素。 想要怯懦退缩,理由有千万个,想要前进,方法却少的可怜,可能只有一两个, 这是严重不对称的!

好了, 之前说了有两种VRF与公钥体制实现的方式,下一篇继续说另一种基于椭圆曲线公钥体制的VRF算法!

欢迎关注公众号:blocksight

相关阅读:

区块链中的数学-RSA签名过程!

区块链中的数学-RSA加解密原理

区块链中的数学-VRF(随机可验证函数)概述

区块链中的数学-Uniwap核心算法解析-完结篇

区块链中的数学-Uniwap核心算法解析(下)

区块链中的数学-Uniwap核心算法解析(中)

区块链中的数学-Uniwap自动化做市商核心算法解析(上)

本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

  • 发表于 2020-10-05 21:50
  • 阅读 ( 129 )
  • 学分 ( 16 )
  • 分类:入门/理论

该内容来自于互联网公开内容,非区块链原创内容,如若转载,请注明出处:https://htzkw.com/archives/27671

联系我们

aliyinhang@gmail.com