[笔记] 密码学原理与实践笔记

Caesar Cipher

凯撒密码。所有的字母全部往后移3位。比如abc则变成def。

Shift Cipher

移位密码。和凯撒密码原理类似。只不过移动的key不是3而可以是0~25中的任何值。所以Caesar Cipher是Shift Cipher的一种特例。

下面写了两个移位密码的编码和解码的小程序。

import sys

if(sys.argv[1] == '-s'):
    plaintext = sys.argv[2]
    cipyertext = ""
    if (sys.argv[3] == '-n'):
        key = int(sys.argv[4]) % 26
        for word in plaintext:
            if (word <= "z" and word >= "a"):
                cipyertext += chr( (ord(word) + key - ord(&#x27;a&#x27;)) %26 + ord(&#x27;a&#x27;) )
            elif (word <= "Z" and word >= "A"):
                cipyertext += chr( (ord(word) + key - ord(&#x27;A&#x27;)) %26 + ord(&#x27;A&#x27;) )
            else:
                cipyertext += word
        print(cipyertext)
    else:
        print(f"unrecognized signal {sys.argv[3]}")
else:
    print(f"unrecognized signal {sys.argv[1]}")

import sys

if(sys.argv[1] == '-s'):
    ciphertext = sys.argv[2]
    plaintext = ""
    if (sys.argv[3] == '-n'):
        key = int(sys.argv[4]) % 26
        for word in ciphertext:
            if (word <= "z" and word >= "a"):
                plaintext += chr( (ord(word) - key - ord(&#x27;a&#x27;) + 26) %26 + ord(&#x27;a&#x27;) )
            elif (word <= "Z" and word >= "A"):
                plaintext += chr( (ord(word) - key - ord(&#x27;A&#x27;) + 26) %26 + ord(&#x27;A&#x27;) )
            else:
                plaintext += word
        print(plaintext)
    elif (sys.argv[3] == &#x27;--all&#x27; or sys.argv[3] == &#x27;-a&#x27;):
        for key in range(1, 26):
            plaintext = ""
            for word in ciphertext:
                if (word <= "z" and word >= "a"):
                    plaintext += chr( (ord(word) - key - ord(&#x27;a&#x27;) + 26) %26 + ord(&#x27;a&#x27;) )
                elif (word <= "Z" and word >= "A"):
                    plaintext += chr( (ord(word) - key - ord(&#x27;A&#x27;) + 26) %26 + ord(&#x27;A&#x27;) )
                else:
                    plaintext += word
            print(f"key: {key}   {plaintext}")
    else:
        print(f"unrecognized signal {sys.argv[3]}")
else:
    print(f"unrecognized signal {sys.argv[1]}")

Affine Cipher

仿射密码。和凯撒密码和移位密码类似。前两者都是在原字母的基础上加上一个常数k。而仿射密码则是在原字母的基础上乘上一个常数a，再加上一个常数b。当然最后都是需要模26的。

为了保证能够被解密，a和26必须是互素的，因为只有这样，a才有逆元，才能够解密。

求逆元可以用拓展欧几里得算法，脑子太笨，还看不懂算法的原理。

以下是加密和解密的脚本

import sys

if(sys.argv[1] == '-s'):
    plaintext = sys.argv[2]
    cipyertext = ""
    if (sys.argv[3] == '-a'):
        key1 = int(sys.argv[4])
        if (key1 in [1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25]):
            if (sys.argv[5] == '-b'):
                key2 = int(sys.argv[6])
                for word in plaintext:
                    if (word <= "z" and word >= "a"):
                        cipyertext += chr( ((ord(word) - ord(&#x27;a&#x27;)) * key1 + key2) % 26 + ord(&#x27;a&#x27;))
                    elif (word <= "Z" and word >= "A"):
                        cipyertext += chr( ((ord(word) - ord(&#x27;A&#x27;)) * key1 + key2) % 26 + ord(&#x27;A&#x27;))
                    else:
                        cipyertext += word
                print(cipyertext)
            else:
                print(f"unrecognized signal {sys.argv[5]}")
        else:
            print(f"error: a must be one of [1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25]")
    else:
        print(f"unrecognized signal {sys.argv[3]}")
else:
    print(f"unrecognized signal {sys.argv[1]}")

import sys

def ext_euclid(a, b):     
    if b == 0:         
        return 1, 0, a     
    else:         
        x, y, q = ext_euclid(b, a % b) 
        # q = gcd(a, b) = gcd(b, a%b)         
        x, y = y, (x - (a // b) * y)         
        return x, y, q

if(sys.argv[1] == '-s'):
    ciphertext = sys.argv[2]
    plaintext = ""
    if (sys.argv[3] == '-a'):
        key1 = int(sys.argv[4])
        if (key1 in [1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25]):
            key1_reverse = (ext_euclid(key1, 26)[0] + 26) % 26 #逆元
            if (sys.argv[5] == '-b'):
                key2 = int(sys.argv[6]) % 26
                for word in ciphertext:
                    if (word <= "z" and word >= "a"):
                        plaintext += chr( ((ord(word) - ord(&#x27;a&#x27;) - key2 + 26) * key1_reverse) % 26 + ord(&#x27;a&#x27;) )
                    elif (word <= "Z" and word >= "A"):
                        plaintext += chr( ((ord(word) - ord(&#x27;A&#x27;) - key2 + 26) * key1_reverse) % 26 + ord(&#x27;A&#x27;) )
                    else:
                        plaintext += word
                print(plaintext)
        else:
            print(f"error: a must be one of [1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25]")
    elif (sys.argv[3] == &#x27;--all&#x27;): #尝试所有的a,b组合
        for key1 in [1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25]:
            key1_reverse = ((ext_euclid(key1, 26))[0] + 26) % 26
            for key2 in range(1, 26):
                plaintext = ""
                for word in ciphertext:
                    if (word <= "z" and word >= "a"):
                        plaintext += chr( ((ord(word) - ord(&#x27;a&#x27;) - key2 + 26) * key1_reverse) % 26 + ord(&#x27;a&#x27;) )
                    elif (word <= "Z" and word >= "A"):
                        plaintext += chr( ((ord(word) - ord(&#x27;A&#x27;) - key2 + 26) * key1_reverse) % 26 + ord(&#x27;A&#x27;) )
                    else:
                        plaintext += word
                print(f"a: {key1} b: {key2}  {plaintext}")
    else:
        print(f"unrecognized signal {sys.argv[3]}")
else:
    print(f"unrecognized signal {sys.argv[1]}")

仿射密码的密钥空间是$\phi(26)*26=312$ϕ(26)∗26=312 遍历起来还是很快的。

仿射密码是线性的，于是为了提高加密强度，便出现了非线性加密方式，比如以下的单表代替。

Monoalphabetic Substitution Ciphers

单表代替密码，其实就是用了一张表，将明文中的字母做一个转换，形成密文。

它的密钥空间十分庞大，即把每一种表的可能都试一遍，当然这个表中的字母不能重复，所以密钥空间是$26! = 403291461126605635584000000$26!=403291461126605635584000000。

从表面上来看，单表代替貌似十分危险，毕竟很难通过暴力测试的方式得到明文。

但是这种单表替换中传承了一个英语的巨大的特征——字母的频率。

我们可以分析明文中各个字母的频率来猜测字母的对应顺序。

以下是统计给定字符串中各个字母的个数并按降序排序的脚本。

import sys

dict = {}
ciphertext = sys.argv[1]
alphanum = 0
for i in ciphertext:
    if (i.isalpha()):
        if (i.lower() in dict.keys()): #已经有键
            dict[i.lower()] += 1
        else:
            dict[i.lower()] = 1
        alphanum += 1
dict = sorted(dict.items(), key=lambda x:x[1], reverse=True)
print(dict)

为了消除密文中的这种频率信息，又有了多表代替密码和多名代替密码。

Vigenere Cipher

维吉尼亚密码就是一种多表代替密码Polyalphabetic Substituton Ciphers。下面我用我的理解来说一下为什么维吉尼亚密码是一种多表代替密码。

假设维吉尼亚的密钥只有一个字母"b"。由于在维吉尼亚密码中"a"实际上是0，那么"b"就是1，所以实际上这时就是偏移为1的移位密码。效果如下。

而这里其实就是一张特殊的单表。

B C D E F …

所以这里也可以看到凯撒密码和移位密码都属于单表密码，都可以用频率分析来得到明文。

而如果维吉尼亚密钥中有两个字母呢？比如说"bc"。很容易想到，这时候其实是有两张表的。奇数位明文用的是"b"的表，而偶数位明文用的是"c"的表。

这就是我理解的多表。

维吉尼亚加密起来非常简单，其实就是做一个ascii变化。代码如下。

import sys

plaintext = sys.argv[1].lower()
key = sys.argv[2].lower()
ciphertext = ""
num = 0
for i in plaintext:
    if (i.isalpha()):
        ciphertext += chr((ord(i) - ord('a') + (ord(key[num % len(key)]) - ord('a'))) % 26 + ord('a'))
        num +=1
    else:
        ciphertext += i
print(ciphertext)

如果知道密钥的话，解密也是十分简单的。

import sys

ciphertext = sys.argv[1].lower()
key = sys.argv[2].lower()
plaintext = ""
num = 0
for i in ciphertext:
    if (i.isalpha()):
        plaintext += chr((ord(i) - ord('a') - (ord(key[num % len(key)]) - ord('a')) + 26) % 26 + ord('a'))
        num +=1
    else:
        plaintext += i
print(plaintext)

那如果我们不知道密钥如何破解维吉尼亚密码呢？由于密钥中每个字母都单独对应一个移位密码表，这就导致明文中同一个字母可能被不同的表加密，从而产生出不同的密文字母，从而整体的频率信息将被破化。看似是坚不可摧了。不知道密文，密钥空间将成为26^n，同时还”消除“了单表代替拥有的频率信息。

实际上频率信息仍然存在着，只不过不是整体的密文体现出来的，我们需要对密文进行分组，分组的依据是模密文长度的余数。

比如这个将 “wuuconixyyds” 用 "abc"加密产生的密文 “wvwcppiyayeu”。将密文每三个分为一组。

可以看到，分好之后，每组的密文字母加密时其实用的都是同一个表，比如"wciy"实际上都是用"a"的表，其实就是没动2333。

其实也就是由于密钥是循环使用的，会导致分组之后的密文重新表现出英文字母的频率性。

说是频率性，其实每一组密文都是移位后的结果 ，我们完全可以遍历所有的偏移来尝试。

但是这里有一个问题，平常我们破解移位密码的时候，就是遍历所有的移位，然后观察每种可能移位解密的结果，去看文本是否有意义。但是这里每组的字母在密文整体中是分散的，这就导致我们无法通过肉眼去判断尝试的偏移是否正确，从而无法判断。

那不弄偏移了，直接看频率来分析。但是很快就也会发现这个问题，我们在破解单表密码的频率分析中充斥着猜测。因为许多字母的频率都是十分相近，除了能够远超其他 字母的e一马当先，其他字母我们都需要代入文本，看看是否组成某个单词等等来猜测。这时我们遇到了和爆破移位同样的问题，即组内密文是离散的，它们无法组成有意义的单词或句子，我们就无法进行猜测了。

这个问题困扰了我很久，便去咨询了密码学大佬shrimpwr。他给出了一个方法，即遍历了偏移，又分析了频率，而且分析的频率不依靠人眼，而真正依靠数学，可以实现全自动化破译。

过程如下。

大体就是去统计密文中各个字母的频率，从"a"到"z"的频率分别和正常文本的“a”到"z"的频率相乘，并把这26个乘数相加，得到一个相关值 Correlation。

然后去模拟偏移，得到26个相关值，这26个相关值中的最大值对应的偏移就是移位的偏移。

为什么正确的偏移的时候相关值最大呢？因为正确偏移的时候，我们相当于做了一遍"a"乘"a"的频率加到"z"乘"z"的频率，即各个字母频率的平方和。在这种情况下 ，最大的频率e会乘上自己，强强联合，实现最大值，最小的频率会乘上自己，自生自灭，不去影响别的大频率，我们想象一下也能得到这种情况是得到的总和是最大的。利用这种方法我们根本就不需要去手动尝试，直接就得出结果了。

以下是脚本 。

q=[ 0.08167, 0.01492, 0.02782, 0.04253, 0.12702, 0.02228, 0.02015, 0.06094, \
    0.06966, 0.00153, 0.00772, 0.04025, 0.02406, 0.06749, 0.07507, 0.01929, \
    0.00095, 0.05987, 0.06327, 0.09056, 0.02758, 0.00978, 0.02360, 0.00150, \
    0.01974, 0.00074 ] #一般文本a~z频率
dict = {} #密文各个字母的个数
for i in range(0, 26): #各字母个数初始化为0
    dict[chr(ord('a') + i)] = 0

ciphertext = ""
with open("ciphertext.txt", "r") as f: #文本中读入密文
    ciphertext = f.read().lower()

alphanum = 0
for i in ciphertext:
    if (i.isalpha()):
        if (i in dict.keys()):
            dict[i] += 1
        alphanum += 1

p = []
for i in range(0, 26):
    p.append( round(dict[chr(ord('a') + i)] / alphanum, 3))

correlations = []
for i in range(0, 26): #模拟偏移，计算correlation
    correlation = 0
    for j in range(0, 26): #26个字母的频率相乘
        correlation += q[j] * p[(j + i - 26) % 26]
    correlations.append(round(correlation, 3))

shift = correlations.index(max(correlations))
print(f"偏移：{shift}  相关值: {max(correlations)}")

with open("result.txt", "w") as f:
    plaintext = ""
    for i in ciphertext:
        if i.isalpha():
            plaintext += chr( (ord(i) - ord('a') - shift + 26) % 26 + ord('a'))
        else:
            plaintext += i
    f.write(plaintext)
    print("result saved in 'result.txt'")

这种方法甚至对一些很短的句子都有效果。

这个句子中中甚至都没有"e"，要手工去分析频率几乎是噩梦，但是用这种方法就是游刃有余了。

好了，现在我们对如何破译每组的密文已经很有把握了，那如何对密文进行分组呢？很显然 ，我们需要知道密钥长度。

但是密钥长度可不是一开始就给你的，破译密钥长度有两种方法，一种是Kasiski Test，它的思路就是由于密钥的循环利用，可能能遇到明文中相同单词用相同密钥部分加密的情况，这就导致密文的一致。我们可以在密文中查找这种一样的，记录它们的距离，距离的公因数就是密钥长度。这种方法感觉脚本编写起来非常麻烦，需要匹配相同字符串，感觉更适合用眼睛看。第二种就十分优秀了，重合指数法，它的思路就是在正常的英文文本中，两个字母重复的概率是接近于"0.065"的，而完全随机的文本的概率则接近"0.038“，而且这个重合指数计算 起来也非常容易，只需要计算字母的频率的平方和即可。所以它非常适合来自动化破解密钥长度。

下面是一段计算重合指数的脚本。

import sys

if (sys.argv[1] == "-h" or sys.argv[1] == "--help" or sys.argv[1] == "help"):
    print("python3 IndexOfCoincidence.py [-s string] [-f filepath]")
    exit(0)
ciphertext = ""
if (sys.argv[1] == "-s"):
    ciphertext = sys.argv[2].lower()
elif (sys.argv[1] == "-f"):
    with open(sys.argv[2], "r") as f:
        ciphertext = f.read().lower()
else:
    print("error. please type -h for more information")
    exit(0)

f = [] #频数
for i in range(0, 26):
    f.append(0) #每个位置对应相依字母，初值置零
alphancount = 0
for i in ciphertext:
    if i.isalpha():
        f[ord(i) - ord('a')] += 1
        alphancount += 1
p = [] #对应频率
ioc = 0
for i in range(0, 26):
    p.append(round(f[i] / alphancount, 3))
    ioc += (f[i] / alphancount) ** 2
print(round(ioc, 4))

我们尝试一下不同的文本，来看看它们的重合指数。

高于正常文本的0.065。

这里简爱中的一句话比之前的flag更加接近理想值。

当尝试简爱中的一个段落的重合指数时更加接近理想值。

当我们把目标变成简爱的第一个章节的时候，重合指数已经稳稳的变成理想值了。

在确定密钥长度时，我利用的方法是计算和理想值的差值，差值最小的那组就是密钥的长度。但是这就需要要求密文的文本较长，否则就像这里的第一个和第二个例子，与理想值差的有些多了，到时候差值也会很大，很可能就被认为不是密钥长度了。

以下是我的维吉尼亚密码最终解密脚本，包含输入密钥的普通解密和不输入密钥的自动破译。

import copy
import sys

def get_key_length(ciphertext):
    dict_model = {} #记录组内各个字母的个数
    for i in range(0, 26):
        dict_model[chr( ord('a') + i )] = 0
    differences = []
    for i in range(1, 10):
        ll = [] #存各组密文字典的列表 
        for j in range(0, i): #加入对应个数的字典
            dict = copy.deepcopy(dict_model) #深拷贝，防止一个变了另一个也变
            ll.append(dict) 
        num = 0
        for c in ciphertext:
            if c.isalpha():
                ll[num % i][c] += 1
                num += 1
        difference = 0
        for dict in ll:
            ioc = 0
            for j in range(0, 26):
                ioc += (dict[chr( ord('a') + j )] / (num // i)) ** 2 #注意这里每组的ioc除以的总数是单组的字母总数，而不是所有的字母总数
            difference += abs(ioc - 0.065) #计算重合指数和0.065的绝对差值
        differences.append(round(difference / i, 3))    #平均插值

    key_length = differences.index(min(differences)) + 1
    return key_length

def get_shift(ciphertext):
    q=[ 0.08167, 0.01492, 0.02782, 0.04253, 0.12702, 0.02228, 0.02015, 0.06094, \
    0.06966, 0.00153, 0.00772, 0.04025, 0.02406, 0.06749, 0.07507, 0.01929, \
    0.00095, 0.05987, 0.06327, 0.09056, 0.02758, 0.00978, 0.02360, 0.00150, \
    0.01974, 0.00074 ] #一般文本a~z频率
    dict = {} #密文各个字母的个数
    for i in range(0, 26): #各字母个数初始化为0
        dict[chr(ord('a') + i)] = 0

    for i in ciphertext:
        dict[i] += 1

    p = []
    for i in range(0, 26):
        p.append( round(dict[chr(ord('a') + i)] / len(ciphertext), 3))

    correlations = []
    for i in range(0, 26): #模拟偏移，计算correlation
        correlation = 0
        for j in range(0, 26): #26个字母的频率相乘
            correlation += q[j] * p[(j + i - 26) % 26]
        correlations.append(round(correlation, 3))

    shift = correlations.index(max(correlations))
    return shift

def decode(ciphertext, key):
    plaintext = ""
    num = 0
    for i in ciphertext:
        if (i.isalpha()):
            plaintext += chr((ord(i) - ord('a') - (ord(key[num % len(key)]) - ord('a')) + 26) % 26 + ord('a'))
            num +=1
        else:
            plaintext += i
    with open("result.txt", "w") as f:
        f.write(plaintext)
    print("result saved  in 'result.txt'")
    if (len(plaintext) < 100):
        print(plaintext)

if __name__ == "__main__":
    if (sys.argv[1] == &#x27;-h&#x27; or sys.argv[1] == &#x27;--help&#x27; or sys.argv[1] == &#x27;help&#x27;):
        print("python3 vigenere_decode.py [-f filepath] [-s string] [-k key]")
        exit(0)
    if (sys.argv[1] == &#x27;-f&#x27;):
        ciphertext = ""
        with open(sys.argv[2], "r") as f:
            ciphertext = f.read().lower()
    elif (sys.argv[1] == &#x27;-s&#x27;):
        ciphertext = sys.argv[2]
    
    try:
        if (sys.argv[3] == &#x27;-k&#x27;):
            decode(ciphertext, sys.argv[4])
    except Exception: #报错说明没有-k，需要去爆破密钥值
        key_length = get_key_length(ciphertext)
        groups = []
        for i in range(0, key_length):
            groups.append("")
        num = 0
        for i in ciphertext:
            if i.isalpha():
                groups[num % key_length] += i
                num += 1
        key = ""
        for i in groups:
            key += chr( ord(&#x27;a&#x27;) + get_shift(i) )
            decode(ciphertext, key)

这里举几个例子，我们先从对解密脚本简单的情况开始，直接把简爱第一章的密文丢给它看看能不能解密出来。

先用加密脚本加密一下，密钥为wuuconix

1

python3 vigenere_encdoe.py -f "plaintext.txt" -k wuuconix

成功解密。

再把难度提升一些，只弄一个段落。

也成功了。再直接用第一句话试试。

失败了2333，果然密文太少了，利用重合指数法就不准了。

Hill Cipher

希尔密码，于1929年发明，利用基本的矩阵来进行替换。它是一种多名代替密码 Polygraphic Substitution Ciphers。

下面我来讲一下我对Monoalphabetic Ciphers,Polyalphabetic Ciphers和Polygraphic Ciphers的理解。

单表代替，每个明文字母只有一种特定的置换方式。

多表代替，每个明文字母会根据在明文中位置的不同，可能有不同的置换方式。(Vigenere Cipher)

多名代替，就是把所有的明文字母一起加密成某个密文，如下图。我们以第一个密文字母c1为例。

$c_1 = m_1*k_{11}+m_2 * k_{21}+m_3*k_{31}+m_4*k_{41}$c1=m1∗k11+m2∗k21+m3∗k31+m4∗k41

我们可以看到第一个密文的加密过程中运用到了所有的明文字母，这大概就是多名的意义了。

希尔密码的密钥需要是一个可逆矩阵，这样才能够被正确解密。

在不知道密钥的情况下也能被破译，但是我已经看不懂了（

希尔加密运用到了现代数学的矩阵知识。希尔密码也很难用人力来加密和解密，但是在现代计算机强大的算力下也被证明是可破译的。

维基百科Polygraphic substitution - Wikipedia也把希尔加密称为是古典密码和现代密码的分界线。

In 1929, Lester S. Hill developed the Hill cipher, which uses matrix algebra to encrypt blocks of any desired length. However, encryption is very difficult to perform by hand for any sufficiently large block size, although it has been implemented by machine or computer. This is therefore on the frontier between classical and modern cryptography.

Permutation Cipher

之前讲的所有密码都属于代替密码，就是通过某种规则把明文的字母代替为另外的字母。

接下来 讲的置换密码Permutation Cipher（又叫做Transpostion Cipher）是什么意思呢？实际上就是把明文中的字母打乱，换个顺序。

下面举几个例子。

1. 铁轨密码 Rail Fence Cipher Rail fence cipher - Wikipedia

   实际上就是把明文按照WWWW的形式来写，然后一行一行读，同时为了可读性，每5个密文加个空格。

   比如flag{wuuconix_yyds}的加密过程

1. f...{...c...x...d..
   .l.g.w.u.o.i._.y.s.
   ..a...u...n...y...}
   

   它最终的密文就是 f{cxd lgwuo i_ysa uny}

2. 三角密码 Triangle Transposition Ciphe

   大概就是把明文以金字塔的方式以从横向写出来。

   然后以竖向的方式读出来就成了密文。

3. 

4. 铝带密码Scytale Cipher

   这就非常牛逼了，把密文绕着斯巴达加密棒绕一圈就可以得到密文。

5. 

6. 块置换加密 Block Permutation Cipher

   举一个例子，明文wuuconix，密钥flag

   我们现根据密钥字母在字母表中的次序写出一下次序2413。即f在flag中排第三位，a在flag中排第一位…

   然后我们根据密钥长度，即4。每行写4个字母，把明文写成一个方块。

onix

然后我们根据刚刚得到的次序2413。先读第2列，再读第4列…得到密文uncxwoui。

知道密钥解密的话也很简单，我们知道密钥flag的情况下，就可以知道一行有4个字母，而密文uncxwoui有八个字母，所以可以推断一列有2个字母，然后再分别写到各个列上，再按行读，就能得到明文啦！

Product Cipher

乘积密码被称为古典密码和现代密码的桥梁。

实际上就是对操作进行进行迭代，比如两次移位，两次代替，两次置换。还可以代替后置换。

Block Cipher

分组密码。根据我的理解，分组密码的和我们之前写的古典密码不同点就在于，它的明文、密钥和密文都是用二进制表示的。

In cryptography, a block cipher is a deterministic algorithm operating on fixed-length groups of bits, called blocks.

一般来说n位的明文会被加密问n位的密文。但是密钥的长度不一定是n位，可能不一样 。

分组加密一般内部运用的加密方式，无非就是代替和置换。

代替的目的是为了混淆 Substitution for Confusion。

置换的目的是为了扩散 Permutation for Diffusion。

在现代分组密码Modern Block Cipher之中，一轮中通常都有一个代替-置换网络Substitution-Permutation Network 可以简写为SPN。

SPN的代替元素被称为S盒S-box。置换元素被称为P盒P-box。

这个SPN可以说是很多现代分组密码的的基础，比如DES,AES,RC6…

DES

Data Encryption Standard。数据加密标准。

它的明文输入是64位二进制，输出同样。密钥输入看似也是64位，但是其8,16,24...位在置换中被丢弃，实际上起作用的密钥只有56位。

下面我简单说一下DES的大体流程。先说明文的处理过程。

64位的明文传入后，首先需要进行一个初始置换 Initial Permutation。

置换完之后将结果分为两部分，左32位称为$L_0$L0，右32位称为$R_0$R0。

$L_0$L0划水。开始对$R_0$R0进行处理。首先32位的$R_0$R0首先需要进行一次拓展置换 Expansion Permutation，将32位猛增为48位，为什么需要把位数扩大呢？因为每轮的密钥实际上是48位的，这个之后说，将$R_0$R0拓展为48位之后，就可以和密钥进行操作了。

$R_0$R0拓展成为48位后，与密钥进行按位与运算。

然后48位的$R_0$R0将进入8个S-box。将48位重新变为32位。

S-box是怎么实现的位数的减少的呢？我们知道 ，一共有8个S盒，所有的输入一共48位，相当于每个S盒处理6位。

我们看这个S盒一共有4行16列，一共64个元素，每行的元素都是0~15。

假设我们的S-box 8的输入是101100一共六位，拿出第一位和最后一位10，转为为十进制就是2，于是我们就选择第二行。中间的四位0110是6，于是我们选择第六列，所以就是第二行第六列，即14。再将14转化为二进制1110。所以最后S-box 8的输出就是4位二进制数1110。从原来的输入的六位变成了输出的四位。一共有8个类似的S盒，每个S盒的输出都是4位，总共的输出就是32位啦！

经过S盒的处理之后再经过一个P盒置换一下，仍然是32位。

将这32位和一直在摸鱼的$L_0$L0按位与一下，就得到了$R_1$R1。$R_1$R1有了，$L_1$L1怎么来呢？左半部分全程摸鱼，$L_1$L1直接等于$R_0$R0哈哈。

以下为DES一轮的流程图。

连续经过16轮这样一样的操作，最后得到$L_{16}$L16和和$R_{16}$R16。把这两个32位二进制位拼接起来 ，但是这里要注意 ，$R_{16}$R16要拼在前面 ，即$R_{16}+L_{16}$R16+L16。我们可以这样理解，这16轮，左半部分全程划水，右半部分奋力拼搏，所以最后把右半部分放在前面以资鼓励2333。

拼接完成得到64位二进制位，这个64位二进制位最后再做一个逆初始置换 Reverse Initial Permutation，这个置换是初始置换的逆。

转置好了就得到 我们的64位密文啦！

以上讲了明文到密文的过程。但是还没有将密钥是如何生成的。刚刚我们讲到和$R_0$R0做与运算的密钥是48位的，那我们输入的64位密钥是怎么变成每轮的48位密钥 的呢？先把流程图放这里吧。

64位密钥输入，首先经过一个叫PC1 Permuted Choice 1的置换。这个置换会把8,16,24..的位数丢失。以下是PC1的具体内容。

58 50 42 34 26 18 10 2 59 51 43 35 27 19 11 3 60 52 44 36 63 55 47 39 31 23 15 7 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4

我们可以发现它是7行8列，一共56个元素，并且仔细观察的话，是没有8的倍数的值的，这就导致原始64位密钥的8倍数的下标的值被丢弃，最终成为56位。

得到的56位二进制数，我们还是把它分为左右两个部分，分别叫$C_0$C0和$D_0$D0。然后$C_0$C0和$D_0$D0需要分别进行循环左移。左移几位呢？我们需要按照这个表来行动。

我们可以看到是左移1位。我们将$C_0$C0和$D_0$D0分别循环左移一位后，再将两者合并，再进行 一次PC2 Permuted Choice 2的置换。这个置换将56位又减少为48位。以下是PC2的值。

3 28 15 6 21 10 23 19 12 4 26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32

是8行6列的，一共48位元素。我们可以发现原56位二进制中的9，18，22，25，35，38，43，54不在此表中，被丢弃。

经过这个PC2得到的48位将成为第一轮密钥$K_1$K1，在$R_0$R0转化为$R_1$R1过程中发挥作用。

以上就是DES的全部原理了，看似很复杂，但是实际上还是比较简单的，无非就是置换、代替、按位与，然后轮数多了点，人手算那肯定是要命的。现代密码就需要用计算机来实现加密和解密。下面我来分析一下加密和解密的脚本编写的难点。

明文和密钥的初始值都是64位的，我们肯定不能写64个01，那太麻烦了，而且那样也没啥意思，加密算法是让我们用来加密某种有意义的信息的，所以我们这里用8个字符来作为明文，8个字符来作为密文。比如我们的明文就是8个字符的字符串wuuconix。要怎么把它转化为64位二进制位呢？实际上也非常简单，每个字符都ascii码值，我们直接把它的二进制码值转化为二进制位就行了，但是由于ascii码一共只有127个，也就是最多7位二进制，所以前面需要手动补零。有些ascii码小的字母缺的位数可能大于1个，我们需要补零补到8位。

"0" + bin(ord('w'))[2:]

然后我们还需要解决的一个问题就是置换如何实现。在许多参考资料中，置换表都是一个方块，那是不是需要用一个二维列表来存储呢？

其实不用，经过我的实验，直接把置换表写成一行反而更加清楚。

这里我举一个例子，为了观察方便 ，就不用01了。

输入abcd。置换表为2 3 1 4。这个置换表里的值是什么意思呢？其实就是在输入字符串里的字符下标，分别取出第二位b，第一位a，依次类推，我们将取出来的字符进行合并，就得到了bcad。这就是置换结果了，十分方便。所有的置换表都可以这要来考虑，写出来的脚本也非常简单易懂。

permutation_table = [2, 3, 1, 4]
input = "abcd"
output = ""
for i in permutation_table:
	output += input[i - 1]
print(output)

置换就是这么简单，就是遍历置换表的值，拿到下标，从输入字符串对应下标出拿到字母加入到输出字符串中。

以上就是我认为的脚本实现DES的难点了，其他的就十分简单了。以下是DES加密和解密脚本。

def get_bin(alpha, mod):
    alpha_bin = ""
    if (mod == "encode"):
        for i in alpha :
            bit = bin(ord(i)).replace("0b", "")
            while (len(bit) < 8): #有些ascii不足7位，在前面补零
                bit = "0" + bit
            alpha_bin += bit
    elif (mod == "decode"):
        alpha_bin = bin(int(alpha, 16))[2:]
        while(len(alpha_bin) < 64):
            alpha_bin = "0" + alpha_bin
    return alpha_bin

def get_key(key_alpha):
    #key_alpha表示密钥的字母形态
    pc1 = [ 57,49,41,33,25,17,9,1,58,50,42,34,26,18,10,2,59,51,43,35,27,19,11,3,60,52,44,36,63,55,47,39,31,23,15,7,62,54,46,38,30,22,14,6,61,53,45,37,9,21,13,5,28,20,12,4 ]
    pc2 = [ 14,17,11,24,1,5,3,28,15,6,21,10,23,19,12,4,26,8,16,7,27,20,13,2,41,52,31,37,47,55,30,40,51,45,33,48,44,49,39,56,34,53,46,42,50,36,29,32 ]
    shift = [ 1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1 ] #每轮左移的位数
    key_alpha_bin = get_bin(key_alpha, "encode") #密钥字母的二进制形态
    key_pc1 = ""
    for i in pc1: #将密钥二进制形态做pc1，得到56位密钥
        key_pc1 += key_alpha_bin[i - 1] #位置1实际上是列表的0
    c, d = key_pc1[0:28], key_pc1[28:] #左半和右半
    keys = [] #存放每轮加密真正要用的48位密钥
    for i in range(0, 16):
        if (shift[i] == 1):
            c = c[1:28] + c[0]
            d = d[1:28] + d[0]
        elif (shift[i] == 2):
            c = c[2:28] + c[0] + c[1]
            d = d[2:28] + d[0] + d[1]
        cd = c + d #cd合并
        key = ""
        for i in pc2:
            key += cd[i - 1]
        keys.append(key)
    return keys

def des(data_alpha, key_alpha, mod):
    ip = [58,50,42,34,26,18,10,2,60,52,44,36,28,20,12,4,62,54,46,38,30,22,14,6,64,56,48,40,32,24,16,8,57,49,41,33,25,17,9,1,59,51,43,35,27,19,11,3,61,53,45,37,29,21,13,5,63,55,47,39,31,23,15,7]
    ep = [32,1,2,3,4,5,4,5,6,7,8,9,8,9,10,11,12,13,12,13,14,15,16,17,16,17,18,19,20,21,20,21,22,23,24,25,24,25,26,27,28,29,28,29,30,31,32,1]
    s = [[14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7,0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8,4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0,15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13], \
        [15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10,3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5,0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15,13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9], \
        [10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8,13,7,0,9,3,4,6,10,2,8,5,14,12,11,15,1,13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7,1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12], \
        [7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15,13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9,10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4,3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14], \
        [2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9,14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6,4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14,11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3], \
        [12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11,10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8,9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6,4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13], \
        [4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1,13,0,11,7,4,9,1,10,14,3,5,12,2,15,8,6,1,4,11,13,12,3,7,14,10,15,6,8,0,5,9,2,6,11,13,8,1,4,10,7,9,5,0,15,14,2,3,12], \
        [13,2,8,4,6,15,11,1,10,9,3,14,5,0,12,7,1,15,13,8,10,3,7,4,12,5,6,11,0,14,9,2,7,11,4,1,9,12,14,2,0,6,10,13,15,3,5,8,2,1,14,7,4,10,8,13,15,12,9,0,3,5,6,11]]
    p = [16,7,20,21,29,12,28,17,1,15,23,26,5,18,31,10,2,8,24,14,32,27,3,9,19,13,30,6,22,11,4,25]
    ip_reverse = [40,8,48,16,56,24,64,32,39,7,47,15,55,23,63,31,38,6,46,14,54,22,62,30,37,5,45,13,53,21,61,29,36,4,44,12,52,20,60,28,35,3,43,11,51,19,59,27,34,2,42,10,50,18,58,26,33,1,41,9,49,17,57,25]
    data_alpha_bin = get_bin(data_alpha, mod)
    data_ip = ""
    for i in ip:
        data_ip += data_alpha_bin[i - 1]
    l, r = data_ip[0:32], data_ip[32:64] #左半右半
    keys = get_key(key_alpha) #获得16轮的密钥列表
    range_ = range(0,16) if mod == "encode" else range(15, -1, -1)
    for wheel in range_: #wheel代表轮数，取自车轮意
        r_ep = ""
        for i in ep:
            r_ep += r[i - 1]
        key = keys[wheel]
        r_ep_xor = ""
        for i in range(0, 48):
            r_ep_xor += str(int(r_ep[i])^int(key[i]))
        r_s_i = [] #s-box的输入，一共8个，每个为六个字母
        for i in range(0, 8):
            s_i_temp = r_ep_xor[i * 6 : i * 6 + 6]
            r_s_i.append(s_i_temp)
        r_s_o = ""
        for i in range(0, 8):
            si = r_s_i[i]
            row = int(si[0]) * 2 + int(si[5])
            column = int(si[1]) * 8 + int(si[2]) * 4 + int(si[3]) * 2 + int(si[4])
            index = row * 16 + column
            so_int = s[i][index]
            so_bin = bin(so_int).replace(&#x27;0b&#x27;, &#x27;&#x27;) #转化为二进制
            while len(so_bin) < 4: #补零
                so_bin = "0" + so_bin
            r_s_o += so_bin
        r_p = ""
        for i in p:
            r_p += r_s_o[i - 1]
        r_next = ""
        for i in range(0, 32):
            r_next += str(int(l[i])^int(r_p[i]))
        l = r #L1 = R0
        r = r_next #R1 = F(L0, R0, Key1)
    data_preout = r + l #最后一步逆转置置换时r在前面
    data_code_bin = "" #密文/明文2进制形态,这里的code表示包含了encode和decode
    for i in ip_reverse:
        data_code_bin += data_preout[i - 1]
    data_code_hex = hex(int(data_code_bin, 2))[2:]
    while (len(data_code_hex) < 16): #密文/明文前面全部为零的情况下直接转化为16进制可能少位数，需要补零
        data_code_hex = "0" + data_code_hex
    if (mod == "decode"):
        data_code_alpha = ""
        for i in range(0, 8):
            bytes_ascii = chr(int(data_code_hex[i * 2 : i * 2 + 2], 16))
            data_code_alpha += bytes_ascii
        return data_code_alpha
    else:
        return data_code_hex

result = des("flagyyds", "wuuconix", "encode")
print(f"des加密结果:{result}")
result = des("46edc4a79ab0f007", "wuuconix", "decode")
print(f"des解密结果:{result}")

Block Cipher——Mode of Operation

由于分组密码加密的对象都是二进制位，而我们输入的明文一般都是字母，比如DES要求明文位64位，也就是8个字母，但是我们实际上要加密的数据肯定不止64位，实际工作中就需要对数据进行处理。分组密码主要有5种工作模式。

1. ECB Electronic Codebook Book 电码本模式。这个思想十分简单 ，就是把明文和密文分组，每组就是那个我们需要的位数。

   因为每组独立，无错误传播。还可以并行处理。

   但是它也有缺点，就是这种方式当某两组的明文同样的话，由于它们的密钥是相同的56位密钥，这就导致它们加密出来的结果也是一样的。

   以下是用ECB方式加密的图片，表现出了明显的轮廓特征。所以一般ECB只会用来加密一些长度很小的内容，比如加密密钥 。

2. 

3. 

4. CBC Cipher Block Chaining 密文链接模式。CBC的特点就是它的每一组的密文都会影响到下一组的加密，因为它和下一组的明文做了按位与的操作。同时由于除了第一组外每一组都会接受前面一组的密文，为了保证统一性，第一组明文会给它一个初始向量IV。

   我们可以很容易知道，CBC会有错误传播，也就是说前一轮密文的错误会影响到后一轮的密文。同时因为一环扣一环，无法做到并行处理。

   有错误传播不是说这个工作模式就不好，因为我们有时候就需要让它错误传播，比如一份重要的文件加密，我们要防止别人篡改其中的某一位。而错误传播就可以让这个微小的修改被无限放大而让接收者知道这份文件发生了错误 。

   由于不同组的明文会收到之前密文的影响，这就导致相同的明文会加密出不同的密文。这就避免了暴露明文的数据模式。

5. 

6. 

7. 

还有三种工作模式分别是CFB Cipher Feedback 密文反馈模式, OFB Output Feedback 输出反馈模式, CTRCounter Mode 计数器模式。
它们的方式都非常奇怪，明文本身没有参与DES加密，进行加密的是初始向量，然后用初始向量的加密结果和8位明文进行按位与。对，因为明文本身不参与DES加密，所以它每组没有把明文分成64位每组，而可以分成更加遍历的位数。甚至可以每组1位，十分牛逼。

3. CFB Cipher Feedback 密文反馈模式。明文是和某个向量经过DES的结果的左边j位进行按位与。同时把密文移动到下个向量的右边j位。

   由于每次对明文产生影响的只有j位，可能这样就导致了错误传播得不会太远。这是它得一个特点。错误传播有界。

4. OFB Output Feedback 输出反馈模式。和CFB类似，但是OFB中影响下一个向量的j位不是上一组的密文，而是直接由上一组向量的加密结果的左j位。所以这就导致密文的错误不会传播。

   还是和之前说的一样，无错误传播不一定好，我们无法确定密文是否被篡改。所以这使用于冗余度较大的图片视频等错了几位不怕的数据。OFB经常被用来加密卫星的传输。

5. CTR Counter Mode 计数器模式相比前两个CFB和OFB就简单多了，也没有初始向量，上一组的输出或者密文也不会影响到下一组。

   这让它可以并行处理。还可以随机区块解密，不用必须从后往前全部解一遍。

AES

Advanced Encryption Standard。高级加密标准。其设计出来便是为了代替因为密钥位数太少而已经不安全的DES

AES提供了3种不同的规格，按照实际需求进行选择，十分灵活，具体参数如下。

分组长度 128 128 128 轮数 10 12 14 轮密钥长度 128 128 128

我们可以看见，就算是最低规格的AES，都远比DES的位数长的多。

我们再来看AES的加密流程。

我们先来看其中最重要的S盒。AES的S盒盒DES的S盒不一样，AES的S盒是可以算出来的，而DES只是给你一堆数，不知道这些数是怎么的出来的。

AES S盒替换又叫做字节代替，其操作就是把明文的的每个字节进行整体代替，相当于把一个字节换成另一个完全不一样的字节。而DES中做法是输入48位二进制，因为 有8个S盒，故分为8组，每组6位二进制，第一位和最后一位组成行，中间4位组成列，在S表中进行定位元素，表中的元素都是4位的，整体S盒是48位输入，32位输出。而AES的S盒实际上比DES的S盒简单的多，因为AES只有一个S盒。这个S盒为16行，16列的正方形。

它的行对应AES输入字节的前八位，它的列对应AES输入字节的后八位，S表的每个元素都是一个字节，所以就实现了输入一个字节，然后替换为另一个字节。

如果要利用查表得话，程序实现起来也是非常得简单。

但是我们之前也说过，这个S表实际上是算出来得。也就是我们可以根据一个字节，然后手动计算出输出，不用查表。

实际上是把输入得字节转化为一个多项式，然后求这个多项式得逆，再把这个逆转化为二进制，然后乘上一一个矩阵，再加上一个矩阵。

听起来挺简单得，但是以我目前的知识，我无法利用python实现多项式的表示，更别说求多项式的逆了。numpy貌似可以解决这个问题，之后再研究吧。

这里就用一个例子手动演示一下计算过程吧！

假设我么输入的字节为0x53，即01010011。

1. 其对应的多项式为$x^6+x^4+x^1+1$x6+x4+x1+1。

2. 然后需要求该多项式在模$x^8+x^4+x^3+x+1$x8+x4+x3+x+1意义下的逆，这个8次多项式是伽罗华域里面指定的，说实话我不太懂2333。

3. 和整数的求逆的过程类似，先写出它的辗转相除的过程。（利用多项式除法 注意 在模意义下 加和减等效）

   $x^8+x^4+x^3+x+1$x8+x4+x3+x+1 =$(x^2+1)*(x^6+x^4+x^1+1)+x^2$(x2+1)∗(x6+x4+x1+1)+x2

   $x^6+x^4+x^1+1 = (x^4+x^2)*x^2+(x+1)$x6+x4+x1+1=(x4+x2)∗x2+(x+1)

   $x^2 = (x+1)*(x+1)+1$x2=(x+1)∗(x+1)+1

   然后开始手动推逆。

   $1 = x^2 + (x+1)*(x+1)$1=x2+(x+1)∗(x+1)    //减直接等效为加来简化运算

   $1 = x^2 + (x+1) * ((x^6 + x^4+x+1)+x^2*(x^4+x^2))$1=x2+(x+1)∗((x6+x4+x+1)+x2∗(x4+x2))

   $1 = (x+1)(x^6+x^4+x+1)+(x^5+x^4+x^3+x^2+1)x^2$1=(x+1)(x6+x4+x+1)+(x5+x4+x3+x2+1)x2

   $1 = (x+1)(x^6+x^4+x+1) + (x^5+x^4+x^3+x^2+1)((x^8+x^4+x^3+x+1)+(x^2+1)*(x^6+x^4+x^1+1))$1=(x+1)(x6+x4+x+1)+(x5+x4+x3+x2+1)((x8+x4+x3+x+1)+(x2+1)∗(x6+x4+x1+1))

   $1 = (x^5+x^4+x^3+x^2+1)(x^8+x^4+x^3+x+1)+(x^7+x^6+x^3+1)(x^6+x^4+x+1)$1=(x5+x4+x3+x2+1)(x8+x4+x3+x+1)+(x7+x6+x3+1)(x6+x4+x+1)

   则我们可以得到多项式$x^6+x^4+x^1+1$x6+x4+x1+1的逆为$(x^7+x^6+x^3+1)$(x7+x6+x3+1)。

   同时我们因为一开始的两个式子很长，导致最后最后推导的时候写那两个式子很麻烦，我们可以一开始设置$p(x)=x^8+x^4+x^3+x+1$p(x)=x8+x4+x3+x+1，设置$q(x)=x^6+x^4+x+1$q(x)=x6+x4+x+1。我们再试着重新写一下过程。

   辗转相除

   $p(x)=(x^2+1)q(x)+x^2$p(x)=(x2+1)q(x)+x2

   $q(x)=(x^4+x^2)x^2+(x+1)$q(x)=(x4+x2)x2+(x+1)

   $x^2=(x+1)(x+1)+1$x2=(x+1)(x+1)+1

   求逆

   $1 = x^2 + (x+1)(x+1)$1=x2+(x+1)(x+1)

   $1 = x^2 + (x+1)q(x)+x^2(x^4+x^2))$1=x2+(x+1)q(x)+x2(x4+x2))

   $1 = (x+1)q(x)+(x^5+x^4+x^3+x^2+1)x^2$1=(x+1)q(x)+(x5+x4+x3+x2+1)x2

   $1 = (x+1)q(x) + (x^5+x^4+x^3+x^2+1)(p(x)+(x^2+1)q(x)$1=(x+1)q(x)+(x5+x4+x3+x2+1)(p(x)+(x2+1)q(x)

   $1 = (x^5+x^4+x^3+x^2+1)p(x)+(x^7+x^6+x^3+x)q(x)$1=(x5+x4+x3+x2+1)p(x)+(x7+x6+x3+x)q(x)

   显得简单了许多。

   所以手动求逆有两个技巧  1. 减转化为加 2.设p(x)和q(x)。

4. 现在我们得到了多项式的逆$x^7+x^6+x^3+1$x7+x6+x3+1。再这个逆转化为二进制11001010

5. 让这个二进制乘上一个Z矩阵，再加上一个C矩阵。注意将那个二进制的矩阵低位在上，高位在下。

   最后得到的矩阵为

   $\begin{pmatrix} 1 \ 0 \ 1 \ 1 \ 0 \ 1 \ 1 \ 1 \ \end{pmatrix}$⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛10110111⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞

   它代表的二进制是10110111嘛？不！刚才说过，低位在上，高位在下。实际的结果应该从下往上读11101101 0xed。

   这就是一开始输入字节01010011 0x53的置换结果了！

   如果要用程序实现这个过程，需要解决多项式求逆的难点，矩阵相乘倒是好求。

   ok，现在我们解决了AES中的字节代替。

   接下来我们看一看行移位。

   手动实现和程序实现的难度都很低，第0行不变，第1行循环右移1，第二行循环右移2，第三行循环右移3。

   然后是列混合。

   列混合实际是把一列转化为一个多项式，下面为高位，下面为低位。

   即$C_{3, 0}x^3+C_{2, 0}x^2+C_{1, 0}x+C_{0,0}$C3,0x3+C2,0x2+C1,0x+C0,0

   值得注意的是每个C实际上是一个字节，它也可以等价转化为一个多项式。

   所以上面这个多项式的实际次数可能不止3。

   然后我们要把这个列对应的多项式乘上一个$C(x)='03'x^3+'01'x^2+'01'x^1+'02'$C(x)=′03′x3+′01′x2+′01′x1+′02′

   同样的，这个C(x)和列多项式一样，实际的次数不止3次，因为$'03'$′03′对应了多项式$x^2$x2。所以$C(x)$C(x)这个多项式的最高次为5。

   然后我要要做的是把列对应的多项式乘上这个$C(x)$C(x)，同时模上$x^4+1$x4+1。最后的结果如上图。

   然后我们把最后结果的每个次数的x前面的系数对应到新的列上。就完成了列混合。

   实际上我们计算列混合的结果时不用考虑的这么多，只需要利用最后的d和c之间的结果即可，实际上它们之间的关系就是乘上了一个矩阵。

   即$d_{0,0}='02'C_{0,0}+'03'C_{1,0}+'01'C_{2,0}+'01'C_{3,0}$d0,0=′02′C0,0+′03′C1,0+′01′C2,0+′01′C3,0

   和之前的结果时一致的。

   值得注意的是，我们一开始的方法多项式表面上最高此次为3，因为没有将C实际转化为多项式，所以模的是$x^4+1$x4+1。

   而现在我们根据结论的时候，是需要将C展开为多项式的，故不能再模$x^4+1$x4+1，需要模那个神奇的多项式$x^8+x^4+x^3+x+1$x8+x4+x3+x+1。

   以下为例子。

   ok，最后一个步骤就是和轮密钥按位与，十分简单。

   那轮密钥是怎么产生的呢？因为AES一共有十轮，所以我们需要根据初始128位的密码进行生成之后的密钥。

   我们先把128位的密钥，即16个字节的密钥的形式换一些，把第一列写成$w_o$wo。

   实际上

   $w_0= \begin{pmatrix} k_{0} \ k_{1} \ k_{2} \ k_{3} \ \end{pmatrix}$w0=⎝⎜⎜⎛k0k1k2k3⎠⎟⎟⎞

   然后我们就可以得到$w_0,w_1,w_2,w_3$w0,w1,w2,w3。这实际上就是初始密钥，没有任何变化，我们只是换种形式表示。

   然后我们需要以此位基础生成第一轮的轮密钥$w_4,w_5,w_6,w_7$w4,w5,w6,w7。

   公式如下

   $\begin{cases} w(i)=w(i-1)\oplus w(i-4)& i\ mod\ 4\neq 0\ w(i)=g(w(i-1))\oplus w(i-4)& i\ mod\ 4 = 0 \end{cases}${w(i)=w(i−1)⊕w(i−4)w(i)=g(w(i−1))⊕w(i−4)i mod 4=0i mod 4=0

   如果w不是4的倍数，那很简单，只需要将w(i-1)和w(i-4)按位与即可。

   如果w是4的倍数，那么复杂一些，需要先把w(i-1)做一点处理，然后再和w(i-4)按位与。

   处理如下。

   课件里把w(i-1)写成横的了，实际上写成竖的更好，整体往上移位。然后将移位后的结果进行字节代替。

   然后将字节代替后的结果的第一个字节加上一个数r。这个r和i相关。$r(i)=2^{(i-1)/4}$r(i)=2(i−1)/4

   如此操作，我们就能得到10轮轮密钥。

   值得注意的是，我们实际用的时候应该是还是得把w转化为方块，然后一行一行来进行按位与。当然把处理后得明文直接按列来直接与也行233。只要是两个16字节的方块按位与即可。

   至此，我们已经厘清了AES的操作。接下来我们分析一下其安全性。

   由于密钥长度的大小，使得暴力破解几乎不可能。

   同时由于行移位和列混合，导致AES一字节的更改，在10轮的迭代后都产生了蝴蝶效应，防止了伪造明文。

6. 

7. 

8. 

9. 

10. 

11. 

12. 

13. 

14. 

15. 

16. 

其他分组密码

1. IDEA

2. RC6

3. Twofish

4. Serpent

脑容量不够了，这几个就不分析了2333

差分分析

以后再说

One-Time Pad

维吉尼亚密码做为古典密码中最出色的密码，由于密钥是重复使用的，使得重合指数法利用频率进行分析成为可能。那么如果密钥和明文一样长，并且完全随机呢？

这种方式加密起来也十分简答， 只要将明文和密钥按位与即可。

$C=M \oplus K$C=M⊕K

同时可以证明，OTP是绝对安全的。

流密码概述

用伪随机来代替随机

Pseudorandom Number Generator(PRNG)   Pseudorandom: 伪随机数

种子是秘密密钥。

和OTP类似，只不过把K换掉了。

$C=M \oplus PRNG(seed)$C=M⊕PRNG(seed)

分组密码和流密码的方式的差别：

1. 因为分组密码的明文都有位数要求，比如DES的明文要求为64位。而实际要加密的数据肯定不止64位，所以要把数据分成一组一组的，每组都是64位，去加密，这也是分组密码名称的由来。

   $c=(c_1c_2..)(c_ic_{i+1}..=e_k(m_1m_2..)e_k(c_ic_{i+1}))$c=(c1c2..)(cici+1..=ek(m1m2..)ek(cici+1))

2. 而流密码实际上做的就是和伪随机密钥流进行按位与，所以它不用分组，来多少按位与多少即可。

   $c=c_1c_2..=e_{k1}(m_1)e_{k2}(m_2)..$c=c1c2..=ek1(m1)ek2(m2)..

   密钥流$(k_1,k_2,..)$(k1,k2,..)

流密码性质

1. 数学性质好，因为它模仿OTP，而OTP是绝对保密的，并且伪随机也有很长的研究历史

2. 加密速度非常快，因为只有按位与

3. 密钥流只能使用一次。

4. 应用很广 比如网路、移动通信等等

伪随机序列发生器 Pseudorandom Number Generation

由于流密码实际的加密过程只有按位与，几乎不用怎么讲。流密码最难得部分就是伪随机密钥流的生成。

密码学中对伪随机数的要求：

1. 随机性

   均匀分布：数列中每个数出现 的频率相等或者近似相等

2. 不可预测性

   密码分析者很难从数列前面的数预测后面的数

伪随机数的应用

1. 相互认证

   使用一次性随机数来防止重放攻击

2. 会话密钥的产生

   用随机数做为会话密钥

3. 公钥密码算法中密钥的产生

   用随机数做为公钥密码算法中的密钥

PRNG定义：

一个伪随机学列发生器G是一个确定的多项式算法，使得

1. 拓展性：

2. 伪随机性

Golomb随机性测试

1. 在序列的一个周期内，0和1的个数相差至多为1。

2. 在序列的一个 周期内，长为1的游程占总游程数的1/2，长为2的游程占总数的

   $1/2^2$

   1/22,…长为i的游程占总数的

   $1/2^i$

   1/2i,…，且在等长的游程中，0和1游程的个数至多差1.

3. 自相关函数为双值（话说双值是什么意思233

周期为31

1的个数为16，0的个数为15，符合Golomb测试的第一个条件

Golomb测试的第二个条件中的游程是什么意思呢？实际上就是连续的1或者连续0的情况，比如000就是0的3-游程

这个字符串总共的游程个数是16个。0和1的1-游程都是4个，总共8个，占16个的一半，正好1/2。2-游程4个，1/4。3-游程两个，1/8。4-游程1个，1/16，5-游程1个，1/16。

同时在等长的游程中，0和1的游程数量几乎一致，最多差1，符合Golomb测试。

LSFR (Linear Feedback Shift Register)

是一种PRNG的实例，大概可以翻译为线性反馈移位寄存器233

这张图中，$z_o$zo寄存器做为输出端，会把一位传到外面，相当于产生了一个随机数。

然后就是移位，本来$z_1$z1寄存器的值会传到$z_0$z0上，$z_2$z2的值会传到$z_1$z1上。而$z2$z2的值是由$z_0$z0和$z_1$z1的值相与得到的，这就是LSFR中的feedback。

一开始这三个寄存器中的初始值叫做seed种子。

这个实例比较简单，如果寄存器再多一些就比较复杂了，因为每个寄存器都可能参与反馈，也可能不参与，我们需要一个简单的方法来让简化。

这里引入反馈系数。

每一个寄存器都对应一个反馈系数，来代表它有没有参与反馈。

这里的反馈实际都是反馈到$z_{n-1}$zn−1这个寄存器的下一个状态，也就是$k_n$kn了。因为$z_{n-2}$zn−2到$z_0$z0的寄存器都是前一个寄存器移位下来的。

我们可以写出这样的反馈式子

然后我们呢可以把这个式子转化为一个对应的特征多项式

$p(x)=1+c_{j-1}x+c_{j-2}x^2+..+c_{j-n}x^n$p(x)=1+cj−1x+cj−2x2+..+cj−nxn

然后我们来思考一下LSFR的周期。

首先，我们很容器想到一个具体的LSFR是有周期上线的，因为n个寄存器，最多有$2^n$2n中可能性，而其中全零是不可能的，不然就一直全零，肯定不是随机序列了嘛233，所以周期最大为$2^n-1$2n−1

这个LSFR实例就达到了最大周期$2^3-1$23−1。值得注意的是，因为LSFR只是一个伪随机数发生器，它实际上产生的随机数序列为$0010111\ 0010111\ 0010111$0010111 0010111 0010111。周期为7。

m-序列：由LSFR产生的最大长度序列是m-序列，结合上面的结论，m序列的周期是$2^n-1$2n−1。并且它满足Golomb随机性检测。在一个周期内，0比1的个数少1个。

定理：

$\{a_i\}${ai}是m-序列当且仅当它的特征多项式$p(x)$p(x)是本原多项式

定义：如果p(x)的次数为n，且其周期为$2^n-1$2n−1则称p(x)为本原多项式。

定义：设p(x)为GF（2）上的多项式，使得式子$p(x)|x^p-1$p(x)∣xp−1成立的最小正整数p为$p(x)$p(x)的周期

这里实际上对周期这个概念做了拓展，让一个多项式也有了周期。

非线性序列

LSFR做到操作是抑或，属于线性操作，如果我们把这种操作改编为非线性的，实际上就可以产生出非线性序列。

它有一下特征：

1. 输出序列的周期为

   $2^n$

   2n *？

2. 最大长度序列是

   $M-序列$

   M−序列

3. M-序列有很好的随机性质

4. M-序列的个数是

   $2^{2^{n-1}-n}$

   22n−1−n

5. 非线性函数是

   $2^{2^n}-2^n$

   22n−2n

对非线性序列的研究还在初级阶段

实际应用中的非线性序列（用m-序列做为驱动序列）

1. 非线性混合序列

2. 钟控序列

非线性混合序列：

它实际上就是把n个LSFR的输出进行非线性混合。

钟控序列：

引入了时钟，看不懂了233

Blum Blum Shub发生器

BBS发生器基于数论中的二次剩余问题。

挺简单的，开局选两个大素数p和q。得到n=pq。

然后选一个和n互素的随机数x。

然后得到bbs初始输入$x_0=x^2(mod\  n)$x0=x2(mod n)

然后我们就根据这些x的二进制的最低位来生成01伪随机序列。注意$x_0$x0的二进制最低位没有加入到输出中。

这里输出99位测试一下。

n=9788476140853110794168855217413715781961
x=873245647888478349013
prn = ""
x = x**2 % n  #x0的二进制最后一位不算入随机数序列中
for i in range(1, 100):
        x = x**2 % n
        prn += bin(x)[-1]
print(prn)

只差1，符合了Golomn测试的第一条。

游程测试也大致符合。

所以BBS产生的随机数还是挺不错的。就是计算量比LSFR大多了2333。

流密码设计目标

1. 长周期

2. 高线性复杂度

3. 统计性能好

4. 足够的混乱

A5

实际上就是对3个LSFR进行非线性综合后输出，同时这三个LSRF是钟控的。

RC4

RC4十分简单与高效。它又有点像分组加密，因为它的密钥一次性生成一个字节，也就是8位。而不像普通的PRNG，每次吐出一位来。

以下位RC4的代码

s = []
k = [22, 33, 233]
for i in range(0, 256):
        s.append(i)
j = 0
for i in range(0, 256):
    j = (j + s[i] + k [i % 3]) % 256
    s[i], s[j] = s[j], s[i]
print(s)
print("----------------------------")
Ks = []

i, j = 0, 0
for num in range(0, 100):
    i = (i + 1) % 256;
    j = (j + s[i]) % 256;
    s[i], s[j] = s[j], s[i]
    t = (s[i] + s[j]) % 256
    Ks.append(s[t])
print(Ks)

首先把0~255进行打乱，打乱的过程中运用到了我们输入的Secret key。

然后进行简单又神秘的操作就可以不断地生成8位密钥。以下运行结果，上部分是打乱后地数组，下面是生成的随机数。

流密码到这里就没了，你可能会疑惑流密码怎么只讲了加密，如何解密呢？

233，实际上因为流密码加密的时候只是与密钥流向亦或了，只要再亦或一个，就回到明文啦！

所以流密码是如此的简单与高效。我觉得我也能设计一个不注重安全的流密码，正常人应该也不会去差分分析之类的把233，所以应该是十分安全的。

非对称密码

之前我们学得密码都属于对称密码。发信者和收信者用得是同一个密钥。

1976年Diffie & Hellman开启了密码学得新方向——非对称密码。这被称为近千年来密码学上最有意义得成就。

这里的非对称指的是密钥的非对称，即加密是用的某个密钥，解密是用的另一个密钥。

RSA

RSA加密过程

选择两个大素数$p$p$q$q。得到$n=pq$n=pq。然后计算$n$n的欧拉函数$\varphi(n)$φ(n)，然后选择一个和$\varphi(n)$φ(n)互素的$e$e。

这个$e$e（意为encode）会用在加密中。然后求$d=e^{-1}\ mod\  \varphi(n)$d=e−1 mod φ(n)。这个$d$d（意为decode）会用在解密中。

以下为加密和解密的过程

$c=E_m(m)=m^e(mod\ m )$c=Em(m)=me(mod m)

$m=D_d(c)=c^d(mod\ n)$m=Dd(c)=cd(mod n)

加密者会把$(n,e)$(n,e)放出来做为公钥，大家都可以用来加密。但是由于素数分解的难题，别人无法知道$d$d，也就无法解密。

私钥就是$(p,q,d)$(p,q,d)。其实我觉得写成$(n, d)$(n,d)就行？直接根据$d$d就能解密，不用实际知道$p,q$p,q。

RSA例子1

1. p选择7，q选择11，则n为77。$\varphi(n)=60$φ(n)=60。

2. 选择一个和$\varphi(n)$φ(n)互素的值，比如37。这个37就是$e$e了，用来加密。

3. 再计算一下$d$d。d是e关于$\varphi(n)$φ(n)的逆。由libnum库计算d为13

4. 

5. 如果密文为2的话。$c=m^e\ mod\ n=2^{37}\ mod\ 77=51$c=me mod n=237 mod 77=51

6. 

7. 解密很简单。$m=c^d\ mod\ n=51^{13}\ mod\ n=2$m=cd mod n=5113 mod n=2。

   可以看见解密出来的就是原文。

RSA例子2

例子1的数比较小。我们试一下这个大的。

这里试着用python实现一波。

import libnum
p, q = 885320963, 238855417
n = p * q #211463707796206571
phi = (p - 1) * (q - 1) #211463706672030192
e = 9007 #encode
d = libnum.invmod(e, phi) #decode 116402471153538991
m = 30120
c = m ** e % n #11353585903572286
print(f"encode: {c}")
result = c ** d % n
print(f"decode: {result}")

能够正常的加密，但是解密就卡住了。

我们分析一波原因，加密的时候的式子为$30120^{9007}\ mod\ 211463707796206571$301209007 mod 211463707796206571。实际上指数已经算很大了，但是由于python强大的计算能力，结果还是秒传。

我们再来看一看解密时候的式子$11353585903572286^{116402471153538991}\ mod\ 211463707796206571$11353585903572286116402471153538991 mod 211463707796206571

底数这么大，指数也这么大，天王老子来了也算不出来，这也就是python为什么卡住了。

我们需要一种快速指数算法Efficient Exponentiation，这里便引出了平方乘算法Square-and-Multiply Algorithm。

Sqaure-and-Multiply Algorithm

平方乘算法的思想实际很简单，首先我们 需要将指数转化为二进制。然后的操作类似于将二进制数转化为十进制数的过程。

比如51的二进制数110011。如何将二进制转化回十进制呢？

1. $1*2^0+1*2^1+1*2^4+1*2^5$1∗20+1∗21+1∗24+1∗25

2. $(((1*2)+1)*2*2*2+1)*2+1$(((1∗2)+1)∗2∗2∗2+1)∗2+1

   第二种方法实际上的从最左端出发

   $1$1

   $10$10->$11$11

   $110$110

   $1100$1100

   $11000$11000->$11001$11001

   $110010$110010->$110011$110011

   每次的乘二相当于整体左移，如果对应的二进制为1，则加上1。如果对应二进制为0，那就是不加1，只乘二右移。

   一系列操作后从最高位的$1$1得到了$110011$110011，也就完成了从1计算得到51的过程。

平方乘算法就利用了上面的第二种方法，只不过算法中的二进制因为是在指数上，所以乘2就是平方，加一就是乘一个底数。

算法如下

bottom = 113535859035722866
exp = 116402471153538991
modu = 211463707796206571

bin_ = bin(exp)[2:]
z = 1
for i in bin_:
    z = z ** 2 % modu
    if i == "1":
        z = z * bottom % modu
print(z)

结果秒出，我们很快得到了例子2中没有得到的结果。

能否用上面说的将二进制转化为十进制方法中的第一种方法来实现平方乘算法呢？我试了一下，很难。但是有一个奇怪的现象，刘杨教我们用快速指数算法手算的时候，用的都是第一种方法，ppt如下。

ppt中的实际和平方乘算法的过程完全不一样，平方乘算法不用刻意的去就求出$79^{2^5},79^{2^4}...$7925,7924...的值，而在一次次平方与乘中自然而然得到了最终的答案。

我们用真正的平方乘算法来写一下过程。

• $51=(110011)_2$

  51=(110011)2

• 初始值为1

• $1^2\ mod\ 90=1$

  12 mod 90=1

  $1*79\ mod\ 90=79$

  1∗79 mod 90=79

• $79^2\ mod\ 90=31$

  792 mod 90=31

  $31*79\ mod\ 90=19$

  31∗79 mod 90=19

• $19^2\ mod\ 90=1$

  192 mod 90=1

• $1^2 \ mod\ 90=1$

  12 mod 90=1

• $1^2\ mod\ 90=1$

  12 mod 90=1

  $1*79\ mod\ 90=79$

  1∗79 mod 90=79

• $79^2\ mod\ 90=31$

  792 mod 90=31

  $31*79\ mod\ 90=19$

  31∗79 mod 90=19

可以看到手动算的时候，我们也可以直接利用算法原本的过程，计算量比ppt更小。

但是也许ppt上的方法更容易让人理解，但是程序是较难实现的。

Miller-Rabin Algorithm (Fermat Test)

费马测试的原理是费马定理。

费马定理：对于素数p，取与p互素的a（0<a<p）。有$a^{p-1}=1\ mod\ p$ap−1=1 mod p。

费马定理实际上就是欧拉公式当n为素数时的的特例。

欧拉公式：若a与n互素，则$a^{\varphi(n)}=1\ mod\ n$aφ(n)=1 mod n

因为素数满足费马定理，所以费马测试就去测试一个数n，若$a^{n-1}=1\ mod\ n$an−1=1 mod n，则n被判定为一个素数。

我们很容易就容易发现，这是一个偏是的测试，因为有一些合数也会满足费马测试，它们被称为伪素数。

然后式子的测试过程中，为了简便操作，将$n-1$n−1分解为$2^km$2km（m为奇数）。第一眼看可能感觉这个n-1不一定能分解为$2^km$2km，但是由于k应该可以取0，所以是一定能够分解的。

费马测试中就去计算$b=a^m$b=am是不是1，如果是1，ok满足条件（这里b为-1貌似也可以，但是不知道为什么ppt里没写）。不满足则看$b^2,b^4,..$b2,b4,..是不是正负1，如果遇到了一个正负1，ok，满足条件。如果到最后$b^{2^k}$b2k都没有得到正负1，说明它是个合数。

这里举一个例子。

1. 取n为97，则n-1为96。96可以分解为$2^5*3$25∗3，即$32*3$32∗3

2. 随便取一个a，比如说2，则看$b=a^m=2^{3}\ mod\ 97$b=am=23 mod 97是不是1。

   $b=8$b=8，不是1，则继续。

3. 

4. $b^2\ mod\ 97=64$b2 mod 97=64。继续

5. $b^4\ mod\ 97=22$b4 mod 97=22。继续

6. $b^8\ mod\ 97=96=-1$b8 mod 97=96=−1。发现-1，测试完毕，输出“素数”。

   这里再详细解释一下为什么遇到-1也能说素数，因为$a^{n-1}=a^{2^km}=b^{2^k}$an−1=a2km=b2k。当遇到$b^{2^x}$b2x等于正负1时，最后的结果式子$b^{2^k}$b2k 实际就是又把-1平方了即便，最后的结果是1，满足费马定理，就判断该数为素数了。

一个合数有四分之一的概率通过费马测试，我们可以通过取多个a的方式来降低误判的概率。但是有一些数，不管你取什么a，都能被判定为素数，这些数被成为Carmichael数，比如561,645,1105。

我们这里对561进行一轮费马测试来模拟一下，a还是取2。

• $n=561$n=561

• $n-1=560$n−1=560

• $560=2^4*35$560=24∗35

• $b=a^m=2^{35}\ mod\ 561=263$b=am=235 mod 561=263

• $b^2\ mod\ 561=166$b2 mod 561=166

• $b^4\ mod\ 561=67$b4 mod 561=67

• $b^8\ mod\ 561=1$b8 mod 561=1

  返回“素数”

分解大素数

其实RSA知道加密解密过程。然后了解平方乘算法来使指数运算称为现实，再利用费马测试来选择一个素数后，我们已经了解完RSA了。

接下来讲的分解大素数，该知识点应用在破解RSA密码中，也就是我们不知道d,p,q，我们只知道$e, n$e,n。

在这种情况下我们就需要对n进行分解。分解出p,q后，$\varphi(n)=(p-1)(q-1)$φ(n)=(p−1)(q−1)也就知道了，$d=e^{-1}\ mod\ n$d=e−1 mod n也就知道了。就可以解密了。但是分解素数不是这么简单的。

此内容之后填充。

1. Elgmal

   此密码和之后的椭圆曲线密码一样，都基于离散对数问题 Discrete Logarithm Problem DLP。

   公钥与私钥的产生

   加密过程

   解密过程

   $m=c_2((c_1)^a)^{-1}$m=c2((c1)a)−1

   解密原理

   因为$c_2=m(\beta)^k=mg^{ak}(mod\ p)$c2=m(β)k=mgak(mod p)

   又$((c_1)^a)^{-1}=(g^{ak})^{-1}(mod\ p)$((c1)a)−1=(gak)−1(mod p)

   故$m=c_2((c_1)^a)^{-1}$m=c2((c1)a)−1

   例子

   Elliptic Curve

   椭圆曲线密码与Elgmal极为类似，可以对照记忆。

   椭圆曲线定义

   椭圆曲线是满足$y^2=x^3+ax+b \ \ \ a,b\in R$y2=x3+ax+b   a,b∈R的所有解$(x,y)\in R\times R$(x,y)∈R×R，加上一个无穷远点O。

   椭圆曲线上的加法

   这个椭圆曲线上的加法十分重要，必须要背出来，之后的加密需要用到。

   当两个点关于x轴对称的话，那么他们相加为O。一个点加上一个O，还是本身。

   如果那么普通的两个点P($x_P,y_P$xP,yP)与Q($x_Q,y_Q$xQ,yQ)，假设它们相加为R点（$x_R,y_R$xR,yR）的话。

   我们首先需要算一个神秘的值$\alpha$α。这个$\alpha$α需要分两种情况讨论。如果$P$P和$Q$Q不是同一个点，$\alpha$α就是就是两点的斜率。如果P和Q是同一个点，那么这时$\alpha = (3x^2+a)/2y$α=(3x2+a)/2y，这里实际上不用区分$x_R$xR还是$x_P$xP了，因为两者的坐标相同。

   然后$x_R=\alpha^2-x_P-x_Q\ mod\ p$xR=α2−xP−xQ mod p。

   $y_R=\alpha(x_P-x_R)-y_P\ mod\ p$yR=α(xP−xR)−yP mod p

   没什么好记忆的法子，考试前多背几遍。

   椭圆曲线上加法例子

   $\alpha = (3 * 1 + 4 ）/ 6\ mod\ 2773$α=(3∗1+4）/6 mod 2773。

   这里我们可以发现式子里的除法不是真的除，而是要转化为乘它的逆。

   $2773=462*6+1$2773=462∗6+1

   $1 = 2773-462*6$1=2773−462∗6

   6的逆为-462，即2311, 则$\alpha = 2312$α=2312。

   ok，然后$x_R=\alpha^2-x_p-x_p=1771\ (mod\ 2773)$xR=α2−xp−xp=1771 (mod 2773)

   $y_R=\alpha(x_P-x_R)-y_R=705\ (mod\ 2773)$yR=α(xP−xR)−yR=705 (mod 2773)

   二次剩余定义

   当我们判断d是p的二次剩余后，去求解x的时候，如果p是一个模4余3的素数，那么x就可以直接给出结果

   $x=\pm d^{(p-1)/4} \ mod\ p$x=±d(p−1)/4 mod p

   ECC中的离散对数DLP问题

   在椭圆曲线群中的$k\times\alpha$k×α，对应$Z_p$Zp中的$\alpha ^k$αk。

   在$Z_p$Zp下求$k$k很难，在椭圆曲线中也很难求$k$k，便以此为依据设计了一个陷门函数，形成了ECC。

   密钥生成

   公钥$(p, E, P_A)$(p,E,PA)，私钥$a$a。

2. 

3. 

4. 

5. 

6. 

7. 

8. 

9. 

1. 选择一个椭圆曲线E(mod p)，p是一个大素数。

2. 选择E上的点G，使得$n\times G=O$n×G=O

3. 选择随机数a,$a<n$a<n

4. 计算$P_A=a\times G$PA=a×G。

5. p=97, g=5, 选择的随机数为a=58,$\beta=g^a=5^{58}(mod\ 97)=44$β=ga=558(mod 97)=44（这一步需要用到平方乘算法，计算量较大

6. 于是(97, 5, 44)便为公钥，大家可以利用公钥来进行加密。58为私钥，只有知道私钥的人才可以解密。

7. 假设需要加密m=3，再选择一个随机数k=36。

   则$c_1=g^k(mod\ p)=5^{36}(mod\ 97)=50$c1=gk(mod p)=536(mod 97)=50（同样平方乘

   $c_2=m\beta^k(mod\ p)=3*44^{36}(mod\ 97)=31$c2=mβk(mod p)=3∗4436(mod 97)=31

   这里经过老杜的指点，不必完全利用平方乘算法来计算，那样计算量太大了。因为如果有是1还要乘44，平方以后再乘44让人受不了，这时候还是之前手工算的时候更灵活，先算平方，再算四次方…$

8. 解密$m=c_2*((c_1)^a)^{-1}(mod\ p)=31*(50^{58})^{-1}(mod\ 97)$m=c2∗((c1)a)−1(mod p)=31∗(5058)−1(mod 97)

   $50^{58}(mod\ 97)$5058(mod 97)认真算一下，发现4次方是-1,之后的八次方，十六次方，以及三十二次方都是1，故最后的结果是75。

   75的逆为22，故$m=31*22(mod\ 97)=3$m=31∗22(mod 97)=3。成功解密得到了明文。

9. 选择一个随机数k，

   $0\leq k\leq p-1$

   0≤k≤p−1

10. 如果要加密消息m

11. 则

    $c_1=g^k(mod\ p)$

    c1=gk(mod p)，

    $c_2=m(\beta)^k(mod\ p)$

    c2=m(β)k(mod p)

12. 产生一个大素数p

13. 选择

    $Z_p$

    Zp的一个生成元g。（大概就是g的幂能够遍历

    $Z_p$

    Zp

14. 选择一个随机数a,

    $0\leq a\leq p-1$

    0≤a≤p−1

15. 计算

    $\beta = g^a\ mod \ p$

    β=ga mod p

16. 公钥为(p,g,

    $\beta$

    β)

17. 私钥为

    $a$

    a

Elgmal

此密码和之后的椭圆曲线密码一样，都基于离散对数问题 Discrete Logarithm Problem DLP。

公钥与私钥的产生

1. 产生一个大素数p

2. 选择

   $Z_p$

   Zp的一个生成元g。（大概就是g的幂能够遍历

   $Z_p$

   Zp

3. 选择一个随机数a,

   $0\leq a\leq p-1$

   0≤a≤p−1

4. 计算

   $\beta = g^a\ mod \ p$

   β=ga mod p

5. 公钥为(p,g,

   $\beta$

   β)

6. 私钥为

   $a$

   a

加密过程

1. 选择一个随机数k，

   $0\leq k\leq p-1$

   0≤k≤p−1

2. 如果要加密消息m

3. 则

   $c_1=g^k(mod\ p)$

   c1=gk(mod p)，

   $c_2=m(\beta)^k(mod\ p)$

   c2=m(β)k(mod p)

解密过程

$m=c_2((c_1)^a)^{-1}$m=c2((c1)a)−1

解密原理

因为$c_2=m(\beta)^k=mg^{ak}(mod\ p)$c2=m(β)k=mgak(mod p)

又$((c_1)^a)^{-1}=(g^{ak})^{-1}(mod\ p)$((c1)a)−1=(gak)−1(mod p)

故$m=c_2((c_1)^a)^{-1}$m=c2((c1)a)−1

例子

1. p=97, g=5, 选择的随机数为a=58,$\beta=g^a=5^{58}(mod\ 97)=44$β=ga=558(mod 97)=44（这一步需要用到平方乘算法，计算量较大

2. 于是(97, 5, 44)便为公钥，大家可以利用公钥来进行加密。58为私钥，只有知道私钥的人才可以解密。

3. 假设需要加密m=3，再选择一个随机数k=36。

   则$c_1=g^k(mod\ p)=5^{36}(mod\ 97)=50$c1=gk(mod p)=536(mod 97)=50（同样平方乘

   $c_2=m\beta^k(mod\ p)=3*44^{36}(mod\ 97)=31$c2=mβk(mod p)=3∗4436(mod 97)=31

   这里经过老杜的指点，不必完全利用平方乘算法来计算，那样计算量太大了。因为如果有是1还要乘44，平方以后再乘44让人受不了，这时候还是之前手工算的时候更灵活，先算平方，再算四次方…$

4. 解密$m=c_2*((c_1)^a)^{-1}(mod\ p)=31*(50^{58})^{-1}(mod\ 97)$m=c2∗((c1)a)−1(mod p)=31∗(5058)−1(mod 97)

   $50^{58}(mod\ 97)$5058(mod 97)认真算一下，发现4次方是-1,之后的八次方，十六次方，以及三十二次方都是1，故最后的结果是75。

   75的逆为22，故$m=31*22(mod\ 97)=3$m=31∗22(mod 97)=3。成功解密得到了明文。

Elliptic Curve

椭圆曲线密码与Elgmal极为类似，可以对照记忆。

椭圆曲线定义

椭圆曲线是满足$y^2=x^3+ax+b \ \ \ a,b\in R$y2=x3+ax+b   a,b∈R的所有解$(x,y)\in R\times R$(x,y)∈R×R，加上一个无穷远点O。

椭圆曲线上的加法

这个椭圆曲线上的加法十分重要，必须要背出来，之后的加密需要用到。

当两个点关于x轴对称的话，那么他们相加为O。一个点加上一个O，还是本身。

如果那么普通的两个点P($x_P,y_P$xP,yP)与Q($x_Q,y_Q$xQ,yQ)，假设它们相加为R点（$x_R,y_R$xR,yR）的话。

我们首先需要算一个神秘的值$\alpha$α。这个$\alpha$α需要分两种情况讨论。如果$P$P和$Q$Q不是同一个点，$\alpha$α就是就是两点的斜率。如果P和Q是同一个点，那么这时$\alpha = (3x^2+a)/2y$α=(3x2+a)/2y，这里实际上不用区分$x_R$xR还是$x_P$xP了，因为两者的坐标相同。

然后$x_R=\alpha^2-x_P-x_Q\ mod\ p$xR=α2−xP−xQ mod p。

$y_R=\alpha(x_P-x_R)-y_P\ mod\ p$yR=α(xP−xR)−yP mod p

没什么好记忆的法子，考试前多背几遍。

椭圆曲线上加法例子

$\alpha = (3 * 1 + 4 ）/ 6\ mod\ 2773$α=(3∗1+4）/6 mod 2773。

这里我们可以发现式子里的除法不是真的除，而是要转化为乘它的逆。

$2773=462*6+1$2773=462∗6+1

$1 = 2773-462*6$1=2773−462∗6

6的逆为-462，即2311, 则$\alpha = 2312$α=2312。

ok，然后$x_R=\alpha^2-x_p-x_p=1771\ (mod\ 2773)$xR=α2−xp−xp=1771 (mod 2773)

$y_R=\alpha(x_P-x_R)-y_R=705\ (mod\ 2773)$yR=α(xP−xR)−yR=705 (mod 2773)

二次剩余定义

当我们判断d是p的二次剩余后，去求解x的时候，如果p是一个模4余3的素数，那么x就可以直接给出结果

$x=\pm d^{(p-1)/4} \ mod\ p$x=±d(p−1)/4 mod p

ECC中的离散对数DLP问题

在椭圆曲线群中的$k\times\alpha$k×α，对应$Z_p$Zp中的$\alpha ^k$αk。

在$Z_p$Zp下求$k$k很难，在椭圆曲线中也很难求$k$k，便以此为依据设计了一个陷门函数，形成了ECC。

密钥生成

1. 选择一个椭圆曲线E(mod p)，p是一个大素数。

2. 选择E上的点G，使得$n\times G=O$n×G=O

3. 选择随机数a,$a<n$a<n

4. 计算$P_A=a\times G$PA=a×G。

公钥$(p, G, P_A)$(p,G,PA)，私钥$a$a。

和Elgmal完全一致。

加密过程

假设需要加密的信息为$P_m$Pm。和Elgmal一样，会加密出来一个$C_1$C1，一个$C_2$C2。

$C_1=kG$C1=kG

$C_2=P_m+kP_A$C2=Pm+kPA

我们发现实际上就是把Elgmal的乘号变成加号，幂变成乘号，就能从Elgmal类推出ECC。这里值得注意的是，我们的信息$P_m$Pm是一个点，实际上$C_1$C1和$C_2$C2也是点，里面有横坐标和纵坐标两个信息。

解密过程

Elgmal的解密是这样的$m=c_2*((c_1)^a)^{-1}$m=c2∗((c1)a)−1。我们可以类推得到ECC的解密公式为$P_m=C_2+(-a*C_1)=C_2-aC_1$Pm=C2+(−a∗C1)=C2−aC1

值得注意的是，加密过程和解密过程中的计算都没有模p。因为这些都是点，两个点相加得时候得计算公式中就是有模p了，相当于每次计算实际都在模p，故最外层就不用写模p了，写了也没用2333，一个点最后怎么模p呢？

例子

$Z_{23}$Z23上的椭圆曲线:$y^2=x^3+x+1$y2=x3+x+1

取$G=(6, 4)$G=(6,4),$a=3$a=3，计算

$P_A=3*(6, 4)=(6,4)+(6,4)+(6,4)$PA=3∗(6,4)=(6,4)+(6,4)+(6,4)

我们先算$(6,4)+(6,4)$(6,4)+(6,4)，求$\alpha=5$α=5。

$x_R=13,\ y_R=7$xR=13, yR=7。即$(6,4)+(6,4)=(13,7)$(6,4)+(6,4)=(13,7)。再计算$(13,7)+(6,4)$(13,7)+(6,4)。

求得$\alpha=3/7=3*10=30=7$α=3/7=3∗10=30=7。

$x_R=7$xR=7，$y_R=12$yR=12

得最后的结果为$(7, 12)$(7,12)

从这里可见ECC的手工计算量有多大，一个普通的乘法实际上内部复杂无比。

于是公钥为$(23, (6,4), (7,12))$(23,(6,4),(7,12))，私钥为a=3

假设明文为$P_m=(5, 4)$Pm=(5,4)

然后选择随机数k=2，现在开始加密

$C_1=kG=2*(6,4)=(6,4)+(6,4)=(13,7)$C1=kG=2∗(6,4)=(6,4)+(6,4)=(13,7)

这里舒服了哈哈，因为之前求$3*(6,4)$3∗(6,4)的过程中已经把$(6,4)+(6,4)$(6,4)+(6,4)算出来了。

$C_2=P_m+k*P_A=(5,4)+2*(7,12)$C2=Pm+k∗PA=(5,4)+2∗(7,12)

先求$(7,12)+(7,12)$(7,12)+(7,12)，求得$\alpha=(3*49+1)/24$α=(3∗49+1)/24，这里就比较有趣了，因为24就是1，1的逆还是1，所以直接不用算了。

$\alpha=10$α=10。

$x_R=\alpha^2-x_p-x_q=100-14=86=17$xR=α2−xp−xq=100−14=86=17

$y_R=\alpha(x_p-x_R)-y_p=10*(-10)-12=158=3$yR=α(xp−xR)−yp=10∗(−10)−12=158=3。

故$(7,12)+(7,12)=(17,3)$(7,12)+(7,12)=(17,3)。

再求$(17,3)+(5,4)$(17,3)+(5,4)

先求$\alpha=21$α=21。$x_R=21^2-17-5=5$xR=212−17−5=5。

$y_R=21*(17-5)-3=19$yR=21∗(17−5)−3=19。

得最后得结果为$(5,19)$(5,19)

所以我们加密的结果为$((13,7),(5,19))$((13,7),(5,19))。

现在还是解密$m=C_2-aC_1=(5,19)-3*(13,7)$m=C2−aC1=(5,19)−3∗(13,7)

$(13+7)+(13,7)=(5,4)$(13+7)+(13,7)=(5,4)。

$(5,4)+(13,7)=(17,3)$(5,4)+(13,7)=(17,3)

所以$m=(5,19)-(17,3)$m=(5,19)−(17,3)。

到这一步你可能不知所措了，因为我们之前所有的运算都是两个点之间的加法，那减法要怎么求呢？

我们可以根据一开始的定义

设$P=(x,y)$P=(x,y)则$-P=(x,-y)$−P=(x,−y)。

所以$m=(5,19)-(17,3)=(5,19)+(-(17,3))=(5,19)+(17,-3)$m=(5,19)−(17,3)=(5,19)+(−(17,3))=(5,19)+(17,−3)

所以实际上减法就是减数的纵坐标转化为相反数，就能转化加法了。

$\alpha=22/(-12)=22/11$α=22/(−12)=22/11。这里我们又遇到了一个比较特别的情况，上下数可以整除了，但是我们应该将将除法转变为乘上分母的逆。11的逆是21。则$\alpha=22*21=(-1)*(-2)=2$α=22∗21=(−1)∗(−2)=2。竟然与直接除是一样的结果。

以后如果发现分母和分子能够直接整除，便可以直接除得到结果，如果发现不能整除，便将乘以分母的逆。

$x_R=2^2-22=-18=5$xR=22−22=−18=5

$y_R=2(5-5)-19=4$yR=2(5−5)−19=4。

所以最后的结果为$(5,4)$(5,4)。和一开始的信息相同，解密成功。

Rabin

Rabin密码利用的数学原理是离散平方根问题，实际上就是合数模下二次剩余求解难的问题。

它的形式非常简单，选择两个模四余数3的素数，做为私钥，将它们的乘积做为公钥。

即，私钥$(p,q)$(p,q)。公钥$n$n。

加密也十分简单。$c=m^2\ (mod\ n)$c=m2 (mod n)

解密的话就是求解同余方程$m^2=c(mod\ n)$m2=c(mod n)。把m求出来即可。

由数学基础知

也就是将模n的同余式转化为求一个同余式组。由于模4余三的素数的解可以直接写出来。然后再根据解出来的信息根据中国剩余定理求出解。一般的解会有4个。

Rabin举例

$n=77$n=77，$c=23$c=23。

这里我们可以轻松得将合数$77$77分解为$7$7和$11$11。7和11正好都是模4余3得素数，相当于白给了。实际上的Rabin密码肯定不会用这么简单的n，肯定是两个大素数相乘的，所以这个Rabin密码看起来利用的数学问题是离散平方根，其基础还是分解问题，如果可以轻易的分解，那就和这道题一样白给了。

$m^2=23\ mod\ 77$m2=23 mod 77

可以转化为以下两个式子

$m^2=23\ mod\ 11$m2=23 mod 11

$m^2 = 23\ mod\ 7$m2=23 mod 7

然后根据模4余三素数的结论

$m=\pm23^{12/4}\ mod\ 11=\pm1$m=±2312/4 mod 11=±1

$m=\pm 23^{8/4}\ mod\ 7=\pm4$m=±238/4 mod 7=±4

这里进行运算的时候，比如第一个式子，因为是模11意义下的，所以23直接就是1，所以直接得出结果了，十分方便。

接下来我们复习一下中国剩余定理。

$x=b_1\ mod\ m_1$x=b1 mod m1

$x=b_2\ mod\ m_2$x=b2 mod m2

$m=m_1*m_2$m=m1∗m2

得$M_1=m2,M_2=m1$M1=m2,M2=m1。因为$m_i*M_i=m$mi∗Mi=m

求$M_1&#x27;=invmod(M_1,m_1)$M1′=invmod(M1,m1)

$M_2&#x27;=invmod(M_2,m_2)$M2′=invmod(M2,m2)

最后得解就是$x=b_1M_1M_1&#x27;+b_2M_2M_2&#x27;\ mod(m)$x=b1M1M1′+b2M2M2′ mod(m)

我们来算一下这道例子。

$m_1=11,m_2=7,m=77$m1=11,m2=7,m=77。

$M_1=7,M_2=11$M1=7,M2=11

$M_1&#x27;=8,M_2&#x27;=2$M1′=8,M2′=2   这里求逆得时候可以直接试，7关于11的逆怎么求呢？直接从1试到8，发现$7*8 =56=1$7∗8=56=1，那8就是逆了。

则最后的解为$x=56b_1+22b_2\ mod\ 77$x=56b1+22b2 mod 77。

这里的$b_1$b1和$b_2$b2实际上都有两种可能，分别为$\pm1$±1和$\pm4$±4。

最后的解分别为$67,45,32,10$67,45,32,10。

Knapsack

背包密码。将信息01串隐藏在选择哪个背包中，比如第一个选，第二个不选，那就是10。

这里我们只考虑简单背包，也就是给你一个重量后，到底选择哪些背包是唯一确定的。

值得注意的是，这里的例子还不是公钥密码，因为它只有一个密钥。我们需要将这种背包的思路转化为一个巧妙的公钥密码。

于是，我们便对这个背包改变一波，给大众一个更改后的背包。

首先取一个整数S，S需要比原本背包的总共重量大。

然后再取一个和S互素的数$t$t。

然后将原始的背包的每个重量都乘上这个t，构成一个新包（记得模

即$u=(u_1,u_2,..u_n)=(ta_1\ mod\ s, ta_2\ mod\ s,...,ta_n\ mod\ s)$u=(u1,u2,..un)=(ta1 mod s,ta2 mod s,...,tan mod s)