这题表面上是一个裸rsa题，给了n，e和c，但实际上n不能分解
但是题目给了个服务器，允许你输入密文，然后告诉你对应的明文的奇偶性
这题我没想出来，看题解提示了两次才做出来，就直接说解法了：
知道m的奇偶性是没什么卵用的，但是如果知道2*m的奇偶性就很有用了
由于m<n，所以如果2*m<n，那么2*m一定是偶数，但是如果2*m>=n，注意服务器检测的实际上是2*m%n=2*m-n，所以会判断为奇数
那么如果2*m<n，就有m<=n/2，如果2*m>=n，有m>=n/2
这样就可以二分了
具体怎么二分呢，其实很简单
最开始l=0，r=n，每次让c*=2^e（让m*=2），然后判断c的奇偶性
如果c是偶数，就让r=mid，否则让l=mid
最后不用考虑选l还是r作为答案，因为l和r也就差1，眼睛可以直接看出来
正确性可以这样来考虑：
第一次判断的时候，根据奇偶性可以划分到n/2的两边
第二次由于m2=m*4，如果之前划到左边就不说了，如果划到右边，那么可以把m看成n/2+m'
这样就有4*(n/2+m')=2*n+4*m'，这样就可以把m'划到n/4的左边或者右边
（注意，上一次的奇偶性对下一次的判断是没有关系的，因为m乘2了，所以上次的n/2对下次没有影响，这里我想错了，看了题解发现）
代码：
1 from pwn import * 2 from Crypto.Util.number import * 3 4 # sh = remote('220.249.52.134', 35781) 5 6 e = 0x10001 7 n = 0x0b7...6db 8 c = 0x4f3...be0 9 10 left, right = 0, n 11 last = 0 12 while left + 1 < right: 13 print(left, right) 14 mid = (left + right) >> 1 15 c = c * pow(2, e, n) % n 16 sh = remote('220.249.52.134', 48658) 17 for i in range(4): 18 s = sh.recvline() 19 20 sh.sendline(str(hex(c))) 21 s = sh.recvline() 22 if s[0] == ord('e'): 23 right = mid 24 else: 25 left = mid 26 27 ans = left 28 s = '' 29 while ans > 0: 30 s = s + chr(ans % 256) 31 ans = ans // 256 32 33 print(s) 34 35 ''' 36 for i in range(4): 37 s = sh.recvline() 38 print(s) 39 40 sh.sendline(str(c)) 41 s = sh.recvline() 42 print(s) 43 '''