MENU

Jarvis OJ Crypto

更新了一下 不过还没有做完 可能是我太菜了

Medium RSA

openssl rsa -pubin -text -modulus -in warmup -in pubkey.pem

提取公钥
N = 0xC2636AE5C3D8E43FFB97AB09028F1AAC6C0BF6CD3D70EBCA281BFFE97FBE30DD
e = 0x10001
http://factordb.com 上查了一下 发现N可以分解
p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239
解出来
d = 0x1806799bd44ce649122b78b43060c786f8b77fb1593e0842da063ba0d8728bf1
呃 openssl 不是很会用 花了很长时间 最后求助涛神 拿到了一个脚本 rsatool.py 贴一下脚本所在地
http://veritas501.space/2017/03/01/%E5%AF%86%E7%A0%81%E5%AD%A6%E7%AC%94%E8%AE%B0/
然后执行

python rsatool.py -o private.pem -e 65537 -p 275127860351348928173285174381581152299 -q 319576316814478949870590164193048041239

这样就获得了私钥文件 然后

openssl rsautl -decrypt -in flag.enc -inkey private.pem 

就获得了flag:PCTF{256b_i5_m3dium}

hard RSA

先提取pubkey文件中的 N 和 e
N = 0xC2636AE5C3D8E43FFB97AB09028F1AAC6C0BF6CD3D70EBCA281BFFE97FBE30DD
e = 0x2
在线分解一下N
p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239
一开始以为是低加密指数攻击 但是尝试之后发现不对 然后才发现是Rabin加密算法
解密过程:
先求 $m_p m_q$
$$m_p \equiv c^{\frac{p+1}{4}} \pmod p$$
$$m_q \equiv c^{\frac{q+1}{4}} \pmod q$$
然后我们根据中国剩余定理可以推出
$$r = (y_p \cdot p \cdot m_q + y_q \cdot q \cdot m_p) \mod n$$
$$-r = n -r$$
$$s= (y_p \cdot p \cdot m_q - y_q \cdot q \cdot m_p) \mod n$$
$$-s = n - s$$
这里的$y_p y_q$是p q模对方的逆元

import gmpy
def n2s(num):
    t = hex(num)[2:]
    if len(t) % 2 == 1:
        return ('0'+t).decode('hex')
    return t.decode('hex')
p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239
n = p*q
c = int(open('flag.enc','rb').read().encode('hex'),16)
mp = pow(c, (p+1)/4, p)
mq = pow(c, (q+1)/4, q)
bp = gmpy.invert(p, q)
bq = gmpy.invert(q, p)
r = (bp*p*mq + bq*q*mp)%n
s = (bp*p*mq - bq*q*mp)%n
print n2s(r)
print n2s(n-r)
print n2s(s)
print n2s(n-s)

最后得到四个结果 其中一个就是flag:PCTF{sp3ci4l_rsa}

very hard RSA

可以从给的py文件中看到 加密时只有一个N 但是有多个e 这就要运用共模攻击
我们可以看到加密时
$c_1\equiv m^{e_1} \pmod{n}$
$c_2\equiv m^{e_2} \pmod{n}$
如果$e_1e_2$互质,就存在$s_1s_2$使:
$s_1e_1+s_2e_2=1$
化简得:$c_1^{s_1}c_2^{s_2}\equiv m$ $mod$ $n$

import gmpy
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
def main():
    n = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929L
    e1 = 17
    e2 = 65537
    c1 = int(open('flag.enc1','rb').read().encode('hex'),16)
    c2 = int(open('flag.enc2','rb').read().encode('hex'),16)
    s = egcd(e1, e2)
    s1 = s[1]
    s2 = s[2]
    if s1<0:
        s1 = - s1
        c1 = gmpy.invert(c1, n)
    elif s2<0:
        s2 = - s2
        c2 = gmpy.invert(c2, n)
    m = pow(c1, s1, n) * pow(c2, s2, n) % n
    print hex(m)[2:].decode('hex')
if __name__ == '__main__':
    main()

flag:PCTF{M4st3r_oF_Number_Th3ory}

Tags: CTF, Crypto, RSA
Archives QR Code
QR Code for this page
Tipping QR Code
Leave a Comment