NSUCRYPTO 2020

Problem 1 (R1). 2020

Đề bài

Cho dãy \(S\), cipher machine có thể thêm vào \(S\) hoặc xóa khỏi \(S\) dãy con với dạng \(11\), \(101\), \(1001\), \(10\ldots 01\). Machine cũng có thể xóa khỏi \(S\) hoặc thêm vào \(S\) một dãy liên tục các số \(0\).

Smith biểu diễn số \(2020\) dưới dạng nhị phân và sử dụng hai cipher machine để biến đổi. Máy đầu tiên trả về dạng nhị phân của số \(1984\), máy thứ hai trả về dạng nhị phân của số \(2021\).

Smith chắc chắn rằng một trong hai máy đã bị lỗi. Làm sao anh ấy biết được?

Giải

Ta viết các số \(2020\), \(1984\) và \(2021\) dưới dạng nhị phân.

Như vậy

\[2020 = 11111100100, \ 1984 = 11111000000, \ 2021 = 11111100101.\]

Đặt \(2020 = 11111 \underbrace{1001}_A 00\) thì nếu ta xóa dãy \(A\) khỏi \(2020\) và thêm vào vị trí đó bốn chữ số \(0\) thì ta có \(1984\). Như vậy máy đầu tiên hoạt động bình thường.

Việc thêm vào hoặc xóa đi \(11\), \(101\), \(1001\), ... thì số lượng bit \(1\) tăng giảm đi một lượng chẵn còn thêm bớt \(0\) không ảnh hưởng. Do \(2020\) và \(2021\) có số lượng bit \(1\) khác tính chẵn lẻ nên không thể biến đổi từ \(2020\) thành \(2021\).

Như vậy máy thứ hai bị hỏng.

Problem 4 (R1). RGB

Đề bài

Trong một server có hai biến \(a\) và \(b\). Khi server nhận query dạng "RED", "GREEN" hoặc "BLUE" thì giá trị của chúng sẽ thay đổi theo query nhận được.

Cụ thể hơn, cặp \((a, b)\) biến thành \((a + 18b, 18a - b)\) nếu query là "RED", biến thành \((17a + 6b, -6a + 17b)\) nếu query là "GREEN" và biến thành \((-10a-15b, 15a-10b)\) nếu là "BLUE".

Khi \(a\) hoặc \(b\) trở thành bội của \(324\) thì nó được reset thành \(0\). Khi \((a, b) = (0, 0)\) thì server crash.

Ban đầu, \((a, b)\) được khai báo là \((20, 20)\). Chứng minh rằng server sẽ không bao giờ crash dù có bao nhiêu query được gửi tới.

Giải

Phép biến đổi tương đương với phép nhân ma trận \((a, b) \to (a, b) \bm{A}\) với \(\bm{A}\) là ma trận xác định bởi

  1. \(\bm{A} = \begin{pmatrix} 1 & 18 \\ 18 & -1 \end{pmatrix}\) khi query là "RED".

  2. \(\bm{A} = \begin{pmatrix} 17 & -6 \\ 6 & 17 \end{pmatrix}\) khi query là "GREEN".

  3. \(\bm{A} = \begin{pmatrix} -10 & 15 \\ -15 & -10 \end{pmatrix}\) khi query là "BLUE".

Kết quả cuối là việc thực hiện liên tiếp các phép nhân có dạng

\[(a, b) \cdot \bm{A}_1 \bm{A}_2 \cdots \bm{A}_r\]

với \(\bm{A}_i\) là một trong ba ma trận trên.

Đặt \(\bm{A}_1 \cdots \bm{A}_r = B\) thì phép nhân tương đương với \((a, b) \cdot \begin{pmatrix} X & Y \\ Z & T \end{pmatrix} = (324, 324)\). Trong đó \(X, Y, Z, T \in \mathbb{Z}\).

Điều này tương đương với \(a \cdot X + b \cdot Z = 324\) và \(a \cdot Y + b \cdot T = 324\). Suy ra \(20 (X + Z) = 324\) và \(20 (Y + T) = 324\). Nhưng điều này không thể xảy ra vì \(324\) không chia hết \(20\).

Như vậy server không bao giờ crash dù có thực hiện bao nhiêu query đi nữa.

Problem 1. Poly

Đề bài

Bob phát minh một thuật toán tên là POLY. Với \(x\) là plaintext thì ciphertext là \(y = p(x)\), với \(p(x)\) là đa thức với hệ số nguyên.

Đồng nghiệp của Bob muốn kiểm tra thuật toán. Khi encrypt \(20\) thì Bob nhận được \(7\). Sau đó anh đồng nghiệp encrypt \(15\) thì nhận được \(5\). Anh ta kết luận rằng thuật toán đã bị cài đặt sai. Chuyện gì đã xảy ra?

Giải

Giả sử đa thức là

\[p(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0.\]

Khi đó

\[p(20) = a_n 20^n + a_{n-1} 20^{n-1} + \cdots + a_1 \cdot 20 + a_0 = 7.\]

Tương tự

\[p(15) = a_n 15^n + a_{n-1} 15^{n-1} + \cdots + a_1 \cdot 15 + a_0 = 5.\]

Suy ra \(p(20) - p(15) = 2\) mà \(p(20) - p(15)\) chia hết cho \(20 - 15 = 5\) nên vô lý vì \(2\) không chia hết cho \(5\). Như vậy thuật toán đã bị cài đặt sai.

Problem 3. Hidden RSA

Đề bài

Bob học về mật mã khóa công khai và bây giờ mọi người đều có thể gửi message cho anh ta. Message được biểu diễn thành số nguyên không âm \(x\) và chứa tối đa \(70\) chữ số trong biểu diễn thập phân. Để gửi message cho Bob, chúng ta nhập \(x\) vào trang web và kết quả được trả về ở dạng

\[\mathtt{Encr}(x) = x^e \pmod n,\]

với \(n\) là modulus (biết rằng \(n\) là tích của hai số nguyên tố phân biệt \(p\) và \(q\)) và \(e\) là số mũ công khai (nguyên tố cùng nhau với \(p-1\) và \(q-1\)). Bob sợ bị hacker tấn công nên giấu đi \(n\) và \(e\).

Victor bắt được một encrypted message

\[y = 71511896681324833458361392885184344933333159830863878600189212073777582178173,\]

được Alice gửi cho Bob.

Hãy giúp Victor giải mã nó.

Giải

Gọi \(f_2\), \(f_3\) và \(f_6\) là kết quả trả về khi nhập \(2\), \(3\) và \(6\) lên trang web. Mình nhận được

\[\begin{split}f_2 & = 50154912289039335014669339773308393642658123228965873078737860474494117389068 \\ f_3 & = 74177167678866806519929337366689313939300015489238864541679630476008627210599 \\ f_6 & = 69732835711852253044075185248502970714729629373386336194927784886349053828079.\end{split}\]

Vì

\[\begin{split}f_6 & \equiv 6^e \pmod n \\ & \equiv (2^e) \cdot (3^e) \pmod n \\ & \equiv f_2 \cdot f_3 \pmod n\end{split}\]

nên suy ra \(n \mid (f_2 \cdot f_3 - f_6)\).

Tương tự, gọi \(f_5\), \(f_7\) và \(f_{35}\) là kết quả trả về khi nhập \(5\), \(7\) và \(35\). Mình nhận được

\[\begin{split}f_5 & = 66788051164865948223783605396869677445056352267867968640234839015540677264876 \\ f_7 & = 25469333231403648059708659888338792850140504272696299331424365245642760908571 \\ f_{35} & = 25850860693609575302160565920815769473222469094759983686766869114847002714718.\end{split}\]

Tương tự \(n \mid (f_3 \cdot f_5 - f_{35})\).

Như vậy

\[n = \gcd(f_2 \cdot f_3 - f_6, f_3 \cdot f_5 - f_{35}).\]

Mình thu được

\[n = 76200708443433250012501342992033571586971760218934756930058661627867825188509.\]

Sử dụng factordb mình tìm được

\[p = 232086664036792751646261018215123451301, \quad q = 328328681700354546732404725320581286809.\]

Với số \(e\) mình chọn \(e = 65537\) là public exponent được dùng nhiều nhất trên thực tế và kiểm tra \(2^e \pmod n\) có khớp với \(f_2\) không, tương tự với \(3^e \pmod n\) với \(f_3\), ... và hoàn toàn trùng kết quả.

Như vậy \(e = 65537\) và tính

\[d = e^{-1} \pmod{(p-1) \cdot (q-1)},\]

từ đó decrypt ra được message ban đầu (theo RSA)

\[m = 202010181600.\]

Sau này đọc bài giải của anh Hiếu (ndh) thì mình mới biết ý nghĩa của plaintext là 2020-10-18-16-00 là năm, tháng, ngày, giờ bắt đầu round 2 (múi giờ Novosibirsk, UTC+7).

solve.py

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

f2 = 50154912289039335014669339773308393642658123228965873078737860474494117389068
f3 = 74177167678866806519929337366689313939300015489238864541679630476008627210599
f6 = 69732835711852253044075185248502970714729629373386336194927784886349053828079
a = f2 * f3 - f6

f5 = 66788051164865948223783605396869677445056352267867968640234839015540677264876
f7 = 25469333231403648059708659888338792850140504272696299331424365245642760908571
f35 = 25850860693609575302160565920815769473222469094759983686766869114847002714718
b = f5 * f7 - f35

f4 = 34176590322694690833975364940063423615063159848675783675025873390206977645476
f9 = 51250457553422544471678089837959016263959958280836142992507348470497811391846
f36 = 38373209266524169859264993312969244741422016390509755242558024317888485094728
c = f4 * f9 - f36

n = gcd(gcd(a, b), c)
p = 232086664036792751646261018215123451301
q = 328328681700354546732404725320581286809
assert n == p * q
y = 71511896681324833458361392885184344933333159830863878600189212073777582178173
e = 65537
d = pow(e, -1, (p - 1) * (q - 1))
m = pow(y, d, n)
print(m)