defget_n(): nset = [] c2 = server_encode(2) c4 = server_encode(4) c8 = server_encode(8) nset.append(c2 * c2 - c4) nset.append(c2 * c2 * c2 - c8) c3 = server_encode(3) c9 = server_encode(9) c27 = server_encode(27) nset.append(c3 * c3 - c9) nset.append(c3 * c3 * c3 - c27) c5 = server_encode(5) c25 = server_encode(25) c125 = server_encode(125) nset.append(c5 * c5 - c25) nset.append(c5 * c5 * c5 - c125) n = nset[0] for x in nset: n = gmpy2.gcd(x, n) while n % 2 == 0: n /= 2 while n % 3 == 0: n /= 3 while n % 5 == 0: n /= 5 print'n =', n return n
选择密文攻击
适用情况:
可以构造任意密文并获得对应明文。
通过选择密文攻击获得特定的明文。
原理
假设服务器创建了密文 C=Memodn,并且把 c 发送给用户,用户可以发送任意密文服务器返回解密后的明文。可以通过下面方法求出 M:
选择任意的 X 与 n 互素。
计算 Y=CXemodn。
由于可以进行选择密文攻击,那么可以求得 Y 对应的解密结果 Z=Yd。
则 Z=Yd=(CXe)d=CdX=MXmodn。由于 X 与 n 互素,很容易求得相应的逆元,进而可以得到 M。
代码
1 2 3 4 5 6 7 8 9 10 11 12
from Crypto.Util.number import *
defget_M(): X = getPrime(5) Y = (c * (X ** e)) % n Z = server_decode(Y) i = 0 whileTrue: M = (n * i + Z) / X if'flag'in long_to_bytes(M): print long_to_bytes(M) break
defget_flag(): k = n.bit_length() decimal.getcontext().prec = k L = decimal.Decimal(0) R = decimal.Decimal(int(n)) for i in range(k): c = (c * pow(2, e, n)) % n recv = server_decode(c) if recv == 1: L = (L + R) / 2 else: R = (L + R) / 2 print long_to_bytes(int((R)))
from Crypto.Util.number import * from fractions import Fraction
defget_flag(): map = {} for i in range(0, 256): map[-n * i % 256] = i
cipher256 = server_encode(256) backup = c
L = Fraction(0, 1) R = Fraction(1, 1) for i in range(128): c = c * cipher256 % n b = server_decode(c) k = map[b] L, R = L + Fraction(k, 256**(i+1)), L + Fraction(k+1, 256**(i+1)) m = int(L * n) print long_to_bytes(m - m % 256 + server_decode(backup))