solution

Lược đồ chữ ký RSA "textbook" (ký $s = m^d \bmod n$, xác minh $s^e \bmod n = m$) có một điểm yếu nghiêm trọng: tính nhân tính (multiplicativity). Nếu $s_1$ là chữ ký hợp lệ của bản tin $m_1$ và $s_2$ là chữ ký hợp lệ của bản tin $m_2$ (cùng một khóa bí mật $d$ không được tiết lộ), thì:

$(s_1 \cdot s_2 \bmod n)^e \bmod n = (m_1 \cdot m_2) \bmod n$

Nói cách khác, $s_1 \cdot s_2 \bmod n$ là chữ ký hợp lệ của bản tin $m_t = m_1 \cdot m_2 \bmod n$ — kẻ tấn công giả mạo được chữ ký cho một bản tin mới mà không cần biết khóa bí mật.

Cho khóa công khai $(n, e)$ và hai cặp (bản tin, chữ ký hợp lệ) $(m_1, s_1)$, $(m_2, s_2)$ dưới cùng khóa bí mật $d$, hãy tính bản tin đích $m_t = m_1 \cdot m_2 \bmod n$ và chữ ký giả mạo tương ứng $s_t = s_1 \cdot s_2 \bmod n$.

Ví dụ: $n=3233, e=17, m_1=65, s_1=588, m_2=10, s_2=969$. Ta có $m_t = 650$, $s_t = 764$.