可验证延迟函数与延迟加密

一、 时间锁谜题

Time lock puzzles and timed release Crypto

假设你有一段消息，需要将其加密到未来，思想是很显然的，可以设置一个复杂度参数S，这个参数和需要加密到的时间T以及机器的运算能力R有关，如果Alice想让拥有运算能录R的Bob在时间T后才能得到解密的信息，那她只需设置S=RT就行。但是显然，只有这一个参数是不够的，因为Alice肯定不希望自己在加密的时候也需要长度为T的时间，故而这就需要构造一个陷门函数，而在这个思想下的方案就是接下来的基于RSA的时间锁谜题

方案

1. $Setup$

• Alice生成大素数 $p,q \in \mathbb{Z}^*$ ，计算 $\phi{(n)}=pq$
• 计算 $t=TS$，其中 $S$ 是Solver每秒钟能做 $x^2 \equiv \; ? \; mod \; n$ 运算的次数，S为需要加密到多久之后，单位为秒

2. $KeyGen$

• Alice选取随机数 $a \in \mathbb{Z}_n^*$ ，计算 $b=a^{2^t} \; mod \; n$
• 为了加速运算，可以先计算 $e = 2^t \; mod \; \phi{(n)}$ ，然后计算 $b=a^e \; mod \; n$
• 显然这个 $b$ 可以用来作为一把密钥来加密任意消息
• 此时输出公共参数 $pp \rightarrow (n,a,t)$

3. $Decrypt$

• Solver接收到公共参数 $pp$ 后，计算 $b=a^{2^t} \; mod \; n$ 即可恢复消息

分析：为什么计算b对于Alice是容易的

A Simple Unpredictable Pseudo-Random Number Generator

• 由于Alice知道 $\phi(n)$ ，所以可以快速计算出 $e = 2^t \; mod \; \phi{(n)}$ ，从而快速计算出 $b=a^e \; mod \; n$

• 证明：

  • 根据欧拉定理，$a^{\phi(n)} \equiv 1 \; mod \; n$ ，所以 $a^{k \cdot \phi(n) + r} \equiv a^r \; mod \; n$ ，其中 $k,r \in \mathbb{Z}^+$ 且 $r < \phi(n)$
  • 因为 $e = 2^t \; mod \; \phi{(n)}$ ，所以存在整数 $k$ 使得 $2^t = k \cdot \phi(n) + e$ ，从而有 $a^{2^t} = a^{k \cdot \phi(n) + e} \equiv a^e \; mod \; n$

• 故而对于Alice来说，时间复杂度为 $O(\log{t})$ ，而对于Solver来说，时间复杂度为 $O(\log{2^t})$ ，显然当 $t$ 很大时，二者的差距是非常明显的，即 $e = 2^t \; mod \; n \ll 2^t$

Simple Code

from Crypto.Util.number import getPrime
import time

class TimeLockPuzzle:
    def __init__(self, bit_length=1024):
        self.bit_length = bit_length

    def setup(self, T, S):
        p = getPrime(self.bit_length // 2)
        q = getPrime(self.bit_length // 2)
        n = p * q
        phi_n = (p - 1) * (q - 1)
        t = T * S
        self.n = n
        self.phi_n = phi_n
        self.t = t
        return n, t

    def keygen(self):
        a = getPrime(self.bit_length // 2) % self.n
        e = pow(2, self.t, self.phi_n)
        b = pow(a, e, self.n)
        self.a = a
        self.b = b
        return a, b

    def decrypt(self):
        b_recovered = self._sequential_square(self.a, self.t, self.n)
        return b_recovered

    def _sequential_square(self, base, exponent, modulus):
        result = base
        for _ in range(exponent):
            result = pow(result, 2, modulus)
        return result
    
if __name__ == "__main__":
    T = 10000  # seconds
    S = 1000  # operations per second (assumed)
    tlp = TimeLockPuzzle()
    n, t = tlp.setup(T, S)
    current = time.time()
    a, b = tlp.keygen()
    print(f"Key generation time: {time.time() - current} seconds")
    print(f"Public parameters: n={n}, a={a}, t={t}")
    current = time.time()
    b_recovered = tlp.decrypt()
    print(f"Decryption time: {time.time() - current} seconds")
    print(f"Recovered b: {b_recovered}")
    assert b == b_recovered, "Decryption failed!"

"""
Key generation time: 0.008075475692749023 seconds
Public parameters: n=61810108824843907643925459580373129519690423489940860100202862297484990410304986100046711503574346022697879308140870937441460343573704624596579937375030021794915980312213384758724465676926095996846213336618114431740018299175891700104135217599794842161257422938682815373756560088332809929584619284410285587977, a=7443314266998431411127448342181248496286899274265431760494371782960829242481068484434694285342619770586185525275770484056179248735233869466965615194303777, t=10000000
Decryption time: 18.805336236953735 seconds
Recovered b: 14566162181363302159423663242722746769045635619954381061036224370343306364598291823767622850797618301464610097291697395426850839384906404062474900741300377029381051710326515638765495985618414061840874456098038537905521886568774360102886677861421150479723433406541128695059738821435682671042526269911589516319
"""