Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [An toàn thông tin] RSA cơ bản: giải mã từng ký tự

    RSA là hệ mật mã khóa công khai kinh điển. Với hai số nguyên tố p,qp, qp,q, ta tính n=p⋅qn = p \cdot qn=p⋅q và φ(n)=(p−1)(q−1)\varphi(n) = (p-1)(q-1)φ(n)=(p−1)(q−1). Số mũ công khai eee thỏa gcd⁡(e,φ(n))=1\gcd(e, \varphi(n)) = 1gcd(e,φ(n))=1; số mũ bí mật ddd là nghịch đảo modulo của eee: e⋅d≡1(modφ(n))e \cdot d \equiv 1 \pmod{\varphi(n)}e⋅d≡1(modφ(n)).

    Trong bài toán "textbook RSA" (giáo trình, không đệm/padding) đơn giản dùng trong nhiều bài CTF nhập môn, mỗi ký tự mmm của flag (mã ASCII, 0≤m<n0 \le m < n0≤m<n) được mã hóa độc lập thành c=me mod nc = m^e \bmod nc=memodn. Việc giải mã dùng công thức m=cd mod nm = c^d \bmod nm=cdmodn.

    Cho p,q,ep, q, ep,q,e và danh sách các số nguyên mã hóa từng ký tự của flag, hãy tìm lại flag gốc.

    Ví dụ: với p=61,q=53,e=17p=61, q=53, e=17p=61,q=53,e=17 (nên n=3233n=3233n=3233), danh sách mã hóa 2790 ứng với ký tự duy nhất A (vì 6517 mod 3233=279065^{17} \bmod 3233 = 27906517mod3233=2790 và 27902753 mod 3233=652790^{2753} \bmod 3233 = 6527902753mod3233=65, với d=2753d=2753d=2753 là nghịch đảo của 171717 theo modulo φ(3233)=3120\varphi(3233)=3120φ(3233)=3120).

    • Định dạng đầu vào:

      Dòng 1: ba số nguyên p q ep\ q\ ep q e cách nhau bởi khoảng trắng (p,qp, qp,q là số nguyên tố, 1<e<φ(n)1 < e < \varphi(n)1<e<φ(n), gcd⁡(e,φ(n))=1\gcd(e, \varphi(n))=1gcd(e,φ(n))=1). Dòng 2: danh sách số nguyên c1 c2 … cLc_1\ c_2\ \ldots\ c_Lc1​ c2​ … cL​ cách nhau bởi khoảng trắng, mỗi số là mã hóa RSA của một ký tự (mã ASCII) của flag, theo đúng thứ tự.

    • Định dạng đầu ra:

      In ra một dòng duy nhất là flag đã giải mã (chuỗi ký tự ASCII, ghép theo đúng thứ tự).

    Ví dụ:

    Đầu vào:

    61 53 17
641 2159 325 855 1859 2680 2790 1516

    Đầu ra:

    CTF{RSA}

    Đầu vào:

    61 53 17
641 2159 325 855 2412 1230 1632 119 2570 1632 1230 3179 281 119 624 2906 1516

    Đầu ra:

    CTF{rsa_basic_01}

    Đang tải editor...