Tags: capturetheflag.withgoogle.com
Rating: 2.7
```python
from Crypto.Util.number import *
n = 0xab802dca026b18251449baece42ba2162bf1f8f5dda60da5f8baef3e5dd49d155c1701a21c2bd5dfee142fd3a240f429878c8d4402f5c4c7f4bc630c74a4d263db3674669a18c9a7f5018c2f32cb4732acf448c95de86fcd6f312287cebff378125f12458932722ca2f1a891f319ec672da65ea03d0e74e7b601a04435598e2994423362ec605ef5968456970cb367f6b6e55f9d713d82f89aca0b633e7643ddb0ec263dc29f0946cfc28ccbf8e65c2da1b67b18a3fbc8cee3305a25841dfa31990f9aab219c85a2149e51dff2ab7e0989a50d988ca9ccdce34892eb27686fa985f96061620e6902e42bdd00d2768b14a9eb39b3feee51e80273d3d4255f6b19
e = 0x10001
c = 0x6a12d56e26e460f456102c83c68b5cf355b2e57d5b176b32658d07619ce8e542d927bbea12fb8f90d7a1922fe68077af0f3794bfd26e7d560031c7c9238198685ad9ef1ac1966da39936b33c7bb00bdb13bec27b23f87028e99fdea0fbee4df721fd487d491e9d3087e986a79106f9d6f5431522270200c5d545d19df446dee6baa3051be6332ad7e4e6f44260b1594ec8a588c0450bcc8f23abb0121bcabf7551fd0ec11cd61c55ea89ae5d9bcc91f46b39d84f808562a42bb87a8854373b234e71fe6688021672c271c22aad0887304f7dd2b5f77136271a571591c48f438e6f1c08ed65d0088da562e0d8ae2dadd1234e72a40141429f5746d2d41452d916
a = 0xe64a5f84e2762be5
chunk_size = 64
#def gen_prime(bits):
# s = random.getrandbits(chunk_size)
def gen_prime(s):
bits = 1024
while True:
s |= 0xc000000000000001
p = 0
for _ in range(bits // chunk_size):
p = (p << chunk_size) + s
s = a * s % 2**chunk_size
#if gmpy2.is_prime(p):
# return p
return p
m = 2**64
n1 = n%m
n2 = n//m%m
r = (n2-2*n1*inverse(a, m))%m
s12a = r*m+n1
print("s12a", s12a)
f = [11, 13, 109, 223, 1290533, 4608287, 167541865434116759]
mf = 1
for t in f:
mf *= t
assert mf==s12a
for b in range(2**(len(f)-1)):
s1a = 1
s2a = 1
for i in range(len(f)):
if b>>i&1:
s1a *= f[i]
else:
s2a *= f[i]
s1 = s1a*inverse(a, m)**15%m
s2 = s2a*inverse(a, m)**15%m
if ((s1&0xc000000000000001)==0xc000000000000001 and
(s2&0xc000000000000001)==0xc000000000000001):
p1 = gen_prime(s1)
p2 = gen_prime(s2)
if p1*p2==n:
print("s1", hex(s1))
print("s2", hex(s2))
d = inverse(e, (p1-1)*(p2-1))
p = pow(c, d, n)
print(long_to_bytes(p))
```
the original writeup : https://qiita.com/kusano_k/items/b3203e7a046625453444#chunk-norris-easy