Trong ký RSA tìm n từ e và nhiều cặp m và c

Khi ký sử dụng RSA với $e = 65537$ và nhiều cặp m và c, ở đâu $$c^e \bmod (n)=m$$ có cách nào để tìm n (n là 2048 bit) không?

tôi đã lên kế hoạch về máy tính $ c^e-m $ và sau đó coi chúng là cơ sở cho một mạng tinh thể. Nhưng mà $c^e$ quá lớn.

có cách nào để tìm n (n là 2048 bit) không?

Có, nếu bạn giả sử phần đệm xác định (đôi khi được sử dụng cho chữ ký, có vẻ như đây là trường hợp bạn đang xem xét)

Bạn đang đi đúng hướng bằng cách xem xét $c^e - m$ (sẽ là bội số của $n$); cho rằng chúng tôi có một số, những gì chúng tôi có thể làm là lấy hai và tính toán:

$$\gcd( c^e-n, c'^e-m' )$$

Cái này sẽ $n$ (nhân với một số nguyên có xác suất nhỏ cao; dễ loại bỏ); đó là câu trả lời của bạn.

Các giá trị chúng tôi đang lấy GCD là khoảng $2^{27}$ độ dài bit - sử dụng thuật toán nhị phân hoặc Euclide tiêu chuẩn có thể sẽ mất nhiều thời gian hơn chúng ta muốn chờ đợi. Tuy nhiên, Thuật toán GCD của Lehmer nên đưa nó vào một phạm vi không thể chịu đựng được ...