原理

多项式RSA适用于整数RSA原理。

多项式所在的域叫做有限域。整数域上的素数p和q，在有限域上有与之对应的是不可约多项式g§和g(q)，即不能进行因式分解的多项式。

g(n)=g§*g(q)，再计算g(n)的欧拉函数φ，选取整数e作为公钥，e须与φ互素，才能保证有乘法逆元d，也就是私钥。

加密过程

g(m)e≡g(c) mod g(n)g(m)^{e}\equiv g(c) \bmod g(n)

解密过程就是反过来，根据φ求出d即可解出，易证。

对于不可约多项式的φ，如何求？首先，欧拉函数是小于n的所有与n互素的数的个数。也就是这个多项式环的阶，即环中所有元素个数，对于一个系数模p，最高次为n-1的多项式来说，元素个数为p^n-1。

脚本

#sage1
#已知p=2,n,e,c
p=
P=PolynomialRing(Zmod(p),name='x')#建立多项式环
x=P.gen()#x为环的生成多项式
e=
n=
c=

#分解n
q1,q2=n.factor()
q1,q2=q1[0],q2[0]

#求φ
phi=(p^q1.degree()-1)*(p^q2.degree()-1)
assert gcd(e,phi)==1
d=inverse_mod(e,phi)
m=pow(c,d,n)

#去多项式系数
flag=bytes(m.coefficients())
print("Flag: ",flag.encode())

#sage2
#已知p=2,n,e,c
p=
P=PolynomialRing(GF(p),name='x')
x=P.gen()
e=
n=
R.<a>=GF(2^2049)#建立一个名为R，生成元为a的有限域，系数模2,2049位
c=[]#假设m分几部分加密成c的数组，c内为多项式

q1,q2=n.factor()
q1,q2=q1[0],q2[0]

phi=(p^q1.degree()-1,p^q2.degree()-1)
assert gcd(e,phi)==1
d=inverse_mod(e,phi)

ans=''
for cc in c:
    cc=P(R.fetch_int(cc))#此多项式在有限域R上获取其系数，再通过P根据系数生成多项式
    m=pow(cc,d,n)
    m=R(P(m)).integer_representation()#同样为获取其系数的函数
    print(m)
    ans+=chr(m)
print(ans)
#变量为y的模素数p下单变量多项式环
R.<y>=PolynomialRing(GF(p))

#环上一随机变量,degree为度数，最高次幂
R.random_element(degree=...)

#是否为可约多项式
PR.is_irreducible()

#R模N的多项式商环，即S=R mod N
S.<x>=R.quotient(N)

参考

RSA | Lazzaro (lazzzaro.github.io)