**Tags:** cryptography small-d wienersattack rsa

Rating:

Knowing that Dachshund is the German word for Wiener dog is a start. If you don't know German, then maybe the picture in the hint will help. Doing a little googling returns several hits for Wiener attack, and I used the Wiki-page (https://en.wikipedia.org/wiki/Wiener%27s_attack) for solving this CTF. There are some libraries that can be downloaded to perform a Wiener attack, but I like math, so I decided to code the attack in Python.

My biggest challenge was performing calculations with really big numbers, but I found the library "decimal" that can handle this. Once the private key d is found the message must be decrypted by raising the encrypted message to the power of d and performing modulus N. This really quickly becomes a massive number, that cannot be handled with (c_m^d) mod(N). However, I found a Python function pow(), that can handle power of large numbers.

My strategy for solving the problem was:

1) Perform one step of Continued Fraction Expansion of e/N which return a guess for d (the public key) and k.

2) Check if d is an odd number (if failed return to 1))

3) Calculate phi(N) = (ed-1)/k and check if this i an integer (if failed return to 1))

4) Try to solve the squared equation x² - (N-phi(N)+1)x + N and check if the two solutions for x are integers. (if failed return to 1))

5) When the equation in 4) returns a valid solution, I know, that I have found the right d (public key) and the encrypted message c_m can be decrypted by c_m^d mod(N).

6) Change the encrypted message from decimal to hexadecimal to text

```

import math

import decimal

D = decimal.Decimal

e = D(1657805339429688812053143505041070479446292128411607570494243421760101704137301539086568061711572914192286708818311951491809958763731922974159879528048217191911809949318252855964312082817709188019888296969176903157632800355049328541044248401990090737592983323338514234850949188504162168586132574428719609765)

N = D(69946612833823474474567341713689184972332063124960313284323963391904325835001536564089987739039075606813821953828737052699889176170852295666471788226146362077823483434246648477714474043193142173165562623552641464965982360870678134642112700029973671619733747905675567176551945786098617460155171179688323257151)

c_m = 29311486423187500425330376488764998659536706623004545634194705326716672050374070671117765893362655752130354154669903618594619025949342070080877875120252533550235579687317810364639488447285875968129203680724128585150906708070170492927818867527457559253200831533156258084726643270961969276171618824314271908005

#Continued fraction expansion of e/N (see https://en.wikipedia.org/wiki/Continued_fraction):

n_fe = e #nominator

d_fe = N #denominator

fraction_list = []

def expand_fraction_list(n_fe, d_fe):

with decimal.localcontext() as ctx:

ctx.prec = 350

cap = math.floor(n_fe/d_fe)

rest = n_fe%d_fe

fraction_list.append(cap)

n_fe = d_fe

d_fe = rest

return (n_fe, d_fe)

def cfe(a_list, j): #Calculate fraction from fraction_list

n_next = 0

d_next = 1

while j >= 0:

d = d_next

k = a_list[j]*d_next+n_next

n_next = d

d_next = k

j = j-1

return k,d #returns guess for k and d. d is the private key.

#Perform Wieners Attack (see https://en.wikipedia.org/wiki/Wiener%27s_attack)

n_fe, d_fe = expand_fraction_list(n_fe, d_fe) #creates 0th element in fraction list

for i in range(1,1000):

n_fe, d_fe = expand_fraction_list(n_fe, d_fe) #adds new element to fraction list

k,d = cfe(fraction_list, i) #calculates the fraction for the i'th fraction expansion

with decimal.localcontext() as ctx:

ctx.prec = 10000

PhiN = D((e*d-1)/k)

if PhiN%1 == 0 and d%2 == 1: #Checks if phi(N) is a natural number and if d is odd

with decimal.localcontext() as ctx: #try to solve square equation x2 + bx + c == 0

ctx.prec = 1000

b = -(N-PhiN+1)

c = N

sqr2 = b**2-4*c

if sqr2 > 0: #checks if squareroot therm is larger than 0

sqr = D(sqr2.sqrt())

if sqr%1 == 0 and ((-b+sqr)/2)%1 == 0 and ((-b-sqr)/2)%1 == 0: #checks if squareroot-therm and the two solutions are all natural numbers

break

print("d = ", d)

N = int(N)

m_c = pow(c_m, d, N)

print("Decrypted message: ", m_c)

from Crypto.Util.number import long_to_bytes

text = long_to_bytes(m_c)

print("Plain text: ", text)

```

Running the code returned:

d = 17722556059078921171403312767566106169092004506516287359630755415494493912749

Decrypted message: 198614235373674103788888306985643587194108045477674049828439422174745801853

Plain text: b'picoCTF{proving_wiener_3878674}'

So the solution is picoCTF{proving_wiener_3878674}