0x01 题目：babyrsa

image-20221104093333709

附件📎：

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

m = bytes_to_long(flag)
p = libnum.generate_prime(1024)
q = gmpy2.next_prime(p)
e = 0x10001
n = p * q
phi=(p-1)*(q-1)
c=pow(m,e,n)
print("phi =",phi)
print("c =",c)
# phi = 11998145197184838105291668748328177280207361667546370722759758550200386112478801305683579153942751165452647656673385449297455560085865712968985383490367475984832103238596934094135353170257339614559178443729484992289380330326343473326373076256926770972074683466001586625109364413771716300886242679064050279982192814946404692347546718488456485946902248120569680365122714051066115263800073280766317934165938044443605816890762489369759667593014079143278938847700684310154017484382180324831332527966465023501690149664921975200082428884572496102388046780321762496321487913829155767534947229165886644311869593584303424397016
# c = 5664235030100231880171042228110930207351619841860785495929861788749956436657598539033166266920085041056539484368799525891006461921744810454002229224070342640529484554920046100814190479604751667796353636578589439575896923937945959721385425716210546145718343511555866077148390467362495462929359632111674082222918151696522137240478900570056689827712787018876034334301771868147820786419006234529563416734953393480238739362002713175495890402512002469332947145115452344040709333447223824491510840788018172189866931550385951940611161143400804317944263940630025758568750312753125034413169961147691163044924934280636235493483

0x0101 解题

分析题目可以看到p的生成使用了next_prime()，

说明$q$可以看成$q = p + \varepsilon$ ，其中$\varepsilon$可以看成一个已知常数。

题目给出了phi，而且p和q非常接近，可以通过

1
prevprime(gmpy2.iroot(phi,2)[0])

直接算出p

所以解题脚本如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
import gmpy2
from sympy import nextprime, prevprime

phi = 11998145197184838105291668748328177280207361667546370722759758550200386112478801305683579153942751165452647656673385449297455560085865712968985383490367475984832103238596934094135353170257339614559178443729484992289380330326343473326373076256926770972074683466001586625109364413771716300886242679064050279982192814946404692347546718488456485946902248120569680365122714051066115263800073280766317934165938044443605816890762489369759667593014079143278938847700684310154017484382180324831332527966465023501690149664921975200082428884572496102388046780321762496321487913829155767534947229165886644311869593584303424397016
c = 5664235030100231880171042228110930207351619841860785495929861788749956436657598539033166266920085041056539484368799525891006461921744810454002229224070342640529484554920046100814190479604751667796353636578589439575896923937945959721385425716210546145718343511555866077148390467362495462929359632111674082222918151696522137240478900570056689827712787018876034334301771868147820786419006234529563416734953393480238739362002713175495890402512002469332947145115452344040709333447223824491510840788018172189866931550385951940611161143400804317944263940630025758568750312753125034413169961147691163044924934280636235493483
e = 0x10001
p=prevprime(gmpy2.iroot(phi,2)[0])
q=nextprime(p)
n=p*q
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
long_to_bytes(m)
1
b'blueshark{ISctf_i4_interest1ng}'

0x02 题目：ezcry

image-20221104094114635

附件📎：

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
from Crypto.Util.number import *
import gmpy2
from flag import flag
m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
s = getPrime(128)
k = getPrime(128)
n = p * q
e = 65537
seek1 = p*s
seek2 = q*k
seek3 = s*k
c = pow(m,e,n)
print(n)
print(seek1)
print(seek2)
print(seek3)
print(c)
"""
17034526359906374675222899048129793386473729727961851733668266173715506273934226618903915327347680201386438684211280871430960401386916021458749533875225149368757915582850037170031336862864220965224712317292408675261654733853726119671544885158743864358155418727967683788352892259519172776767011253307992508658787036093010953540438865556151687132667690293590304094069132122821611257522409132491206241878258953750975043892338280574703622715614385904469190033441247428911800257097240824225432194243602777112774675510936575635571170740329720227162079500469956310746873132644419840611848333802207608652869080821316814006039
31064534580137722018723185060822560614595271317101024671103834301982025703308358280617670492170754990183711198694392500995348706299728134379707212369534471489902209545060592051514886997951859233729914969365008090709174580598044945031296428531946547802954873288796478626936584991410702713951383782424003825610226728036611739090258953115031673157531
24213197274140919663950771475506320265583015671558310318006684746019240494812396672068641326932339831508586851960432536051863105773343184877340119017546817780287117748145293115469964769795237573829418533841547969451268532899237529671580701722254679851009751345719473395857872899046537572034595080443184983155696803469587776652323407147950333716539
44155715757886274586781970607943060213741487009882893164192666734219021562031
6636871845889289821451339461667353441602430792099749101933216934629214305159040913567522609116395485018234259025910227221402350884391969711051377864656945164699379734982178962637190192088596776288873871651609167259167456816094141938735498585327839045360319836147041837569528592447701501104067430848582239927052031661696213986982946173792468753773505681630323945625892041031455025095934790620541499679023777086690062211807019645557781380979957862910047981754126193036968611612056475750787560328372643151874535031184052794483578557248028165948247504989100884012688908781349748818365779371062209169311607720595792421590
"""

0x0201 解题

从题目所给的三个seek可以首先得出k和s:

1
2
k = gmpy2.gcd(seek2,seek3)
s = gmpy2.gcd(seek1,seek3)

再通过seek1和seek2可以得出p和q

1
2
p = seek1//s
q = seek2//k

最后就是常规解法，所以最后解题脚本：

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 *
import gmpy2
n = 17034526359906374675222899048129793386473729727961851733668266173715506273934226618903915327347680201386438684211280871430960401386916021458749533875225149368757915582850037170031336862864220965224712317292408675261654733853726119671544885158743864358155418727967683788352892259519172776767011253307992508658787036093010953540438865556151687132667690293590304094069132122821611257522409132491206241878258953750975043892338280574703622715614385904469190033441247428911800257097240824225432194243602777112774675510936575635571170740329720227162079500469956310746873132644419840611848333802207608652869080821316814006039
seek1 = 31064534580137722018723185060822560614595271317101024671103834301982025703308358280617670492170754990183711198694392500995348706299728134379707212369534471489902209545060592051514886997951859233729914969365008090709174580598044945031296428531946547802954873288796478626936584991410702713951383782424003825610226728036611739090258953115031673157531
seek2 = 24213197274140919663950771475506320265583015671558310318006684746019240494812396672068641326932339831508586851960432536051863105773343184877340119017546817780287117748145293115469964769795237573829418533841547969451268532899237529671580701722254679851009751345719473395857872899046537572034595080443184983155696803469587776652323407147950333716539
seek3 = 44155715757886274586781970607943060213741487009882893164192666734219021562031
c = 6636871845889289821451339461667353441602430792099749101933216934629214305159040913567522609116395485018234259025910227221402350884391969711051377864656945164699379734982178962637190192088596776288873871651609167259167456816094141938735498585327839045360319836147041837569528592447701501104067430848582239927052031661696213986982946173792468753773505681630323945625892041031455025095934790620541499679023777086690062211807019645557781380979957862910047981754126193036968611612056475750787560328372643151874535031184052794483578557248028165948247504989100884012688908781349748818365779371062209169311607720595792421590
e = 65537
k = gmpy2.gcd(seek2,seek3)
s = gmpy2.gcd(seek1,seek3)
# print(f"k = {k}")
# print(f"s = {s}")
assert isPrime(s) and isPrime(k) and seek3 == s*k
p = seek1//s
q = seek2//k
# print(f"p = {p}")
# print(f"q = {q}")
phi = (q-1)*(p-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
long_to_bytes(m)
1
b'ISCTF{iiii|||yesyes||7777}'

0x03 题目：ezRSA

image-20221104094507246

附件📎：

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

flag="ISCTF{************}"
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)
'''
146061540583135242741006647792481468215928177245453689591382075771990192360040412020479342624228118794110240955451899373848827328177557126556072570082923983968091404980923313006963667391261364191537502509633623502033578910844508808321175673461956149400289968262858691371016246515264343715246136003074155184273
106988826778655284666865642844938578070029566283623778317110345394696520999319699165122638213405544697509248818119744714371964212582672270467711234178627339558783803718844973937701655329775612593193896887658613019039808270266901149871250769922857432588126510259997039777751047281603319139760808677732919216899
740
6282526058961246581872664236584053247822096703448673698014149841099601111078858783085447440545491467659016466697346055841162217815656467685468263870813754625318960798390457353869689600971254126026498299128586642169553158659216998193596000256435504143502966206895545701691216757482393700125791878031903647831939512035110314068235625347074791191183719857770670134500097347113475463330210378392860796906074883251200522628116993249459465350593837432195675595929482809838619649519612607292091411530134831844063986714485104831320923176335931609571205307034732956741442770883207107022828296237748601658720079333177460160664
'''

0x0301 解题

简单分析一下题目中的循环：

1
2
3
4
5
6
7
8
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

可以得出以下结论：

  1. $e$不一定为素数
  2. $e$和$\phi$一定不互素
  3. $e$和$\phi$的最大公因数为t，且t可以直接求出来

由RSA公式可知$e$和$\phi$需要互为素数才可以求出$d$，所以需要先求出t进行计算
只是最后得出的$m$需要对t进行开方
解题脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
p = 146061540583135242741006647792481468215928177245453689591382075771990192360040412020479342624228118794110240955451899373848827328177557126556072570082923983968091404980923313006963667391261364191537502509633623502033578910844508808321175673461956149400289968262858691371016246515264343715246136003074155184273
q = 106988826778655284666865642844938578070029566283623778317110345394696520999319699165122638213405544697509248818119744714371964212582672270467711234178627339558783803718844973937701655329775612593193896887658613019039808270266901149871250769922857432588126510259997039777751047281603319139760808677732919216899
e = 740
c = 6282526058961246581872664236584053247822096703448673698014149841099601111078858783085447440545491467659016466697346055841162217815656467685468263870813754625318960798390457353869689600971254126026498299128586642169553158659216998193596000256435504143502966206895545701691216757482393700125791878031903647831939512035110314068235625347074791191183719857770670134500097347113475463330210378392860796906074883251200522628116993249459465350593837432195675595929482809838619649519612607292091411530134831844063986714485104831320923176335931609571205307034732956741442770883207107022828296237748601658720079333177460160664
from Crypto.Util.number import *
import gmpy2
phi = (p-1)*(q-1)
n = p*q
t = gmpy2.gcd(e,phi)
print(f"t = {t}")

d = inverse(e//t,phi)
m = pow(c, d, n)
plaintext = gmpy2.iroot(m, t)[0]
plaintext = long_to_bytes(plaintext)
print(plaintext)
1
2
t = 4
b'ISCTF{1dedc976-d253-4053-b2f5-557282f41fc5}'