基于多项式的RSA体制

1
首发先知社区:https://xz.aliyun.com/t/4545

前言

周末做了0CTF的babyrsa,其中在对于多项式的欧拉函数计算时遇到一些阻碍,记录一下解决过程。

算法分析

代码很容易看懂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#!/usr/bin/env sage
# coding=utf-8

from pubkey import P, n, e
from secret import flag
from os import urandom

R.<a> = GF(2^2049)

def encrypt(m):
global n
assert len(m) <= 256
m_int = Integer(m.encode('hex'), 16)
m_poly = P(R.fetch_int(m_int))
c_poly = pow(m_poly, e, n)
c_int = R(c_poly).integer_representation()
c = format(c_int, '0256x').decode('hex')
return c

if __name__ == '__main__':
ptext = flag + os.urandom(256-len(flag))
ctext = encrypt(ptext)
with open('flag.enc', 'wb') as f:
f.write(ctext)

encrypt函数是一个标准的RSA加密过程。但是区别在于这里的明文与N都是多项式表达。

我们先回顾一下基于整数的RSA加解密原理。

整数RSA加解密原理

首先 选取素数p q。$n=p*q​$

然后求 φ(n),那么 $φ(n)=(p-1)*(q-1)​$

选取一个e与φ(n)互质。

之后就可以加密 $(m^e)\equiv c \ mod \ n​$ 得到密文c。

计算私钥d 满足 $e*d \equiv 1\ mod \ φ(n)​$

解密原理 :首先得到式子①
$$
c^d \equiv (m^e)^d \equiv m^{ed} \equiv m^{φ(n)+1}\ mod \ n \ \
$$
暂且仅考虑 $ gcd(n,m)=1$

由欧拉定理得 式子②
$$
m^{φ(n)}\equiv1 \ mod \ n \
m^{φ(n)+1}\equiv m \ mod \ n
$$
有①②得出
$$
(c^d)\equiv m \ mod \ n
$$

多项式RSA推导

在上面RSA原理的基础上将多项式的代入整数进行分析。

在有限域上选取两个不可约多项式 g(p) g(q) 。$g(n)=g(p)*g(q)​$

计算出 $g(n)$的欧拉函数 $φ(g(n))=phi$。

选取一个整数e作为公钥,e与phi是互素的。

那么对于明文g(m),加密过程 $g(m)^e \equiv g(c)\ mod \ g(n)$

计算私钥d 满足 ($ e*d \equiv 1\mod\ phi$)

接下来与上面的推导一样。
$$
g(c)^d \equiv (g(m)^e)^d \equiv g(m)^{ed} \equiv g(m)^{phi+1}\ mod \ g(n) \ \
$$
同样考虑 g(n)与g(m)互素。

欧拉定理对于多项式亦成立,得到:
$$
g(m)^{phi+1}\equiv g(m) \ mod \ n \
所以 (g(c)^d)\equiv g(m) \ mod \ g(n)
$$
那么显然RSA对于整数的体制可以适用于有限域上的多项式。

解题踩坑

利用sage语言来解题。

先对密文进行还原

1
2
3
4
file_object = open('./flag.enc','rb')
file_context = file_object.read()
x=int(file_context.encode('hex'),16)
print x

得到明文的整数形式。

对n进行分解得到两个不可约多项式p q

计算phi,以及d。

1
2
sage: phi=(p-1)*(q-1)
sage: d=inverse_mod(e,phi)

此时出现了报错,因为e是整数而phi为多项式,将phi转为整数

1
sage:phi_int=R(P(phi)).integer_representation()

继而求出了d。

解密

1
2
sage:flag=pow(c,d,n)
sage:flag_int=R(P(flag)).integer_representation()

接下来对flag_int转string发现乱码。

接下来陷入了自闭。

多次进行检查验证,算法本身是没有问题的,出问题可能就出在求d的过程中。

解决问题

求d需要e和phi。那么问题只能出在phi身上。

对于素数x,φ(x)=x-1。

但是对于不可约多项式p(x),经过简单验证φ(p(x))=x-1是不成立的。

那么是否$φ(x)=x-y $ (y为$GF(2^n)$的本源多项式) ,经过简单的举例验证他依旧是不成立的。

不可约多项式的欧拉函数怎么求呢。回到欧拉函数定义本身,欧拉函数是小于或等于n的正整数中与n互质的数的数目。

再看不可约多项式p(x),除了0,长度为n每一个多项式都与p(x)互素,因此,$φ(p(x))=2^n-1$。

那么对于此题的$φ(p) = 2^{821}-1 \ φ(q)=2^{1227}-1​$

正确的phi即为 $φ(p)*φ(q)​$

获得flag

得到了正确的phi再进行解密

1
2
3
4
5
sage: c_poly=P(R.fetch_int(c))
sage: phi_int=(2^1227-1)*(2^821-1)
sage: d=inverse_mod(e_int,phi_int)
sage: flag=pow(c_poly,d,n)
sage: flag_int=R(P(flag)).integer_representation()

得到flag_int,转为字符串

总结

总的来说基于整数和基于多项式的RSA体制大致相同,只是多项式在值的计算上例如欧拉函数,取模反等地方需要注意区别。