最近开始调研同态加密实现的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 os


rand_bits = 128

def 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,sk


def 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_list
    

def 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_arr


def 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_list


def 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_client


def 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 list
    common_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 array

db_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