[ شرح ] حل تحدي bAby_rSA من مسابقة TTUCTF المقامه في جامعه الطفيله التقنيه

[SARAHSARAH is verified member.]

اول اشي بنعرض ملفات التحدي


description

I wanted to raise the power of a number, but my friend picked a number to put in the equation int("9" * 1000)

but

My friend's number is bigger than everything...even if another number is raised to a power it (My friend's number) is still huge

code.py

import math
from Crypto.Util.number import *

# p and q consist of 15 digits
p = 366652997......
q = 926782929......
n = p * q
e = 7
phi = ( p - 1 ) * (q - 1 )

m = bytes_to_long(b"TTUCTF{r5A

o2 = 36861728689062005922079472777522260642618880598666338535731
m = int(m / o2) # m mod o2 == 0
print("c =" , pow(m,e,n))

x = ??
# If you know the value of x in range (47,53) Search manually...

k = pow((p - 1) , x , int("9" * 1000))
l = pow((q + 1) , x , int("9" * 1000))

print("k =" , k)
print("l =" , l)

output.txt

c = 311913313541165347372338283513
k = 163215726038713706989303647202033813645656998721543259773716955657012777001268130391390337238803033531298800406273193471792517987655733198024052623295990627680047932855450905833612355053222129266244897458798107424636949257267538463481106742627778551880169706371109273488541086719441064673434510966061295060106777276283596345721682333625355355301263665402761829008707748571859919234952755203896556877605897112652874533509643603149649407222415013720382770201796615663941476197080525214619330481679165262067227009142818461236173238265736794147415707673483980537693113730323824816643471707227661325849801684556166966783171610575891637750703167580778938949676377613702776550081118365942918745441127133906376446240753169401705738010624
l = 22330646905727778425635861987069204693215970647562903916876004162496159529518859015558170558031262035907153330872961135722376390948852891725435071183940360278565929635687183617052079231961950215282311720415612754844622706742909303234455865864979682591897660681126883478584603323934231497632933373005498700493328277824406083414380485576686901746940334376226382246559420803020679840747685377636787506274763880791139386073106571543141282932745813402305238355842655089697799341016628143259309379348741857056408635522117422908816590175132226230786839667450612026309747355213805870264753210975572503460096313340144017677260036955239504477394642004832783781349896149175741154621045322429396182383646214225605580360145491238182572304357590700798722780954624

---

الحل​

اول اشي بنفهمه من الوصف انه بحكي عن هدول السطرين من الكود

k = pow((p - 1) , x , int("9" * 1000))
l = pow((q + 1) , x , int("9" * 1000))

بنفهم من الوصف انه القيمة int("9" * 1000) كبيرة وهي مبينة معنا وبنقدر نعرف برضو انها اكبر من (q + 1) قوة x من الوصف يعني بنستنتج انه اي اشي صغير mode كبير بعطينا الصغير نفسه يعني ما الها قيمة اصلا الـ int("9" * 1000) ف بنمحيها وبنخلي العملية بس قوة
الـ pow بتساوي

pow( A , B ,C ) == A ^ B mod C

وزي ما طلع بالهنت انه

هاي القيمة
pow((p - 1) , x , int("9" * 1000))
هي نفسها هاي القيمة
(p - 1) ^ x

اللي معنى الوصف


الان بنشوف انه معنا قيم p and q لكن ناقصات

p = 366652997......
q = 926782929......

ومعطينا انه كل وحدة منهم 15 رقم

بنعمل فور لوب من القيمة هاي 366652997000000 اللي هي الرقم اللي بنعرفه وبنحط باقي القيم صفار عشان يبدا من اقل قيمة ممكن تكون هي قيمة الـ p وبنخلي الفور لوب تخلص للـ 366652998000000 اللي هي اعلا قيمة ممكن تكون هي القيمة يعني زدا واحد على اخر رقم كان 7 خليناه 8 ف هيك راح يجرب كل القيم الممكنة لـ p وبنعمل نفس الاشي للـ q ف بصفي عننا

for p in range(366652997000000, 366652998000000):
        for q in range(926782929000000, 926782930000000):

هسا بنحط الشرط اللي يتأكد اذا كانت الـ p والـ q صح
هو معطينا بالسؤال
k = (p - 1) ** x
l = ( q + 1 ) ** x

معطينا قيمة الـ x ومعطينا قيمة الـ k ف بنخليه يعمل العملية هاي k = (p - 1) ** x اللي هي من السؤال ويتأكد اذا طابقت القيمة اللي معطينا اياها if k == k2

وبنعمل نفس الاشي للـ q ف بصفي عننا

for p in range(366652997000000, 366652998000000):
    k = (p - 1) ** x
    if k == k2:
        for q in range(926782929000000, 926782930000000):
            l = ( q + 1 ) ** x
            if l == l2:

اخر اشي صار معنا القيم الـ p والـ q بنطبق الخوارزمية rsa وهي شرحها

شرح 3b0-0d

الموضوع 'شرح خوارزمية الـ RSA بالتفصيل وتطبيق عملي من موقع Crypto hack + التلخيص للفيديو كامل 👇'

4 يناير 2024

​

---

الشرح + Note​

---

​

• 3b0-0d
• الردود: 2
• المنتدى: قسم التشفير | Cryptography 🔐

• 

اخر اشي بنكتب هاد السطر وشرحه كالاتي

print(long_to_bytes(pow(c, inverse(e, (p - 1) * (q - 1)), p * q) * o2).decode())

بنبدا من جوا

pow( c , inverse( e , (p - 1) * (q - 1) )  , p * q)
phi =  (p - 1) * (q - 1)

so...

pow( c , inverse( e , phi )  , p * q)
d = inverse( e , phi )

so...

pow( c , d  , p * q)
n = p * q

so...

m = pow( c , d  , n)  >> in RSA

اخر اشي بنضرب قيمة m بالقيمة o2 لانه بالسؤال قسم قيمة m على الـ o2 وحكالنا انه مافي باقي قسمة m mod o2 == 0 #


بصفي معنا الكود كامل

from Crypto.Util.number import *

e = 7
c = 311913313541165347372338283513
k2 = 163215726038713706989303647202033813645656998721543259773716955657012777001268130391390337238803033531298800406273193471792517987655733198024052623295990627680047932855450905833612355053222129266244897458798107424636949257267538463481106742627778551880169706371109273488541086719441064673434510966061295060106777276283596345721682333625355355301263665402761829008707748571859919234952755203896556877605897112652874533509643603149649407222415013720382770201796615663941476197080525214619330481679165262067227009142818461236173238265736794147415707673483980537693113730323824816643471707227661325849801684556166966783171610575891637750703167580778938949676377613702776550081118365942918745441127133906376446240753169401705738010624
l2 = 22330646905727778425635861987069204693215970647562903916876004162496159529518859015558170558031262035907153330872961135722376390948852891725435071183940360278565929635687183617052079231961950215282311720415612754844622706742909303234455865864979682591897660681126883478584603323934231497632933373005498700493328277824406083414380485576686901746940334376226382246559420803020679840747685377636787506274763880791139386073106571543141282932745813402305238355842655089697799341016628143259309379348741857056408635522117422908816590175132226230786839667450612026309747355213805870264753210975572503460096313340144017677260036955239504477394642004832783781349896149175741154621045322429396182383646214225605580360145491238182572304357590700798722780954624
o2 = 36861728689062005922079472777522260642618880598666338535731
x = 50


for p in range(366652997000000, 366652998000000):
    k = (p - 1) ** x
    if k == k2:
        for q in range(926782929000000, 926782930000000):
            l = ( q + 1 ) ** x
            if l == l2:
                m = print(long_to_bytes(pow(c, inverse(e, (p - 1) * (q - 1)), p * q) * o2).decode())

مشاهدة المرفق 12435​

الله يعطيكِ الف عافية

 

[Řanda]

بارك الله فيك وجزاك الله كل خير
ننتظر جديدك دائما

اجمعين
باذن الله

 

[Řanda]

الله يعطيكِ الف عافية

الله يعافيكِ

 

[Řanda]

الله يعطيك الف عافية

الله يعافيكِ