刷题记录

[AFCTF2018]可怜的RSA

做的挺难受的一道题

首先看题目给的文件

“flag.enc”:

1
GVd1d3viIXFfcHapEYuo5fAvIiUS83adrtMW/MgPwxVBSl46joFCQ1plcnlDGfL19K/3PvChV6n5QGohzfVyz2Z5GdTlaknxvHDUGf5HCukokyPwK/1EYU7NzrhGE7J5jPdi0Aj7xi/Odxy0hGMgpaBLd/nL3N8O6i9pc4Gg3O8soOlciBG/6/xdfN3SzSStMYIN8nfZZMSq3xDDvz4YB7TcTBh4ik4wYhuC77gmT+HWOv5gLTNQ3EkZs5N3EAopy11zHNYU80yv1jtFGcluNPyXYttU5qU33jcp0Wuznac+t+AZHeSQy5vk8DyWorSGMiS+J4KNqSVlDs12EqXEqqJ0uA==

“public.key”:

1
2
3
4
5
6
7
8
9
-----BEGIN PUBLIC KEY-----
MIIBJDANBgkqhkiG9w0BAQEFAAOCAREAMIIBDAKCAQMlsYv184kJfRcjeGa7Uc/4
3pIkU3SevEA7CZXJfA44bUbBYcrf93xphg2uR5HCFM+Eh6qqnybpIKl3g0kGA4rv
tcMIJ9/PP8npdpVE+U4Hzf4IcgOaOmJiEWZ4smH7LWudMlOekqFTs2dWKbqzlC59
NeMPfu9avxxQ15fQzIjhvcz9GhLqb373XDcn298ueA80KK6Pek+3qJ8YSjZQMrFT
+EJehFdQ6yt6vALcFc4CB1B6qVCGO7hICngCjdYpeZRNbGM/r6ED5Nsozof1oMbt
Si8mZEJ/Vlx3gathkUVtlxx/+jlScjdM7AFV5fkRidt0LkwosDoPoRz/sDFz0qTM
5q5TAgMBAAE=
-----END PUBLIC KEY-----

这道题不知道为什么不能用pow(c,d,n)pow(c,d,n)的方法来做，所以一直得到乱码

首先读公钥文件，转换成nn和ee

1
2
3
4
5
from Crypto.PublicKey import RSA
f=open('./[AFCTF2018]可怜的RSA/public.key','r').read()
key=RSA.importKey(f)
n=key.n
e=key.e

之后在线网站解密得到pp和qq，随后就是求dd

1
2
3
4
p=3133337
q=n//p
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)

但是这里我分析密文文件的时候是用base64解密之后再转换成数字

1
2
3
4
5
6
from Crypto.PublicKey import RSA
from base64 import b64decode

flag=open('./[AFCTF2018]可怜的RSA/flag.enc','r').read()
c=b64decode(flag)
c=bytes_to_long(c)

随后进行计算

1
2
m=pow(c,d,n)
print(long_to_bytes(m))

得到一串乱码

1
b'\xb2u~\xc4\xd0\xbeV\x1c\x80\x0b\x16F\xee[\xe9\xf4\xbfJ\xd2\x17p\xc2c\xfcvb\x14\xe4\x8c`A\xd4\'Iy=\x11\xeah:\xb9n\x0b\x01\xd2\x03V\xaa\xb2C{\xc3yP\x8aw\xd3\\\xe5\x89\x8e\x8b\xf7\x96\xab["\xfb\xb7(\xfd(\x8b\xa8L,\xf84,l\xf6\xba\x0cr--\xaf\xfc\xbb\xcf6\xdfh\xa4\xae\xb5\x9dh{\x89\x0f]/;\xfa\xcf\xadF\x9d\xdc\x15L!\xbb\xac\xaf^e\x1e\xb4\x9d.\xca8\x02\xf2\x8b5\x82\xc5\xf6\xe6\xd9\x1ci\xc3r\x9a\x7f\x90k\xda\x15/\xaaM_\xa1\x18wY\x98\xa7\xbb\xe4vO\xa57H\xf6y@?k\xc2\xdd)\xf7\x0bvx&\xd4H\xb1\xcf\x88\xf8\x90J\xa0f\x01]\x18\xf4\xf0YG-\x08\x08Jc\xeb\x16\x1bh\xbe\xc3\xa9\x92\xa9D\xcc(\x1bt\x9e\x9a[g\x1eJ\xc5\xfc\xe7\x99\xcb\xaa\xf61D\x8d$\xf1\xce\'0\xc5cuD\x88\xd8\xeb\xe9\xdd\xac\x9cN\xc5-\xaf\x1d\xde\x92\xeb\xe3)g\xe8\r;\xbc\xab\xe6'

之后到网上搜题解，无一例外的都用了

1
2
3
4
key = RSA.construct((n, e, d, p, q))
key = RSA.importKey(key.exportKey())
key = PKCS1_OAEP.new(key)
m = key.decrypt(c)

我也不知道为什么用一般的写不出来，希望有大佬可以指点一下，这里就先死记了。

最后上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from base64 import b64decode
import gmpy2

flag=open('./[AFCTF2018]可怜的RSA/flag.enc','r').read()
c=b64decode(flag)

f=open('./[AFCTF2018]可怜的RSA/public.key','r').read()
k=RSA.importKey(f)
n=k.n
e=k.e
p=3133337
q=n//p
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)

from Crypto.Cipher import PKCS1_OAEP
key = RSA.construct((n, e, int(d), p, q))
key = RSA.importKey(key.exportKey())
key = PKCS1_OAEP.new(key)
m = key.decrypt(c)
print(m)

[RoarCTF2019]babyRSA

先看题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import sympy
import random

def myGetPrime():
    A= getPrime(513)
    print(A)
    B=A-random.randint(1e3,1e5)
    print(B)
    return sympy.nextPrime((B!)%A)
p=myGetPrime()
#A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
#B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596

q=myGetPrime()
#A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
#B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026

r=myGetPrime()

n=p*q*r
#n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
c=pow(flag,e,n)
#e=0x1001
#c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428
#so,what is the flag?

这道题的n,e,cn,e,c都已经给出，重点就是求p,qp,q的值。那么就观察myGetPrimemyGetPrime这个函数，发现它只需要求出B!B!就好了，而且AA和BB都已经给出。但是BB的阶乘非常大，可能要费很长时间，跑了十分钟没跑出来，之后就搜题解，发现是用威尔逊定理写的，这个之前在信安数学基础学了但是现在都忘光了，看来得好好复习这些基础知识，那么话不多说，直接来看正确思路。

先来看看威尔逊定理说了什么：

如果pp为素数，那么

(p−1)!≡−1mod  p(p-1)!\equiv-1\mod{p}

由这个威尔逊定理可以对这个题目进行转换：

首先(A−1)!≡−1mod  A(A-1)!\equiv-1\mod{A}，此时令k=(A−1)!B!k=\frac{(A-1)!}{B!}，这个kk要比B!B!好计算的多，它相当于BB之后，AA之前的所有数相乘

那么此时的公式就可以转变成B!∗k≡−1mod  AB!*k\equiv-1\mod{A}

找到kk的逆元，就可以求出B!≡−k−1mod  AB!\equiv-k^{-1}\mod{A}

这样就可以省很多计算，上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import sympy
import random
import gmpy2
from Crypto.Util.number import *
def myGetPrime(A,B):
    k=1
    for i in range(B+1,A):
        k=k*i%A
    x=gmpy2.invert(k,A)
    xB=-x%A
    return sympy.nextprime(xB)

A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596
p=myGetPrime(A1,B1)

A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026
q=myGetPrime(A2,B2)

n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733

r=(n//p)//q
phi=(p-1)*(q-1)*(r-1)
e=0x1001
d=gmpy2.invert(e,phi)
c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428

m=pow(c,d,n)
flag=long_to_bytes(m)
print(flag)

RSA & what

这道题也不算难，但是最后有个base64隐写之前没见过，吸取线下赛经验，把它记到博客上。

首先题目给出了四个文件

RSA&What_1

看给出的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from Crypto.Util.number import *
from random import randint
from gmpy2 import powmod

p = getPrime(2048)
q = getPrime(2048)
N = p*q
Phi = (p-1)*(q-1)
def get_enc_key(N,Phi):
    e = getPrime(N)
    if Phi % e == 0:
        return get_enc_key(N, Phi)
    else:
        return e
e1 = get_enc_key(randint(10, 12), Phi)
e2 = get_enc_key(randint(10, 12), Phi)

fr = open(r"./base64", "rb")#flag is in this file
f1 = open(r"./HUB1", "wb")
f2 = open(r"./HUB2", "wb")
base64 = fr.read(255)
f1.write("%d\n%d\n" % (N, e1))
f2.write("%d\n%d\n" % (N, e2))
while len(base64)>0:
    pt = bytes_to_long(base64)
    ct1 = powmod(pt, e1, N)
    ct2 = powmod(pt, e2, N)
    f1.write("\n%d" % ct1)
    f2.write("\n%d" % ct2)
    base64 = fr.read(255)
fr.close()
f1.close()
f2.close()

很明显这里用了相同的模数N和两个公钥，加密得出了多个密文，都存放在HUB1和HUB2中，考虑共模攻击：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
from Crypto.Util.number import *
from random import randint
from gmpy2 import powmod
import base64
import primefac
def same_n_attack(n,e1,e2,c1,c2):
    def egcd(a,b):
         x, lastX = 0, 1
         y, lastY = 1, 0
         while (b != 0):
             q = a // b
             a, b = b, a % b
             x, lastX = lastX - q * x, x
             y, lastY = lastY - q * y, y
         return (lastX, lastY)
    s = egcd(e1,e2)
    s1 = s[0]
    s2 = s[1]
    if s1 < 0:
        s1 = -s1
        c1 = primefac.modinv(c1, n)
        if c1 < 0:
            c1 += n
    elif s2 < 0:
        s2 = -s2
        c2 = primefac.modinv(c2, n)
        if c2 < 0:
            c2 += n
    m = (pow(c1, s1, n) * pow(c2, s2, n)) % n
    return m

import gmpy2
f1 = open(r"./HUB1", "r").readlines()
f2 = open(r"./HUB2", "r").readlines()
n=int(f1[0])
e1=int(f1[1])
e2=int(f2[1])
print(e1,e2)
c=''
gcd, s, t = gmpy2.gcdext(e1, e2)
flag=''
for i in range(3,len(f2)):
    message1 = int(f1[i])
    message2 = int(f2[i])
    plain = same_n_attack(n,e1,e2,message1,message2)
    c=long_to_bytes(plain)
    flag+=str(c)
print()
flag = flag[2:-2].split('\\n')
for i in flag:
    print(base64.b64decode(i).decode('utf-8'),end=' ')

得到一串字符串

2

同时会报错

RSA&What_2

一开始不知道为什么报错。输出一下报错的那段密文转换过来的值

RSA&What_4

这里卡了很久，还以为题目出问题了。之后上网搜索才发现是因为这道题就是这样出的，它用了base64隐写，base64的隐写发在这里了。

直接用脚本就可以，最后得到7c86d8f7d6de33a87f7f9d6b005ce640，包上flag{}提交