基于多项式的RSA

jiangmingzi

船山信安 2024-03-01 00:01 湖南

前言

周末做了0CTF的babyrsa，其中在对于多项式的欧拉函数计算时遇到一些阻碍，记录一下解决过程。
(由于先知这里不支持数学公式，所以带公式的我都进行了截图，观赏性会受影响，抱歉。)

算法分析

代码很容易看懂

#!/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加解密原理

[color=rgba(0, 0, 0, 0.9)]

多项式RSA推倒

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

[color=rgba(0, 0, 0, 0.9)]

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

解题踩坑

利用sage语言来解题。

先对密文进行还原

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

得到明文的整数形式。

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

[color=rgba(0, 0, 0, 0.9)]

计算phi，以及d。

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

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

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

继而求出了d。

解密

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)互素，因此

[color=rgba(0, 0, 0, 0.9)]

获得flag

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

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，转为字符串

[color=rgba(0, 0, 0, 0.9)]

总结

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

[color=rgba(0, 0, 0, 0.9)]来源：https://xz.aliyun.com/ 感谢【altman】