V. Thuật toán Pollard (tiếp)

2. Tấn công phân tích nhân tử theo thuật toán Pollard Rho (Pollard $\rho$)

2.1. Thuật toán Pollard $\rho$

Xét số $n$ là tích của hai số nguyên tố lớn $p$ và $q$. Tương tự với ý tưởng của thuật toán Pollard's $\rho - 1$, để tìm được một ước nguyên tố của $n$, chúng ta sẽ tìm kiếm hai số nguyên dương $x$ và $x'$ không vượt quá $n$ và thỏa mãn:

$$x \equiv x' \pmod {p}$$

Vì khi đó $p\ |\ (x-x')$, mà $p\ |\ n$ nên $p\ |\ gcd(x-x', n)$. Từ đó:

$$n > gcd(x-x', n) \geq p > 1$$

Hay $gcd(x-x', n)$ chắc chắn là một ước (khác $1$) của $n$. Bài toán trở về tìm một ước nguyên tố $r$ của $gcd(x-x', n)$. Độ khó của bài toán mới này có tăng lên không, sẽ phụ thuộc vào cách chúng ta chọn được cặp số $(x, x')$ ra sao (vì bài toán tìm ước chúng lớn nhất có thể giải quyết dễ dàng bằng thuật toán Euclid).

Một ý tưởng đơn giản có thể thực hiện để giải quyết vấn đề này như sau: chọn ra tập $X \subset Z$ chứa các số nguyên không vượt quá $n$. Chúng ta quan tâm tới việc tìm ra hai phần tử $x, x'\in X$ sao cho $gcd(x-x', n) > 1$, hay $x \equiv x' \pmod {p}$. Xét ánh xạ $x \rightarrow x \pmod {p}$, với xác suất tồn tại hai phần tử có cùng ánh xạ đích từ $50\%$ trở lên, theo nghịch lý ngày sinh nhật thì chúng ta chỉ cần chọn ra tập $X$ có số phần tử $\geq 1.71\times \sqrt{p}$. Tuy nhiên, để tìm được sự "trùng ánh xạ" này trong tập $X$, số lần tính toán ước chung lớn nhất cần thực hiện là:

$$\frac{|X|\times(|X|-1)}{2}$$

Lúc này, cách thực hiện của thuật toán Pollard $\rho$ giúp chúng ta giảm đi số lần tính toán GCD. Thay vì sinh ngẫu nhiên một tập $X$, thuật toán sẽ chọn các phần tử theo quy tắc. Xét $f$ là một đa thức hệ số nguyên, đầu tiên, chọn $x_1$ là một số nguyên nhỏ hơn $n$, lần lượt xác định:

$$x_{i+1} = f(x_i) \mod n,\ \ \ \text{i}=1,2,3, ...$$

Cuối cùng thu được tập $X=\{x_1, x_2, ..., x_m\}$. Cụ thể vì sao cách chọn này có thể giảm số lần tính GCD như đã nêu, cùng theo dõi các tính chất sau.

Giả sử có $x_i \equiv x_j \pmod p$ (mục tiêu chúng ta hướng tới), do $f$ là đa thức hệ số nguyên nên cũng sẽ có $f(x_i) \equiv f(x_j) \pmod p$.

Do $x_{i+1} = f(x_i) \mod n$ và $p$ là một ước của $n$ nên:

$$x_{i+1} \mod p = (f(x_i) \mod n) \mod p = f(x_i) \mod p\\ \rightarrow x_{i+1}\equiv f(x_i)\pmod p$$

Tương tự có $x_{j+1}\equiv f(x_j)\pmod p$ nên suy ra $x_{i+1}\equiv x_{j+1}\pmod p$

Tổng quát: Nếu có $x_i \equiv x_j \pmod p$ thì $\forall k\geq 0$ có: $x_{i+k} \equiv x_{j+k} \pmod p$ (tính chất *)

Từ đây có thể thấy, khi liên tục tính $x_{i+1}$ từ $x_i$ (lưu ý theo định nghĩa phía trên chúng ta đang tính theo module $n$), và nhìn theo một dãy số mới qua module $p$, dần dần chúng ta sẽ đi vào một vòng lặp tuần hoàn:

$$x_1 \rightarrow x_2 \rightarrow x_3 \rightarrow \ ...\ \rightarrow x_i \pmod p\\ x_i \rightarrow x_{i+1} \rightarrow x_{i+2} \rightarrow \ ...\ \rightarrow x_j = x_i \pmod p$$

Để hình dung dễ hơn về vòng lặp này, xét ví dụ: $n=7171$, $f(x)=x^2+1$, chọn $x_1=1$. Tính được $18$ số hạng đầu của tập $X$ là:

$$1,2,5,26,677,6557,4105,6347,4903,2218,219,4936,4210,4560,4872,375,4377,4389$$

# f(x) = x*x + 1
def f(i, n):
    if i == 1:
        return 1
    return (f(i - 1, n) * f(i - 1, n) + 1) % n

Viết lại dãy này thành một dãy mới theo module $p=71$ có hình dạng như sau:

Do hình dạng lặp lại tương tự ký tự $\rho$ nên Pollard đã đặt tên là thuật toán Pollard $\rho$. Từ hình trên có thể thấy $x_7\equiv x_{18} \pmod {71}$. Túc là bằng việc tính toán liên tục $gcd(x_i - x_j, n)$ có thể thu được $p=71$ là một ước nguyên tố của $n$.

Lúc này, chú ý rằng thời gian và tài nguyên sử dụng cho việc tìm ra số nguyên tố $p$ dựa vào số lần tính toán $gcd(x_i - x_j, n)$ với cặp số chọn từ trong tập $X$. Như vậy chiến thuật thực hiện tính toán là rất quan trọng!

Chẳng hạn, mỗi khi tập $X$ có thêm một thành viên mới $x_j$ thì chúng ta sẽ cần tính $j-1$ lần GCD tương ứng với $j-1$ cặp $(x_1, x_j), (x_2, x_j), ...$. Để gặp được cặp $(x_i, x_j)$ là kết quả mong đợi, chúng ta cần thực hiện $\frac{(j-1)(j-2)}{2}+i$ lần tính toán.

Tuy nhiên, nếu tục tính thêm phần tử mới cho $X$, do đi vào vòng lặp tuần hoàn số dư module $p$, nên sẽ có vô số cặp $(x_{i+k}, x_{j+k})$ cũng thỏa mãn $gcd(x_{i+k}-x_{j+k}, n)=p$. Điều đó cho thấy không nhất thiết cặp số cần chọn phải là cặp số $(x_i, x_j)$ đầu tiên của vòng lặp. Chúng ta sẽ xây dựng một chiến thuật mới nhằm giảm đi số lần tính ước chung lớn nhất. Xét vòng lặp module đầu tiên $x_i \rightarrow x_{i+1} \rightarrow x_{i+2} \rightarrow \ ...\ \rightarrow x_j = x_i \pmod p$, chúng ta tìm kiếm một chỉ số $i'$ thỏa mãn $i'$ là bội của $j-i$. Có thể khẳng định chỉ số $i'$ này luôn tồn tại, thật vậy, đặt $i'=k(j-i)$, luôn có thể tìm thấy $k$ thỏa mãn:

$$i\leq i'=k(j-i) \leq j-1$$

Từ tính chất * suy ra $x_{i+\alpha } = x_{i+\alpha +(j-i)} = ... = x_{i+\alpha +\beta (j-i)} \pmod p$ với $\alpha ,\beta $ bất kỳ. Chọn $\alpha =i'-i$, $\beta =k$ ta có:

$$x_{i'} = x_{i' +k(j-i)} =x_{2i'}\pmod p$$

Tức cặp số $(x_{i'}, x_{2i'})$ thỏa mãn $gcd(x_{i'}-x_{2i'}, n)=p$. Chúng ta chỉ mất nhiều nhất $j$ lần là có thể tìm được $i'$ thỏa mãn - số lần tính GCD đã được giảm đi đáng kể.

Vẫn từ ví dụ trên, $n=7171$, $f(x)=x^2+1$, chọn $x_1=1$, lần lượt tính toán $gcd(x_{1}-x_{2}, n)$, $gcd(x_{2}-x_{4}, n)$, $gcd(x_{3}-x_{6}, n)$, ... cuối cùng thu được $gcd(x_{11}-x_{22}, n)=71$ là một ước nguyên tố của $n$.

Thuật toán Pollard $\rho$ có thể cài đặt dễ dàng bằng ngôn ngữ Python như sau:

n = 7171

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

# f(x) = x*x + 1
def f(i, n):
    if i == 1:
        return 1
    return (f(i - 1, n) * f(i - 1, n) + 1) % n

def Pollard_p(n):
    i = 1
    p = 1
    while p == 1:
        x = f(i, n)
        x_ = f(2 * i, n)
        p = gcd(x - x_, n)
        i += 1
    return p

p = Pollard_p(n)
if p == n:
    print("please choose another f(x)")
else:
    print("p =", p)

Kết quả:

Tùy vào mỗi trường hợp, chúng ta có thể cài đặt thuật toán với các chiến thuật tìm kiếm cặp $(x_i, x_j)$ phù hợp.

2.2. Hàm $f(x)$ và dãy số ngẫu nhiên

Sau khi hiểu về thuật toán Pollard $\rho$, bạn đọc sẽ không khó để phát hiện thuật toán dựa vào "xác suất" để tìm ra ước nguyên tố của $n$, trong đó việc chọn ra dãy ngẫu nhiên $x, f(x), f(f(x)), f(f(f(x))), ...$ đóng vai trò quan trọng. Vậy thì, cần xác định hàm $f(x)$ như thế nào để dãy thu được sẽ "sớm" đi vào một vòng lặp $\rho$?

Một cách chọn phổ biến nhất là $f(x)=x^2 + c \pmod n$. Với $x_1=0, c= 24, n=9409$, quan sát $100$ giá trị đầu tiên của dãy ngẫu nhiên:

Các giá trị khá ngẫu nhiên và chưa thấy rõ quy luật, tuy nhiên, nếu đổi thành $n=9400$:

Bảng giá trị bắt đầu trở nên có quy luật! Bởi mỗi số đều được sinh ra dựa vào số ngay trước nó qua hàm $f(x)$, cũng bởi tính module, nên số lượng số sinh ra là có hạn, do đó sớm hay muộn cũng sẽ đi vào một vòng lặp $\rho$. Chúng ta cần có "niềm tin" này khi thực hiện chọn hàm $f(x)$ phù hợp với từng trường hợp của $n$.

Chúng ta cùng xem xét challenge CTF về mật mã RSA, mã nguồn cung cấp được viết bằng Python như sau:

from Crypto.Util.number import getPrime, isPrime, bytes_to_long
flag = 'Viblo{****************************}'
nbits = 2048
gbits = 1000
g = getPrime(int(gbits))
while True:
    a = getPrime(int(nbits * 0.5) - gbits)
    p = 2 * g * a + 1
    if isPrime(p):
        break

while True:
    b = getPrime(int(nbits * 0.5) - gbits)
    q = 2 * g * b + 1
    if p != q and isPrime(q):
        break
N = p * q
e = 65537

def str2int(s):
    return bytes_to_long(flag.encode())

with open('pubkey.txt', 'w') as f:
    f.write(str(e) + '\n')
    f.write(str(N) + '\n')

plain = str2int(flag)

c = pow(plain, e, N)
with open('cipher.txt', 'w') as f:
    f.write(hex(c))

Nội dung file cipher.txt:

0x5cf9b2a6a0f5723dcd90e4e7cd8c2f4a115aa8e2d123eb949d4d1e4641a276c445b5a0dc5f3e7ae77cfacec09debc5544a32247885e383a6b11c82eaa794d3f23f0a73aa5a3cc760c7f132f2b2a5b74d57b8fd789f125a130f3e3bfc2854b60f51bc9d976f3e58f8c694cf4b2aa93a952e69df3d80d346ec65387dc7096d17e0a301ff6b25e5fa120ec4dce1c1429443940e3c38713ff5a43ee2e7403bad33195c5c418dcdae4ec7e60c44470759bc2c4688667c5c6e9f0443cd39aad077a4cc6e4b6bc6fd2fe2867b5d16c355ec02c68b0c81123cffb94222637b80888222b66b4311234cc5695028610c93d582384ecc0ea9931e26b5b4e73a54cfebc0fb3b

Nội dung file pubkey.txt:

65537
20902790268633126850940679053298116769870106633933056047845154148737759906850349907720879485630593331090207332245583521473134664307263774133558697957031694642194157647671844964402839468299788129346761280107832521466479427160024734846709374068332170121459314888809358316863795032578177090450355693844943882436399605171289629939417439079078271299240693557149051279583801809487720045200649857180919839745011714126062683953532293990025086093547019729918799593133102015844167158296181560011275838819713053780666492185682095297862014018657264790208019989335446936012947041060652330757324747617960007836606179355980236498609

Nhìn vào số $n$ có thể thấy cơ chế RSA này đảm bảo an toàn do độ dài khóa công khai $n$ lên tới $2048$ bit. Tuy nhiên, chúng ta chú ý tới cách sinh hai số nguyên tố lớn $p,q$ trong đề bài:

nbits = 2048
gbits = 1000
g = getPrime(int(gbits))
while True:
    a = getPrime(int(nbits * 0.5) - gbits)
    p = 2 * g * a + 1
    if isPrime(p):
        break

while True:
    b = getPrime(int(nbits * 0.5) - gbits)
    q = 2 * g * b + 1
    if p != q and isPrime(q):
        break

Ở đây, challenge sử dụng số nguyên tố $g$ có độ dài $1000$ bit, sinh ra hai số nguyên tố $p,q$ lớn theo công thức:

$$p = 2 * g * a + 1\\ q = 2 * g * b + 1$$

Cách sinh số đặc biệt này cho biết $p-1$ và $q-1$ tồn tại một ước nguyên tố chung là $g$ ($1000$ bit). Đây chính là điểm mấu chốt để tìm ra hướng đi bài toán phân tích số $n$ dài $2048$ bit ra thừa số nguyên tố trong trường hợp này. Thật vậy, khi đó ta có:

$$n - 1 = p\times q - 1\\ = (pq - p - q + 1) + (p - 1) + (q - 1)\\ = (p-1)(q-1) + (p - 1) + (q - 1)$$

Sử dụng module $g$ ta có:

$$n-1\equiv (p-1)(q-1) + (p - 1) + (q - 1) \pmod g\\ \rightarrow n-1\equiv 0 \pmod g \rightarrow n\equiv 1 \pmod g$$

Tham khảo mục THE FIRST STAGE OF THE ATTACK tại FURTHER ATTACKS ON SERVER-AIDED RSA CRYPTOSYSTEMS chúng ta sẽ chọn hàm:

$$f(x) = x^{n-1} + 3 \pmod n$$

Cách chọn này sẽ giảm độ phức tính toán xuống $O(\sqrt{\frac{p}{g}})$. Mã nguồn lời giải gợi ý bạn đọc có thể tham khảo:

from Crypto.Util.number import getPrime, isPrime, bytes_to_long, long_to_bytes

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

def mapx(x):
    # sử dụng module pow(x, n - 1, n) nhằm giảm tính toán
    x = (pow(x, n - 1, n) + 3) % n
    return x

def pollard_rho(x1, x2):
    while True:
        x1 = mapx(x1)
        x2 = mapx(mapx(x2))
        p = gcd(x1 - x2, n)
        if (p == n):
            print("fail")
            return
        elif (p != 1):
            print("p: ", p)
            print("q: ", n // p)
            break

def main():
    pollard_rho(1, 1)
    return 

n = 44327510143608652757309189121332002880736698826750814657928212799250989192533667090201158810441527941988339241953786693677345673674361495114190715248262185309157465424294779216031542945593633753442877226657245200617765607501935803024360190835150880116213395142289073140262609992858604295835861176915393471286050495813474776327352620577951619237771437380151233189336755447495103212957954178961674076787878537486516933808009793508283662417305262989135712933581661719965234419967031722873415515599146228798914453074940076094660682125563394179615976699753629942908617177026410858707681194686016943415767375769391168384273     
main()

Kết quả thu được hai số nguyên tố $p$ và $q$:

Tài liệu tham khảo

• https://en.wikipedia.org/wiki/RSA_(cryptosystem)
• https://www.amsi.org.au/teacher_modules/pdfs/Maths_delivers/Encryption5.pdf
• https://sites.math.washington.edu/~morrow/336_09/papers/Yevgeny.pdf
• https://en.wikipedia.org/wiki/Pollard's_p_−_1_algorithm
• https://www.geeksforgeeks.org/pollards-rho-algorithm-prime-factorization/
• https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.1333&rep=rep1&type=pdf