# Training WCO4 #2 RSA
## Set 1
### modular Exponentiation
" Mọi phép toán trong RSA đều liên quan đến lũy thừa modulo "
Lũy thừa modulo là phép toán lũy thừa và sau đó chia lấy phần dư cho một số gọi là modulo.
Trong RSA, với phần lõi là lũy thừa modulo và phân tích thừa số nguyên tố, từ đó có thể tạo ra một "trapdoor function" - là một hàm dễ tính theo chiều xuôi nhưng khó để tính ngược lại, trừ khi có được khóa bí mật. Phần khó của RSA là tìm được p và q hay phân tích thừa số nguyên tố của N.
Hiện nay mật mã RSA được xem là an toàn nếu như thỏa điều kiện như n đủ lớn ( >= 2048 bits ), p và q là 2 số nguyên tố ngẫu nhiên khác nhau và cách xa nhau, không có dạng đặc biệt ( vd p là số đảo ngược của q ), e là một số nguyên tố vừa đủ ( thường là 65537 ), đảm bảo gcd( e, $\phi$ ) = 1 với $\phi$ = (p-1) * (q-1), d đủ lớn, và không bị lộ p, q, d.
Chúng ta có thể dùng hàm pow(base, exponent, modulus) để thực hiện lũy thừa modulo nhanh.
#### Script :

print( pow( 101, 17, 22663 ))

### Public Keys
Công thức mã hóa của RSA là
$$ c = m^e \pmod{n}$$
Và công thức giải mã là
$$m=c^d \pmod{n}$$
Với
$$d=e^{-1} \pmod{\phi} , \; \phi = (p-1)*(q-1)$$
#### Script :

m = 12
e = 65537 
p = 17
q = 23
n = p * q
c = pow( m, e, n )
print( c )

### Euler's Totient
Sử dụng công thức tính phi hàm Euler ở trên để tính. $\phi$ chính là "trapdoor" để giải RSA.
$\phi$ là số lượng phần tử từ 1 - n cùng nguyên tố với n hay gcd của chúng bằng 1.
#### Script :

p = 857504083339712752489993810777
q = 1029224947942998075080348647219
phi = ( p - 1 ) * ( q -  1 )
print( phi )

### Private Keys
Khóa bí mật d là chìa khóa để giải RSA, được tạo bằng cách nghịch đảo nhân modulo của e theo $\phi$ và điều kiện để có được nghịch đảo modulo là $$ gcd( e, \phi ) = 1 $$
Có thể chứng minh theo Extended Euclidean
$$ d *e + c * \phi = gcd( e, \phi)$$
Xét trên mod ($\phi$ )
$$d*e = 1 \pmod{\phi}$$
$$d = e ^{-1} \pmod{\phi}$$
### RSA Decryption
Sử dụng factordb.com để phân tích thừa số nguyên tố N, từ đó giải mã theo công thức
#### Script :

N = 882564595536224140639625987659416029426239230804614613279163
e = 65537
c = 77578995801157823671636298847186723593814843845525223303932
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
phi = ( p - 1 ) * ( q - 1 )
d = pow( e, -1, phi )
m = pow( c, d, N )
print( m )

### RSA Signatures
Để xác định được người gửi, ta sử dụng " ký " tin nhắn.
Ký cũng sử dụng công thức như RSA, nhưng trước đó phải sử dụng hàm băm chữ ký, sau đó cho vào công thức
$$S = H(m)^{d1} \pmod{N1}$$
Với H(m) là Hash( message ) là kết quả của chữ kí sau khi băm ( thường là SHA256 )
Để đảm bảo an toàn thì các tham số như d, e, n đều phải khác nhau giữa hàm mã hóa chữ ký và mã hóa thông tin.
Xác minh chữ ký bằng cách giải mã để lấy H(m), sau đó hash chữ ký của người gửi, so sánh chúng với nhau để xác thực người gửi tin.
Chữ ký số giúp ta thỏa mãn được 4 điều quan trọng nhất trong mật mã học là tính bảo mật, tính toàn vẹn, tính xác thực, tính chống chối bỏ, điều này giúp hệ thống mã hóa được an toàn và tín nhiệm hơn.
private.key
https://cryptohack.org/static/challenges/private_0a1880d1fffce9403686130a1f932b10.key
#### Script :

from Crypto.Util.number import long_to_bytes, bytes_to_long
import hashlib
N = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803
d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689
msg = b"crypto{Immut4ble_m3ssag1ng}"
msg = bytes_to_long( hashlib.sha256( msg ).digest() )
sign = pow( msg, d, N )
print( sign )

### Tổng kết starter 1 - 5
RSA là một hệ mật mã khóa công khai dựa trên toán học modulo, lõi của nó là lũy thừa modulo và bài toán phân tích thừa số nguyên tố.
RSA là một "trapdoor function" với các tham số p, q, n, e, d, $\phi$
p, q là hai số nguyên tố lớn, tạo thành n - modulus của RSA,
$\phi$ = ( p - 1 ) * ( q - 1 ) là thành phần quan trọng để tạo khóa bí mật và cũng là trapdoor giúp giải mã RSA, d là khóa bí mật, e là số mũ không khai.
RSA được xem là an toàn nếu như thỏa điều kiện như n đủ lớn ( >= 2048 bits ), p và q là 2 số nguyên tố ngẫu nhiên khác nhau và cách xa nhau, không có dạng đặc biệt ( vd p là số đảo ngược của q ), e là một số nguyên tố vừa đủ ( thường là 65537 ), đảm bảo gcd( e, $\phi$ ) = 1 với $\phi$ = (p-1) * (q-1), d đủ lớn, và không bị lộ p, q, d.
Ngoài $\phi$ ra nếu ta biết được Carmichael( λ ) của RSA thì cũng có thể giải được theo cách thông thường thay cho $\phi$, Carmichael là chu kì chung nhỏ nhất của các phần tử cùng nguyên tố với n thỏa điều kiện $a^{\lambda}=1\pmod{n}$, a là các phần tử. 
Công thức của Carmichael
Và công thức tính LCM
$$
\mathrm{lcm}(a,b) = \frac{|ab|}{\gcd(a,b)}
$$
Vì Carmichael là LCM nên sẽ nhỏ hơn hoặc bằng $\phi$, vì thế có thể thực hiện nhanh hơn $\phi$.
Để đảm bảo an toàn hơn cho RSA, trong cấu trúc sẽ không chưa mỗi raw plaintext mà có thêm padding, giúp ngăn chăn hầu hết các cuộc tấn công RSA. Phổ biến là kiểu OAEP trong mã hóa tin và PSS cho chữ ký số.
Cách khởi tạo RSA ( gen key ) :
- Sinh p, q
- Tính $\phi$ hoặc λ
Chọn 1 giá trị e thỏa $\gcd(e,λ(n))=1$ hoặc $\gcd(e,\phi(n))=1$
Tính khóa bí mật d theo công thức $d=e^{-1} \pmod{\phi(n) / λ(n)}$
Mã hóa
$$ c = m^e \pmod{n}$$
Giải mã
$$m=c^d \pmod{n}$$

Chữ ký số dùng để xác thực người gửi, các bước thực hiện ký số:
- Băm chữ ký $h = H( m )$
- Mã hóa $S = h^d \pmod{n}$
- Giải mã $h'=S^e \pmod{n}$
- Xác minh h' = H( m )
---
## Set 2
### Factoring
Chỉ cần phân tích được thừa số nguyên tố của n thì RSA hoàn toàn bị phá. Vậy thì kích thước của n bao nhiêu là đủ mạnh và không làm chậm tốc độ. Hiện nay là 2048 bits, vì hiện nay với n 2048 bits thì vẫn chưa thể phân tích hoàn chỉnh được, các số n nhỏ hơn ( 1024, 512 bits ) đã được nghiên cứu và phân tích hoàn toàn, nên chúng không còn an toàn, còn các số lơn hơn( 4096, 8192 ) thì quá lớn, khiến tốc độ bị chậm lại nhiều. Nhưng với sự phát triển của máy tính lượng tử, có thể n sẽ thay đổi về kích thước.
Sử dụng các tool factor để phân tích thừa số
https://github.com/ryosan-470/factordb-python
https://factordb.com/
https://www.alpertron.com.ar/ECM.HTM
### Monoprime
Với việc chỉ dùng 1 prime làm modulus thì vấn đề khó khăn nhất của RSA là phân tích thừa số nguyên tố bị loại bỏ hoàn toàn, đồng nghĩa với việc hệ thống không hề an toàn.
Theo công thức của $\phi$ thì $\phi(n)$ = n - 1

output.txt
https://cryptohack.org/static/challenges/output_086036e35349a406b94bfac9a7af6cca.txt
#### Script :

from Crypto.Util.number import long_to_bytes
n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591                                                                  
e = 65537
ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942  
phi = n - 1
d = pow( e, -1, phi )
m = pow( ct, d, n )
print( long_to_bytes( m ).decode() )

### Manyprime


output.txt
https://cryptohack.org/static/challenges/output_5a478a5d4764257d0bbdfaed340fcbdd.txt
Có các các thuật toán phân tích phổ biến như

| Thuật toán | Trường hợp |
| -------- | -------- |
| Fermat | abs( p - q ) nhỏ |
|pollard p - 1| p - 1 tạo từ các thừa số nhỏ ( smooth)|
| ECM | multi prime, các thừa số nguyên tố nhỏ/ trung bình |
|Pollard Rho| các thừa số nguyên tố nhỏ|

Ta sẽ dùng ECM cho bài này, tool https://www.alpertron.com.ar/ECM.HTM
#### Script :

from Crypto.Util.number import long_to_bytes
p = [ 9282105380008121879 , 9303850685953812323 , 9389357739583927789 , 10336650220878499841 , 10638241655447339831 , 11282698189561966721 , 11328768673634243077 , 11403460639036243901 , 11473665579512371723 , 11492065299277279799 , 11530534813954192171 , 11665347949879312361 , 12132158321859677597 , 12834461276877415051 , 12955403765595949597 , 12973972336777979701 , 13099895578757581201 , 13572286589428162097 , 14100640260554622013 , 14178869592193599187 , 14278240802299816541 , 14523070016044624039 , 14963354250199553339 , 15364597561881860737 , 15669758663523555763 , 15824122791679574573 , 15998365463074268941 , 16656402470578844539 , 16898740504023346457 , 17138336856793050757 , 17174065872156629921 , 17281246625998849649
]
n = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
e = 65537
ct = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464
phi = 1
for i in p:
    phi *= ( i - 1 )
d = pow( e, -1, phi )
m = pow( ct, d, n )
print( long_to_bytes( m ).decode() )

### Salty
#### Đề :

#!/usr/bin/env python3

from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes

e = 1
d = -1

while d == -1:
    p = getPrime(512)
    q = getPrime(512)
    phi = (p - 1) * (q - 1)
    d = inverse(e, phi)

n = p * q

flag = b"XXXXXXXXXXXXXXXXXXXXXXX"
pt = bytes_to_long(flag)
ct = pow(pt, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"ct = {ct}")

pt = pow(ct, d, n)
decrypted = long_to_bytes(pt)
assert decrypted == flag

output.txt
https://cryptohack.org/static/challenges/output_95f558e889cc66920c24a961f1fb8181.txt

Điểm lỗi ở bài này là số mũ e = 1, do đó theo công thức $c=m^e \pmod{n}$ $\Rightarrow c=m \pmod{n}$
Chỉ cần chuyển biến $ct$ từ số nguyên sang bytes là được.
#### Scrip :

from Crypto.Util.number import long_to_bytes
n = 110581795715958566206600392161360212579669637391437097703685154237017351570464767725324182051199901920318211290404777259728923614917211291562555864753005179326101890427669819834642007924406862482343614488768256951616086287044725034412802176312273081322195866046098595306261781788276570920467840172004530873767                                                                  
e = 1
ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485
print( long_to_bytes( ct ) )

### Modulus Inutilis
#### Đề :

#!/usr/bin/env python3

from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes

e = 3
d = -1

while d == -1:
    p = getPrime(1024)
    q = getPrime(1024)
    phi = (p - 1) * (q - 1)
    d = inverse(e, phi)

n = p * q

flag = b"XXXXXXXXXXXXXXXXXXXXXXX"
pt = bytes_to_long(flag)
ct = pow(pt, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"ct = {ct}")

pt = pow(ct, d, n)
decrypted = long_to_bytes(pt)
assert decrypted == flag

output.txt
https://cryptohack.org/static/challenges/output_30cff153b7432055fc947fc5abdb57d3.txt
Bài này không còn dùng e = 1 đơn giản như bài trước để dễ bị giải nữa, nhưng e lại không đủ lớn ( e = 3 ) tức $m^3<n$, vì thế vẫn có thể tính căn để tìm lại m mà không cần để ý đến mod n.
#### Script giải :

from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot
n = 17258212916191948536348548470938004244269544560039009244721959293554822498047075403658429865201816363311805874117705688359853941515579440852166618074161313773416434156467811969628473425365608002907061241714688204565170146117869742910273064909154666642642308154422770994836108669814632309362483307560217924183202838588431342622551598499747369771295105890359290073146330677383341121242366368309126850094371525078749496850520075015636716490087482193603562501577348571256210991732071282478547626856068209192987351212490642903450263288650415552403935705444809043563866466823492258216747445926536608548665086042098252335883
e = 3
ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957
m = iroot( ct, e )[0]
print( long_to_bytes( m ).decode() )

### Inferius Prime
#### Đề :

#!/usr/bin/env python3

from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes, GCD

e = 0x10001

# n will be 8 * (100 + 100) = 1600 bits strong (I think?) which is pretty good
p = getPrime(100)
q = getPrime(100)
phi = (p - 1) * (q - 1)
d = inverse(e, phi)

n = p * q

FLAG = b"crypto{???????????????}"
pt = bytes_to_long(FLAG)
ct = pow(pt, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"ct = {ct}")

pt = pow(ct, d, n)
decrypted = long_to_bytes(pt)![image](https://hackmd.io/_uploads/B1LeC6pzZl.png)

assert decrypted == FLAG

output.txt
https://cryptohack.org/static/challenges/output_cf39018a5db981bd454ddcdcf6595167.txt
Tác giả nghĩ n = 8 * ( 100 + 100 ) = 1600 bits nên đủ mạnh để tạo sự khó khăn cho việc phân tích, nhưng thực tế vì p và q là hai số nguyên tố 100 bits nên n chỉ khoảng 200 bits ( $(2^{100} -1)^2<=2^{200}$ và $2^{99*2}<=2^{198}$ ). Vì thế nên rất dễ để phân tích n và tìm p, q. Đây là điểm chết của bài.
#### Script :

from Crypto.Util.number import long_to_bytes
e = 65537
q = 848445505077945374527983649411
p = 1160939713152385063689030212503
ct = 948553474947320504624302879933619818331484350431616834086273
n = 984994081290620368062168960884976209711107645166770780785733
phi = ( p - 1 ) * ( q - 1 )
d = pow( e, -1, phi )
m = pow( ct, d, n )
print( long_to_bytes( m ).decode() )

### Square Eyes
output.txt
https://cryptohack.org/static/challenges/output_00dace150c0bc52f7abf03fc3e9529d2.txt
Theo như đề nói thì n được tạo từ 2 p, q bằng nhau hay $n=p^2$, từ đó tính căn của n sẽ ra được p. Áp dụng công thức tính phi hàm Euler với 1 số nguyên phân tích duy nhất mũ bằng 2
$\phi = p*(p-1)$
#### Script :

from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot
n = 535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449
e = 65537
ct = 222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896
p = iroot( n, 2 )[0]
phi = ( p - 1 ) * p
d = pow( e, -1, phi )
m = pow( ct, d, n )
print( long_to_bytes( m ).decode() )

Ngoài cách tìm căn ta có thể sử dụng tool để phân tích ra được p.
### Tổng kết set 2
Set 2 cho ta biết được các lỗi nghiêm trọng khi tạo dựng RSA, đồng thời cho biết cách tận dụng chúng để giải mã ở mức cơ bản. Các lỗi bao gồm e quá nhỏ, đặc biệt ( e = 1 ), chỉ dùng 1 số nguyên tố để làm modulus, sử dụng nhiều số nguyên tố để làm modulus nhưng các số không đủ lớn, tính toán sai kích thước của n từ đó chọn sai kích thước cho p và q, sử dụng 2 số nguyên tố giống nhau để tạo modulus.

---
## Set 3
### Endless Emails
#### Đề :

#!/usr/bin/env python3

from Crypto.Util.number import bytes_to_long, getPrime
from secret import messages


def RSA_encrypt(message):
    m = bytes_to_long(message)
    p = getPrime(1024)
    q = getPrime(1024)
    N = p * q
    e = 3
    c = pow(m, e, N)
    return N, e, c


for m in messages:
    N, e, c = RSA_encrypt(m)
    print(f"n = {N}")
    print(f"e = {e}")
    print(f"c = {c}")

output.txt
https://cryptohack.org/static/challenges/output_0ef6d6343784e59e2f44f61d2d29896f.txt
Đây là dạng cơ bản của Håstad Broadcast Attack - là kiểu tấn công cho các trường hợp mã hóa cùng một plaintext với nhiều modulus khác nhau nhưng dùng cùng exponent. Trường hợp đơn giản nếu có e = 3 và nhiều đoạn ciphertext được mã hóa với các n khác nhau nhưng cùng e, thì chỉ cần biết 3 ciphertext cùng với n tương ứng có thể tìm lại được plaintext.
Với e = 3 ta có thể dùng crt với 3 phương trình để tìm được $m^e = m^3$, và vì $m^3 < n1*n2*n3\;$nên ta chỉ cần tìm căn bậc 3 của $m^3$ trong số nguyên không cần mod.
Tổng quát: Nếu tất cả đều cùng số mũ công khai ( exponent ) e thì cần >= e phương trình để có thể tìm lại được plaintext. Dạng cơ bản chỉ hoạt động với e nhỏ.
Tài liệu : https://www.ams.org/notices/199902/boneh.pdf
#### Script giải :

import re
from itertools import combinations
from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot

e = 3 
cs = [ 6965891612987861726975066977377253961837139691220763821370036576350605576485706330714192837336331493653283305241193883593410988132245791554283874785871849223291134571366093850082919285063130119121338290718389659761443563666214229749009468327825320914097376664888912663806925746474243439550004354390822079954583102082178617110721589392875875474288168921403550415531707419931040583019529612270482482718035497554779733578411057633524971870399893851589345476307695799567919550426417015815455141863703835142223300228230547255523815097431420381177861163863791690147876158039619438793849367921927840731088518955045807722225, 5109363605089618816120178319361171115590171352048506021650539639521356666986308721062843132905170261025772850941702085683855336653472949146012700116070022531926476625467538166881085235022484711752960666438445574269179358850309578627747024264968893862296953506803423930414569834210215223172069261612934281834174103316403670168299182121939323001232617718327977313659290755318972603958579000300780685344728301503641583806648227416781898538367971983562236770576174308965929275267929379934367736694110684569576575266348020800723535121638175505282145714117112442582416208209171027273743686645470434557028336357172288865172, 5603386396458228314230975500760833991383866638504216400766044200173576179323437058101562931430558738148852367292802918725271632845889728711316688681080762762324367273332764959495900563756768440309595248691744845766607436966468714038018108912467618638117493367675937079141350328486149333053000366933205635396038539236203203489974033629281145427277222568989469994178084357460160310598260365030056631222346691527861696116334946201074529417984624304973747653407317290664224507485684421999527164122395674469650155851869651072847303136621932989550786722041915603539800197077294166881952724017065404825258494318993054344153, 1522280741383024774933280198410525846833410931417064479278161088248621390305797210285777845359812715909342595804742710152832168365433905718629465545306028275498667935929180318276445229415104842407145880223983428713335709038026249381363564625791656631137936935477777236936508600353416079028339774876425198789629900265348122040413865209592074731028757972968635601695468594123523892918747882221891834598896483393711851510479989203644477972694520237262271530260496342247355761992646827057846109181410462131875377404309983072358313960427035348425800940661373272947647516867525052504539561289941374722179778872627956360577, 8752507806125480063647081749506966428026005464325535765874589376572431101816084498482064083887400646438977437273700004934257274516197148448425455243811009944321764771392044345410680448204581679548854193081394891841223548418812679441816502910830861271884276608891963388657558218620911858230760629700918375750796354647493524576614017731938584618983084762612414591830024113057983483156974095503392359946722756364412399187910604029583464521617256125933111786441852765229820406911991809039519015434793656710199153380699319611499255869045311421603167606551250174746275803467549814529124250122560661739949229005127507540805, 23399624135645767243362438536844425089018405258626828336566973656156553220156563508607371562416462491581383453279478716239823054532476006642583363934314982675152824147243749715830794488268846671670287617324522740126594148159945137948643597981681529145611463534109482209520448640622103718682323158039797577387254265854218727476928164074249568031493984825273382959147078839665114417896463735635546290504843957780546550577300001452747760982468547756427137284830133305010038339400230477403836856663883956463830571934657200851598986174177386323915542033293658596818231793744261192870485152396793393026198817787033127061749, 15239683995712538665992887055453717247160229941400011601942125542239446512492703769284448009141905335544729440961349343533346436084176947090230267995060908954209742736573986319254695570265339469489948102562072983996668361864286444602534666284339466797477805372109723178841788198177337648499899079471221924276590042183382182326518312979109378616306364363630519677884849945606288881683625944365927809405420540525867173639222696027472336981838588256771671910217553150588878434061862840893045763456457939944572192848992333115479951110622066173007227047527992906364658618631373790704267650950755276227747600169403361509144 ]
ns = [ 14528915758150659907677315938876872514853653132820394367681510019000469589767908107293777996420037715293478868775354645306536953789897501630398061779084810058931494642860729799059325051840331449914529594113593835549493208246333437945551639983056810855435396444978249093419290651847764073607607794045076386643023306458718171574989185213684263628336385268818202054811378810216623440644076846464902798568705083282619513191855087399010760232112434412274701034094429954231366422968991322244343038458681255035356984900384509158858007713047428143658924970374944616430311056440919114824023838380098825914755712289724493770021, 20463913454649855046677206889944639231694511458416906994298079596685813354570085475890888433776403011296145408951323816323011550738170573801417972453504044678801608709931200059967157605416809387753258251914788761202456830940944486915292626560515250805017229876565916349963923702612584484875113691057716315466239062005206014542088484387389725058070917118549621598629964819596412564094627030747720659155558690124005400257685883230881015636066183743516494701900125788836869358634031031172536767950943858472257519195392986989232477630794600444813136409000056443035171453870906346401936687214432176829528484662373633624123, 19402640770593345339726386104915705450969517850985511418263141255686982818547710008822417349818201858549321868878490314025136645036980129976820137486252202687238348587398336652955435182090722844668488842986318211649569593089444781595159045372322540131250208258093613844753021272389255069398553523848975530563989367082896404719544411946864594527708058887475595056033713361893808330341623804367785721774271084389159493974946320359512776328984487126583015777989991635428744050868653379191842998345721260216953918203248167079072442948732000084754225272238189439501737066178901505257566388862947536332343196537495085729147, 12005639978012754274325188681720834222130605634919280945697102906256738419912110187245315232437501890545637047506165123606573171374281507075652554737014979927883759915891863646221205835211640845714836927373844277878562666545230876640830141637371729405545509920889968046268135809999117856968692236742804637929866632908329522087977077849045608566911654234541526643235586433065170392920102840518192803854740398478305598092197183671292154743153130012885747243219372709669879863098708318993844005566984491622761795349455404952285937152423145150066181043576492305166964448141091092142224906843816547235826717179687198833961, 17795451956221451086587651307408104001363221003775928432650752466563818944480119932209305765249625841644339021308118433529490162294175590972336954199870002456682453215153111182451526643055812311071588382409549045943806869173323058059908678022558101041630272658592291327387549001621625757585079662873501990182250368909302040015518454068699267914137675644695523752851229148887052774845777699287718342916530122031495267122700912518207571821367123013164125109174399486158717604851125244356586369921144640969262427220828940652994276084225196272504355264547588369516271460361233556643313911651916709471353368924621122725823, 25252721057733555082592677470459355315816761410478159901637469821096129654501579313856822193168570733800370301193041607236223065376987811309968760580864569059669890823406084313841678888031103461972888346942160731039637326224716901940943571445217827960353637825523862324133203094843228068077462983941899571736153227764822122334838436875488289162659100652956252427378476004164698656662333892963348126931771536472674447932268282205545229907715893139346941832367885319597198474180888087658441880346681594927881517150425610145518942545293750127300041942766820911120196262215703079164895767115681864075574707999253396530263, 19833203629283018227011925157509157967003736370320129764863076831617271290326613531892600790037451229326924414757856123643351635022817441101879725227161178559229328259469472961665857650693413215087493448372860837806619850188734619829580286541292997729705909899738951228555834773273676515143550091710004139734080727392121405772911510746025807070635102249154615454505080376920778703360178295901552323611120184737429513669167641846902598281621408629883487079110172218735807477275590367110861255756289520114719860000347219161944020067099398239199863252349401303744451903546571864062825485984573414652422054433066179558897 ]


def Crt( a, n ):
    N = 1
    for i in n:
        N *= i
    x = 0
    for i, j in zip( a, n ):
        Ni = N // j
        Yi = pow( Ni, -1, j )
        x += i * Ni * Yi
    return x % N

data = ( cs, ns )
for i in range( e, 7 ):
    for combo in combinations( range( 7 ), i ):
        c = []
        n = []
        for i in combo:
            c.append( cs[i] )
            n.append( ns[i] )
        x = Crt( c, n )
        m, check = iroot( x, 3 )
        if( check ):
            flag = long_to_bytes( m )
            if( b"crypto" in flag ):
                print( flag.decode() )
                exit()

### Infinite Descent
#### Đề :

#!/usr/bin/env python3

import random
from Crypto.Util.number import bytes_to_long, isPrime

FLAG = b"crypto{???????????????????}"


def getPrimes(bitsize):
    r = random.getrandbits(bitsize)
    p, q = r, r
    while not isPrime(p):
        p += random.getrandbits(bitsize//4)
    while not isPrime(q):
        q += random.getrandbits(bitsize//8)
    return p, q


m = bytes_to_long(FLAG)
p, q = getPrimes(2048)
n = p * q
e = 0x10001
c = pow(m, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")

output.txt
https://cryptohack.org/static/challenges/output_14f82a67efe7b7edffb810dbb7ab5f27.txt
Xem cách sinh số nguyên tố p, q của hàm getPrime ta nhận thấy mỗi lần p không phải số nguyên tố thì sẽ cộng thêm một số 2048 // 4 = 512 bits, còn q sẽ cộng thêm một số 2048 // 8 = 256 bits. Mỗi bước cộng thêm khá ít nên p và q sẽ rất gần nhau, có thể là hai số nguyên tố liền kề nhau, | p - q | nhỏ. Đây là dấu hiệu cho Fermat Factorize, điều kiện dùng là | p - q | < n^(1/4)
Cách hoạt động của Fermat Factorize dựa trên phương trình phân tích số nguyên chẵn n thành hiệu bình phương của hai giá trị $$n = a^2 - b^2 = (a-b)*(a+b)$$
Nếu tìm được a và b thỏa điều kiện thì $p=a+b \;và \;q=a-b$
Cách thực hiện:

-Đặt a là trần ( ceil ) của căn n ( căn bậc 2 của n + 1 nếu a không phải là căn hoàn chỉnh của n )
-Tìm $b^2 = a^2-n$, sau đó tìm căn bậc 2 của $b^2$, nếu tồn tại căn bậc 2 hoàn chỉnh là b thì $p=a+b ; \; q=a-b$
Tài liệu: https://en.wikipedia.org/wiki/Fermat's_factorization_method
#### Fermat Factorize

from gmpy2 import iroot, isqrt
n = 
def fermat_factor( n ):
    a = isqrt(n)
    if a * a < n:
        a += 1
    while 1:
        x = a ** 2 - n 
        b, check = iroot( x, 2 )
        if check:
            p = a + b 
            q = a - b
            if( p * q != n ):
                a += 1
                continue
            break
        a += 1
    return p, q

#### Script giải :

from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot, isqrt
n = 383347712330877040452238619329524841763392526146840572232926924642094891453979246383798913394114305368360426867021623649667024217266529000859703542590316063318592391925062014229671423777796679798747131250552455356061834719512365575593221216339005132464338847195248627639623487124025890693416305788160905762011825079336880567461033322240015771102929696350161937950387427696385850443727777996483584464610046380722736790790188061964311222153985614287276995741553706506834906746892708903948496564047090014307484054609862129530262108669567834726352078060081889712109412073731026030466300060341737504223822014714056413752165841749368159510588178604096191956750941078391415634472219765129561622344109769892244712668402761549412177892054051266761597330660545704317210567759828757156904778495608968785747998059857467440128156068391746919684258227682866083662345263659558066864109212457286114506228470930775092735385388316268663664139056183180238043386636254075940621543717531670995823417070666005930452836389812129462051771646048498397195157405386923446893886593048680984896989809135802276892911038588008701926729269812453226891776546037663583893625479252643042517196958990266376741676514631089466493864064316127648074609662749196545969926051
e = 65537
c = 98280456757136766244944891987028935843441533415613592591358482906016439563076150526116369842213103333480506705993633901994107281890187248495507270868621384652207697607019899166492132408348789252555196428608661320671877412710489782358282011364127799563335562917707783563681920786994453004763755404510541574502176243896756839917991848428091594919111448023948527766368304503100650379914153058191140072528095898576018893829830104362124927140555107994114143042266758709328068902664037870075742542194318059191313468675939426810988239079424823495317464035252325521917592045198152643533223015952702649249494753395100973534541766285551891859649320371178562200252228779395393974169736998523394598517174182142007480526603025578004665936854657294541338697513521007818552254811797566860763442604365744596444735991732790926343720102293453429936734206246109968817158815749927063561835274636195149702317415680401987150336994583752062565237605953153790371155918439941193401473271753038180560129784192800351649724465553733201451581525173536731674524145027931923204961274369826379325051601238308635192540223484055096203293400419816024111797903442864181965959247745006822690967920957905188441550106930799896292835287867403979631824085790047851383294389

def fermat_factor( n ):
    a = isqrt(n)
    if a * a < n:
        a += 1
    while 1:
        x = a ** 2 - n 
        b, check = iroot( x, 2 )
        if check:
            p = a + b 
            q = a - b
            if( p * q != n ):
                a += 1
                continue
            break
        a += 1
    return p, q
p, q = fermat_factor( n )
phi = ( p - 1 ) * ( q - 1 )
d = pow( e, -1, phi )
m = pow( c, d, n )
print( long_to_bytes( m ).decode() )

### Everything is Big
#### Đề :

#!/usr/bin/env python3

from Crypto.Util.number import getPrime, bytes_to_long

FLAG = b"crypto{?????????????????????????}"

m = bytes_to_long(FLAG)

def get_huge_RSA():
    p = getPrime(1024)
    q = getPrime(1024)
    N = p*q
    phi = (p-1)*(q-1)
    while True:
        d = getPrime(256)
        e = pow(d,-1,phi)
        if e.bit_length() == N.bit_length():
            break
    return N,e


N, e = get_huge_RSA()
c = pow(m, e, N)

print(f'N = {hex(N)}')
print(f'e = {hex(e)}')
print(f'c = {hex(c)}')

output.txt
https://cryptohack.org/static/challenges/output_1884d0ba92d19ad074549e174cdf5a70.txt
Từ hàm **get_huge_RSA** ta thấy được một điểm khá khác với cách tạo RSA thông thường, d nhỏ hơn nhiều so với n ( bit length của d = 1/8 n ), đây là đặc điểm để thực hiện Wiener Attack. Điều kiện thực hiện Wiener Attack là
$$
\begin{aligned}
d &< \frac{1}{3} n^{\frac{1}{4}} \\
q &< p < 2q \\
e &< n^{\frac{3}{2}}
\end{aligned}
$$
Dựa trên công thức tính $\phi$ $$\phi=(p-1)*(q-1)=p*q-(p+q)+1$$
Vì n lớn hơn rất nhiều so với p và q nên ta có thể xấp xỉ $\phi \approx n$
Thêm một chút biến đổi công thức $e*d \equiv 1 \pmod{\phi(n)} \iff e*d-1 = k*\phi(n)$
Chia 2 vế cho $d*\phi(n)$ được $$\frac{e}{\phi(n)} - \frac{1}{d*\phi(n)}= \frac{k}{d}$$
Do $\frac{1}{d*\phi(n)}$ rất nhỏ nên có thể xấp xỉ $$\frac{e}{n} \approx \frac{k}{d}$$
Toàn bộ vế trái là các thông tin công khai, vế phải là 2 ẩn k và d.
Xét đa thức $(x-p)*(x-q)=0$ có 2 nghiệm là p và q, khai triển ta được $x^2 - (p+q)*x+p*q=0$ thay $p*q=n$ và $p+q=n+1-\phi(n)$ , ta được phương trình bậc 2 có 2 nghiệm p, q $$x^2-(n+1-\phi(n))*x+n=0$$
Vậy nên nếu tìm được $\phi(n)$ làm cho phương trình có 2 nghiệm phân biệt dương thì 2 nghiệm đó là p và q.
Để tìm $\phi(n)$ có các bước

-Chuyển phân số $\frac{e}{n}$ thành phân số liên tục dạng $$
[a_0; a_1, a_2, \ldots, a_{k-2}, a_{k-1}, a_k]
$$
Bằng cách gán a[i] = tử / mẫu, sau đó đổi tử, mẫu = mẫu, tử % mẫu, lặp lại đến khi mẫu bằng 0, lúc đó ta được một mảng chứa các hệ số.

def  continued_fraction( a, b, frac ):
    frac.append( a // b )
    a, b = b, a % b
    if( b == 0 ):
        return frac
    return continued_fraction( a, b, frac )
frac = []

-Lặp lại các phân số hội tụ ( convergents ) tại từng phần tử trong phân số liên tục
$$
\frac{a_0}{1},\;
a_0 + \frac{1}{a_1},\;
a_0 + \frac{1}{a_1 + \frac{1}{a_2}},\;
\ldots,\;
a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \cdots + \frac{1}{a_{k-1}}}}
$$
Có công thức tính các convergents là $$
\begin{aligned}
k_{-2} &= 0,\quad k_{-1} = 1 \\
d_{-2} &= 1,\quad d_{-1} = 0 \\
k_i &= a_i k_{i-1} + k_{i-2} \\
d_i &= a_i d_{i-1} + d_{i-2}
\end{aligned}
$$

def convergents( a, b, frac ):
    continued_fraction( a, b, frac )
    d1, d0 = 1, 0
    k1, k0 = 0, 1
    conv = []
    for cf in frac:
        d = cf * d0 + d1
        k = cf * k0 + k1
        conv.append(( k, d ))
        d1, d0 = d0, d
        k1, k0 = k0, k
    return conv

-Kiểm tra xem các convergents có phải là $\frac{k}{d}$ không bằng cách
- Đặt d là tử số, k là mẫu số của convergent
- Nếu d là số lẻ thì chuyển qua convergent mới
- Nếu $e*d \;\; !=1\pmod{k}$ thì chuyển qua convergent mới
- Tính $\phi(n)=\frac{e*d-1}{k}$, sau đó tìm nghiệm của phương trình bậc 2. Nếu 2 nghiệm là số nguyên thì tìm được d .

conv = convergents( e, n, frac )
for k, d in conv : 
    if( d % 2 == 0 ):
        continue
    if k == 0:
        continue 
    if( ( e * d - 1 ) % k != 0 ):
        continue
    phi = ( e * d - 1 ) // k
    s = n - phi + 1
    delta = s ** 2 - 4 * n
    
    t = math.isqrt( delta )
    p = (s + t) // 2
    q = (s - t) // 2

    if p*q == n:
        print("Found d =", d)
        break

Có thể sử dụng thư viện có sẵn của python để giải tiện hơn
Tài liệu :
https://cryptohack.gitbook.io/cryptobook/untitled/low-private-component-attacks/wieners-attack#automation
https://bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-2/#wieners-attack
https://en.wikipedia.org/wiki/Wiener%27s_attack
#### Script giải :

from Crypto.Util.number import long_to_bytes
from owiener import attack
n = "b8af3d3afb893a602de4afe2a29d7615075d1e570f8bad8ebbe9b5b9076594cf06b6e7b30905b6420e950043380ea746f0a14dae34469aa723e946e484a58bcd92d1039105871ffd63ffe64534b7d7f8d84b4a569723f7a833e6daf5e182d658655f739a4e37bd9f4a44aff6ca0255cda5313c3048f56eed5b21dc8d88bf5a8f8379eac83d8523e484fa6ae8dbcb239e65d3777829a6903d779cd2498b255fcf275e5f49471f35992435ee7cade98c8e82a8beb5ce1749349caa16759afc4e799edb12d299374d748a9e3c82e1cc983cdf9daec0a2739dadcc0982c1e7e492139cbff18c5d44529407edfd8e75743d2f51ce2b58573fea6fbd4fe25154b9964d"
e = "9ab58dbc8049b574c361573955f08ea69f97ecf37400f9626d8f5ac55ca087165ce5e1f459ef6fa5f158cc8e75cb400a7473e89dd38922ead221b33bc33d6d716fb0e4e127b0fc18a197daf856a7062b49fba7a86e3a138956af04f481b7a7d481994aeebc2672e500f3f6d8c581268c2cfad4845158f79c2ef28f242f4fa8f6e573b8723a752d96169c9d885ada59cdeb6dbe932de86a019a7e8fc8aeb07748cfb272bd36d94fe83351252187c2e0bc58bb7a0a0af154b63397e6c68af4314601e29b07caed301b6831cf34caa579eb42a8c8bf69898d04b495174b5d7de0f20cf2b8fc55ed35c6ad157d3e7009f16d6b61786ee40583850e67af13e9d25be3"
c = "3f984ff5244f1836ed69361f29905ca1ae6b3dcf249133c398d7762f5e277919174694293989144c9d25e940d2f66058b2289c75d1b8d0729f9a7c4564404a5fd4313675f85f31b47156068878e236c5635156b0fa21e24346c2041ae42423078577a1413f41375a4d49296ab17910ae214b45155c4570f95ca874ccae9fa80433a1ab453cbb28d780c2f1f4dc7071c93aff3924d76c5b4068a0371dff82531313f281a8acadaa2bd5078d3ddcefcb981f37ff9b8b14c7d9bf1accffe7857160982a2c7d9ee01d3e82265eec9c7401ecc7f02581fd0d912684f42d1b71df87a1ca51515aab4e58fab4da96e154ea6cdfb573a71d81b2ea4a080a1066e1bc3474"
c = int( c, 16 )
n = int( n, 16 )
e = int( e, 16 )
d = attack( e, n )
m = pow( c, d, n )
print( long_to_bytes( m ).decode() )

### Crossed Wires
#### Đề :

from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long, inverse
import math
from gmpy2 import next_prime

FLAG = b"crypto{????????????????????????????????????????????????}"

p = getPrime(1024)
q = getPrime(1024)
N = p*q
phi = (p-1)*(q-1)
e = 0x10001
d = inverse(e, phi)

my_key = (N, d)

friends = 5
friend_keys = [(N, getPrime(17)) for _ in range(friends)]

cipher = bytes_to_long(FLAG)

for key in friend_keys:
    cipher = pow(cipher, key[1], key[0])

print(f"My private key: {my_key}")
print(f"My Friend's public keys: {friend_keys}")
print(f"Encrypted flag: {cipher}")

output.txt
https://cryptohack.org/static/challenges/output_434cbf2b937bac1177bed299b2049a92.txt
Đề cho ta biết được N, d và e, cùng với các số mũ công khai của từng friend. công thức mã hóa là $$ct=m^{e0\;*\;e1\;*\;e2\;*\;e3\;*\;e4} \pmod{N}$$
Khi biết được khóa bí mật d thì có cách để phân tích được p, q.
Cách thực hiện
- Đặt $\;k = e * d -1$
- Chọn một số **g** ngẫu nhiên từ 2 đến N-1, đặt $t = k$
- Nếu $t\;\%\; 2 = 0$ thì $t=t/2$ và đặt $x=g^{t}\pmod{N}$. nếu $t\;\%\; 2 \not= 0$ thì quay lại bước trên
- Nếu $x>1$ và $gcd(x-1,N)>1$ thì ta tìm được $p=gcd(x-1,N)$ và $q=N/y$ , nếu không thì quay lại bước trên.

Tài liệu :
https://di-mgt.com.au/rsa_factorize_n.html
https://crypto.stackexchange.com/questions/62482/algorithm-to-factorize-n-given-n-e-d/62487#62487

def factor_know_d( d, n , e ):
    used = []
    k = d * e - 1
    if( k % 2 == 1 ):
        exit()
    while 1:
        g = random.randint( 2, n - 1 )
        if( g not in used ):
            used.append( g )
        else:
            continue
        t = k
        while( t % 2 == 0 ):
            t = t // 2 
            x = pow( g, t, n )
            y = math.gcd( x - 1, n )
            if( x <= 1 or y <= 1 ):
                continue
            p = y
            q = n // y 
            if( p * q == n ):
                return p, q

#### Script giải :

import random
import math
from Crypto.Util.number import long_to_bytes
n = 21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771
d = 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097
e = 0x10001
friends_key = [(21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 106979), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 108533), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 69557), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 97117), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 103231)]
ct = 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117
def factor_know_d( d, n , e ):
    used = []
    k = d * e - 1
    if( k % 2 == 1 ):
        exit()
    while 1:
        g = random.randint( 2, n - 1 )
        if( g not in used ):
            used.append( g )
        else:
            continue
        t = k
        while( t % 2 == 0 ):
            t = t // 2 
            x = pow( g, t, n )
            y = math.gcd( x - 1, n )
            if( x <= 1 or y <= 1 ):
                continue
            p = y
            q = n // y 
            if( p * q == n ):
                return p, q
p, q = factor_know_d( d, n, e )
friend_e = 1
for key in friends_key:
    friend_e *= key[1]
phi = ( p - 1 ) * ( q - 1 )
friend_d = pow( friend_e, -1, phi )
m = pow( ct, friend_d, n )
print( long_to_bytes( m ).decode() )

Ngoài ra lúc đầu em có thử brute tìm k luôn và chạy được nên em gửi luôn script brute bài này :))))

from Crypto.Util.number import long_to_bytes

my_key = (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097)
friends_key = [(21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 106979), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 108533), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 69557), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 97117), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 103231)]
ct = 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117
e = 65537
n, d = my_key
for k in range ( 1, 10 ):
    phi = ( e * d - 1 ) // k
    cipher = ct
    for key in friends_key:
        D = pow( key[1], -1, phi )
        cipher = pow( cipher, D, n )
    cipher = long_to_bytes( cipher )
    if( b"crypto" in cipher ):
        print( cipher )
        break

### Tổng kết set 3
4 bài của set 3 giúp ta biết thêm 4 cách tấn công Håstad Broadcast Attack, Wiener Attack, Factor n khi biết d, Fermat's factor Attack
## DreamHack
### Emoji RSA
#### Đề :

from Crypto.Util.number import *
import random

EMOJIS = "🤣😅😇😍🤪🤑🤔🙄🥵🥶"
FLAG = open('flag', 'r').read()
MENU = """1. Encrypt your input
2. Change e
3. Encrypt the flag"""

def get_e(p, q):
    while True:
        t = random.randint(2 ** 16 + 1, 2 ** 18 + 1) | 1
        if GCD(t, (p - 1) * (q - 1)) == 1:
            return t

def emojify(emojis, s):
    return ''.join(emojis[int(ch)] for ch in str(s))

def main():
    emojis = list(EMOJIS)
    random.shuffle(emojis)

    p = getStrongPrime(512)
    q = getStrongPrime(512)
    n = p * q
    e = get_e(p, q)

    print(f"e: {e}")

    while True:
        print(MENU)
        inp = int(input('choice > ').strip())

        if inp == 1:
            inp = int(input('input > ').strip())
            print(emojify(emojis, pow(inp, e, n)))
        elif inp == 2:
            e = get_e(p, q)
            print(f"e: {e}")
        elif inp == 3:
            print(emojify(emojis, pow(bytes_to_long(FLAG.encode()), e, n)))

if __name__ == "__main__":
    main()

#### Phân tích và ý tưởng
Đây là một bài RSA chỉ cho biết e và cho phép nhập input để mã hóa input, thay đổi e, mã hóa flag và tất cả thông tin sau mã hóa được đổi thành các emoji ( tráo đổi sau mỗi lần chạy server ). Ý tưởng đầu tiên của em là sẽ brute-force các emoji, khoảng 8! lần, vì 2 emoji đầu em sẽ biết được qua việc nhập input là 1 và 0 ( $1^e \pmod{n} = 1$ và $0^e \pmod{n} = 0$ ) từ đó tạo ra các hoán vị của 8 emoji còn lại và thử với từng bộ emoji.
Gọi khoảng 3 giá trị bất kì để mã hóa, ví dụ là 5, 7 và 11, sau khi mã hóa là $5^e \pmod{n} = enc1$ , $7^e\pmod{n}=enc2$ và $11^e \pmod{n} = enc3$, thay các giá trị của emoji vào thành các số tương úng, từ đó khả năng cao suy ra được $n =gcd(5^e-enc1,7^e-enc2,11^e-enc3)$, sau đó gọi enc flag, đổi e và gọi enc flag lần nữa với 2 e khác nhau nhưng cùng n và cùng plaintext có thể thực hiện Common Modulus Attack.
Common Modulus Attack có thể thực hiện khi cùng 1 plaintext, modulus và 2 giá trị e khác nhau ( gcd( e1, e2 ) = 1 càng tốt ) cho ra 2 ciphertext khác nhau
$$
\begin{aligned}
c1=m^{e1}\pmod{n} \\
c2=m^{e2}\pmod{n} \\
\end{aligned}
$$
Nếu có 2 giá trị a, b thỏa
$$a*e1+b*e2=gcd(e1,e2)=1$$
thì
$$
\begin{aligned}
c1^a=m^{a*e1}\pmod{n} \\
c2^b=m^{b*e2}\pmod{n} \\
\Rightarrow c1^a*c2^b=m^{a*e1+b*e2}\pmod{n} \\
\Rightarrow ct^a*c2^b=m^1=m\pmod{n}
\end{aligned}
$$
Vậy nhiệm vụ là tìm a và b thỏa mãn, điều đó đã có Extended GCD thực hiện. Sau khi tìm được m thì chuyển thành bytes và kiểm tra có đúng format của đề không.
**Nhưng cách này không chạy được ( hoặc quá lâu máy em chịu không nổi )** Vì cỡ 8! chạy rất nhanh nhưng quá rườm rà vì tương tác với server quá nhiều lần, cũng có thể là do các tìm n chưa thể ra đúng được.
Do đó có cách khác để tìm được n là nhập vào input là -1 sẽ lấy được n - 1 bị mapping bằng emoji, vì $(-1)^e\pmod{n}=n-1$ với e là số lẻ. Từ đó tạo hoán vị của 8 emoji như lúc đầu, thay vào tạo thành số n - 1 nguyên, tìm ra n, kiểm tra lại xem mapping tạo từ hoán vị có đúng không bằng cách nhập input khác ( ví dụ 17 ), sau đó chuyển đoạn enc thành số, ddamr bảo $enc = 17^e \pmod{n}$. Sau đó thwujc hiện Common Modulus Attack như cách trước đó để tìm flag.
Cách này tìm được chính xác n - 1, việc ta chỉ cần giải mapping ra và tìm lại được n, ít tương tác với server. Cách đầu tiên chỉ có thể tìm được n thôi vì có thể sẽ trả về k*n.
Cảm ơn Mai Đăng Khoa ( dkoazw ) vì hint tìm n này :))))))
Bài này em chạy local và nhập input để check là 17, vì em chưa thạo pwntool , em sẽ học kĩ thêm sau ạ.
#### Script :

from Crypto.Util.number import long_to_bytes
import itertools 


def egcd(a, b):
    x, y, u, v = 0, 1, 1, 0
    while a != 0:
        q, r = b // a, b % a
        m, n = x - u * q, y - v * q
        b, a, x, y, u, v = a, r, u, v, m, n
    gcd = b
    return gcd, x, y
e1 = 185053
e2 = 128769
# gcd( e1, e2 ) = 1 
n_1 = "🥵😇😇🤪😍🤔🥵🤣🥶🤣😇🤑🙄🤪🥵🥶😍🥵😍🤣🥵🙄🤣🤣😅🤣🙄🤪🙄😅😅🤣🤔😍🥶🤪😍🤪🤔🤔🤔🥵🤪😅🤣🤔🥶😅🙄🤪🤪🤑🤑🤪😅😍🤪🤔😇🥶🤣🤔😅🥵😇🥵🤑😇🤑🤣🤪🙄🤑🤪🤪🤪😍🙄😅🤔🥶😇🤪🤑🤔🤑😍🤣😍😍🙄🤔🥶🤔😇😅😅🤑🙄🥵🤑🤔🥵😅🥵😍😇😅🤪🤣😅😍🥵🥵🤣🤔😍🤣🤑🤪🙄🤣🥶🤑🙄🤑🤣🥶🤣🤣🥶🥵🤔😍😇🥵🤑🤪🤪🤑🤪🥶🤪🤪😅🥶😍🤔😍🥶🤑🥶🥶😅🤔🤪🤑🙄🤣🤔🤣🥶😅🤣🤑🤑🥵😍🥶🤣🤑🥵😇🤑🥶😍😇🥵🤑😇🙄😍🥶🤑😇🤔😍😍🤑🤣🤪🤔😅😇🤑🤑🥵🤔😅😍😍🤑🤪🙄🥵🥶🤣🤑😅🥶🤪🤣🤣🤑🤣🤑😅🤑🤑🤣🥵🤣🥶😅🙄🤣🥶🥵😍😅🤪🙄🤣🙄😍😍😇🤔🤣🤪🤑🤣🥵😍🥵🤑🤔🥵🤪🥶😍😍🤣🥵🥵🥵🙄🥶😍🥶🤑🤔🥵🤪🤑😅🙄🙄😇🤔🙄🙄🥵😇🥶😇😅😅🥶🥶🥶🥵🤪🤔🤪🥶🙄🤑😍😅🤣🤣🥵🤣🤑🥵😍😇🥵🤪🙄😅😅🥶🥵🤪🤪😅😍"
emoji = "🤪🥵"
EMOJIS = "🤣😅😇😍🤑🤔🥶🙄"
enc_17 = "🤣🥶🤑🥵😇🥶🥵😅🤪🤪😅🥵😍🤣🥵😇🤑🤔😍🤑😍😅🤔🤪🤔😍🤪🤑🥶😇🤔🥵🙄😅😇🤑🤣🥶🙄🤔🙄😇🥶🤣😍🥶🙄🥵🤔😍🤪🤑😍🥶🤪🥶🤔🤑🤣🤣🙄😇🥶😍🙄🙄🙄🥵🤣😅🤑🤣🤪🤔😍🤑🤪🥶🤔😇🤑🤪😍🤔🥶🤑🤪🥵🥶🤣🥵🤑🥶🤣🤑🥶😅🥵🥶🤣🤔🤣🤣🥵🙄🤪🤔🤑🤑🥵🥵🤣🤣😍😍🥶🤣🤔😅😇🤣🥵😇🤔😇🤣🥵🤪🤔😇😍😍🤔😇🙄🥵🤣🤪🤣🤪😇😇🥵🤣😍😍🥵🤑🙄🤑🥶🙄😍😇😇🤑🥶🙄🤑🙄😍😍🥶😅🥶🥶🥵😍🙄🤑🥶😅🤪🥶🥵🙄😅😍🤪🥶🥶🥶🤔🤪🤔🤔🤣😅😍😇🥵🤔🤑🤪🙄🤣🤑🥵🥶😅🤔🥵😇🥵🤪🥵🤔😅🤔🤔😅🥶😇🤣🥶🥶😇🥶🥵🥶😇🥵😍🙄🥵🥶🤣😇😍😅🥵🤑🤔🤪🤔😇🤣🤣🙄😇😍🥵🤑😇🤔🥶😍🤑🥶😅🤔🤑🤔🥶😅😇🤔🙄😍😇🤔🙄🤔😇😇🥵🙄🙄🙄😇😇😇🤣😅😅🤑🤔🤣🥶😇😍🤔🙄😇🥶🥵😍🤪🤣🤣🥵🤔🤣🤣🥵🤔🤪🥶🤑😅🤪🥵😅😇🤣😇😇🥵"
ct1 = "🥵😇🥵🤔😅🤣🤔😇🤔🤔😍🥶😇🤔😍🤑🤔😍😍😍😇😍😅🥵🥵😅🤣🥶🤑🙄🥶🤪😅😇🤣🤔🤣🤣🤪🤔🤑🤔🥵😇🤑😅🙄😇😇😇🤑🤔🙄🥶🤑🥵🤑🙄🤔🤔🤑😍🤣🤣😇🥵🤔😅😇🙄🤑🤪🥶🥵😍🥶😇😅🤔🤔🤪🤔🙄😇🤪😍🤣🤪🙄🤑🥵😇🤔🤑😅😇🥵🤣🙄🤔🙄🤣🤔🥶🤪🙄🥵🤑🥶😇🙄🤪🤔🤑🙄🥵🤪🤑🤪😇🥵😇🥵🥶🤔🥶🤔🙄🤔🥶🥶🤑🤣🤑😅😍😇😅🤑🤪🤪🤪🥶🤑🤣🤔😇😅🤔🥵😍🤑🤣😅😍😍😅🤪😅😅🙄🥶🤪🥶🤑🙄😅😍🥵🙄🥶😇🙄😇🤪🤔🤑🙄🤑🤣🤔🤣🙄🥵🥵🤪😅😇🤪🙄🤪😅🤪🤑🤣😅🤔🤔🥵😅🤣🥵🥵🙄🙄😅🤑🥶😇😅🤣🥵🥵🥵🤑🤪🥶😇🤔🤔🥶🤣🤑🥵🙄🥶🤔🙄🤣😇🤣🤑😇🥵🙄🤪😅🤪🤑😅😅🥶🤔🥶😇🙄🤑🤑🤑😅🤑🤪😅🤔🤔😅😅🥵😅🤑😍🤪🙄🤪🤔😇🥵🤑😅🙄😍🤔🥶😅🤔🤪😇🙄🥶😇🤔🤑🥶😍🥶🥶🥶😍🤪🥵🤑🤪😇😅🤪🥶😇😅😇🤪🤑🤔🙄😅🥵😇🤪😍🤑"
ct2 = "🥵🤪🥵🤪🤔🤣🥶😍🤪🤔🥶😍🙄🤑🙄🤪😅🤪🤔🤑🥶🤔🤪🥵🤣🤑🥵🥵😅🤔🥶🥶🙄🙄😍😇😇🤔😅🤣🥶😇🙄😍😍🤣🙄🤑😍🤣😇🥵🤑🤑😅🙄🤣🥶🤔😅🥶🤪🥶🤑😍🤣🙄🤔🤑😅😅🥵😅🤣🤣🤣🤑😍🥶😅😅😍🤪🥵🤔🤑🥶😍😅🥵🤣😍🥵😅🙄🥶🤪😅🤪🤔🤔🤣🤔🥵🤔😅🥶🤪🤣🤣😅🤣😍🤪🤑🙄😇🤪🙄🙄😇🤑😍🤣🤑🥶😍🤑😇😇😅🤔🤑😅😍🤣🤣😇😍🤣🤑😇😇🤑🙄😇🤪😇🤑🤔🥵🤑🤪🙄🥶🤪🥶🤣🥵🥶🤪😍🥵🥵🙄🤑🙄🥶🤪🥶🤔🤪😇🤣😇😅🥶😅🤪🤑🥵😅🥶🙄🤪🥵😇😍😇🤔🤪😍🤔🥶🙄🥵🤑🤑😅😅🤔🥶🥶🤑😍🥵🤔😇🥵🤑🙄🤑🤑😅🙄🙄🙄🥵🙄🥶🤪🥵🙄😍🤣🥶😍😍🤪😍🙄🤔😅🥶🥶😍🤪🥵🤪🤑🤣🤣😇🙄🤔🤔😍🤪🙄😍🤣🥶🥵😇🙄😇🤪🙄😍🙄🙄😍🥵😅🥶😍😍😅😇😍😅😅🤔🥶🤪🤪😅🥶🤣😇😍🥶🥶🤪🥵🤪🤔🤔😇🙄🤔🥶😇😅🤪🥵😍🥵🙄🤪😇🤪😍🤣🥶😇🥵😍😍"
EMOJIS = list( EMOJIS )
combos = itertools.permutations( EMOJIS )
for combo in combos:
    emo = emoji + "".join( combo )
    n_num = ""
    for i in n_1:
        n_num += str( emo.index( i ) )
    n_num = int( n_num ) + 1
    ct = ""
    for i in enc_17:
        ct += str( emo.index( i ) )
    ct = int( ct )
    if( pow( 17, e1, n_num ) == ct ):
        ct_1 = ""
        for i in ct1:
            ct_1 += str( emo.index( i ) )
        ct_2 = ""
        for i in ct2:
            ct_2 += str( emo.index( i ) )
        ct_1 = int( ct_1 )
        ct_2 = int( ct_2 )
        _, a, b = egcd( e1, e2 )
        m = ( pow( ct_1, a, n_num ) * pow( ct_2, b, n_num ) % n_num )
        pt = long_to_bytes( m )
        if( b"DH" in pt ):
            print( pt.decode() )
            break

>Flag : DH{0b77fa509d0da7233d1ce0c971f699f2fea1fc83ed358121cf45d476d67d4c30}
### Special RSA
#### Đề :

from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag

e = 257
P = bytes_to_long(flag)

while True:
    p = getPrime(1024)
    if (p - 1) % e**2 != 0 and (p - 1) % e == 0:
        break

q = getPrime(1024)

n = p * q

C = pow(P, e, n)

assert (q - 1) % e != 0
assert (p - 1) % e == 0
assert (p - 1) % e**2 != 0

print(f"p = {p}")
print(f"q = {q}")
print(f"e = {e}")
print(f"n = {n}")
print(f"C = {C}")

Parameter.txt

p = 102917468046616568070479080437602349605790044856847368227989900438678598347252242912474630778930183524103498634272903762436029311481137741713080659077027483465896792512517855786714336938418831349151567425537183094315541122606131460802382497841037179253750742567612375678233281962828108691356598122015035462931
q = 155409405226203238058015527018600466439894178201393804291867914008619674289107580497614221099756010997177702316412488380301911465872315087011512265127913696978059566003514595719636467623534496220114055190116473471302619324855013682151351145662146108598413909004492093001297173273875378143449965795752096407249
e = 257
n = 15994342496511457631852165745889134659106113775792815345660283109468603940964892042894072452338973417508989267182581106246598435022873385443407040336706693823717245966048048753547976289148494787906459582665400524599910456936861809339918570553400623639334162939976766980991427000240636672326892016855733342336543332550988035515870213111437557851461183289944204759548833820909869065701576126243727856888072220248575585769081790850141026448275329427960153467083111068539569641547854318739805365356286162575492346400298725777857883327406673789140613479637379861625904116837931896101781221369655018622189149174730619186819
C = 9616384404213524657863670808981125526907268432622976664325249394851244870192789713737122799469499856887739253362805246859649606786263701308805488844336941066141053596437114630658542913559798796936296332917154444568198618992503828589914317105542317632873299732945292007245940129956165369995868033142331830348424499649247621627957887323716236781832428323377989036111392368810898382355775057357502240259332598797482858241354811610086476550911065698726091155648159869780115791767209206584503973202288411298660473001567148602289414544500536763463431773097574512189310225492456529147806648758189442259263483402853811323777

#### Phân tích và ý tưởng
Điểm đặc biệt của bài là e = 257 và (p - 1) % e^2 != 0; (p - 1) % e == 0.
Khi đó $\gcd(\phi,e) \not= 1$ vì thế với kiểu mã hóa thông thường sẽ cho ra ciphertext nhưng khi giải mã thì sẽ ra được nhiều plaintext khác nhau.
Vì RSA trong bài này không được tạo theo cách chuẩn nên dùng phi sẽ không đúng, thay vào đó sẽ dùng carmichael $(\lambda)$.
Trong $\lambda$ có một e nên sẽ tách e bằng $\lambda'$ với $\lambda$=$\lambda'*e$, vậy $gcd(\lambda',e)=1$
Tìm plaintext đầu tiên bằng cách $m_0=C^d\pmod{n}$ ($d=e^{-1}\pmod{\lambda'}$), tìm các plaintext còn lại bằng cách nhận với một giá trị $L^i ( L = k^{\lambda'})$ với k là một số bất kì thỏa yêu cầu $L\not=1$, và 1<i<e.
Vì
$$
\begin{align}
(m_0*L^i)^e\pmod{n}=C*k^{i*\lambda'*e\pmod{n}}=C*k^{i\lambda}\pmod{n}=C\pmod{n}
\end{align}
$$
Vì thế cách làm là tìm L, brute e giá trị plaintext, kiểm tra điều kiện của flag là "BISC{" nằm ở đầu.
Tài liệu:
https://crypto.stackexchange.com/questions/81949/how-to-compute-m-value-from-rsa-if-phin-is-not-relative-prime-with-the-e
#### Script giải :

import math 
import random
from Crypto.Util.number import long_to_bytes
p = 102917468046616568070479080437602349605790044856847368227989900438678598347252242912474630778930183524103498634272903762436029311481137741713080659077027483465896792512517855786714336938418831349151567425537183094315541122606131460802382497841037179253750742567612375678233281962828108691356598122015035462931
q = 155409405226203238058015527018600466439894178201393804291867914008619674289107580497614221099756010997177702316412488380301911465872315087011512265127913696978059566003514595719636467623534496220114055190116473471302619324855013682151351145662146108598413909004492093001297173273875378143449965795752096407249
e = 257
n = 15994342496511457631852165745889134659106113775792815345660283109468603940964892042894072452338973417508989267182581106246598435022873385443407040336706693823717245966048048753547976289148494787906459582665400524599910456936861809339918570553400623639334162939976766980991427000240636672326892016855733342336543332550988035515870213111437557851461183289944204759548833820909869065701576126243727856888072220248575585769081790850141026448275329427960153467083111068539569641547854318739805365356286162575492346400298725777857883327406673789140613479637379861625904116837931896101781221369655018622189149174730619186819
C = 9616384404213524657863670808981125526907268432622976664325249394851244870192789713737122799469499856887739253362805246859649606786263701308805488844336941066141053596437114630658542913559798796936296332917154444568198618992503828589914317105542317632873299732945292007245940129956165369995868033142331830348424499649247621627957887323716236781832428323377989036111392368810898382355775057357502240259332598797482858241354811610086476550911065698726091155648159869780115791767209206584503973202288411298660473001567148602289414544500536763463431773097574512189310225492456529147806648758189442259263483402853811323777

carmichael = ( p - 1 ) * ( q - 1 ) // math.gcd( p - 1, q - 1 )
car = carmichael // e
while 1:
    k = random.randint( 1, e )
    L = pow( k, car, n )
    if( L != 1 ):
        break
for i in range( e ):
    d = pow( e, -1, car )
    m = pow( C, d, n ) * pow( L, i, n ) % n
    flag = long_to_bytes( m )
    if( b"BISC" in flag ):
        print( flag.decode() )
        break

>Flag: BISC{special_parameter_for_https://crypto.stackexchange.com/questions/81949/how-to-compute-m-value-from-rsa-if-phin-is-not-relative-prime-with-the-e_ed9fd3b21b8190eb2bd91c56c996e362bfbeeeccdc5ff9692f521127e6193d1f}
## Bonus
### AlpacaHACK Round 2
#### Đề :

from math import gcd
import os
from Crypto.Util.number import getPrime, bytes_to_long
 
e = 19
while True:
    p = getPrime(2048)
    q = getPrime(2048)
    if gcd((p - 1) * (q - 1), e) == 1:
        break
n = p * q
 
flag = os.environ.get("FLAG", "Alpaca{**** REDACTED ****}")
assert len(flag) == 26 and flag.startswith("Alpaca{") and flag.endswith("}")
 
m = bytes_to_long((flag * 1337).encode())
c = pow(m, e, n)
 
print(f"{n = }")
print(f"{e = }")
print(f"{c = }")
'''
n = 434245275129793896913302623186216967500119715299127153234221039838158526818290666891561167619572507897277032319251523352710966722158326513857889678449160348496647427753832233179173745189495799707833020232209447520485615893168704144655033371807912826948460011240258726843346618328839282439390863464375320181495406806870462330735361196286553150480225927729088313551861682406252457739974850015509783430978939475350707211461876140420181118923743456062581297038004651412953310377554877499792225388059857865550418697212704277742826280689987165702071346542831836616149138379224837551040036947064990027047482745931141458056028719767845142490618375017582275824317241572815337810658684051187938258804346960781372035972758516593800419459342799854863845667715099378564373594732798224797622583907677749880918106223965727445907355069025939554400938193579295415911074889648122298896605189398591684277376327938718166279159875826993866460251900514487349848332991005775574378131897581182876147580659857596204121970624162722935263271888969020482566142620134100258216288390250174699829806817678453601913377347867137739622906815272561714188564065071077762169177825466514512198167566882661748389120146622447920498988341055543170346944366105037929197965527
e = 19
c = 78338816976998323261765735600063671710448529902850366859501110834174319629348492230679353792803618614020892663940158627385470036549819116375194598599193512981265682997072278631964394686243958989105159463105190885437258093111178664394786430767942639437287236999171486583513816766766869843448941665224796216610702708658300011987744401747551989248270799179750556330952646223694000679475842632497149402602469848595868051660228892506097962300820851000134370939783634534516434054009303981106884637932006844265722691022870174977860945699441650254771777451995160642261482879537396171107016491225773397809485749640163676209732235156461483660111845782227127763086286553520914359194795617080980736767821995556156173267185240945707717461037831992544868933876015548419376861213017988005848033349136839971120363078490938026883354839573512645985195570831018461470031329716026531550172207332072481279548470657090575709419245114386419567236219816237412255505882075283974654569995321334498673793010812162088796252555619242463561750801895032793870706949913548310632113206159695535952422316840587214237406730422405058644629458566515378607614900910335034732797410592671297941526063690060922625005949094383664832255082556088451940780657576420871470920836
'''

#### Phân tích và ý tưởng
Độ dài của flag là 26 bytes và flag được nhân thêm 1337 trước khi chuyển sang số nguyên và đưa vào RSA.
Khi nhân chuỗi với một số nguyên thì chuỗi đó sẽ lặp lại theo số lần của số đó.
Lặp lại đoạn chuỗi thực chất là phép dịch bit và nhập lại thành string.
Ví dụ "AAA" khi chuyển sang số nguyên sẽ là $55*256^0+55*256^1+55*256^2$
Ta có thể nhận ra được công thức để tính số nguyên đó là $val*\sum{256^{n-1}}$ với n chạy từ 1 đến độ dài của chuỗi, val là giá trị thập phân của byte đó.
Vậy với block lặp lại thì sao?
Ví dụ trên xét trên 1 byte riêng lẻ lặp lại thì độ dài của chuỗi được lặp là 1 byte. Nếu block dài l bytes thì có công thức $val*\sum{256^{l*(n-1)}}$ với val là giá trị thập phân của block bị lặp, n chạy từ 1 đến len( string ) // len( block ) tức số lượng block trong chuỗi.
Theo đề thì độ dài của flag là 26 bytes, flag được lặp lại 1337 lần thì len( block ) = 26 và có 1337 block trong chuỗi lớn.
Sử dụng công thức trên để tìm ra $x*z$ với x là val còn z là tổng sigma, ta được
$$c=m^e\pmod{n}=(x*z)^e\pmod{n}=x^e*z^e\pmod{n}$$
Và nếu $GCD(z^e,n)=1$ thì tồn tại nghịch đảo modulo
$$c*z^{-e}=x^e\pmod{n}$$
Vì e = 19 ( nhỏ ) và x có độ lớn là 26 bytes còn n tận 2048 bytes nên $x^e$ sẽ luôn nhỏ hơn n, có thể tính căn bậc 19 mà không cần quan tâm đến mod n.
#### Script :

from Crypto.Util.number import long_to_bytes, bytes_to_long
from gmpy2 import iroot
import math
n = 434245275129793896913302623186216967500119715299127153234221039838158526818290666891561167619572507897277032319251523352710966722158326513857889678449160348496647427753832233179173745189495799707833020232209447520485615893168704144655033371807912826948460011240258726843346618328839282439390863464375320181495406806870462330735361196286553150480225927729088313551861682406252457739974850015509783430978939475350707211461876140420181118923743456062581297038004651412953310377554877499792225388059857865550418697212704277742826280689987165702071346542831836616149138379224837551040036947064990027047482745931141458056028719767845142490618375017582275824317241572815337810658684051187938258804346960781372035972758516593800419459342799854863845667715099378564373594732798224797622583907677749880918106223965727445907355069025939554400938193579295415911074889648122298896605189398591684277376327938718166279159875826993866460251900514487349848332991005775574378131897581182876147580659857596204121970624162722935263271888969020482566142620134100258216288390250174699829806817678453601913377347867137739622906815272561714188564065071077762169177825466514512198167566882661748389120146622447920498988341055543170346944366105037929197965527
e = 19
c = 78338816976998323261765735600063671710448529902850366859501110834174319629348492230679353792803618614020892663940158627385470036549819116375194598599193512981265682997072278631964394686243958989105159463105190885437258093111178664394786430767942639437287236999171486583513816766766869843448941665224796216610702708658300011987744401747551989248270799179750556330952646223694000679475842632497149402602469848595868051660228892506097962300820851000134370939783634534516434054009303981106884637932006844265722691022870174977860945699441650254771777451995160642261482879537396171107016491225773397809485749640163676209732235156461483660111845782227127763086286553520914359194795617080980736767821995556156173267185240945707717461037831992544868933876015548419376861213017988005848033349136839971120363078490938026883354839573512645985195570831018461470031329716026531550172207332072481279548470657090575709419245114386419567236219816237412255505882075283974654569995321334498673793010812162088796252555619242463561750801895032793870706949913548310632113206159695535952422316840587214237406730422405058644629458566515378607614900910335034732797410592671297941526063690060922625005949094383664832255082556088451940780657576420871470920836

mul = 0
for i in range( 1337 ):
    mul += 256 ** ( 26 * i )  
if( gcd( mul, n ) == 1 ):
    mul = pow( mul, - e, n )
    c = c * mul % n
    m, check = iroot( c, e )
    if( check ):
        print( long_to_bytes( int(m) ).decode() )
    else:
        print("haha")