# rsa-otp

a guest
Mar 18th, 2020
667
0
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
9.     r.sendline(str(m))
12.     return len(out)
13. key = RSA.construct((n,e))
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)