基于多项式的RSA

wsw

船山信安 2024-03-01 00:01 湖南
前言
周末做了0CTF的babyrsa，其中在对于多项式的欧拉函数计算时遇到一些阻碍，记录一下解决过程。


算法分析
代码很容易看懂

1. #!/usr/bin/env sage
   
2. # coding=utf-8
   
3. 
   
4. from pubkey import P, n, e
   
5. from secret import flag
   
6. from os import urandom
   
7. 
   
8. R.<a> = GF(2^2049)
   
9. 
   
10. def encrypt(m):
    
11.     global n
    
12.     assert len(m) <= 256
    
13.     m_int = Integer(m.encode('hex'), 16)
    
14.     m_poly = P(R.fetch_int(m_int))
    
15.     c_poly = pow(m_poly, e, n)
    
16.     c_int = R(c_poly).integer_representation()
    
17.     c = format(c_int, '0256x').decode('hex')
    
18.     return c
    
19. 
    
20. if __name__ == '__main__':
    
21.     ptext = flag + os.urandom(256-len(flag))
    
22.     ctext = encrypt(ptext)
    
23.     with open('flag.enc', 'wb') as f:
    
24.         f.write(ctext)

复制代码

encrypt函数是一个标准的RSA加密过程。但是区别在于这里的明文与N都是多项式表达。
我们先回顾一下基于整数的RSA加解密原理。


整数RSA加解密原理


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

那么显然RSA对于整数的体制可以适用于有限域上的多项式。

解题踩坑
利用sage语言来解题。

先对密文进行还原

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

复制代码

得到明文的整数形式。

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

计算phi，以及d。

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

复制代码

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

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

复制代码

继而求出了d。

解密

1. sage:flag=pow(c,d,n)
   
2. 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)互素，因此


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

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

复制代码

得到flag_int，转为字符串

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