废话

大二上开始学习现代密码学了，说到密码学如果算上古典密码的话我第一次解除的应该是rot13还是在一个新生赛的misc里，转眼都过去快一年了吧，平时很少做密码的题，比赛里也仅限于RSA的签到题，平时也对数学谈不上喜欢，那不如趁着写作业的机会写写文字，也好好学学密码学吧~

仿射变换

题一

p11

THE NATIONAL SECURITY AGENCY

带入加密即可得到密码
eg:
首字母 T 对应 19

带入得故第一个加密字母为Y

同理可得加密结果
YWP KXYHVKXO NPTJCHYB XLPKTB

python代码

def encode(m,a,b):
    c=''
    for i in m:
        if i==' ':
            c+=i
            continue
        num = ord(i)-ord('A')
        res = (a*num+b)%26
        c+=chr(res+ord('A'))
    return c
if __name__ == '__main__':
    a=11
    b=23
    m='THE NATIONAL SECURITY AGENCY'
    c = encode(m,a,b)
    print(c)

题二

p11 习题 2

一直明文的前两个字符是if,可列出以下俩式子

两式相减可得

得
带入可得
带入

得明文为ifyoucanreadthisthankateahcer

python 代码

def decode(c,a,b):
    a_inv = exgcd(a,26)
    m = ""
    for i in c:
        if i == " ":
            m+=i
            continue
        num = ord(i) - ord('a')
        m+=chr((a_inv[0]*(num-b))%26+ord('a'))
    return m
def get_num(a):
    return ord(a)-ord('a')
def get_a_b(m1,m2,c1,c2):
    m1=get_num(m1)
    m2=get_num(m2)
    c1 = get_num(c1)
    c2 = get_num(c2)
    """
    8a+b(mod 26)=4
    5a+b(mod 26)=3
    """
    a= (exgcd(m1-m2,26)[0]*(c1-c2))%26
    b=(c1-a*m1)%26
    return a,b


if __name__ == '__main__':
    c ="edsgickxhuklzveqzvkxwkzukvcuh"
    m1='i'
    m2='f'
    c1='e'
    c2='d'
    a,b=get_a_b(m1,m2,c1,c2)
    m=decode(c,a,b)
    print(m)

多表代换密码

对于多表替换加密来说，加密后的字母几乎不再保持原来的频率，所以我们一般只能通过寻找算法实现对应的弱点进行破解，顾不能通过字频来破解加密

在教材中，当时，加密密码为希尔密码

一般逆矩阵的计算公式:

$$A^{-1} =\frac{A^*}{\vert A \vert}=\frac{1}{\vert A \vert} \times A^*$$

其中 为矩阵， 为 的逆矩阵， 为 的伴随矩阵， 为 的行列式。

希尔密码密钥矩阵的逆矩阵:

$$K^{-1} = d^{-1} \times adj(K)$$

其中 为密钥矩阵， 为 的逆矩阵， 为 的行列式， 为 的伴随矩阵

2 x 2矩阵的伴随矩阵如下计算：

$$adj \begin{pmatrix} a & b \\ c & d \end{pmatrix} = \begin{pmatrix} d & -b \\ -c & a \end{pmatrix}$$

题三

p12 习题 4

设

又分为俩组，则
,,,

由公式得
式子1:
式子2:
式子3:
式子4:
先计算式子1和式子3
对于式子1

$$a=\frac{4-14b}{3}\pmod{26}$$

又在模下的逆元为
故

带入式子3得

带入式子1得
同理可得

python代码

根据得

故可得python代码

import numpy as np
def exgcd(a, b):
    if b == 0:
        x = 1
        y = 0
        return x, y
    x1, y1 = exgcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return x, y
def mod_inverse(M,N):
    det = int(round(np.linalg.det(M)))
    det = det % 26
    det_exgcd = exgcd(det,26)[0]%26
    return det_exgcd
def adjunct_matrix(M):
    ret=M
    ret[0][0]=M[1][1]%26
    ret[0][1]=(-M[0][1])%26
    ret[1][0]=(-M[1][0])%26
    ret[1][1]=M[0][0]%26
    return ret
def know_plaintext_attack(m,c):
    m_list=[ord(char)-ord('a') for char in m]
    c_list = [ord(char) - ord('a') for char in c]
    M = np.array(m_list).reshape(-1,2)
    C=np.array(c_list).reshape(-1,2)
    M_inv = mod_inverse(M,26)
    M_adj = adjunct_matrix(M)
    M_exgcd = np.dot(M_inv,M_adj)
    A=np.dot(M_exgcd,C)%26
    return A
if __name__=='__main__':
    A = know_plaintext_attack("dont","elni")
    print(A)

流密码

题1

p30 1

时有4种线性反馈函数分别为、、、

函数 ：
| | | | 输出 |
| :—-: | :—-: | :—-: | :—-: |
| 1 | 0 | 1 | |
| 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 |

故周期为3

函数 :

周期7

函数:
| | | | 输出 |
| :—-: | :—-: | :—-: | :—-: |
| 1 | 0 | 1 | |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |

周期2

：
| | | | 输出 |
| :—-: | :—-: | :—-: | :—-: |
| 1 | 0 | 1 | |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 |

周期7

python代码求

def lfsr(c1, c2, c3, init_state, length=15):
    state = init_state.copy()
    sequence = []
    seen_states = {}
    for i in range(length):
        output = state[0]
        sequence.append(output)

        feedback = (c1 * state[0]) ^ (c2 * state[1]) ^ (c3 * state[2])

        state = [state[1], state[2], feedback]

        state_tuple = tuple(state)
        if state_tuple in seen_states:
            cycle_start = seen_states[state_tuple]
            period = i - cycle_start
            return sequence, period
        else:
            seen_states[state_tuple] = i

    return sequence, None

initial_state = [1, 0, 1]

feedback_functions = [
    (1, 1, 0),  # x1 ⊕ x2
    (1, 0, 1),  # x1 ⊕ x3
    (1, 1, 1),  # x1 ⊕ x2 ⊕ x3
    (1, 0, 0),  # x1
]

for idx, (c1, c2, c3) in enumerate(feedback_functions):
    sequence, period = lfsr(c1, c2, c3, initial_state)
    print(f"反馈函数 {idx + 1}: c1={c1}, c2={c2}, c3={c3}")
    print(f"输出: {sequence}")
    print(f"周期: {period}\n")

题2

p30 2

因为$p(x)|(x^p-1)$,故存在使得$x^p-1=p(x)q(x)$
又$p(x)A(x)=\phi(x)$
有

$$(x^p-1)A(x)=\phi(x)q(x)$$

又因为次数不超过
故不超过
又知次数不超过
故次数不超过
可得任意正整数( i )，都有
设故有故所以

又有

$$A(x) = \frac{a_1+a_2x+...+a_rx^{r-1}}{x^r-1}=\frac{\phi(x)}{p(x)}$$

又不可约，次数不超过所以，故
故有

题3

p30 3
由

$$f(a_1,a_2,a_3,a_4)=a_1\oplus a_4 \oplus 1 \oplus a_2a_3$$

周期为5

def get_(n, init, steps=20):
    state = init[:]
    sequence = []

    for _ in range(steps):
        feedback = state[0] ^ state[3] ^ 1 ^ (state[1] & state[2])
        sequence.append(state[-1])
        state = [feedback] + state[:-1]
    return sequence

def find_period(sequence):
    length = len(sequence)
    for p in range(1, length):
        if sequence[:p] == sequence[p:2*p]:
            return p
    return length


n = 4
init = [1, 1, 0, 1]


output = get_(n, init)


period = find_period(output)

print("输出:", output)
print("周期:", period)