Chủ đề 4: Chủ đề 4: Mã hóa bất đối xứng Mã hóa bất đối xứng

Mở đầu Mở đầu

trong ccáácc hhệệ ththốốngng mãmã hhóóaa quyquy ưướớcc chung mãmã khkhóóaa kk gigiữữaa ngưngườờii ggửửii A A vvàà

dung ccủủaa mãmã khkhóóaa kk

thông tin tin vvềề mãmã , do đđóó, , ccầầnn ccóó ssựự traotrao đđổổii thông

, A vvàà B B phphảảii traotrao đđổổii vvớớii nhaunhau

VVấấnn đđềề phpháátt sinhsinh trong llàà viviệệcc quyquy ưướớcc chung ngưngườờii nhnhậậnn B. B. TrênTrên ththựựcc ttếế, , nhunhu ccầầuu thaythay đđổổii nnộộii dung llàà ccầầnn thithiếếtt, do khkhóóaa kk gigiữữaa A A vvàà B. B. ĐĐểể bbảảoo mmậậtt mãmã khkhóóaa kk, A trêntrên mmộộtt kênhkênh liênliên llạạcc ththậậtt ssựự an an totoàànn vvàà bbíí mmậậtt. . nhiên, , rrấấtt khkhóó ccóó ththểể bbảảoo đđảảmm đưđượợcc ssựự an an totoàànn TuyTuy nhiên ccủủaa kênhkênh liênliên llạạcc nênnên mãmã khkhóóaa kk vvẫẫnn ccóó ththểể bbịị phpháátt hihiệệnn bbởởii ngưngườờii C! C!

Mở đầu Mở đầu

công ccộộngng đưđượợcc Whitfield DiffieDiffie ttạạii

Martin Hellman ccủủaa Martin

Stanford gigiớớii thithiệệuu vvààoo nămnăm 1976. 1976. phương phpháápp DiffieDiffie--Hellman Whitfield DiffieDiffie đãđã đưđượợcc công

công bbốố. . 1977, trêntrên bbááoo ""The Scientific American

Ronald Rivest

Rivest, , AdiAdi Shamir phương phpháápp RSA, RSA, phương

The Scientific American", ", nhnhóómm Leonard Shamir vvàà Leonard công bbốố phương phương phpháápp công ccộộngng nnổổii titiếếngng vvàà đưđượợcc ssửử ddụụngng rrấấtt trong ccáácc ứứngng ddụụngng mãmã hhóóaa vvàà bbảảoo vvệệ

Ý Ý tưtưởởngng vvềề hhệệ ththốốngng mãmã hhóóaa khkhóóaa công Martin Hellman, Ralph MerkleMerkle vvàà Whitfield Martin Hellman, Ralph ĐĐạạii hhọọcc Stanford SauSau đđóó, , phương Hellman vvàà Whitfield Hellman NămNăm 1977, ttáácc gigiảả Ronald Adleman đãđã công Adleman mãmã hhóóaa khkhóóaa công nhinhiềềuu hihiệệnn nay nay trong thông tintin thông

Mở đầu Mở đầu

công ccộộngng ssửử ddụụngng haihai loloạạii khkhóóaa

MMộộtt hhệệ ththốốngng khkhóóaa công trong ccùùngng mmộộtt ccặặpp khkhóóaa: : trong

công bbốố rrộộngng rãirãi công ccộộngng (public key)

(public key) đưđượợcc công tin, thông tin, trong mãmã hhóóaa thông

riêng (private key)

(private key) chchỉỉ do do mmộộtt ngưngườờii nnắắmm gigiữữ tin đãđã đưđượợcc mãmã thông tin

công ccộộngng. . khkhóóaa công vvàà đưđượợcc ssửử ddụụngng trong khkhóóaa riêng vvàà đưđượợcc ssửử ddụụngng đđểể gigiảảii mãmã thông hhóóaa bbằằngng khkhóóaa công

CCáácc phương phương phpháápp mãmã hhóóaa nnààyy khaikhai ththáácc nhnhữữngng áánhnh xxạạ ff mmàà viviệệcc ththựựcc hihiệệnn áánhnh xxạạ ngưngượợcc f f ––11 rrấấtt khkhóó so so vvớớii viviệệcc ththựựcc hihiệệnn áánhnh xxạạ ff. . ChChỉỉ khikhi bibiếếtt đưđượợcc mãmã khkhóóaa riêng ththìì mmớớii ccóó ththểể ththựựcc hihiệệnn đưđượợcc áánhnh xxạạ ngưngượợcc f f ––11 . . riêng

công ccộộngng MãMã hhóóaa khkhóóaa công Mã hóa khóa công cộng

Phương pháp RSA Phương pháp RSA

1978, R.L.Rivest

L.Adleman đãđã đđềề RSA (hay còncòn A.Shamir vvàà L.Adleman công ccộộngng RSA (hay

) = (pp––1) (1) (qq––1) 1) R.L.Rivest, , A.Shamir NămNăm 1978, xuxuấấtt hhệệ ththốốngng mãmã hhóóaa khkhóóaa công đưđượợcc ggọọii llàà ““hhệệ ththốốngng MITMIT””). ). phương phpháápp nnààyy, , ttấấtt ccảả ccáácc phphéépp ttíínhnh đđềềuu Trong phương Trong đưđượợcc ththựựcc hihiệệnn trêntrên ZZnn vvớớii nn llàà ttííchch ccủủaa haihai ssốố nguyên nguyên ttốố llẻẻ pp vvàà qq khkháácc nhaunhau. . KhiKhi đđóó, , tata ccóó φφ((nn) = (

Phương pháp mã hóa RSA Phương pháp mã hóa RSA

nguyên ttốố llẻẻ phânphân bibiệệtt. .

, nguyên ttốố,

k = (n, p, q, a, b) ) ∈∈ KK, , đđịịnhnh nghnghĩĩaa::

) = xxbb mod mod nn vvàà ddkk((yy) = ) = yyaa mod mod nn, , vvớớii xx, , yy ∈∈ ZZnn

(public key) công bbốố (public key)

n n = = pqpq vvớớii pp vvàà qq llàà haihai ssốố nguyên P = C = ZZn n vvàà đđịịnhnh nghnghĩĩaa:: Cho Cho P = C = KK = {(= {((n, p, q, a, b (n, p, q, a, b): ): n n = = pqpq, , pp, , qq llàà ssốố nguyên 1 (mod φφ((nn))}))} abab ≡≡ 1 (mod VVớớii mmỗỗii k = (n, p, q, a, b eekk((xx) = GiGiáá trtrịị nn vvàà bb đưđượợcc công (private key) GiGiáá trtrịị pp, , qq, , aa đưđượợcc gigiữữ bbíí mmậậtt (private key)

Sử dụng phương pháp RSA Sử dụng phương pháp RSA

nguyên ttốố ccóó gigiáá trtrịị llớớnn pp vvàà qq

) = (p p –– 1) (1) (q q –– 1)1)

nguyên bb (1 < (1 < b b < < φφ((nn)) )) ththỏỏaa

công bbốố ((khkhóóaa công

PhPháátt sinhsinh haihai ssốố nguyên TTíínhnh n n = = pqpq vvàà φφ((nn) = ( nhiên mmộộtt ssốố nguyên ChChọọnn ngngẫẫuu nhiên gcd(gcd(bb, , φφ((nn)) = 1 )) = 1 TTíínhnh gigiáá trtrịị aa = = bb––11 mod mod φφ((nn) () (bbằằngng thuthuậậtt totoáánn Euclide Euclide mmởở rrộộngng)) GiGiáá trtrịị nn vvàà bb đưđượợcc công công ccộộngng) ) riêng)) gigiáá trtrịị pp, , qq, , aa đưđượợcc gigiữữ bbíí mmậậtt ((khkhóóaa riêng

VíVí dụdụ

p=5 & q=7 p=5 & q=7 =(4)*(6) = 24 n=5*7=35 vvàà φφ((nn) ) =(4)*(6) = 24 n=5*7=35 b = 5 b = 5 a = 29 , (29x5 ––1) 1) chiachia hhếếtt chocho 24 24 a = 29 , (29x5 CCặặpp khkhóóaa đưđượợcc xxáácc đđịịnhnh nhưnhư sausau::

KhKhóóaa công KhKhóóaa riêng MãMã hhóóaa ttừừ love

) = (35,5) công ccộộngng: (: (n,bn,b) = (35,5) riêng: (: (n,an,a) = (35, 29) ) = (35, 29) love ssửử ddụụngng công

GiGiảả ssửử ccáácc kýký ttựự Alphabet

công ththứứcc (e = Alphabet nnằằmm trong

(e = xxbb mod n) mod n) trong khokhoảảngng ttừừ 11(cid:198)(cid:198)2626

Plain Text Plain Text

xxbb

ll oo vv ee

Numeric Numeric Representation Representation 1212 1515 2222 55

248832 248832 759375 759375 5153632 5153632 3125 3125

Cipher Text (e = xxbb Cipher Text (e = mod n) mod n) 1717 1515 2222 1010

VíVí dụdụ

GiGiảảii mãmã ttừừ love

love ssửử ddụụngng công

công ththứứcc (d =

(d = yyaa mod n) mod n)

n = 35, a=29 n = 35, a=29

yyaa

Cipher Cipher TextText

(d = yyaa (d = mod n) mod n)

Plain Plain TextText

481968572106750915091411825223072000 481968572106750915091411825223072000

1717

1212

12783403948858939111232757568359400 12783403948858939111232757568359400

1515

1515

2222

852643319086537701956194499721110000000 852643319086537701956194499721110000000

2222

1010

100000000000000000000000000000 100000000000000000000000000000

55

ll oo vv ee

Một số phương pháp tấn công RSA Một số phương pháp tấn công RSA

phương phpháápp RSA RSA ddựựaa trêntrên cơcơ tin đãđã thông tin không ththểể ththựựcc

công bbẻẻ khkhóóaa công ccộộngng đđểể tương ứứngng. . ĐiĐiềềuu quanquan trtrọọngng riêng tương

TTíínhnh chchấấtt an an totoàànn ccủủaa phương ssởở chi chi phphíí chocho viviệệcc gigiảảii mãmã bbấấtt hhợợpp llệệ thông đưđượợcc mãmã hhóóaa ssẽẽ ququáá llớớnn nênnên xemxem nhưnhư không hihiệệnn đưđượợcc VVìì khkhóóaa llàà công công ccộộngng nênnên viviệệcc ttấấnn công phương phpháápp RSA RSA thưthườờngng ddựựaa vvààoo khkhóóaa công phương xxáácc đđịịnhnh đưđượợcc khkhóóaa riêng llàà ddựựaa vvààoo nn đđểể ttíínhnh pp, , qq ccủủaa nn, , ttừừ đđóó ttíínhnh đưđượợcc dd..

Phương pháp sử dụng φ(n) Phương pháp sử dụng φ(n)

công bibiếếtt đưđượợcc gigiáá trtrịị φφ((nn). ). KhiKhi đđóó

2

p

0

−

GiGiảả ssửử ngưngườờii ttấấnn công viviệệcc xxáácc đđịịnhnh gigiáá trtrịị pp, , qq đưđượợcc đưađưa vvềề viviệệcc gigiảảii haihai phương trtrììnhnh sausau phương

phương trtrììnhnh bbậậcc haihai

nn = = pp ⋅⋅ qq ThayThay qq = = nn//pp, , tata đưđượợcc phương phương trtrììnhnh bbậậcc haihai ( ) ( )( )1 nφ p 1 q − = − ) ( ( ) n n np 1 φ − + =+ pp, , qq chchíínhnh llàà haihai nghi nghiệệmm ccủủaa phương nnààyy. . TuyTuy nhiên khkhóó hơnhơn viviệệcc xxáácc đđịịnhnh haihai ththừừaa ssốố nguyên

nhiên vvấấnn đđềề phpháátt hihiệệnn đưđượợcc gigiáá trtrịị φφ((nn) ) còncòn

nguyên ttốố ccủủaa nn. .

Thuật toán phân tích ra thừa số p-1 Thuật toán phân tích ra thừa số p-1

NhNhậậpp nn vvàà BB 1. 1. a a = 2= 2 2. 2. forfor j j = 2 = 2 toto B B dodo a a = = aajj mod mod nn 3. 3. d d = = gcd(gcd(aa −−1, 1, nn)) 4. 4. ifif 1 < 1 < d d < < nn thenthen

dd llàà ththừừaa ssốố nguyên công)) nguyên ttốố ccủủaa n n ((ththàànhnh công

elseelse

nguyên ttốố ccủủaa nn

không xxáácc đđịịnhnh đưđượợcc ththừừaa ssốố nguyên không ((ththấấtt bbạạii))

Thuật toán phân tích ra thừa số p-1 Thuật toán phân tích ra thừa số p-1

Pollard pp--1 (1974) 1 (1974) llàà mmộộtt trong

nguyên ttốố ccáácc ssốố nguyên

nguyên ttốố vvàà gigiáá trtrịị gigiớớii hhạạnn BB. .

nguyên chưa bibiếếtt) ) vvàà BB llàà mmộộtt ssốố nguyên

p

∧≤

−⇒−

trong nhnhữữngng ThuThuậậtt totoáánn Pollard thuthuậậtt totoáánn đơnđơn gigiảảnn hihiệệuu ququảả ddùùngng đđểể phânphân ttííchch rara ththừừaa ssốố nguyên nguyên llớớnn. . ThamTham ssốố đđầầuu vvààoo ccủủaa thuthuậậtt totoáánn llàà ssốố nguyên nguyên ((llẻẻ) ) nn ccầầnn đưđượợcc phânphân ttííchch rara ththừừaa ssốố nguyên GiGiảả ssửử n n = = p.qp.q ((pp, , qq chưa đđủủ llớớnn, , vvớớii mmỗỗii ththừừaa ssốố nguyên nguyên ttốố kk, ,

(

) B !1

( pkBk

) 1

Thuật toán phân tích ra thừa số p-1 Thuật toán phân tích ra thừa số p-1

ỞỞ cucuốốii vòng

vòng llặặpp ((bưbướớcc 2), 2), tata ccóó a a ≡≡ 22BB!! (mod : a a ≡≡ 22BB!! (mod

(mod nn) ) (mod pp) ) Fermat, tata ccóó : : 1 (mod pp) )

1 (mod pp) ) SuySuy rara: Do Do pp||nn nênnên theotheo đđịịnhnh lýlý Fermat, 22pp--11 ≡≡ 1 (mod Do (Do (pp--1)|1)|BB!, !, nênnên ởở bưbướớcc 3 3 ccủủaa thuthuậậtt totoáánn, , tata ccóó: : a a ≡≡ 1 (mod

VVìì ththếế, , ởở bưbướớcc 4: 4: pp|(|(aa −−1) 1) vvàà pp||nn nênnên nnếếuu d d = = gcd(gcd(aa −−1,1,nn) ) ththìì d d = = pp

Thuật toán phân tích ra thừa số p-1 Thuật toán phân tích ra thừa số p-1

VVíí ddụụ: :

180, chchúúngng tata xxáácc

= 11620221425 ởở bưbướớcc 3 3 ccủủaa thuthuậậtt

135978 chchỉỉ ccóó ccáácc

công do do gigiáá trtrịị 135978 nguyên ttốố nhnhỏỏ khikhi phânphân ttííchch rara ththừừaa ssốố

= 15770708441. GiGiảả ssửử nn = 15770708441. ÁÁpp ddụụngng thuthuậậtt totoáánn pp –– 1 1 vvớớii BB == 180, đđịịnhnh đưđượợcc aa = 11620221425 totoáánn vvàà xxáácc đđịịnhnh đưđượợcc gigiáá trtrịị dd = 135979. = 135979. Trong trưtrườờngng hhợợpp nnààyy, , viviệệcc phânphân ttííchch rara ththừừaa ssốố Trong nguyên ttốố ththàànhnh công nguyên ththừừaa ssốố nguyên nguyên ttốố:: nguyên

135978 = 2 ×× 3 3 ×× 131 135978 = 2

173 131 ×× 173 173 ssẽẽ đđảảmm bbảảoo điđiềềuu kikiệệnn

Do Do đđóó, , khikhi chchọọnn BB ≥≥ 173 135978⏐⏐ BB!! 135978

Thuật toán phân tích ra thừa số p-1 Thuật toán phân tích ra thừa số p-1

phương vvàà nhânnhân

Euclide ccóó đđộộ

USCLN ssửử ddụụngng thuthuậậtt totoáánn Euclide ((log nn))33). ).

OO((B B log Trong thuthuậậtt totoáánn p p −− 1 1 ccóó B B −− 1 1 phphéépp ttíínhnh llũũyy ththừừaa Trong modulo, mmỗỗii phphéépp đòiđòi hhỏỏii ttốốii đađa 2log2log22BB phphéépp nhânnhân modulo, modulo ssửử ddụụngng thuthuậậtt totoáánn bbììnhnh phương modulo ViViệệcc ttíínhnh USCLN phphứứcc ttạạpp OO((log NhưNhư vvậậyy, , đđộộ phphứứcc ttạạpp ccủủaa thuthuậậtt totoáánn llàà + (log nn))33)) log BB(log(log nn))2 2 + (log

Thuật toán phân tích ra thừa số p-1 Thuật toán phân tích ra thừa số p-1

n

B ≈ ) ) ththìì gigiảảii nhưng thuthuậậtt totoáánn nnààyy ssẽẽ không không

tương đđốốii nhnhỏỏ vvàà ththỏỏaa điđiềềuu

công, , nhưng

XXáácc susuấấtt chchọọnn gigiáá trtrịị BB tương kikiệệnn llàà rrấấtt ththấấpp. . KhiKhi tăngtăng gigiáá trtrịị BB ((chchẳẳngng hhạạnn nhưnhư thuthuậậtt ssẽẽ ththàànhnh công nhanh hơnhơn gigiảảii thuthuậậtt chiachia ddầầnn nhưnhư trtrììnhnh bbààyy trêntrên.. nhanh

Thuật toán phân tích ra thừa số p-1 Thuật toán phân tích ra thừa số p-1

công phương

phương phpháápp nguyên ttốố pp mmàà trong trưtrườờngng hhợợpp nn ccóó ththừừaa ssốố nguyên

nguyên ttốố rrấấtt nhnhỏỏ

công ccộộngng RSA an

tương ttựự ttììmm qq11 nguyên

GiGiảảii thuthuậậtt nnààyy chchỉỉ hihiệệuu ququảả khikhi ttấấnn công RSA RSA trong ((p p −− 1) 1) chchỉỉ ccóó ccáácc ưướớcc ssốố nguyên ChChúúngng tata ccóó ththểể ddễễ ddààngng xâyxây ddựựngng mmộộtt hhệệ ththốốngng mãmã RSA an totoàànn đđốốii vvớớii gigiảảii thuthuậậtt hhóóaa khkhóóaa công công p p −− 1. 1. CCááchch đơnđơn gigiảảnn nhnhấấtt llàà ttììmm mmộộtt ssốố ttấấnn công nguyên ttốố pp11 llớớnn, , mmàà p p = 2= 2pp11 + 1 + 1 ccũũngng llàà ssốố nguyên nguyên nguyên ttốố, , tương nguyên ttốố llớớnn vvàà qq == 22qq11 ++ 1 1 nguyên ttốố.. nguyên

Bẻ khóa dựa trên các tấn công lặp lại Bẻ khóa dựa trên các tấn công lặp lại

thương Norris: hhệệ ththốốngng RSA RSA ccóó ththểể bbịị ttổổnn thương công llặặpp liênliên titiếếpp. . NNếếuu đđốốii ththủủ bibiếếtt công ccộộngng {{nn, , bb} } vvàà ttừừ khkhóóaa CC ththìì ccóó ththểể

Simons vvàà Norris: Simons khikhi ssửử ddụụngng ttấấnn công ccặặpp khkhóóaa công ttíínhnh chuchuỗỗii ccáácc ttừừ khkhóóaa sausau: :

CC11==CCee ((modmod nn)) ee ((modmod nn)) CC22==CC11 …… CCii==CCii--11

ee ((modmod nn)) NNếếuu ccóó mmộộtt phphầầnn ttửử CCjj trong saosao chocho CCjj = = CC ththìì khi khi đđóó ssẽẽ ttììmm đưđượợcc M M = = CCjj--11 vvìì

ee ((modmod nn))

CCjj = = CCjj--11 C C = = MMee ((modmod nn))

trong chuchuỗỗii CC11, , CC22, , CC33,,……., ., CCii

Bẻ khóa dựa trên các tấn công lặp lại Bẻ khóa dựa trên các tấn công lặp lại

}={35, 17, 3},anhanh ta ta

VVíí ddụụ: : GiGiảả ssửử anhanh ta ta bibiếếtt {{nn, , bb, , CC}={35, 17, 3}, ssẽẽ ttíínhnh::

35) = 33 ) = 317 (modmod 35) = 33 ) = 3317 (mod 35) = 3 (mod nn) = 3317 (mod 35) = 3

CC11 = = CCee ((modmod nn) = 317 ( ee (mod CC22 = = CC11 VVìì CC22 = = CC nênnên M M = = CC11 = 33= 33

Sự che dấu thông tin trong hệ thống RSA Sự che dấu thông tin trong hệ thống RSA

tin không thông tin không phphảảii

= 35. NNếếuu anhanh tata mumuốốnn

865 ththìì hhệệ ththốốngng hohoàànn 109, qq == 97, 97, ee == 865

HHệệ ththốốngng RSA RSA ccóó đđặặcc điđiểểmm llàà thông luôn đưđượợcc cheche ddấấuu. . luôn = 17, n n = 35. GiGiảả ssửử ngưngườờii ggởởii ccóó e e = 17, ggởởii bbấấtt ccứứ ddữữ liliệệuu nnààoo thuthuộộcc ttậậpp sausau {1, 6, 7, 8, 13, 14, 15, 20, 21, 22, 27, 28, 29, 34} {1, 6, 7, 8, 13, 14, 15, 20, 21, 22, 27, 28, 29, 34} ththìì kkếếtt ququảả ccủủaa viviệệcc mãmã hhóóaa llạạii chchíínhnh llàà ddữữ liliệệuu ban ban đđầầuu. . NghNghĩĩaa llàà, , MM == MMee modmod nn. . CònCòn khi khi pp == 109, totoàànn không không ccóó ssựự cheche ddấấuu thông thông tin,

tin, bbởởii vvìì:: ∀∀MM, , MM == MM865865 modmod (109*97) (109*97)

Sự che dấu thông tin trong hệ thống RSA Sự che dấu thông tin trong hệ thống RSA

VVớớii mmỗỗii gigiáá trtrịị nn, , ccóó íítt nhnhấấtt 9 9 trưtrườờngng hhợợpp kkếếtt ququảả mãmã hhóóaa chchíínhnh llàà ddữữ liliệệuu ngunguồồnn ban ban đđầầuu. . ThThậậtt vvậậyy, , MM == MMee modmod nn

hayhay: :

MM == MMee modmod pp vvàà MM == MMee modmod q

q (*)(*) (*) ccóó íítt nhnhấấtt baba gigiảảii trong (*)

{0, 1, --1}. 1}. không đưđượợcc cheche ddấấuu ((không không bbịị thaythay đđổổii

VVớớii mmỗỗii ee, , mmỗỗii đđẳẳngng ththứứcc trong phpháápp thuthuộộcc ttậậpp {0, 1, SSốố thông thông điđiệệpp không sausau khi khi mãmã hhóóaa): ):

m m = [1+= [1+gcdgcd((ee--1, 1, pp--1)][1+ 1)][1+gcdgcd((ee--1), 1), qq--1]1]

Nhận xét Nhận xét

thông tin l tin làà ccóó đưđượợcc

, ta ccóó ththểể ddễễ ddààngng ttíínhnh ra ra ) = (pp –– 1)(1)(qq –– 1) 1) vvàà gigiáá trtrịị aa = = bb––11 modmod φφ((nn) )

Euclide mmởở rrộộngng. .

nguyên nn ccóó ththểể đưđượợcc phânphân ttííchch ra ra ththừừaa ssốố

phương phpháápp RSA RSA

MMấấuu chchốốtt đđểể ccóó ththểể gigiảảii mãmã đưđượợcc thông gigiáá trtrịị pp vvàà qq ttạạoo nênnên gigiáá trtrịị nn. . Khi Khi ccóó đưđượợcc haihai gigiáá trtrịị nnààyy, ta đưđượợcc φφ((nn) = ( theotheo thuthuậậtt totoáánn Euclide NNếếuu ssốố nguyên nguyên ttốố, , ttứứcc llàà gigiáá trtrịị pp vvàà qq ccóó ththểể đưđượợcc xxáácc đđịịnhnh nguyên ththìì xemxem nhưnhư ttíínhnh an an totoàànn ccủủaa phương không còncòn đưđượợcc bbảảoo đđảảmm nnữữaa. . không

Nhận xét Nhận xét

phương phpháápp RSA RSA ddựựaa trêntrên chưa đđủủ khkhảả nguyên rrấấtt llớớnn

nguyên ttốố. .

1994, Peter ShorShor, , mmộộtt nhnhàà khoa

nghiệệmm AT&T,

phòng khoa hhọọcc ttạạii phòng AT&T, đãđã đưađưa ra ra mmộộtt thuthuậậtt totoáánn ccóó ththểể nguyên rrấấtt llớớnn

NhưNhư vvậậyy, , ttíínhnh an an totoàànn ccủủaa phương cơcơ ssởở ccáácc mmááyy ttíínhnh ttạạii ththờờii điđiểểmm hihiệệnn ttạạii chưa năngnăng gigiảảii quyquyếếtt viviệệcc phânphân ttííchch ccáácc ssốố nguyên ra ra ththừừaa ssốố nguyên NămNăm 1994, Peter ththíí nghi phânphân ttííchch mmộộtt ccááchch hihiệệuu ququảả ccáácc ssốố nguyên trêntrên mmááyy ttíínhnh lưlượợngng ttửử. .

Vấn đề số nguyên tố Vấn đề số nguyên tố

RSA, ssốố không ththểể ddễễ ddààngng titiếếnn

nguyên ttốố. .

nguyên ttốố đãđã 130 chchữữ nguyên ccóó trêntrên 130

nguyên ttốố pp vvàà qq ccầầnn phphảảii đđủủ llớớnn, , vvíí ddụụ

ĐĐểể bbảảoo đđảảmm an an totoàànn chocho hhệệ ththốốngng mãmã hhóóaa RSA, nguyên n n = = pqpq phphảảii đđủủ llớớnn đđểể không nguyên hhàànhnh viviệệcc phânphân ttííchch nn rara ththừừaa ssốố nguyên HiHiệệnn ttạạii, , ccáácc thuthuậậtt totoáánn phânphân ttííchch ththừừaa ssốố nguyên ccóó ththểể gigiảảii quyquyếếtt đưđượợcc ccáácc ssốố nguyên ssốố ((ththậậpp phânphân). ). ĐĐểể an an totoàànn, , ssốố nguyên nhưnhư trêntrên 100 100 chchữữ ssốố. . VVấấnn đđềề đđặặtt rara ởở đâyđây llàà gigiảảii quyquyếếtt bbààii totoáánn: : llààmm ththếế nnààoo nhanh chchóóngng vvàà chchíínhnh xxáácc mmộộtt đđểể kikiểểmm tratra mmộộtt ccááchch nhanh ssốố nguyên nguyên ttốố hay hay hhợợpp ssốố? ? dương nn llàà ssốố nguyên nguyên dương

Vấn đề số nguyên tố Vấn đề số nguyên tố

dương nn llàà ssốố nguyên dương

dương). ).

n

⎡ ⎣

⎤ ⎦

⎤ ⎦

⎡ ⎣

nguyên ttốố khikhi vvàà chchỉỉ khikhi nn không không 2,..., dương nnààoo thuthuộộcc đođoạạnn

Theo đđịịnhnh nghnghĩĩaa, , mmộộtt ssốố nguyên Theo nguyên ttốố khikhi vvàà chchỉỉ khikhi nn chchỉỉ chiachia hhếếtt chocho 1 1 vvàà nn ((ởở nguyên đâyđây chchỉỉ xxéétt ccáácc ssốố nguyên nguyên dương TTừừ đđóó suysuy rara, , nn llàà ssốố nguyên ccóó ưướớcc ssốố dương . . NhưNhư vvậậyy, , tata ccóó: :

i

2,...,

n

,

i

⇔ ∀ ∈

nn llàà ssốố nguyên nguyên ttốố

( 0 mod

)

( n ¬ ≡

)

⎡ ⎣

⎤ ⎦

⎡ ⎣

⎤ ⎦

Vấn đề số nguyên tố Vấn đề số nguyên tố

nguyên ttốố

dương nn llàà ssốố nguyên nguyên dương phương phpháápp trêntrên ssẽẽ đưađưa rara kkếếtt ququảả hohoàànn totoàànn

nhiên, , ththờờii giangian xxửử lýlý ccủủaa thuthuậậtt totoáánn rõrõ rrààngng llàà rrấấtt

trong không ththểể ththựựcc hihiệệnn đưđượợcc, , trong

ViViệệcc kikiểểmm tratra mmộộtt ssốố nguyên theotheo phương chchíínhnh xxáácc. . TuyTuy nhiên llớớnn, , hohoặặcc ththậậmm chchíí không trưtrườờngng hhợợpp nn tương tương đđốốii llớớnn. .

Thuật toán Miller-Rabin Thuật toán Miller-Rabin

dương nn llàà nguyên dương phương phpháápp thuthuộộcc

TrênTrên ththựựcc ttếế, , viviệệcc kikiểểmm tratra mmộộtt ssốố nguyên ssốố nguyên nguyên ttốố thưthườờngng áápp ddụụngng ccáácc phương Monte Carlo, nhnhóómm thuthuậậtt totoáánn Monte Carlo, vvíí ddụụ: :

Solovay--Strassen Strassen hay hay thuthuậậtt totoáánn MillerMiller--

Robin thưthườờngng đưđượợcc ssửử ddụụngng phphổổ

thuthuậậtt totoáánn Solovay Robin; Robin; thuthuậậtt totoáánn MillerMiller--Robin bibiếếnn hơnhơn. .

Thuật toán thuộc nhóm Monte Carlo Thuật toán thuộc nhóm Monte Carlo

Monte Carlo đưđượợcc ssửử ddụụngng ThuThuậậtt totoáánn thuthuộộcc nhnhóómm Monte Carlo trong viviệệcc khkhẳẳngng đđịịnhnh hay hay phphủủ đđịịnhnh mmộộtt vvấấnn đđềề nnààoo trong đđóó. . ThuThuậậtt totoáánn luôn luôn đưađưa rara câucâu trtrảả llờờii vvàà câucâu trtrảả llờờii (yes) hohoặặcc llàà thuthu đưđượợcc chchỉỉ ccóó khkhảả năngnăng hohoặặcc llàà ““CCóó”” (yes) (no) Không”” (no) ““Không

trong đđóó, , câucâu trtrảả llờờii ““CCóó”” (Yes)

biased Monte Carlo”” llàà thuthuậậtt totoáánn (Yes) luôn luôn (No) ccóó ththểể nhưng câucâu trtrảả llờờii ““Không Không”” (No)

ThuThuậậtt totoáánn ““yesyes--biased Monte Carlo Monte Carlo, trong Monte Carlo, chchíínhnh xxáácc nhưng không chchíínhnh xxáácc không

Thuật toán Miller-Rabin Thuật toán Miller-Rabin

nguyên dương nhanh ((ssốố nguyên

dương nn ccóó ththểể trong ththờờii giangian ttỉỉ llệệ vvớớii loglog22nn, , ttứứcc llàà ssốố trong bibiểểuu didiễễnn nhnhịị phânphân ccủủaa nn) )

không chchíínhnh xxáácc llàà không không caocao. .

ƯuƯu điđiểểmm: : XXửử lýlý nhanh đưđượợcc kikiểểmm tratra trong lưlượợngng ccáácc bit bit trong không hohoàànn totoàànn CCóó khkhảả năngnăng kkếếtt luluậậnn ccủủaa thuthuậậtt totoáánn không chchíínhnh xxáácc, , nghnghĩĩaa llàà ccóó khkhảả năngnăng mmộộtt hhợợpp ssốố nn llạạii đưđượợcc nguyên ttốố, , mmặặcc ddùù xxáácc susuấấtt xxảảyy rara kkếếtt kkếếtt luluậậnn llàà ssốố nguyên luluậậnn không CCóó ththểể khkhắắcc phphụụcc bbằằngng ccááchch ththựựcc hihiệệnn thuthuậậtt totoáánn nhinhiềềuu llầầnn đđểể gigiảảmm khkhảả năngnăng xxảảyy rara kkếếtt luluậậnn saisai xuxuốốngng dưdướớii ngưngưỡỡngng chocho phphéépp (cid:206)(cid:206) kkếếtt luluậậnn ccóó đđộộ tin tin ccậậyy caocao

Thuật toán Miller-Rabin Thuật toán Miller-Rabin

nguyên dương nhiên ssốố nguyên

{1, 2, ..., n n –– 1}1}

dương nn = 2= 2kkmm + 1 + 1 vvớớii m m llẻẻ dương aa ∈∈ {1, 2, ..., nguyên dương

) then 1 (mod pp) then

PhânPhân ttííchch ssốố nguyên ChChọọnn ngngẫẫuu nhiên TTíínhnh bb = = aamm mod mod pp if if bb ≡≡ 1 (mod

KKếếtt luluậậnn ““pp llàà ssốố nguyên

nguyên ttốố”” vvàà ddừừngng thuthuậậtt totoáánn

end if end if for ii = 0 to for

= 0 to kk −− 1 1 if if bb ≡≡ pp −− 1 (mod

) then 1 (mod pp) then nguyên ttốố”” vvàà ddừừngng thuthuậậtt totoáánn

KKếếtt luluậậnn ““pp llàà ssốố nguyên

elseelse

bb = = bb22 mod mod pp

end if end if

end for end for KKếếtt luluậậnn ““pp llàà hhợợpp ssốố””

Thuật toán Miller-Rabin Thuật toán Miller-Rabin

Rabin llàà thuthuậậtt totoáánn MillerMiller--Rabin

biased totoáánn ““yesyes--biased dương nn nguyên dương

ThuThuậậtt Monte Carlo”” đđốốii vvớớii phpháátt bibiếếuu ““ssốố nguyên Monte Carlo llàà hhợợpp ssốố””. . XXáácc susuấấtt xxảảyy rara kkếếtt luluậậnn saisai, , nghnghĩĩaa llàà thuthuậậtt totoáánn đưađưa rara nguyên ttốố”” khikhi nn ththậậtt ssựự llàà hhợợpp ssốố, , kkếếtt luluậậnn ““nn llàà ssốố nguyên 25%. chchỉỉ ttốốii đađa llàà 25%. NNếếuu áápp ddụụngng thuthuậậtt totoáánn kk llầầnn vvớớii ccáácc gigiáá trtrịị aa khkháácc nhaunhau mmàà tata vvẫẫnn thuthu đưđượợcc kkếếtt luluậậnn ““nn llàà ssốố nguyên nguyên ttốố”” ththìì xxáácc susuấấtt chchíínhnh xxáácc ccủủaa kkếếtt luluậậnn nnààyy llàà 11--44--kk (cid:198)(cid:198) 11, , vvớớii kk đđủủ llớớnn. .

Xử lý số học Xử lý số học

i

downto 0 0

TTíínhnh gigiáá trtrịị ccủủaa bibiểểuu ththứứcc zz = = xxbb mod mod nn ThuThuậậtt totoáánn ““bbììnhnh phương phương vvàà nhânnhân”” BiBiểểuu didiễễnn bb ddạạngng nhnhịị phânphân bbll--11bbll--22......bb11bb00, , bbii∈∈{0, 1}, 0 zz = 1= 1 xx = = xx mod mod nn forfor ii = = ll--1 1 downto z z = = zz22 mod mod nn ifif bbi i = 1 = 1 thenthen z z = = zz××xx mod mod nn end if end if end for end for

Mã hóa đối xứng VS mã hóa bất đối xứng Mã hóa đối xứng VS mã hóa bất đối xứng

phương phpháápp mãmã hhóóaa quyquy ưướớcc ccóó ưuưu điđiểểmm xxửử lýlý phương phpháápp mãmã hhóóaa khkhóóaa công nhanh so so vvớớii ccáácc phương công

CCáácc phương rrấấtt nhanh ccộộngng. . Do Do khkhóóaa ddùùngng đđểể mãmã hhóóaa ccũũngng đưđượợcc ddùùngng đđểể gigiảảii mãmã dung ccủủaa khkhóóaa vvàà mãmã nênnên ccầầnn phphảảii gigiữữ bbíí mmậậtt nnộộii dung (secret key). NgayNgay ccảả khkhóóaa đưđượợcc ggọọii llàà khkhóóaa bbíí mmậậtt (secret key). trong trưtrườờngng hhợợpp khkhóóaa đưđượợcc traotrao đđổổii trtrựựcc titiếếpp ththìì mãmã trong khkhóóaa nnààyy vvẫẫnn ccóó khkhảả năngnăng bbịị phpháátt hihiệệnn. . VVấấnn đđềề khkhóó khănkhăn đđặặtt rara đđốốii vvớớii ccáácc phương phương phpháápp mãmã hhóóaa nnààyy chchíínhnh llàà bbààii totoáánn traotrao đđổổii mãmã khkhóóaa. .

Mã hóa đối xứng VS mã hóa bất đối xứng Mã hóa đối xứng VS mã hóa bất đối xứng

í h p i h C

K 1

K 2

K 4

4 6

8 2 1

6 5 2

2 1 5

Ñoä daøi maõ khoùa (bits)

Đồ thị so sánh chi phí công phá khóa bí mật và khóa công cộng

Mã hóa đối xứng VS mã hóa bất đối xứng Mã hóa đối xứng VS mã hóa bất đối xứng

công hơnhơn khkhóóaa bbíí mmậậtt. . công ccộộngng ddễễ bbịị ttấấnn công

thông tin

thông điđiệệpp sausau khikhi gigiảảii thông điđiệệpp ban ban đđầầuu trưtrướớcc khikhi mãmã hhóóaa

không llạạii llàà mmộộtt vvấấnn đđềề khkhóó khănkhăn. . công ccộộngng, , viviệệcc công

KhKhóóaa công ĐĐểể ttììmm rara đưđượợcc khkhóóaa bbíí mmậậtt, , ngưngườờii gigiảảii mãmã ccầầnn phphảảii tin liênliên quanquan đđếếnn ccáácc đđặặcc ttíínhnh ccóó thêmthêm mmộộtt ssốố thông ccủủaa vănvăn bbảảnn ngunguồồnn trưtrướớcc khikhi mãmã hhóóaa đđểể ttììmm rara manhmanh mmốốii gigiảảii mãmã thaythay vvìì phphảảii ssửử ddụụngng phương phương phpháápp vvéétt ccạạnn mãmã khkhóóaa. . NgoNgoààii rara, , viviệệcc xxáácc đđịịnhnh xemxem thông mãmã ccóó đđúúngng llàà thông hay hay không công phpháá hohoàànn totoàànn ĐĐốốii vvớớii ccáácc khkhóóaa công ccóó ththểể ththựựcc hihiệệnn đưđượợcc vvớớii điđiềềuu kikiệệnn ccóó đđủủ ttààii nguyên nguyên vvàà ththờờii giangian xxửử lýlý. .