Anti-Fermat
authored by prt-yudai
I invented Anti-Fermat Key Generation for RSA cipher since I'm scared of the Fermat's Factorization Method.
from Crypto.Util.number import isPrime, getStrongPrime
from gmpy import next_prime
from secret import flag
# Anti-Fermat Key Generation
p = getStrongPrime(1024)
q = next_prime(p ^ ((1<<1024)-1))
n = p * q
e = 65537
# Encryption
m = int.from_bytes(flag, 'big')
assert m < n
c = pow(m, e, n)
print('n = {}'.format(hex(n)))
print('c = {}'.format(hex(c)))
$p,q$が互いに近いときに素因数分解できるフェルマー法がいやらしく、$q$の値を以下で生成しています。
q = next\_prime(p \oplus 2^{1024}-1)
解法
mask = (1 << 1024)-1とすると、maskは補数と考えることができます。つまり、上の式は
q = mask - p
と表せます。
さて、next_prime関数で増えた値を$t$とすると、qは以下で表されることになります。
q = (mask - p) + t
つまり、
p+q = p + (mask - p) + t = mask + t
となり、$p,q$がわからなくても$t$の値を探索することで、p+qが求まりそうです。
ここで、実験をしてみましょう。
from Crypto.Util.number import getStrongPrime
from gmpy2 import next_prime
avg = 0
for _ in range(100):
p = getStrongPrime(1024)
q = next_prime(p ^ (1 << 1024)-1)
t = q - (p ^ (1 << 1024)-1)
avg += t
print(avg//100)
$t$の値が取る平均を求めてみます。すると結果は641となりました。
つまり、$t$の値は明らかに総当り可能であることがわかります。
さて、$N = pq, s = p+q$とすると、
x^2 -sx + N = 0
となるような$x$の解を探せば良いことがわかります($(x-p)(x-q)=0$を展開すると上式になります。)
そして、整数値として出てくるためには、判別式$D = s^2 -4N$が$D=u^2$といったある数字$u$の平方数となっていれば良いでしょう。
以上から、$D=u^2$となるように、$t$の値を調整してあげ、割れた$p,q$が素数か判定することで探すことができるでしょう。
from gmpy2 import iroot
import sympy
from Crypto.Util.number import long_to_bytes
n = 0x1ffc7dc6b9667b0dcd00d6ae92fb34ed0f3d84285364c73fbf6a572c9081931be0b0610464152de7e0468ca7452c738611656f1f9217a944e64ca2b3a89d889ffc06e6503cfec3ccb491e9b6176ec468687bf4763c6591f89e750bf1e4f9d6855752c19de4289d1a7cea33b077bdcda3c84f6f3762dc9d96d2853f94cc688b3c9d8e67386a147524a2b23b1092f0be1aa286f2aa13aafba62604435acbaa79f4e53dea93ae8a22655287f4d2fa95269877991c57da6fdeeb3d46270cd69b6bfa537bfd14c926cf39b94d0f06228313d21ec6be2311f526e6515069dbb1b06fe3cf1f62c0962da2bc98fa4808c201e4efe7a252f9f823e710d6ad2fb974949751
c = 0x60160bfed79384048d0d46b807322e65c037fa90fac9fd08b512a3931b6dca2a745443a9b90de2fa47aaf8a250287e34563e6b1a6761dc0ccb99cb9d67ae1c9f49699651eafb71a74b097fc0def77cf287010f1e7bd614dccfb411cdccbb84c60830e515c05481769bd95e656d839337d430db66abcd3a869c6348616b78d06eb903f8abd121c851696bd4cb2a1a40a07eea17c4e33c6a1beafb79d881d595472ab6ce3c61d6d62c4ef6fa8903149435c844a3fab9286d212da72b2548f087e37105f4657d5a946afd12b1822ceb99c3b407bb40e21163c1466d116d67c16a2a3a79e5cc9d1f6a1054d6be6731e3cd19abbd9e9b23309f87bfe51a822410a62
mask = (1 << 1024)-1
def brute_force_t():
for t in range(10000):
s = mask + t
D = s**2 - 4*n
a, b = iroot(D, 2)
if b == True:
return s
x = sympy.Symbol('x')
s = brute_force_t()
p = sympy.solve(x**2 - s*x + n)
p = int(p[0])
q = n//p
e = 65537
d = pow(e, -1, (p-1)*(q-1))
m = pow(c, d, n)
print(long_to_bytes(m).decode())
Good job! Here is the flag:
+-----------------------------------------------------------+
| zer0pts{F3rm4t,y0ur_m3th0d_n0_l0ng3r_w0rks.y0u_4r3_f1r3d} |
+-----------------------------------------------------------+
flag:zer0pts{F3rm4t,y0ur_m3th0d_n0_l0ng3r_w0rks.y0u_4r3_f1r3d}