# how does a time-memory trade off attack work?

I'm a student who learning cryptography, refer to this book "Applied Cryptanalysis - Breaking Ciphers in the Real World" (page 133). It helped me know about time-memory trade off. Then I had a homework CTF things which must use time trade off attack to deal with it. I gave up from first start because I don't know where should I start. This is the answer exercise!

import base36

table = {}
S = 0

print '[-] Generating table...'

for i in range(0, 2**33, 2**20): # sufficient bounds
table[pow(g, i, p)] = i

print '[-] Performing look-up in table...'

for i in range(0, 2**18):
B = (B * g) % p
if B in table:
print  ' >> B = g ^', table[B] - i
S = pow(A, table[B] - i, p)
break

print '[+] Key found:\n\n', base36.dumps(S), '\n'


Could anyone help me understand time-memory trade off? Maybe with an example building upon my homework

• What are you trying to attack? (ECC? DLog? PW-Hashes? Symmetric Keys?) TMTOs are known in a variety of settings. – SEJPM Nov 9 '16 at 23:42
• @SEJPM I'm trying to solve a CTF challenge. It's kind of RSA ( Asymmetric Keys ) – Mr2uang Nov 10 '16 at 6:48