参考Kicky_Mu佬的学习ing

[ISG 2023]FakeRSA

考点：费马小定理

题面：

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
from Crypto.Util.number import *
#flag = b"ISG{***************************************************}"
m = bytes_to_long(flag)
p, q = getPrime(1024), getPrime(1024)
N = p * q
e = 0x10001

g = getRandomInteger(2048) % N
r_1 = getRandomInteger(2048) % N
r_2 = getRandomInteger(2048) % N
g_1 = pow(g, r_1*(p-1), N)
g_2 = pow(g, r_2*(q-1), N)
sk = g_1, g_2
s_1 = pow(2, r_1, N)
s_2 = pow(2, r_2, N)
c_1 = pow(m, e, N) * pow(g_1, s_1, N) % N
c_2 = pow(m, e, N) * pow(g_2, s_2, N) % N
with open("info_leak.txt", 'w') as f:
    f.write(f"N = {N}\n")
    f.write(f"e = {e}\n")
    f.write(f"c_1 = {c_1}\n")
    f.write(f"c_2 = {c_2}\n")
    f.write(f"g_1 = {g_1}\n")
    f.write(f"g_2 = {g_2}\n")
N = 19847620135822668847564514587942391948142624860181655735976934793142518668448318713906565631067926756575383231918008750320314318388342153000764317436938181753432239594989585637171839692228131563530710256600537628487979942994048525298362384704877859902808184444222096716564895401232578897723044129300645044323034052671774897679133209083253985051039010667384545090074079940175443302000660736565924866897854894975144801717146983216246279171532978445848360788240501229409058122640344180850723589598379999463896719432194098148150730453207196992264577662129500076382789140147725633949387830756940746588747464997105199040847
e = 65537
c_1 = 1756115882899235333767373412952685058442578502362305178148708348397221699382473322607024057374181363259992143822782466595632557188733429609610437516825340510258579461836830981981515610525669855890508880687879237365862600631017783112431782409053401059679909119087279725255362593628680270527043535327044114537521767844175613946742069798280407430255538431961464100994053843455293830848713979793641759592848965709164401923805202865181278248599013059304674374932785159449985020076949947804463531636632218338979436633344262978442310866256196263672451806491567851964985444336191269723675403138965510273692493690922361284742
c_2 = 2803882274464201632040310581340103954084366760475201812662337610119769672819960061278044921535221513068638607844358489732622395365341033774881175819904209471697333114522738668213960797378289175577854350822191156502389735396131609058051616247521510491333054934440476132327664414576125210514726048893532826553354112713412642050620661244235614627904861745988056133532835701882528265437296782174901011907579127296290336500125990526397809739665495288624623561555437259052010679639283282062401845887548408945917975559038856053229947588628662730086650236283183680761269321053645374046392192539882589660212309427186121150806
g_1 = 13683841336865841027652885569517449118992937497136804390789331098331105352858652504602625539672234430450616300504934856205064301811453804827917010475710699981014147946901465471877276000648012394735526065867450733647157768937302975684732550438551576742898866575823747069190609092224595543227133253510681145175984336182160164364554214802315164481578086371211804484783458365930147218337811369364850919070408100347945643554041867922429579033971970570060727603461691767890539331854786545982199998297298219754661137384625652128251904967127785945241854788060742454470903059115886397423042297289925395685450803460831897928252
g_2 = 1715827607770822027916388359002895605121557965635122390638079472658089153470011628164369842925275875967712538848782207398137721300785000148786237090186504979128222511965981575912913326516029139664053593759312951800545982648954917607038575718360849770282586139468386428432823626468085403220001310594753857986186494335432908855975879089482927309452461286290921871478006193072624494526500896055795364974923120807686893394782469634994819939396068806887992467663531650404341622534450045351363338604611403508251536208868099600795923830484553848138777019101735178671893852703652034757522746423826105891841738087294547994803

分析：

$$
g_1≡g^{r_1(p-1)}\ mod\ p\
g_2≡g^{r_2(p-1)}\ mod\ p\
$$

一眼丁真，用费马小定理，可以得到：
$$
g_1≡g^{r_1(p-1)}\ mod\ p≡1 \ mod\ p \
g_2≡g^{r_2(q-1)}\ mod\ q≡1 \ mod\ q\
$$
所以我们可以知道

gcd(g1-1,n)=p

gcd(g2-1,n)=q

再看密文的形式：
$$
c_1≡m^eg_1^s\ mod\ n\
c_2≡m^eg_2^s\ mod\ n\
$$
再次利用费马小定理可以得到
$$
c_1≡m^eg_1^s\ mod\ n≡m^e \ mod\ p\
c_2≡m^eg_2^s\ mod\ n≡m^e \ mod\ q\
$$
那么解密即为：
$$
m = c^{dp}\ mod\ p
$$

题解：

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

n = 19847620135822668847564514587942391948142624860181655735976934793142518668448318713906565631067926756575383231918008750320314318388342153000764317436938181753432239594989585637171839692228131563530710256600537628487979942994048525298362384704877859902808184444222096716564895401232578897723044129300645044323034052671774897679133209083253985051039010667384545090074079940175443302000660736565924866897854894975144801717146983216246279171532978445848360788240501229409058122640344180850723589598379999463896719432194098148150730453207196992264577662129500076382789140147725633949387830756940746588747464997105199040847
e = 65537
c_1 = 1756115882899235333767373412952685058442578502362305178148708348397221699382473322607024057374181363259992143822782466595632557188733429609610437516825340510258579461836830981981515610525669855890508880687879237365862600631017783112431782409053401059679909119087279725255362593628680270527043535327044114537521767844175613946742069798280407430255538431961464100994053843455293830848713979793641759592848965709164401923805202865181278248599013059304674374932785159449985020076949947804463531636632218338979436633344262978442310866256196263672451806491567851964985444336191269723675403138965510273692493690922361284742
c_2 = 2803882274464201632040310581340103954084366760475201812662337610119769672819960061278044921535221513068638607844358489732622395365341033774881175819904209471697333114522738668213960797378289175577854350822191156502389735396131609058051616247521510491333054934440476132327664414576125210514726048893532826553354112713412642050620661244235614627904861745988056133532835701882528265437296782174901011907579127296290336500125990526397809739665495288624623561555437259052010679639283282062401845887548408945917975559038856053229947588628662730086650236283183680761269321053645374046392192539882589660212309427186121150806
g_1 = 13683841336865841027652885569517449118992937497136804390789331098331105352858652504602625539672234430450616300504934856205064301811453804827917010475710699981014147946901465471877276000648012394735526065867450733647157768937302975684732550438551576742898866575823747069190609092224595543227133253510681145175984336182160164364554214802315164481578086371211804484783458365930147218337811369364850919070408100347945643554041867922429579033971970570060727603461691767890539331854786545982199998297298219754661137384625652128251904967127785945241854788060742454470903059115886397423042297289925395685450803460831897928252
g_2 = 1715827607770822027916388359002895605121557965635122390638079472658089153470011628164369842925275875967712538848782207398137721300785000148786237090186504979128222511965981575912913326516029139664053593759312951800545982648954917607038575718360849770282586139468386428432823626468085403220001310594753857986186494335432908855975879089482927309452461286290921871478006193072624494526500896055795364974923120807686893394782469634994819939396068806887992467663531650404341622534450045351363338604611403508251536208868099600795923830484553848138777019101735178671893852703652034757522746423826105891841738087294547994803

p = GCD(g_1-1,n)
q = GCD(g_2-1,n)

dp = invert(e,p-1)
m = pow(c_1,dp,p)
print(long_to_bytes(m))

[GKCTF 2021]RRRRsa

考点：费马小定理，二项式定理

题面：

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

flag = b'xxxxxxxxxxxxx'
p = getPrime(512)
q = getPrime(512)
m = bytes_to_long(flag)
n = p*q
e = 65537
c = pow(m,e,n)
print('c={}'.format(c))

p1 = getPrime(512)
q1 = getPrime(512)
n1 = p1*q1
e1 = 65537
assert gcd(e1,(p1-1)*(q1-1)) == 1
c1 = pow(p,e1,n1)
print('n1={}'.format(n1))
print('c1={}'.format(c1))
hint1 = pow(2020 * p1 + q1, 202020, n1)
hint2 = pow(2021 * p1 + 212121, q1, n1)
print('hint1={}'.format(hint1))
print('hint2={}'.format(hint2))

p2 = getPrime(512)
q2 = getPrime(512)
n2 = p2*q2
e2 = 65537
assert gcd(e1,(p2-1)*(q2-1)) == 1
c2 = pow(q,e2,n2)
hint3 = pow(2020 * p2 + 2021 * q2, 202020, n2)
hint4 = pow(2021 * p2 + 2020 * q2, 212121, n2)
print('n2={}'.format(n2))
print('c2={}'.format(c2))
print('hint3={}'.format(hint3))
print('hint4={}'.format(hint4))

#c=13492392717469817866883431475453770951837476241371989714683737558395769731416522300851917887957945766132864151382877462142018129852703437240533684604508379950293643294877725773675505912622208813435625177696614781601216465807569201380151669942605208425645258372134465547452376467465833013387018542999562042758
#n1=75003557379080252219517825998990183226659117019770735080523409561757225883651040882547519748107588719498261922816865626714101556207649929655822889945870341168644508079317582220034374613066751916750036253423990673764234066999306874078424803774652754587494762629397701664706287999727238636073466137405374927829
#c1=68111901092027813007099627893896838517426971082877204047110404787823279211508183783468891474661365139933325981191524511345219830693064573462115529345012970089065201176142417462299650761299758078141504126185921304526414911455395289228444974516503526507906721378965227166653195076209418852399008741560796631569
#hint1=23552090716381769484990784116875558895715552896983313406764042416318710076256166472426553520240265023978449945974218435787929202289208329156594838420190890104226497263852461928474756025539394996288951828172126419569993301524866753797584032740426259804002564701319538183190684075289055345581960776903740881951
#hint2=52723229698530767897979433914470831153268827008372307239630387100752226850798023362444499211944996778363894528759290565718266340188582253307004810850030833752132728256929572703630431232622151200855160886614350000115704689605102500273815157636476901150408355565958834764444192860513855376978491299658773170270
#n2=114535923043375970380117920548097404729043079895540320742847840364455024050473125998926311644172960176471193602850427607899191810616953021324742137492746159921284982146320175356395325890407704697018412456350862990849606200323084717352630282539156670636025924425865741196506478163922312894384285889848355244489
#c2=67054203666901691181215262587447180910225473339143260100831118313521471029889304176235434129632237116993910316978096018724911531011857469325115308802162172965564951703583450817489247675458024801774590728726471567407812572210421642171456850352167810755440990035255967091145950569246426544351461548548423025004
#hint3=25590923416756813543880554963887576960707333607377889401033718419301278802157204881039116350321872162118977797069089653428121479486603744700519830597186045931412652681572060953439655868476311798368015878628002547540835719870081007505735499581449077950263721606955524302365518362434928190394924399683131242077
#hint4=104100726926923869566862741238876132366916970864374562947844669556403268955625670105641264367038885706425427864941392601593437305258297198111819227915453081797889565662276003122901139755153002219126366611021736066016741562232998047253335141676203376521742965365133597943669838076210444485458296240951668402513

分析：

$$
hint1=(2020p_1+q_1)^{202020}\ mod\ n_1\
hint2=(2021p_1+212121)^{q_1}\ mod\ n_1\
$$

一般看到指数上是这种p,q之类的，先想到了费马小定理：
$$
hint2≡(2021p_1+212121)^{q_1}\ mod\ q_1 ≡2021p_1+212121\ mod\ q_1
$$

$$
hint2-212121≡(2021p_1)\ mod\ q_1
$$

对于hint1这样的直接二项式展开
$$
hint1≡(2020p_1)^{202020}+q_1^{202020}\ mod\ n_1 ≡(2020p_1)^{202020}\ mod\ q_1
$$
凑项：
$$
2021^{202020}hint1-2020(hint2-212121)^{202020} ≡ 0\ mod\ q_1\ =kq_1
$$
然后与n1求最大公因数即可

$$
hint3=(2020p_2+2021q_2)^{202020}\ mod\ n_2\
hint4=(2021p_2+2020q_2)^{212112}\ mod\ n_2
$$

$$
hint3≡(2020p_2)^{202020}\ mod\ q_2\
hint4≡(2021p_2)^{212121}\ mod\ q_2
$$

凑项：
$$
(2021^{202020}hint3)^{212121}-(2021^{212121}hint4)^{202020} = kq_2
$$
然后与n2求最大公因数即可

以上在进行大指数运算的时候可以模对应的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
28
29
30
31
32
33
34
35
36
from Crypto.Util.number import *
from gmpy2 import *

c=13492392717469817866883431475453770951837476241371989714683737558395769731416522300851917887957945766132864151382877462142018129852703437240533684604508379950293643294877725773675505912622208813435625177696614781601216465807569201380151669942605208425645258372134465547452376467465833013387018542999562042758
n1=75003557379080252219517825998990183226659117019770735080523409561757225883651040882547519748107588719498261922816865626714101556207649929655822889945870341168644508079317582220034374613066751916750036253423990673764234066999306874078424803774652754587494762629397701664706287999727238636073466137405374927829
c1=68111901092027813007099627893896838517426971082877204047110404787823279211508183783468891474661365139933325981191524511345219830693064573462115529345012970089065201176142417462299650761299758078141504126185921304526414911455395289228444974516503526507906721378965227166653195076209418852399008741560796631569
hint1=23552090716381769484990784116875558895715552896983313406764042416318710076256166472426553520240265023978449945974218435787929202289208329156594838420190890104226497263852461928474756025539394996288951828172126419569993301524866753797584032740426259804002564701319538183190684075289055345581960776903740881951
hint2=52723229698530767897979433914470831153268827008372307239630387100752226850798023362444499211944996778363894528759290565718266340188582253307004810850030833752132728256929572703630431232622151200855160886614350000115704689605102500273815157636476901150408355565958834764444192860513855376978491299658773170270
n2=114535923043375970380117920548097404729043079895540320742847840364455024050473125998926311644172960176471193602850427607899191810616953021324742137492746159921284982146320175356395325890407704697018412456350862990849606200323084717352630282539156670636025924425865741196506478163922312894384285889848355244489
c2=67054203666901691181215262587447180910225473339143260100831118313521471029889304176235434129632237116993910316978096018724911531011857469325115308802162172965564951703583450817489247675458024801774590728726471567407812572210421642171456850352167810755440990035255967091145950569246426544351461548548423025004
hint3=25590923416756813543880554963887576960707333607377889401033718419301278802157204881039116350321872162118977797069089653428121479486603744700519830597186045931412652681572060953439655868476311798368015878628002547540835719870081007505735499581449077950263721606955524302365518362434928190394924399683131242077
hint4=104100726926923869566862741238876132366916970864374562947844669556403268955625670105641264367038885706425427864941392601593437305258297198111819227915453081797889565662276003122901139755153002219126366611021736066016741562232998047253335141676203376521742965365133597943669838076210444485458296240951668402513


q1 = gcd(pow(2021,202020)*hint1-pow(2020*(hint2-212121),202020),n1)
p1 = n1//q1
e1 = 65537
phi1 = (p1-1)*(q1-1)
d1 = invert(e1, phi1)
p = pow(c1,d1,n1)
print(p)

q2 = gcd(pow(pow(2021,202020)*hint3,212121,n2)-pow(pow(2020,212121)*hint4,202020,n2),n2)
print(q2)
p2 = n2//q2
e2 = 65537
phi2 = (p2-1)*(q2-1)
d2 = invert(e2, phi2)
q = pow(c2,d2,n2)
print(q)

phi = (p-1)*(q-1)
e = 65537
d = invert(e, phi)
m = pow(c,d,p*q)
print(long_to_bytes(m))