加密解密工具 之 波利比奥斯方阵密码(棋盘加密原理)
加密解密工具 之 波利比奥斯方阵密码(棋盘加密原理)
波利比奥斯方阵密码（Polybius Square Cipher或称波利比奥斯棋盘）是棋盘密码的一种，是利用波利比奥斯方阵进行加密的密码方式，简单的来说就是把字母排列好，用坐标(行列)的形式表现出来。字母是密文，明文便是字母的坐标。
工具链接：
密码学是研究编制密码和破译密码的技术科学。研究密码变化的客观规律，应用于编制密码以保守通信秘密的，称为编码学；应用于破译密码以获取通信情报的，称为破译学，总称密码学。
密码是通信双方按约定的法则进行信息特殊变换的一种重要保密手段。依照这些法则，变明文为密文，称为加密变换；变密文为明文，称为脱密变换。密码在早期仅对文字或数码进行加、脱密变换，随着通信技术的发展，对语音、图像、数据等都可实施加、脱密变换。
密码学是在编码与破译的斗争实践中逐步发展起来的，并随着先进科学技术的应用，已成为一门综合性的尖端技术科学。它与语言学、数学、电子学、声学、信息论、计算机科学等有着广泛而密切的联系。它的现实研究成果，特别是各国政府现用的密码编制及破译手段都具有高度的机密性。
进行明密变换的法则，称为密码的体制。指示这种变换的参数，称为密钥。它们是密码编制的重要组成部分。密码体制的基本类型可以分为四种：错乱——按照规定的图形和线路，改变明文字母或数码等的位置成为密文；代替——用一个或多个代替表将明文字母或数码等代替为密文；密本——用预先编定的字母或数字密码组，代替一定的词组单词等变明文为密文；加乱——用有限元素组成的一串序列作为乱数，按规定的算法，同明文序列相结合变成密文。以上四种密码体制，既可单独使用，也可混合使用 ，以编制出各种复杂度很高的实用密码。
20世纪70年代以来，一些学者提出了公开密钥体制，即运用单向函数的数学原理，以实现加、脱密密钥的分离。加密密钥是公开的，脱密密钥是保密的。这种新的密码体制，引起了密码学界的广泛注意和探讨。
利用文字和密码的规律，在一定条件下，采取各种技术手段，通过对截取密文的分析，以求得明文，还原密码编制，即破译密码。破译不同强度的密码，对条件的要求也不相同，甚至很不相同。
中国古代秘密通信的手段，已有一些近于密码的雏形。宋曾公亮、丁度等编撰《武经总要》“字验”记载，北宋前期，在作战中曾用一首五言律诗的40个汉字，分别代表40种情况或要求，这种方式已具有了密本体制的特点。
1871年，由上海大北水线电报公司选用6899个汉字，代以四码数字，成为中国最初的商用明码本，同时也设计了由明码本改编为密本及进行加乱的方法。在此基础上，逐步发展为各种比较复杂的密码。
在欧洲，公元前405年，斯巴达的将领来山得使用了原始的错乱密码；公元前一世纪，古罗马皇帝凯撒曾使用有序的单表代替密码；之后逐步发展为密本、多表代替及加乱等各种密码体制。
二十世纪初，产生了最初的可以实用的机械式和电动式密码机，同时出现了商业密码机公司和市场。60年代后，电子密码机得到较快的发展和广泛的应用，使密码的发展进入了一个新的阶段。
密码破译是随着密码的使用而逐步产生和发展的。1412年，波斯人卡勒卡尚迪所编的百科全书中载有破译简单代替密码的方法。到16世纪末期，欧洲一些国家设有专职的破译人员，以破译截获的密信。密码破译技术有了相当的发展。1863年普鲁士人卡西斯基所著《密码和破译技术》，以及1883年法国人克尔克霍夫所著《军事密码学》等著作，都对密码学的理论和方法做过一些论述和探讨。1949年美国人香农发表了《秘密体制的通信理论》一文，应用信息论的原理分析了密码学中的一些基本问题。
自19世纪以来，由于电报特别是无线电报的广泛使用，为密码通信和第三者的截收都提供了极为有利的条件。通信保密和侦收破译形成了一条斗争十分激烈的隐蔽战线。
1917年，英国破译了德国外长齐默尔曼的电报，促成了美国对德宣战。1942年，美国从破译日本海军密报中，获悉日军对中途岛地区的作战意图和兵力部署，从而能以劣势兵力击破日本海军的主力，扭转了太平洋地区的战局。在保卫英伦三岛和其他许多著名的历史事件中，密码破译的成功都起到了极其重要的作用，这些事例也从反面说明了密码保密的重要地位和意义。
当今世界各主要国家的政府都十分重视密码工作，有的设立庞大机构，拨出巨额经费，集中数以万计的专家和科技人员，投入大量高速的电子计算机和其他先进设备进行工作。与此同时，各民间企业和学术界也对密码日益重视，不少数学家、计算机学家和其他有关学科的专家也投身于密码学的研究行列，更加速了密码学的发展。
现在密码已经成为单独的学科，从传统意义上来说，密码学是研究如何把信息转换成一种隐蔽的方式并阻止其他人得到它。
密码学是一门跨学科科目，从很多领域衍生而来：它可以被看做是信息理论，却使用了大量的数学领域的工具，众所周知的如数论和有限数学。
原始的信息，也就是需要被密码保护的信息，被称为明文。加密是把原始信息转换成不可读形式，也就是密码的过程。解密是加密的逆过程，从加密过的信息中得到原始信息。cipher是加密和解密时使用的算法。
最早的隐写术只需纸笔，现在称为经典密码学。其两大类别为置换加密法，将字母的顺序重新排列；替换加密法，将一组字母换成其他字母或符号。经典加密法的资讯易受统计的攻破，资料越多，破解就更容易，使用分析频率就是好办法。经典密码学现在仍未消失，经常出现在智力游戏之中。在二十世纪早期，包括转轮机在内的一些机械设备被发明出来用于加密，其中最著名的是用于第二次世界大战的密码机Enigma。这些机器产生的密码相当大地增加了密码分析的难度。比如针对Enigma各种各样的攻击，在付出了相当大的努力后才得以成功。
波利比奥斯方阵
公元前2世纪，一个叫Polybius的希腊人设计了一种将字母编码成符号对的方法。他使用了一个称为Polybius的校验表。Polybius校验表由一个5行5列的网格组成，网格中包含26个英文字母，其中I和J在同一格中。相应字母用数对表示。在古代，这种棋盘密码被广泛使用。Polybius校验表如下：
假设我们需要发送明文信息“Hello”，找到H对应2行3列，则加密为23，e加密为15，以此类推，得到密文：2315 31 31 34。
ADFGX密码
1918年，第一次世界大战将要结束时，法军截获了一份德军电报，电文中的所有单词都由A、D、F、G、X五个字母拼成，因此被称为ADFGX密码。ADFGX密码是1918年3月由德军上校FritzNebel发明的，是结合了波利比奥斯方阵和置换密码的双重加密方案。ADFGX密码之所以选择ADFGX一个字母，是因为它们译成摩斯密码时不容易混淆，可以降低传输错误的机率。ADFGX密码表如下：
这样加密的话Hello的密文就是：DD XF AG AGDF。
ADFGVX密码
ADFGX密码发送含有大量数字的信息会有问题。 在1918年6月，又加入一个字母V扩充，变成以6×6格共36个字符加密，这使得所有英文字母（不再将I和J视为同一个字）以及数字0到9都可混合使用。ADFGVX是被法国陆军中尉Georges Painvin所破解的。
这些天都在没日没夜地关注一个话题，谷歌人工智能程序AlphaGo（国内网友亲切地称为“阿尔法狗”）以5:0击败欧洲职业围棋冠军樊麾二段，并在和世界冠军的比赛中2:0领先。
什么！！
19年前计算机击败国际象棋冠军卡斯帕罗夫的情景还历历在目，现在计算机又要来攻克围棋了吗！？
虚竹在天龙八部里自填一子，无意中以“自杀”破解“珍笼”棋局，逍遥子方才亲传掌门之位。难道以后“阿尔法狗”要出任逍遥派掌门了？
1933年，东渡日本19岁的吴清源迎战当时的日本棋坛霸主、已经60岁的本因坊秀哉，开局三招即是日本人从未见过的三三、星、天元布阵，快速进击逼得对方连连暂停“打卦”和弟子商量应对之策。随后以“新布局”开创棋坛新纪元。难道阿尔法狗会再造一个“新新布局”？
作为一个关心人工智能和人类命运的理科生，近些天刷了好些报道，记者们说“阿尔法狗是个‘价值神经网络’和‘策略神经网’络综合蒙特卡洛搜索树的程序”，但我觉得光知道这些概念是不够的。我想看看“阿尔法狗”的庐山真面目。
准备好棋盘和脑容量，一起来探索吧？
围棋棋盘是19x19路，所以一共是361个交叉点，每个交叉点有三种状态，可以用1表示黑子，-1表示白字，0表示无子，考虑到每个位置还可能有落子的时间、这个位置的气等其他信息，我们可以用一个361 * n维的向量来表示一个棋盘的状态。我们把一个棋盘状态向量记为s。
当状态s下，我们暂时不考虑无法落子的地方，可供下一步落子的空间也是361个。我们把下一步的落子的行动也用361维的向量来表示，记为a。
这样，设计一个围棋人工智能的程序，就转换成为了，任意给定一个s状态，寻找最好的应对策略a，让你的程序按照这个策略走，最后获得棋盘上最大的地盘。
如果你想要设计一个特别牛逼惊世骇俗的围棋程序，你会从哪里开始呢？对于在谷歌DeepMind工作的黄士杰和他的小伙伴而言，第一招是：
蒙特卡洛搜索树（Monte-Carlo Tree Search）是一种“大智若愚”的方法。面对一个空白棋盘S0，黄士杰的老师Coulum最初对围棋一无所知，便假设所有落子方法分值都相等，设为1。然后扔了一个骰子，从361种落子方法中随机选择一个走法a0。Coulum想象自己落子之后，棋盘状态变成S1，然后继续假设对手也和自己一样二逼，对方也扔了一个筛子，随便瞎走了一步，这时棋盘状态变成S2，于是这两个二逼青年一直扔骰子下棋，一路走到Sn，最后肯定也能分出一个胜负r，赢了就r记为1，输了则为0，假设这第一次r=1。这样Coulum便算是在心中模拟了完整的一盘围棋。
Coulum心想，这样随机扔骰子也能赢？运气不错啊，那把刚才那个落子方法（S0,a0）记下来，分值提高一些：
我刚才从（S0, a0）开始模拟赢了一次，r=1，那么新分数=2，除了第一步，后面几步运气也不错，那我把这些随机出的局面所对应落子方法(Si,ai)的分数都设为2吧。然后Coulum开始做第二次模拟，这次扔骰子的时候Coulum对围棋已经不是一无所知了，但也知道的不是太多，所以这次除（S0, a0）的分值是2之外，其他落子方法的分数还是1。再次选择a0的概率要比其他方法高一点点。
那位假想中的二逼对手也用同样的方法更新了自己的新分数，他会选择一个a1作为应对。如法炮制，Coulum又和想象中的对手又下了一盘稍微不那么二逼的棋，结果他又赢了，Coulum于是继续调整他的模拟路径上相应的分数，把它们都+1。随着想象中的棋局下得越来越多，那些看起来不错的落子方案的分数就会越来越高，而这些落子方案越是有前途，就会被更多的选中进行推演，于是最有“前途”的落子方法就会“涌现”出来。
最后，Coulum在想象中下完10万盘棋之后，选择他推演过次数最多的那个方案落子，而这时，Coulum才真正下了第一步棋。
蒙特卡洛搜索树华丽转身为相当深刻的方法，可以看到它有两个很有意思的特点：
1）没有任何人工的feature，完全依靠规则本身，通过不断想象自对弈来提高能力。这和深蓝战胜卡斯帕罗夫完全不同，深蓝包含了很多人工设计的规则。MCTS靠的是一种类似遗传算法的自我进化，让靠谱的方法自我涌现出来。让我想起了卡尔文在《大脑如何思维》中说的思维的达尔文主义[6]。
2）MCTS可以连续运行，在对手思考对策的同时自己也可以思考对策。Coulum下完第一步之后，完全不必要停下，可以继续进行想象中的对弈，直到对手落子。Coulum随后从对手落子之后的状态开始计算，但是之前的想象中的对弈完全可以保留，因为对手的落子完全可能出现在之前想象中的对弈中，所以之前的计算是有用的。这就像人在进行对弈的时候，可以不断思考，不会因为等待对手行动而中断。这一点Coulum的程序非常像人，酷毙了。
但黄士杰很快意识到他老师的程序仍然有局限：初始策略太简单。我们需要更高效地扔骰子。
如何更高效的扔骰子呢？
用P_human()来扔。
如果某一步被随机到很多次，就应该主要依据模拟得到的概率而非P_human。
所以P_human的初始分会被打个折扣：
这样就既可以用P_human快速定位比较好的落子方案，又给了其他位置一定的概率。看起来很美，然后实际操作中却发现：“然并卵”。因为，P_human()计算太慢了。
一次P_human()计算需要3ms，相对于原来随机扔骰子不到1us，慢了3000倍。如果不能快速模拟对局，就找不到妙招，棋力就不能提高。所以，黄士杰训练了一个简化版的P_human_fast()，把神经网络层数、输入特征都减少，耗时下降到了2us，基本满足了要求。先以P_human()来开局，走前面大概20多步，后面再使用P_human_fast()快速走到最后。兼顾了准确度和效率。
这样便综合了深度神经网络和MCTS两种方案，此时黄士杰的围棋程序已经可以战胜所有其他电脑，虽然距离人类职业选手仍有不小的差距，但他在2015年那篇论文的最后部分信心满满的表示：“我们围棋软件所使用的神经网络和蒙特卡洛方法都可以随着训练集的增长和计算力的加强（比如增加CPU数）而同步增强，我们正前进在正确的道路上。”
看样子，下一步的突破很快就将到来。同年2月，黄士杰在Deepmind的同事在顶级学术期刊nature上发表了“用神经网络打游戏”的文章[2]。这篇神作，为进一步提高MCTS的棋力，指明了前进的新方向：
红白机很多人小时候都玩过，你能都打通吗？黄士杰的同事通过“强化学习”方法训练的程序在类似红白机的游戏机上打通了200多个游戏，大多数得分都比人类还好。
“强化学习”是一类机器学习方法，Agent通过和环境s的交互，选择下一步的动作a，这个动作会影响环境s，给Agent一个reward，Agent然后继续和环境交互。游戏结束的时候，Agent得到一个最后总分r。这时我们把之前的环境状态s、动作a匹配起来就得到了一系列s,a，设定目标为最后的总得分r，我们可以训练一个神经网络去拟合在状态s下，做动作a的总得分。下一次玩游戏的时候，我们就可以根据当前状态s，去选择最后总得分最大的动作a。通过不断玩游戏，我们对s,a下总得分的估计就会越来越准确，游戏也玩儿得越来越好。
打砖块游戏有一个秘诀：把球打到墙的后面去，球就会自己反弹得分。强化学习的程序在玩了600盘以后，学到这个秘诀：球快要把墙打穿的时候评价函数v的分值就会急剧上升。
机器学习的开山鼻祖Samuel早在1967年就用自对弈的方法来学习国际跳棋[7]，而之前的蒙特卡洛搜索树也是一个自对弈的过程。但是现在黄士杰不仅有一个从人类对弈中学习出的P_human这样一个高起点，而且有一个神经网络可以从对弈样本中学习，有理由相信这次会有更好的结果。
黄士杰准备在MCTS框架之上融合局面评估函数v()。这次还是用P_human作为初始分开局，每局选择分数最高的方案落子，下到第L步之后，改用P_human_fast把剩下的棋局走完，同时调用v(SL)，评估局面的获胜概率。然后按照如下规则更新整个树的分数：
前两项和原来一样，如果待更新的节点就是叶子节点，那局面评估分就是v(SL)。如果是待更新的节点是上级节点，局面评估分是该节点所有叶子节点v()的平均值。
如果v()表示大局观，“P_human_fast模拟对局”表示快速验算，那么上面的方法就是大局观和快速模拟验算并重。如果你不服，非要做一个0.5: 0.5之外的权重，黄士杰团队已经实验了目前的程序对阵其他权重有95%的胜率。
以上，便是阿尔法狗的庐山真面目。
上图演示了阿尔法狗和樊麾对弈时的计算过程，阿尔法狗执黑，红圈是阿尔法狗实际落子的地方。1、2、3和后面的数字表示他想象中的之后双方下一步落子的地方。白色方框是樊麾的实际落子。在复盘时，樊麾觉得位置1的走法更好。
深度学习、蒙特卡洛搜索树，自我进化三招齐出，所有其他围棋ai都毫无还手之力。99%的胜率不说，“阿尔法狗”还可以在让四子的情况下以77%的胜率击败crazystone。“阿尔法狗”利用超过170个GPU，粗略估算超过800万核并行计算，不仅有前期训练过程中模仿人类，自我对弈不断进化，还有实战时的模拟对局可以实时进化，已经把现有方法发挥到了极限，是目前人工智能领域绝对的巅峰之作。
围棋是NP-hard问题，如果用一个原子来存储围棋可能的状态，把全宇宙的原子加起来都不够储存所有的状态。于是我们把这样的问题转换为寻找一个函数P，当状态为S时，计算最优的落子方案a = P(s)。我们看到，无论是“狂拽酷炫”的深度学习，还是“大智若愚”的MCTS，都是对P(s)的越来越精确的估计，但即使引入了“左右互搏”来强化学习，黄士杰和团队仍然做了大量的细节工作。所以只有一步一个脚印，面对挑战不断拆解，用耐心与细心，还有辛勤的汗水，才能取得一点又一点的进步，而这些进步积累在一起，终于让计算机达到并超过了人类职业选手的水平。
应该都是一样的，都是2/(25*26).
首先要选出一个字母i，1/26,然后是放在放j的盒子里，1/25.先选j也是这样的，所以乘2。
根据明文和密钥区分。
由于ij同时出现的概率较低，所以同格。ij可以根据明文和密钥来区分。
棋盘密码是利用波利比奥斯方阵进行加密的密码方式，产生于公元前两世纪的希腊，相传是世界上最早的一种密码。
