这是一道数论高配题。整数要用大整数，方程要用模方程，模方程要用二次模方程，二次模方程要用二次模合数方程，求逆要选离散对数。感谢作者大神，学习了。

该题选用了mbedtls大数库，可以对应着源代码查看分析。

作者一如既往的对话框程序，我们需要关心两个程序。sub_403B00 输入字符处理函数和sub_404270校验函数。校验函数做了抗F5小处理。将此处Nop掉即可F5分析。

.text:00404B1E                 pop     ebp

输入字符处理

简单查看了一下。合法字符串使用“XXXX”进行分割，分为前后两个部分，并转化为string类型。

该函数要满足3个条件，才能返回正确结果。下面分别分析这三个条件。

大整数初始化

第一个条件是个限制条件，4*b < 2^0xff – 0x13。

这里我们另r=b-a，循环6次的过程如下

sum0 =  r^0/N                 *3 =3

sum1 =  r^1*0/N              +sum0/N = 3

sum2 =  r^2*1/N              +sum1/N = (r^2+3)/N

sum3 =  r^3*0/N              +sum2/N = (r^2+3)/N

sum4 =  r^4*0x40/N +sum3/N = 0X40r^4/N + (r^2+3)/N

sum5 =  r^5*0/N +sum4

最后得到的方程

(64r^4/N + (r^2 +3)/N)/n = a

这里我们另x=r^2，这里往回逆的时候要逆两次。化简后可得一个二次模方程。

64x^2 + x +3-a = 0(mod N)

从方程可知，求出a即可反推x，r最后求得b。那么我们继续分析，看如何求a值。

代码几个关键步骤说明：

1、 将keyBefore（输入字符串得前半部分）最后一位+0x0A；

2、 将keyBfore内容转换为0x19进制数，记作E；

3、 米勒罗宾素性测试，确保E为素数；

4、 E与(N-1)最大公约数为1

5、 检测计算

          D = E^-1 mod (N-1)

         X = A^D mod N

         A = X^E mode N

N=0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED

这里我们已知A和X得四组数据

求D，求离散对数。利用作者dlp工具可以跑出D。

这样我们可以一路反推D->E->keyBefore->a

将a带回二次模方程，这里简单提一下方程化简过程

64r^4 + r^2 + 3-0x4B435446524541445955 = 0 mod N

64x^2 + x + 3-0x4B435446524541445955 = 0 mod N

转换为一般模方程

x^2 = A mode M      A是奇数非素数   M是个合数  GCD（A,M）==1

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课