2021强网杯 ezmath writeup

前言

题目ida查看后发现是浮点数的运算,涉及到精度的问题,本来想的是爆破每一位,但是发现条件由于精度损失的问题不可能相等,且数据越来越大,直到程序inf。后来听说是math有关的知识,看了别人的wp,发现竟是一大堆的数学公式的运算:积分,泰勒公式,辛普森公式。下面就分析一下题目功能和思路。

题目功能

题目逻辑是内置了一个长度为19的数组,输入的数据经过函数sub_13F3运算后,如果相等则输出correct!

  __isoc99_scanf("%39s", s);
  if ( strlen(s) == 38 )
  {
    for ( i = 0; i <= 37; i += 2 )
    {
      if ( dbl_4020[i / 2] != sub_13F3(*(unsigned __int16 *)&s[i]) )
        goto LABEL_2;
    }
    puts("correct");
    result = 0LL;
  }

sub_13F3函数,功能是从8225到输入数据的大小循环迭代v3,如下:

double __fastcall sub_13F3(int a1)
{
  int i; // [rsp+8h] [rbp-Ch]
  double v3; // [rsp+Ch] [rbp-8h]

  v3 = qword_2010;// 0x3f3fa5e61d8cedfd  0.00048291080524950886
  for ( i = 0x2021; i < a1; ++i )
    v3 = 2.718281828459045 - (double)i * v3;    
  return v3;
}

尝试

经过调试,得到了qword_2010的值0.00048291080524950886,然后按照程序的逻辑仿写了代码,对每个字符进行爆破,但是结果发现,得到的数据一正一负且越来越大最后越界inf。发现爆破不太行,陷入了僵局。到底哪里出了问题?后来发现2.718281828459045 是自然数e,根据题目名字ezmath猜测是和math有关,函数里面是关于v3的递推,发现类似于 I n = e − n ∗ I n − 1 I_n = e-n*I_{n-1} In​=e−n∗In−1​,这就需要数学辨识力了实际上它是积分: ∫ 0 1 x n e x d x ≈ e / n \int_{0}^{1}x^ne^x\text{d}x \approx e/n ∫01​xnexdx≈e/n,下面分析一下如何得到

分析数学算法

∫ 0 1 x n e x d x ≈ e / n \int_{0}^{1}x^ne^x\text{d}x \approx e/n ∫01​xnexdx≈e/n,时间上是个积分运算,涉及到凑微分,泰勒展开式、极限的运算。
lim ⁡ n → ∞ n ∫ 0 1 x n e x d x ① = lim ⁡ n → ∞ n ∫ 0 1 x n ∑ i = 0 ∞ x i i ! d x ② = lim ⁡ n → ∞ n ∫ 0 1 ∑ i = 0 ∞ x i + n i ! d x = lim ⁡ n → ∞ n ∑ i = 0 ∞ ∫ 0 1 x i + n d x i ! ③ = lim ⁡ n → ∞ n ∑ i = 0 ∞ 1 ( i + n + 1 ) i ! = lim ⁡ n → ∞ ∑ i = 0 ∞ 1 ( i + 1 n + 1 ) i ! = ∑ i = 0 ∞ 1 i ! = e \lim_{n\rightarrow \infty}n\int_0^1x^ne^xdx\\①=\lim_{n\rightarrow \infty}n\int_0^1x^n\sum_{i=0}^{\infty}\frac{x^i}{i!}dx\\②=\lim_{n\rightarrow \infty}n\int_0^1\sum_{i=0}^{\infty}\frac{x^{i+n}}{i!}dx=\lim_{n\rightarrow \infty}n\sum_{i=0}^{\infty}\frac{\int_0^1x^{i+n}dx}{i!}\\ ③ =\lim_{n\rightarrow \infty}n\sum_{i=0}^{\infty}\frac{1}{(i+n+1)i!}=\lim_{n\rightarrow \infty}\sum_{i=0}^{\infty}\frac{1}{(\frac{i+1}{n}+1)i!}\\=\sum_{i=0}^{\infty}\frac{1}{i!}=e limn→∞​n∫01​xnexdx①=limn→∞​n∫01​xn∑i=0∞​i!xi​dx②=limn→∞​n∫01​∑i=0∞​i!xi+n​dx=limn→∞​n∑i=0∞​i!∫01​xi+ndx​③=limn→∞​n∑i=0∞​(i+n+1)i!1​=limn→∞​∑i=0∞​(ni+1​+1)i!1​=∑i=0∞​i!1​=e
到①式 lim ⁡ n → ∞ ∫ 0 1 e x d x = lim ⁡ n → ∞ ∫ 0 1 ∑ i = 0 ∞ x i i ! d x \lim_{n\rightarrow \infty}\int_0^1e^xdx = \lim_{n\rightarrow \infty}\int_0^1\sum_{i=0}^{\infty}\frac{x^i}{i!}dx limn→∞​∫01​exdx=limn→∞​∫01​∑i=0∞​i!xi​dx为 e x e^x ex的泰勒展开
到②式为化简,求和符号提出去
到③式是对 ∫ 0 1 x i + n d x = 1 i + n + 1 ∗ x i + n + 1 ∣ 0 1 = 1 i + n + 1 \int_0^1x^{i+n}dx = \frac{1}{i+n+1}*x^{i+n+1}|_0^1 = \frac{1}{i+n+1} ∫01​xi+ndx=i+n+11​∗xi+n+1∣01​=i+n+11​的积分
最后得到了 ∑ i = 0 ∞ 1 i ! = e \sum_{i=0}^{\infty}\frac{1}{i!}=e ∑i=0∞​i!1​=e
至此可以得到 ∫ 0 1 x n e x d x = x n e x ∣ 0 1 − ∫ 0 1 e x d x n = e − n ∗ ∫ 0 1 x n − 1 e x d x ≈ e / n \int_{0}^{1}x^ne^x\text{d}x = x^ne^x|^1_0-\int_{0}^{1}e^x\text{d}x^n = e-n*\int_{0}^{1}x^{n-1}e^x\text{d}x\approx e/n ∫01​xnexdx=xnex∣01​−∫01​exdxn=e−n∗∫01​xn−1exdx≈e/n
所以要求n,就可以用 e ∫ 0 1 x n e x d x \frac{e}{\int_{0}^{1}x^ne^x\text{d}x} ∫01​xnexdxe​,其中 ∫ 0 1 x n e x d x \int_{0}^{1}x^ne^x\text{d}x ∫01​xnexdx为题目中给的数组数据。这里有精度的问题,所以要适当调整。

exp

import math
import codecs
res = [0.00009794904266317233, 0.00010270456917442, 0.00009194256152777895,
0.0001090322021913372, 0.0001112636336217534, 0.0001007442677411854,
0.0001112636336217534, 0.0001047063607908828, 0.0001112818534005219,
 0.0001046861985862495, 0.0001112818534005219, 0.000108992856167966,
0.0001112636336217534, 0.0001090234561758122, 0.0001113183108652088,
0.0001006882924839248, 0.0001112590796092291, 0.0001089841164633298,
0.00008468431512187874]
flag = b''
for i in res:
 flag += codecs.decode(hex(int(math.e/i)-1)[2:],'hex')[::-1]
print flag
print len(flag) 

总结

题目让我了解了数学知识在程序中的应用,加深了数学从理论到时间的认识,一切源于数学,我个菜鸡该好好补补数学知识了!!

参考

https://blog.csdn.net/weixin_43363675/article/details/118078787
https://blog.csdn.net/SCP000111/article/details/118033127
https://cdcq.github.io/2021/06/15/20210615a/

上一篇:bugku-writeup-MISC-白哥的鸽子


下一篇:BUUCTF笔记之Web系列部分WriteUp(二)