چالش رمزنگاری اول - اشک غماز من

توضیحات

توضیحات این سوال شامل دو پرونده بوده است که از اینجا و اینجا در دسترس است.

حل چالش

پرونده‌های مربوط به این سوال یک کلید عمومی با قالب pem و پرونده‌ای به نام خروجی شامل یک عبارت رمزشده از همین اسکریپت است.

برای استخراج کلید عمومی به صورت عددی از پرونده‌ی pem از کد زیر استفاده می‌کنیم:

from Crypto.PublicKey import RSA
pubkey = RSA.importKey(open('pubkey.pem', 'r').read())
n = pubkey.n

که عدد به عدد زیر می‌رسیم:

21624454309208755040696118287676727541296763690680123936902297640391387560880782562531
786027768955448969632703538166395779658858561640465578530405353007148896631722573457417

البته می‌توان به صورت مستقیم از کتابخانه openssl برای خواندن کلید استفاده کرد:

openssl rsa -in pubkey.pem -text -inform PEM -pubin

که خروجی آن به شکل زیر است:

$ openssl rsa -in pubkey.pem -text -inform PEM -pubin
Public-Key: (573 bit)
Modulus:
    16:61:e8:3b:75:44:a1:dc:be:c3:0f:4b:18:8d:0d:
    04:8c:86:ea:c3:5d:87:74:cf:fe:45:5f:af:c3:81:
    d3:4b:9c:91:0b:28:b6:63:14:bc:87:61:57:03:4a:
    c1:17:b0:c7:48:59:40:ff:45:79:34:14:72:e0:16:
    ff:5d:3d:40:c9:8d:79:b5:7b:86:68:09
Exponent: 65537 (0x10001)
writing RSA key
-----BEGIN PUBLIC KEY-----
MGMwDQYJKoZIhvcNAQEBBQADUgAwTwJIFmHoO3VEody+ww9LGI0NBIyG6sNdh3TP
/kVfr8OB00uckQsotmMUvIdhVwNKwRewx0hZQP9FeTQUcuAW/109QMmNebV7hmgJ
AgMBAAE=
-----END PUBLIC KEY-----

این خروجی به ما می‌گوید که کلید عمومی ۵۳۷ بیتی و هم‌چنین e = 65537 است و البته n را به صورت هگزادسیمال نیز خروجی می‌دهد.

از آن‌جایی که اطلاعات زیادی در این سوال در دست نیست و آسیب‌پذیری دیگری به جز تجزیه‌پذیر بودن عدد n به علت کم بودن تعداد بیت‌های آن، در گام اول به نظر نمی‌رسد، با استفاده از کد زیر تلاش می‌کنیم این عدد را تجزیه کنیم:

import gmpy2
def fermat_factor(n):
    assert n % 2 != 0
    a = gmpy2.isqrt(n)
    b2 = gmpy2.square(a) - n

    while not gmpy2.is_square(b2):
        a += 1
        b2 = gmpy2.square(a) - n

    p = a + gmpy2.isqrt(b2)
    q = a - gmpy2.isqrt(b2)

    return int(p), int(q)

p, q = fermat_factor(n)

البته می‌توان از سایت‌های تجزیه‌ی عدد هم استفاده کرد به طور مثال این سایت که البته زمانی در حدود ۳۰ دقیقه یا کمی بیش‌تر طول می‌کشد تا عدد تجزیه شود! در نهایت اگر خودتان عدد را تجزیه کنید به دو عدد و اگر از سایت آن را تجزیه کنید به سه عدد می‌رسید:

p = 147052556282469143075987409214410668986784067005985790199654610587514528368007503848109
q = 147052556282469143075987409214410668986783067005985790199654610587514528368007503848013

که عدد دوم خودش اول نیست و تجزیه می‌شود به اعداد زیر:

q1 = 11703015632802739555916477103806485281823807
q2 = 12565355878897661791812311007679668227526259

حال باید مقدار phi را محاسبه کنیم:

phi = (p1 - 1) * (p2 - 1) * (p3 - 1)

اگر از طریق سایت عدد را تجزیه کرده باشید خودش این مقدار را نیز محاسبه می‌کند.

در نهایت باید d را به شکل زیر محاسبه کنیم:

from Crypto.Util.number import *
from Crypto.PublicKey import RSA
e = 65537
phi = 21624454309208755040696118287676727541296760121954056328708268471310782508508722406638591742126131269150041915799881878542127974159780141510871776073394683145009669509682384
enc = 4260374773134132438689258664455079137066561145252409125458105203295494666452101159367658719685941660887403148860701161120659520178777342295281622045201732188805806929134405
n = 21624454309208755040696118287676727541296763690680123936902297640391387560880782562531786027768955448969632703538166395779658858561640465578530405353007148896631722573457417

d = inverse(e, phi)
print(long_to_bytes(pow(enc, d, n)))

که منجر به رسیدن به پرچم زیر می‌شود:

parcham{I_L0v3__p43R__4Nd_____RSA_____}