• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • CTF – RootMe解题报告 [Programming : Arithmetic progression]

    渗透测试 EXP 39阅读 0评论

    挑战入口:Root-Me(https://www.root-me.org/en/Challenges/Programming/Arithmetic-progression-18)
      分类目录:Link to …(http://exp-blog.com/2019/01/02/pid-2597/8/)


    题目分析

    高中数学题。

    多刷新几次挑战页面可以得到一个规律,挑战给出了一条 固定格式递推公式

    U_{n+1} = ( A + U_n ) \quad op \quad ( n * B )

    同时给出初值 U_0 , 要求在 2秒内 求出当 n 为某个数时,U_n 的值。

    其中:

    • AB 是一个随机整数,每次刷新页面都会变化
    • op 是一个运算符,只会是 +
    • U_0 是随机整数,每次刷新页面都会变化
    • n 是随机正整数,每次刷新页面都会变化,且 n 值较大

    解题思路

    直观的做法是直接从 U_0 开始代入递推公式,一直循环计算,直到算出 U_n 为止。

    但是这是不可能的,因为题目所要求的 n 值都很大,大到基本不可能在 2秒内 通过递推公式推算 U_n 的结果。

    因此正确的做法是,根据递推公式求出通项公式,这是高中的 数列 知识。

    求通项公式

    求通项公式有很多种方法,这里使用 累加法, 求解过程如下:

    U_{n+1} = ( A + U_n ) \quad op \quad ( n * B ) 变形得到:

    U_{n+1} – U_n = A \quad op \quad B * n

    逐项作差,于是有:

    \small{ \begin{cases} U_n – U_{n-1} = A \quad op \quad B * ( n – 1 ) \\\ U_{n-1} – U_{n-2} = A \quad op \quad B * ( n – 2 ) \\\ U_{n-2} – U_{n-3} = A \quad op \quad B * ( n – 3 ) \\\ \text{…… } \\\ U_3 – U_2 = A \quad op \quad B * 2 \\\ U_2 – U_1 = A \quad op \quad B * 1 \\\ U_1 – U_0 = A \quad op \quad B * 0 \end{cases} }

    对等号的左右两边分别相加,有:

      ( U_n – U_{n-1} ) + ( U_{n-1} – U_{n-2} ) + …… + ( U_2 – U_1 ) + ( U_1 – U_0 )
       = A * n \quad op \quad B * [(n – 1) + (n – 2) + (n – 3) + … + 2 + 1 + 0]

    化简得:

    U_n – U_0 = A * n \quad op \quad B * \dfrac{(n-1)*n}{2}

    即通项公式为:

    U_n = A * n \quad op \quad B * \dfrac{(n-1)*n}{2} + U_0

    解题代码

    得到通项公式,就可以在给定任意 n 值的情况下,直接计算 U_n 的值了。

    即代码只需从挑战页面的 html 源码中实时抠取 ABopU_0n 的值,再代入通项公式计算 U_n 即可。

    详细代码如下:

    注:此代码是用 python 3.5.2 写的,运行前需确保已在浏览器登陆了 rootme 并打开过此挑战页面

    代码的调用结果如下,页面提示 Congratz 说明完成挑战:


    转载请注明:EXP 技术分享博客 » CTF – RootMe解题报告 [Programming : Arithmetic progression]

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址