IV. Một số kỹ thuật tấn công n - phân tích số lớn ra tích hai thừa số nguyên tố (tiếp)

2. Tấn công với số n không phải tích hai số nguyên tố lớn

Một số bạn có thể thắc mắc, mật mã RSA thực chất là bài toán lũy thừa trong module số $n$, vậy thì tại sao buộc phải chọn $n$ là tích hai số nguyên tố lớn. Có thể chọn $n$ chỉ là một số đủ lớn, hay thậm chí chỉ là một số nguyên tố đủ lớn hay không?

Khi $n$ không tuân thủ nguyên tắc là tích hai thừa số nguyên tố lớn, sẽ ảnh hưởng tới tính bí mật của giá trị $\phi(n)$. Thật vậy, trong trường hợp $n$ chứa các ước là hợp số, chúng ta có thể tiếp tục phân tích các ước hợp số đó ra thừa số nguyên tố, ... làm giảm độ khó của bài toán phân tích từ $n$ xuống các ước của $n$ và tương tự có thể giảm tiếp. Khi đó, độ khó trong việc tìm ra $\phi(n)$ sẽ giảm, ảnh hưởng trực tiếp tới tính bảo mật của số mũ bí mật $d$. Khi kẻ tấn công tính ra được $d$, họ dễ dàng tính ngược lại thông điệp gốc.

Nếu $n$ chỉ được chọn là một số nguyên tố lớn, $\phi(n)$ sẽ có giá trị ngay lập tức bằng $n-1$.

Challenge luyện tập cho trường hợp này: Monoprime.

Nếu $n$ được tính bằng tích nhiều thừa số nguyên tố: so với trường hợp $n$ có cùng độ lớn nhưng tạo bởi tích hai thừa số nguyên tố, trường hợp này có khả năng cao hơn bị phân tích thành công do độ lớn các thừa số nguyên tố tỉ lệ nghịch với số lượng thừa số.

Challenge luyện tập cho trường hợp này: Manyprime.

Bởi vậy, khi xây dựng bộ khóa cho RSA, cần đảm bảo số $n$ là tích hai thừa số nguyên tố lớn, việc này mục đích chính là cản trở khả năng số $n$ bị phân tích ra tích các thừa số nguyên tố - công việc bắt buộc cần làm để tính ra $\phi(n)$.

3. Tấn công số $n$ với cặp số nguyên tố giống nhau

Một câu hỏi nối tiếp từ phần $2$, để tiết kiệm thời gian, chúng ta chỉ chọn một số nguyên tố $p$ và sử dụng nó hai lần để thu được số $n$, hay nói cách khác, chọn $n$ là bình phương của một số nguyên tố đủ lớn có an toàn không?

Khi sử dụng công thức tính hàm $\phi()$, chúng ta có ngay kết quả $\phi(n)=p(p-1)$. Bài toán trở về khai căn bậc hai một số nguyên lớn. Chỉ số bảo mật của cách chọn số nguyên tố này không hẳn là lỏng lẻo như phần trên, tuy nhiên, bài toán khai căn một số nguyên lớn dễ dàng giải quyết hơn bài toán phân tích ra thừa số nguyên tố. Chẳng hạn chúng ta có thể sử dụng hàm isqrt() trong module math.

a = isqrt(1024)
print(a) # 32

Bạn đọc có thể luyện tập với challenge Square Eyes

4. Fermat attack

Trong trường hợp hai số nguyên tố $p$, $q$ được chọn có độ lớn gần nhau, tức $|p-q|$ khá nhỏ, chúng ta có thể sử dụng kỹ thuật tấn công Fermat để tìm ra chúng. Vì $p$, $q$ là hai số nguyên tố lẻ (trường hợp chúng đủ lớn) nên có thể viết (giả sử $p>q$):

$$p + q = 2a \\ p - q = 2b$$

Từ đây có:

$$p = a + b\\ q = a - b$$

Viết lại số $n$:

$$n = p \times q = (a+b)(a-b)=a^2-b^2\\ \rightarrow b^2 = a^2 - n$$

Vì số $b=\frac{p - q}{2}$ nhỏ nên có thể coi:

$$\begin{cases} a \approx \sqrt{n}\\ a \geq \sqrt{n} \end{cases}$$

Nên chúng ta chỉ cần thử bắt đầu từ giá trị $a = \lfloor \sqrt{n} \rfloor$ (phần nguyên cận dưới), tăng dần $a$ cho tới khi $a^2 - n$ là số chính phương, là thu được $a$ và $b$. Cài đặt hàm bằng chương trình Python như sau:

def fermat(n):
    a = isqrt(n)
    check = n - a * a
    b = isqrt(check)
    while b * b != check:
        a = a + 1
        check = a * a - n
        b = isqrt(check)
    p = a + b
    q = a - b
    return p, q

Điều kiện để phương pháp tấn công Fermat hoạt động hiệu quả nhất là khi $|p-q|<n^{\frac{1}{4}}$. Bài tập dành cho bạn đọc: Hãy tìm ra flag với bộ khóa public như sau:

n = 966808932627497190635859236054960349099463975227350564265384373280336699853387254070662881265937565163000758606154308757944030571837175048514574473061401566330836334647176655282619268592560172726526643074499534129878217409046045533656897050117438496357231575999185527675071002803951800635220029015932007465117818739948903750200830856115668691007706836952244842719419452946259275251773298338162389930518838272704908887016474007051397194588396039111216708866214614779627566959335170676055025850932631053641576566165694121420546081043285806783239296799795655191121966377590175780618944910532816988143056757054052679968538901460893571204904394975714081055455240523895653305315517745729334114549756695334171142876080477105070409544777981602152762154610738540163796164295222810243309051503090866674634440359226192530724635477051576515179864461174911975667162597286769079380660782647952944808596310476973939156187472076952935728249061137481887589103973591082872988641958270285169650803792395556363304056290077801453980822097583574309682935697260204862756923865556397686696854239564541407185709940107806536773160263764483443859425726953142964148216209968437587044617613518058779287167853349364533716458676066734216877566181514607693882375533
c = 168502910088858295634315070244377409556567637139736308082186369003227771936407321783557795624279162162305200436446903976385948677897665466290852769877562167487142385308027341639816401055081820497002018908896202860342391029082581621987305533097386652183849657065952062433988387640990383623264405525144003500286531262674315900537001845043225363148359766771033899680111076181672797077410584747509581932045540801777738548872747597899965366950827505529432483779821158152928899947837196391555666165486441878183288008753561108995715961920472927844877569855940505148843530998878113722830427807926679324241141182238903567682042410145345551889442158895157875798990903715105782682083886461661307063583447696168828687126956147955886493383805513557604179029050981678755054945607866353195793654108403939242723861651919152369923904002966873994811826391080318146260416978499377182540684409790357257490816203138499369634490897553227763563553981246891677613446390134477832143175248992161641698011195968792105201847976082322786623390242470226740685822218140263182024226228692159380557661591633072091945077334191987860262448385123599459647228562137369178069072804498049463136233856337817385977990145571042231795332995523988174895432819872832170029690848
e = 65537

V. Thuật toán Pollard

1. Tấn công phân tích nhân tử theo thuật toán Pollard $\rho - 1$

Trước hết, chúng ta cần biết tới khái niệm B-powersmooth. Xét một số nguyên dương $M$, giả sử phân tích số $M$ ra tích các thừa số nguyên tố thu được $k$ số lũy thừa như sau:

$$M = p_1^{s_1}\times p_2^{s_2}\times ... \times p_k^{s_k}$$

Trong đó $p_i^{s_i} = max\{p_1^{s_1}, p_2^{s_2}, ..., p_k^{s_k}\}$ thì ta gọi $M$ là một số $p_i^{s_i}-\text{powersmooth}$.

Ví dụ: Số $1302=2\times 3\times 7\times 31$ là số $31-\text{powersmooth}$, số $3696=2^4\times 3\times 7\times 11$ là số $16-\text{powersmooth}$.

Về khái niệm này chúng ta có tính chất như sau: $M$ là số $B-\text{powersmooth}$, giai thừa $B!=1\times 2\times 3\times ... \times (B-1)\times B$ thì:

$$M\ |\ B!$$

Có thể chứng minh điều này đơn giản: Với bất kỳ $p_i^{s_i}\leq B$ thì từ $1$ đến $B$ luôn có $s_i$ số là bội của $p_i$ nên $p_i^{s_i}\ |\ B!$ (với $1\leq i\leq k$ bất kỳ), mà $k$ số $p_1^{s_1}, p_2^{s_2}, ... , p_k^{s_k}$ đôi một nguyên tố cùng nhau nên $p_1^{s_1}\times p_2^{s_2}\times ... \times p_k^{s_k}\ |\ B!$ hay $M\ |\ B!$.

Tiếp theo, để hiểu được ý tưởng của thuật toán Pollard's p - 1, tôi sẽ cùng các bạn tiếp cận theo hướng giải quyết bài toán tìm một ước nguyên tố của $n$.

• Thay vào đó, chúng ta sẽ đi theo một hướng gián tiếp bằng cách tìm một số $s$ không nguyên tố cùng nhau với $n$, khi đó $gcd(s, n)$ chắc chắn là một ước của $n$.
• Giả sử $p$ là một ước nguyên tố của $n$, thì số $s$ cần tìm là một bội của $p$.
• Đặt $x = s + 1$ thì $x \equiv 1 \pmod {p}$, chúng ta đi tìm $x$ theo module $p$.
• Áp dụng định lý nhỏ Fermat có: $2^{p-1}\equiv 1 \pmod {p}$, số $x$ sẽ được chọn là bội của $2^{p-1}$.
• Lúc này vẫn đề lại quay trở về tìm ra $p-1$, nhưng điều này không khác gì việc tìm ra $p$? Thay vào đó, chúng ta sẽ tìm ra một bội của $p-1$, cũng sẽ thỏa mãn được điều kiện của $x$ vì $2^{(p-1)t}\equiv 1 \pmod {p}$
• Nhớ lại tính chất powersmooth trên. Nếu $p-1$ là số $B-\text{powersmooth}$ thì có $B!$ là một bội của $p-1$.
• Tức là số $x$ được chọn bằng $2^{B!} \pmod {p}$.

Sau khi tìm được $B$ thì có:

$$x = 2^{B!} \pmod {p}\\ \rightarrow s = x - 1$$

Do tính theo phép tính module nên có $s < n$ hay $p = gcd(s, n)$

Như vậy, chúng ta đã đưa từ bài toán tìm ước nguyên tố của $n$ trở về bài toán tìm số $B$ là thừa số nguyên tố lũy thừa lớn nhất của $p-1$. Cụ thể, khi $p-1=p_1^{s_1}\times p_2^{s_2}\times ... \times p_k^{s_k}$ thì:

$$B=p_i^{s_i} = max\{p_1^{s_1}, p_2^{s_2}, ..., p_k^{s_k}\}$$

Vì $p$ là số nguyên tố nên số $p-1$ có thể phân tích thành tích nhiều thừa số nguyên tố nhỏ hơn khác. Độ lớn giá trị của số $p$ (cần tìm ban đầu) đã được giảm xuống rất nhiều thành giá trị của $B$ theo cách xác định đã nêu.

Cài đặt kỹ thuật tấn công Pollard's p - 1 bằng ngôn ngữ Python khá đơn giản như sau:

a = 2
B = 2
while True:
    a = pow(a, B, N)
    res = gcd(a - 1, N) # hàm gcd()
    if res != 1 and res != N:
        q = N // res
        print("B = ", B)
        print("p = ", res)
        print("q = ", q)
        break
    B += 1

Dễ dàng nhận thấy độ hiệu quả của phương pháp này càng tăng khi $p-1$ hoặc $q-1$ có thể phân tích ra thành tích của càng nhiều thừa số nguyên tố, vì khi đó $B$ càng nhỏ.

Challenge dành cho bạn đọc:

N = 1224542620373200232525165378018470774334801515191193204875465445916504222883935188890019876845076388385357911730689547124547346252951158814249284724565588433721828377715469374541007756509231399263095022024229078845538543233785364809917406108015271780070196140628158427541531563472532516237632553353655535922926443707617182025475004547531104052989085765070550150028833424395972178427807901747932614235844448614858629761183210600428438018388051958214596857405813088470933109693499438012040822262549119751099008671892966082341548512112435591881692782766559736840448702039918465573051130405935280702181505538733234675792472428666968900055706926735800561218167237812066851519973807203332801575980055838563085817664973968944323258406789203078387708964307931318918136664885818917720073433998810127482159223895026085726623747340692196977140382318293090736558135980651252533606603312148824142669800602887109353065489282386215179238458743567166284295855288783740314247952124965482197632971993708775190564519250754150756867653033527903848903210074426177258586450311109023467944412194124015505951966140443860862968311560843608415723549525497729679097936310538451467530605937684408079363677707513923579164067808729408365886209340192468399685190639
c = 145742860621666495489510776707734134231023214235535481878205099324276369445463746101469487674333600296204530932386373415987357363515200117271393133347844479863240936801112306080456942844796779477817786176831015954410967693647534326733641573842953783193563678040093734579772976410574013857063137696465850300484753282472377882118892522844694078667622111244886303620349388556315704648609353412177123230438077637042880490566244740468503369707900343076369151796123461132932226563486870411965536062339169788331659119981901553536009275158600580698576110294775989992794065611215170351808698605911258789407992833170968332058255364527244293283228694886707241979238145252395651417561576433516407782575454294499521347378058366557950770592472271985004818847838711060048422015207674862177145761946560579360220239667890707135827136815780729363013864130107808776517514214310689477005999830284272130148939734935547341627208913181919190392205389452185597444280635342938046191904062547803917870268485346888653569349729643793041018550170090471310374856687407102762116819004790791936814214507908374380597027347007448114684844276041116955473180015221164545212550832233007714133699817366745648092776901013502840540012912660742166994968977400188176557657864
e = 0x10001

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://crypto.stackexchange.com/questions/5170/why-do-we-need-in-rsa-the-modulus-to-be-product-of-2-primes
• https://en.wikipedia.org/wiki/Pollard's_p_−_1_algorithm