基于RSA隐私求交（PSI）的python 实现

最近开始调研同态加密实现的PSI，回顾了一下基于RSA的PSI方式，见文章

https://eprint.iacr.org/2009/491.pdfzzi

按自己的理解实现了一个python的RSA隐私求交的流程

流程基本按下图实现：

 为了理解中间“盲化”和哈希的过程，所以没有用现成的RSA加解密方案 而是用gmpy2 库的加速模幂计算方法做了 加解密操作。

from Cryptodome.PublicKey import RSA
import hashlib
import binascii 
import gmpy2
import osrand_bits = 128def hash_bignumber(num,method='sha1'):'''num: an integer '''if method == 'sha1':hash_obj = hashlib.sha1(str(num).encode('utf-8'))digest_hex = hash_obj.hexdigest()return int(digest_hex,16)def gen_key():key = RSA.generate(1024)pk = (key.n,key.e)sk = (key.n,key.d)return pk,skdef blind_msg_arr_use_pk(msg_arr, pk):msg_hash_number_blind = []rand_private_list = [] for item in msg_arr:hash_num = hash_bignumber(item)hash_num = hash_num % pk[0]ra = int(binascii.hexlify(os.urandom(rand_bits)),16)cipher_ra = gmpy2.powmod(ra,pk[1],pk[0])rand_private_list.append(ra)msg_hash_number_blind.append(hash_num*cipher_ra)return msg_hash_number_blind, rand_private_listdef deblind_arr_from_client(hash_arr_blind,sk):deblind_hash_arr = []for item in hash_arr_blind:de_blind_number = gmpy2.powmod(item,sk[1],sk[0])deblind_hash_arr.append(de_blind_number)return deblind_hash_arrdef enc_and_hash_serverlist(server_list,sk):hash_server_list = []for item in server_list:hash_num = hash_bignumber(item)c_hash_num = gmpy2.powmod(hash_num,sk[1],sk[0])hash_server_list.append(hash_bignumber(c_hash_num))return hash_server_listdef hash_deblind_client_arr(deblind_hash_arr, rand_list, pk):db_client = []for item,ra in zip(deblind_hash_arr,rand_list):ra_inv = gmpy2.invert(ra,pk[0]) # ra*ra_inv == 1 mod n db_client.append(hash_bignumber((item * ra_inv) % pk[0]))return db_clientdef get_common_elements_idx(db_client,db_server):# search out the common elements in O(n^2) complexity# return the common elements index in local data listcommon_set_index = []for idx in range(len(db_client)):rec_a = db_client[idx]for rec_b in db_server:if rec_a == rec_b:common_set_index.append(idx)return common_set_index# Server side:
# RSA key generation and send pk to client
pk,sk = gen_key()# Client side blind the local array and send to server 
msg_arr_client = [12,3,4,8,10,23]  
blind_arr, rlist = blind_msg_arr_use_pk(msg_arr_client,pk)# Server side 
# receive the blind arr from client and deblind them with secret key
received_blind_arr = blind_arr.copy()
deblind_hash_arr = deblind_arr_from_client(received_blind_arr,sk)server_list = [12,3,4,5,1,32,45] #12,3,4,8,10,23
# encrypt and hash the server list 
hashed_server_list = enc_and_hash_serverlist(server_list,sk)
# send the deblind array and hashed list to client# Client side
# Receive the deblind array and hashed server list
received_deblind_hash_arr = deblind_hash_arr.copy()
db_server = hashed_server_list.copy()# hash the dblind arraydb_client = hash_deblind_client_arr(received_deblind_hash_arr,rlist,pk)
common_index_local_list = get_common_elements_idx(db_client,db_server)print('The hash of db Client:', db_client)
print('The hash of db Server:', db_server)for idx, true_id in zip(common_index_local_list,[0,1,2]):assert idx == true_id