What is RSA? Really Spicy Applesauce? Ridiculously Smart Alpaca? Random Squirrel Alliance? Nope, not at all. Just some dudes who made a cool public-key cryptosystem!
Author: Gary
Attachment: chal.py
from Crypto.Util.number import getStrongPrime, getPrime, bytes_to_long as b2l
FLAG = open('flag.txt', 'r').read().strip()
OUT = open('output.txt', 'w')
l = len(FLAG)
flag1, flag2, flag3 = FLAG[:l//3], FLAG[l//3:2*l//3], FLAG[2*l//3:]
# PART 1
e = 0x10001
p = getStrongPrime(1024)
q = getStrongPrime(1024)
n = p*q
ct = pow(b2l(flag1.encode()), e, n)
OUT.write(f'*** PART 1 ***\ne: {e}\np: {p}\nq: {q}\nct: {ct}')
# PART 2
e = 3
p = getStrongPrime(1024)
q = getStrongPrime(1024)
n = p*q
ct = pow(b2l(flag2.encode()), e, n)
OUT.write(f'\n\n*** PART 2 ***\ne: {e}\nn: {n}\nct: {ct}')
# PART 3
e = 65537
p = getPrime(24)
q = getPrime(24)
n = p*q
fl = round(len(flag3)/4)
f3_parts = [flag3[i:i+4] for i in range(0, len(flag3), 4)]
assert ''.join(f3_parts) == flag3
ct_parts = []
for part in f3_parts:
pt = b2l(part.encode())
assert pt < n
ct = pow(pt, e, n)
ct_parts.append(ct)
OUT.write(f'\n\n*** PART 3 ***\ne: {e}\nn: {n}\nct: {ct_parts}')
Ở bài này mình sẽ phân tích từng part. Trước hết là part 1:
# PART 1
e = 0x10001
p = getStrongPrime(1024)
q = getStrongPrime(1024)
n = p*q
ct = pow(b2l(flag1.encode()), e, n)
OUT.write(f'*** PART 1 ***\ne: {e}\np: {p}\nq: {q}\nct: {ct}')
Part 1 này, mình được cung cấp 3 dữ liệu là e, p, q và c. Mọi thứ cơ bản đã có sẵn, việc chúng ta cần chỉ là tính n = p * q, tính phi = (p-1)*(q-1) và d = e^-1 (mod phi). Cuối cùng, giải mã c bằng công thức m = c^d (mod n).
Tiếp theo đến part 2. Ở đây chúng ta được cung cấp e, n và c.
# PART 2
e = 3
p = getStrongPrime(1024)
q = getStrongPrime(1024)
n = p*q
ct = pow(b2l(flag2.encode()), e, n)
OUT.write(f'\n\n*** PART 2 ***\ne: {e}\nn: {n}\nct: {ct}')
Dù chỉ có 2 dữ kiện nhưng việc e = 3, một số rất nhỏ đã tạo nên lỗ hổng small e. Để dễ hình dung:
e = 3 <=> c = m^3 (mod n) | ==> m = c^1/3
Do m nhỏ => m^3 < n |
Vậy là đơn giản chỉ cần căn bậc 3 của c, ta sẽ giải mã được part 2. Lưu ý hàm long_to_bytes của thư viện Crypto chỉ dùng với Integer, nên mình sẽ dùng hàm real_root của thư viện Sympy.
# PART 3
e = 65537
p = getPrime(24)
q = getPrime(24)
n = p*q
fl = round(len(flag3)/4)
f3_parts = [flag3[i:i+4] for i in range(0, len(flag3), 4)]
assert ''.join(f3_parts) == flag3
ct_parts = []
for part in f3_parts:
pt = b2l(part.encode())
assert pt < n
ct = pow(pt, e, n)
ct_parts.append(ct)
OUT.write(f'\n\n*** PART 3 ***\ne: {e}\nn: {n}\nct: {ct_parts}')
Ở đây thì message bị chia ra làm các part và mã hóa từng part. Mình được cung cấp đủ e, n và c của chúng. Để giải mã được bằng công thức m = c^d (mod n) thì chúng ta cần tính được d thông qua p,q. Để ý ở đây n là một số nguyên tố không lớn, ta có thể factor nó ra và lấy từng cặp giá trị cho p,q. Với bài này thì sau khi factor chỉ ra 2 giá trị duy nhất, nên mình sẽ gán nó là p,q luôn và tiến hành giải mã
e3 = 65537
p3 = 8885719
q3 = 12121807
d3 = inverse(e3, (p3-1)*(q3-1))
n3 = p3 * q3
c_parts = [18128889449669, 12202311999558, 10705744036504, 23864757944740]
m_parts = [long_to_bytes(pow(ct, d3, n3)) for ct in c_parts]
m3 = ''.join([pt.decode('utf-8') for pt in m_parts])
Tiến hành ghép kết quả 3 part với nhau, mình ra được flag. Full solution python: RSAIntro
Flag: flag{361862d054e2a9abe41cc315517cfa31}
RSA Outro
I didn't feel like fitting this one in the RSA Intro, so here is an RSA Outro!
Author: Gary
Attachment: chal.py
from Crypto.Util.number import getStrongPrime, isPrime, inverse, bytes_to_long as b2l
FLAG = open('flag.txt', 'r').read()
# safe primes are cool
# https://en.wikipedia.org/wiki/Safe_and_Sophie_Germain_primes
while True:
q = getStrongPrime(512)
p = 2*q + 1
if (isPrime(p)):
break
n = p*q
phi = (p-1)*(q-1)
e = 0x10001
d = inverse(e, phi)
pt = b2l(FLAG.encode())
ct = pow(pt,e,n)
open('output.txt', 'w').write(f'e: {e}\nd: {d}\nphi: {phi}\nct: {ct}')
output.txt
e = 65537
d = 53644719720574049009405552166157712944703190065471668628844223840961631946450717730498953967365343322420070536512779060129496885996597242719829361747640511749156693869638229201455287585480904214599266368010822834345022164868996387818675879350434513617616365498180046935518686332875915988354222223353414730233
phi = 245339427517603729932268783832064063730426585298033269150632512063161372845397117090279828761983426749577401448111514393838579024253942323526130975635388431158721719897730678798030368631518633601688214930936866440646874921076023466048329456035549666361320568433651481926942648024960844810102628182268858421164
ct = 37908069537874314556326131798861989913414869945406191262746923693553489353829208006823679167741985280446948193850665708841487091787325154392435232998215464094465135529738800788684510714606323301203342805866556727186659736657602065547151371338616322720609504154245460113520462221800784939992576122714196812534
Ở đây q là một số nguyên tố 512-bit, khá lớn để có thể sử dụng các cách như factor hay divisor. Tuy nhiên ở bài này sử dụng phép toán để gán giá trị cho p là p = 2*q + 1. Điều này vô tình tạo nên điểm yếu cho thuật toán RSA này. Do đã biết giá trị của phi, nên ta có thể làm như sau:
Phép toán trên là một phương trình bậc 2 một ẩn, ta hoàn toàn có thể tính được q rồi tính ngược lại p. Lúc này, mọi chuyện còn lại không có gì khó khăn nữa. Mình sẽ sử dụng hàm solve thư viện Sympy cho công việc này.
from Crypto.Util.number import isPrime, long_to_bytes
from sympy import symbols, Eq, solve
e = 65537
d = 53644719720574049009405552166157712944703190065471668628844223840961631946450717730498953967365343322420070536512779060129496885996597242719829361747640511749156693869638229201455287585480904214599266368010822834345022164868996387818675879350434513617616365498180046935518686332875915988354222223353414730233
phi = 245339427517603729932268783832064063730426585298033269150632512063161372845397117090279828761983426749577401448111514393838579024253942323526130975635388431158721719897730678798030368631518633601688214930936866440646874921076023466048329456035549666361320568433651481926942648024960844810102628182268858421164
ct = 37908069537874314556326131798861989913414869945406191262746923693553489353829208006823679167741985280446948193850665708841487091787325154392435232998215464094465135529738800788684510714606323301203342805866556727186659736657602065547151371338616322720609504154245460113520462221800784939992576122714196812534
q = symbols('q')
phi = 245339427517603729932268783832064063730426585298033269150632512063161372845397117090279828761983426749577401448111514393838579024253942323526130975635388431158721719897730678798030368631518633601688214930936866440646874921076023466048329456035549666361320568433651481926942648024960844810102628182268858421164
equation = Eq(2*q**2 - 2*q - phi, 0)
solution = solve(equation, q)
for sol in solution:
if isPrime(int(sol)):
q = int(sol)
p = 2*q + 1
n = p*q
m = long_to_bytes(pow(ct,d,n)).decode()
print(m)
