Các cuộc thi năm 2019

AceBear

Baby RSA

Đề bài

# 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 \(c_1 = (p + q)^{2019}\), \(c_2 = (p + 2019)^{q}\).

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

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

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

Ta có \(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ố \(a\), \(b\) để \(a \cdot n + b \cdot (c_2 - 2019)\) trở nên gọn nhất có thể.

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

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

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

\[\begin{split}& \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.\end{split}\]

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

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

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))