Bài tập | NEU OJ

Cho khóa công khai RSA $(n, e)$ được sinh từ hai số nguyên tố $p, q$ (tức $n = pq$ ) và một dãy gồm $k$ khối bản rõ $m_1, m_2, \ldots, m_k$ (mỗi $0 \le m_i < n$ ). Hãy mã hóa từng khối theo công thức:

$c_i = m_i^e \bmod n$

Ví dụ: $p = 61$ , $q = 53$ , $e = 17$ $\Rightarrow n = 3233$ . Với $m_1 = 65$ , $c_1 = 65^{17} \bmod 3233 = 2790$ .

Định dạng đầu vào:
Dòng 1: ba số nguyên $p\ q\ e$ ( $2 \le p, q \le 10^6$ , $p, q$ nguyên tố, $p \ne q$ , $\gcd(e,\varphi(n))=1$ ). Dòng 2: một số nguyên $k$ ( $0 \le k \le 1000$ ) — số lượng khối. Dòng 3: $k$ số nguyên $m_1\ m_2\ \ldots\ m_k$ cách nhau bởi khoảng trắng (bỏ trống nếu $k = 0$ ).
Định dạng đầu ra:
In ra một dòng gồm $k$ số nguyên $c_1\ c_2\ \ldots\ c_k$ cách nhau bởi khoảng trắng, theo đúng thứ tự đầu vào (in dòng trống nếu $k = 0$ ).

solution

Đề bài: [An toàn thông tin] Mã hóa RSA cho dãy khối bản rõ