变色龙哈希学习笔记

用于记录变色龙哈希的学习历程

没写完，不打算写了~

Chameleon Hashing and Signatures

作者：Hugo Krawczyk, Tal Rabin

时间：1997

Based on Claw-free Trapdoor Permutations

General Construction

计算过程

实验代码

#基于线性方程进行模拟
import random
import gmpy2
from Crypto.Util.number import *

a = 0 ; b = 0 ; c = 0 ; d = 0 ; p = 0

def init():
    global a, b, c, d, p
    p = getPrime(512)
    while True:
        a = random.randint(1, 2**512)
        c = random.randint(1, 2**512)
        if gmpy2.gcd(a, p) == 1 and gmpy2.gcd(c, p) == 1:  # 确保 a 和 c 与 p 互质
            break
    b = random.randint(1, 2**512)
    d = random.randint(1, 2**512)

# 线性变换函数
def f1(x):
    return (a * x + b) % p

def f2(x):
    return (c * x + d) % p

# 线性变换逆函数
def inv_f1(y):
    return (y - b) * gmpy2.invert(a, p) % p

def inv_f2(y):
    return (y - d) * gmpy2.invert(c, p) % p

if __name__ == '__main__':
    init()
    m1 = bytes_to_long(b'flag{Chameleon_Hash_is_good}')
    r1 = random.randint( 1 , p - 1 )

    # 计算 H(m1, r1)
    H = r1
    for i in str(bin(m1)[2:]):
        if i == '1':
            H = f1(H)
        else:
            H = f2(H)
    print(f"H(m1, r1): {H}")

    m2 = bytes_to_long(b'flag{I_agree_with_msg1}')

    # 构造新的随机数 r2，使 H(m1, r1) = H(m2, r2)
    r2 = H
    for i in reversed(str(bin(m2)[2:])):  # 逆序推回原随机数
        if i == '1':
            r2 = inv_f1(r2)
        else:
            r2 = inv_f2(r2)
    print(f"Recovered r2: {r2}")

    # 验证碰撞：计算 H(m2, r2)
    H2 = r2
    for i in str(bin(m2)[2:]):
        if i == '1':
            H2 = f1(H2)
        else:
            H2 = f2(H2)
    print(f"H(m2, r2): {H2}")

    # 验证碰撞结果
    if H == H2:
        print("Hash collision successful!")
    else:
        print("Hash collision failed!")

Based on the Intractability of Factoring

系统参数

计算过程

困难问题

该问题的核心为平方根的计算，可以规约到因数分解问题

给定 $n = p \cdot q$ 和一个整数 $y \in \mathbb{Z}_n$，想要找到 $x \in \mathbb{Z}_n$ 使得：

$x^2 \equiv y \mod n$

也就是计算 $y$ 在模 $n$ 下的平方根。

这在一般情况下是一个困难的问题，除非知道 $n$ 的两个素因数 $p$ 和 $q$。

实验代码

1	#总是有问题，后面再解决

Based on Discrete Log

系统参数

计算过程

推导

已知 $CH(m,r) = g^m\cdot y^r$

即 $CH(m,r) = g^m\cdot g^{x\cdot r} = g^{m+x\cdot r}$

故令 $CH(m’,r’)\equiv CH(m,r)\mod p$

有 $g^{m’+x\cdot r’}\equiv g^{m+x\cdot r}\mod p$

即 $m’+x\cdot r’\equiv m+x\cdot r\mod q$

移项得到 $r’\equiv r+\frac{m-m’}{x}\mod q$

实验代码

#具体见比赛代码
SK = random.randint(1, q)
PK = pow( g , x , p )

r1 = random.randint(1, q)
CH = pow( g , h , p ) * pow( PK , r1 , p ) % p
r2 = exgcd(SK,q)[0] * ( H(m1) - H(M2) + SK * r1 ) % q

Chameleon Signature Schemes

Chameleon Signing

签名步骤

验证步骤

争议解决

Enhancements

The recipient’s identity

签名时不仅绑定消息的哈希值，还绑定接收者 RRR 的身份 $id_R$。这样可以避免签名者更改签名中的身份信息。

Exposure-freeness

Memory requirements

Security Requirements

A Full Chameleon Signature Scheme

Algorithm

Chameleon Hashing without Key Exposure

作者：Xiaofeng Chen

时间：2004

Preliminary Works

Gap Diffie-Hellman Group

设 $G$ 是一个由生成元 $g$ 生成的循环乘法群，其阶数为素数 $q$。假设 $G$ 上的求逆运算和乘法运算可以高效完成。在这样的群 $G$ 上，定义以下三个问题：

一个群 $G$ 被称为 Gap Diffie-Hellman 群，如果：

判定性 Diffie-Hellman 问题（DDHP）可以在多项式时间内高效解决。
计算性 Diffie-Hellman 问题（CDHP）在没有特殊辅助信息的情况下没有多项式时间算法能够解决。

换句话说，在这样的群中，验证 $g^c = g^{ab}$ 是简单的，但直接计算$g^{ab}$ 是困难的。

Chameleon Hashing

Composition

Security properties

Mention

“Key Exposure Problem” is not but——

（这一条存疑）

how to key_exp

$CH(m)=g^{m+x\cdot r} \\ CH(m')=g^{m'+x\cdot r'}$

$g$是系统公共参数，已知

$\begin{flalign} 已知&\ g^my^r=g^{m'}y^{r'}\\ 所以有&\ g^mg^{x\cdot r}=g^{m'}y^{x\cdot r'}\\ 则有&\ m+x\cdot r=m'+x\cdot r'\\ 移项得到&\ x=\frac{m-m'}{r'-r} \end{flalign}$

On the Key Exposure Problem in Chameleon Hashes

作者：Giuseppe Ateniese

时间：2004

Introduction

上一篇论文提供了一种密钥无暴露变色龙哈希函数的具体构造，该函数在具有双线性配对的 Gap 群设置下工作。虽然这无疑是密钥无暴露变色龙哈希的第一个完整构造，但它并没有解决是否存在基于其他加密假设或更高效方案的构造的问题，例如与 [12] 中的原始变色龙哈希函数具有可比性能的构造。

Ateniese, G., de Medeiros, B.:
Identity-based chameleon hash and applications.
In Fi-
nancial Cryptography 2004. LNCS 3110, Springer-Verlag (2004) 164–180. Available online at
http://eprint.iacr.org/2003/167/.