密码学——保序加密算法（OPE算法-2009年提出）通俗易懂解析（小学生都能懂！）含python代码

保序加密算法（OPE算法-2009年提出）通俗易懂解析（小学生都能懂！）一、预备知识保序加密算法：最初是由2009年，Boldyreva等四个人提出来的，可简称BCLO-09算法，论文题目为。。。。。。。，请自行搜索并下载，本文直接让你读懂该论文的核心算法。算法目的：简单来说就是本来有顺序的明文，加密之后依然保持顺序，但是除此之外不知道任何信息。简单来说，我要加密2,5,8三个数字，我把它们分别换

料理码王

13030人浏览 · 2020-12-17 22:52:20

料理码王 · 2020-12-17 22:52:20 发布

一、预备知识

保序加密算法：最初是由2009年，Boldyreva等四个人提出来的，可简称BCLO-09算法，论文题目为《Order-Preserving Symmetric Encryption》，请自行搜索并下载，本文直接让你读懂该论文的核心算法。
算法目的：简单来说就是本来有顺序的明文，加密之后依然保持顺序，但是除此之外不知道任何信息。简单来说，我要加密2,5,8三个数字，我把它们分别换成45，4424,22224，这样就保证了别人不知道我原来的数字，但是又保持了原来的顺序，但是我们必须保证能把后面三个数字复原回去才行（解密），BCLO-09算法就做了这项工作。这项工作的难度在于如何能复原，又能保证复原的复杂性，不易于被破解。
超几何分布（也就是下面论文算法图里面的HGD这个函数）：

小括号的意思是组合数，上面的 $(\begin{matrix} y\\x\end{matrix})$ 也就是 $C^x_y$ 。我解释一下这个公式的意思，只需要记住这个公式的意思就行：一个框里面有N个球，其中黑球M个，白球N-M个，从这个框里面拿起来y个球，数一下我拿起了多少个黑球，记为x。x就是这个函数要返回的一个值。接下来我们继续看看论文作者怎么用这个超几何分布进行抽样（用这个x）。

二、算法讲解

在这里插入图片描述

举个栗子~我要把[1, 100]这个区间的整数映射到[1, 1000]中，我们采用上述方法映射一个数字，我们先选择25进行映射。
我们直接看第十行：x = HGD（M，N，y），它的意思是：我们从一个框里面抽球，里面黑球有M个（就是明文域的大小100），白球有N个（就是密文域的大小1000），我抽了y个球（就是密文域大小的一半500），这个函数可以给我返回我抽了多少个黑球，也就是数值x（这个值必然是0-100之间的数，因为我从1100个球里面抽，可能抽不到黑球，也可能抽到所有的黑球）。
接下来，阐述具体的超几何采样的步骤：

第一步：假设我采样到了44这个数，因为大于25，所以重新调整明文域和密文域分别为[1, 44]，[1, 500]；反之，如果我抽到的数小于25，假设是11，那么分别调整为[11, 100]，[500，1000]。
第二步：调整后，继续进行上述抽球活动。就这样反复抽几轮，一定能抽到明文域里的25，密文域也在一半一半的切，至于切左区间还是右区间，要看每次抽样抽到的x与25的大小关系，最后从区间[283, 298]的区间中随机取一个数作为25的密文。注意！不仅要抽样，还要把每次抽样结果记录在key_table这张表里面！
第三步：下面我们加密明文域里面的26，我们查看key_table这张表发现，一直到原来的第⑥步，抽样的过程都可以省略，直接把之前抽到的x拿来用完全合理，但是第⑥步由于26>25，所以我要取第⑥步密文域的右半部分才合理即[299, 313]，然后剩下26与27，26就是值在左边，所以再取左区间[299, 306]。再从最后这个左区间随机取一个数作为26的密文。
第四步：解密的步骤就是一个反向查表的过程。不赘述。

三、思考

我们通过25和26的加密可以发现：在最后随机取数的两个区间中，无论取得什么值，最后的密文必然和原来的明文所反映的大小是相同的，即（25<26）=（25对应的密文<26对应的密文）
安全的地方在于：首先是抽样的随机性，但是抽取的时候由控制好了区间，保证了抽取的数必然在符合大小条件的区间中；然后就是对key_table这张表的保密，加密者不可以泄露这张表！
值得思考的是，论文作者用这种方法，保证了原来的数字加密后顺序依然不变，并且还能还原回原来的数字。然而敌手得到密文后完全不可能（有抽样的过程）知道原来的数字，除了原来数字的大小顺序（所以叫保序加密）。

四、代码

1 超几何分布python代码

超几何分布(hypergeometric):
        ----numpy中实现：
            np.random.hypergeometric(ngood,nbad,nsample,size)-->产生size个随机数，每个随机数为在总样本中随机抽取
            nsample个样本后好样本的个数。所有样本由ngood个好样本和nbad个坏样本组成。
 
import numpy as np

# 超几何分布,7个好的3个坏的，摸3个，重复10次，返回好球的个数组成的数组
r = np.random.hypergeometric(7, 3, 3, 10)
print(r)

运行结果：
[2 1 3 3 2 2 3 3 2 2]

2 BCLO-09算法代码

新建一个BCLO09.csv文件，存放密钥表格

（注意：一定要先创建一个记事本文件，然后修改文件名为BCLO09.csv，否则会报编码错误！）

再创建一个BCLO09.py文件

import csv
import random

import numpy as np
import pymysql

key_table = "BCLO09.csv"
def HGD(D, R):
    len_D = len(D)
    len_R = len(R)
    y = int(len_R / 2)
    x = np.random.hypergeometric(len_D, len_R, y, size=1)
    a = x[0]
    if x[0] >= len_D:
        a = len_D - 1
    return D[a]

def writeCsv(path, data, modle): #传入变量csv文件的路径和要写入的数据
    with open(path,modle,newline="") as f: # 以写入的方式打开文件，newline="" 可以让数据不隔行写入
        writer_csv=csv.writer(f) #调用csv的writer方法往文件里面写入数据，并赋值给writer_scv变量
        writer_csv.writerow(data) #把数据循环写入到writer_csv变量中

#读取csv文件
def readCsv(path): #传入变量csv文件的路径
    list_one=[]    #定义一个空列表
    with open(path,"r") as f: #以只读的方式打开文件
        read_scv=csv.reader(f) #调用csv的reader方法读取文件并赋值给read_scv变量
        for i in read_scv:
            list_one.append(i) #将读取到的数据追加到list列表里面
    return list_one #返回列表数据


def key_tableIsContain(param):
    list_one = readCsv(key_table)
    if len(list_one) == 0:
        return 0, 0
    flag = 0
    for i in range(len(list_one)):
        if str(int(param)) == list_one[i][0]:
            flag = 1
            return 1, int(list_one[i][1])
    if flag != 1:
        return 0, 0



def Enc2(key_table, D, R, m):
    _D = D
    _R = R
    M = max(D) - min(D) + 1
    N = max(R) - min(R) + 1
    center = int((max(R) + min(R)) / 2)
    iscontain, values = key_tableIsContain(center)
    if iscontain == 1:
        c = values #记录D中的抽样值
        x = values
    else:
        x = HGD(D, R)
        a = []
        a.append(center)
        a.append(x)
        writeCsv(key_table, a ,"a")
    print("区间是D[%d, %d]" % (min(_D), max(_D)))
    print("区间是R[%d, %d]" % (min(_R), max(_R)))
    if M == 1:
        print(m)
        print("区间是R[%d, %d]" % (min(_R), max(_R)))
        # return random.randint(min(R), max(R))
        return str(m) + " " + str(min(R)) + " " + str(max(R))

    if M == 2:
        print(m)
        if min(D) == m:
            print("最后的区间是R(%d, %d]" % (min(_R), center))
            return str(m) + " " + str(min(R)) + " " + str(center)
        else:
            print("最后的区间是R(%d, %d]\n" % (center, max(_R)))
            return str(m) + " " + str(center) + " " + str(max(R))

        # return random.randint(min(R), max(R))



    if m <= x: #左边
        D = []
        for i in range(min(_D), x + 1):
            D.append(i)
        R = []
        for j in range(min(_R), center + 1):
            R.append(j)
    else:  #右边
        D = []
        for i in range(x + 1, max(_D) + 1):
            D.append(i)
        R = []
        for j in range(center + 1, max(_R) + 1):
            R.append(j)
    print("D[%d, %d] 抽样值:%d"%(min(_D), max(_D), x))
    print("R[%d, %d] 中间值:%d \n" % (min(_R), max(_R), center))
    return Enc2(key_table, D, R, m)


def Dnc2(key_table, D, R, m):
    _D = D
    _R = R
    M = max(D) - min(D) + 1
    N = max(R) - min(R) + 1
    center = int((max(R) + min(R)) / 2)
    print("区间是D[%d, %d]" % (min(_D), max(_D)))
    print("区间是R[%d, %d]" % (min(_R), max(_R)))
    if M == 1:
        print(m)
        print("明文是：%d\n区间是R[%d, %d]" % (min(D), min(_R), max(_R)))
        return random.randint(min(R), max(R))
    if M == 2:
        if m <= center:
            print("明文是：%d\n最后的区间是R(%d, %d]" % (min(D), min(_R), center))
        else:
            print("明文是：%d\n最后的区间是R[%d, %d)\n" % (max(D), center, max(_R)))

        return random.randint(min(R), max(R))
    iscontain, values = key_tableIsContain(center)
    if iscontain == 1:
        c = values  # 记录D中的抽样值
        x = values
    else:
        print("可能解密错误！")
        return
        x = HGD(D, R)
        a = []
        a.append(center)
        a.append(x)
        # writeCsv(key_table, a, "a")

    if m <= center:  # 左边
        D = []
        for i in range(min(_D), x + 1):
            D.append(i)
        R = []
        for j in range(min(_R), center + 1):
            R.append(j)
    else:  # 右边
        D = []
        for i in range(x + 1, max(_D) + 1):
            D.append(i)
        R = []
        for j in range(center + 1, max(_R) + 1):
            R.append(j)
    return Dnc2(key_table, D, R, m)



if __name__ == '__main__':
	# searchContentList = searchContent()
    # print(searchContentList)
    # Back()

    while (1):
        print("=================\n"
              "\t1、加密\n"
              "\t2、解密\n"
              "\t3、循环加密\n"
              "\t4、退出加密程序\n"
              "=================")
        flag = input("请输入你要操作的编号：")
        if flag == "4":
            break 
        if flag == "1":
            D = []
            for i in range(100):
                D.append(i + 1)
            R = []
            for i in range(1000):
                R.append(i + 1)
            m = input("请输入你要加密的数字：")
            Enc2(key_table, D, R, int(m))
        if flag == "2":
            D = []
            for i in range(100):
                D.append(i + 1)
            R = []
            for i in range(1000):
                R.append(i + 1)
            m = input("请输入你要解密的数字：")
            Dnc2(key_table, D, R, int(m))
        if flag == "3":
            D = []
            result = []
            for i in range(100):
                D.append(i + 1)
            R = []
            for i in range(1000):
                R.append(i + 1)
            for i in range(100):
                result.append(Enc2(key_table, D, R, int(i + 1)))
            for c in range(len(result)):
                print(result[c])