密码学小知识(6)：变色龙哈希函数（Chameleon Hash）

本篇博文将介绍变色龙哈希函数。

在介绍变色龙哈希函数之前，我们先简单回顾一下经典的哈希函数，这样就能对比它们之间的差别。

一、哈希函数

哈希函数$Hash()$是密码学中经常用到的一个函数（记住它并不是加密技术，独立于非对称加密和对称加密之外的函数），任意大小的输入消息$m$经过哈希函数$H()$映射成一个固定长度的输出值$h$，通常称$h$为哈希值或哈希摘要，即
$$h=H(m)$$具有三个特别重要的性质：

• 1）单向性：从输入到输出的计算过程较为容易，而由输出值推出输入值是不可能的（计算上几乎不可能实现）；
• 2）抗碰撞性：一般分为弱抗碰撞性和强抗碰撞性（一般很容易搞混，注意区分）
  • 弱抗碰撞性：任意给定消息$m$，寻找$m^{\prime }(m^{\prime }\ne m)$，使得$H(m^{\prime })=H(m)$在计算上是不可能的；
  • 强抗碰撞性：找到任意两个相同哈希值$H(m)=H(m^{\prime })$的不同消息对$(m,m^{\prime })$在计算上是不可能的。
• 3）高灵敏性：输入若发生非常非常微小的变化（甚至加个标点符号或空格)，则输出值会发生巨大的变化（至少一半长的比特位变化）。

一句话概括哈希函数：将任意长度、类型或大小的字符串输入到哈希函数中，输出固定长度的字符串。

二、变色龙哈希函数

变色龙哈希函数（Chameleon Hash），听名字感觉就很怪，一个哈希函数怎么跟小动物相关呢，一开始我看到这个中文译名也是一样感觉。可以这样理解，变色龙是一种会随着周围环境变化而改变自身颜色的小动物，而哈希函数又是一种只知道输出而无法知道输入的函数，两者结合起来，是否可以理解为变色龙哈希函数的某种情况下知道输出可以推出输入？

定义：任何人可以通过给定的公钥$pk$进行变色龙哈希后，拥有$sk$的用户可以广义地找到哈希碰撞，即使得$Ch\_Hash(m^{\prime })=Ch\_Hash(m)$。

变色龙哈希函数具有4个主要的算法：

• 1）密钥生成算法$Ch\_Gen(1^{\lambda })=(pk,sk)$：给定一个安全常数$\lambda$，输出变色龙哈希的公钥$pk$和私钥$sk$（陷门）；
  
• 2）哈希生成算法$Ch\_Hash(pk,m,r)=(h,p)$：输入公钥$pk$、随机数$r$和任意消息$m$，生成哈希值$h$和随机数$p$；
  
• 3）哈希验证算法$Ch\_Ver(pk,m,(h,p))$：输入公钥$pk$、任意消息$m$和哈希值$h$、随机数$p$，若$(h,p)$是正确的哈希值，则输出1，否则输出0；
  
• 4）哈希碰撞算法$Ch\_Cld(sk,m,m^{\prime },(h,p))$：输入私钥$sk$（陷门）、消息$m$、新消息$m^{\prime }$和哈希值$h$、随机数$p$，输出新随机数$r^{\prime }$，使得$Ch\_Ver(pk,m,(h,p),r)=Ch\_Ver(pk,m^{\prime },(h,p),r^{\prime })=1$。
  

三、变色龙哈希的安全需求

• 1）抗碰撞性：在没有陷门$sk$的情况下，输入消息$m_1$、随机数$r_1$和消息$m_2$，求满足$Hash(m_1,r_1)=Hash(m_2,r_2)$的整数$r_2$是几乎不可能的。
• 2）陷门碰撞：在输入陷门$sk$后，对于任意的$m_1、r_1$，给定消息$m_2$，可以计算出$r_2$，满足$Hash(m_1,r_1)=Hash(m_2,r_2)$。
• 3）语义安全：对于任意消息$m_1,m_2$，他们的$Hash(m_1,r_1)$和$Hash(m_2,r_2)$的概率分布在计算上是不可区分的。

四、基于离散对数的变色龙哈希函数的构造(举例)

假设$p、q$为两个素数且$q$为足够大的素数，其中$p、q$满足$p=kq+1$，$Z_p^{\ast }$是一个阶为$q$的群，$g$是群的生成元。设陷门$sk$为$x\in Z_p^{\ast }$，则公钥$pk$表示为$y=g^{x}modp$，给定一个消息$m_1\in Z_p^{\ast }$和一个随机值$r_1\in Z_p^{\ast }$，则消息$m_1$的CH值为$Hash(m_1,r_1)=g^{m_1}{y}^{r_1}modp$。

求任意给定$m_1、m_2、r_1$，能够找到$r_2\in Z_p^{\ast }$，使得$Hash(m_1,r_1)=Hash(m_2,r_2)？$

解：

由于$$Hash(m_1,r_1)=g^{m_1}{y}^{r_1}modp=g^{m_1+x{r}_1}modp$$$$Hash(m_2,r_2)=g^{m_2}{y}^{r_2}modp=g^{m_2+x{r}_2}modp$$

所以有
$$r_2=\frac{m_1-m_2}{x}+r_{1}modp$$

相应的代码实现，可以参考大佬写的java实现，见评论区！