冲就完事

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都没有范围到底应该怎么求呢?

y316+(((ymodx)5modxmody)2019)+y+1xy^{316} + \left(\left(\left(y\bmod{x}\right)^{5}\bmod{x\bmod{y}}\right)^{2019}\right) + \frac{y + 1}{x}

本题的突破口就再确定范围上,我们知道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>BA > B,且AA是一个素数,那么

1=(A1)!modA=(A1)(A2)(B+1)(B)1modA=(A1)(B+1)×B!modA\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}

然后我们相当于取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不互素

QQ截图20200413024342.jpg

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}'

V&N2020 easy_RSA

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
# import primefac
n = 7941371739956577280160664419383740967516918938781306610817149744988379280561359039016508679365806108722198157199058807892703837558280678711420411242914059658055366348123106473335186505617418956630780649894945233345985279471106888635177256011468979083320605103256178446993230320443790240285158260236926519042413378204298514714890725325831769281505530787739922007367026883959544239568886349070557272869042275528961483412544495589811933856131557221673534170105409
p = 102634610559478918970860957918259981057327949366949344137104804864768237961662136189827166317524151288799657758536256924609797810164397005081733039415393
d = 7515987842794170949444517202158067021118454558360145030399453487603693522695746732547224100845570119375977629070702308991221388721952258969752305904378724402002545947182529859604584400048983091861594720299791743887521228492714135449584003054386457751933095902983841246048952155097668245322664318518861440
cipher = 1618155233923718966393124032999431934705026408748451436388483012584983753140040289666712916510617403356206112730613485227084128314043665913357106301736817062412927135716281544348612150328867226515184078966397180771624148797528036548243343316501503364783092550480439749404301122277056732857399413805293899249313045684662146333448668209567898831091274930053147799756622844119463942087160062353526056879436998061803187343431081504474584816590199768034450005448200
e = 0x10001

import gmpy2
q = gmpy2.invert(d, p*p)

k = 1
while True:
tmp = gmpy2.iroot(q + k * p * p, 2)
if tmp[1] == True:
q = tmp[0]
break
else: k += 1

r = n // q // p
phin = (r - 1) * (q - 1) * (p - 1)
d = gmpy2.invert(e, phin)
c = pow(cipher, d, n)


def modular_sqrt(a, p):
""" Find a quadratic residue (mod p) of 'a'. p
must be an odd prime.

Solve the congruence of the form:
x^2 = a (mod p)
And returns x. Note that p - x is also a root.

0 is returned is no square root exists for
these a and p.

The Tonelli-Shanks algorithm is used (except
for some simple cases in which the solution
is known from an identity). This algorithm
runs in polynomial time (unless the
generalized Riemann hypothesis is false).
"""
# Simple cases
#
if legendre_symbol(a, p) != 1:
return 0
elif a == 0:
return 0
elif p == 2:
return 0
elif p % 4 == 3:
return pow(a, (p + 1) // 4, p)

# Partition p-1 to s * 2^e for an odd s (i.e.
# reduce all the powers of 2 from p-1)
#
s = p - 1
e = 0
while s % 2 == 0:
s //= 2
e += 1

# Find some 'n' with a legendre symbol n|p = -1.
# Shouldn't take long.
#
n = 2
while legendre_symbol(n, p) != -1:
n += 1

# Here be dragons!
# Read the paper "Square roots from 1; 24, 51,
# 10 to Dan Shanks" by Ezra Brown for more
# information
#

# x is a guess of the square root that gets better
# with each iteration.
# b is the "fudge factor" - by how much we're off
# with the guess. The invariant x^2 = ab (mod p)
# is maintained throughout the loop.
# g is used for successive powers of n to update
# both a and b
# r is the exponent - decreases with each update
#
x = pow(a, (s + 1) // 2, p)
b = pow(a, s, p)
g = pow(n, s, p)
r = e

while True:
t = b
m = 0
for m in range(r):
if t == 1:
break
t = pow(t, 2, p)

if m == 0:
return x

gs = pow(g, 2 ** (r - m - 1), p)
g = (gs * gs) % p
x = (x * gs) % p
b = (b * g) % p
r = m


def legendre_symbol(a, p):
""" Compute the Legendre symbol a|p using
Euler's criterion. p is a prime, a is
relatively prime to p (if p divides
a, then a|p = 0)

Returns 1 if a has a square root modulo
p, -1 otherwise.
"""
ls = pow(a, (p - 1) // 2, p)
return -1 if ls == p - 1 else ls

from Crypto.Util.number import long_to_bytes
m = modular_sqrt(c, r)
print((m**2-c)//k)
>>> 'flag{fd462593-25e4-4631-a96a-0cd5c72b2d1b}'

# k = 0
# while True:
# m = gmpy2.iroot(c + k * r, 2)
# if m[1] == True:
# print(m[0])
# break
# else: k += 1

WUSTCTF babyrsa

1
b'wctf2020{just_@_piece_0f_cak3}'

WUSTCTF dp

详见RSA2,dp泄露

1
b'wctf2020{dp_leaking_1s_very_d@angerous}'

AFCTF2018 Tiny LFSR

我们需要注意到给出的条件有一组明文和密文,使用了lfsr生成了密钥流加密了后后半段.由前半段密文与明文再异或可以知道key的值.随后问题变为知道初始状态和密码机求下一位的事情,所以我们复制代码即可

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
c = open('cipher.txt','rb').read().hex()
# print(c)
key = bytearray()
m = open('Plain.txt','r').read()
for i in range(8):
key += (int(c[2*i:2*(i+1)],16)^ord(m[i])).to_bytes(1,'big')

# key = key.hex()
# a = ''.join([chr(int(b, 16)) for b in [key[i:i+2] for i in range(0, len(key), 2)]])
print(key)
flag_en = open('flag_encode.txt','rb').read()
print(str(flag_en))
for i in range(8):
print(chr(flag_en[i]^key[i]),end='')

mask = 0b1101100000000000000000000000000000000000000000000000000000000000

def lfsr(R, mask):
output = (R << 1) & 0xffffffffffffffff
i=(R&mask)&0xffffffffffffffff
lastbit=0
while i!=0:
lastbit^=(i&1)
i=i>>1
output^=lastbit
return (output,lastbit)
R = int(key.hex(),16)
lent = len(flag_en)
for i in range(len(a), lent):
tmp=0
for j in range(8):
(R,out)=lfsr(R,mask)
tmp=(tmp << 1)^out
print(chr(tmp^flag_en[i]),end='')

得到flag

image-20200503212731412

评论