密码学实践（一）

前前后后忙了近半个月，总算是把实践弄完了
记录一下密码学的基础知识吧

单表替代密码

Caesar Cipher

恺撒密码（英语：Caesar cipher），或称恺撒加密、恺撒变换、变换加密，是一种最简单且最广为人知的加密技术。它是一种替换加密的技术，明文中的所有字母都在字母表上向后（或向前）按照一个固定数目进行偏移后被替换成密文。

def encrypt(plaintext, key):
    re_str = ""
    for i in plaintext:
        if not i.isalpha():
            re_str += i  # 判断是否为字母，若不是则不需要操作
        else:
            a = "A" if i.isupper() else "a"  
            # 根据当前字母是否大小写，确定其ASCII码范围值
            re_str += chr((ord(i) - ord(a) + key) % 26 + ord(a))
    return re_str

def decrypt(ciphertext, key):
    return encrypt(ciphertext, 26 - key)

Keyword Cipher

关键字（词）密码，给定一个关键字key（假定），得到关键字列表：“keyabcdfghijlmnopqrstuvwxz”，然后对照明文，按照“a”->“k”，“b”->“e”，…，来进行替换

def getKeywordList(keyword):
    """ 主要用于生成密码表 """
    normalList = ''
    keyword = keyword.lower()
    for i in range(26):
        normalList = normalList + chr(ord('a') + i)
    toCombine = keyword + normalList
    combineList = ''
    for i in toCombine:
        if i in combineList:
            pass
        else:
            combineList = combineList + i
    if len(combineList) == 26:
        return combineList
    else:
        return ''

def replaceChar(keywordList, inputChar):
    """
    对于大写字母，就先转换为小写然后继续调用改函数
    转换至小写字母后，得到该字母在字母表上的位置然后使用keywordList替换即可
    """
    if inputChar.isupper():
        return replaceChar(keywordList, inputChar.lower()).upper()
    else:
        return keywordList[ord(inputChar) - 97]

def dereplaceChar(keywordList, inputChar):
    """ 解密函数就是加密函数的逆过程 """
    if inputChar.isupper():
        return dereplaceChar(keywordList, inputChar.lower()).upper()
    else:
        return chr(keywordList.find(inputChar) + 97)

def encrypt(toReplace, keyword):
    """ keyword 字符替换法 替换函数 """
    afterReplace = ''
    keywordList = getKeywordList(keyword)
    for i in toReplace:
        if i.isalpha():
            afterReplace = afterReplace + replaceChar(keywordList, i)
        else:
            afterReplace = afterReplace + i
    return afterReplace

def decrypt(toReplace, keyword):
    """ keyword 字符替换法  反替换函数 """
    afterReplace = ''
    keywordList = getKeywordList(keyword)
    for i in toReplace:
        if i.isalpha():
            afterReplace = afterReplace + dereplaceChar(keywordList, i)
        else:
            afterReplace = afterReplace + i
    return afterReplace

Affine Cipher

仿射密码为单表加密的一种，字母系统中所有字母都藉一简单数学方程加密，对应至数值，或转回字母

def gcd(a, b):
    """ 求a，b的最大公因数，仿射密码中，a与b互素 """
    if a < b:
        a, b = b, a
    while b != 0:
        temp = a % b
        a = b
        b = temp
    return a

def egcd(a, b):
    """ 扩展欧几里得算法，用于之后求逆元 """
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

def modinv(a, m):
    """ 求逆元 """
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def encrypt(plaintext, a, b):
    """ 加密函数：E(x) = (ax + b)(mod m) m为编码系统中的字母数，一般为26 """
    cipher = ""
    for i in plaintext:
        if not i.isalpha():
            cipher += i
        else:
            n = "A" if i.isupper() else "a"
            cipher += chr((a * (ord(i) - ord(n)) + b) % 26 + ord(n))
    return cipher

def decrypt(ciphertext, a, b):
    """ 解密函数：D(x) = a^-1 * (x - b)(mod m) a^-1:a在m上的乘法逆元 """
    a1 = modinv(a, 26)
    plain = ""
    for i in ciphertext:
        if not i.isalpha():
            plain += i
        else:
            n = "A" if i.isupper() else "a"
            plain += chr((a1 * (ord(i) - ord(n) - b)) % 26 + ord(n))

Multiliteral Cipher

与棋盘密码相识，不过棋盘密码中是将字母替换为数字，而在Multiliteral中，是替换为字母
给出一个长度为5的单词，然后将26个字母排成5*5的矩阵，其中i和j合在一起，对照着明文的每一个字母，找到字母在矩阵中的位置，将其替换为key中相应位置的两个字母

def removePunctuation(text):
    filter = '[^A-Z]'
    return re.sub(filter, '', text.upper())

def encrypt(plaintext, key):
    """ 主要算法，获取加密字母在二维字母表中的行列值，其密文为与之对应的key中位置的相应字母 """
    plain = removePunctuation(plaintext).replace('J', 'I')
    key = key.upper()
    cipher = ''
    for i in range(len(plain)):
        row = int(keywordList.index(plain[i]) / 5)
        cipher += key[row]
        col = keywordList.index(plain[i]) % 5
        cipher += key[col]
    return cipher

def decrypt(ciphertext, key):
    """ 主要算法：对密文两两遍历，找到相应字母在key中的位置，分别对应明文在字母表中的行列 """
    cipher = removePunctuation(ciphertext).replace('J', 'I')
    key = key.upper()
    plain = ''
    for i in range(0, len(cipher), 2):
        row = key.index(cipher[i])
        col = key.index(cipher[i + 1])
        num = row * 5 + col
        plain += keywordList[num]
    return plain

多表替代密码

Vigenere Cipher

密码学经典加解密之一
直接百科

def encrypt(plaintext, key):
    """ vigenere密码就相当于Caesar密码，不同的是vigenere的密钥key是可变的几个值，然后使用这几个值进行加解密 """
    cipher = ''
    count = 0  # 设置一个计数器，当遇到非字母的时候加一，便于之后确定key
    key = key.lower()
    for i in range(len(plaintext)):
        if not plaintext[i].isalpha():
            cipher += plaintext[i]
            count += 1
        else:
            a = "A" if plaintext[i].isupper() else "a"
            offset = ord(key[(i - count) % len(key)]) - ord('a')  # offset:相当于Caesar中的key
            cipher += chr((ord(plaintext[i]) - ord(a) + offset) % 26 + ord(a))
    return cipher

def decrypt(ciphertext, key):
    """ 解密算法原理同Caesar """
    plain = ''
    count = 0
    key = key.lower()
    for i in range(len(ciphertext)):
        if not ciphertext[i].isalpha():
            plain += ciphertext[i]
            count += 1
        else:
            a = "A" if ciphertext[i].isupper() else "a"
            offset = ord(key[(i - count) % len(key)]) - ord('a')
            plain += chr((ord(ciphertext[i]) - ord(a) - offset) % 26 + ord(a))
    return plain

Autokey Cipher

Autokey就是Vigenere的一种变种，在Vigenere加密中，密钥是循环使用的，这样就有了被爆破的可能，在Autokey中，有两种形式，一种是Autokey Plaintext，就是将明文直接添加在key之后作为密钥进行加密，另一种是Autokey Ciphertext，是先用key加密得到的Cipher片段作为key循环进行加密
Plaintext与Ciphertext的加解密正好是相反的

def removePunctuation(text, filter='[^A-Z]'):
    return re.sub(filter, '', text.upper())

def encryptPlain(text, keyword):
    """
    对于Autokey Plaintext，本质上和vigenere相同，相当于将明文附加在key后面作为密钥来进行vigenere加密
    但明文中的空格、非字母字符会影响加密，所以在Autokey的加解密中将除去所有非字母字符，并将全部字母大写
    """
    text = removePunctuation(text)
    res = ""
    key = keyword.upper()
    for (i, c) in enumerate(text):
        if i < len(key):  # 明文前i项，使用key进行vigenere加密
            offset = ord(key[i]) - 65
        else:  # 从明文的i+1项，使用明文作为密钥进行vigenere加密
            offset = ord(text[i - len(key)]) - 65
        res += chr((ord(c) - 65 + offset) % 26 + 65)
    return res

def decryptPlain(text, keyword):
    """ 因为Autokey本质上是vigenere加密，所以在解密上唯一不同的点就是“-offset” """
    text = removePunctuation(text)
    res = ""
    key = keyword.upper()
    for (i, c) in enumerate(text):
        if i < len(key):
            offset = ord(key[i]) - 65
        else:
            offset = ord(res[i - len(key)]) - 65
        res += chr((ord(c) - 65 - offset) % 26 + 65)  # 不同点
    return res

def encryptCipher(text, keyword):
    """
    Autokey Cipher的加解密与Autokey Plain的解加密相对应
    但在求offset上不同，此处使用的与plain相反
    """
    text = removePunctuation(text)
    res = ""
    key = keyword.upper()
    for (i, c) in enumerate(text):
        if i < len(key):
            offset = ord(key[i]) - 65
        else:
            offset = ord(res[i - len(key)]) - 65
        res += chr((ord(c) - 65 + offset) % 26 + 65)
    return res

def decryptCipher(text, keyword):
    text = removePunctuation(text)
    res = ""
    key = keyword.upper()
    for (i, c) in enumerate(text):
        if i < len(key):
            offset = ord(key[i]) - 65
        else:
            offset = ord(text[i - len(key)]) - 65
        res += chr((ord(c) - 65 - offset) % 26 + 65)
    return res

多图替代密码

Playfair Cipher

密码详情见百科

def getKeywordList(keyword):
    """ 获取密钥矩阵 """
    keyword = keyword.upper().replace('J', 'I')
    normalList = 'ABCDEFGHIKLMNOPQRSTUVWXYZ'
    toCombine = keyword + normalList
    combineList = ''
    for i in toCombine:
        if i in combineList:
            pass
        else:
            combineList = combineList + i
    return combineList

def removePunctuation(text):
    """ 将文本中非英文字母去掉，并将字母转为大写 """
    filter = '[^A-Z]'
    return re.sub(filter, '', text.upper())

def encryptPart(keywordList, a, b):
    """
    加密主要算法：
    首先获取得到的两个字母在矩阵中的行列值
    然后对两个坐标分别进行判断：
    1.位于同一行，返回两个字母在矩阵中右边的字母
    2.位于同一列，返回两个字母在矩阵中下边的字母
    3.位于对角，返回相应对角字母
    """
    arow, acol = int(keywordList.index(a) / 5), keywordList.index(a) % 5
    brow, bcol = int(keywordList.index(b) / 5), keywordList.index(b) % 5
    if arow == brow:
        return keywordList[arow * 5 + (acol + 1) % 5] + keywordList[brow * 5 + (bcol + 1) % 5]
    elif acol == bcol:
        return keywordList[((arow + 1) % 5) * 5 + acol] + keywordList[((brow + 1) % 5) * 5 + bcol]
    else:
        return keywordList[arow * 5 + bcol] + keywordList[brow * 5 + acol]

def decryptPart(keywordList, a, b):
    """ 加密算法的逆运算 """
    arow, acol = int(keywordList.index(a) / 5), keywordList.index(a) % 5
    brow, bcol = int(keywordList.index(b) / 5), keywordList.index(b) % 5
    if arow == brow:
        return keywordList[arow * 5 + (acol - 1) % 5] + keywordList[brow * 5 + (bcol - 1) % 5]
    elif acol == bcol:
        return keywordList[((arow - 1) % 5) * 5 + acol] + keywordList[((brow - 1) % 5) * 5 + bcol]
    else:
        return keywordList[arow * 5 + bcol] + keywordList[brow * 5 + acol]

def encrypt(plaintext, key):
    """
    对获取的明文进行基本的处理
    转为大写
    除去非字母
    如果遇到两个相同的字母，在中间加'Q'
    文本长度不足2的倍数需要加'X'补齐
    然后以两两字母进行加密
    """
    plaintext = removePunctuation(plaintext).replace('J', 'I')
    plain = ""
    plain += plaintext[0]
    for i in range(1, len(plaintext)):
        if plain[len(plain) - 1] == plaintext[i]:
            plain += 'Q'
        plain += plaintext[i]
    keywordList = getKeywordList(key)
    if len(plain) % 2 == 1:
        plain += 'X'
    ret = ''
    for c in range(0, len(plain), 2):
        ret += encryptPart(keywordList, plain[c], plain[c + 1])
    return ret

def decrypt(ciphertext, key):
    """ 同加密 """
    cipher = removePunctuation(ciphertext).replace('J', 'I')
    keywordList = getKeywordList(key)
    if len(cipher) % 2 == 1:
        cipher += 'X'
    ret = ''
    for c in range(0, len(cipher), 2):
        ret += decryptPart(keywordList, cipher[c], cipher[c + 1])
    return ret

置换密码

Permutation cipher

给定一个顺序，例：1,4,5,3,2，然后将明文按照此顺序输出即可，例：abcde fghij -> adecb fijhg

def removePunctuation(text, filter='[^A-Z]'):
    return re.sub(filter, '', text.upper())

def inverseKey(key):
    """ 通过key获取解密时所需要的key的逆解 """
    inverse = []
    for i in range(min(key), max(key) + 1):
        inverse.append(key.index(i) + 1)
    return inverse

def encrypt(plaintext, key):
    """
    便于在之后对文本的遍历，首先将文本补齐，使其长度为密钥长度的整数倍
    然后开始分组遍历，通过对range参数的设置，使每次加密都对密钥长度的明密文进行加解密
    然后对组内明密文进行加解密
    """
    plaintext = removePunctuation(plaintext)
    cipher = ''
    for i in range(0, len(plaintext) % len(key) * -1 % len(key)):
        plaintext += "X"
    for i in range(0, len(plaintext), len(key)):  # 步长设置为密钥长度
        for j in [a - 1 for a in key]:
            cipher += plaintext[i + j]
        cipher += " "
    return cipher[:-1]

def decrypt(ciphertext, key):
    """ 得到逆密钥，然后和加密一样 """
    return encrypt(ciphertext, inverseKey(key))

Column permutation cipher

原理与置换密码相似，将明文按照key的长度排成矩阵，然后根据key中字母在字母表中的先后顺序输出每一列，即为密文
Double Translation Cipher即为两次列置换加密

def removePunctuation(text, filter='[^A-Z]'):
    return re.sub(filter, '', text.upper())

def sortind(key):
    """ 通过key获取加密顺序 """
    t1 = [(key[i], i) for i in range(len(key))]
    t2 = [(k[1], i) for i, k in enumerate(sorted(t1))]
    return [q[1] for q in sorted(t2)]

def unsortind(key):
    """ 通过key获取解密顺序 """
    t1 = [(key[i], i) for i in range(len(key))]
    return [q[1] for q in sorted(t1)]

def encrypt(plaintext, key):
    """ 加密函数 """
    plain = removePunctuation(plaintext)
    cipher = ''
    ind = sortind(key)
    for i in range(len(key)):
        cipher += plain[ind.index(i)::len(key)]
    return cipher

def decrypt(ciphertext, key):
    """ 解密函数 """
    cipher = removePunctuation(ciphertext)
    plain = ['_'] * len(cipher)
    l, m = len(cipher), len(key)
    ind = unsortind(key)
    upto = 0
    for i in range(len(key)):
        collen = int(l / m)
        if ind[i] < l % m:
            collen += 1
        plain[ind[i]::m] = cipher[upto:upto + collen]
        upto += collen
    return ''.join(plain)