Playfair 密码

简介

首发于公众号：深大信安Aurora

Playfair 密码（Playfair cipher or Playfair square）是一种对称式密码，是首种双字母取代的加密法。1854 年由英国人查尔斯 · 惠斯通（Charles Wheatstone）发明，惠斯登的朋友普莱费尔勋爵普及了这个加密法。基本算法如下：

1. 选取一串英文字母，除去重复出现的字母，将剩下的字母逐个逐个加入 5 × 5 的矩阵内，剩下的空间由未加入的英文字母依 A-Z 的顺序加入。注意，将 Q 去除，或将 I 和 J 视作同一字。
2. 将要加密的明文分成两个一组。若组内的字母相同，将 X（或 Q）加到该组的第一个字母后，重新分组。若剩下一个字，也加入 X 。
3. 在每组中，找出两个字母在矩阵中的地方。
   • 若两个字母不同行也不同列，在矩阵中找出另外两个字母（第一个字母对应行优先），使这四个字母成为一个长方形的四个角。
   • 若两个字母同行，取这两个字母右方的字母（若字母在最右方则取最左方的字母）。
   • 若两个字母同列，取这两个字母下方的字母（若字母在最下方则取最上方的字母）。

新找到的两个字母就是原本的两个字母加密的结果。

以 playfair example为密匙，得

要加密的讯息为 THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG, 根据规则我们需要在某位补上一个X, 得到

TH EQ UI CK BR OW NF OX JU MP SO VE RT HE LA ZY DO GX

以TH为例，根据规则得到ZB，如下：

同理，按照加密规则就会得到

ZB XO TR BN CI QV SL QE RT IF KQ AD IU DM AY WF OV QG

以下给出加解密脚本

import string


class Playfair:
    def __init__(self, key):
        self.table = []

        self.create_table(key)

    def create_table(self, key):
        letter_list = string.ascii_uppercase.replace('J', 'I')
        # 格式化字符串
        key = key.upper().replace('J', 'I')  # 将密钥变为大写, 且将I和J看为同一个字符
        table = []  # 加密表
        for i in key:
            # 过滤非字母 以及 去除重复字母 并加入加密表中
            if i.isalpha() and i not in table:
                table.append(i)

        # 将a-z中不在加密表的字母加入
        for i in letter_list:
            if i not in table:
                table.append(i)
        # 将加密表变为 5*5
        self.table = [table[i*5:i*5+5] for i in range(5)]

    def get_index(self, ch):
        for i in range(5):
            for j in range(5):
                if ch == self.table[i][j]:
                    return i, j
        return -1, -1

    def encrypt(self, plaintext):
        plaintext = plaintext.upper().replace('J', 'I')  # 将明文变为大写, 且将I和J看为同一个字符

        # 进行分组，如果相邻字母相同就在该组的第一个字母后加入X后重新分组, 如果第一个字母为X则加Q
        i = 0
        sum = 0  # 计算字母数
        while i < len(plaintext):
            if not plaintext[i].isalpha():
                i += 1
            else:
                if i == len(plaintext) - 1:
                    sum += 1
                    break
                while not plaintext[i+1].isalpha() and i < len(plaintext):
                    i += 1
                if plaintext[i] == plaintext[i+1]:
                    ch = 'X' if plaintext[i] != 'X' else 'Q'
                    plaintext = plaintext[:i+1] + ch + plaintext[i+1:]
                i += 2
                sum += 2

        # 如果明文处理后为奇数就在最后加入X
        if sum % 2:
            for i in range(len(plaintext)-1, -1, -1):
                if plaintext[i].isalpha():
                    ch = 'X' if plaintext[i] != 'X' else 'Q'
                    plaintext += ch
                    break

        ciphertext = ""
        i = 0
        while i < len(plaintext):
            if not plaintext[i].isalpha():
                ciphertext += plaintext[i]
                i += 1
                continue
            x0, y0 = self.get_index(plaintext[i])

            tmp = ""
            while not plaintext[i+1].isalpha() and i < len(plaintext):
                tmp += plaintext[i+1]
                i += 1

            x1, y1 = self.get_index(plaintext[i + 1])

            if x0 == x1:  # 如果在同一行
                ciphertext += self.table[x0][(y0 + 1) %
                                             5] + tmp + self.table[x1][(y1 + 1) % 5]

            elif y0 == y1:  # 如果在同一列
                ciphertext += self.table[(x0 + 1) %
                                         5][y0] + tmp + self.table[(x1 + 1) % 5][y1]

            else:  # 不同行不同列
                ciphertext += self.table[x0][y1] + tmp + self.table[x1][y0]

            i += 2
        return ciphertext

    def decrypt(self, ciphertext):
        plaintext = ""
        ciphertext = ciphertext.upper()

        sum = 0
        for i in ciphertext:
            sum += 1 if i.isalpha() else 0
        assert sum % 2 == 0

        i = 0
        while i < len(ciphertext):
            if not ciphertext[i].isalpha():
                plaintext += ciphertext[i]
                i += 1
                continue

            x0, y0 = self.get_index(ciphertext[i])

            tmp = ""
            while not ciphertext[i+1].isalpha() and i < len(ciphertext):
                tmp += ciphertext[i+1]
                i += 1

            x1, y1 = self.get_index(ciphertext[i + 1])

            if x0 == x1:  # 如果在同一行
                plaintext += self.table[x0][(y0 - 1) %
                                            5] + tmp + self.table[x1][(y1 - 1) % 5]

            elif y0 == y1:  # 如果在同一列
                plaintext += self.table[(x0 - 1) %
                                        5][y0] + tmp + self.table[(x1 - 1) % 5][y1]

            else:  # 不同行不同列
                plaintext += self.table[x0][y1] + tmp + self.table[x1][y0]

            i += 2

        return plaintext


if __name__ == "__main__":
    key = "playfair example"
    plaintext = "THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG"
    playfair = Playfair(key)
    ciphertext = playfair.encrypt(plaintext)
    print(ciphertext) # ZBX OTRBN CIQVS LQE RTIFK QADI UDM AYWF OVQG
    plaintext = playfair.decrypt(ciphertext)
    print(plaintext) # THE QUICK BROWN FOX IUMPS OVER THE LAZY DOGX

攻击方法

在不知道密钥的情况下，可以使用该GitHub项目所给的方法进行暴力破解，具体使用方法项目也说的比较清晰，这里不再赘述

PlayfairCrack

例题

实验吧-密码学-Fair-Play

• 题目描述

  The quick brown fox jumps over the lazy dog!
  ihxo{smzdodcikmodcismzd

• 解题思路

  • 根据所给题目描述我们猜测The quick brown fox jumps over the lazy dog!就是所给密钥，我们用我们上述给的脚本直接进行解密，当然，要注意我们的脚本用的是大写，记得转换为小写即可

  • from Playfair import Playfair
    key = "The quick brown fox jumps over the lazy dog!"
    ciphertext = "ihxo{smzdodcikmodcismzd}"
    playfair = Playfair(key)
    plaintext = playfair.decrypt(ciphertext)
    print(plaintext.lower())
    

  • 得到flag: ctfx{playfairisfairplay}

Crack

PlayfairCrack