nssctf
[RSA1]P1
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
from Crypto.Util.number import inverse,long_to_bytes
'''
flag = b'NSSCTF{******}'
p = getPrime(512)
q = getPrime(512)
n = p*q
e = 65537
phi = (p-1)*(q-1)
m = bytes_to_long(flag)
c = pow(m, e, n)
print(f'p = {p}')
print(f'q = {q}')
print(f'e = {e}')
print(f'c = {c}')
'''
p = 10554915510546378513140074459658086644656654144905337809416976066414771647836950941616441505897207397834928781511863699153349798682451297889979721668885951
q = 8246403321715011123191410826902524505032643184038566851264109473851746507405534573077909160292816825514872584170252311902322051822644609979417178306809223
e = 65537
c = 40005881669517895877352756665523238535105922590962714344556374248977905431683140065629966778249773228248201807844489945346731806741025157651474530811920115794270396320935022110691338083709019538562205165553541077855422953438117902279834449006455379382431883650004540282758907332683496655914597029545677184720
phi=(p-1)*(q-1)
d = inverse(e,phi)
n=p*q
m = pow(c,d,n)
flag = long_to_bytes(m)
print(flag)
常规RSA解法:
- 由
p,q求n和欧拉函数phi - 由
e,phi求逆元d - 由
c,d,n求m - 整数
m转为字节流
[RSA1]P2
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
from Crypto.Util.number import inverse,long_to_bytes
'''
flag = b'NSSCTF{******}'
p = getPrime(256)
q = getPrime(256)
n = p*q
e = 65537
phi = (p-1)*(q-1)
m = bytes_to_long(flag)
c = pow(m, e, n)
print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')
'''
n = 7382582015733895208810490097582153009797420348201515356767397357174775587237553842395468027650317457503579404097373070312978350435795210286224491315941881
e = 65537
c = 6511001389892474870028836129813814173158254564777610289284056550272120510686249909340499673868720839756059423749304765055919251717618117507007046973023557
p=70538125404512947763739093348083497980212021962975762144416432920656660487657
q=104660876276442216612517835199819767034152013287345576481899196023866133215633
phi=(p-1)*(q-1)
d = inverse(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))
n可分解:
- 用factordb或
yafu分解n得到p,q - 常规RSA解法
[RSA1]P3
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
from Crypto.Util.number import inverse,long_to_bytes
flag = b'NSSCTF{******}'
'''
p = getPrime(128)
q = getPrime(128)
n = p*q
e = 65537
phi = (p-1)*(q-1)
m = bytes_to_long(flag)
c = pow(m, e, n)
print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')
'''
n = 53690629441472827148854210396580805205350972614395425306316047967905824330731
e = 65537
c = 22130296334673852790451396673112575082637108306697684532954477845025885087040
p=193584665240506752994134779660255197091
q=277349599849597463956171076348973750041
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))
n可分解
[RSA1]P4
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
from Crypto.Util.number import inverse,long_to_bytes
from gmpy2 import isqrt,next_prime
'''
flag = b'NSSCTF{******}'
p = getPrime(512)
q = gmpy2.next_prime(p)
n = p*q
e = 65537
phi = (p-1)*(q-1)
m = bytes_to_long(flag)
c = pow(m, e, n)
print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')
'''
n = 115637000420176820831322601039129424406844427046456738651883381559357542765613732363445112111006849040385859313572091386802534464534403117787314180179562651607533039692795522388596550968316951090748054495960090527479954143448774136390568881020918710834542819900918984139672802889774720153267841255456602500057
e = 65537
c = 98161406745910866780822530171878255235776133393411573803496865047700715941955255328757920065032397556905095591171977170479344602512244671081108703687450560269408412671849929423399172588599903975793985819498354819305128607934552101433664794909855378636055525016664559476808490723554481335856183927702549281730
sn=isqrt(n)
q=next_prime(sn)
p=n//q
phi=(p-1)*(q-1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
p,q接近
- $n = p \times q$
- $\text{sn} = \sqrt[e]{n}$
- $q = \mathrm{next\_prime}(p)$
- $p = \left\lfloor \frac{n}{q} \right\rfloor$
- 常规RSA解法