维吉尼亚密码——笔记1

原理

• 是一种多表代换密码
• 若**$K=(k_0,k_1,k_2,...,k_{m-1})$K=(k0​,k1​,k2​,...,km−1​),即**长度为m；明文为$(x_0,x_1,x_2,...)$(x0​,x1​,x2​,...),对应密文为$(y_0,y_1,y_2,...)$(y0​,y1​,y2​,...)
• 则对于明文中的每一个字符$x_i$xi​，有$\begin{cases} 加密函数\,e(x_i)=(x_i+k_{i\,mod\, m})\\ 解密函数\,d(y_i)=(y_i-k_{i\,mod\, m}) \end{cases}${加密函数e(xi​)=(xi​+kimodm​)解密函数d(yi​)=(yi​−kimodm​)​

无**破译分析

• 首先需要找到**的长度m
  • Kasiski测试法
    • 由Friedrich Kasiski在1863年给出描述，由Charles Babbage于1854年首先发现

    基于这样一个事实：两个相同的明文段将加密成相同的密文段，它们的位置间距假设为$\delta$δ，则$\delta=0(mod\,m)$δ=0(modm)。反过来，如果在密文中观察到两个相同的长度至少为3的密文段，那么将给破译者带来很大方便，因为它们实际上对应了相同的明文串

    • 工作流程：
      • 搜索长度至少为3的相同的密文段，记下其离起始点的那个密文段的距离
      • 假设得到距离为：$\delta_{1},\delta_{2},...$δ1​,δ2​,...
      • 那么可以猜测$m$m为这些$\delta_i$δi​的最大公因子的因子
  • 重合指数法
    • 由William Friedman提出

    设$\textbf{x}=x_1x_2...x_n$x=x1​x2​...xn​是一条n个字母的串，$\textbf{x}$x的重合指数记为$I_c(x)$Ic​(x),定义为$\textbf{x}$x中两个随机元素相同的概率

    • 若$f_0,f_1,...,f_{25}$f0​,f1​,...,f25​分别表示A,B,…,Z在x中出现的频数
    • 则$I_c(x) =\frac{\sum_{i=0}^{25}\binom{f_i}{2}}{\binom{n}{2}}=\frac{\sum_{i=0}^{25}f_i(f_i-1)}{n(n-1)}$Ic​(x)=(2n​)∑i=025​(2fi​​)​=n(n−1)∑i=025​fi​(fi​−1)​
    • 如果x是英文文本串，有$I_c(x)\approx0.065$Ic​(x)≈0.065
    • 如果x是一个完全的随机串，有$I_c(x)=\frac{1}{26}\approx0.038$Ic​(x)=261​≈0.038
    • 也就是说对于一个英文文本串，或是其经过移位密码加密后的密文，其重合指数$I_c(x)$Ic​(x)应该接近0.065
      • 但Vigenere加密中对每一明文字符移位距离不一定相同
      • 对这种问题，我们将用**字中相同字符加密后的密文提取出
        • 如$\textbf{y}_i=y_iy_{m_i}y_{2m+i}...$yi​=yi​ymi​​y2m+i​...这样提取出的字符串的重合指数应该接近0.065
    • 由上一步分析结果，可对m进行测试，对于每一个测试的m，可将密文$y$y分组$\begin{aligned} \textbf{y}_0&=y_0y_my_{2m}...\\ \textbf{y}_1&=y_1y_{m+1}y_{2m+1}...\\ \vdots\\ \textbf{y}_{m-1}&=y_{m-1}y_{2m-1}y_{3m-1}... \end{aligned}$y0​y1​⋮ym−1​​=y0​ym​y2m​...=y1​ym+1​y2m+1​...=ym−1​y2m−1​y3m−1​...​
    • 求出这些字串的重合指数平均数，按平均数与0.065的接近程度排序，得到一系列m的可能值
    • 可依次对每个m的可能值进行下步内容（确定**内容+译码）
• 得到**长度$m$m后，确定**内容
  • 由前步分析知，对于分割的每一个子串，子串中每个密文字符都是用同一**字符加密的，相当于一个移位加密，其中子串$\textbf{y}_i$yi​对应移位为$k_i$ki​
  • 用$n$n表示字串$\textbf{y}_i$yi​长度，$f_0,f_1,...,f_{25}$f0​,f1​,...,f25​表示此子串中字母A,B,…,Z出现的频数，则有26个字母在子串中的概率分布估计为：
    $\frac{f_0}{n},\frac{f_1}{n},...,\frac{f_{25}}{n}$nf0​​,nf1​​,...,nf25​​
  • 又因为移位为$k_i$ki​，所以明文中频率$\frac{f_j}{n}$nfj​​等于密文中频率$\frac{f_{j+k_i}}{n}$nfj+ki​​​
  • 于是有数值$M=\sum_{i=0}^{25}\frac{p_if_{i+k_i}}{n}\approx\sum_{i=0}^{25}p_i^2=0.065$M=i=0∑25​npi​fi+ki​​​≈i=0∑25​pi2​=0.065
  • 到现在我们已经有了如下问题转换$确定**内容\Rightarrow确定每个子串中对应k_i\Rightarrow通过改变k_i值对M进行测试$确定密钥内容⇒确定每个子串中对应ki​⇒通过改变ki​值对M进行测试
  • 如上步所述，对$k_i$ki​测试，记测试值为$g,(0\leq g\leq 25)$g,(0≤g≤25),有数值$M_g=\sum_{i=0}^{25}\frac{p_if_{i+g}}{n}$Mg​=i=0∑25​npi​fi+g​​
  • 取使得$M_g$Mg​最接近0.065的g作为$k_i$ki​
    • 这样的取法可能导致最终**并不一定是正确的，但大部分正确的可能性比较大，最后解密结果可能与真实结果有偏差，但偏差一般不会很大，一般可以人为看出来，如原文为Helloworld，可能错破译为Hjllowhrld
  • 集合所得到的所有$k_i$ki​，合成最终**字
• 解密

代码

class VigenereCipher:
    def __init__(self,s):
        self.msg=s.lower()
    # 更改字串
    def update(self,s):
        self.msg=s.lower()
    # 重合指数计算
    def Ic(self,x):
        assert type(x)==str
        x=x.lower()
        n=len(x)
        ans=0
        for i in range(26):
            f=x.count(chr(i+ord('a')))
            ans+=f*(f-1)
        ans=float(ans)/(n*(n-1))
        return ans
    # 得到**字长度的可能值（依各子串重合指数平均数与0.065的接近排序，接近的在前）
    def findKeyLen(self,maxkeylen=30):
        assert type(self.msg)==str
        mp={}
        for m in range(1,maxkeylen+1):
            ans=sum([self.Ic(self.msg[i::m]) for i in range(m)])/float(m)
            mp[m]=ans
        mp=dict(sorted(mp.items(),key=lambda item:abs(item[1]-0.065)))
        return list(mp.keys())
    # 确定**内容
    # 并不一定是真正的**内容，只是可能性大，即便**长度判断是正确的
    def findKeyContent(self,keylen):
        key=""
        p=[float(i)/1000 for i in [82,15,28,43,127,22,20,61,70,2,8,40,24,67,75,19,1,60,63,91,28,10,23,1,20,1]]
        for i in range(keylen):
            yi=self.msg[i::keylen]
            n=len(yi)
            #频率f/n
            fn=[float(fi)/n for fi in [yi.count(chr(i+ord('a'))) for i in range(26)]]
            M=lambda g: sum(p[i]*fn[(i+g)%26] for i in range(26))
            # 直接令每一块使得Mg最接近0.065的为ki
            ki=min(range(26),key=lambda g:abs(M(g)-0.065))
            key+=chr(ord('a')+ki)            
        return key
    # 根据**对msg解密
    def decode(self,key):
        assert type(self.msg)==str
        key=key.lower()
        m=len(key)
        digit=lambda a: ord(a)-ord('a')
        alpha=lambda a: chr(a+ord('a'))
        sub=lambda a,b: alpha((digit(a)-digit(b))%26)
        ans=""
        for i in range(len(self.msg)):
            ans+=sub(self.msg[i],key[i%m])
        return ans
    # 根据**对msg加密
    def encode(self,key):
        assert type(self.msg)==str
        key=key.lower()
        m=len(key)
        digit=lambda a: ord(a)-ord('a')
        alpha=lambda a: chr(a+ord('a'))
        add=lambda a,b: alpha((digit(a)+digit(b))%26)
        ans=""
        for i in range(len(self.msg)):
            ans+=add(self.msg[i],key[i%m])
        return ans
    # **
    def violentCrack(self,maxkeylen=30):
        cnt=0
        for m in self.findKeyLen(maxkeylen):
            key=self.findKeyContent(m)
            print("key="+key+":\n"+self.decode(key),end='\n\n')
            cnt+=1
            if cnt%10 == 0:
                q=input('输入q退出。。。')
                try:
                    if ord(q[0]) in [ord('q'),ord('Q')]:
                        return 
                except:
                    pass


if __name__=="__main__":
    s="CHREEVOAHMAERATBIAXXWTNXBEEOPHBSBQMQEQERBWRVXUOAKXAOSXXWEAHBWGJMMQMNKGRFVGXWTRZXWIAKLXFPSKAUTEMNDCMGTSXMXBTUIADNGMGPSRELXNJELXVRVPRTULHDNQWTWDTYGBPHXTFALJHASVBFXNGLLCHRZBWELEKMSJIKNBHWRJGNMGJSGLXFEYPHAGNRBIEQJTAMRVLCRREMNDGLXRRIMGNSNRWCHRQHAEYEVTAQEBBIPEEWEVKAKOEWADREMXMTBHHCHRTKDNVRZCHRCLQOHPWQAIIWXNRMGWOIIFKEE"
    
    ss="KCCPKBGUFDPHQTYAVINRRTMVGRKDNBVFDETDGILTXRGUDDKOTFMBPVGEGLTGCKQRACQCWDNAWCRXIZAKFTLEWRPTYCQKYVXCHKFTPONCQQRHJVAJUWETMCMSPKQDYHJVDAHCTRLSVSKCGCZQQDZXGSFRLSWCWSJTBHAFSIASPRJAHKJRJUMVGKMITZHFPDISPZLVLGWTFPLKKEBDPGCEBSHCTJRWXBAFSPEZQNRWXCVYCGAONWDDKACKAWBBIKFTIOVKCGGHJVLNHIFFSQESVYCLACNVRWBBIREPBBVFEXOSCDYGZWPFDTKFQIYCWHJVLNHIQIBTKHJVNPIST"
    tmp=VigenereCipher(ss)
    tmp.violentCrack()