Các cuộc thi năm 2019
#####################

AceBear
*******

Baby RSA
========

Đề bài

.. code-block:: python

    # rsa.py
    from Crypto.Util.number import *
    from secret import flag

    m = bytes_to_long(flag)

    p = getPrime(512)
    q = getPrime(512)
    n = p*q
    e = 65537

    c = pow(m, e, n)

    print(n)
    # 132991872691788324082134861997953579720626276400340540687013665099477551458348129102088618361745158673111757871083783880384786818716675179609957267487624993539275409316283860268944400754318665280566429956092526555947286266806591767802818223484766666271142927737412289284611614382748008696676464334157695348471

    print(c)
    # 51298575439582965784709335152059190835305126166438646589369499569428503835480418841408132266294091481013029021796067865137829386370176771358549523435135941877535688535317287350930103706346511719290416785053872504275498831270025102211793188751664805369414883387849038010293938521738911310864582949611581363258

    print(pow(p+q, 2019, n))
    # 116622952696503724444465816906812927416603315297598995734109952470693593204299624097288573735780464942963720997719694033378973971604112334413336782598075611956878592757766346915810900585142701963781432186914454664547551508332077962977944352243565906344660561255453917679867097810681750809061744116605905787747

    print(pow(p+2019, q, n))
    # 46935581819524717607675319301313485106684889957138298327245990937934310422542055504175491111118389178173005337213903985686712577881019021348501335888175248295397612880683801733649468701485843002169345784241756189697901370624950199354359977266595488202827970067500373575114835718127956891051157026649793602861

Đặt :math:`c_1 = (p + q)^{2019}`, :math:`c_2 = (p + 2019)^{q}`.

Khi đó :math:`(p + 2019)^q - c_2` chia hết cho :math:`n`, suy ra :math:`(p + 2019)^q - c_2` chia hết :math:`q`, và :math:`(p + 2019)^q \equiv c_2 \bmod q`.

Theo định lý Fermat, :math:`(p + 2019)^q \equiv p + 2019 \bmod q`, suy ra :math:`p + 2019 \equiv c_2 \bmod q`, và :math:`p + 2019 - c_2` chia hết :math:`q`.

Ta cũng có :math:`n` chia hết cho :math:`q` nên :math:`a \cdot n + b \cdot (c_2 - p - 2019)` chia hết :math:`q`, với :math:`a`, :math:`b` là các số nguyên bất kì.

Ta có :math:`a \cdot n + b \cdot (c_2 - p - 2019) = a \cdot n + b \cdot (c_2 - 2019) - b \cdot p` (1) nên ta sẽ tìm số :math:`a`, :math:`b` để :math:`a \cdot n + b \cdot (c_2 - 2019)` trở nên gọn nhất có thể.

Vì :math:`\gcd(n, c_2 - 2019) = 1` nên ta dùng thuật toán Euclid mở rộng để tìm :math:`a`, :math:`b` để :math:`a \cdot n + b \cdot (c_2 - 2019) = 1`.

Thay :math:`a` và :math:`b` vào (1) ta có :math:`1 - b \cdot p` chia hết :math:`q` nên :math:`b \cdot p - 1 = k \cdot q`, hay :math:`b \cdot p = k \cdot q + 1` (2).

Ta lại có :math:`(p + q)^{2019} \equiv c_1 \bmod n`

.. math:: 
    
    & \Longrightarrow (p + q) \cdot 2019 \equiv c_1 \bmod q \\ 
    & \Longrightarrow (p + q) \cdot 2019 \cdot b^{2019} ≡ c_1 \cdot b^{2019} \bmod n \\
    & \Longrightarrow (b \cdot p + b \cdot q)^{2019} \equiv (c_1 \cdot b^{2019}) \bmod n.

Thay (2) vào đây ta được :math:`(1 + (k + b) \cdot q)^{2019} \equiv (c_1 \cdot b^{2019}) \bmod q`.

Vì :math:`1 + (k + b) \cdot q \equiv 1 \bmod q` nên :math:`(c_1 \cdot b^{2019}) \bmod n - 1` chia hết :math:`q`, suy ra :math:`\gcd(n, (c_1 \cdot b^{2019}) \bmod n - 1) = q` vì :math:`(c_1 \cdot b^{2019}) \bmod n - 1` không chia hết :math:`n`. Như vậy tìm ước chung lớn nhất giữa :math:`n` và :math:`(c_1 \cdot b^{2019 - 1}) \bmod n` sẽ được :math:`q`. Từ đó tính :math:`p` và giải mã được bài toán.

.. code-block:: python

    n = 132991872691788324082134861997953579720626276400340540687013665099477551458348129102088618361745158673111757871083783880384786818716675179609957267487624993539275409316283860268944400754318665280566429956092526555947286266806591767802818223484766666271142927737412289284611614382748008696676464334157695348471
    from Crypto.Util.number import *

    c = 51298575439582965784709335152059190835305126166438646589369499569428503835480418841408132266294091481013029021796067865137829386370176771358549523435135941877535688535317287350930103706346511719290416785053872504275498831270025102211793188751664805369414883387849038010293938521738911310864582949611581363258

    # print(pow(p+q, 2019, n))
    c1 = 116622952696503724444465816906812927416603315297598995734109952470693593204299624097288573735780464942963720997719694033378973971604112334413336782598075611956878592757766346915810900585142701963781432186914454664547551508332077962977944352243565906344660561255453917679867097810681750809061744116605905787747

    # print(pow(p+2019, q, n))
    c2 = 46935581819524717607675319301313485106684889957138298327245990937934310422542055504175491111118389178173005337213903985686712577881019021348501335888175248295397612880683801733649468701485843002169345784241756189697901370624950199354359977266595488202827970067500373575114835718127956891051157026649793602861
    x = c2 - 2019
    def isqrt(n):
        x = n
        y = (x + n // x) // 2
        while y < x:
            x = y
            y = (x + n // x) // 2
        return x

    def xgcd(b, a):
        x0, x1, y0, y1 = 1, 0, 0, 1
        while a != 0:
            q, b, a = b//a, a, b%a
            x0, x1 = x1, x0 - q*x1
            y0, y1 = y1, y0 - q*y1
        return b, x0, y0

    def mulinv(a, b):
        """return x such that (x * a) % b == 1"""
        g, x, _ = xgcd(a, b)
        if g == 1:
            return x % b
    _, a, b = xgcd(n, c2-2019)
    tmp = (1-c1*b**2019) % n
    # print(xgcd(n, tmp))
    q = 13167511664664654241879722275239314077796628288014993501946163865534098363688179601787128893069641975126584216420427952135663458656314745346906315477111831
    p = n // q
    assert (p*q == n)
    phi = (p-1)*(q-1)
    d = mulinv(65537, phi)
    m = pow(c, d, n)
    print(long_to_bytes(m))

.. raw:: html

   <script async src="https://pagead2.googlesyndication.com/pagead/js/adsbygoogle.js?client=ca-pub-2343650775986433"
     crossorigin="anonymous"></script>
   <!-- First Ads -->
   <ins class="adsbygoogle"
      style="display:block"
      data-ad-client="ca-pub-2343650775986433"
      data-ad-slot="4417625951"
      data-ad-format="auto"
      data-full-width-responsive="true"></ins>
   <script>
      (adsbygoogle = window.adsbygoogle || []).push({});
   </script>