密码学读书笔记——Fiat-Shamir
交互式的身份验证
在中心准备签发智能卡时，会信选择出一个模数n和一个伪随机函数f，这个伪随机函数f可以将任意的字符串与[0,n)当中的一个数联系起来。n是两个秘密（只有中心知道）素数p和q的乘积。
当一个合法的用户希望申请一个智能卡时，中心会解析它的所有相关信息，包括名字、地址、ID、物理特征描述等，这些信息会被包括在一个字符串当中，同时有关卡片本身的一些信息也会被包含在其中（发行日期，有效性限制等）。这些信息一旦被确认发行之后就无法修改，所以保证它正确很有必要。
以下是中心对于字符串I的操作：
- 计算vj=f(I,j),j 是一些很小的数；
- 选择k个不同的j，使得vj是n的平方剩余，同时计算关于vj-1（mod n）的最小平方根sj，其中vj-1应该是vj关于n的欧拉函数的逆；
- 发行这张新的智能卡，在这张智能卡中包括了字符串I，k个*sj*和它们所对应的索引。
当用户使用智能卡时，验证者需要对该智能卡进行验证，通常在验证的机器中值保存着模数n和伪随机函数f。智能卡向验证者证明它知道*s1，…,sk*的值，同时不会泄露这些值给验证者。
证明协议包括以下协议步骤（其中A是证明者，B是验证者）：
-
A将I发送给B；
-
B计算vj=f(I,j)，j=1,…,k;
以下3-6步骤将重复t次，i=1,…,t:
-
A选择一个随机数ri ∈ \in ∈[0,n),计算xi=ri2(mod n)发送给B；
-
B选择一个随机向量（ei1,…,eik） ∈ \in ∈{0,1}，发送给A；
-
A计算yi，并发送给B；
- B计算以下公式，如果成立，则证明A是合法的。
非交互式的签名方案
在交互式的签名方案中，B需要发送eij矩阵给A，A和B之间存在交互，下面将介绍一种非交互验证方案，使得两者之间不需要通过交互即可验证A的合法性。
在证明者这一端：
- A选择随机的r1,…,rt ∈ \in ∈[0,n),同时计算xi=ri2(mod n);
- A计算 f(m,x1,…,xt),同时使用计算结果的钱kt位作为矩阵eij的值（1 ≤ \leq ≤i ≤ \leq ≤t,1 ≤ \leq ≤j ≤ \leq ≤k）;
- A计算yi，通是将I,m和eij矩阵发送给验证者B。
在验证者这一端，验证A在消息m上的签名是否合法：
-
B计算vj=f(I,j),j=1,…,k;
-
B计算
-
B验证*f(m,z1,…,zt)的前kt位是否等于eij.如果成立证明A的签名合法。
关于Fait-Shamir安全性的思考
在交互式的身份验证方案中，随机矩阵eij是由验证者决定和发送的，而在非交互式的身份签名方案中，随机矩阵eij是由证明者通过随机函数计算结果所选择的，这个矩阵的随机性完全依赖于韩系函数f，一旦f被破解，也就会带来安全问题，证明者可以控制它的那几个值会被验证。