3.1K 228 109

Đã đăng vào Thứ Sáu, 6:36 SA 3 phút đọc

Giải thuật Euclid mở rộng (extended Euclidean algorithm) và phương trình ax+by=c

I. Phương trình ax+by=c

Xét phương trình $ax+by=c$ với các hệ số nguyên, cần tìm $(x,y)$ là các ẩn nguyên. Đặt $d = gcd(a, b)$ (ước chung lớn nhất), khi đó tồn tại các số nguyên $x,y$ sao cho $ax+by=d$ . Từ kết quả có thể chứng minh được điều kiện cần và đủ để phương trình $ax+by=c$ có nghiệm nguyên là $gcd(a, b)$ là ước của $c$ (Bạn đọc tự chứng minh).

II. Thuật toán Euclid tìm ƯCLN

Bài toán tìm ước chung lớn nhất của hai số nguyên dương $a$ và $b$ đã quá quen thuộc với chúng ta, trong đó cách cài đặt bằng thuật toán Euclid đạt hiệu quả cao về tốc độ tính toán cũng như hiệu suất. Ý tưởng như sau:

Giả sử $a>b$ , đem $a$ chia cho $b$ thu được số dự $r$ , chúng ta tiếp tục đi tìm ước chung lớn nhất của cặp số $(b, r)$
Coi $(b, r)$ là $(a, b)$ và làm tương tự như trên cho tới khi thu được số dư bằng $0$ .

Chương trình minh họa bằng Python:

def euclidean_gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

III. Giải thuật Euclid mở rộng (extended Euclidean algorithm) và phương trình ax+by=c

Để giải phương trình Diophantine $ax+by=c$ trên, một ý tưởng hiệu quả là sử dụng giải thuật Euclid mở rộng kết hợp thuật toán tìm ƯCLN được đề cập trên. Gọi $d=gcd(a,b)$ , trước hết chúng ta tìm nghiệm của phương trình $ax+by=d$ . Khi phương trình này có nghiệm $(x_0,y_0)$ thì rõ ràng $(\frac{cx_0}{d},\frac{cy_0}{d})$ là nghiệm của phương trình $ax+by=c$ .

Không mất tính tổng quát, giả sử $a>b>0$ . Đặt $(a, b)=(r_0, r_1)$ , đem chia $r_0$ cho $r_1$ thu được thương $q_1$ và dư $r_3$ . Tiếp tục chia $r_1$ cho $r_2$ thu được thương $q_2$ và dư $r_4$ , ... Lặp lại quá trình cho tới khi thu được số dư $r_{m+2}=0$ sau hữu hạn bước. Ta có:

$r_0=q_1\times r_1+r_2\\ r_1=q_2\times r_2+r_3\\ ...\\ r_{m-1}=q_m\times r_m+r_{m+1}\\ r_{m}=q_{m+1}\times r_{m+1}$

Với $0<r_{m+1}<r_m<...<r_2<r_1$ . Lúc này $r_{m+1}$ cũng chính là $d$ , sử dụng công thức truy hồi, chúng ta sẽ tìm các $x_i,y_i$ sao cho:

$ax_i+by_i=r_i$

Với $i=0$ , có $ax_0+by_0=r_0=a$ , chọn $(x_0,y_0)=(1,0)$

Với $i=1$ , có $ax_1+by_1=r_1=b$ , chọn $(x_1,y_1)=(0,1)$

Như vậy có hai giá trị đầu tiên của $x_i, y_i$ là $x_0=1, x_1=0, y_0=0, y_1=1$ .

Từ $r_i=q_{i+1}\times r_{i+1} + r_{i+2}$ suy ra:

$r_i - q_{i+1}\times r_{i+1} = r_{i+2}\\ (a\times x_i+b\times y_i) - q_{i+1}\times (a\times x_{i+1}+b\times y_{i+1}) = r_{i+2}\\ a\times (x_i-q_{i+1}\times x_{i+1}) + b\times (y_i-q_{i+1}\times y_{i+1}) = r_{i+2}$

Có thể chọn $x_{i+2}=x_i-q_{i+1}\times x_{i+1}$ và $y_{i+2}=y_i-q_{i+1}\times y_{i+1}$ . Kết hợp $x_0=1, x_1=0, y_0=0, y_1=1$ chúng ta có công thức truy hồi để tính $x_i, y_i$ . Sau khi có được nghiệm của phương trình $ax+by=d$ thì dễ dàng có được nghiệm của $ax+by=c$ . Giải thuật được mô tả qua mã giả như sau:

{Thuật toán Euclide: a, b không đồng thời bằng 0, trả về gcd(a, b)}
function gcd(a, b);
begin
  while b ≠ 0 do
    begin
      r:= a mod b; a:= b; b:= r;
    end;
  Result:= a;
end;
{Thuật toán Euclide mở rộng: a, b không đồng thời bằng 0, trả về cặp (x, y) sao cho a * x + b * y = gcd(a, b)
Về tư tưởng là ghép quá trình tính cặp số (x, y) vào trong vòng lặp chính của thuật toán Euclide.}
function Extended_gcd(a, b); 
begin
  (xa, ya):= (1, 0);
  (xb, yb):= (0, 1);
  while b ≠ 0 do
    begin
      q:= a div b;
      r:= a mod b; a:= b; b:= r; //Đoạn này giống thuật toán Euclide.
      (xr, yr):= (xa, ya) - q * (xb, yb); //Hiểu là: (xr, yr):= (xa, ya) "mod" (xb, yb);
      (xa, ya):= (xb, yb);
      (xb, yb):= (xr, yr);
    end;
  Result:= (xa, ya);
end;

IV. Ứng dụng trong mật mã RSA

1. Tìm số nghịch đảo - số mũ bí mật d

Cùng nhớ lại thuật toán RSA, sau khi chọn được số mũ công khai $e$ , chúng ta cần chọn số mũ bí mật $d$ thỏa mãn:

$de \equiv 1 \pmod{\phi(n)}$

Hay $de$ có thể viết lại thành $de=k\times \phi(n) + 1$ , tức $(d, k)$ là một cặp nghiệm của phương trình:

$xe + y\phi(n) = 1$

Đây chính là phương trình dạng $ax+by=c$ với $c=1$ . Điều kiện có nghiệm của phương trình là $gcd(e, \phi(n))=1$ - lý giải cho vì sao chúng ta cần chọn số mũ công khai $e$ thỏa mãn điều kiện này.

Bỏ qua vấn đề an toàn, xét ví dụ với $\phi(n)=29, e = 8$ , dựa vào giải thuật Euclid mở rộng trên chúng ta có bảng sau:

Bước $i$	$r_{i}$	$r_{i+1}$	$r_{i+2}$	$q_{i+1}$	$x_{i}$	$x_{i+1}$	$x_{i+2}$	$y_{i}$	$y_{i+1}$	$y_{i+2}$
0	29	8	5	3	1	0	1	0	1	-3
1	8	5	3	1	0	1	-1	1	-3	4
2	5	3	2	1	1	-1	2	-3	4	-7
3	3	2	1	1	-1	2	-3	4	-7	11
4	2	1	0	2

Từ đây thu được nghiệm $(x,y)=(11,-3)$ nên $d=11$ . Kiểm tra lại có $de=88$ chia cho $29$ dư $1$ (thỏa mãn).

2. Challenge CTF 1

David and George have been sharing secrets in the office. They have been using RSA, but every time they send messages to each other they send the same message twice with different e&d pairs.

n = 821145496340604994326551113777327586712517116620710138023054342574561508685841651221395336923009432483632922988810280492233212938499610799302600039372236950091107415608469420373862484991247563501588476379781833166384349047256248750305151647368869191030962402077545654309677921204852761327474210545126231678365653938950875121407802825449417647436581800984094019773441138824103100874107518637740157619401903676758887305144344197013469731097784600887460586080710165172482576075554962211636042250812985660796823586807936400193119329788414901163974273519389637577743274602328794149195160641844665952005304891539239569281271190359677800733335753851272087825367905649608365380311871961227784025384860567980372211829089046263037976143489649037301004190176743451524855021975173331377848869766803669380738028850423188441730950930293351831551235608896471056414832724437298313834205316903183915777214359716054610505148862937481302816735818707845634855944420246486170440894211568345806270149624349863659569587253363399011002661439234940175509430324800131974720796290147011359912907511800794856022323351326527433065369890076901244769188559744857014437935275331668815662843342949028524668792900934778393081540969378177946315133482100129146436669233497
e1 = 65537
e2 = 65541
c1 = 780658436829916376849384953245046160585006566851042012704483209702863678062476060756861957431999166629960572489603381700463275558025911158723111813760955911506337953716534563343115021823289248053271415861008199599068709619941387500593662710034484419278437304369245662463380173948899883854712600886743561289754388478767465223935093798360125367362879875535793567716252747828959165300728670927677586083626110399715409764034270617075449717200906494499007185580184170259914847655677050502720118962936087740966849768882421990167461773397556896691265675635559329081186546667946536578010983532961277846787291599634467295299791558850634527709927175609022598253337622813256745216579309329227079025559132092995655055119144058999133469290767315748585571388688867103997098949375862975626251519059108022935941373746765178464580101421855461208548905080081593390398889796527136710377487129081581831121286368672927500388994836835845435585150657365737164257330248359564521338736375940961805472256343202225082865355879734551573811089188154855414127614241972020512898828117635938918343107026058446893772322369436471625258214860657502565115735633197652559346691974162384457065240574498012155398418564013515671469264618447355250305094991187170237948576532077
c2 = 735256250724848919984419549223350440687010098689497431056824014318841425273065986563198012277778606699050926497774004587167419278887354216966505104389832590247499586117280759436568682554909948301402068424408481233976792164353363568704843297902646179376701101900716343576808207672817119703685570017152992516703199387294606025366214936169620062431844539552660353581055307719518672730666646883176367112225249117457203626111247753957934293964536347814602877293954317021311068194603103261553902983633945548264531851583976628406674945528700774166193949004095627256850179767579796266297204984826579278250065231424113006680578898890762351089566765496523085076722100692059011518474695680484208750408305954465250291735352661456585824028043147958682132602952760603303724587765805310693061276622110845551989485749458552976541846731437090553929509382776662651311781608275507521192811542982284336804252667371580739212453551948383592762228515781281038213490066164297052624301734231340763458124727723598624463430414991981456321144843359843333762263992265225858385273530114542865878399383406365897452952175231015883782841247741656618056534670777373786071766344721200071296309102595821678398629910918245754738867818121283533241588042800700371495337081540

Đề bài nói về quá trình gửi thông điệp giữa David và George được mã hóa bằng RSA, nhưng mỗi lần sử dụng hai cặp khóa $(e,d)$ khác nhau. Từ các thông tin được challenge cung cấp, chúng ta cần tìm ra thông điệp $m$ - chính là flag.

Do thông điệp được mã hóa bằng hai cặp khóa bí mật thu được hai bản mã $c_1$ và $c_2$ nên ta có:

$c_1 \equiv m^{e_1} \pmod{n}\\ c_2 \equiv m^{e_2} \pmod{n}$

Có thể bạn đọc đang thắc mắc challenge này có vẻ như đơn thuần là kiến thức liên quan tới RSA, sẽ cố gắng đi tìm các số mũ bí mật $d_1, d_2$ . Tuy nhiên, chú ý rằng $gcd(e_1,e_2)=1$ , nên từ thuật toán Euclid mở rộng cho thấy chúng ta có thể tìm ra hai số $a,b$ sao cho:

$a\times e_1 + b\times e_2 = 1$

def gcdExtended(e1, e2):  

    # Base Case  
    if e1 == 0 :   
        return e2, 0, 1

    gcd, a1, b1 = gcdExtended(e2 % e1, e1)  

    # Update a and b using results of recursive  
    # call  
    a = b1 - (e2 // e1) * a1  
    b = a1  

    return gcd, a, b

Từ đây, ta có:

$m = m^{ae_1 + be_2} = m^{ae_1}\times m^{be_2} = (m^{e_1})^a\times (m^{e_2})^b\\ \equiv c_1^a\times c_2^b \pmod{n}$

Bạn đọc hãy dựa vào gợi ý các bước trên đưa ra chương trình tìm ra flag nhé!

3. Challenge CTF 2 - sRSA (RaRCTF 2021)

Challenge cung cấp hai file script.py và output.txt:

# script.py
from Crypto.Util.number import *

p = getPrime(256)
q = getPrime(256)
n = p * q
e = 0x69420

flag = bytes_to_long(open("flag.txt", "rb").read())
print("n =",n)
print("e =", e)
print("ct =",(flag * e) % n)

n = 5496273377454199065242669248583423666922734652724977923256519661692097814683426757178129328854814879115976202924927868808744465886633837487140240744798219
e = 431136
ct = 3258949841055516264978851602001574678758659990591377418619956168981354029697501692633419406607677808798749678532871833190946495336912907920485168329153735

Dễ dàng kiểm tra $e$ và $n$ là hai số nguyên tố cùng nhau, nên có thể sử dụng thuật toán Euclid mở rộng tìm được hai số $u$ và $v$ thỏa mãn:

$e\times u + v\times n = 1$

Sử dụng module $n$ suy ra:

$eu \equiv 1 \pmod{n}\ (1)$

Do (flag * e) % n = ct nên:

$ct \equiv flag \times e \pmod{n}\\ \rightarrow ct\times u \equiv flag \times e\times u \pmod{n}\\ \rightarrow ct\times u \equiv flag \pmod{n}\text{ do (1)}$

Tức là chúng ta chỉ cần tính $ct\times u \pmod{n}$ là có thể tìm ra flag. Do $u$ có thể dễ dàng tìm được bằng cách sử dụng thuật toán Euclid mở rộng nên hoàn toàn có thể tìm ra flag. Phần cài đặt chương trình xin dành cho bạn đọc.

Tài liệu tham khảo

Bước $i$	$r_{i}$	$r_{i+1}$	$r_{i+2}$	$q_{i+1}$	$x_{i}$	$x_{i+1}$	$x_{i+2}$	$y_{i}$	$y_{i+1}$	$y_{i+2}$
0	29	8	5	3	1	0	1	0	1	-3
1	8	5	3	1	0	1	-1	1	-3	4
2	5	3	2	1	1	-1	2	-3	4	-7
3	3	2	1	1	-1	2	-3	4	-7	11
4	2	1	0	2

Bước $i$	$r_{i}$	$r_{i+1}$	$r_{i+2}$	$q_{i+1}$	$x_{i}$	$x_{i+1}$	$x_{i+2}$	$y_{i}$	$y_{i+1}$	$y_{i+2}$
0	29	8	5	3	1	0	1	0	1	-3
1	8	5	3	1	0	1	-1	1	-3	4
2	5	3	2	1	1	-1	2	-3	4	-7
3	3	2	1	1	-1	2	-3	4	-7	11
4	2	1	0	2