PicoCTF - Dachshund Attacks

Posted on | Post modified | In |

PicoCTF - Dachshund Attacks

tags: PicoCTF CTF Crypto

Background

How about if the private key is too small? Refer Extending Wiener’s Attack

Exploit - Small Private Key

  1. git clone https://github.com/pablocelayes/rsa-wiener-attack Put the exploit file in this repo.
  2. Whole Exploit 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    		 
     from pwn import *
 from Crypto.Util.number import long_to_bytes
 import ContinuedFractions, Arithmetic


 context.arch = 'amd64'
 r = remote("mercury.picoctf.net", 37455)

 def wiener_hack(e, n):
     # firstly git clone https://github.com/pablocelayes/rsa-wiener-attack.git !
     frac = ContinuedFractions.rational_to_contfrac(e, n)
     convergents = ContinuedFractions.convergents_from_contfrac(frac)
     for (k, d) in convergents:
         if k != 0 and (e * d - 1) % k == 0:
             phi = (e * d - 1) // k
             s = n - phi + 1
             discr = s * s - 4 * n
             if (discr >= 0):
                 t = Arithmetic.is_perfect_square(discr)
                 if t != -1 and (s + t) % 2 == 0:
                     print("Hacked!")
                     return d
     return False

 r.recvline()
 e = int(str(r.recvline().strip().decode()).split(" ")[-1])
 n = int(str(r.recvline().strip().decode()).split(" ")[-1])
 c = int(str(r.recvline().strip().decode()).split(" ")[-1])

 d = wiener_hack(e, n)
 print(long_to_bytes(pow(c, d, n)))

 r.interactive()

Reference

CTF_RSA解密学习指南(三) - 低解密指数攻击