+2

Mật mã RSA - phần 5

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ố nn là tích của hai số nguyên tố lớn ppqq. Tương tự với ý tưởng của thuật toán Pollard's ρ1\rho - 1, để tìm được một ước nguyên tố của nn, chúng ta sẽ tìm kiếm hai số nguyên dương xxxx' không vượt quá nn và thỏa mãn:

xx(modp)x \equiv x' \pmod {p}

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

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

Hay gcd(xx,n)gcd(x-x', n) chắc chắn là một ước (khác 11) của nn. Bài toán trở về tìm một ước nguyên tố rr của gcd(xx,n)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)(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 XZX \subset Z chứa các số nguyên không vượt quá nn. Chúng ta quan tâm tới việc tìm ra hai phần tử x,xXx, x'\in X sao cho gcd(xx,n)>1gcd(x-x', n) > 1, hay xx(modp)x \equiv x' \pmod {p}. Xét ánh xạ xx(modp)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%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 XX có số phần tử 1.71×p\geq 1.71\times \sqrt{p}. Tuy nhiên, để tìm được sự "trùng ánh xạ" này trong tập XX, số lần tính toán ước chung lớn nhất cần thực hiện là:

X×(X1)2\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 XX, thuật toán sẽ chọn các phần tử theo quy tắc. Xét ff là một đa thức hệ số nguyên, đầu tiên, chọn x1x_1 là một số nguyên nhỏ hơn nn, lần lượt xác định:

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

Cuối cùng thu được tập X={x1,x2,...,xm}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ó xixj(modp)x_i \equiv x_j \pmod p (mục tiêu chúng ta hướng tới), do ff là đa thức hệ số nguyên nên cũng sẽ có f(xi)f(xj)(modp)f(x_i) \equiv f(x_j) \pmod p.

Do xi+1=f(xi)modnx_{i+1} = f(x_i) \mod npp là một ước của nn nên:

xi+1modp=(f(xi)modn)modp=f(xi)modpxi+1f(xi)(modp)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ó xj+1f(xj)(modp)x_{j+1}\equiv f(x_j)\pmod p nên suy ra xi+1xj+1(modp)x_{i+1}\equiv x_{j+1}\pmod p

Tổng quát: Nếu có xixj(modp)x_i \equiv x_j \pmod p thì k0\forall k\geq 0 có: xi+kxj+k(modp)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 xi+1x_{i+1} từ xix_i (lưu ý theo định nghĩa phía trên chúng ta đang tính theo module nn), và nhìn theo một dãy số mới qua module pp, dần dần chúng ta sẽ đi vào một vòng lặp tuần hoàn:

x1x2x3 ... xi(modp)xixi+1xi+2 ... xj=xi(modp)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=7171n=7171, f(x)=x2+1f(x)=x^2+1, chọn x1=1x_1=1. Tính được 1818 số hạng đầu của tập XX là:

1,2,5,26,677,6557,4105,6347,4903,2218,219,4936,4210,4560,4872,375,4377,43891,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=71p=71 có hình dạng như sau:

image.png

image.png

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 x7x18(mod71)x_7\equiv x_{18} \pmod {71}. Túc là bằng việc tính toán liên tục gcd(xixj,n)gcd(x_i - x_j, n) có thể thu được p=71p=71 là một ước nguyên tố của nn.

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ố pp dựa vào số lần tính toán gcd(xixj,n)gcd(x_i - x_j, n) với cặp số chọn từ trong tập XX. 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 XX có thêm một thành viên mới xjx_j thì chúng ta sẽ cần tính j1j-1 lần GCD tương ứng với j1j-1 cặp (x1,xj),(x2,xj),...(x_1, x_j), (x_2, x_j), .... Để gặp được cặp (xi,xj)(x_i, x_j) là kết quả mong đợi, chúng ta cần thực hiện (j1)(j2)2+i\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 XX, do đi vào vòng lặp tuần hoàn số dư module pp, nên sẽ có vô số cặp (xi+k,xj+k)(x_{i+k}, x_{j+k}) cũng thỏa mãn gcd(xi+kxj+k,n)=pgcd(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ố (xi,xj)(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 xixi+1xi+2 ... xj=xi(modp)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ố ii' thỏa mãn ii' là bội của jij-i. Có thể khẳng định chỉ số ii' này luôn tồn tại, thật vậy, đặt i=k(ji)i'=k(j-i), luôn có thể tìm thấy kk thỏa mãn:

ii=k(ji)j1i\leq i'=k(j-i) \leq j-1

Từ tính chất * suy ra xi+α=xi+α+(ji)=...=xi+α+β(ji)(modp)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 α=ii\alpha =i'-i, β=k\beta =k ta có:

xi=xi+k(ji)=x2i(modp)x_{i'} = x_{i' +k(j-i)} =x_{2i'}\pmod p

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

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

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ả:

image.png

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 (xi,xj)(x_i, x_j) phù hợp.

2.2. Hàm f(x)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 nn, trong đó việc chọn ra dãy ngẫu nhiên x,f(x),f(f(x)),f(f(f(x))),...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)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)=x2+c(modn)f(x)=x^2 + c \pmod n. Với x1=0,c=24,n=9409x_1=0, c= 24, n=9409, quan sát 100100 giá trị đầu tiên của dãy ngẫu nhiên:

image.png

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=9400n=9400:

image.png

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)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)f(x) phù hợp với từng trường hợp của nn.

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ố nn có thể thấy cơ chế RSA này đảm bảo an toàn do độ dài khóa công khai nn lên tới 20482048 bit. Tuy nhiên, chúng ta chú ý tới cách sinh hai số nguyên tố lớn p,qp,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ố gg có độ dài 10001000 bit, sinh ra hai số nguyên tố p,qp,q lớn theo công thức:

p=2ga+1q=2gb+1p = 2 * g * a + 1\\ q = 2 * g * b + 1

Cách sinh số đặc biệt này cho biết p1p-1q1q-1 tồn tại một ước nguyên tố chung là gg (10001000 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ố nn dài 20482048 bit ra thừa số nguyên tố trong trường hợp này. Thật vậy, khi đó ta có:

n1=p×q1=(pqpq+1)+(p1)+(q1)=(p1)(q1)+(p1)+(q1)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 gg ta có:

n1(p1)(q1)+(p1)+(q1)(modg)n10(modg)n1(modg)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)=xn1+3(modn)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(pg)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ố ppqq:

image.png

Tài liệu tham khảo


All Rights Reserved

Viblo
Let's register a Viblo Account to get more interesting posts.