冲就完事

Alice 和 Bobs

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

def isprime(n):
if n < 2:
return False
for i in range(2, int(math.sqrt(n))+1):
if n % i == 0:
return False
return True

number = 98554799767

for i in range(2, int(math.sqrt(number))+1):
if isprime(i):
if (number % i) == 0:
print(i,(int)(number/i))
>>>101999 966233

随后md5加密,得到 flag{d450209323a847c8d01c6be47c81811a}

Windows系统密码

Win系统的用户密码存储于C:\windows\system32\config\sam文件中,其中每行第三项是经过不可逆加密算法处理的Hash散列

MD5查询随后得到 flag{good-luck}

Old-fashion

替换密码解密网站

词频分析,随后找到keyword 对应并解密即可 flag{n1_2hen-d3_hu1-mi-ma_a}

异性相吸

1
2
3
4
5
6
7
key = open('Key.txt').read()
se = open('密文.txt').read()
flag = ''
for i in range(0, len(key)):
res = ord(list(se)[i]) ^ ord(list(key)[i])
flag = flag + chr(res)
print(flag)

rsa

1
2
3
4
5
6
>>> import gmpy2
>>> p = 473398607161
>>> q = 4511491
>>> e = 17
>>> print(gmpy2.invert(e, (p - 1) * (q - 1)))
125631357777427553

rsa0

nc一下你就知道

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import gmpy2
import socket
import gmpy2 as gmpy
from gmpy2 import mpz

# p+q = 19535108824686079298103430130639174145750230041916262263097212225311599247760201261496470477474464945873279929563828744134641334704537928436540586277098798
# p-q = 1715377243199240625359611797930181825764380022390422741836451657422141114569571440576855806625836750331155657808084343603681367211016316104120143037141744

tmp1 = 1953510882
tmp2 = 1715377243199240625359611797930181825764380022390422741836451657422141114569571440576855806625836750331155657808084343603681367211016316104120143037141744
c = 88919324565
e = 11725463
p = (tmp1 + tmp2) // 2
q = tmp1 - p
n = q * p
phi = (p - 1) * (q - 1)
d = int(gmpy2.invert(e, phi))
m = pow(c, d, n)
print(long_to_bytes(m))

rsa1

二元二次方程不说了把, 不过每次访问会给出新的e与c也可以采用共模攻击

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import gmpy2 as gmpy
from math import sqrt
from Crypto.Util.number import long_to_bytes
# p ^ 2+q ^ 2 = 261250950113940115263931339089739723002301595229279628454068575459510387873043884246182160831686503970390747401190437785493781420012414953552269534344997442525413827300160424799311521957708663779882738461087444076834019460757570934436554114907216921679971452882218749840839513177750266588810994177422744732090
# p-q = 3979121538048563322124057457898863457414028819475426236369426354782533221385721015683207277210128225428081267873508998914802091170259302823612435298130156
tmp1 = 261250950113
tmp2 = 397912153
c = 1073488623
e = 14579417
n = -(tmp2 * tmp2 - tmp1) // 2
tmp3 = tmp1 + 2 * n
tmp1 = gmpy.iroot(tmp3, 2)[0] # p + q
q = (tmp2 + tmp1) // 2
p = n // q

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

rsa2

补充()方向过程

所以我们采用wienerAttack, 工具链接 : https://github.com/pablocelayes/rsa-wiener-attack

1
2
3
4
5
6
7
8
9
import hashlib
import RSAwienerHacker

N = 101991809
e = 46731919563

d = RSAwienerHacker.hack_RSA(e, N)
flag = "flag{" + hashlib.md5(hex(d).encode('utf-8')).hexdigest() + "}"
print(flag)

rsarsa

1
2
3
4
5
6
7
8
9
10
import gmpy2 as gmpy
import binascii

p = 96484230
q = 1187484383
e = 65537
c = 832082989
d = gmpy.invert(e, (p - 1) * (q - 1))
m = pow(c, d, p * q)
print(m)

RSA

几个点,从文件读取(推荐使用这个库)和需要发现模数n不大可以分解,从而得到flag

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 long_to_bytes
from factordb.factordb import FactorDB
from Crypto.PublicKey import RSA
import gmpy2 as gmpy
import binascii
with open('pub.key', 'r') as f:
key = RSA.importKey(f.read())
n = key.n
e = key.e
f = FactorDB(n)
f.connect()
factors = f.get_factor_list()
q = factors[0]
p = factors[1]
d = gmpy.invert(e, (p - 1) * (q - 1))
with open('flag.enc', 'rb') as f:
c = bytes.hex(f.read())
c = int(c, 16)
m = pow(c, d, n)
print(long_to_bytes(m))
>>>b'\x02\x9d {zR\x1e\x08\xe4\xe6\x18\x06\x00flag{decrypt_256}\n'

RSA1

dp,dq泄露,参考我rsa那篇文章,有详细证明.以下直接给出代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import gmpy2 as gmpy
import binascii
p = 863763376
q = 126406749
dp = 65007957022
dq = 78347226367
c = 2472230540388
m1 = pow(c, dp, p)
m2 = pow(c, dq, q)
qinv = gmpy.invert(q, p)
h = (qinv * (m1 - m2)) % p
m = m2 + h * q
m = hex(m)[2:]
print(binascii.unhexlify(m))

RSA2

dp泄露,那边文章同样有分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
import gmpy2
from Crypto.Util.number import long_to_bytes
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751
for i in range(1, e):
if (e * dp - 1) % i == 0:
p = (e * dp - 1) // i + 1
if n % p == 0:
q = n // p
phin = (p - 1) * (q - 1)
d = gmpy2.invert(e, phin)
print(long_to_bytes(pow(c, d, n)))
break
>>> b'flag{wow_leaking_dp_breaks_rsa?_98924743502}'

RSA3

同一个n,两个密文两个公钥,猜测共模攻击,使用gmpy自带的扩展欧几里得函数就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import gmpy2 as gmpy
import binascii

n = 227080788158850..
c1 = 22322035275663..
e1 = 11187289
c2 = 18702010045187..
e2 = 9647291

gcd, s, t = gmpy.gcdext(e1, e2)
m = pow(c1, s, n) * pow(c2, t, n) % n
m = hex(m)[2:]
print(binascii.unhexlify(m))
>>> b'flag{49d91077a1abcb14f1a9d546c80be9ef}'

RSA4

一开始发现没有公钥??猜测采用同一个公钥加密,于是有以下公式

c1memodn1c2memodn2c3memodn3\begin{array}{l} c_{1} \equiv m^{e} \bmod n_{1} \\ c_{2} \equiv m^{e} \bmod n_{2} \\ c_{3} \equiv m^{e} \bmod n_{3} \end{array}

我们用剩余定理求解mem^{e}就好了,不过坑人的是,它不是10进制!!第一次求解报错了ZeroDivisionError: invert() no inverse exists

所以先转换一下

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
import gmpy2 as gmpy
from Crypto.Util.number import long_to_bytes
N1 = 33131032...
c1 = 31002000...

N2 = 30224000...
c2 = 112200203...

N3 = 3322003...
c3 = 10013444..

N1 = int(str(N1),5)
N2 = int(str(N2), 5)
N3 = int(str(N3), 5)
c1 = int(str(c1),5)
c2 = int(str(c2), 5)
c3 = int(str(c3), 5)


mlist = [N1, N2, N3]
blist = [c1, c2, c3]

def crt(blist, mlist):
m = 1
for i in mlist:
m *= i
ans = 0
for i in range(0, len(mlist)):
Mi = m // mlist[i]
try:
ans += (blist[i] * Mi * gmpy.invert(Mi, mlist[i])) % m
except:
print("Error!")
return False
return ans % m
me = crt()
for i in range(2, 10000):
result = gmpy.iroot(me, i)
if result[1] == True:
print(i, long_to_bytes(result[0]))
>>> 3 b'noxCTF{D4mn_y0u_h4s74d_wh47_4_b100dy_b4s74rd!}'

RSA5

这题吧…有点点意思

看到这么多的n,就应该考虑到模不互素的问题,关键是找出那两个不互素…

来一个double 循环就行啦…虽然python循环很方便但有时候还是想念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
import gmpy2 as gmpy
from Crypto.Util.number import long_to_bytes
from factordb.factordb import FactorDB

# m = xxxxxxxx
e = 65537
# == == == == == n c == == == == ==
nlist = []
clist = []
with open('data.txt', 'r') as f:
for line in f:
# if 'c = ' in line or '\n' in line:
# continue
if 'n = ' in line:
nlist.append(line[4:-1])
if 'c = ' in line:
clist.append(line[4:-1])
n1 = n2 = ngcd = c = 0
for i in range(0, len(nlist)):
for j in range(i + 1, len(nlist)):
if (gmpy.gcd(int(nlist[i]), int(nlist[j])) != 1):
n1 = int(nlist[i])
n2 = nlist[j]
c = int(clist[i])
ngcd = gmpy.gcd(int(nlist[i]), int(nlist[j]))
q = n1 // ngcd
phin = (q - 1) * (ngcd - 1)
d = gmpy.invert(e, phin)
m = pow(c, d, n1)
print(long_to_bytes(m))

[Running] python -u "c:\Users\10179\Desktop\Tmp_file\1.py"
b'flag{abdcbe5fd94e23b3de429223ab9c2fdf}'
//flag到手, 爽!

Dangerous RSA

small public index related attck 跑跑跑🛫🛫

1
2
3
4
5
6
7
8
9
10
11
12
13
import gmpy2 as gmpy
from Crypto.Util.number import long_to_bytes
e = 0x3
n = 0x52d483c2...
c = 0x10652cdfa...
k = 0
while True:
if gmpy.iroot(c + k * n, 3)[1] == True:
m = gmpy.iroot(c + k * n, 3)[0]
print(long_to_bytes(m))
break
k += 1
>>> b'flag{25df8caf006ee5db94d48144c33b2c3b}'

basic rsa

有点水哈

1
2
3
4
5
6
7
8
9
10
11
12
import gmpy2
from Crypto.Util.number import *
from binascii import a2b_hex,b2a_hex
flag = "*****************"
p = 262248800182277040650192055439906580479
q = 262854994239322828547925595487519915551
e = 65533
n = p * q
c = 27565231154623519221597938803435789010285480123476977081867877272451638645710
d = gmpy2.invert(e, (p - 1) * (q - 1))
m = pow(c, d, n)
print(long_to_bytes(m))

bbbbbbrsa

第一点把题读懂,第二点判断e模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 as gmpy
import base64
from Crypto.Util.number import long_to_bytes

flag = "*****************"

p = 177077389675257695042507998165006460849
n = 37421829509887796274897162249367329400988647145613325367337968063341372726061
c = '==gMzYDNzIjMxUTNyIzNzIjMyYTM4MDM0gTMwEjNzgTM2UTN4cjNwIjN2QzM5ADMwIDNyMTO4UzM2cTM5kDN2MTOyUTO5YDM0czM3MjM'
c = base64.b64decode(c[::-1])
c = int(c)
q = n // p
phin = (p - 1) * (q - 1)
for e in range(0, 70001):
if (gmpy.gcd(e, phin) == 1):
d = gmpy.invert(e, phin)
m = pow(c, d, n)
m = long_to_bytes(m)
if 'flag' in str(m):
print(e, m)
break
>>> 51527 b'flag{rs4_1s_s1mpl3!#}'

BabyRSA

1
flag{cc7490e-78ab-11e9-b422-8ba97e5da1fd}

RSAROLL

开始盲猜给的数字为n,d,结果解密之后发现明文不对,猜测为n,e.随后考虑到n不大可以分解,即可得到答案

当然我把data.txt稍微改了改

1
2
3
4
5
6
24dfbd5
ae4e2b
abf5353
22b04624
1fa19eda
b4172a8 //很迷的数字
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import gmpy2 as gmpy
from factordb.factordb import FactorDB
n = 920139713
e = 19

f = FactorDB(n)
f.connect()
factors = f.get_factor_list()
q = factors[0]
p = factors[1]
d = gmpy.invert(e, (p - 1) * (q - 1))
with open('data.txt', 'r') as f:
for line in f:
if line == '\n':
continue
m = pow(int(line), d, n)
print(chr(int(hex(m)[2:], 16)), end='')
>>> flag{13212je2ue28fy71w8u87y31r78eu1e2}
exited with code=0 in 2.068 seconds

childRSA

两个方法

第一使用yafu分解

第二查看生成素数p,q的函数可以发现p - 1是光滑的,所以可以采用Pollard' p-1算法分解,其实我觉得考点在第二个??

NCTF babyRSA

捕获.PNG

分析出来是要我们求n,根据它的素数生成算法可以知道p,q挨得很近,且我们有如下公式

(p1)2<φ(n)<(q1)2(p-1)^{2}<\varphi(n)<(q-1)^{2}

那么我们把φ(n)\varphi(n)开方随后依次检验q和p的值即可

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 gmpy2 as gmpy
from Crypto.Util.number import long_to_bytes
from sympy import isprime

d = 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913
c = 5382723168073828110696168558294206681757991149022777821127563301413483223874527233300721180839298617076705685041174247415826157096583055069337393987892262764211225227035880754417457056723909135525244957935906902665679777101130111392780237502928656225705262431431953003520093932924375902111280077255205118217436744112064069429678632923259898627997145803892753989255615273140300021040654505901442787810653626524305706316663169341797205752938755590056568986738227803487467274114398257187962140796551136220532809687606867385639367743705527511680719955380746377631156468689844150878381460560990755652899449340045313521804
e = 65537

k = 1
kphi = e * d - 1
n = 0

while True:
if kphi % k == 0:
phi = kphi // k
q = gmpy.iroot(phi, 2)[0]
for i in range(q, q + 2000):
if phi % (i - 1) == 0:
p = phi // (i - 1) + 1
if isprime(p):
n = p * i
print(long_to_bytes(pow(c, d, n)))
exit()
k += 1
>>> b'NCTF{70u2_nn47h_14_v3ry_gOO0000000d}'

BJDCTF easyrsa

解方程

1
b'BJD{Advanced_mathematics_is_too_hard!!!}'

BJDCTF RSA

分析附件,可以发现假定了e小于100000,且给了明文’294’,可以爆破,随后取n与n’的公因数再反求p,q即可

1.PNG

1
b'BJD{p_is_common_divisor}'

RoarCTF RSA

这道题的操作就比较虚幻了😁.后来我总结为抓大头的方法(逃.

2.PNG

分析附件,发现这个公式,刚开始我想x,y,z都没有范围到底应该怎么求呢?

\begin{equation*}y^{316} + \left(\left(\left(y\bmod{x}\right)^{5}\bmod{x\bmod{y}}\right)^{2019}\right) + \frac{y + 1}{x}\end{equation*}

本题的突破口就再确定范围上,我们知道A是一个较大的整数,但是发现里面的2019次方很大pow(2,2019) > A == True,可以大胆推测(((y%x)**5)%(x%y))=1 or (((y%x)**5)%(x%y))=0,后面又有一个316次方相比与后面的分数还是太大,我们直接忽略掉那个分数尝试把A开316方根的到83

1
2
3
4
5
# for i in range(0, 1000):
# if pow(i, 316) > A:
# print(i)
# break
# y = 84 > A

随后我们在y依次减小和x依次增大的循环里面找到符合的x,y,最后我们得到了``x, y == 2, 83`

那我们继续,q,p分别取素数,我们分析大小可以发现p>xyz,p>zp > xyz, p > z,那么对NN也有N>xyzzN > xyz\cdot z,既然我们已经确定了x,y那么可以把z的范围也能求出来,我们尝试n // x // y再开方,得到了一个tmpz>ztmpz > z,那么知道在小于tmpztmpz的范围内找到那个真正的zz即可,代码如下

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
A = 268334...
n = 117930...
c = 419718...
e = 0x10001

y = gmpy2.iroot(A, 316)[0]
x = 0
def calc(x, y):
for j in range(y, 1, -1):
y = j
try:
for i in range(1, 100):
x = i
if ((((y % x) ** 5) % (x % y)) ** 2019 + y ** 316 + (y + 1) // x) == A:
return x, y
except:
pass
x, y = calc(x, y)
tmpz = gmpy2.iroot(n // x // y, 2)[0]

for i in range(tmpz, 1, -1):
q = gmpy2.next_prime(i)
if n % q == 0:
p = n // q
d = gmpy2.invert(e, (p - 1) * (q - 1))
m = pow(c, d, n)
print(long_to_bytes(m))
break
>>> b'RoarCTF{wm-l1l1ll1l1l1l111ll}'

所以总结下来就是寻找对式子影响最大的变量,随后确定范围遍历检查,进而得到确值

RoarCTF babyRSA

分析一下附件,可以发现下面这个生成算法有问题

QQ截图20200403221511.jpg

它的目的是求B!modaB!\bmod a的值,我们直接算BB的阶乘肯定爆了,那么如何求解B!B!的值呢

根据WilsonWilson定理,其中pp为素数

(p1)!1modp(p-1)!\equiv-1\bmod p

并且我们有 $A > B, A$是一个素数,那么

\begin{equation}\begin{aligned} -1 &=(A-1)!\bmod A \\ &=(A-1)(A-2) \cdots(B+1)(B)\cdots 1 \bmod A \\ &=(A-1)\cdots(B+1)\times B!\bmod A \end{aligned}\end{equation}

然后我们相当于取B!B!的逆元即可,代码如下:

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
import sympy
import random
from Crypto.Util.number import long_to_bytes
import gmpy2 as gmpy
import binascii

A1 = 21856963...
B1 = 21856963...
A2 = 16466113...
B2 = 16466113...
c = 757008830...
n = 85492663
e = 0x1001

def wilson(a, b):
result = 1
for i in range(b + 1, a):
result = result * i
result = result % a
return sympy.nextprime(gmpy.invert(-result, a) % a)

q = wilson(A1, B1)
p = wilson(A2, B2)

r = n // q // p
phin = (p - 1) * (q - 1) * (r - 1)
d = gmpy.invert(e, phin)
m = pow(c, d, n)
print(long_to_bytes(m))
>>> b'RoarCTF{wm-CongrAtu1ation4-1t4-ju4t-A-bAby-R4A}'

GWCTF BabyRSA

分析一下,flag被分为了两半,转数字组合为c1, c2.随后c1与c2再用公钥加密得到m1,m2

所以我们吧m1和m2解密后解一个二元三次方程就好了啊,不过怎么得到d呢.

这个其实用yafu分解一下就好了注意到它的素数生成算法中会导致|p - q|较小,其实可以直接开方,随后再用sympy.nextprime()得到一个接近的素数

1
2
3
4
5
6
7
8
9
10
11
flag1 = flag[:half]
flag2 = flag[half:]
F1 = bytes_to_long(flag1)
F2 = bytes_to_long(flag2)

c1 = F1 + F2
c2 = pow(F1, 3) + pow(F2, 3)
assert(c2 < N)

m1 = pow(c1, e, N)
m2 = pow(c2, e, N)

最后用sympy这个库解方程得到flag1与flag2

1
2
3
4
5
6
7
8
9
# 直接开方法
# n = gmpy2.iroot(N,2)[0]
# p = sympy.nextprime(n2)
# q = n // p
eq = [x + y - m1, x ** 3 + y ** 3 - m2]
result = nonlinsolve(eq, [x, y])
print(result)
>>> FiniteSet((1141553212031156130619789508463772513350070909, 1590956290598033029862556611630426044507841845)
>>> b'GWHT{f709e0e2cfe7e5' b'30ca8972959a1033b2}'

AFCTF 可怜的RSA

1
flag{R54_|5_$0_B0rin9}

De1CTF2019 babyrsa

考点: 低指数,n分解,eφe\varphi不互素

捕获.PNG

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
import gmpy2 as gmpy
from libnum import solve_crt
from Crypto.Util.number import long_to_bytes

n = [20129615352491765499340112943188317180548761597861300847305827141510465619670536844634558246439230371658836928103063432870245707180355907194284861510906071265352409579441048101084995923962148527097370705452070577098780246282820065573711015664291991372085157016901209114191068574208680397710042842835940428451949500607613634682684113208766694028789275748528254287705759528498986306494267817198340658241873024800336013946294891687591013414935237821291805123285905335762719823771647853378892868896078424572232934360940672962436849523915563328779942134504499568866135266628078485232098208237036724121481835035731201383423, 31221650155627849964466413749414700613823841060149524451234901677160009099014018926581094879840097248543411980533066831976617023676225625067854003317018794041723612556008471579060428898117790587991055681380408263382761841625714415879087478072771968160384909919958010983669368360788505288855946124159513118847747998656422521414980295212646675850690937883764000571667574381419144372824211798018586804674824564606122592483286575800685232128273820087791811663878057827386379787882962763290066072231248814920468264741654086011072638211075445447843691049847262485759393290853117072868406861840793895816215956869523289231421, 29944537515397953361520922774124192605524711306753835303703478890414163510777460559798334313021216389356251874917792007638299225821018849648520673813786772452822809546571129816310207232883239771324122884804993418958309460009406342872173189008449237959577469114158991202433476710581356243815713762802478454390273808377430685157110095496727966308001254107517967559384019734279861840997239176254236069001453544559786063915970071130087811123912044312219535513880663913831358790376650439083660611831156205113873793106880255882114422025746986403355066996567909581710647746463994280444700922867397754748628425967488232530303, 25703437855600135215185778453583925446912731661604054184163883272265503323016295700357253105301146726667897497435532579974951478354570415554221401778536104737296154316056314039449116386494323668483749833147800557403368489542273169489080222009368903993658498263905567516798684211462607069796613434661148186901892016282065916190920443378756167250809872483501712225782004396969996983057423942607174314132598421269169722518224478248836881076484639837343079324636997145199835034833367743079935361276149990997875905313642775214486046381368619638551892292787783137622261433528915269333426768947358552919740901860982679180791]
c = [19131432661217908470262338421299691998526157790583544156741981238822158563988520225986915234570037383888112724408392918113942721994125505014727545946133307329781747600302829588248042922635714391033431930411180545085316438084317927348705241927570432757892985091396044950085462429575440060652967253845041398399648442340042970814415571904057667028157512971079384601724816308078631844480110201787343583073815186771790477712040051157180318804422120472007636722063989315320863580631330647116993819777750684150950416298085261478841177681677867236865666207391847046483954029213495373613490690687473081930148461830425717614569, 15341898433226638235160072029875733826956799982958107910250055958334922460202554924743144122170018355117452459472017133614642242411479849369061482860570279863692425621526056862808425135267608544855833358314071200687340442512856575278712986641573012456729402660597339609443771145347181268285050728925993518704899005416187250003304581230701444705157412790787027926810710998646191467130550713600765898234392350153965811595060656753711278308005193370936296124790772689433773414703645703910742193898471800081321469055211709339846392500706523670145259024267858368216902176489814789679472227343363035428541915118378163012031, 18715065071648040017967211297231106538139985087685358555650567057715550586464814763683688299037897182845007578571401359061213777645114414642903077003568155508465819628553747173244235936586812445440095450755154357646737087071605811984163416590278352605433362327949048243722556262979909488202442530307505819371594747936223835233586945423522256938701002370646382097846105014981763307729234675737702252155130837154876831885888669150418885088089324534892506199724486783446267336789872782137895552509353583305880144947714110009893134162185382309992604435664777436197587312317224862723813510974493087450281755452428746194446, 2282284561224858293138480447463319262474918847630148770112472703128549032592187797289965592615199709857879008271766433462032328498580340968871260189669707518557157836592424973257334362931639831072584824103123486522582531666152363874396482744561758133655406410364442174983227005501860927820871260711861008830120617056883514525798709601744088135999465598338635794275123149165498933580159945032363880613524921913023341209439657145962332213468573402863796920571812418200814817086234262280338221161622789516829363805084715652121739036183264026120868756523770196284142271849879003202190966150390061195469351716819539183797]

p = gmpy.iroot(solve_crt(c, n), 4)[0]
ee1 = 42
ee2 = 3
ce1 = 45722651786340123946960815003059322528810481841378247280642868553607692149509126962872583037142461398806689489141741494974836882341505234255325683219092163052843461632338442529011502378931140356111756932712822516814023166068902569458299933391973504078898958921809723346229893913662577294963528318424676803942288386430172430880307619748186863890050113934573820505570928109017842647598266634344447182347849367714564686341871007505886728393751147033556889217604647355628557502208364412269944908011305064122941446516990168924709684092200183860653173856272384
ce2 = 13908468332333567158469136439932325992349696889129103935400760239319454409539725389747059213835238373047899198211128689374049729578146875309231962936554403287882999967840346216695208424582739777034261079550395918048421086843927009452479936045850799096750074359160775182238980989229190157551197830879877097703347301072427149474991803868325769967332356950863518504965486565464059770451458557744949735282131727956056279292800694203866167270268988437389945703117070604488999247750139568614939965885211276821987586882908159585863514561191905040244967655444219603287214405014887994238259270716355378069726760953320025828158
tmp = 864078778078609835167779565982540757684070450697854309005171742813414963447462554999012718960925081621571487444725528982424037419052194840720949809891134854871222612682162490991065015935449289960707882463387
n = 15911581555796798614711625288508309704791837516232122410440958830726078821069050404012820896260071751380436992710638364294658173571101596931605797509712839622479368850251206419748090059752427303611760004621378226431226983665746837779056271530181865648115862947527212787824629516204832313026456390047768174765687040950636530480549014401279054346098030395100387004111574278813749630986724706263655166289586230453975953773791945408589484679371854113457758157492241225180907090235116325034822993748409011554673180494306003272836905082473475046277554085737627846557240367696214081276345071055578169299060706794192776825039
# assert(pow(e1, ee1, n) == ce1)
# assert (pow(e2 + tmp, ee2, n) == ce2)
k = 0
while True:
if gmpy.iroot(ce2 + k * n, 3)[1] == True:
m = gmpy.iroot(ce2 + k * n, 3)[0]
e2 = m - tmp
break
k += 1
k = 0
while True:
if gmpy.iroot(ce1 + k * n, 42)[1] == True:
m = gmpy.iroot(ce1 + k * n, 42)[0]
e1 = m
break
k += 1

e = 46531
c = 14992132140996160330967307558503117255626925777426611978518339050671013041490724616892634911030918360867974894371539160853827180596100892180735770688723270765387697604426715670445270819626709364566478781273676115921657967761494619448095207169386364541164659123273236874649888236433399127407801843412677293516986398190165291102109310458304626261648346825196743539220198199366711858135271877662410355585767124059539217274691606825103355310348607611233052725805236763220343249873849646219850954945346791015858261715967952461021650307307454434510851869862964236227932964442289459508441345652423088404453536608812799355469
n2 = 16278524034278364842964386062476113517067911891699789991355982121084973951738324063305190630865511554888330215827724887964565979607808294168282995825864982603759381323048907814961279012375346497781046417204954101076457350988751188332353062731641153547102721113593787978587135707313755661153376485647168543680503160420091693269984008764444291289486805840439906620313162344057956594836197521501755378387944609246120662335790110901623740990451586621846212047950084207251595169141015645449217847180683357626383565631317253913942886396494396189837432429078251573229378917400841832190737518763297323901586866664595327850603
pn2 = 127587319253436643569312142058559706815497211661083866592534217079310497260365307426095661281103710042392775453866174657404985539066741684196020137840472950102380232067786400322600902938984916355631714439668326671310160916766472897536055371474076089779472372913037040153356437528808922911484049460342088835693
qn2 = 127587319253436643569312142058559706815497211661083866592534217079310497260365307426095661281103710042392775453866174657404985539066741684196020137840472950102380232067786400322600902938984916355631714439668326671310160916766472897536055371474076089779472372913037040153356437528808922911484049460342088834871
phin2 = (pn2 - 1) * (qn2 - 1)
dn2 = gmpy.invert(e, phin2)
hint = pow(c, dn2, n2)
# print(long_to_bytes(hint))
# >>> b'orz...you.found.me.but.sorry.no.hint...keep.on.and.enjoy.it!'
q1 = min(qn2, pn2)
q2 = 114401188227479584680884046151299704656920536168767132916589182357583461053336386996123783294932566567773695426689447410311969456458574731187512974868297092638677515283584994416382872450167046416573472658841627690987228528798356894803559278308702635288537653192098514966089168123710854679638671424978221959513
n1 = p * q1
n2 = p * q2
phin1 = (p - 1) * (q1 - 1)
phin2 = (p - 1) * (q2 - 1)

c1 = 262739975753930281690942784321252339035906196846340713237510382364557685379543498765074448825799342194332681181129770046075018122033421983227887719610112028230603166527303021036386350781414447347150383783816869784006598225583375458609586450854602862569022571672049158809874763812834044257419199631217527367046624888837755311215081173386523806086783266198390289097231168172692326653657393522561741947951887577156666663584249108899327053951891486355179939770150550995812478327735917006194574412518819299303783243886962455399783601229227718787081785391010424030509937403600351414176138124705168002288620664809270046124
c2 = 7395591129228876649030819616685821899204832684995757724924450812977470787822266387122334722132760470911599176362617225218345404468270014548817267727669872896838106451520392806497466576907063295603746660003188440170919490157250829308173310715318925771643105064882620746171266499859049038016902162599261409050907140823352990750298239508355767238575709803167676810456559665476121149766947851911064706646506705397091626648713684511780456955453552020460909638016134124590438425738826828694773960514221910109473941451471431637903182205738738109429736425025621308300895473186381826756650667842656050416299166317372707709596

gcd = gmpy.gcd(e1, e2)
a1 = e1 // gcd
a2 = e2 // gcd

bd1 = gmpy.invert(a1, phin1)
bd2 = gmpy.invert(a2, phin2)

m1 = pow(c1, bd1, n1)
m2 = pow(c2, bd2, n2)
c = solve_crt([m1, m1, m2], [p, q1, q2])
# print(c)
phin = (q1 - 1) * (q2 - 1)
d = gmpy.invert(7, phin)
n = q2 * q1
m = pow(c, d, n)
print(long_to_bytes(gmpy.iroot(m, 2)[0]))
>>> b'de1ctf{9b10a98b-71bb-4bdf-a6ff-f319943de21f}'

MRCTF Easy_RSA

捕获.PNG

考察了多个考点,其中对与gen_q,我们知道ed,ned,n可以求出p,q,算法如下

2020032923302471.png

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
import sympy
from gmpy2 import gcd, invert, iroot, is_odd
from random import randint
from Crypto.Util.number import getPrime, isPrime, getRandomNBitInteger, bytes_to_long, long_to_bytes
import base64

base = 65537


P_n = 14057332139537395701238463644827948204030576528558543283405966933509944444681257521108769303999679955371474546213196051386802936343092965202519504111238572269823072199039812208100301939365080328518578704076769147484922508482686658959347725753762078590928561862163337382463252361958145933210306431342748775024336556028267742021320891681762543660468484018686865891073110757394154024833552558863671537491089957038648328973790692356014778420333896705595252711514117478072828880198506187667924020260600124717243067420876363980538994101929437978668709128652587073901337310278665778299513763593234951137512120572797739181693
P_F_n = 14057332139537395701238463644827948204030576528558543283405966933509944444681257521108769303999679955371474546213196051386802936343092965202519504111238572269823072199039812208100301939365080328518578704076769147484922508482686658959347725753762078590928561862163337382463252361958145933210306431342748775024099427363967321110127562039879018616082926935567951378185280882426903064598376668106616694623540074057210432790309571018778281723710994930151635857933293394780142192586806292968028305922173313521186946635709194350912242693822450297748434301924950358561859804256788098033426537956252964976682327991427626735740
Q_n = 20714298338160449749545360743688018842877274054540852096459485283936802341271363766157976112525034004319938054034934880860956966585051684483662535780621673316774842614701726445870630109196016676725183412879870463432277629916669130494040403733295593655306104176367902352484367520262917943100467697540593925707162162616635533550262718808746254599456286578409187895171015796991910123804529825519519278388910483133813330902530160448972926096083990208243274548561238253002789474920730760001104048093295680593033327818821255300893423412192265814418546134015557579236219461780344469127987669565138930308525189944897421753947
Q_E_D = 100772079222298134586116156850742817855408127716962891929259868746672572602333918958075582671752493618259518286336122772703330183037221105058298653490794337885098499073583821832532798309513538383175233429533467348390389323225198805294950484802068148590902907221150968539067980432831310376368202773212266320112670699737501054831646286585142281419237572222713975646843555024731855688573834108711874406149540078253774349708158063055754932812675786123700768288048445326199880983717504538825498103789304873682191053050366806825802602658674268440844577955499368404019114913934477160428428662847012289516655310680119638600315228284298935201
Ciphertext = 40855937355228438525361161524441274634175356845950884889338630813182607485910094677909779126550263304194796000904384775495000943424070396334435810126536165332565417336797036611773382728344687175253081047586602838685027428292621557914514629024324794275772522013126464926990620140406412999485728750385876868115091735425577555027394033416643032644774339644654011686716639760512353355719065795222201167219831780961308225780478482467294410828543488412258764446494815238766185728454416691898859462532083437213793104823759147317613637881419787581920745151430394526712790608442960106537539121880514269830696341737507717448946962021

p, q = sympy.symbols('p, q')
eq = [p * q - P_n, (p - 1) * (q - 1) - P_F_n]
result = sympy.nonlinsolve(eq, [p, q])
p, q = list(result)[0]
assert (p < q)
factor2 = 2021 * p + 2020 * q
if factor2 < 0:
factor2 = (-1) * factor2
P = sympy.nextprime(factor2)

ed, n = Q_E_D, Q_n
f, s = ed - 1, 0
while True:
if f % pow(2, s) == 0:
t = f // pow(2, s)
if is_odd(t):
break
else: s += 1
i, a = s, 2
b = pow(a, t, n)
while b == 1:
a = sympy.nextprime(a)
b = pow(a, t, n)

while i != 1:
c = pow(b, 2, n)
if c != 1:
b = c
i -= 1
else: break

if b == n - 1:
a = sympy.nextprime(a)
b = pow(a, t, n)
while b == 1:
a = sympy.nextprime(a)
b = pow(a, t, n)
p = gcd(b - 1, n)
q = n // p
assert (p < q)
factor2 = 2021 * p - 2020 * q
if factor2 < 0:
factor2 = (-1) * factor2
Q = sympy.nextprime(factor2)
n = P * Q
phin = (P - 1) * (Q - 1)
d = invert(base, phin)
m = pow(Ciphertext, d, n)
print(long_to_bytes(m))
>>> b'MRCTF{Ju3t_@_31mp13_que3t10n}'

WUSTCTF dp

详见RSA2,dp泄露

1
b'wctf2020{dp_leaking_1s_very_d@angerous}'

评论




Blog content follows the Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) License

loading...loading... , total visits times