密码分析学-Enigma机破解-Toy模板网

这篇具有很好参考价值的文章主要介绍了密码分析学-Enigma机破解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

密码分析学

Enigma机破解

作业要求

（1）给定明文HELLOWORLD，按照以下给定参数，编程实现Enigma机的加密，并输出对应的密文。

接线板（6条连线）K1：

S = [1, 0, 2, 4, 3, 5, 13, 7, 8, 9, 24, 11, 20, 6, 14, 15, 16, 17, 22, 19, 12, 21, 18, 23, 10, 25]

即a与b相连，d与e相连，g与n相连，k与y相连，m与u相连，s与w相连
扰频器组合（固定3个转子，无需从5个中选择3个）

快速转子QUICK = [0, 18, 24, 10, 12, 20, 8, 6, 14, 2, 11, 15, 22, 3, 25, 7, 17, 13, 1, 5, 23, 9, 16, 21, 19, 4]

即快速转子的表格中左侧一列为0，1，2，…，25，右侧一列0，18，24，…，4；下同

中速转子MID = [0, 10, 4, 2, 8, 1, 18, 20, 22, 19, 13, 6, 17, 5, 9, 3, 24, 14, 12, 25, 21, 11, 7, 16, 15, 23]

慢速转子SLOW = [24, 22, 7, 10, 12, 19, 23, 0, 14, 6, 9, 15, 8, 25, 20, 17, 3, 1, 18, 4, 21, 5, 11, 13, 16, 2]

各转子起始点K2：(4, 4, 16)
反射器

T = [10, 20, 14, 8, 25, 15, 16, 21, 3, 18, 0, 23, 13, 12, 2, 5, 6, 19, 9, 17, 1, 7, 24, 11, 22, 4]

即a与k相连，b与u相连，……

（2）给定如下明密文数据流，1）中的快中慢三个转子和反射器的定义不变，尝试恢复密钥K1和K2。

明文：…HELLOWORLD…

密文：…WELLDONEEFGHIJ…

摘要

加密结果：
$Enc_{K1,K2}("HELLOWORLD") ="MUCDUGWPXB"$
破解结果：

不考虑未知的字母，未知的字母全部当做没有接线，一共有38个解。python运行时间：8.356976747512817s

格式：[K2, K1]

[[2,14,8],  [0,1,2,13,25,18,19,20,17,9,11,10,12,3,14,15,16,8,5,6,7,21,24,23,22,4]] 
[[2,14,8],  [0,1,2,13,25,23,19,20,8,9,11,10,17,3,14,15,16,12,18,6,7,21,24,5,22,4]] 
[[2,14,8],  [0,1,5,13,25,2,19,20,8,9,11,10,12,3,14,15,16,17,18,6,7,21,24,23,22,4]] 
[[2,14,8],  [0,1,2,13,25,8,19,20,5,9,11,10,12,3,14,15,16,18,17,6,7,21,24,23,22,4]] 
[[2,14,8],  [0,1,2,13,25,12,19,20,8,9,11,10,5,3,14,15,16,23,18,6,7,21,24,17,22,4]] 

此处省略部分，太长了..

[[24,17,3], [0,1,2,3,4,20,24,12,8,17,10,21,7,18,19,22,16,9,13,14,5,11,15,23,6,25]]
[[24,17,3], [0,1,2,3,4,9,24,12,8,5,10,21,7,18,19,22,16,20,13,14,17,11,15,23,6,25]]
[[24,17,3], [5,1,2,3,4,0,24,12,8,9,10,21,7,18,19,22,16,23,13,14,20,11,15,17,6,25]]
[[25,10,6], [0,4,3,2,1,13,8,23,6,9,22,19,12,5,24,15,16,18,17,11,20,21,10,7,14,25]]

正文

一：Enigma机加密

1.1 背景

Enigma密码机在1920年代早期开始被用于商业，也被一些国家的军队与政府采用过，在这些国家中，最著名的是第二次世界大战时的纳粹德国。Enigma密码机的大部分设置都会在一段时间（一般为一天）以后被更换。1932年，波兰密码学家马里安·雷耶夫斯基，杰尔兹·罗佐基和亨里克·佐加尔斯基破译了德军的Enigma机，但随后德军对Enigma机进行了改进。波兰战败后，将研究成果分享给英法，随后英国的图灵和其他专家共同破译了Enigma机。

1.2 加密原理

Enigma密码机的构造

共由五个主要部件组成。分别是：

包含26个英文字母的键盘： 输入端，每次输入一个英文字母。
线路接线板： 将l对字母相连接，进行加密工作。
扰频组合： 由快速扰频器、中速扰频器、慢速扰频器组成，进行加密工作。
反射器： 保证加密后得到的字母与输入的字母一定不相同。
包含26个英文字母的显示灯的显示灯板： 输出端，在键盘上输入一个英文字母后，灯盘上都会有一个英文字母亮起来，代表明文字母加密后的所对应的密文字母。

Enigma密码机的加密原理
Enigma密码机加密是一种多表代换的对称加密算法，逐字母加密。除此之外，Enigma密码机是对称加密，加解密过程一致，不论加密还是解密，

明文空间： $P\in \mathbb{\{A\}^n}$ ， $\mathbb{A}$ 表示字母表 ${A-Z\}$

密文空间： $C\in \mathbb{\{A\}^n}$

秘钥： $K 1 ， K 2$ ，分别表示接线板和三个转子的初始位置

加解密算法：

设置好 $K 1$ 和 $K 2$ 后，明文 $P$ 经过：

① 标有26个英文字母的线路接线板（ $S$ ）

②扰频组合（ $R$ ）

③反射器（ $T$ ）

④扰频组合（ $R^{-1}$ ）

⑤标有26个英文字母的线路接线板( $S$ )

得到密文 $C$ ，解密同理。因为加解密算法一致，所以此处不作区分。
$C =Enc_{K1,K2}(P)\\ P = Enc_{K1,K2}(C)$
扰频器的作用

扰频器也称作转子。单个转子的加密是一种单表置换。转子的左右两侧各有26个点，分别代表A-Z这26个英文字母。一端输入一端输出。为了达到加密的目的，将左右两侧的字母交叉连接，例如：转子左侧的字母A并不与转子右侧的A相连，而是与字母E相连，即表示字母A经过扰频器的加密后变成了字母E。

因为这种单个转子提供的密码表是固定不变的，加密出来的密文比较容易被破解,因此选择三个转子串联在一起从而达到加密的目的。
三个转子被串联后，输入的字母经过这三个转子被进行多次替换。如果转子不转，那么输入的字母不论经过几个串联的转子，最终得到的依旧是一个固定的密码表，安全性依旧不高。因此为了提高加密的安全性，每输入一个字母后，第一个转子就会自动转动一格。当第一个转子转动一圈后，第二个转子就转动一格。同理，第二个转子转动一圈后，第三个转子转动一格。这样原来的单表置换经过旋转变为多表置换，使得安全性更高。

根据 $Kerc kh o ff s$ 假设，加密算法的内部结构是公开的，也就是说转子的内部结构对于加解密双方来说是一致的。秘钥 $K 2$ 包含的是转子的排列方式和初始位置，如果有n个转子，选用m个进行加密，秘钥空间为
$K2| = A_n^m*26^3$
对于只有三个转子的Enigma机，密钥空间只有 $3!*26^3=105456$ ，这种级别的安全性是不够的，这时候接线板 $K 1$ 就起了关键作用。我们会在安全性分析中做解释。

反射器作用

反射器的加密是一种固定的单表置换（这里的单表置换是自定义的，无密钥）。加密方式是将最后一个转子的其中两个触点连接起来，并将电流沿一个不同的路倒回到线路接线板。这样的反射器导致加密后的字母与输入字母一定不相同，并且使得Enigma密码机的加密过程是自反的，这也是加解密一致的关键部件。同时还让Enigma机有了另一个性质，即：一个字母不会加密成自身。这也是后面破解的关键。

计算只用3个转子,接线板有6个连接线的enigma的密钥空间有多大,密码学作业,安全

1.3 安全性分析

我们说过，Enigma机的本质是一种多表替换，我们之前学习过的凯撒密码和维吉尼亚密码也是替换密码，但后两种密码我们知道会有字母频率的漏洞。主要因为他们的加密都是使用的同一张密码表，而Enigma机每加密一个字母，就会转动一下，相当于换了一张密码表，基本可以做到加密一个字母就更换一次密码表并且不重复。

没有了字母频率攻击的“后顾之忧”，那我们再考虑暴力破解：

我们在前面讨论过对于3个转子的Enigma机，他的转子排列和初始位置的组合 $K 2$ 只有105456大小。这显然不够，我们来考虑接线板（ $K 1$ ）的作用。26个字母，有 $t$ 根连线，那么就有
$\frac{26!}{(26-t)!*t!*2^t}$
种接线方式，如果有6根接线， $t = 6$ ，那么K1就有
$|K1|=\frac{26!}{(26-6)!*6!*2^6} = 70,605,879,373,725,696,000\approx 7*10^{20}$
总密钥空间大小：
$|K1|*|K2|=A_5^3*26^3*\frac{26!}{(26-6)!*6!*2^6}=4,236,352,762,423,541,760,000\approx 4*10^{22}$
可以看到接线板对整体密钥空间的扩大起重要作用。二战时期没有高速计算机，通过人工穷举密钥，对于这种数量级的密钥空间是不现实的。即使是使用计算机进行穷举，大部分电脑的单秒运算量在10的七次方到10的九次方之间，我们假设每秒穷举 $10^9$ 个密钥为例，筛选出正确密钥的期望时间约为 $400000$ 年。

除此之外，德军在使用Enigma机时还规定了一定的操作流程，他们在通信时，会先使用日秘钥加密一个会话秘钥，然后使用会话秘钥来加密明文。会话秘钥也是三个字母，德军先使用日秘钥加密会话秘钥两次，然后将这6个字母发送出去。比如日秘钥ABC，会话秘钥QWE，那么 $QWEQWE\stackrel{ABC}{\longrightarrow}DCYXEV$ ，加密两边是为了防止出现错误。德军本意是为了保证每条信息都是用不同的密钥进行加密的，避免了使用同一个密钥加密过多内容而被破解者找到破绽。但是波兰人便是从这六个字母中找到了规律，实现了的初步的破解。但波兰的破解是不具有普遍性的，德军改进Enigma机和操作流程后便失效了。

1.4 加密算法实现

这里我们用一个具体的字母举例，待加密字符为 ‘H’，K1,K2为题目所给，看一下加密算法的具体实现过程：

计算只用3个转子,接线板有6个连接线的enigma的密钥空间有多大,密码学作业,安全

接线板K1

在键盘上输入字母H（7），H首先经过接线板（Stecker），发现H没有与其它字母相连，所以经过接线板后明文没有发生变化，仍为H（7）。

正向扰频器组合（Rotors）

首先通过密钥K2（4,4,16）将转子转动到相应位置。再将H（7）分别通过这三个转子。

H对应位置为7，将7作为输入通过快速转子，找到此时的第7个位置对应的左侧数字为11，再找到右侧对应的11，位置为6，所以经过快速转子，输出变为6。然后再以位置6作为输入通过中速转子，此时位置6对应的左侧数字为10，找到右侧对应的10，位置为23，经过中速转子，输出变为23。再将23作为输入通过慢速转子，位置23对应的左侧数字为13，找到右侧对应的13，位置为7。经过慢速转子，输出变为7。

反射器

正向扰频器输出的结果为7，将7作为输入通过反射器，输出结果为21。

逆向扰频器组合

将上一步的结果21作为输入先通过慢速转子，此时位置21对应的右侧数字为15，找到左侧对应的15，位置为25。同理，再依次通过中速转子输出变为24，最后通过快速转子输出变为20。

接线板K1

将20作为输入，通过逆向线路接线板，得到输出为12，对应字母为M。

最终M作为最终结果在显示灯板上显示出来。同理，可以对E进行类似的加密得到U。

关键函数：

'''（整体被包装在类中，完整代码见压缩包 my_Enigma.py ）'''

def Encode_Decode(self,inputtext='',K2 = []):   
    if K2: 
        '''可以通过显式提供K2来设置enigma机，K1一般不改变，只能通过self.SET函数设置'''
        self.SET(K2)
    if inputtext.isalpha():
        outputtext = ""
        inputtext = inputtext.lower()
        for ch in inputtext:
            tmp = ord(ch)-97
            '''通过接线板'''
            tmp = self.K1[tmp]
            '''通过三个转子'''     
            tmp = (Cog_quick_re[(tmp + self.offset[0])% 26] - self.offset[0] + 26)%26 
            tmp = (Cog_mid_re[(tmp + self.offset[1])% 26] - self.offset[1] + 26)%26
            tmp = (Cog_slow_re[(tmp + self.offset[2])% 26] - self.offset[2] + 26)%26
            '''通过反射器'''
            tmp = T[tmp]
            '''通过三个轮子的逆'''
            tmp = (Cog_slow[(tmp + self.offset[2])%26] - self.offset[2] + 26)%26
            tmp = (Cog_mid[(tmp + self.offset[1])%26] - self.offset[1] + 26)%26
            tmp = (Cog_quick[(tmp + self.offset[0])%26] - self.offset[0] + 26)%26
            '''通过接线板'''
            tmp = self.K1[tmp]
            outputtext += chr(tmp+97)
            self.Rotate(1) #加密一个字符之后需要转动一下
    return outputtext

加密结果示意图：

计算只用3个转子,接线板有6个连接线的enigma的密钥空间有多大,密码学作业,安全

加密结果.png

二：Enigma解密

2.1 历史上的解密

Enigma机在投入使用之后，英法的情报部门曾经尝试破解，但即使是最简单的3个转子，6对接线板的Enigma机，秘钥空间都有 $10^{16}$ 的数量级，以当时的算力是不可能破解的。于是英法放弃了对Enigma机的破解，但是波兰面对黑云压城的德军，没有放弃的借口，破解Enigma机的第一次突破就来自波兰的数学家雷耶夫斯基（Marian Rejewski）。雷耶夫斯基通过数学分析，避免了接线板的转换，将秘钥空间降低到10万级别，然后就可以手动破解Enigma机了，参考Enigma机的破解一文。

波兰人的工作可以破解比较简单的Enigma机，但是后来德军改进了Enigma机，比如增加转子数量，接线板交换的字母从6对增加到10对，使用日密钥加密会话密钥时不再加密两遍等，这些改进让波兰人的破解变的无效。1939年，德军入侵波兰，波兰人将Enigma机的复制品和掌握的破解方法提供给了英法。这也让之前轻易放弃破解的英法无比震惊和惭愧。接下来就是英国数学家图灵的表演时间了。

2.2 Enigma机破解原理

2.2.1 寻找明密文对关系 – Ciber

因为Enigma反射器和转子的设计，所以在Enigma机加密过程中，一个字母是不会被加密成自身的。如上题H加密成M的过程，如果H被加密为自身，那么逆过程和正过程必须完全一致，而因为反射器的存在，正逆两个过程一定不会输出一样的结果。

根据Enigma的这个性质，我们就可以猜测明文的几个单词，并找到他们可能的位置。在密文中猜测出几个单词的明文并不困难，因为德国人在信息正文中喜欢用固定的词组，比如Heil Hitler（希特勒万岁）等。英国人还发现德军喜欢在早上发送一条当天的天气预报，所以在早上6点钟截获的电文开头中肯定包含wetter（天气）这个单词。

比如，我们用wetter在密文段上滑动比较，就可以确定wetter可能的位置，也就确定了它对应的密文，感觉可以理解为有限的选择明文攻击。

题目中所给：
计算只用3个转子,接线板有6个连接线的enigma的密钥空间有多大,密码学作业,安全

计算只用3个转子,接线板有6个连接线的enigma的密钥空间有多大,密码学作业,安全

2.2.2 通过环路屏蔽接线板

在解题过程中，三个Ciber都经过尝试，这里用Ciber1来举例。

Ciber1中有两个环路： $H\to L\to D\to H$ 和 $E\to L\to O\to E$ 。我们把第一个环路展开，可以得到：
计算只用3个转子,接线板有6个连接线的enigma的密钥空间有多大,密码学作业,安全
我们注意到， $v 2$ 和 $v 2^{'}$ 是相等的， $v 3$ 和 $v 3^{'}$ 是相等的， $v 4$ 和 $v 1$ 是相等的，我们将相等的变量直接相连，可以得到：

计算只用3个转子,接线板有6个连接线的enigma的密钥空间有多大,密码学作业,安全

这样就可以消除掉接线板的作用，我们要利用这个环，通过筛选缩小密钥空间。首先我们要遍历所有的转子组合，也就是 $26 * 26 * 26 = 17576$ 种 $K 2$ ，每一种 $K 2$ 下，我们让v1遍历a-z，然后在上述转子状态下进行加密得到 $v 2 、 v 3 、 v 4$ ，然后判断 $v 4$ 是否和 $v 1$ 相等，如果相等，说明这一组 $[k 2, v 1]$ 是满足这个环的。把所有的可能秘钥都记录下来形成一个较小的可能秘钥空间。

前面提到，这个Ciber中还有另一个环 $E\to L\to O\to E$ ，此时我们只需要在第一个环筛选出的可能秘钥空间中，再用第二个环筛选一遍，就可以进一步缩小密钥空间。
秘钥筛选分析：

我们在遍历的过程中，对于有一些k2，可以让某一个字母经过环之后加密成自身，但是有些k2不行，我们称前一种为 $p oss ib l eK 2$ ，后一种为 $im p oss ib l eK 2$ 。对于 $im p oss ib l eK 2$ ，也就是说，在这种转子组合下，26个字母都不能被加密成自身。我们假设每个字母被加密后变成任一个字母的概率都是一样的，虽然这个假设对某一个k2是不合理的，但是考虑所有的秘钥空间，可以认为概率相等，那么 $im p oss ib l eK 2$ 就是一种”错排”，而这种”错排“一共有:
$D_n = n!(\frac{1}{2!}-\frac{1}{3!}+...+(-1)^n\frac{1}{n!})$
总的字母排列有 $26!$ 种，所以 $im p oss ib l eK 2$ 的比例就是
$D_{26}/26! = 0.36787944117144245$
因为我们的转子的内部连线是不能更改的，只能对转子进行转动，因为我们的密钥空间没有26!那么大，但是经过筛选之后，发现，通过一个环路筛选出的 $p oss ib l eK 2$ 占总 $K 2$ 的比例是
$\approx 1-D_{26}/26!$
这也说明我们的假设是比较合理的，也可以说，我们的筛选结果是大概率是正确的。

2.2.3 还原接线板

经过两个环路的筛选，我们得到了一组密钥空间 $p oss ib l eK 2$ 和以及 $v 1$ 的信息。再观察我们的环路：
计算只用3个转子,接线板有6个连接线的enigma的密钥空间有多大,密码学作业,安全

我们在筛选过程中，用到的 $v 1 ， v 2 ， v 3$ ，分别可以确定 $H ， L ， D$ 的接线关系，同理，另一个环路筛选出的 $v 1 ， v 2 ， v 3$ ，也可以确定一部分接线关系，注意这里还存在一个接线板冲突的筛选。

而我们的破解，是针对这一组明密文对应关系（一个 $C ib er$ ）的，只要能找到一组转子组合 $K 2$ ，接线板 $K 1$ ，让 $H E LL O W OR L D$ 加密成 $LL D ONEEFG H$ 就可以了。那么，在某一组 $[p oss ib l eK 2, R in g 1 [v 1, v 2, v 3] ， R in g 2 [v 1, v 2, v 3]]$ 中，只有几个字母的接线板是不确定的了，对于不能确定的字母，穷举一下字母表，判断是否存在接线板冲突，如果没有冲突，那么就认为这种接线是合理的。对于没有出现过的字母，我们这里默认他们是没有接线的，但是也有可能他们是有接线关系的，但是没有我们没有足够信息。因此我们有可能没有找到完全正确的接线板，只是找到了适用于 $C ib er$ 的几种转子和接线组合。

2.3 解密算法实现

利用环路筛选秘钥，关键逻辑：

for x in range(len(Ring)):
    if not x:
        enigma = Enigma()
        for i in range(26):
            for j in range(26):
                for k in range(26):     	  # i,j,k遍历所有转轮组合
                    flag = 0
                    tmp = []
                    k2 = [i,j,k]        
                    for v1 in ALPHA:    	  # 对某一种转子组合和环路下，遍历字母表，查找是否有字母能加密为自身
                        enigma.SET(k2)
                        v4 = v1
                        v1v2v3=[]
                        for r in Ring[x][0]:  # Ring是环路的记录
                            v1v2v3.append(ord(v4)-97)
                            if r :
                                enigma.Rotate(r)         # 根据环路记录的相对位置调整转子
                            v4 = enigma.Encode_Decode(v4)# 加密
                        if v4 == v1 :                    # 经过环路之后，判断是否等与自身
                            flag = 1                     # 如果等于自身，意味着本次k2下，存在可能解，flag=1
                            tmp.append(v1v2v3)           # 把环路加密过程中所有的过程变量都记录下
                    if flag:                             
                        possible.append([k2,tmp])   # 遍历字母表之后，再插入'秘钥可能'中，因为可能一个k2有多个解
        print(len(possible))

利用环路初步确定接线板：(见2.2.3的图)

'''两个环路'''
possibleK2 = Enigma_crackK2(1)
print(len(possibleK2))
possibleK1 = []  # [[k2,K1],[k2,K1],...]
enigma = Enigma()
for pos in possibleK2:
    k2 = pos[0]                 # 获取k2
    for v1v2v3 in pos[1]:       # 获取第一个环的过程变量
        for v1v2v3_ in pos[2]:  # 获取第二个环的过程变量
            if v1v2v3_[1] != v1v2v3[1]:  # 两个环路中存在的相同字母，对应接线板设置也肯定是一样的
                continue        # 踩坑：注意continue和break的区别
            tmp_K1 = [-1]*26    # 用于记录K1
            v1v2v3.append(v1v2v3_[0]) 
            v1v2v3.append(v1v2v3_[2])
            M = [7,11,3,4,14]   # 通过两个环可以确定这5个字母的接线
            flag = 0            
            for i in range(5):  # 遍历这五个变量，更新tmp_K1
                result = K1_update(tmp_K1,M[i],v1v2v3[i])
                if not result:  # 更新失败，说明有冲突，先break，再continue
                    flag = 1
                    break
            if flag:
                continue
            possibleK1.append([k2,tmp_K1])  # 经过两个环路筛选和接线板冲突后，所有可能的[k2,k1]
print(len(possibleK1))

根据其他明密文对应还原接线板，关键逻辑：

tmp_possibleK1 = []
'''我们猜测的明文和其对应的密文中，只剩下几个字母的接线板还不能确定，通过加密判断筛选和穷举未知量，得到所有秘钥可能'''
for pos in possibleK1:     # 遍历现有的所有[k2,k1]
    k2 = pos[0]                 
    tmp_k1_0 = pos[1][:]
    P_E = tmp_k1_0[4]      # P_E 代表P(E)，即E经过接线板后的输出，经过上述过程后，这些量都是确定的
    P_L = tmp_k1_0[11]     # L经过接线板后的输出P_L
    P_O = tmp_k1_0[14]     # O经过接线板后的输出P_O

    '''未确定的对应关系：O-N,L-G'''
    enigma.SET(k2)
    enigma.Rotate(4)
    P_N = ord(enigma.Encode_Decode(chr(P_O+97)))-97     # P_O是确定的，加密一下就得到P_N
    enigma.SET(k2)      
    enigma.Rotate(8)
    P_G = ord(enigma.Encode_Decode(chr(P_L+97)))-97     # P_L是确定的，加密一下就得到P_G
    if K1_update(tmp_k1_0,ord('n')-97,P_N) and K1_update(tmp_k1_0,ord('g')-97,P_G):     
        # 判断计算得到的P_N和P_G是否冲突
        for P_W in range(26):                           # 如果不冲突，再判断'W-E'的对应关系
            tmp_k1_1 = tmp_k1_0[:]
            enigma.SET(k2)
            enigma.Rotate(5)
            S_pw = ord(enigma.Encode_Decode(chr(P_W+97)))-97
            # S_pw = S(P(W))，因为P_E是已知的，遍历字母表,加密做判断，就可以找到P_W
            if S_pw == P_E and K1_update(tmp_k1_1,ord('w')-97,P_W):
                for P_R in range(26):                    
                    # 最后确定'R-F'的关系，这两个的对应都不知道，只需要穷举P_R，计算P_F，并判断有无冲突即可
                    tmp_k1_2 = tmp_k1_1[:]
                    enigma.SET(k2)                       
                    # 注意，每次计算最好都要重置enigma，因为enigma会自己动
                    enigma.Rotate(7)
                    P_F = ord(enigma.Encode_Decode(chr(P_R+97)))-97  # 计算P_F
                    if K1_update(tmp_k1_2,ord('r')-97,P_R) and K1_update(tmp_k1_2,ord('f')-97,P_F): 
                        # 判断这一组R和F是否冲突
                        for i in range(26):              
                       	#最后还剩下一些没有信息的数据，我们这里默认他们是没有接线的
                            if tmp_k1_2[i] == -1:
                                tmp_k1_2[i] = i
                        tmp_possibleK1.append([k2,tmp_k1_2])
possibleK1 = tmp_possibleK1