P05. 基于N分解的RSA题目

  • 对N进行分解（只要知道p和q,就能解出任何rsa）
  • N在有一般情况下不可分解的，如果p和q太接近，或相差过大，或pq很小等情况

1.在线查询分解网站

1
http://www.factordb.com/index.php

2.使用yafu工具分解

下载地址：https://sourceforge.net/projects/yafu/

1
2
3
4
5
#以分解49为例
yafu-x64.exe factor(49)

#导入文件进行分解，主要注意文本结尾要换行！！！不然要报错
yafu-x64.exe "factor(@)" -batchfile 1.txt

3.使用费马分解

网上找的脚本，p和q太接近

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
def isqrt(n):
  x = n
  y = (x + n // x) // 2
  while y < x:
    x = y
    y = (x + n // x) // 2
  return x

def fermat(n, verbose=True):
    a = isqrt(n) # int(ceil(n**0.5))
    b2 = a*a - n
    b = isqrt(n) # int(b2**0.5)
    count = 0
    while b*b != b2:
        # if verbose:
        #     print('Trying: a=%s b2=%s b=%s' % (a, b2, b))
        a = a + 1
        b2 = a*a - n
        b = isqrt(b2) # int(b2**0.5)
        count += 1
    p=a+b
    q=a-b
    assert n == p * q
    # print('a=',a)
    # print('b=',b)
    # print('p=',p)
    # print('q=',q)
    # print('pq=',p*q)
    return p, q
fermat(n)

脚本2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def fermat_factorization(n):
    factor_list = []
    gmpy2.get_context().precision = 2048
    sqrt_n = int(gmpy2.sqrt(n))
    c = sqrt_n
    while True:
        c += 1
        d_square = c**2 - n
        if gmpy2.is_square(d_square):
            d_square = gmpy2.mpz(d_square)
            gmpy2.get_context().precision = 2048
            d = int(gmpy2.sqrt(d_square))
            factor_list.append([c+d,c-d])
        if len(factor_list)==1:
            break
    return factor_list

4.分解出来后，用脚本解密即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import gmpy2
import libnum

p= 
q= 
e= 
c= 

n=p*q
phi_n=(p-1)*(q-1)

#求逆元
#d=libnum.invmod(e,phi_n)
d=gmpy2.invert(e,phi_n)

m=pow(c,d,n)
print(m)
print(libnum.n2s(int(m)).decode())

出题脚本

随机生成flag

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import random
import hashlib
import string

#字符串列表
a=string.printable
#随机生成flag
for i in range(10):
    flag = ""
    for i in range(10):
        flag += a[random.randint(0, 99)]
    flag = hashlib.md5(flag.encode()).hexdigest()
    print("flag{" + flag + "}")

from uuid import uuid1
flag="flag{"+str(uuid1())+"}"
print(flag)

p,q接近，很快就能分解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import libnum
import gmpy2

p=libnum.generate_prime(1024)
#下一个素数
q=gmpy2.next_prime(p)
print(p)
print(q)
print(gmpy2.is_prime(q))
e=65537
m="flag{20d6e2da95dcc1fa5f5432a436c4be18}"
m=libnum.s2n(m)
n=p*q
phi_n=(p-1)*(q-1)
d=libnum.invmod(e,phi_n)
c=pow(m,e,n)

print("n=",n)
print ("e=",e)
print ("c=",c)

解题脚本

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
import  gmpy2
import libnum

def isqrt(n):
  x = n
  y = (x + n // x) // 2
  while y < x:
    x = y
    y = (x + n // x) // 2
  return x

def fermat(n, verbose=True):
    a = isqrt(n) # int(ceil(n**0.5))
    b2 = a*a - n
    b = isqrt(n) # int(b2**0.5)
    count = 0
    while b*b != b2:
        # if verbose:
        #     print('Trying: a=%s b2=%s b=%s' % (a, b2, b))
        a = a + 1
        b2 = a*a - n
        b = isqrt(b2) # int(b2**0.5)
        count += 1
    p=a+b
    q=a-b
    assert n == p * q
    # print('a=',a)
    # print('b=',b)
    print('p=',p)
    print('q=',q)
    # print('pq=',p*q)
    return p, q
n= 11236396438945464079176717143196471087880430124798640194523124584883161483744355761881720924798661332027501424643154414538029585287580122761405974427818841257794157497994556608202723391478027760181705924317533420305444809223444128034654367210331137068958693840582892819495487826045956577156074156668942232139402108462349340352898572481115406698318121299787982873916502591396884489682255184448165523604671743400422220149772905676655777228607948091675612455989601008858361759327370403306760674195506394280387024357322586732298060169962426894360775981877169895632927906390632063530920611197753716095903307467004289983267
e= 65537
c= 4260482466101011731957430920901406417434306478040387371588613512063428441001754753741853444857207349755032658064826592770143368278573527632514794087007140974732031358793249329430363014561312271335226315065519570861993052432656879088776144909638480994662696119431870831156129142403063675855781198930583825083362703887688501680905266707624440432914989795886392952354713859444836529227033324455920455610359249535012999943891644938239837207994673190694512955995798836266797112432609992164908679997257920566918693544746179908166741635316261624634351348613130319346356388546672516037747806222134853885202448682842353199133
pq=fermat(n)
p=pq[0]
q=pq[1]
phi_n=(p-1)*(q-1)
#求逆元
#d=libnum.invmod(e,phi_n)
d=gmpy2.invert(e,phi_n)
m=pow(c,d,n)
print(m)
print(libnum.n2s(int(m)).decode())

P06.RSA密钥生成与读取

1.pycryptodome模块

公钥生成

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.PublicKey import RSA

p= 787228223375328491232514653709
q= 814212346998672554509751911073
n= 640970939378021470187479083920100737340912672709639557619757
d= 590103645243332826117029128695341159496883001869370080307201
e= 65537


rsa_components = (n, e)
keypair = RSA.construct(rsa_components)
with open('pubckey.pem', 'wb') as f :
    f.write(keypair.exportKey())

私钥生成

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.PublicKey import RSA

p= 787228223375328491232514653709
q= 814212346998672554509751911073
n= 640970939378021470187479083920100737340912672709639557619757
d= 590103645243332826117029128695341159496883001869370080307201
e= 65537


rsa_components = (n,e,d,p,q)
keypair = RSA.construct(rsa_components)
with open('private1.pem', 'wb') as f :
    f.write(keypair.exportKey())

公钥读取

1
2
3
4
5
from Crypto.PublicKey import RSA
with open("pubckey.pem","rb") as f:
    key = RSA.import_key(f.read())
    print('n = %d' % key.n)
    print('e = %d' % key.e)

私钥读取

1
2
3
4
5
6
7
8
from Crypto.PublicKey import RSA
with open("private1.pem","rb") as f:
    key = RSA.import_key(f.read())
    print('n = %d' % key.n)
    print('e = %d' % key.e)
    print('d = %d' % key.d)
    print('p = %d' % key.p)
    print('q = %d' % key.q)

2.rsa模块 （不推荐）

公钥生成

1
2
3
4
5
6
7
8
9
10
11
12
13
import rsa

p= 787228223375328491232514653709
q= 814212346998672554509751911073
n= 640970939378021470187479083920100737340912672709639557619757
d= 590103645243332826117029128695341159496883001869370080307201
e= 65537

pubkey = rsa.PublicKey(n , e )
print(pubkey)
pub=rsa.PublicKey.save_pkcs1(pubkey)
with open("pub.pem","wb") as f:
    f.write(pub)

私钥生成

1
2
3
4
5
6
7
8
9
10
11
12
import rsa

p= 787228223375328491232514653709
q= 814212346998672554509751911073
n= 640970939378021470187479083920100737340912672709639557619757
d= 590103645243332826117029128695341159496883001869370080307201
e= 65537
prikey = rsa.PrivateKey(n , e , d , p , q)
print(prikey)
pri=rsa.PrivateKey.save_pkcs1(prikey)
with open("pri.pem","wb") as f:
    f.write(pri)

公钥读取

1
2
3
4
5
6
7
import rsa
with open('2.pem','rb') as f:
    keydata= f.read()
pubckey = rsa.PublicKey.load_pkcs1(keydata)
#pubckey = rsa.PublicKey.load_pkcs1_openssl_pem(keydata)
print(pubckey.n)
print(pubckey.e)

私钥读取

1
2
3
4
5
6
7
8
9
import rsa
with open('1.pem','rb') as f:
    keydata= f.read()
pubckey = rsa.PrivateKey.load_pkcs1(keydata)
print(pubckey.n)
print(pubckey.e)
print(pubckey.d)
print(pubckey.q)
print(pubckey.p)

出题脚本

随机生成flag

1
2
3
4
5
6
7
8
9
10
11
12
13
import random
import hashlib
import string

#字符串列表
a=string.printable
#随机生成flag
for i in range(10):
    flag = ""
    for i in range(10):
        flag += a[random.randint(0, 99)]
    flag = hashlib.md5(flag.encode()).hexdigest()
    print("flag{" + flag + "}")

基于N分解的题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import libnum
import gmpy2
from Crypto.PublicKey import RSA

p=libnum.generate_prime(1024)
#下一个素数
q=int(gmpy2.next_prime(p))
e=65537
m="flag{a272722c1db834353ea3ce1d9c71feca}"
m=libnum.s2n(m)
n=p*q
c=pow(m,e,n)
flag_c=libnum.n2s(c)
rsa_components = (n, e)
keypair = RSA.construct(rsa_components)
with open('pubckey1.pem', 'wb') as f :
    f.write(keypair.exportKey())
with open("flag.txt","wb") as f:
    f.write(flag_c)

解题脚本

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
52
53
54
55
import libnum
import gmpy2
from Crypto.PublicKey import RSA


def isqrt(n):
  x = n
  y = (x + n // x) // 2
  while y < x:
    x = y
    y = (x + n // x) // 2
  return x

def fermat(n, verbose=True):
    a = isqrt(n) # int(ceil(n**0.5))
    b2 = a*a - n
    b = isqrt(n) # int(b2**0.5)
    count = 0
    while b*b != b2:
        # if verbose:
        #     print('Trying: a=%s b2=%s b=%s' % (a, b2, b))
        a = a + 1
        b2 = a*a - n
        b = isqrt(b2) # int(b2**0.5)
        count += 1
    p=a+b
    q=a-b
    assert n == p * q
    # print('a=',a)
    # print('b=',b)
    # print('p=',p)
    # print('q=',q)
    # print('pq=',p*q)
    return p, q


with open("pubckey1.pem","rb") as f:
    key = RSA.import_key(f.read())
    n=key.n
    e=key.e

with open("flag.txt","rb") as f:
    c=f.read()
    c=libnum.s2n(c)

#费马分解,
n1=fermat(n)
p=n1[0]
q=n1[1]
phi_n=(p-1)*(q-1)
#求逆元
d=libnum.invmod(e,phi_n)
m=pow(c,d,n)
print(m)
print(libnum.n2s(int(m)).decode())

自动生成密钥及加解密过程

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
from Crypto.Cipher import PKCS1_v1_5
from Crypto import Random
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP


random_generator = Random.new().read
rsa = RSA.generate(2048, random_generator)
# 生成私钥
private_key = rsa.exportKey()
# print(private_key.decode('utf-8'))
with open('rsa_private_key.pem', 'wb')as f:
    f.write(private_key)
# 生成公钥
public_key = rsa.publickey().exportKey()
# print(public_key.decode('utf-8'))
with open('rsa_public_key.pem', 'wb')as f:
    f.write(public_key)


#测试用密钥加密
public_key = RSA.importKey(public_key)
msg='flag'
pk = PKCS1_v1_5.new(public_key)
encrypt_text = pk.encrypt(msg.encode())
print(encrypt_text)

#测试密钥解密
private_key = RSA.importKey(private_key)
pk = PKCS1_v1_5.new(private_key)
msg = pk.decrypt(encrypt_text,0)
print(msg)


#两种标准
rsa_components = (n, e, int(d), p, q)
arsa = RSA.construct(rsa_components)
rsakey = RSA.importKey(arsa.exportKey())
rsakey = PKCS1_OAEP.new(rsakey)
decrypted = rsakey.decrypt(c)
print(decrypted)

P07.共模攻击

共模攻击，也称同模攻击。

同模攻击利用的大前提就是，RSA体系在生成密钥的过程中使用了相同的模数n。

在CTF题目中，就是 同一明文，同一n,不同e，进行加密。

m，n相同；e，c不同，且e1 和 e2互质

出题脚本

随机生成flag

1
2
3
4
5
6
7
8
9
10
11
12
13
import random
import hashlib
import string

#字符串列表
a=string.printable
#随机生成flag
for i in range(10):
    flag = ""
    for i in range(10):
        flag += a[random.randint(0, 99)]
    flag = hashlib.md5(flag.encode()).hexdigest()
    print("flag{" + flag + "}")

题目1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#coding:utf-8
import libnum
import gmpy2
#生成素数
p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
e1=2333
e2=23333
m="flag{6ed4c74e022cb18c8039e96de93aa9ce}"
m=libnum.s2n(m)
n=p*q
#pow(x, y[, z])
#函数是计算 x 的 y 次方，如果 z 在存在，则再对结果进行取模
c1=pow(m,e1,n)
c2=pow(m,e2,n)
print("n1:",n)
print("e1:",e1)
print("c1:",c1)
print("n2:",n)
print("e2:",e2)
print("c2:",c2)

题目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
34
#coding:utf-8
import gmpy2
import libnum

n=10509135007927020910961570498020654777820601579825669027410027026173076573380693204454238919762243178647774720169342528691085983225219960236799370268896666867164869238677749575679762611540687182614629847614275763451130215062534086871119259415866636857654106010518677919485438729877453549868724935457349692430637646827845074169704597756894678350214029352130966923159025112991395150214022844221949818486992653054085916326074567355928744181958934887632087019273037034539054980148783728604561167417571308543568511557184742388987903995431328908643666134429145944816840592528868078022503367301892068877343146684216682292031
e1=2333
c1=7817747253100075445080016685151086112268236401548478039383697586624131257005712900744875480257235019856465005133060251952853265167801711501859975585492982445693865641552507292652891995513965716569403068769379922648392091598433743576490830481993190692094310002540291082497060442504191087716491306341060343322555758506922102525722142895936303098845293736052077805416603114326241892440936798612985329887620848022507113494020806335634837064221561034485913416272720657761870572787579710754920585427628542146537468299211892356070884683021760416483687996756045071803827949139730328011630778732391114457251096093112357217218
n2=10509135007927020910961570498020654777820601579825669027410027026173076573380693204454238919762243178647774720169342528691085983225219960236799370268896666867164869238677749575679762611540687182614629847614275763451130215062534086871119259415866636857654106010518677919485438729877453549868724935457349692430637646827845074169704597756894678350214029352130966923159025112991395150214022844221949818486992653054085916326074567355928744181958934887632087019273037034539054980148783728604561167417571308543568511557184742388987903995431328908643666134429145944816840592528868078022503367301892068877343146684216682292031
e2=23333
c2=4005739533838233872100900192412804692746056018222370689494999429600683965220671145551011781360384072398973847079099863801781412654844344905559510784496389730242858693821886631397324132791823439680955157172958658051082121321917953586754734740594115385719917993135141183252010390389651513644552790616554115701338569755344442572426665297172781226400939991451728779259308086811204397695171302495091439788703682660000347393283282772216143916787270940246611837483151694679246528820414931162726657909701256510917389048934521382784300651451892299324944208983841733409704979351560563883697858790944929943311340614454947233485


#共模攻击
#共模攻击函数
def rsa_gong_N_def(e1,e2,c1,c2,n):
    e1, e2, c1, c2, n=int(e1),int(e2),int(c1),int(c2),int(n)
    print("e1,e2:",e1,e2)
    print(gmpy2.gcd(e1,e2))
    s = gmpy2.gcdext(e1, e2)
    print(s)
    s1 = s[1]
    s2 = s[2]
    if s1 < 0:
        s1 = - s1
        c1 = gmpy2.invert(c1, n)
    elif s2 < 0:
        s2 = - s2
        c2 = gmpy2.invert(c2, n)
    m = (pow(c1,s1,n) * pow(c2 ,s2 ,n)) % n
    return int(m)

m = rsa_gong_N_def(e1,e2,c1,c2,n)
print(m)
print(libnum.n2s(int(m)).decode())

题目2（密钥型，跟2018年巅峰极客的类似）

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
import libnum
from Crypto.PublicKey import RSA
import base64
p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
e1=2333
e2=23333
n=p*q
m="flag{09edeb8aa1db60814c34da8994590758}"
m=libnum.s2n(m)
n=p*q
c1=pow(m,e1,n)
c2=pow(m,e2,n)
#print "d:",d

rsa_components = (n, e1)
keypair = RSA.construct(rsa_components)
with open('pubkey1.pem', 'wb') as f :
    f.write(keypair.exportKey())

rsa_components = (n, e2)
keypair = RSA.construct(rsa_components)
with open('pubkey2.pem', 'wb') as f :
    f.write(keypair.exportKey())

with open("c1.enc","wb") as f:
    f.write(base64.b64encode(libnum.n2s(c1)))
with open("c2.enc","wb") as f:
    f.write(base64.b64encode(libnum.n2s(c2)))

题目2解密脚本

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
#coding:utf-8
import gmpy2
import libnum
from Crypto.PublicKey import RSA
import base64

with open("pubkey1.pem","rb") as f:
    key = RSA.import_key(f.read())
    n1=key.n
    e1=key.e

with open("pubkey2.pem","rb") as f:
    key = RSA.import_key(f.read())
    n2=key.n
    e2=key.e

with open("c1.enc","rb") as f:
    c1=f.read()
    c1=base64.b64decode(c1)
    c1=libnum.s2n(c1)
with open("c2.enc","rb") as f:
    c2=f.read()
    c2=base64.b64decode(c2)
    c2=libnum.s2n(c2)

n=n1
# 共模攻击
# 扩展欧几里得算法
s = gmpy2.gcdext(e1, e2)
s1 = s[1]
s2 = -s[2]
#求逆元
c2 = gmpy2.invert(c2, n)
m = (pow(c1,s1,n) * pow(c2 , s2 , n)) % n
print(m)
print(libnum.n2s(int(m)).decode())

共模攻击原理

https://www.dazhuanlan.com/2019/12/18/5df98f54585e8/

两个及以上的公钥(n,e)来加密同一条信息m

1
2
c1 = pow(m, e1, n)
c2 = pow(m, e2, n)

e1，e2互质，则有

1
gcd(e1,e2)=1

根据扩展欧几里德算法 对于不完全为 0 的整数 a，b，gcd（a，b）表示 a，b 的最大公约数。那么一定存在整数 x，y 使得 gcd（a，b）=ax+by

1
e1*s1+e2*s2 = 1

s1、s2皆为整数，但是一正一负，假设s1为正数,s2为负数

因为

1
2
c1 = m^e1%n
c2 = m^e2%n

可得：

1
(c1^s1*c2^s2)%n = ((m^e1%n)^s1(m^e2%n)^s2)%n

根据模运算性质： 幂运算是一种关于幂的数学运算。同底数幂相乘，底数不变，指数相加。同底数幂相除，底数不变，指数相减。幂的乘方，底数不变，指数相乘。

1
2
(a * b) % p = (a % p * b % p) % p
a ^ b % p = ((a % p) ^ b) % p

简化公式为：

1
2
3
4
5
6
7
8
9
10
11
(c1^s1*c2^s2)%n = ((m^e1%n)^s1*(m^e2%n)^s2)%n

=> (c1^s1*c2^s2)%n = ((m^e1%n)^s1%n*(m^e2%n)^s2%n)%n #(a * b) % p = (a % p * b % p) % p

=> (c1^s1*c2^s2)%n = ((m^e1)^s1%n*(m^e2)^s2%n)%n #((a % p) ^ b) % p =a ^ b % p

=> (c1^s1*c2^s2)%n = ((m^e1)^s1*(m^e2)^s2)%n # (a % p * b % p) % p=(a * b) % p

=>(c1^s1*c2^s2)%n = ((m^(e1*s1)*(m^(e2*s2))%n #。幂的乘方，底数不变，指数相乘。

(c1^s1*c2^s2)%n = (m^(e1*s1+e2*s2))%n  # 同底数幂相乘，底数不变，指数相加。

因为 e1s1+e2s2 = 1 得：

1
2
3
(c1^s1*c2^s2)%n = (m^1)%n

(c1^s1*c2^s2）%n=m

上述就是rsa共模攻击的过程

因此，同一m，同一n,不同e，进行加密。在不需要知道d的情况下，可以进行解密。

P08.wiener(维纳)攻击

低解密指数攻击

维纳攻击：e指数很大(理论上d<N**0.25此攻击起作用)

维纳攻击原理：https://zhuanlan.zhihu.com/p/400818185

本节的脚本主要参考 https://github.com/pablocelayes/rsa-wiener-attack

出题脚本

随机生成flag

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
import random
import hashlib
import string

#字符串列表
a=string.printable
#随机生成flag
for i in range(10):
    flag = ""
    for i in range(10):
        flag += a[random.randint(0, 99)]
    flag = hashlib.md5(flag.encode()).hexdigest()
    print("flag{" + flag + "}")
import libnum
import random
import gmpy2
#生成随机素数
p=libnum.generate_prime(512)
q=libnum.generate_prime(512)
m="flag{20d6e2da95dcc1fa5f5432a436c4be18}"
#字符串转数字
m=libnum.s2n(m)
n=p*q
phi_n=(p-1)*(q-1)

#计算d
while True:
    nbits=1024
    d = random.getrandbits(nbits // 4)
    if (libnum.gcd(d, phi_n) == 1 and 36 * pow(d, 4) < n):
        break
#计算e
e = libnum.invmod(d,phi_n)

c=pow(m,e,n)


print ("n=",n)
print ("e=",e)
print ("c=",c)

解密脚本

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import gmpy2
import libnum

def continuedFra(x, y):
    """计算连分数
    :param x: 分子
    :param y: 分母
    :return: 连分数列表
    """
    cf = []
    while y:
        cf.append(x // y)
        x, y = y, x % y
    return cf
def gradualFra(cf):
    """计算传入列表最后的渐进分数
    :param cf: 连分数列表
    :return: 该列表最后的渐近分数
    """
    numerator = 0
    denominator = 1
    for x in cf[::-1]:
        # 这里的渐进分数分子分母要分开
        numerator, denominator = denominator, x * denominator + numerator
    return numerator, denominator
def solve_pq(a, b, c):
    """使用韦达定理解出pq，x^2−(p+q)∗x+pq=0
    :param a:x^2的系数
    :param b:x的系数
    :param c:pq
    :return:p，q
    """
    par = gmpy2.isqrt(b * b - 4 * a * c)
    return (-b + par) // (2 * a), (-b - par) // (2 * a)
def getGradualFra(cf):
    """计算列表所有的渐近分数
    :param cf: 连分数列表
    :return: 该列表所有的渐近分数
    """
    gf = []
    for i in range(1, len(cf) + 1):
        gf.append(gradualFra(cf[:i]))
    return gf


def wienerAttack(e, n):
    """
    :param e:
    :param n:
    :return: 私钥d
    """
    cf = continuedFra(e, n)
    gf = getGradualFra(cf)
    for d, k in gf:
        if k == 0: continue
        if (e * d - 1) % k != 0:
            continue
        phi = (e * d - 1) // k
        p, q = solve_pq(1, n - phi + 1, n)
        if p * q == n:
            return d


n=
e=
c=
d=wienerAttack(e, n)
m=pow(c, d, n)
print(libnum.n2s(m).decode())

P09.低加密指数攻击

加密指数指的是e，e一般选取65535，当e很小，可直接破解。

这类攻击在CTF题中，一般是 e=3

1
2
3
4
5
6
如果e=3，且m^e<n，c开3次根式，得到m。

如果e=3，且m^e>n，那么设k，有：
 c= m^e +kn

爆破k，如果c−kn能开三次根式，得到m.

出题脚本

随机生成flag

1
2
3
4
5
6
7
8
9
10
11
12
13
import random
import hashlib
import string

#字符串列表
a=string.printable
#随机生成flag
for i in range(10):
    flag = ""
    for i in range(10):
        flag += a[random.randint(0, 99)]
    flag = hashlib.md5(flag.encode()).hexdigest()
    print("flag{" + flag + "}")

e=3 出题脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import libnum
import gmpy2

#生成随机素数
p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
e=3
m="flag{20d6e2da95dcc1fa5f5432a436c4be18}"
#字符串转数字
m=libnum.s2n(m)
n=p*q
phi_n=(p-1)*(q-1)
#求逆元
d=gmpy2.invert(e,phi_n)
c=pow(m,e,n)

print ("n=",n)
print ("e=",e)
print ("c=",c)

e=3 解密脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import gmpy2
import libnum

def de(c, e, n):
    k = 0
    while True:
        mm = c + n*k
        result, flag = gmpy2.iroot(mm, e)
        if True == flag:
            return result
        k += 1
e= 3
n=
c=

m=de(c,e,n)
print(m)
print(libnum.n2s(int(m)).decode())

附录 多进程爆破脚本

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
#/usr/bin/python
# coding=utf-8
import gmpy2
from Crypto.PublicKey import RSA
from multiprocessing import Pool
pool = Pool(4)

with open('./pubkey.pem', 'r') as f:
    key = RSA.importKey(f)
    N = key.n
    e = key.e
with open('flag.enc', 'r') as f:
    cipher = f.read().encode('hex')
    cipher = int(cipher, 16)


def calc(j):
    print j
    a, b = gmpy2.iroot(cipher + j * N, 3)
    if b == 1:
        m = a
        print '{:x}'.format(int(m)).decode('hex')
        pool.terminate()
        exit()


def SmallE():
    inputs = range(0, 130000000)
    pool.map(calc, inputs)
    pool.close()
    pool.join()


if __name__ == '__main__':
    print 'start'
    SmallE()

P10.低加密指数广播攻击

如果选取的加密指数较低，并且使用了相同的加密指数给一个接受者的群发送相同的信息，那么可以进行广播攻击得到明文。

在CTF中，n、c不同，明文m，e相同，其e比较小。使用中国剩余定理求解

出题脚本

随机生成flag

1
2
3
4
5
6
7
8
9
10
11
12
13
import random
import hashlib
import string

#字符串列表
a=string.printable
#随机生成flag
for i in range(10):
    flag = ""
    for i in range(10):
        flag += a[random.randint(0, 99)]
    flag = hashlib.md5(flag.encode()).hexdigest()
    print("flag{" + flag + "}")

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import libnum
#生成随机素数
def rsa_def(e,m):
    p=libnum.generate_prime(1024)
    q=libnum.generate_prime(1024)
    #字符串转数字
    m=libnum.s2n(m)
    n=p*q
    c=pow(m,e,n)
    n_lt.append(n)
    c_lt.append(c)

n_lt=[]
c_lt=[]
e=23
m='flag{2cb2eb4b2c7fdf4e94e10344be856446}'
for i in range(7):
    rsa_def(e,m)

print("e=",e)
print("n=",n_lt)
print("c=",c_lt)

解密脚本

解密脚本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
34
35
36
37
38
39
40
import libnum
from gmpy2 import invert, gcd, iroot


def op(x):
    res = 1
    for i in x:
        res *= i
    return res


def CRT(m, a):
    assert (len(m) == len(a))
    M = op(m)
    sum = 0
    for m, a in zip(m, a):
        Mi = M // m
        ti = invert(Mi, m)
        sum += a * ti * Mi
    return sum % M
def GCRT(m, a):
    assert (len(m) == len(a))
    curm, cura = m[0], a[0]
    for m, a in zip(m[1:], a[1:]):
        d = gcd(curm, m)
        c = a - cura
        assert (c % d == 0)
        K = c // d * invert(curm // d, m // d)
        cura += curm * K
        curm = curm * m // d
    return cura % curm

e= 23
n=[]
c=[]

m = CRT(n, c)
m1 = iroot(m, e)  # 开e次方
print(m1)
print(libnum.n2s(int(m1[0])))

解密脚本2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import binascii,gmpy2
from functools import reduce

import libnum


def CRT(mi, ai):
    assert(reduce(gmpy2.gcd,mi)==1)
    assert (isinstance(mi, list) and isinstance(ai, list))
    M = reduce(lambda x, y: x * y, mi)
    ai_ti_Mi = [a * (M // m) * gmpy2.invert(M // m, m) for (m, a) in zip(mi, ai)]
    return reduce(lambda x, y: x + y, ai_ti_Mi) % M

e= 23
n=[]
c=[]

m=gmpy2.iroot(CRT(n, c), e)[0]
print(m)
print(libnum.n2s(int(m)))

P11.共享素数-N不互素

两个n里使用有相同的素数p或q 在CTF中，同样一个e（一般为65537）和m， 有两个或多个n和c时，那么n之间可能是共享素数

出题脚本

随机生成flag

1
2
3
4
5
6
7
8
9
10
11
12
13
import random
import hashlib
import string

#字符串列表
a=string.printable
#随机生成flag
for i in range(10):
    flag = ""
    for i in range(10):
        flag += a[random.randint(0, 99)]
    flag = hashlib.md5(flag.encode()).hexdigest()
    print("flag{" + flag + "}")

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import libnum

#生成随机素数
p1=libnum.generate_prime(1024)
p2=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
e=65537
m="flag{c9d48baa792e91ce65d175bb586f8c24}"
#字符串转数字
m=libnum.s2n(m)
print(q)
n1=p1*q
n2=p2*q
#求逆元
c1=pow(m,e,n1)
c2=pow(m,e,n2)

print ("e=",e)
print("n1=",n1)
print("n2=",n2)
print ("c1=",c1)
print ("c2=",c2)

解题脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import libnum
import gmpy2


e= 65537
n1= 
n2= 
c1= 
c2=

#求最大公约数
q=gmpy2.gcd(n1,n2)
p1=n1//q

phi_n=(q-1)*(p1-1)
#求逆元d
d1=libnum.invmod(e,phi_n)
m=pow(c1,d1,n1)
print(m)
#数字转字节，转字符串
print(libnum.n2s(int(m)).decode())

模不互素,另类脚本 sage

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
e= 65537
n1= 21093893530165595850339636291340886775560459889174993298599564679470961520127537242137351793326916956073009495303622153882623912792088101281148271957920985536369095953335024370158909102755939425266322061024660469804331164229029302486833732919273709880115072578649082360889893770131535569945349586879686172801621707802368786052168013925892590355941771860436819249314675001571361991296570354259045254453585842424561844676250437625123809885279029491512960326206418322762119343167800501997630708987739950144724219375568233516957162796160222178022591375724806703162674485897117438453945303273004012532132059011075717387753
n2= 14824267720565830614198366423536599666692078969408403530258418602151322644585576708517191288357418574410537646212589360867055238409644225020114747038342097744542022643037865665129552322573216047070677736725417436626920538199776045223182025555032687422098410274010072272948921387942284889428172227747124840681230287572405913777684484640035353309074356839921615363768839468380890923086904115913017609689750326299359077846457821010369130002914875100460359637094049091716624328545343429605828899486733904861746381542564902018804771429533804771098266001841458433664015729735822285137823715376774756745985491673136930276941
c1= 15493359169301410074294742205843127951680374731395022149514872755993630629089162028408320207198994693027373636212060578272511287443597043280252256375148624563670499072871754643384189774533934405727733699679220914275088403183879336594241788249627810478123376166068327204499510069769671107400170031827409347799781818216854334998468909013183811525688284142974464445136216626020389073625379426889005557474784633107067037562364550927860932957239328403322326674852543731738932181913222422086087135017041465305467628933404091450876573447149054228726054585012570036091080257371923849834757954329673617514640675309941718326627
c2= 1129639783725801764965293730716077563236066858849848417513754106728304324550964149779456929545632835403665303400567929779454798061338838786581070336886869145357696864488611518771125027534268787109010503430313447389460984683822032899389007646158783785728285343713347931494062199917243631366285764058939519090743602216977513724902021454418835574712871092514940757735723709297452463014431720040155161772629328937153713384012521957796438994675887733312827926502709695530933411909694455038223632075992122461473772324457706144526855909934434396846023332605403533525981854297958006877942800622448532300316434156727548355876

p=GCD(n1,n2) 
q1=n1//p 
q2=n2//p 
e=0x10001 
a=crt([c1,c2],[n1,n2]) 
d=inverse_mod(e,(p-1)*(q1-1)*(q2-1)) 
m=pow(int(a),d,p*q1*q2) 
print(m)
nb=int(m).bit_length()//8+1 
print(int(m).to_bytes(nb,'big'))

P12.dp泄露

出题脚本

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
#coding:utf-8
import random
import base64
import hashlib
import string
import libnum

def put_flag():
    # 字符串列表
    a = string.printable
    flag = ""
    for i in range(10):
        flag += a[random.randint(0, 99)]
    flag = r"flag{%s}"%(hashlib.md5(flag.encode()).hexdigest())
    print(flag)
    return flag

#生成素数
p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
e=65537
n=p*q
phi_n=(p-1)*(q-1)
d=libnum.invmod(e,phi_n)
dp=d%(p-1)
m=put_flag()
m=libnum.s2n(m)
n=p*q
c=pow(m,e,n)

print("n=",n)
print("e=",e)
print("dp=",dp)
print("c=",c)

解密脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#coding:utf-8
import libnum
import gmpy2

n= 20591086052762884774007642208627186047740785982069905465339106113815517926005138245376424039890471346116595814990565096469487055161205492208983070664066759158320021466738870626889248859926445073065690645149662384802893003569214932187478720052507261122240086903309849212209649669687231860209185304367043990868365998317112708060029389114801978983457120555456044119368210749131216212628106714166030746209367457730301494656881326171842507368964603885018433049753989158109159264897704177466521001420986879635961230539498749382319333460275823384358292388617142535346744858436238862753394517975326105321275152062417195136487
e= 65537
dp= 117650567231513516304011449747630188369389787217757178598401487861414722594762697578263686709962979384903219013406107957537598898044022905612629709116256327804419610618227360381750844695360296505774931533979275522382118810562627585509057288685774693859111511668637640128536485929734825688725882979874153712289
c= 11882214238703654387165659956294046561271974803426268099981312451686746219445527904685768634078193803230258145834800940089716687361084767393552437220859938746433048199198403178660887457673639116251966379227242789841204694915397745327702138343494160974011134668539019661693330405169786812935866677630175241506856985283075068700171501509407518847350856175791919328062950403163853767193784729690208750698852790441958574336390898190131490970318926320913093369651228634714453458106787439297347445279781184630937957106170862280836800221040231888465070504491616197979521787557062164298550636929825159364431658963099844517487

for i in range(1,65535):
    p=(dp*e-1)//i+1
    if n%p==0:
        q=n//p
        break
print(p)
print(q)
phi_n= (p-1)*(q-1)
d=gmpy2.invert(e,phi_n)
m=pow(c,d,n)
print(m)
flag=libnum.n2s(int(m)).decode()
print(flag)

题目解析

已知公钥n,e以及dp

其中,dp = d mod (p-1)

已知：

1
2
3
4
5
c = m^e mod n
m = c^d mod n
ϕ(n)=(p−1)*(q−1)
d∗e ≡ 1 mod ϕ(n)
dp = d mod (p−1)

由上式可以得到

1
dp*e≡d*e mod (p−1)

因此可以得到

1
2
式1：d∗e=k∗(p−1)+dp∗e
式2：d∗e≡1 mod ϕ(n)

式1带入式2

1
2
3
4
5
6
7
8
9
=> k∗(p−1)+dp∗e ≡1 mod ϕ(n)

=> k∗(p−1)+dp∗e ≡1 mod (p−1)∗(q−1)

=> k1∗(p−1)+dp∗e = k2*(p−1)∗(q−1)+1

=> dp*e =  k2*(p−1)∗(q−1)+1-k1∗(p−1)+dp∗e

=> dp*e = (p-1)*[k2*(p-1)-k1]+1

因dp<p−1（dp是d//（p-1）的余数，dp<p−1）

所以e > k2∗(q−1)−k1

假设 x=k2∗(q−1)−k1

x的范围为 (0,e)

x∗(p−1)+1=dp∗e

求出p-1方法，遍历(0,e)的范围，其中肯定有一个p可以被n整除，那么求出p和q

P13.dp,dq

出题脚本

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
#coding:utf-8
import random
import base64
import hashlib
import string
import libnum

def put_flag():
    # 字符串列表
    a = string.printable
    flag = ""
    for i in range(10):
        flag += a[random.randint(0, 99)]
    flag = r"flag{%s}"%(hashlib.md5(flag.encode()).hexdigest())
    print(flag)
    return flag
#生成素数
p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
e=65537
n=p*q
phi_n=(p-1)*(q-1)
d=libnum.invmod(e,phi_n)
dp=d%(p-1)
dq=d%(q-1)
m=put_flag()
m=libnum.s2n(m)
n=p*q
c=pow(m,e,n)

print("p=",p)
print("q=",q)
print("dq=",dq)
print("dp=",dp)
print("c=",c)

解题脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# coding=utf-8
import gmpy2
import libnum

def decrypt(dp,dq,p,q,c):
    InvQ = gmpy2.invert(q, p)
    mp = pow(c, dp, p)
    mq = pow(c, dq, q)
    m = (((mp-mq)*InvQ) % p)*q+mq
    print(libnum.n2s(int(m)).decode())

p= 
q= 
dq= 
dp= 
c= 

decrypt(dp,dq,p,q,c)

题目解析

1
2
3
4
5
6
7
8
9
10
11
c = m^e mod n

m = c^d mod n

ϕ(n)= (p−1)∗(q−1)

d∗e≡ 1 mod ϕ(n)

dp= d mod (p−1)

dq= d mod (q−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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
m=c^d mod n

gcd(p,q)=1
n=p∗q

利用中国剩余定理,得：
m1=c^d mod p
m2=c^d mod q
m=c^d mod n
m=c^d+k∗n

n=p∗q
m=c^d+p∗q∗k


同时取余q和p

m1≡c^d mod q
m2≡c^d mod p

c^d=kp+m1


式1带入式2
m2≡(kp+m1) mod q

等式两边同时减去m1,
(m2−m1)≡kp mod q

gcd(p,q)=1

所以可以求p的逆元，得到
(m2−m1)∗p1≡k mod q

得到如下两个式子
k≡(m2−m1)∗p1mod q
c^d=kp+m1
m≡c^d mod n


上下两个式子合并

c^d = ((m2−m1)∗p1 mod q)p+m1
m ≡ c^d mod n

最后可以有

m≡(((m2−m1)∗p1 mod q)p+m1) mod n

只剩最后一步了

m1≡cd mod q
m2≡cd mod p

m1和m2怎么求

d≡dp mod (p−1)
d≡dq mod (q−1)

那么分别带入

m1≡cdq mod (q−1) mod q
m2≡cdp mod (p−1) mod p

费马小定理即假如p是质数，且gcd(a,p)=1
a(p−1)≡1 mod p

所以如果我们有等式

d=dp+k∗(p−1)

直接带入
m2≡c^dp+k∗(p−1) mod p

这里的指数，我们拆开，为
m2≡c^dp∗ck∗(p−1) mod p

ck∗(p−1)≡1 mod p

因为p是大素数，显然和c互素所以可以直接得到
m2≡cdp mod p

那么m1根据对称性也可以同理得到

m1≡cdq mod q

故此，我们现在拥有了所有条件，下面归纳一下为

m1≡cdq mod q
m2≡cdp mod p
m≡(((m2−m1)∗p1 mod q)p+m1) mod n

P14.n是p的r次方

ctf中，遇到过这样的题目：

1
n = p^r ，p为素数，没有q了。因为p=q。

那么计算n的欧拉函数φ(n)就是

1
φ(n)=p^r-p^{r-1}

推导过程为：

1
2
3
4
5
6
7
8
9
欧拉函数φ(n)的定义是小于n的自然数中与n互质的数的个数。

p^r 质因数就只有p，那么不与它互质的数都含有p，

和它不互质的数的个数：p^r/p=p^r-1/p=p^{r-1} 

剩下就是互质的数，其个数就是：p^r-p^{r-1} 

则有 φ(n)=p^r-p^{r-1}

出题脚本

随机生成flag

1
2
3
4
5
6
7
8
9
10
11
12
13
import random
import hashlib
import string

#字符串列表
a=string.printable
#随机生成flag
for i in range(10):
    flag = ""
    for i in range(10):
        flag += a[random.randint(0, 99)]
    flag = hashlib.md5(flag.encode()).hexdigest()
    print("flag{" + flag + "}")

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import libnum

#生成随机素数
p=libnum.generate_prime(1024)
e=65537
m="flag{de8c3ea714f7f780185924d473997bcb}"
#字符串转数字
m=libnum.s2n(m)
n=p**4
phi_n=p**4-p**3
#求逆元
d=libnum.invmod(e,phi_n)
c=pow(m,e,n)

print ("n=",n)
print ("e=",e)
print ("c=",c)

解密脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import libnum
import gmpy2

n= 
e= 
c= 
#分解n
#yafu-x64.exe  factor()
p= 
phi_n=p**4-p**3
#求逆元
d=libnum.invmod(e,phi_n)
m=pow(c,d,n)
print(m)
#数字转字节，转字符串
print(libnum.n2s(int(m)).decode())

P15.已知e_d n 求p q

已知e,d n 求p q

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
# 给出n,e,d, 求 q,p
import random
import gmpy2


def gcd(a, b):
    if a < b:
        a, b = b, a
    while b != 0:
        temp = a % b
        a = b
        b = temp
    return a


def getpq(n, e, d):
    p = 1
    q = 1
    while p == 1 and q == 1:
        k = d * e - 1
        g = random.randint(0, n)
        while p == 1 and q == 1 and k % 2 == 0:
            k //= 2
            y = pow(g, k, n)
            if y != 1 and gmpy2.gcd(y - 1, n) > 1:
                p = gmpy2.gcd(y - 1, n)
                q = n // p
    return p, q


def main():
    n = 16352578963372306131642407541567045533766691177138375676491913897592458965544068296813122740126583082006556217616296009516413202833698268845634497478988128850373221853516973259086845725813424850548682503827191121548693288763243619033224322698075987667531863213468223654181658012754897588147027437229269098246969811226129883327598021859724836993626315476699384610680857047403431430525708390695622848315322636785398223207468754197643541958599210127261345770914514670199047435085714403641469016212958361993969304545214061560160267760786482163373784437641808292654489343487613446165542988382687729593384887516272690654309
    e = 65537
    d = 9459928379973667430138068528059438139092368625339079253289560577985304435062213121398231875832264894458314629575455553485752685643743266654630829957442008775259776311585654014858165341757547284112061885158006881475740553532826576260839430343960738520822367975528644329172668877696208741007648370045520535298040161675407779239300466681615493892692265542290255408673533853011662134953869432632554008235340864803377610352438146264524770710345273439724107080190182918285547426166561803716644089414078389475072103315432638197578186106576626728869020366214077455194554930725576023274922741115941214789600089166754476449453
    p, q = getpq(n, e, d)
    print(p)
    print(q)

if __name__ == '__main__':
    main()

已知e_d n 求p q

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
52
53
54
55
56
57
58
59
60
61
62
63
64
#coding=utf-8
from random import randint
import gmpy2
def oddR(r):
    while r%2==0:
        r=r//2
    return r

def bits(b):
    k=[]
    while b:
        if b%2!=0:
            k.append(1)
        else:
            k.append(0)
        b>>=1
    k.reverse()      
    return k

def quickmod(a,b,n):      #a^b mod n 快速幂模n运算
    f=1
    k=bits(b)
    for i in range(len(k)):
        f=(f*f)%n
        if k[i]:
            f=(f*a)%n
    return f

def gcd(m,n):
    while(n!=0):
        m,n=n,m%n
    return m

def func(e_d,N):
    k=e_d-1            
    r=oddR(k)           #求出k=2^t*r中的r

    while True:
        b=randint(2,N-1)    #获取区间(2,N-1)的一个随机数
        a=quickmod(b,r,N)   
        if a==1:            
            continue    
        y=gcd(a-1,N)
        if a>1 and y>1:    
            q=N//y
            return q
        else:
            r=r*2         

def deciphering(e_d,n):    、
    p=func(e_d,n)
    q=n//p
    phi=n-(p+q)+1
    if p*q==n:
        print p
        print q
    else:
        print"error"



n =  20714298338160449749545360743688018842877274054540852096459485283936802341271363766157976112525034004319938054034934880860956966585051684483662535780621673316774842614701726445870630109196016676725183412879870463432277629916669130494040403733295593655306104176367902352484367520262917943100467697540593925707162162616635533550262718808746254599456286578409187895171015796991910123804529825519519278388910483133813330902530160448972926096083990208243274548561238253002789474920730760001104048093295680593033327818821255300893423412192265814418546134015557579236219461780344469127987669565138930308525189944897421753947
e_d=  100772079222298134586116156850742817855408127716962891929259868746672572602333918958075582671752493618259518286336122772703330183037221105058298653490794337885098499073583821832532798309513538383175233429533467348390389323225198805294950484802068148590902907221150968539067980432831310376368202773212266320112670699737501054831646286585142281419237572222713975646843555024731855688573834108711874406149540078253774349708158063055754932812675786123700768288048445326199880983717504538825498103789304873682191053050366806825802602658674268440844577955499368404019114913934477160428428662847012289516655310680119638600315228284298935201
deciphering(e_d,n)

P16.N分解三个素数

对n进行分解，得到了3个素数 n=pqr

随机生成flag

1
2
3
4
5
6
7
8
9
10
11
12
13
import random
import hashlib
import string

#字符串列表
a=string.printable
#随机生成flag
for i in range(10):
    flag = ""
    for i in range(10):
        flag += a[random.randint(0, 99)]
    flag = hashlib.md5(flag.encode()).hexdigest()
    print("flag{" + flag + "}")

出题脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import libnum
import gmpy2
#生成随机素数
p=libnum.generate_prime(32)
q=libnum.generate_prime(32)
r=libnum.generate_prime(512)
e=65537
m="flag{20d6e2da95dcc1fa5f5432a436c4be18}"
#字符串转数字
m=libnum.s2n(m)
n=p*q*r
phi_n=(p-1)*(q-1)*(r-1)
#求逆元
d=libnum.invmod(e,phi_n)
c=pow(m,e,n)
print ("n=",n)
print ("e=",e)
print ("c=",c)

解题脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import libnum
import gmpy2


n=
e= 
c= 
#分解n
#yafu-x64.exe  factor()
p= 
q = 
r = 

phi_n=(p-1)*(q-1)*(r-1)
d=gmpy2.invert(e,phi_n)
m=pow(c,d,n)
print(m)
print(libnum.n2s(int(m)))

P18.e和phi_n不互素

出题脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import gmpy2
import libnum
import random
import uuid
flag="flag{"+str(uuid.uuid4())+"}"
m=libnum.s2n(flag)

while 1:
    e = random.randint(100,1000)
    p=libnum.generate_prime(1024)
    q=libnum.generate_prime(1024)
    phi_n=(p-1)*(q-1)
    t=gmpy2.gcd(e,phi_n)
    if  gmpy2.invert(e // t, phi_n) and t !=1:
        break
n=p*q
c=pow(m,e,n)
print("p=",p)
print("q=",q)
print("e=",e)
print("c=",c)

解题脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import gmpy2
from Crypto.Util.number import *
#当e约去公约数后与phi互素
def decrypt(p,q,e,c):
    n=p*q
    phi=(p-1)*(q-1)
    t=gmpy2.gcd(e,phi)
    d=gmpy2.invert(e//t,phi)
    m=pow(c,d,n)
    msg=gmpy2.iroot(m,t)
    if msg[1]:
        print(long_to_bytes(msg[0]))
p=149728544112555599590936673615696271318636529352637830106348687941183054498250042553549708433208468004536400117026086238076264785396396599290721801532887662723160698502186620809003309343021490868380464762486274154096814166441270611631342173101926176645742035350917214925625954628200341278782929951624259583527
q=149728544112555599590936673615696271318636529352637830106348687941183054498250042553549708433208468004536400117026086238076264785396396599290721801532887662723160698502186620809003309343021490868380464762486274154096814166441270611631342173101926176645742035350917214925625954628200341278782929951624259582993
e=180
c=17971123746814947059314270113966290245749007752378241906733564181493060407114219968936077930494933520528427074831694818994710527963410153282657079091353179846750982127804195747725871635911272654572811618799762595633801414107052800867035212498914627567940429340162711284873714117628807667324064684965941290688518710890089086623981356782977499005308798890348799101436318386502089586589964942282091818134339082321114129830959264557408611168516265190076744300272908807347811446203373025446057616713876047942653095947804696077860211107853183353180163392501353685418796451123620066941329424857070023018877454625734091037559


decrypt(p,q,e,c)

已知n、e、c，基础解

已知n、e、c，但n不能分解

1
m = sympy.nthroot_mod(c,e,n)

已知n、e、c，但n不是数字

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

c='GVd1d3viIXFfcHapEYuo5fAvIiUS83adrtMW/MgPwxVBSl46joFCQ1plcnlDGfL19K/3PvChV6n5QGohzfVyz2Z5GdTlaknxvHDUGf5HCukokyPwK/1EYU7NzrhGE7J5jPdi0Aj7xi/Odxy0hGMgpaBLd/nL3N8O6i9pc4Gg3O8soOlciBG/6/xdfN3SzSStMYIN8nfZZMSq3xDDvz4YB7TcTBh4ik4wYhuC77gmT+HWOv5gLTNQ3EkZs5N3EAopy11zHNYU80yv1jtFGcluNPyXYttU5qU33jcp0Wuznac+t+AZHeSQy5vk8DyWorSGMiS+J4KNqSVlDs12EqXEqqJ0uA=='
e=65537
n=79832181757332818552764610761349592984614744432279135328398999801627880283610900361281249973175805069916210179560506497075132524902086881120372213626641879468491936860976686933630869673826972619938321951599146744807653301076026577949579618331502776303983485566046485431039541708467141408260220098592761245010678592347501894176269580510459729633673468068467144199744563731826362102608811033400887813754780282628099443490170016087838606998017490456601315802448567772411623826281747245660954245413781519794295336197555688543537992197142258053220453757666537840276416475602759374950715283890232230741542737319569819793988431443
p=3133337
q=25478326064937419292200172136399497719081842914528228316455906211693118321971399936004729134841162974144246271486439695786036588117424611881955950996219646807378822278285638261582099108339438949573034101215141156156408742843820048066830863814362379885720395082318462850002901605689761876319151147352730090957556940842144299887394678743607766937828094478336401159449035878306853716216548374273462386508307367713112073004011383418967894930554067582453248981022011922883374442736848045920676341361871231787163441467533076890081721882179369168787287724769642665399992556052144845878600126283968890273067575342061776244939

c=b64decode(c)
phi = (q-1) * (p-1)
d = gmpy2.invert(e,phi)

rsa_components=(n,e,int(d),p,q)
arsa=RSA.construct(rsa_components)
rsakey = RSA.importKey(arsa.exportKey())
rsakey = PKCS1_OAEP.new(rsakey) 
decrypted = rsakey.decrypt(c)
print(decrypted)

已知n、e、c，但e与phi不互素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import gmpy2
from Crypto.Util.number import long_to_bytes 

e = 54722
n = 17083941230213489700426636484487738282426471494607098847295335339638177583685457921198569105417734668692072727759139358207667248703952436680183153327606147421932365889983347282046439156176685765143620637107347870401946946501620531665573668068349080410807996582297505889946205052879002028936125315312256470583622913646319779125559691270916064588684997382451412747432722966919513413709987353038375477178385125453567111965259721484997156799355617642131569095810304077131053588483057244340742751804935494087687363416921314041547093118565767609667033859583125275322077617576783247853718516166743858265291135353895239981121
c = 3738960639194737957667684143565005503596276451617922474669745529299929395507971435311181578387223323429323286927370576955078618335757508161263585164126047545413028829873269342924092339298957635079736446851837414357757312525158356579607212496060244403765822636515347192211817658170822313646743520831977673861869637519843133863288550058359429455052676323196728280408508614527953057214779165450356577820378810467527006377296194102671360302059901897977339728292345132827184227155061326328585640019916328847372295754472832318258636054663091475801235050657401857262960415898483713074139212596685365780269667500271108538319
p = 106021448991021391444550749375115277080844281746248845802565680557785009341952320484175568763707424932172033597514861602114171459176440279045761846695231788376075050452154924141266290931413542110639081792550648106240966552406813059396358355737185354885474455248579946190266152416149137616855791805617206153497
q = 161136651053130509602530659420755324119806487925813087617466818245407407797561810253722204813002837916779909309520498985459703212021249251124954613236122142746302911323565396331355397916764254680629384957057354297855676493062493901977415968666512459829211010720514167083018352796496733697235524845188512914793

phi = (q-1) * (p-1)
d=gmpy2.invert(e//2,phi)
m=gmpy2.powmod(c,int(d),n)
m=gmpy2.iroot(m,2)[0]
print (long_to_bytes(m))

dp泄露，已知n、e、c和dp

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
from Crypto.Util.number import *
import gmpy2

e = 65537
n = 156808343598578774957375696815188980682166740609302831099696492068246337198792510898818496239166339015207305102101431634283168544492984586566799996471150252382144148257236707247267506165670877506370253127695314163987084076462560095456635833650720606337852199362362120808707925913897956527780930423574343287847
c = 108542078809057774666748066235473292495343753790443966020636060807418393737258696352569345621488958094856305865603100885838672591764072157183336139243588435583104423268921439473113244493821692560960443688048994557463526099985303667243623711454841573922233051289561865599722004107134302070301237345400354257869
dp = 734763139918837027274765680404546851353356952885439663987181004382601658386317353877499122276686150509151221546249750373865024485652349719427182780275825

#先爆破K得到p、q
temp=dp*e
for i in range(1,e) :
    if (temp-1)%i==0:
        x=(temp-1)//i+1
        y=n%x
        if y==0:
            p=x
            break
q = n // p
assert isPrime(p)
assert isPrime(q)
#print(f"p={p}\nq={q}")

phi = (q-1) * (p-1)
d = gmpy2.invert(e,phi)
#print(d)
m = pow(c,d,n)
m = long_to_bytes(m)
print(m)

pq相似

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import gmpy2
import sympy
from Crypto.Util.number import long_to_bytes

n=177606504836499246970959030226871608885969321778211051080524634084516973331441644993898029573612290095853069264036530459253652875586267946877831055147546910227100566496658148381834683037366134553848011903251252726474047661274223137727688689535823533046778793131902143444408735610821167838717488859902242863683
e = 65537
c=1457390378511382354771000540945361168984775052693073641682375071407490851289703070905749525830483035988737117653971428424612332020925926617395558868160380601912498299922825914229510166957910451841730028919883807634489834128830801407228447221775264711349928156290102782374379406719292116047581560530382210049

n2=gmpy2.iroot(n,2)[0]
p=sympy.nextprime(n2)
q=n//p
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

共模攻击

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import gmpy2
from Crypto.Util.number import long_to_bytes

e1 = 2767
e2 = 3659

n = 21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111

c1 = 20152490165522401747723193966902181151098731763998057421967155300933719378216342043730801302534978403741086887969040721959533190058342762057359432663717825826365444996915469039056428416166173920958243044831404924113442512617599426876141184212121677500371236937127571802891321706587610393639446868836987170301813018218408886968263882123084155607494076330256934285171370758586535415136162861138898728910585138378884530819857478609791126971308624318454905992919405355751492789110009313138417265126117273710813843923143381276204802515910527468883224274829962479636527422350190210717694762908096944600267033351813929448599
c2 = 11298697323140988812057735324285908480504721454145796535014418738959035245600679947297874517818928181509081545027056523790022598233918011261011973196386395689371526774785582326121959186195586069851592467637819366624044133661016373360885158956955263645614345881350494012328275215821306955212788282617812686548883151066866149060363482958708364726982908798340182288702101023393839781427386537230459436512613047311585875068008210818996941460156589314135010438362447522428206884944952639826677247819066812706835773107059567082822312300721049827013660418610265189288840247186598145741724084351633508492707755206886202876227

_, r, s = gmpy2.gcdext(e1, e2)

m = pow(c1, r, n) * pow(c2, s, n) % n
print(long_to_bytes(m))

小明文攻击

1
2
3
4
5
6
7
8
9
import gmpy2
from Crypto.Util.number import long_to_bytes

e = 0x10001
f=open('rsa_16m.txt',"r")
f.readline()
c=int(f.readline().split("=")[1],16)
m = gmpy2.iroot(c,e)[0]
print(long_to_bytes(m))

已知e、d、c，不知道n

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

e = 0x10001
d = 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913
c = 5382723168073828110696168558294206681757991149022777821127563301413483223874527233300721180839298617076705685041174247415826157096583055069337393987892262764211225227035880754417457056723909135525244957935906902665679777101130111392780237502928656225705262431431953003520093932924375902111280077255205118217436744112064069429678632923259898627997145803892753989255615273140300021040654505901442787810653626524305706316663169341797205752938755590056568986738227803487467274114398257187962140796551136220532809687606867385639367743705527511680719955380746377631156468689844150878381460560990755652899449340045313521804

kphi = e*d - 1

for k in range(1, e):
    if kphi % k == 0:
        phi = kphi // k
        root = iroot(phi, 2)[0]
        for p in range(root - 2000, root + 2000):
            if phi % (p-1) == 0: break
        else: continue
        break

q = phi//(p-1) + 1
m = pow(c, d, p*q)
print(long_to_bytes(m))

已知n、c，不知道e

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
'''
A=(((y%x)**5)%(x%y))**2019+y**316+(y+1)/x
p=next_prime(z*x*y)
q=next_prime(z)
'''
A =  2683349182678714524247469512793476009861014781004924905484127480308161377768192868061561886577048646432382128960881487463427414176114486885830693959404989743229103516924432512724195654425703453612710310587164417035878308390676612592848750287387318129424195208623440294647817367740878211949147526287091298307480502897462279102572556822231669438279317474828479089719046386411971105448723910594710418093977044179949800373224354729179833393219827789389078869290217569511230868967647963089430594258815146362187250855166897553056073744582946148472068334167445499314471518357535261186318756327890016183228412253724
n =  117930806043507374325982291823027285148807239117987369609583515353889814856088099671454394340816761242974462268435911765045576377767711593100416932019831889059333166946263184861287975722954992219766493089630810876984781113645362450398009234556085330943125568377741065242183073882558834603430862598066786475299918395341014877416901185392905676043795425126968745185649565106322336954427505104906770493155723995382318346714944184577894150229037758434597242564815299174950147754426950251419204917376517360505024549691723683358170823416757973059354784142601436519500811159036795034676360028928301979780528294114933347127
c =  41971850275428383625653350824107291609587853887037624239544762751558838294718672159979929266922528917912189124713273673948051464226519605803745171340724343705832198554680196798623263806617998072496026019940476324971696928551159371970207365741517064295956376809297272541800647747885170905737868568000101029143923792003486793278197051326716680212726111099439262589341050943913401067673851885114314709706016622157285023272496793595281054074260451116213815934843317894898883215362289599366101018081513215120728297131352439066930452281829446586562062242527329672575620261776042653626411730955819001674118193293313612128

import sympy
from gmpy2 import *
from Crypto.Util.number import long_to_bytes

p = 842868045681390934539739959201847552284980179958879667933078453950968566151662147267006293571765463137270594151138695778986165111380428806545593588078365331313084230014618714412959584843421586674162688321942889369912392031882620994944241987153078156389470370195514285850736541078623854327959382156753458569
q = 139916095583110895133596833227506693679306709873174024876891023355860781981175916446323044732913066880786918629089023499311703408489151181886568535621008644997971982182426706592551291084007983387911006261442519635405457077292515085160744169867410973960652081452455371451222265819051559818441257438021073941183
phi=(p-1)*(q-1)

e=2
str1="RoarCTF{"
while(e<100000):
    e=next_prime(e)
    try:
        d=invert(e,phi)
        m=pow(c,d,n)
    except:
        print (e)
    else:
        d=invert(e,phi)
        m=pow(c,d,n)
        str2=str(long_to_bytes(m))
        if str1 in str2:
            print(long_to_bytes(m))
            break

只有三组c、n

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
from gmpy2 import *
from Crypto.Util.number import *
from functools import reduce

N1 = int(str(331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004),5)
c1 = int(str(310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243),5)
N2 = int(str(302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114),5)
c2 = int(str(112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344),5)
N3 = int(str(332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323),5)
c3 = int(str(10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242),5)

N = [N1,N2,N3]
c = [c1,c2,c3]

def chinese_remainder(modulus, remainders):
    Sum = 0
    prod = reduce(lambda a, b: a*b, modulus)
    for m_i, r_i in zip(modulus, remainders):
        p = prod // m_i
        Sum += r_i * (inverse(p,m_i)*p)
    return Sum % prod
e = 3
# print(chinese_remainder(N,c))
pow_m_e = chinese_remainder(N,c)
# pow_m_e = 17446992834638639179129969961058029457462398677361658450137832328330435503838651797276948890990069700515669656391607670623897280684064423087023742140145529356863469816868212911716782075239982647322703714504545802436551322108638975695013439206776300941300053940942685511792851350404139366581130688518772175108412341696958930756520037
m = iroot(pow_m_e,3)[0]
print(long_to_bytes(m))

只知道三组m、c，不知道n、e

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
from Crypto.Util.number import *
from gmpy2 import *
from sympy import *
#from secret import flag
'''
p = getPrime(25)
e = # Hidden
q = getPrime(25)
n = p * q
m = bytes_to_long(flag.strip(b"npuctf{").strip(b"}"))

c = pow(m, e, n)
print(c)
print(pow(2, e, n))
print(pow(4, e, n))
print(pow(8, e, n))

'''
c = 169169912654178
c1 = 128509160179202
c2 = 518818742414340
c3 = 358553002064450
m1 = 2
m2 = 4
m3 = 8

n = gcd(pow(c1,2)-c2,c1*c2-c3)
#1054494004042394<16> = 2 · 18195301 · 28977097

e = discrete_log(n//2,c1,2)

p = 18195301
q = 28977097
phi = (q-1) * (p-1)
d = invert(e,phi)
m = pow(c,int(d),int(n//2))

print(long_to_bytes(m))

已知c、e、p、q

但是，由于不互素，所以按常规求不出d

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
from gmpy2 import *
from Crypto.Util.number import *
from tqdm import tqdm
def onemod(p,r):
    t = p-2
    while pow(t, (p-1) // r, p) == 1: t -= 1
    return pow(t, (p-1) // r, p)
def solution(p,root): 
    g = onemod(p, 0x1337)
    may = []
    for i in range(0x1337):
        if i % 100 == 0:
            print(i)
        may.append(root * pow(g,i,p) % p)
    return may
c = 10562302690541901187975815594605242014385201583329309191736952454310803387032252007244962585846519762051885640856082157060593829013572592812958261432327975138581784360302599265408134332094134880789013207382277849503344042487389850373487656200657856862096900860792273206447552132458430989534820256156021128891296387414689693952047302604774923411425863612316726417214819110981605912408620996068520823370069362751149060142640529571400977787330956486849449005402750224992048562898004309319577192693315658275912449198365737965570035264841782399978307388920681068646219895287752359564029778568376881425070363592696751183359
p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059
q = 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741
e = 0x1337
n = p * q
c_p = pow(c, (1 + 3307 * (p - 1) // e) // e, p)
C1 = solution(p, c_p)
c_q = pow(c, (1 + (2649 * (q - 1) // e)) // e, q)
C2 = solution(q, c_q)
a = invert(p, q)
b = invert(q, p)
flag=0
for i in tqdm(C1):
    for j in tqdm(C2):
        flag += 1
        if flag % 1000000 == 0:
            print(flag)
        x = (b * q * i + a * p * j) % n
        if b"NCTF{" in long_to_bytes(x):
            print(long_to_bytes(x))
            exit()