1.BCP算法簡(jiǎn)介
- BCP加密算法是由Bresson,Catalano,Pointcheval三個(gè)人于2003提出含思，發(fā)表于亞密(ASIACRYPT)喷兼。BCP加密算法是在Paillier加密算法基礎(chǔ)上進(jìn)行改進(jìn)作彤。BCP加密算法支持加同態(tài)運(yùn)算晌区，同時(shí)具有雙陷門的性質(zhì)(可以理解為明文由公鑰加密后歇式，不僅可以由私鑰解密鉴分，還可以用主密鑰解密)。相關(guān)論文：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.復(fù)現(xiàn)BCP加密算法
2.1 環(huán)境配置
- OS: Linux(Ubuntu 18.04 LTS)
- 編程語(yǔ)言：Python3.6
- 依賴包：Charm惧蛹，Charm是Joseph A. Akinyele等在2013提出的一個(gè)用于進(jìn)行快速加密的平臺(tái)(Python庫(kù))扇救。項(xiàng)目地址：https://github.com/JHUISI/charm 。Charm庫(kù)本身還需要依賴GMP,PBC和OPENSSL. 關(guān)于Charm及其依賴包的安裝可以參考文章：Charm-crypto的安裝與使用香嗓。
2.2 重要步驟說(shuō)明
- 首先需要從Charm包中導(dǎo)入相關(guān)的函數(shù)迅腔、類。
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
這些函數(shù)的作用可以根據(jù)其名字推斷靠娱，例如randomPrime是隨機(jī)找一個(gè)質(zhì)數(shù)沧烈，isPrime是判斷一個(gè)數(shù)是否為質(zhì)數(shù)，等等像云。
- 第一步：初始化锌雀，生成公共參數(shù)和系統(tǒng)主密鑰。
選擇一個(gè)安全參數(shù)迅诬，用來(lái)表示位長(zhǎng)度（一個(gè)整數(shù)轉(zhuǎn)換為二進(jìn)制后的長(zhǎng)度腋逆，稱為位長(zhǎng)度）。選取兩個(gè)安全素?cái)?shù)
侈贷，之后計(jì)算
惩歉，根據(jù)安全素?cái)?shù)的定義，
和
也都是素?cái)?shù)俏蛮。之后計(jì)算
作為模數(shù)撑蚌，使其位長(zhǎng)度為
(
表示從1到
所有與
的階(群中元素的階的概念)為
并且使得
争涌。這樣明文空間是
,公共參數(shù)
，主密鑰
辣恋。
相關(guān)代碼如下：
def __init__(self,secparam=1024,param = None):
# 安全參數(shù)secparam被設(shè)置為1024亮垫，即默認(rèn)的位長(zhǎng)度是1024
# 可以指定參數(shù)
if param:
self.N2 = param.N2
self.N = param.N
self.g = param.g
self.k = param.k
# 如果未指定參數(shù)
else:
# p,q用randomPrime()函數(shù)生成解幼，位長(zhǎng)度是512位（N=pq,要求N是1024位，則p,q為512位）
# 第二個(gè)參數(shù)設(shè)置為True包警，表示是安全素?cái)?shù)撵摆，即可以保證(p-1)/2和(q-1)/2也是素?cái)?shù)
self.p, self.q = randomPrime(int(secparam/2),True), randomPrime(int(secparam/2),True)
# pp，qq對(duì)應(yīng)p',q'
self.pp = (self.p -1)/2
self.qq = (self.q - 1)/2
# N = pq
self.N = self.p * self.q
# 下面這段while邏輯害晦，是要找一個(gè)好的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è)好的g
while True:
# 經(jīng)過(guò)下面兩步，保證g足夠隨機(jī)
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}
- 第二步：生成密鑰
根據(jù)公共參數(shù)
隨機(jī)選擇鲫剿，計(jì)算
，公鑰
私鑰
稻轨。
相關(guān)代碼：
def KeyGen(self):
tmp = self.N2 /2
sk = random(tmp) % self.N2
pk = (self.g**sk) % self.N2
return pk,sk
- 第三步：加密
明文灵莲，隨機(jī)選取
，利用公鑰
殴俱，其中
政冻，
相關(guān)代碼：
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
- 第四步：解密
當(dāng)一個(gè)明文由公鑰
明场。
相關(guān)代碼：
def Decrypt(self,ciphertext,sk):
t1 = integer(int(ciphertext['B']*((ciphertext['A']**-1)**sk)) -1) % self.N2
m = integer(t1) / self.N
return m
- 第五步：利用主密鑰解密
當(dāng)一個(gè)明文
首先計(jì)算私鑰苦锨，這里
表示
模
的逆。
之后計(jì)算加密步驟中選取的隨機(jī)數(shù)趴泌。
令表示
模
,這樣明文
。
相關(guān)代碼：
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)
- 關(guān)于解密的正確性和算法的安全性嗜憔，可以閱讀開頭提到的論文秃励。
- 完整代碼：
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.測(cè)試
- 測(cè)試代碼
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)
- 結(jié)果：滿足正常加解密運(yùn)算
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
