Cryptography – 360 pts (219 solves) – Chall author: qopruzjf
Having many bits in your RSA modulus sounds great, but its security is defined by its generation. And let me tell you, using a load of small primes is not the way too go! The modulus can easily be factored and hence the ciphertext decrypted.
Check out write-ups by my teammates on K3RN3L4RMY.com
Exploration
For this challenge we receive the source code and its output as follows.
from Crypto.Util.number import getPrime, bytes_to_long
from private import flag
def prod(lst):
ret = 1
for num in lst:
ret *= num
return ret
m = bytes_to_long(flag)
primes = [getPrime(32) for _ in range(128)]
n = prod(primes)
e = 65537
print(n)
print(pow(m, e, n))
n = 50630448182626893495464810670525602771527685838257974610483435332349728792396826591558947027657819590790590829841808151825744184405725893984330719835572507419517069974612006826542638447886105625739026433810851259760829112944769101557865474935245672310638931107468523492780934936765177674292815155262435831801499197874311121773797041186075024766460977392150443756520782067581277504082923534736776769428755807994035936082391356053079235986552374148782993815118221184577434597115748782910244569004818550079464590913826457003648367784164127206743005342001738754989548942975587267990706541155643222851974488533666334645686774107285018775831028090338485586011974337654011592698463713316522811656340001557779270632991105803230612916547576906583473846558419296181503108603192226769399675726201078322763163049259981181392937623116600712403297821389573627700886912737873588300406211047759637045071918185425658854059386338495534747471846997768166929630988406668430381834420429162324755162023168406793544828390933856260762963763336528787421503582319435368755435181752783296341241853932276334886271511786779019664786845658323166852266264286516275919963650402345264649287569303300048733672208950281055894539145902913252578285197293
ct = 15640629897212089539145769625632189125456455778939633021487666539864477884226491831177051620671080345905237001384943044362508550274499601386018436774667054082051013986880044122234840762034425906802733285008515019104201964058459074727958015931524254616901569333808897189148422139163755426336008738228206905929505993240834181441728434782721945966055987934053102520300610949003828413057299830995512963516437591775582556040505553674525293788223483574494286570201177694289787659662521910225641898762643794474678297891552856073420478752076393386273627970575228665003851968484998550564390747988844710818619836079384152470450659391941581654509659766292902961171668168368723759124230712832393447719252348647172524453163783833358048230752476923663730556409340711188698221222770394308685941050292404627088273158846156984693358388590950279445736394513497524120008211955634017212917792675498853686681402944487402749561864649175474956913910853930952329280207751998559039169086898605565528308806524495500398924972480453453358088625940892246551961178561037313833306804342494449584581485895266308393917067830433039476096285467849735814999851855709235986958845331235439845410800486470278105793922000390078444089105955677711315740050638
The most interesting thing here is that the RSA modulus is created with 128 smaller primes as opposed the usual two large primes. The smaller the primes used, the easier it is to recover them from the modulus, regardless of the size of the modulus. So let’s try to factor the modulus to recover the used 128 32-bit primes.
Exploitation
My first go-to is Alpertron for integer factorisation (not sponsored). It was able to quickly dismantle our 4096-bit modulus into 128 32-bit primes. From the recovered primes we can follow the steps of RSA key generation to recover the secret exponent ‘d’ and recover the plaintext message. Here is the script I used.
# Factorisation from Alpertron
pstr = "2148 630611 × 2157 385673 × 2216 411683 × 2223 202649 × 2230 630973 × 2240 170147 × 2278 427881 × 2293 226687 × 2322 142411 × 2365 186141 × 2371 079143 × 2388 797093 × 2424 270803 × 2436 598001 × 2444 333767 × 2459 187103 × 2491 570349 × 2510 750149 × 2525 697263 × 2572 542211 × 2575 495753 × 2602 521199 × 2636 069911 × 2647 129697 × 2657 405087 × 2661 720221 × 2672 301743 × 2682 518317 × 2695 978183 × 2703 629041 × 2707 095227 × 2710 524571 × 2719 924183 × 2724 658201 × 2733 527227 × 2746 638019 × 2752 963847 × 2753 147143 × 2772 696307 × 2824 169389 × 2841 115943 × 2854 321391 × 2858 807113 × 2932 152359 × 2944 722127 × 2944 751701 × 2949 007619 × 2959 325459 × 2963 383867 × 3012 495907 × 3013 564231 × 3035 438359 × 3056 689019 × 3057 815377 × 3083 881387 × 3130 133681 × 3174 322859 × 3177 943303 × 3180 301633 × 3200 434847 × 3228 764447 × 3238 771411 × 3278 196319 × 3279 018511 × 3285 444073 × 3291 377941 × 3303 691121 × 3319 529377 × 3335 574511 × 3346 647649 × 3359 249393 × 3380 851417 × 3398 567593 × 3411 506629 × 3417 563069 × 3453 863503 × 3464 370241 × 3487 902133 × 3488 338697 × 3522 596999 × 3539 958743 × 3589 083991 × 3623 581037 × 3625 437121 × 3638 373857 × 3646 337561 × 3648 309311 × 3684 423151 × 3686 523713 × 3716 991893 × 3721 186793 × 3760 232953 × 3789 253133 × 3789 746923 × 3811 207403 × 3833 706949 × 3833 824031 × 3854 175641 × 3860 554891 × 3861 767519 × 3865 448239 × 3923 208001 × 3941 016503 × 3943 871257 × 3959 814431 × 3961 738709 × 3978 832967 × 3986 329331 × 3991 834969 × 3994 425601 × 4006 267823 × 4045 323871 × 4056 085883 × 4073 647147 × 4091 945483 × 4098 491081 × 4135 004413 × 4140 261491 × 4141 964923 × 4152 726959 × 4198 942673 × 4205 028467 × 4218 138251 × 4227 099257 × 4235 456317 × 4252 196909 × 4270 521797 × 4276 173893".replace(' ','').split('×')
# Convert string to integer
plst = [int(p) for p in pstr]
# Calculate secret exponent d
e = 0x10001
f = 1
for p in plst:
f *= (p-1)
d = inverse(e,f)
# Recover plaintext message
m = pow(c,d,n)
print(long_to_bytes(m))
Ta-da!
corctf{to0_m4ny_pr1m3s55_63aeea37a6b3b22f}
PREVIOUSRACTF 2021 - Military Grade