Advertisement
Guest User

rsa-otp

a guest
Mar 18th, 2020
418
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. from Crypto.Util.number import bytes_to_long, long_to_bytes, isPrime
  2. from Crypto.PublicKey import RSA
  3. from pwn import *
  4. r = remote('crypto.2020.chall.actf.co',20600)
  5. n = 136018504103450744973226909842302068548152091075992057924542109508619184755376768234431340139221594830546350990111376831021784447802637892581966979028826938086172778174904402131356050027973054268478615792292786398076726225353285978936466029682788745325588134172850614459269636474769858467022326624710771957129
  6. e = 0x10001L
  7. def get(m, read=True):
  8.     if read: r.readuntil(": ")
  9.     r.sendline(str(m))
  10.     r.readline()
  11.     out = r.readline(keepends=False)
  12.     return len(out)
  13. key = RSA.construct((n,e))
  14. r.readline()
  15. f = int(r.readline(keepends=False))
  16. baseline = get(f, read=False)
  17. upper = pow(2,baseline)
  18. lower = pow(2,baseline-1)
  19. dd = upper-lower
  20. # part 1: get close enough
  21. mid = (upper+lower)>>1
  22. for num in range(baseline+1,n.bit_length()):
  23.     x = pow(2,num)//mid
  24.     test = (f*key.encrypt(x,0)[0])%n
  25.     res = get(test)
  26.     upper = min(upper,(pow(2,res)-1)//x)
  27.     lower = max(lower,pow(2,res-1)//x)
  28.     if upper-lower < dd:
  29.         dd = upper-lower
  30.         mid = (upper+lower)>>1
  31.     if dd <= 1:
  32.         # binary search is hard, add a tolerance
  33.         break
  34. # part 2: refine
  35. i = 5*pow(10,26) # suitably large number
  36. shift = n*i
  37. for num in range(n.bit_length()):
  38.     x = (pow(2,num)+shift)//mid
  39.     test = (f*key.encrypt(x,0)[0])%n
  40.     res = get(test)
  41.     if res==n.bit_length():
  42.         # we didn't wrap around
  43.         upper = min(upper,(shift-1)//x)
  44.         lower = max(lower,(pow(2,res-1)+shift-n)//x)
  45.     else:
  46.         upper = min(upper,(shift+pow(2,res)-1)//x)
  47.         lower = max(lower,(pow(2,res-1)+shift)//x)
  48.     if upper-lower < dd:
  49.         dd = upper-lower
  50.         mid = (upper+lower)>>1
  51.     if dd <= 1:
  52.         break
  53. print long_to_bytes(upper)
  54. print long_to_bytes(mid)
  55. print long_to_bytes(lower)
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement