BCP加密算法改进方案（DT-PKC）复现记录

2019-10-31 本文已影响0人不懂球的2大业

1.简介

相关论文：An efficient privacy-preserving outsourced calculation toolkit with multiple keys。这篇论文由Ximeng LIU,RobertH.DENG,Kim-Kwang Raymond CHOO,Jian WENG发表于TIFS（IEEE Transactions on Information Forensics and Security）。该论文针对BCP算法构建的多密钥下同态运算的方案提出一些改进（改进后的方案称为：DT-PKC），将可以解密的系统主密钥（ $MK$ ），拆分为两个部分，任何一个部分都不能单独解密。这样可以解决中心节点拥有主密钥所产生的安全性问题。
本文主要介绍其对BCP算法的改进部分，即如何拆分主密钥及拆分主密钥后的解密运算。
关于BCP加密算法的简介：参考文章BCP加密算法复现记录。

2.DT-PKC复现记录

2.1 环境配置

参考：BCP加密算法复现记录。

2.2 重要步骤说明

导入依赖的库及函数

from charm.toolbox.integergroup import IntegerGroup
from charm.schemes.pkenc.pkenc_rsa import RSA_Enc, RSA_Sig
from charm.core.math.integer import integer,randomBits,random,randomPrime,isPrime,encode,decode,hashInt,bitsize,legendre,gcd,lcm,serialize,deserialize,int2Bytes,toInt

第一步：初始化，生成公共参数及系统主密钥。
首先选取一个安全参数 $secparam$ ，之后选取两个安全素数（safe prime） $p,q$ ，使其位长度（bit length）为 $secparam$ ，根据安全素数的定义， $p^{'} = (p-1)/2$ 和 $q^{'}=(q-1)/2$ 也是素数。之后计算 $N = pq$ 和 $\lambda = lcm(p-1,q-1)/2$ （ $lcm:$ 最小公倍数）。定义一个函数： $L(x) = (x-1)/N$ 。选取一个 $(p-1)(q-1)/2$ 阶元 $g$ ， $g$ 可以通过随机选取 $a\in Z^{*}_{N^2}$ ,计算 $g = -a^{2N}$ 获得，相关论文：Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption。这样,系统的主密钥 $MK = \lambda$ 。
相关代码：

def __init__(self,secparam = 128):
        self.p,self.q = randomPrime(secparam,True),randomPrime(secparam,True)
        self.pp = (self.p - 1)/2
        self.qq = (self.q - 1)/2
        self.N = self.p * self.q
        self.N2 = self.N**2
        self.lamda = lcm(self.p-1,self.q-1)/2
        
        # 一下为选取一个(p-1)(q-1)/2阶元
        # 先随机选取a
        self.a = random(self.N2)
        # 计算a^2N
        tmp = self.a**(2*self.N)
        # 计算-a^2N
        self.g = (int(self.N2)-int(tmp))%self.N2
        self.mk = self.lamda

第二步：密钥生成。
随机选取 $\theta \in [1,N/4]$ ，计算 $h = g^{\theta} mod N^2$ 。公钥 $pk = (N,g,h)$ ，私钥 $sk = \theta$ 。
相关代码：

    def KeyGen(self):
        theta = random(self.N/4)
        h = self.g**(theta)%self.N2
        pk = {"N":self.N,"g":self.g,"h":h}
        sk = theta
        return pk,sk

第三步：加密。
明文空间： $m\in Z_N$ ，选取随机数 $r \in [1,N/4]$ 。这样使用公钥 $pk$ 加密 $m$ 得到密文可以表示为 $[m]_{pk} = \{ T_1,T_2 \}$ ， $T_1 = h^r(1+mN)modN^2$ ， $T_2 = g^r mod N^2$ 。
相关代码：

    def Encrypt(self,pk,plaintext):
        r = random(self.N/4)
        T1 = int(pk["h"]**(r))*int(1+plaintext*self.N) % self.N2
        T2 = pk["g"]**(r) % self.N2
        ciphertext = {"T1":T1,"T2":T2}
        return ciphertext

第四步：使用私钥解密。
密文 $[m]_{pk} = \{ T_1,T_2 \}$ 可以由私钥 $sk = \theta$ 解密，解密公式： $m = L({T_1 \over T_2^\theta} mod N^2)$ 。
相关代码：

    def Decrypt(self,ciphertext,sk):
        T1 = ciphertext["T1"]
        T2 = ciphertext["T2"]
        tmp = (T1 / (T2**sk)) % self.N2
        m = (int(tmp)-1)/self.N
        return m

第五步：使用主密钥解密。
密文 $[m]_{pk} = \{ T_1,T_2 \}$ 还可以由主密钥 $MK = \lambda$ 解密。首先计算 $T_1^\lambda mod N^2 = h^{\lambda r}(1+mN\lambda) mod N^2=g^{\lambda \theta r}(1+mN\lambda)mod N^2 = (1+mN\lambda)$ ，由于 $gcd(\lambda,N) = 1$ ， $m = L(T_1^\lambda mod N^2)\lambda^{-1}mod N$ 。
相关代码：

    def DecryptMK(self,ciphertext,mk):
        tmp = ciphertext["T1"]**(mk) % self.N2
        mk = mk % self.N
        mk_1 = mk**(-1)
        
        m = ((int(tmp)-1)/self.N)*int(mk_1)%self.N
        return integer(m)

第六步：主密钥切分。
主密钥 $MK = \lambda$ 可以被随机切分为两个部分 $\lambda_1,\lambda_2$ ，需要满足 $\lambda_1+\lambda_2\equiv0 mod \lambda$ 并且 $\lambda_1+\lambda_2\equiv1 mod N^2$ 。下面分析可以这样切分的原因：
根据中国剩余定理，由于 $gcd(\lambda,N^2)=1$ ，因此存在 $s$ ，使得 $s\equiv0mod \lambda$ 并且 $s \equiv 1modN^2$ ，且 $s = \lambda \cdot(\lambda^{-1}mod N^{2})mod \lambda N^{2}$ ，参考：C. Ding, Chinese Remainder Theorem. Singapore: World Scientific,1996.
这样，只需随机选取 $\lambda_1,\lambda_2$ ，使得 $\lambda_1+\lambda_2=s$ 即可，相关代码：

    def SplitMK(self,mk):
        mk = mk % self.N
        mk_1 = mk**(-1)
        tmp = int(mk)*int(int(mk_1)%self.N2)
        modulus = int(mk)*int(self.N2)
        s = tmp % modulus
        lamda1 = random(s)
        lamda2 = s - int(lamda1)
        return integer(lamda1),integer(lamda2)

第七步：利用切分后的主密钥进行解密。

这一步又可以分为两小步：

1）利用部分主密钥 $\lambda_1$ 得到中间结果 $CT_1$ ： $CT_1 = {(T_1)}^{\lambda_1}=g^{\lambda_1 r \theta }(1+mN\lambda_1)mod N^2$ 。相关代码：

    def PSDec1(self,ciphertext,lamda1):
        ct1 = ciphertext["T1"]**(lamda1)
        return ct1

2）利用部分主密钥 $\lambda_2$ 与中间结果 $CT_1$ 计算首先得到 $CT_2$ ，之后利用 $CT_1,CT_2$ 计算得到结果： $CT_2={(T_1)}^{\lambda_2}={(T_1)}^{\lambda_2}=g^{\lambda_2 r \theta }(1+mN\lambda_2)mod N^2$ , $T^{"}=CT_1 \cdot CT_2$ ， $m = L(T^{"})$ 。相关代码：

    def PSDec2(self,ciphertext,lamda2,ct1):
        ct2 = ciphertext["T1"]**(lamda2)
        T = ct1*ct2
        m = (int(T)-1)/int(self.N)
        return integer(int(m))

完整代码：

from charm.toolbox.integergroup import IntegerGroup
from charm.schemes.pkenc.pkenc_rsa import RSA_Enc, RSA_Sig
from charm.core.math.integer import integer,randomBits,random,randomPrime,isPrime,encode,decode,hashInt,bitsize,legendre,gcd,lcm,serialize,deserialize,int2Bytes,toInt

class DTPKC():
    def __init__(self,secparam = 128):
        self.p,self.q = randomPrime(secparam,True),randomPrime(secparam,True)
        self.pp = (self.p - 1)/2
        self.qq = (self.q - 1)/2
        self.N = self.p * self.q
        self.N2 = self.N**2
        self.lamda = lcm(self.p-1,self.q-1)/2
        
        self.a = random(self.N2)
        tmp = self.a**(2*self.N)
        self.g = (int(self.N2)-int(tmp))%self.N2
        self.mk = self.lamda

    def GetMK(self):
        return self.mk
    
    def KeyGen(self):
        theta = random(self.N/4)
        h = self.g**(theta)%self.N2
        pk = {"N":self.N,"g":self.g,"h":h}
        sk = theta
        return pk,sk

    def Encrypt(self,pk,plaintext):
        r = random(self.N/4)
        T1 = int(pk["h"]**(r))*int(1+plaintext*self.N) % self.N2
        T2 = pk["g"]**(r) % self.N2
        ciphertext = {"T1":T1,"T2":T2}
        return ciphertext

    def Decrypt(self,ciphertext,sk):
        T1 = ciphertext["T1"]
        T2 = ciphertext["T2"]
        tmp = (T1 / (T2**sk)) % self.N2
        m = (int(tmp)-1)/self.N
        return m

    def DecryptMK(self,ciphertext,mk):
        tmp = ciphertext["T1"]**(mk) % self.N2
        mk = mk % self.N
        mk_1 = mk**(-1)
        
        m = ((int(tmp)-1)/self.N)*int(mk_1)%self.N
        return integer(m)

    def SplitMK(self,mk):
        mk = mk % self.N
        mk_1 = mk**(-1)
        tmp = int(mk)*int(int(mk_1)%self.N2)
        modulus = int(mk)*int(self.N2)
        s = tmp % modulus
        lamda1 = random(s)
        lamda2 = s - int(lamda1)
        return integer(lamda1),integer(lamda2)

    def PSDec1(self,ciphertext,lamda1):
        ct1 = ciphertext["T1"]**(lamda1)
        return ct1

    def PSDec2(self,ciphertext,lamda2,ct1):
        ct2 = ciphertext["T1"]**(lamda2)
        T = ct1*ct2
        m = (int(T)-1)/int(self.N)
        return integer(int(m))

3.测试

测试代码：

if __name__ == "__main__":
    
    dt_pkc = DTPKC()
    mk = dt_pkc.GetMK()
    print("mk is:",mk)
    pk,sk = dt_pkc.KeyGen()
    print("------------------------------")
    print("pk is:",pk,"sk is:",sk)
    plaintext = 1024
    print("------------------------")
    print("plaintext is:",plaintext)
    ciphertext = dt_pkc.Encrypt(pk,1024)
    print("------------------------")
    print("ciphertext is:",ciphertext)
    m1 = dt_pkc.Decrypt(ciphertext,sk)
    print("-------------------------")
    print("Using sk to decrypt ciphertext,result is:",m1)
    m2 = dt_pkc.DecryptMK(ciphertext,mk)
    print("-------------------------")
    print("Using mk to decrypt ciphertext,result is:",m2)

    lamda1,lamda2 = dt_pkc.SplitMK(mk)
    print("-------------------------")
    print("lamda1 is:",lamda1)
    print("lamda2 is:",lamda2)
    print("now we use lamda1 and lamda2 to decrypt:")
    ct1 = dt_pkc.PSDec1(ciphertext,lamda1)
    print("-------------------------")
    print("The middle result is:",ct1)
    print("-------------------------")
    m3 = dt_pkc.PSDec2(ciphertext,lamda2,ct1)
    print("Using lamda1 and lamda2 to decrypt ciphertext,result is:",m3)

测试结果：加解密运算正确

mk is: 22338062150910213287096358186084458203294109371215927224896109781996280749289
------------------------------
pk is: {'N': 89352248603640853148385432744337832813774312926927445628961672829724410984689, 'g': 5796069204765623542573279877045795421667308892848339471072299243822410092499008991382506301127284670227987017148628307351991077555531163469032056732101199 mod 7983824330526838791274511562029416677868477739833493115159981949744753275885355914958363600037866383924640499394589563036708131942917863905100086592426721, 'h': 7935721887038910245545505888433794372349511663547277093912096084521177913556538675688906850177251874779422538574782147394495941080326621060611267735334082 mod 7983824330526838791274511562029416677868477739833493115159981949744753275885355914958363600037866383924640499394589563036708131942917863905100086592426721} sk is: 76204058112965194407732331957567427660809926855819726246456305039472675957297 mod 89352248603640853148385432744337832813774312926927445628961672829724410984689
------------------------
plaintext is: 1024
------------------------
ciphertext is: {'T1': 1189202078396194739872313433810947540535206630405742685355335605588797450138354847755661690141041049479509074532983600670745074186493313833872690728336707 mod 7983824330526838791274511562029416677868477739833493115159981949744753275885355914958363600037866383924640499394589563036708131942917863905100086592426721, 'T2': 2031968094987867056707267176620567341361755305640188891998505629184921793767586718829208072634700218440322730486634379570080555010326243084347844702963534 mod 7983824330526838791274511562029416677868477739833493115159981949744753275885355914958363600037866383924640499394589563036708131942917863905100086592426721}
-------------------------
Using sk to decrypt ciphertext,result is: 1024
-------------------------
Using mk to decrypt ciphertext,result is: 1024
-------------------------
lamda1 is: 1505802704812095957081963280847475955421013132898588206367067311511714138058340080719320579687618270014411099365999155016669463468104328753042522940931295
lamda2 is: 260804022002047759634149184903924934389916372259491181826426268699503308739361628589967413175895360769713621921485147556575752847045942699929051799977835
now we use lamda1 and lamda2 to decrypt:
-------------------------
The middle result is: 3433002371868990949360033462226377385418613313243722104147586473147340479553469853206909391421965360453688842498974729295524950767714321345265678668705251 mod 7983824330526838791274511562029416677868477739833493115159981949744753275885355914958363600037866383924640499394589563036708131942917863905100086592426721
-------------------------
Using lamda1 and lamda2 to decrypt ciphertext,result is: 1024