pell方程与群的笔记

发表于 更新于 本文字数： 4.3k 阅读时长 ≈ 4 分钟
有关pell方程与群的简要笔记

Pell 方程与群

Pell 方程的解组成的群

Pell 方程是指形如 \[ x^2-Dy^2=1 \] 的二元二次方程，其中 \(D\) 为正整数。

对于模 \(n\) 的 Pell 方程，我们有 \[ x^2-Dy^2\equiv 1\pmod{n} \] 在这个群上，根据 Pell 方程的性质，有元素加法 \[ (x_3,y_3)=(x_1,y_1)\oplus (x_2,y_2)=(x_1x_2+Dy_1y_2,x_1y_2+x_2y_1) \] 有数乘 \[ e\otimes (x,y)=\overbrace{(x,y)\oplus (x,y)\oplus\cdots\oplus(x,y)}^{\text {e }} \] 显然，其是一个阶数为 \(p-1\) 加法循环群 \(C_p\)。

我们可以对这个循环群做一个同构映射 \(\psi:C_p\to F_p^*\)，定义如下 \[ \psi:(1,0)\to1\\ \psi:(x,y)\to x-ay\pmod{p} \] 其中，\((x,y)\in C_p\)，\(a^2\equiv D\pmod{p}\)。

\(\psi^{-1}:F_p^*\to C_p\) 定义如下 \[ \psi^{-1}:1\to (1,0)\\ \psi^{-1}:u\to (\frac{u+u^{-1}}{2},\frac{u^{-1}-u}{2a})\pmod{p} \] 由于其循环群性质，一定存在 \(k\equiv 1\pmod{p-1}\) 满足 \[ k\otimes (x,y)\equiv (x,y)\pmod{p} \] 如果说 \(n=pq\)，其中 \(p,q\) 为大素数，那么我们同样可以定义同构映射 \(\psi:C_n\to Z_n^*\)，有 \[ \psi:(1,0)\to1\\ \psi:(x,y)\to x-ay\pmod{n} \] 其中，\((x,y)\in C_n\)，\(a^2\equiv D\pmod{n}\)。

\(\psi^{-1}:Z_n^*\to C_n\) 定义如下 \[ \psi^{-1}:1\to (1,0)\\ \psi^{-1}:u\to (\frac{u+u^{-1}}{2},\frac{u^{-1}-u}{2a})\pmod{n} \] 在这之上，我们可以将数乘改写为幂乘，即 \[ i\otimes (x,y)\equiv (x-ay)^i\pmod{n} \] 同时，该循环群性质一定存在 \(k\equiv 1\pmod{\mathrm{lcm}(p-1,q-1)}\) 有 \[ (x,y)\equiv k\otimes(x,y)\pmod{n} \]

Pell 方程群与 RSA

密钥生成

如 RSA 一样，接收者需要选择大素数 \(p,q\)，令 \(n=pq\) 且 \(N=\mathrm{lcm}(p-1,q-1)\)。

同时接收者选取一个整数 \(e\) 满足 \(\gcd(e,N)=1\)，那么解密密钥就是 \(d=e^{-1}\pmod{N}\)。

那么公钥对为 \((e,n)\)，私钥是 \((p,q,d)\)。

传输方案一

加密

假设发送者想要传输的信息是 \(M_y\in Z_n^*\)，那么

  1. 计算 \(Z_1\equiv M_xM_y\pmod{n},Y=M_y\)，其中 \(M_x\) 随机选取。
  2. 在环 \(Z_n\) 上解方程 \(X-aY\equiv Z_1,X+aY=Z_1^{-1}\)。
  3. 计算 \(X\equiv \frac{Z_1+Z_1^{-1}}{2}\pmod{n},Y\equiv \frac{Z_1^{-1}-X}{Y}\pmod{n},D\equiv a^2\pmod{n}\)，那么 \((X,Y)\) 是佩尔方程 \(x^2-Dy^2\equiv 1\pmod{n}\) 的解。
  4. 计算 \((C_x,C_y)\equiv e\otimes (X,Y)\)。
  5. 发送 \((C_x,C_y,a)\) 给接收者。

解密

  1. 计算 \(C\equiv C_x-aC_y\pmod{n}\)
  2. 计算 \(M\equiv C^d\pmod{n}\)
  3. 计算 \(X\equiv \frac{M^{-1}+M}{2}\pmod{n},Y\equiv\frac{M^{-1}-M}{2a}\pmod{n}\)，显然 \(Z_1\equiv X,Y\equiv M_y\)
  4. 计算 \(M_x\equiv \frac{M}{Y}\pmod{n},M_y=Y\)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
from Crypto.Util.number import getPrime, bytes_to_long, inverse
import random

def pell_addition(p1, p2, n):
    x1, y1 = p1
    x2, y2 = p2
    return (x1 * x2 + D * y1 * y2) % n, (x1 * y2 + x2 * y1) % n

def pell_nummul(k, p, n):
    ret = p
    for _ in range(1, k):
        ret = pell_addition(ret, p, n)
    return ret

flag = b"flag{fake_flag}"
p = getPrime(256)
q = getPrime(256)
n = p * q
N = (p - 1) * (q - 1)
e = 65537
Mx = random.getrandbits(30 * 8)
My = bytes_to_long(flag)
Z1 = (Mx * My) % n
inv_Z1 = inverse(Z1, n)
inv_2 = inverse(2, n)
X = ((Z1 + inv_Z1) * inv_2) % n
Y = My
inv_Y = inverse(Y, n)
a = ((inv_Z1 - X) * inv_Y) % n
D = (a * a) % n

C = pell_nummul(e, (X, Y), n)
Cx, Cy = C
assert (Cx ** 2 - a ** 2 * Cy ** 2) % n == 1

print(f"{n = }")
print(f"{e = }")
print(f"{a = }")
print(f"{C = }")
"""
n = 10875869887787663804047839718193475543686118884019867572490803738648470308993079737759024578860813280711311716156127433305656013081574096984215062308086369
e = 65537
a = 10116438763770833335071963736482633275409537527635919273281738401076055253869316673041392938506765451934508925012357512109305204520982892722901613311800701
C = (4849960393113794464754080440760696916372299516798584397604977732217190475324711280614363849676614028060514423502894807465940532815099018702845064455373256, 2090931220172552969273275305442140295254277142601056005437730699641113025524595059533700684844894262935856020588590490821984640023923039365658842315589801)
"""

需要私钥 \(p,q\) 才可解密

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
p = 110074976061845580741863727679250881593298868143338959238797850091713336013909
q = 98804199436546420052453170362402913799134300214316056984844454343092057022941
n = 10875869887787663804047839718193475543686118884019867572490803738648470308993079737759024578860813280711311716156127433305656013081574096984215062308086369
N = (p - 1) * (q - 1)
e = 65537
a = 10116438763770833335071963736482633275409537527635919273281738401076055253869316673041392938506765451934508925012357512109305204520982892722901613311800701
Cxy = (4849960393113794464754080440760696916372299516798584397604977732217190475324711280614363849676614028060514423502894807465940532815099018702845064455373256, 2090931220172552969273275305442140295254277142601056005437730699641113025524595059533700684844894262935856020588590490821984640023923039365658842315589801)
Cx, Cy = Cxy
assert (Cx ** 2 - a ** 2 * Cy ** 2) % n == 1

D = (a * a) % n
C = (Cx - a * Cy) % n
d = inverse(e, N)
M = pow(C, d, n)
inv_M = inverse(M, n)
inv_2 = inverse(2, n)
inv_a = inverse(a, n)
X = (inv_M + M) * inv_2 % n
Y = (inv_M - M) * inv_2 * inv_a % n
My = Y
Mx = M * inverse(Y, n) % n
print(Mx, My)