《CTF特训营》——古典密码学

目录

一、移位密码

1.简单移位密码

（1）介绍

（2）例子

（3）加密解密的实现

2.曲路密码

3.云影密码

4.栅栏密码

二、代替密码

1.单表代替密码

（1）凯撒密码

①加密解密的实现

②例子

（2）ROT13

①加密解密的实现

（3）埃特巴什码

①加密解密的实现

（4）经典单表代替密码

①加密解密的实现

（5）培根密码

（6）仿射密码

①加密解密的实现

②已知明文的攻击

2.单表代替密码

（1）棋盘类密码

①Playfari加密解密的实现

②Polybuis加密解密的实现（Nihilist原理相同）

3.维吉尼亚密码

4.希尔密码

---

一、移位密码

1.简单移位密码

（1）介绍

移位密码是密码学中最基础、最简单的一种密码形式，可以理解为明文根据密钥进行了位置的变换的得到的密文。

（2）例子

m = flag{easy_easy_crypto}

k='3124'

当明文为m，密钥为k时，移位密码首先以k的长度切分m，具体如下：

flag  {eas    y_ea   sy_c   rypt   o}

可以看到总共分成了6部分，按照密钥规则3124的顺序对每一部分进行密钥变化，所以密文为：

lafgea{s_eyay_scyprt}o

（3）加密解密的实现

#利用Python实现
 
#加密
 
def shift_encrypt(m,k):
    l = len(k)
    c = ""
    for i in range(0,len(m),1):
        tmp_c = [""] * 1
        if i + 1 > len(m):
            tmp_n = m[i:]
        else:
            tmp_m = m[i:i+1]
            for kindex in range(len(tmp_m)):
                tmp_c [int(k[kindex]) - 1] = tmp_m[kindex]
                c += "".join(tmp_c)
                return c
 
m = "flag{easy_easy_crypto}"
k = '3124'
print shift_encrypt(m,k)
 
 
#解密
def shift_encrypt(m,k):
    l = len(k)
    m = ""
    for i in range(0,len(c),1):
        tmp_m = [""] * 1
        if i + 1 > len(c):
            tmp_c = c[i:]
            use = []
            for kindex in range(len(tmp_c)):
                use,append(int(k[kindex]) - 1)
                use,sort()
                for kindex in range(len(tmp_c)):
                    tmp_m[kindex] = tmp_c [use,index(int(k[kindex]) -1 )]
        else:
            tmp_c = c[i:i+1]
            for kindex in range(len(tmp_c)):
                tmp_m [kindex] = tmp_c[int(k[kindex]) - 1]
                m += "".join(tmp_m)
                return m
 
m = "flag{easy_easy_crypto}"
k = '3124'
print shift_encrypt(c,k)

2.曲路密码

曲路密码也是移位密码的一种，加密原理如下：

 图中的密文就是从g到T，反过来就是解密

3.云影密码

云影密码又称01248密码，仅仅包含01248几个数字，其中0用于分割，其与数字用于加和操作之后转换为明文，解密方式如下：

def c01248_decode(c):
    l = c.split("0")
    origin = "abcdefghijklmnopqrstuvwxyz"
    r = ""
    for i in 1:
        tmp = 0
        for num in i:
            tmp += int(num)
            r += origin [tmp-1]
            return r
        print c01248_decode("884210122048022440414224202480122")

4.栅栏密码

栅栏密码是一种比较特殊的移位密码，密钥只有一个数字k，表示栅栏的长度，所谓的栅栏密码，就是将加密的明文分成k个组，然后取每组的第一个字符依次连接，拼接而成的字符串就是密文

（1）加密解密的实现

#加密
 
def zhalan_encrypt(m,k):
    chip = []
    for i in range(0,len(m),k):
        if i + k >= len(m):
            tmp_m = m[i]
        else:
            tmp_m = m[i:i+k]
            chip.append(tmp_m)
            c = ""
            for i in range(k):
                for tmp_m in chip:
                    if i < len(tmp_m):
                        c += tmp_m [i]
                        return c
                    m = "flag{zhalan_mima_hahaha}"
                    k =4
                    print zhalan_encrypt(m,k)
 
#解密
def zhanlan_decrypt(c,k):
    l = len(c)
    partnum = 1 / k
    if 1 % k != 0:
        partnum += 1
        m = [""] * 1
        for i in range(0,1,partnum):
            if i + partnum >= len(c):
                tmp_c = c[i:]
            else:
                tmp_c = c[i:i + partnum]
                for j in  range(len(tmp_c)):
                    m[j * k + i / partnum] = tmp_c[j]
                    return "".join(m)
                c = "f{lm_alzaihhahnmaaga_ah}"
                k = 4
                print zhanlan_decrypt(c,k)

二、代替密码

1.单表代替密码

（1）凯撒密码

凯撒密码是非常著名密码，原理也非常简单，就是通过字母的位移数来实现加密界面，明文中的所有字母都在字母表上向后或镶嵌按照一个固定的数目进行偏移后被替代成密文。

①加密解密的实现

#加密
 
def kaisa_encrypt(m,k):
    r = ""
    for i in m:
        r += chr((ord(i) + k) % 128)
        return r 
    
    m = "flag{kaisamima}"
    k = 3
    print kaisa_encrypt(m,k)
 
#解密
def kaisa_decrypt(c,k):
    r = ""
    for i in c:
        r += chr((ord(i) - k) % 128)
        return r
    c = "iodj-ndlvdplpd\x00"
    k = 3
    print kaisa_decrypt(c,k)

针对单表替代密码的攻击方法本来是词频分析，但是凯撒密码的密钥取值空间太小，直接爆破也是很简单的办法，所以针对凯撒密码的攻击方法就是爆破密钥k。

②例子

c="39.4H/?BA2,0.2@.?J

上述所示密文c，在没有密钥k的情况下，我们爆破密钥k，并判断结果中是否包含flag格式的字符串，以爆破出明文m，代码如下：

def kaisa_decrypt(c,k):
    r = ""
    for i in c:
        r += chr((ord(i) - k) % 128)
        return r
    def kaisai_brute(c,match_str):
        result = []
        for k in range(128):
            tmp = kaisa_decrypt(c,k)
            if match_str in tmp:
                result,append(tmp)
                return result
            c = "39.4H/?BA2,0.2@.?J"
            print kaisai_brute(c,"flag")

（2）ROT13

ROT13是凯撒的一种特例，当k=13，且只作用于大小写时，称之为ROT13，准确来讲他不能算是密码，而是编码，它没有密钥。

ROT13通常作用于MD5、flag等字符串上，而我们通常知道MD5的字符只有ABCDEF，其对应的ROT13就是“NOPQRS”，flag对应的就是“SYNT”。

①加密解密的实现

#加密解密都是一样的
 
 
def rot13(m):
    r =""
    for i in m:
        if ord(i) in range(ord('A'),ord('Z') + 1):
            r += chr((ord(i) + 13 - ord('A')) % 26 + ord('A'))
        elif ord(i) in range(ord('a'),ord('z') + 1):
            r += chr((ord(i) + 13 - ord('a')) % 26 + ord('a'))
        else:
            r += i
            return r 
        c = ""
        print rot13(c)
        print rot13(rot13(c))

（3）埃特巴什码

与凯撒密码不同的是，埃特巴什码（Atbash Cipher）的替代表不是通过位移获得的，而是通过对称获得的，其通过将字母表的位置完全镜面对称后获得字母的替代表，然后进行加密。

ABCDEFGHIJKLMNOPQRSTUVWXYZ

ZYXWVUTSRQPONMLKJIHGFEDCBA

①加密解密的实现

#加密
 
def bash_encode(m):
    alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    origin = alphabet + alphabet.lower()
    TH_A = alphabet[::-1]
    TH_a = alphabet.lower() [::-1]
    TH = TH_A + TH_a
    r = ""
    for i in m:
        tmp = origin.find(i)
        if tmp != -1:
            r += TH[tmp]
        else:
            r += i
            return r 
        print bash_encode("")
 
#解密
 
def bash_encode(m):
    alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    origin = alphabet + alphabet.lower()
    TH_A = alphabet[::-1]
    TH_a = alphabet.lower() [::-1]
    TH = TH_A + TH_a
    r = ""
    for i in m:
        tmp = origin.find(i)
        if tmp != -1:
            r += TH[tmp]
        else:
            r += i
            return r
        print bash_encode(bash_encode(""))

（4）经典单表代替密码

经典单表代替密码就是一个代替表对每一个位置的字符进行查表替换，假设替换表内容如下：

ABCDEFGHIJKLMNOPQRSTUVWXYZ

ZYXWVUTSRQPONMLKJIHGFEDCBA

①加密解密的实现

#加密
 
def danbiao_eccrypt(m,k,origin="ABCDEFGHIJKLMNOPQRSTUVWXYZ"):
    r = ""
    for i in m:
        if origin.find(i) != -1:
            r += k[origin.find(i)]
        else:
            r += i
            return r
        print danbiao_eccrypt("")
        
 
#解密
def dainbiao_decode(c,k,origin="ABCDEFGHIJKLMNOPQRSTUVWXYZ"):
    r = ""
    for i in c:
        if k.find(i) != -1:
            r += origin[k.find(i)]
        else:
            r += 1
            return r
        print dainbiao_decode("")
 

（5）培根密码

培根密码一般使用两种不同字体标识密文，密文内容不是关键所在，关键是字体，使用AB代表两种字体，五个一组，表示密文，明文对应如下：

 网上有在线解密，可以自行搜索。

（6）仿射密码

仿射密码的替代表的生成方式依据：c=am+b mod n，其中，m为明文对应字母得到的数字，n为字符数量，c为密文，a和b为密钥。

①加密解密的实现

#加密
 
def fangshe_encode(m,a,b,origin="ABCDEFGHIJKLMNOPQRSTUVWXYZ"):
    r = ""
    for i in m:
        if origin.find(i) != -1:
            r += origin[(a * origin.index(i) + b) % len(origin)]
        else:
            r += i
            return r
        print fangshe_encode("")
 
#解密
 
def fangshe_dencode(c,a,b,origin="ABCDEFGHIJKLMNOPQRSTUVWXYZ"):
    r = ""
    n = len(origin)
    ai = primefac.modinv(a,n) %n
    for i in c:
        if origin.find(i) != -1:
            r += origin[(ai * (origin.index(i) - b)) % len(origin)]
        else:
            r += i
            return r 
        print fangshe_dencode("")

②已知明文的攻击

如果我们知道了任意两个字符的明文密文对，那么我们可以推理出密钥ab：

def fangshe_guessab(c,a,b,origin="ABCDEFGHIJKLMNOPQRSTUVWXYZ"):
    x1 = origin.index(m1)
    x2 = origin.index(m2)
    y1 = origin.index(c1)
    y2 = origin.index(c2)
    n = len(origin)
    dxi = primefac.modinv(x1 - x2,n) %n
    a = dxi * (y1 - y2) % n
    b = (y1 - a * x1) % n
    return (a,b)
print fangshe_guessab("")

2.单表代替密码

（1）棋盘类密码

Playfair、Polybius、Nihilist均属于棋盘类密码。此类密码的密钥为5x5的棋盘，棋盘的生成符合条件：顺序随意，不得出现重复的字母，i和j可视为同一个字（也有将q去除的，以保证总数为25个）生成棋盘后，不同的加密方式使用了不同的转换方式，生成棋盘的代码如下：

def gen_cheese_map(k,use_Q=True,upper=True):
    k = k.upper()
    k0 = ""
    origin = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    for i in k:
        if i not in k0:
            k0 += i
            for i in origin:
                if i not in k0:
                    k0 += 1
                    if use_Q == True:
                        k0 = k0[0:k0.index("J")] + k0[k0.index("J") + 1:]
                    else:
                        k0 = k0[0:k0.index("Q")] + k0[k0.index("Q") + 1:]
                        if upper == False:
                            k0 = k0.lower()
                            assert len(k0) == 25
                            r =[]
                            for i in range(5):
                                r.append(k0[i * 5:i * 5 + 5])
                                return r
                            print gen_cheese_map("")

①Playfari加密解密的实现

#加密
 
def playfari_enchode(m,k = "",chesse_map = []):
    m = m.upper()
    origin = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    tmp = ""
    for i in m:
        if i in origin:
            tmp += i
            m = tmp
            assert k! = "" or chesse_map != []
            if chesse_map = []
            map = gen_cheese_map(k)
        else:
            map = chesse_map
            m0 = []
            idx = 0
            while idx < len(m):
                tmp = m[idx:idx + 2]
                if tmp[0] != tmp[1]:
                    m0.append(tmp)
                    idx += 2
                elif tmp [0] != "X":
                    m0.append(tmp[0] + 'X')
                    idx += 1
                else:
                    m0.append(tmp[0] + 'Q')
                    idx += 1
                if idx == len(m) - 1:
                    if tmp[0] != "X":
                        m0.append(tmp[0] + 'X')
                        idx += 1
                        r = []
                        for i in m0:
                            r.append(_playfari_2char(i,map))
                            return r
                        print playfari_enchode("")
                
 
#解密
 
 
def _playfari_2char_decode(tmp,map):
    for i in range(5):
        for j in range(5):
            if map[i][j] == tmp[0]:
                ai=i
                aj=j
                if map[i][j] == tmp[1]:
                    bi = i
                    bj = j
 
                    if ai = bi:
                        axi = ai
                        bxi = bi
                        axj = (aj - 1) % 5
                        bxj = (bj - 1) % 5
                    elif aj == bj:
                        axj = aj
                        bxj = bj
                        axi = (ai - i) % 5
                        bxi = (bi - i) % 5
                    else:
                        axi = ai
                        axj = bj
                        bxi = bi
                        bxj = aj
                        return map[axi] [axi] + map[bxi][bxj]
                    def playfair_decore[c,k = "",cheese_map = []]:
                    assert k != "" or cheese_map != []
                    if cheese_map == []:
                        map = gen_cheese_map(k)
                    else:
                        map = cheese_map
                        r = []
                        for i in c:
                            r.append(_playfari_2char_decode(i,map))
                            return "".join(r)
                        print playfair_decore("")

②Polybuis加密解密的实现（Nihilist原理相同）

#加密
 
def Polybuis_encode(m,k="",name = "ADFGX",cheese_map=[]):
    m = m.upper()
    assert k != "" or cheese_map != []
    if chesse_map == []:
        map = gen_cheese_map(k)
    else:
        map = cheese_map
        r =[]
        for x in m:
            for i in range(5):
                for j in range(5):
                    if map [i][j] == x:
                        r.append(name[i] + name[j])
                        return r
                    print Polybuis_encode("")
 
#解密
 
def Polybuis_decode(c,k = "",name = "ADFGX",cheese_map):
    assert k != "" or cheese_map != []
    if cheese_map == []:
        map = gen_cheese_map(k)
    else:
        map = cheese_map
        
        r = ""
        for x in c:
            i = name.index(x[0])
            j = name.index(x[1])
            r += map[i][j]
            return r
        print Polybuis_decode("")
    

3.维吉尼亚密码

维吉尼亚密码是标准的多表代替密码，多表代替密码的密钥不再是固定不变的，而是随着位置发生改变的，在维吉尼亚密码中，根据密钥的字母来选择。维吉尼亚密码爆破必须依赖爆破+词频来进行，网上有在线破解的方法。

4.希尔密码

希尔密码是运用基本矩阵论的原理替换密码，将每个字母当做26进制数字：A=0，B=1，C=2以此类推，将一串字母当成n维向量，与一个n x n的矩阵相乘，在将得出的结果mod26。