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}