导语：本课堂用通俗易懂的系列内容为大家呈现区块链与密码学领域相关知识。这里有知识也有故事，从感兴趣到有乐趣，全民课堂等你来学。这个系列中的课程内容首先从比特币着手进行入门介绍，再延伸至区块链的相关技术原理与发展趋势，然后深入浅出地依次介绍在区块链中应用的各类密码学技术。欢迎大家订阅本公众号，持续进行学习。
8.2 RST环签名算法
2001-2002年，以Rivest等人提出的环签名定义为标志，这一阶段的工作主要参考Rivest等人的方案提出的签名方案。
2003-2004年，经过两年对环签名的概念和意义的认识和理解后，许多密码界人士开始对环签名进行深入研究，涌现了很多新思想、新模型和新方案，是环签名发展的关键时期。
2005年至今，这一阶段更加注重环签名的安全性、效率和实用性的研究，包括安全高效的环签名算法研究、环签名与通常的数字签名相互转化的研究以及环签名推广方面的研究。
今天我们要学习的是RST环签名算法。
首先给出单向陷门函数的定义：
给定x，可以较容易的计算y=f(x)，而给定y，计算满足y=f(x)的x即计算是困难的。但若得到对应的陷门t，计算是容易的。
单向陷门函数可以看作将给定的x放在一个有暗门的盒子当中，如下图：
基于RSA算法的陷门函数：
每个环成员(1≤ i≤ r) 有一个RSA公私钥对 (=(，)，=)，其中=1 modφ()，由此定义了单向陷门函数：
显然，只有拥有对应陷门信息的环成员能够计算出。
为了将单个签名方便的组合成环签名，将陷门函数扩展到上的
组合函数：
定义一种带密钥的组合函数(，，…，)，输入为密钥k，初始值v和任意，，…，∈，以对称加密算法为子程序，输出z∈，计算方式及示意图如下：
对任意给定的密钥k和初始值v，组合函数(，，…，) 需满足以下三个性质：
- 对每个输入进行排列：对每个s，1≤ s ≤r，固定y_i (1≤i≤r且i≠s)，组合函数为y_s到输出值z的一一映射
- 单一输入有效可解：对每个s，1≤s≤r，给定z和(1≤i≤r且i≠s)，可有效解得满足(，，…，)=z
例如:思考k=3的情况：(，，)=(⨁(⨁(⨁v)))=z，若给定z，，，求满足(，，)=z的。提示：已知值为 k，v，z，，
- 没有陷门输入不可求：给定k，v和z，如果敌手不能求得任一陷门函数，，…，的逆，则求解满足如下等式的，，…，是不可行的
算法描述：
1. 密钥对生成
生成陷门函数，公布函数并保存陷门信息. (即·=1 mod)
2. 环签名生成
给定待签名消息m，签名者π密钥π和所有环成员公钥，，…，，签名者通过以下步骤生成环签名：
①选取密钥k：计算k=h(m)（或k=h(m，，…，)）；
②选取随机粘合值：随机选择初始（粘合）值v∈；
③选取随机值：为所有其他环成员选择∈(1≤i≤r，i≠π)，并计算
④求解π：根据(1≤i≤r，i≠π)，求满足如下等式的π
组合函数的性质②保证了方程可解；
⑤对陷门函数求逆：根据π和陷门信息（私钥）求逆
⑥输出环签名：对m的环签名为一个(2r+1)元组
3. 环签名验证
根据对消息的m的签名(，…，;v;，…，)，验证者通过以下方式验证环签名。
①应用陷门函数：对i=1，2，…，r，计算
②获取密钥k：计算加密密钥k
③验证环等式：验证y_i是否满足
若等式成立，环签名为有效签名，否则为无效签名。
今天的课程就到这里啦，下节课我们将继续学习经典的环签名算法，敬请期待！
同学们可以关注PlatON World，持续学习哦。我们下节课见啦。
本文转载自https://mp.weixin.qq.com/s?__biz=MzUzNTg2ODg5MQ==&mid=2247494151&idx=1&sn=c2dc1e8a47ac79825995f12c8a4b8dbc&chksm=fafc4eb3cd8bc7a553f2b98df44c10fc532381c29b1e5d99007d3529bb12433b3ac32b1063f7&scene=178&cur_album_id=1411898566347735044#rd
