RSA有毒

Jarvis OJ Medium RSA
Jarvis OJ hard RSA
Jarvis OJ very hard RSA
Jarvis OJ Extremely hard RSA
God Like RSA

Jarvis OJ Medium RSA

首先用如下命令得到n的值

1	openssl rsa -noout -text -inform PEM -in pubkey.pem -pubin

n的值如下

1	0x00c2636ae5c3d8e43ffb97ab09028f1aac6c0bf6cd3d70ebca281bffe97fbe30dd

做素数分解得到p和q，编写如下代码得到flag，注意解密得到的16进制是基数位，所以从第二位开始以ascii码输出

import binascii
import gmpy2
import base64
n = 0x00c2636ae5c3d8e43ffb97ab09028f1aac6c0bf6cd3d70ebca281bffe97fbe30dd
e = 0x10001
enc = 0x6D3EB7DF23EEE1D38710BEBA78A0878E0E9C65BD3D08496DDA64924199110C79
p =  275127860351348928173285174381581152299
q =  319576316814478949870590164193048041239
d = gmpy2.invert(e, (p-1)*(q-1))
msg = gmpy2.powmod(enc,d,p*q)
flag = str(hex(msg))
print flag
flag = flag[3:]
c = binascii.a2b_hex(flag)
print c

flag如下

1	PCTF{256b_i5_m3dium}

Jarvis OJ hard RSA

拿到这个题目发现和上一题非常相似，连n都是一样，但是这里的e = 2。一开始还是想像上一题一样的解法，然而，它果然不会让人这么轻易拿到flag。隐隐约约记得老师上课的时候讲过模n二次根的算法，一翻发现了Rabin公钥密码，是这个没跑了。然后我们用二次符号判断enc(mod p)和enc(mod q)是否是p或q的平方剩余。

root@localhost:~/Temp# python
Python 2.7.14+ (default, Dec  5 2017, 15:17:02) 
[GCC 7.2.0] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import gmpy2
>>> enc = 0x6D3EB7DF23EEE1D38710BEBA78A0878E0E9C65BD3D08496DDA64924199110C79
>>> p =  275127860351348928173285174381581152299
>>> q =  319576316814478949870590164193048041239
>>> x1 = enc % p
>>> gmpy2.jacobi(x1,p)
1
>>> x2 = enc % q
>>> gmpy2.jacobi(x2,q)
1
>>> gmpy2.f_divmod(p,4)
(mpz(68781965087837232043321293595395288074L), mpz(3))
>>> gmpy2.f_divmod(q,4)
(mpz(79894079203619737467647541048262010309L), mpz(3))

经过上述判断，我们就可以用存在二次根的数x1和x2求解二次根，最后用中国剩余定理得到明文

import gmpy2
import binascii
enc = 0x39DE036DE3132757E819F769EAD64BB487EE3F47E67843AFB73748FD9E979BE0
p =  275127860351348928173285174381581152299
q =  319576316814478949870590164193048041239
n = 0x00c2636ae5c3d8e43ffb97ab09028f1aac6c0bf6cd3d70ebca281bffe97fbe30dd
xp = gmpy2.powmod(enc,(p+1)/4,p)
xq = gmpy2.powmod(enc,(q+1)/4,q)
inv_q = gmpy2.invert(q,p)
inv_p = gmpy2.invert(p,q)
c1 = xp*q*inv_q
c2 = xq*p*inv_p
m = ''
m = hex(gmpy2.f_mod(c1+c2,n))[2:] + hex(gmpy2.f_mod(c1-c2,n))[2:] + hex(gmpy2.f_mod(c2-c1,n))[2:] + hex(gmpy2.f_mod(0-c1-c2,n))[2:]
c = binascii.a2b_hex(m[1:])
print c

得到flag为

Jarvis OJ very hard RSA

通过加密代码可知，这两个加密文件共用了模数，自然想到模数攻击，其原理如下
$$
c_1 = m^{e_1} \mod n
$$

$$
c_2 = m^{e_2}\mod n
$$

$$
若e_1和e_2互素，有re_1+se_2 = 1，则可以根据
$$

$$
(c_1)^r*(c2)^s = m^{re_1+se_2} = m \mod n
$$

所以编写solve.py如下

import binascii
import gmpy2

e1 = 17
e2 = 65537
a = gmpy2.gcdext(e1,e2)
r = int(a[1])
s = int(a[2])

fo1 = open('flag.enc1','rb')
fo2 = open('flag.enc2','rb')
c1 = fo1.read()
c1 = int(c1.encode('hex'),16)
c2 = fo2.read()
c2 = int(c2.encode('hex'),16)
fo1.close()
fo2.close()

N = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929L

m = (gmpy2.powmod(c1,r,N)*gmpy2.powmod(c2,s,N))%N
flag = hex(m)
flag = binascii.a2b_hex(flag[2:])
print flag

得到flag如下

1	PCTF{M4st3r_oF_Number_Th3ory}