1.BCP算法简介
- BCP加密算法是由Bresson,Catalano,Pointcheval三个人于2003提出，发表于亚密(ASIACRYPT)。BCP加密算法是在Paillier加密算法基础上进行改进。BCP加密算法支持加同态运算，同时具有双陷门的性质(可以理解为明文由公钥加密后，不仅可以由私钥解密，还可以用主密钥解密)。相关论文：Bresson E, Catalano D, Pointcheval D. A Simple Public-Key Cryptosystem with a Double Trapdoor Decryption Mechanism and Its Applications.[C]// International Conference on Advances in Cryptology-asiacrypt. 2003.
2.复现BCP加密算法
2.1 环境配置
- OS: Linux(Ubuntu 18.04 LTS)
- 编程语言：Python3.6
- 依赖包：Charm，Charm是Joseph A. Akinyele等在2013提出的一个用于进行快速加密的平台(Python库)。项目地址：https://github.com/JHUISI/charm 。Charm库本身还需要依赖GMP,PBC和OPENSSL. 关于Charm及其依赖包的安装可以参考文章：Charm-crypto的安装与使用。
2.2 重要步骤说明
- 首先需要从Charm包中导入相关的函数、类。
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
这些函数的作用可以根据其名字推断，例如randomPrime是随机找一个质数，isPrime是判断一个数是否为质数，等等。
- 第一步：初始化，生成公共参数和系统主密钥。
选择一个安全参数，用来表示位长度（一个整数转换为二进制后的长度，称为位长度）。选取两个安全素数
，之后计算
，根据安全素数的定义，
和
也都是素数。之后计算
作为模数，使其位长度为
(
表示从1到
所有与
的阶(群中元素的阶的概念)为
并且使得
。这样明文空间是
,公共参数
，主密钥
。
相关代码如下：
def __init__(self,secparam=1024,param = None):
# 安全参数secparam被设置为1024，即默认的位长度是1024
# 可以指定参数
if param:
self.N2 = param.N2
self.N = param.N
self.g = param.g
self.k = param.k
# 如果未指定参数
else:
# p,q用randomPrime()函数生成，位长度是512位（N=pq,要求N是1024位，则p,q为512位）
# 第二个参数设置为True，表示是安全素数，即可以保证(p-1)/2和(q-1)/2也是素数
self.p, self.q = randomPrime(int(secparam/2),True), randomPrime(int(secparam/2),True)
# pp，qq对应p',q'
self.pp = (self.p -1)/2
self.qq = (self.q - 1)/2
# N = pq
self.N = self.p * self.q
# 下面这段while逻辑，是要找一个好的N
while True:
if bitsize(self.N) ==secparam and len(int2Bytes(self.N)) == int(secparam/8) and int2Bytes(self.N)[0] &128 !=0:
break
self.p, self.q = randomPrime(int(secparam/2),True), randomPrime(int(secparam/2),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.g = random(self.N2)
one = integer(1)% self.N2
# 下面这段逻辑，是找到一个好的g
while True:
# 经过下面两步，保证g足够随机
self.g = random(self.N2)
self.g = integer((int(self.g)-1)*(int(self.g)-1))% self.N2
# 保证g的阶不是0
if self.g == one:
continue
# 保证g的阶不是p
tmp = self.g**self.p %self.N2
if tmp == one:
continue
# 保证g的阶不是p'
tmp = self.g**self.pp % self.N2
if tmp == one:
continue
# 保证g的阶不是q
tmp = self.g**self.q %self.N2
if tmp == one:
continue
# 保证g的阶不是q'
tmp = self.g**self.qq %self.N2
if tmp == one:
continue
# 保证g的阶不是pp'
tmp =self.g**(self.p*self.pp) % self.N2
if tmp == one:
continue
# 保证g的阶不是pq
tmp = self.g**(self.p*self.q) %self. N2
if tmp== one:
continue
# 保证g的阶不是pq'
tmp = self.g**(self.p*self.qq) % self.N2
if tmp == one:
continue
# 保证g的阶不是p'q
tmp = self.g**(self.pp*self.q) % self.N2
if tmp == one:
continue
# 保证g的阶不是p'q'
tmp = self.g**(self.pp*self.qq) % self.N2
if tmp == one:
continue
# 保证g的阶不是qq'
tmp = self.g**(self.q*self.qq) % self.N2
if tmp == one:
continue
# 保证g的阶不是pp'q
tmp = self.g**(self.p*self.pp*self.q) % self.N2
if tmp == one:
continue
# 保证g的阶不是pp'q'
tmp =self.g**(self.p*self.pp*self.qq) % self.N2
if tmp == one:
continue
# 保证g的阶不是pqq'
tmp =self.g**(self.p*self.q*self.qq) % self.N2
if tmp == one:
continue
# 保证g的阶不是p'qq'
tmp =self.g**(self.pp*self.q*self.qq) % self.N2
if tmp == one:
continue
break
# 求得k
self.k = integer((int(self.g**(self.pp*self.qq)) - 1)) / self.N % self.N
# 获得主密钥
self.MK ={"pp":self.pp,"qq":self.qq}
- 第二步：生成密钥
根据公共参数
随机选择，计算
，公钥
私钥
。
相关代码：
def KeyGen(self):
tmp = self.N2 /2
sk = random(tmp) % self.N2
pk = (self.g**sk) % self.N2
return pk,sk
- 第三步：加密
明文，随机选取
，利用公钥
，其中
，
相关代码：
def Encrypt(self,pk,plaintext):
r = random(self.N/4) % self.N2
A = (self.g** r ) % self.N2
B1 = (self.N*plaintext+1)% (self.N2)
B2 = (pk**r) % (self.N2)
B = B1*B2 % self.N2
ciphertext = {"A":A,"B":B}
return ciphertext
- 第四步：解密
当一个明文由公钥
。
相关代码：
def Decrypt(self,ciphertext,sk):
t1 = integer(int(ciphertext['B']*((ciphertext['A']**-1)**sk)) -1) % self.N2
m = integer(t1) / self.N
return m
- 第五步：利用主密钥解密
当一个明文
首先计算私钥，这里
表示
模
的逆。
之后计算加密步骤中选取的随机数。
令表示
模
,这样明文
。
相关代码：
def DecryptMK(self,ciphertext,MK,pk):
k_1 = self.k ** -1
tmp = (int(pk**(MK['pp']*MK['qq'])) -1) % self.N2
tmp = integer(tmp) /self.N
a = tmp * integer(k_1) % self.N
tmp = (int(ciphertext['A'] **(MK['pp']*MK['qq'])) -1) % self.N2
tmp = integer(tmp) /self.N
r = tmp * integer(k_1) % self.N
gama = a*r %self.N
sig = ((MK['pp']*MK['qq'])%self.N) **-1
tmp = (self.g **-1)**gama
tmp = ciphertext['B'] *tmp
tmp = (int(tmp**(MK['pp']*MK['qq'])) -1)% self.N2
tmp = integer(tmp) /self.N
m = integer(tmp) * integer(sig) %self.N
return integer(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 Param():
def __init__(self):
pass
def setParam(self,N2,N,g,k):
self.N2 = N2
self.N = N
self.g = g
self.k = k
class BCP():
def __init__(self,secparam=1024,param = None):
if param:
self.N2 = param.N2
self.N = param.N
self.g = param.g
self.k = param.k
else:
self.p, self.q = randomPrime(int(secparam/2),True), randomPrime(int(secparam/2),True)
self.pp = (self.p -1)/2
self.qq = (self.q - 1)/2
self.N = self.p * self.q
while True:
if bitsize(self.N) ==secparam and len(int2Bytes(self.N)) == int(secparam/8) and int2Bytes(self.N)[0] &128 !=0:
break
self.p, self.q = randomPrime(int(secparam/2),True), randomPrime(int(secparam/2),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.g = random(self.N2)
one = integer(1)% self.N2
while True: #choose a good g
self.g = random(self.N2)
self.g = integer((int(self.g)-1)*(int(self.g)-1))% self.N2
if self.g == one:
continue
tmp = self.g**self.p %self.N2
if tmp == one:
continue
tmp = self.g**self.pp % self.N2
if tmp == one:
continue
tmp = self.g**self.q %self.N2
if tmp == one:
continue
tmp = self.g**self.qq %self.N2
if tmp == one:
continue
tmp =self.g**(self.p*self.pp) % self.N2
if tmp == one:
continue
tmp = self.g**(self.p*self.q) %self. N2
if tmp== one:
continue
tmp = self.g**(self.p*self.qq) % self.N2
if tmp == one:
continue
tmp = self.g**(self.pp*self.q) % self.N2
if tmp == one:
continue
tmp = self.g**(self.pp*self.qq) % self.N2
if tmp == one:
continue
tmp = self.g**(self.q*self.qq) % self.N2
if tmp == one:
continue
tmp = self.g**(self.q*self.qq) % self.N2
if tmp == one:
continue
tmp = self.g**(self.p*self.pp*self.q) % self.N2
if tmp == one:
continue
tmp =self.g**(self.p*self.pp*self.qq) % self.N2
if tmp == one:
continue
tmp =self.g**(self.p*self.q*self.qq) % self.N2
if tmp == one:
continue
tmp =self.g**(self.pp*self.q*self.qq) % self.N2
if tmp == one:
continue
break
self.k = integer((int(self.g**(self.pp*self.qq)) - 1)) / self.N % self.N
self.MK ={"pp":self.pp,"qq":self.qq}
def GetMK(self):
return self.MK
def GetParam(self):
param = Param()
param.setParam(self.N2, self.N, self.g, self.k)
return param
def KeyGen(self):
tmp = self.N2 /2
sk = random(tmp) % self.N2
pk = (self.g**sk) % self.N2
return pk,sk
def Encrypt(self,pk,plaintext):
r = random(self.N/4) % self.N2
A = (self.g** r ) % self.N2
B1 = (self.N*plaintext+1)% (self.N2)
B2 = (pk**r) % (self.N2)
B = B1*B2 % self.N2
ciphertext = {"A":A,"B":B}
return ciphertext
def Decrypt(self,ciphertext,sk):
t1 = integer(int(ciphertext['B']*((ciphertext['A']**-1)**sk)) -1) % self.N2
m = integer(t1) / self.N
return m
def DecryptMK(self,ciphertext,MK,pk):
k_1 = self.k ** -1
tmp = (int(pk**(MK['pp']*MK['qq'])) -1) % self.N2
tmp = integer(tmp) /self.N
a = tmp * integer(k_1) % self.N
tmp = (int(ciphertext['A'] **(MK['pp']*MK['qq'])) -1) % self.N2
tmp = integer(tmp) /self.N
r = tmp * integer(k_1) % self.N
gama = a*r %self.N
sig = ((MK['pp']*MK['qq'])%self.N) **-1
tmp = (self.g **-1)**gama
tmp = ciphertext['B'] *tmp
tmp = (int(tmp**(MK['pp']*MK['qq'])) -1)% self.N2
tmp = integer(tmp) /self.N
m = integer(tmp) * integer(sig) %self.N
return integer(m)
def multiply(self,ciphertext1,ciphertext2):
ciphertext={}
ciphertext['A'] = ciphertext1['A'] * ciphertext2['A']
ciphertext['B'] = ciphertext1['B'] * ciphertext2['B']
return ciphertext
def exponentiate(self,ciphertext,m):
text={}
text['A'] = ciphertext['A'] **m % self.N2
text['B'] = ciphertext['B'] **m % self.N2
return text
3.测试
- 测试代码
if __name__ == "__main__":
bcp = BCP()
mk = bcp.GetMK()
print("mk is:",mk)
pk,sk = bcp.KeyGen()
print("------------------------")
print("pk is:",pk,"sk is:",sk)
plaintext = 1024
print("------------------------")
print("plaintext is:",plaintext)
ciphertext = bcp.Encrypt(pk,plaintext)
print("-------------------------")
print("ciphertext is:",ciphertext)
m1 = bcp.Decrypt(ciphertext,sk)
print("-------------------------")
print("Using sk to decrypt ciphertext,result is:",m1)
m2 = bcp.DecryptMK(ciphertext,mk,pk)
print("-------------------------")
print("Using mk to decrypt ciphertext,result is:",m2)
- 结果：满足正常加解密运算
mk is: {'pp': 8085308361220211021, 'qq': 8074162483544779991}
------------------------
pk is: 2327067015883561054197990332426819861947346756531764313703384468027403763054 mod 68188027578479421068471198257847466460478763055291934213409505489802965962361 sk is: 57367126269859549947589515646769721080756993424096049630783473449899601736315 mod 68188027578479421068471198257847466460478763055291934213409505489802965962361
------------------------
plaintext is: 1024
-------------------------
ciphertext is: {'A': 938193878176646758481378597525256135099055012583309087654629417103271925777 mod 68188027578479421068471198257847466460478763055291934213409505489802965962361, 'B': 65213284378251907450069755084784844288839906212981359092246031298436351553270 mod 68188027578479421068471198257847466460478763055291934213409505489802965962361}
-------------------------
Using sk to decrypt ciphertext,result is: 1024
-------------------------
Using mk to decrypt ciphertext,result is: 1024
