变色龙哈希
- 单向性：就像普通的哈希函数一样，给定一个输入消息，计算哈希值是容易的，但反过来从哈希值推导出输入消息是困难的。
- 陷门性：变色龙哈希函数有一个秘密值（通常称为陷门），知道这个秘密值的人可以很容易地找到两个不同的消息，使它们具有相同的哈希值（即生成碰撞）。
- 公钥和私钥：类似于公钥加密系统，变色龙哈希也有公钥和私钥。公钥用于生成哈希值，私钥则用于生成碰撞。
- 哈希计算：给定一个消息 ( M ) 和一个随机数 ( r )，哈希值计算为 ( H(M, r) )。
- 碰撞生成：如果掌握了私钥，则可以在给定哈希值 ( h = H(M_1, r_1) ) 和任意新消息 ( M_2 ) 的情况下，找到一个新的随机数 ( r_2 )，使得 ( H(M_2, r_2) = h )。
- 系统参数：选择一个大素数
和生成元 。 - 密钥生成：选择私钥
，计算公钥 。 - 哈希计算：给定消息
和随机数 ，计算哈希值为 - 碰撞生成：假设有一个初始消息
和其对应的哈希值 ，以及新的消息 。我们希望找到一个 ，使得 通过私钥 ，可以计算出 的值为