郑长生 發表於 2026-3-31 20:02:00

密码学系列之流密码&RSA&ECC等

<p><img src="https://img2024.cnblogs.com/blog/3426414/202603/3426414-20260331195854707-1269957529.png" alt="Snipaste_2026-03-31_19-58-43" loading="lazy"><br>
注意本篇大多数的题解都是直接在VsCode点击按钮运行的，如果控制台终端输入python ABC.py(ABC.py为你写的脚本的名称)很可能会报一些小错误。这里我也不知道为什么，真的想不懂。</p>
<h1 id="lsfr">LSFR</h1>
<p>题目：3级线性反馈移位寄存器在c3=1时有4种线性反馈函数,设其初始状态为(a1,a2,a3)=(1,0,1),求各线性反馈函数的输出序列及周期,输出他们的密钥流,并利用生成的密钥流对明文'0x0123456789ABCDEF'进行加密,输出加密后的结果,再对密文进行解密,输出解密后的结果。<br>
已知：</p>
<ul>
<li>寄存器长度：n = 3</li>
<li>状态：(a1, a2, a3)</li>
<li>初始状态：(1, 0, 1)</li>
<li>条件：<strong>c3 = 1</strong></li>
</ul>
<p>LFSR 的反馈函数是：f=c1a1⊕c2a2⊕c3a3。因为：c3=1，所以：f=c1a1⊕c2a2⊕a3</p>
<p>因为：<span class="math inline">\(c_1 \in \{0,1\}\)</span>，<span class="math inline">\(c_2 \in \{0,1\}\)</span>，所以一共有4种情况，对应4 个反馈函数。</p>
<table>
<thead>
<tr>
<th>编号</th>
<th><span class="math inline">\((c_1,c_2,c_3)\)</span></th>
<th>反馈函数</th>
<th>周期</th>
</tr>
</thead>
<tbody>
<tr>
<td>1</td>
<td><span class="math inline">\((0,0,1)\)</span></td>
<td><span class="math inline">\(a_3\)</span></td>
<td>很短</td>
</tr>
<tr>
<td>2</td>
<td><span class="math inline">\((0,1,1)\)</span></td>
<td><span class="math inline">\(a_2 \oplus a_3\)</span></td>
<td>较短</td>
</tr>
<tr>
<td>3</td>
<td><span class="math inline">\((1,0,1)\)</span></td>
<td><span class="math inline">\(a_1 \oplus a_3\)</span></td>
<td>可能最大</td>
</tr>
<tr>
<td>4</td>
<td><span class="math inline">\((1,1,1)\)</span></td>
<td><span class="math inline">\(a_1 \oplus a_2 \oplus a_3\)</span></td>
<td>最大周期7（m序列）</td>
</tr>
</tbody>
</table>
<p>状态更新原则：</p>
<p></p><div class="math display">\[(a_1, a_2, a_3) \rightarrow (a_2, a_3, f)
\]</div><p></p><p>每一轮输出值：</p>
<p></p><div class="math display">\[\text{输出值} 为 a_1
\]</div><p></p><pre><code class="language-python">def lfsr_step(state, c1, c2):
    a1, a2, a3 = state
    f = (c1 &amp; a1) ^ (c2 &amp; a2) ^ a3
    return (a2, a3, f)


def generate_sequence(init_state, c1, c2):
    state = init_state
    seen = []
    output = []

    while state not in seen:
      seen.append(state)
      output.append(state)
      state = lfsr_step(state, c1, c2)

    return output, len(seen)


def bits_to_bytes(bits):
    res = []
    for i in range(0, len(bits), 8):
      byte = 0
      for j in range(8):
            if i + j &lt; len(bits):
                byte = (byte &lt;&lt; 1) | bits
      res.append(byte)
    return res


def encrypt(hex_str, keystream_bits):
    data = bytes.fromhex(hex_str)
    ks = bits_to_bytes(keystream_bits)
    return bytes( for i, d in enumerate(data)]).hex()


def decrypt(cipher_hex, keystream_bits):
    data = bytes.fromhex(cipher_hex)
    ks = bits_to_bytes(keystream_bits)
    return bytes( for i, d in enumerate(data)]).hex()


# ==========================
# 主程序
# ==========================
init_state = (1, 0, 1)
plaintext = "0x0123456789ABCDEF"

configs = [
    (0, 0),
    (0, 1),
    (1, 0),
    (1, 1)
]

for c1, c2 in configs:
    print("=" * 40)
    print(f"反馈函数: f = {c1}*a1 ⊕ {c2}*a2 ⊕ a3")

    seq, period = generate_sequence(init_state, c1, c2)

    print("输出序列:", seq)
    print("周期:", period)

    # 生成64bit密钥流
    keystream = (seq * (64 // len(seq) + 1))[:64]
    print("密钥流(bit):", keystream)

    # 加密
    cipher = encrypt(plaintext, keystream)
    print("密文:", cipher)

    # 解密
    plain = decrypt(cipher, keystream)
    print("解密:", plain)


</code></pre>
<p><img src="https://img2024.cnblogs.com/blog/3426414/202603/3426414-20260331193750927-913770287.png" alt="Snipaste_2026-03-31_16-52-25" loading="lazy"></p>
<h1 id="nflsr">NFLSR</h1>
<p>题目：设n=4,f(a1,a2,a3,a4)=a1* a4^(a2 * a3),初始状态为(a1,a2,a3,a4)=(1,1,0,1),求此非线性反馈移位寄存器的输出序列及周期,输出他的密钥流,并利用生成的密钥流对明文'0x0123456789ABCDEF'进行加密,输出加密后的结果,再对密文进行解密,输出解密后的结果。<br>
流密码原理 1）生成密钥流（keystream）；2）明文 XOR 密钥流 → 密文 3）密文 XOR 密钥流 → 明文。<br>
加密：cipher = plaintext XOR keystream    解密：decrypt(cipher) == plaintext</p>
<ul>
<li>寄存器长度：<span class="math inline">\(n = 4\)</span></li>
<li>状态：<span class="math inline">\((a_1, a_2, a_3, a_4)\)</span></li>
<li>反馈函数：</li>
</ul>
<p></p><div class="math display">\[f(a_1, a_2, a_3, a_4) = a_1 \cdot a_4 \oplus (a_2 \cdot a_3)
\]</div><p></p><p>状态更新原则：</p>
<p></p><div class="math display">\[(a_1, a_2, a_3, a_4) \rightarrow (a_2, a_3, a_4, f)
\]</div><p></p><p>输出序列一般取：</p>
<p></p><div class="math display">\[\text{输出} = a_1 \quad (\text{最左边})
\]</div><p></p><pre><code class="language-python">def nlfsr_step(state):
    a1, a2, a3, a4 = state
    # 非线性反馈函数
    f = (a1 &amp; a4) ^ (a2 &amp; a3)
    # 移位
    return (a2, a3, a4, f)


def generate_sequence(init_state):
    state = init_state
    seen = []
    output_seq = []

    while state not in seen:
      seen.append(state)
      output_seq.append(state)# 输出 a1
      state = nlfsr_step(state)

    period = len(seen)
    return output_seq, period


def bits_to_bytes(bits):
    res = []
    for i in range(0, len(bits), 8):
      byte = 0
      for j in range(8):
            if i + j &lt; len(bits):
                byte = (byte &lt;&lt; 1) | bits
      res.append(byte)
    return res


def encrypt(plaintext_hex, keystream_bits):
    plaintext = bytes.fromhex(plaintext_hex)
    keystream_bytes = bits_to_bytes(keystream_bits)

    cipher = bytes( for i, p in enumerate(plaintext)])
    return cipher.hex()


def decrypt(cipher_hex, keystream_bits):
    cipher = bytes.fromhex(cipher_hex)
    keystream_bytes = bits_to_bytes(keystream_bits)

    plain = bytes( for i, c in enumerate(cipher)])
    return plain.hex()


# ==========================
# 主流程
# ==========================
init_state = (1, 1, 0, 1)

# 生成序列
seq, period = generate_sequence(init_state)

print("输出序列:", seq)
print("周期:", period)

# 生成足够长的密钥流（明文8字节=64bit）
keystream_bits = (seq * (64 // len(seq) + 1))[:64]

print("密钥流(bit):\n", keystream_bits)

# 明文
plaintext = "0x0123456789ABCDEF"

# 加密
cipher = encrypt(plaintext, keystream_bits)
print("密文:", cipher)

# 解密
decrypted = decrypt(cipher, keystream_bits)
print("解密结果:", decrypted)


</code></pre>
<p><img src="https://img2024.cnblogs.com/blog/3426414/202603/3426414-20260331193808603-1658601156.png" alt="Snipaste_2026-03-31_16-47-07" loading="lazy"></p>
<h1 id="ecc">ECC</h1>
<p>题目：已知椭圆曲线E11(1,6)，编程求其上所有的点。</p>
<p>这个问题本质是在有限域 <span class="math inline">\(\mathbb{F}_{11}\)</span> 上求椭圆曲线</p>
<p></p><div class="math display">\[E: y^2 \equiv x^3 + x + 6 \pmod{11}
\]</div><p></p><p>的所有点。</p>
<p>思路：</p>
<ol>
<li>枚举 <span class="math inline">\(x \in \)</span></li>
<li>计算右边<p></p><div class="math display">\[rhs = x^3 + x + 6 \pmod{11}
\]</div><p></p></li>
<li>枚举 <span class="math inline">\(y \in \)</span>，找满足以下 条件的解<p></p><div class="math display">\[y^2 \equiv rhs \pmod{11}
\]</div><p></p></li>
<li>加上无穷远点 <span class="math inline">\(O\)</span></li>
</ol>
<pre><code class="language-C">#include &lt;stdio.h&gt;

#define p 11
#define a 1
#define b 6

typedef struct {
    int x;
    int y;
} Point;

int isOnCurve(Point point) {
    int left = (point.y * point.y) % p;
    int right = (point.x * point.x * point.x + a * point.x + b) % p;
    return left == right;
}

int main() {
    int count = 0;

    for (int x = 0; x &lt; p; x++) {
      for (int y = 0; y &lt; p; y++) {
            Point point = {x, y};
            if (isOnCurve(point)) {
                printf("(%d, %d)\n", point.x, point.y);
                count++;
            }
      }
    }

    printf("Point at infinity: O\n"); //注意，必须添加无穷远点。
    printf("Total points (including O): %d\n", count + 1);

    return 0;
}


</code></pre>
<p><img src="https://img2024.cnblogs.com/blog/3426414/202603/3426414-20260331195304921-2002982147.png" alt="Snipaste_2026-03-31_17-02-38" loading="lazy"></p>
<pre><code class="language-python">p = 11
a = 1
b = 6

points = []

for x in range(p):
    rhs = (x**3 + a*x + b) % p
    for y in range(p):
      if (y*y) % p == rhs:
            points.append((x, y))

# 加上无穷远点
points.append("O")

print("椭圆曲线上的点：")
for pt in points:
    print(pt)

print("\n点的总数：", len(points))


</code></pre>
<p><img src="https://img2024.cnblogs.com/blog/3426414/202603/3426414-20260331195321260-1736111763.png" alt="Snipaste_2026-03-31_17-11-29" loading="lazy"></p>
<h1 id="背包">背包</h1>
<p>题目：编程实现背包密码的加密和解密，假设选取的私钥为超递增背包向量 A=，选取模数k&nbsp;= 1590和乘数t&nbsp;= 43，计算新的背包向量B == t * A (mod k)作为公钥。利用上述密码算法对明文“SAUNA AND HEALTH”进行加密，输出密文，并对密文进行解密。</p>
<p>实现一个<strong>公钥加密系统</strong>：</p>
<ul>
<li>私钥：超递增序列 A</li>
<li>公钥：B = t·A mod k</li>
<li>加密：用 B 做“子集和”</li>
<li>解密：用 A 做“贪心恢复”</li>
</ul>
<pre><code class="language-go">加解密原理：
超递增序列（私钥）。A = 。 满足每个元素 &gt; 前面所有元素之和
保证子集和可唯一反推（贪心）。
↓
公钥生成 Bi​=(t⋅Ai​)mod k ， k = 1590，t = 43（i是下标）
↓
加密。把字符 → 二进制（10 bit，对应 A 长度） C=∑bi​⋅Bi​
↓
解密。1. 求逆元：t^-1 modk
   2. 还原：C′=C⋅t^−1 modk
   3. 用 A 贪心恢复 bit
</code></pre>
<pre><code class="language-python"># 私钥
A =

# 参数
k = 1590
t = 43


# 求逆元（扩展欧几里得）
def modinv(a, m):
    def egcd(a, b):
      if b == 0:
            return a, 1, 0
      g, x1, y1 = egcd(b, a % b)
      return g, y1, x1 - (a // b) * y1

    g, x, _ = egcd(a, m)
    if g != 1:
      raise Exception("无逆元")
    return x % m


# 生成公钥
B = [(t * ai) % k for ai in A]
print("公钥 B:", B)


# 字符转10bit
def char_to_bits(c):
    val = ord(c)
    return [(val &gt;&gt; i) &amp; 1 for i in reversed(range(10))]


# bits转字符
def bits_to_char(bits):
    val = 0
    for b in bits:
      val = (val &lt;&lt; 1) | b
    return chr(val)


# 加密
def encrypt(plaintext):
    ciphertext = []
    for ch in plaintext:
      bits = char_to_bits(ch)
      c = sum(b * bi for b, bi in zip(bits, B))
      ciphertext.append(c)
    return ciphertext


# 解密
def decrypt(ciphertext):
    inv_t = modinv(t, k)
    plaintext = ""

    for c in ciphertext:
      c_prime = (c * inv_t) % k

      # 贪心恢复
      bits = * len(A)
      for i in reversed(range(len(A))):
            if c_prime &gt;= A:
                bits = 1
                c_prime -= A

      plaintext += bits_to_char(bits)

    return plaintext


# ==========================
# 主程序
# ==========================
plaintext = "SAUNA AND HEALTH"

print("明文:", plaintext)

cipher = encrypt(plaintext)
print("密文:", cipher)

decrypted = decrypt(cipher)
print("解密:", decrypted)


</code></pre>
<p><img src="https://img2024.cnblogs.com/blog/3426414/202603/3426414-20260331195430721-89184755.png" alt="Snipaste_2026-03-31_17-39-48" loading="lazy"></p>
<h1 id="elgamal">ElGamal</h1>
<p>题目：编程实现ElGamal的加密和解密，假设用户A选择素数p=11和本原根g=2，并且选择私钥α=5，输出A的公钥；若用户B向用户A发送消息m=6，随机数k=7，输出对该消息加密后的密文，以及对密文进行解密的明文。</p>
<p>已知：</p>
<ul>
<li>素数：p=11</li>
<li>本原根：g=2</li>
<li>A 的私钥：α=5</li>
</ul>
<pre><code class="language-go">生成公钥。β=g^α modp,计算β=2^5 mod 11= 32 mod 11= 10,所以A的公钥为(p, g, β) = (11, 2, 10)
↓
加密（B → A）。给定，明文：m = 6，随机数：k = 7。计算 c1​=g^k mod p= 2^7 mod 11= 7,c2​=m⋅β^k mod p=6*10^7 mod 11=5。所以密文为(c1, c2) = (7, 5)
↓
解密（A）。m=c2​⋅(c1^α​)^−1 mod p=5*(7^5)^-1 mod 11=5*(7^5mod 11)^-1 mod 11=5*10^-1 mod 11=6。


</code></pre>
<pre><code class="language-go"># 参数
p = 11
g = 2
alpha = 5# 私钥

# 快速幂
def mod_exp(base, exp, mod):
    result = 1
    base %= mod
    while exp &gt; 0:
      if exp &amp; 1:
            result = (result * base) % mod
      base = (base * base) % mod
      exp &gt;&gt;= 1
    return result


# 求逆元
def modinv(a, p):
    for i in range(1, p):
      if (a * i) % p == 1:
            return i
    return None


# ==========================
# 1. 生成公钥
# ==========================
beta = mod_exp(g, alpha, p)
print("公钥 (p, g, β):", (p, g, beta))


# ==========================
# 2. 加密
# ==========================
m = 6
k = 7

c1 = mod_exp(g, k, p)
c2 = (m * mod_exp(beta, k, p)) % p

print("密文 (c1, c2):", (c1, c2))


# ==========================
# 3. 解密
# ==========================
s = mod_exp(c1, alpha, p)
s_inv = modinv(s, p)

m_decrypted = (c2 * s_inv) % p

print("解密后的明文:", m_decrypted)


</code></pre>
<p><img src="https://img2024.cnblogs.com/blog/3426414/202603/3426414-20260331195514438-840820072.png" alt="Snipaste_2026-03-31_17-44-24" loading="lazy"></p>
<h1 id="rsa">RSA</h1>
<p>题目：编程实现RSA的加密和解密，选择参数p=71593，q=77041，e=1757316971，输出公钥和私钥，并对消息“I need your best time”进行加密，输出密文。最后对密文进行解密，输出明文。<br>
已知：</p>
<ul>
<li>两个大素数 p=71593,q=77041</li>
<li>公钥指数 e=1757316971</li>
</ul>
<pre><code class="language-go">RSA 核心原理：

1.n=p⋅q
1. ϕ(n)=(p−1)(q−1)
2. 私钥 d 满足：e⋅d ≡1(modϕ(n))

3. 加密：c=m^e mod n

4. 解密：m=c^d mod n其中 m 是明文整数。字符串 → 数字需 ASCII 编码 或 utf-8。

</code></pre>
<pre><code class="language-python"># 参数
p = 71593
q = 77041
e = 1757316971

# 计算 n 和 phi
n = p * q
phi = (p - 1) * (q - 1)

# 求逆元 d
def modinv(a, m):
    def egcd(a, b):
      if b == 0:
            return a, 1, 0
      g, x1, y1 = egcd(b, a % b)
      return g, y1, x1 - (a // b) * y1
    g, x, _ = egcd(a, m)
    if g != 1:
      raise Exception("No modular inverse")
    return x % m

d = modinv(e, phi)

print("公钥 (n, e):", (n, e))
print("私钥 d:", d)


# ==========================
# 分块加密
# ==========================
message = "I need your best time"
message_bytes = message.encode('utf-8')

# 每块最大长度（保证 m &lt; n）
max_block_size = (n.bit_length() - 1) // 8
blocks = for i in range(0, len(message_bytes), max_block_size)]

cipher_blocks = []
for block in blocks:
    m_int = int.from_bytes(block, 'big')
    c = pow(m_int, e, n)
    cipher_blocks.append(c)

print("密文分块:", cipher_blocks)

# ==========================
# 分块解密
# ==========================
decrypted_bytes = b''
for c in cipher_blocks:
    m_decrypted = pow(c, d, n)
    length = (m_decrypted.bit_length() + 7) // 8
    decrypted_bytes += m_decrypted.to_bytes(length, 'big')

decrypted_message = decrypted_bytes.decode('utf-8')
print("解密后的明文:", decrypted_message)


</code></pre>
<p><img src="https://img2024.cnblogs.com/blog/3426414/202603/3426414-20260331195553279-722944016.png" alt="Snipaste_2026-03-31_18-59-50" loading="lazy"></p>
<h1 id="dh">DH</h1>
<p>题目：编程计算25的所有本原根。</p>
<ol>
<li>本原根定义</li>
</ol>
<p>对于整数 <span class="math inline">\(n\)</span> 和 <span class="math inline">\(g\)</span>（模 <span class="math inline">\(n\)</span>），如果 <span class="math inline">\(g\)</span> 的阶等于欧拉函数 <span class="math inline">\(\phi(n)\)</span>，则称 <span class="math inline">\(g\)</span> 是 <span class="math inline">\(n\)</span> 的本原根：</p>
<p></p><div class="math display">\[g^1, g^2, ..., g^{\phi(n)} \mod n
\]</div><p></p><p>会生成模 <span class="math inline">\(n\)</span> 的所有互质剩余类（即整数 1 到 <span class="math inline">\(n-1\)</span> 与 <span class="math inline">\(n\)</span> 互质的整数）。</p>
<ol start="2">
<li>计算步骤</li>
</ol>
<ul>
<li><span class="math inline">\(n = 25\)</span></li>
<li>计算 <span class="math inline">\(\phi(25) = 25 \cdot (1 - 1/5) = 20\)</span></li>
<li>检查每个 <span class="math inline">\(g \in \)</span>，若：</li>
</ul>
<p></p><div class="math display">\[g^{20/p} \neq 1 \pmod{25} \quad \forall p \text{ 是 } 20 \text{ 的质因子}
\]</div><p></p><p>则 <span class="math inline">\(g\)</span> 是本原根。</p>
<ul>
<li>20 的质因子：2, 5。</li>
</ul>
<pre><code class="language-python">def euler_phi(n):
    """计算欧拉函数 φ(n)"""
    result = n
    p = 2
    temp = n
    while p * p &lt;= temp:
      if temp % p == 0:
            while temp % p == 0:
                temp //= p
            result -= result // p
      p += 1
    if temp &gt; 1:
      result -= result // temp
    return result

def prime_factors(n):
    """返回 n 的质因子集合"""
    i = 2
    factors = set()
    while i * i &lt;= n:
      if n % i == 0:
            factors.add(i)
            while n % i == 0:
                n //= i
      i += 1
    if n &gt; 1:
      factors.add(n)
    return factors

def is_primitive_root(g, n):
    """判断 g 是否为 n 的本原根"""
    if gcd(g, n) != 1:
      return False
    phi = euler_phi(n)
    for p in prime_factors(phi):
      if pow(g, phi // p, n) == 1:
            return False
    return True

def gcd(a, b):
    while b:
      a, b = b, a % b
    return a

# =====================
n = 25
roots = []
for g in range(1, n):
    if is_primitive_root(g, n):
      roots.append(g)

print(f"{n} 的所有本原根:",roots)

</code></pre>
<p><img src="https://img2024.cnblogs.com/blog/3426414/202603/3426414-20260331194056742-1906498396.png" alt="Snipaste_2026-03-31_19-08-47" loading="lazy"></p>
<p>题目：编程实现Diffie-Hellman密钥交换协议，假设共享素数p=19，它的一个本原元g =3，A选秘密的随机数x=5，B选秘密的随机数y=7，输出A和B共享的密钥。</p>
<ul>
<li>素数：p=19</li>
<li>本原元：g=3</li>
<li>A 的私钥：x=5</li>
<li>B 的私钥：y=7</li>
</ul>
<p>A计算并发送15</p>
<p></p><div class="math display">\[A = g^x \mod p = 3^5 \mod 19 = 15
\]</div><p></p><p>B计算并发送2</p>
<p></p><div class="math display">\[B = g^y\mod p = 3^7 \mod 19 =2
\]</div><p></p><p>计算共享密钥<br>
A计算</p>
<p></p><div class="math display">\[K = B^x \mod p = 2^5 \mod 19= 13
\]</div><p></p><p>B计算</p>
<p></p><div class="math display">\[K = A^y \mod p = 15^7 \mod 19= 13
\]</div><p></p><p>所以最终的共享密钥就是K=13</p>
<pre><code class="language-python"># 参数
p = 19
g = 3
x = 5# A的私钥
y = 7# B的私钥

# 快速幂
def mod_exp(base, exp, mod):
    result = 1
    base %= mod
    while exp &gt; 0:
      if exp &amp; 1:
            result = (result * base) % mod
      base = (base * base) % mod
      exp &gt;&gt;= 1
    return result

# A计算并发送
A = mod_exp(g, x, p)
print("A发送:", A)

# B计算并发送
B = mod_exp(g, y, p)
print("B发送:", B)

# 共享密钥
K_A = mod_exp(B, x, p)
K_B = mod_exp(A, y, p)

print("A计算的共享密钥:", K_A)
print("B计算的共享密钥:", K_B)


</code></pre>
<p><img src="https://img2024.cnblogs.com/blog/3426414/202603/3426414-20260331194000421-838848507.png" alt="Snipaste_2026-03-31_19-12-36" loading="lazy"></p><br><br>
来源：https://www.cnblogs.com/red1giant-star/p/19803538
頁: [1]
查看完整版本: 密码学系列之流密码&RSA&ECC等