首先回顾整数的rsa：
那么，当n是多项式的时候呢？
有如下推导：
那么显然RSA对于整数的体制可以适用于有限域上的多项式。
解密步骤：对N进行多项式分解，得到多项式p和多项式q，求出phi( p(n) )，之后类似于整数rsa求出d后求出m。
注意: 有限域上的多项式求欧拉函数时，φ(p(x)) ！= x-1
回到欧拉函数定义本身，欧拉函数是小于或等于n的正整数中与n的数的数目。
欧拉函数phi(n)表示小于n的所有与n互质的数的个数，多项式的phi(P(y))则类似，表示不高于P(y)幂级的环内所有多项式中，与P(y)无公因式（非1）的其他多项式的个数。
这里补充一下 有限域GF（p）的知识：
- 有限域的元素个数是一个素数的幂p ** n，n为正整数，一般记为GF(p ** n)，我们最为关注的只有两种情况：n=1即GF(p)；p为2即GF(2 ** n)。
- GF(p)的空间是模p的完全剩余类Zp:{0,1,⋯,p−1}
因此这里，对于p(x)，φ(p(x)) = p ** n - 1 (这里p表示有限域的模数，n表示有限域多项式中的最高次幂数)
所以，φ(p(n)) = φ(p(x)) * φ(q(x)) = （p ** n1 - 1） * （q ** n2 - 1）
例题：[watevrCTF 2019]Swedish RSA
题目：
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
| flag = bytearray(raw_input())
flag = list(flag)
length = len(flag)
bits = 16
p = random_prime(2^bits-1, False, 2^(bits-1))
file_out = open("downloads/polynomial_rsa.txt", "w")
file_out.write("Prime: " + str(p) + "\n")
R.<y> = PolynomialRing(GF(p))
def gen_irreducable_poly(deg):
while True:
out = R.random_element(degree=deg)
if out.is_irreducible():
return out
P = gen_irreducable_poly(ZZ.random_element(length, 2*length))
Q = gen_irreducable_poly(ZZ.random_element(length, 2*length))
e = 65537
N = P*Q
file_out.write("Modulus: " + str(N) + "\n")
S.<x> = R.quotient(N)
m = S(flag)
c = m^e
file_out.write("Ciphertext: " + str(c))
file_out.close()
|
分析发现，给出了N和c，因此首先需要先分解N获取p和q，又因为p和q是通过gen_irreducable_poly函数返回的，该函数进行的就是不可约检验，因此p和q为不可约多项式。接下来就是常规rsa。
wp：（需要通过sage分解多项式）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
from sage.all import *
import gmpy2
P=43753
R.<y> = PolynomialRing(GF(P))
N=34036*y^177 + ...... //省略号表示y^176到1的多项式
S.<x> = R.quotient(N)
C=5209*x^176 + .....
p,q = N.factor()
p,q = p[0],q[0]
p = y^65 + ....
q = y^112 + .....
phi=(pow(P,65)-1)*(pow(P,112)-1)
e = 65537
d = gmpy2.invert(e,phi)
m = C^d
print("".join([chr(c) for c in m.list()]))
|
