栅栏密码笔记

普通栅栏算法

加密算法描述

1. 现有明文 Thi5_1s_a_fl4g，对其进行两两分组得到：

   Th、i5、_1、s_、a_、fl、4g

2. 然后取每组的第 1 个字符连成第一段，每组的第 2 个字符连成第二段，最后得到：

   Ti_saf4、h51__lg

3. 将以上多段组合起来，得到密文：

   Ti_saf4h51__lg

从以上可以看出，普通栅栏算法当明文过于简单、分组个数较小和加密轮数低时，容易被直接破解。

解密算法描述

1. 现有密文 Ti_saf4h51__lg，已知加密时是两两分组，我们便将其分为两段 (或者理解为密文长度为 10，加密用的是因数 2 进行分组，则解密使用因数 5 进行分组)：

   Ti_saf4、h51__lg

2. 然后取每组的第 1 个字符连成第一段，每组的第 2 个字符连成第二段，最后得到：

   Th、i5、_1、s_、a_、fl、4g

3. 将以上多段组合起来，得到明文：

   Thi5_1s_a_fl4g

从以上可以看出，普通栅栏算法可以采用同一个函数进行加解密，只是投入的密钥不相同。

算法定义

通过以上算法描述，我们可以做出以下简单定义：

将明文分成 \(k\) 组，取每一组的第 \(n\) 个字符连成一段，最后再将各段连接得到密文。

同时可知栅栏密码本质上是一个换位密码，并不改变明文信息，只改变明文顺序，理论上复杂度只取决于明文字长、分组个数和加密轮数。

栅栏算法可以如下定义，其中\(m\)为明文，\(c\)为密文，\(length\)为明文（密文）长度，\(F(x,y)\)为普通栅栏算法： \[ length=pq(p,q\in\Z)\\ c=F(m,p)\\ m=F(c,q) \] 以上我们可以称\(p\)为私钥 (private key)，而\(q\)为公钥 (public key)

算法实现

def railfence(data:str, key:int):
    return "".join(data[i::key] for i in range(key))

其中我们也可以实现对密文进行爆破的算法：

import math

def railfence(data:str, key:int):
    return "".join(data[i::key] for i in range(key))

# 获取 x 的所有因数
def factor(x:int):
    for i in range(2, math.floor(math.sqrt(x))+1):
        if x % i == 0:
            yield i
            yield x // i

def crack(data:str, needkeys:bool=False):
    if needkeys:
        facs = [i for i in factor(len(data))]
        return facs, [railfence(data, i) for i in facs]
    else:
        return [railfence(data, i) for i in factor(len(data))]

def print_crack(data:str):
    keys, msg = crack(data, True)
    for k, m in zip(keys, msg):
        print(f"{k}栏: {m}")

print_crack("Ti_saf4h51__lg")

密钥栅栏算法

加密算法描述

1. 现有明文 Thi5_1s_a_fl4g，对其每七个为一组分组得到：

   Thi5_1s、_a_fl4g

2. 然后取每组的第 1 个字符连成第一段，每组的第 2 个字符连成第二段，最后得到：

   T_、ha、i_、5f、_l、14、sg

3. 密钥即是组合顺序，现有密钥 3127645，则组合的密文为：

   i_T_hasg145f_l

可以看出，相比起普通栅栏算法，更难看出明文原本的顺序，但始终受制于明文字长、分组个数和加密轮数，与密钥复杂度不呈现相关性。

解密算法描述

1. 现有密文 i_T_hasg145f_l，按照密钥 3127645 还原各段：

   T_、ha、i_、5f、_l、14、sg

2. 然后取每段的第 1 个字符连成第一组，每段的第 2 个字符连成第二组，最后得到：

   Thi5_1s、_a_fl4g

3. 将以上多段组合起来，得到明文：

   Thi5_1s_a_fl4g

可以看出，相比起普通栅栏算法，还原明文时受制于密钥，如果不掌握密钥恢复的可能性将大大降低。

算法实现

def railfence_plus_encode(data:str, key:list):
    return "".join([data[i::len(key)] for i in range(len(key))][i-1] for i in key)
def railfence_plus_decode(data:str, key:list):
    k = len(data)//len(key)
    return "".join([data[key.index(i+1)*k + j] for j in range(k) for i in range(len(key))])

print(railfence_plus_encode("Thi5_1s_a_fl4g", [3,1,2,7,6,4,5]))
print(railfence_plus_decode("i_T_hasg145f_l", [3,1,2,7,6,4,5]))

理论上，我们可以对密文进行爆破，仅需得到密钥的全排列即可 (可以使用 itertools.permutations)

W型栅栏算法

算法描述

将明文按w型排列，然后将每一行的字母依次连起来组成密文，行数就是密钥。

解密则同样画出这个w型图案，将每一列的字母依次连接起来组成明文。

W型栅栏密码的密钥不只是密文长度的因数，任何小于密文长度大于1的整数都有可能。

算法实现

# 获取 w 型矩阵
def railfence_w(data:str, key:int):
    mat = [[None]*len(data) for i in range(key)]
    row = 0
    upflag = False
    for col in range(len(data)):
        mat[row][col] = data[col]
        if row == key-1:
            upflag = True
        if row == 0:
            upflag = False
        if upflag:
            row -= 1
        else:
            row += 1
    return mat

# 加密
def railfence_w_encode(data, key):
    mat = railfence_w(data, key)
    msg = []
    for row in range(key):
        for col in range(len(data)):
            if mat[row][col] != None:
                msg.append(mat[row][col])
    return mat, msg

# 解密
def railfence_w_decode(data, key):
    mat = railfence_w(data, key)
    sub = 0
    for row in range(key):
        for col in range(len(data)):
            if mat[row][col] != None:
                mat[row][col] = data[sub]
                sub += 1
    msg = []
    for col in range(len(data)):
        for row in range(key):
            if mat[row][col] != None:
                msg.append(mat[row][col])
    return mat, msg

# 爆破算法
def crack_w(data:str, needkeys:bool=False):
    if needkeys:
        keys = [i for i in range(2, len(data))]
        return keys, [''.join(railfence_w_decode(data, k)[1]) for k in keys]
    else:
        return [''.join(railfence_w_decode(data, k)[1]) for k in range(2, len(data))]

def print_crack_w(data:str):
    keys, msg = crack_w(data, True)
    for k, m in zip(keys, msg):
        print(f"{k}栏: {m}")

print_crack_w("ccehgyaefnpeoobe{lcirg}epriec_ora_g")