Chương 1. KIEN THUC CO SO oioi.ccccccccccccccccccscesescsvssessscsesseesscevsvesesesveecansveeeees 3 1:1; T1 18D Ta gttiqotGGWONIGGNGuG003gÁG90008/00888568488g00gg3x& + L1, TRE PHAN. BH Ei cedex nrc eens men oat san wena + belies DE TINO DfĐHDTHTTouoevvagdiodadgtuieotbi bay S56096400403633800/2003)380/40042004 4 mon —. “VRHH:Í KHE Ìn»eonscoiisorbsbbdiigiiiisg00501-62600046650006080i300655068600811000566432g08884Q500300.
Định nghĩa của vành: .- 5 2< 1111333321 33 vn ve 3 Lids TCA (HH EBÌ) sesoasoaesioskiesssehstaitiiaruiSti6icutiidkoidbioiI648/E041d0428958.6g8 6 l3, ViệỄh Hi/0Hš (QUGRISIE ETDD gang ng do bat 2iadá tt) li y8isoaieusaia 6 1. Đồng dư số hỌC. 7 LBA, DWC OGHE ẨỨ cssansasetunaplSu/010020078/G0200/BG4800036340S80080)0830582ASISAGGg8. Phần tử nghịch đảo của phép nhân đồng dư.
“That tear Ny Tita nan ssc sssssisecceracnanssassccsmcomarmacenacmeancnweneaeses 9 Chuong 2. TONG QUAN VE RSA. Hệ mã RSA gỐC. 12 Does “THA Tin ROA ween rece dGG0AS00 SG lạng agiasgaewae 12 2.
Phân tích số nguyên lớn.-¿- - ke SE S£EE+E£EeE£E+EeEeEErEeEerkrkerrrkd 12 2. Khoa bi mt 06 $6 mii nho .5 3, Kifn:eb0ng Khai gỗ số tri HHỔ con ssseweeoessoovanS0403393800003563896648:8. Tân công thực thi .- -- 2 ¿s5 E£St£EE+ES£E£EeEkeEketkerkrrsrrrrrerrver 14 503, 'TỔn:nững bằNG LIỀN xeuuuesesrenevrtrtdikeotibtrrikutatVAta4i8u002006G6058150010g601601060/ i) 733. MOCO Wie ERE CS RSA ccsncessccrescsucczssnsroseoncotnseonrsnensncenseoeeeaneraremaionasoaconness 16 23.
KSA Wen van thong Gat Ca he wiscsicssnsccsmeccessnonnnenconcnanervnanennexcenssiens 16 2. RSA trên vành thương các số nguyên Gauss. RSA trên nhóm nhân các ma trận khả nghịch .- 5< «<<: 18 235A: RSA Wen nhỏm đườn§ c0núg 6l visoissasasseasesasaibiasiisdserasssoee 19 2. RSA trên vành Bergmann.-- -- << Ă s12 311 ng ng 20 31:6; Thận ôi:võ cấp biên KHếunneannueeeonnneinndibnsiainuliditigtidii0A30200450117886a 036 21 Chương 3.
XÂY DỰNG HỆ MÃ RSA TRÊN VÀNH End(7„ x Z„m). Đặc điểm của vành End(Z; X Zpm ). Phần tử khả nghịch trong End(Z„ X Zipm). Xây dựng hệ mã RSA trên vành End(2ạ X am) .1, EOS VHH ND cu 3Š s5 đổ Ï uconneebiandtdidtiiiktiiititl4i0i440060000L6156068ố0/866 28 3.
Xây dựng hệ mã RSA trên vành End(Za X 7 ⁄qm). 33 lu, (Giá AEVÑ/GũNHH: H18 NỆ THỗ:u.áoscoassioraioilvt8020155042k0811085966880066g855800/66s56/488668649uã88 3a BSA]; CALE HS Ma os siiscics ce crc 35 Ai Tiếu SPREE I Ti xexengnngunnntrorgaYiPGA3/00000010000000000001800000901018007900001001240/60000000088000) 4I Chuữ0nø 4, BOT DUAN cncuunmannanumnmemmamnmananaumecamennuss 44 4. Két qua dat duc. ,EUETHĐNHHEĐIETGIuauessvrosothubotitikttligSGG0i004303030100006300000000/0048680601464.0210300050601036108/ 44 TAI LIEU THAM KHẢO.
- 2 2S E£SE£E2SE£EE£EEEEEEEEEEEEEEEEEEEErEErrkrserrrred 46 Danh mục các kí hiệu, các từ viet tat , fr .ˆ , ` oA “ Kí hiệu Ý nghĩa CRT Định lý phần dư Trung hoa (Chinese Remainder Theorem) gcd Ước chung lớn nhất (Greatest Common Divisor) lcm Bội chung nhỏ nhất (Least Common Multiple) Danh muc cac hinh anh Hinh 3. Giao diện tổng quan của hệ mã.-- - 2 + 2s 2S Sz+E££zzE££z+Eczxzzzzxd 36 Hinh 3. CGH@rnrnhmrginh: KHI uxeesasasesoeindbitnoidiudnikiidg0akssioiS468088664144404480051040A14Eh 36 Hinh 3. Thông báu khí nhập giá trị Thì không hợp le seveseseccccsccncescessenscssascesessecass 37 Hinh 3.
Thông báo nhập nội dung mã hóa. KHE HH THẾ H~_ uuenaeneuerrsebtiongiEitetoiiaxitiUtt0gt309%01911/0N0000N0102900109000001 0500001. Chức tilng MS hóa HHÌG VĂN DẪĂ-cecccccsiiiniodavoisiirkdilseoAaG61002500166 4606066605380 39 Hinh 3. Thống báo nHấp ñøi duñg Sia MF cissccsccvcwispnarnsspniswsepeneciemsianveesvaees 40 Hinh 3.
ChWG:TTINE MEN. LH VẬN ĐIỆN uenanneserserosegstxoA000g003850 033040005N8300.60700E38000/69980 4I Danh muc cac bang biéu Bảng 2. Độ dài mô-đun và số các phép tính của các biến thể RSA eee ee eee eee eee) MO DAU Hệ mã RSA là một trong số những hệ mã công khai được sử dụng phổ biến nhất hiện nay. Hệ mã được giới thiệu vào 1978 bởi ba tác giả là Ron Rivest, Adi Shamir va Len Adleman.
Khi nghiên cứu về hệ ma RSA, trén thé giới có hai xu hướng, đó là: phát triên các biến thê của RSA và thám mã RSA. Sự phát triển các biến thể của RSA có thê chia làm hai hướng. Hướng thứ nhất tập trung vào hệ mã RSA góc nhưng cải tiễn các thuật toán mã hóa và giải mã nhằm giảm độ phức tạp tính toán hoặc xây dựng RSA trên vành Z„ với n có dạng phức tạp hơn thay vì là tích của hai số nguyên tô phân biệt. Trong hướng thứ hai, các biến thể của RSA được xây dựng trên các cấu trúc đại số phức tạp hơn.
Một số biên thể của RSA được xây dựng theo hướng thứ hai như sau: e RSA trên vành thương các đa thức [I] e© RSA trên vành thương các số nguyên Gauss [1] e RSA trên nhóm nhân các ma trận [2| e RSA trén nhom duong cong elliptic [3] e RSA trén vanh Bergman [4] Có thể thấy, một số bién thé cua RSA được xây dựng trên các câu trúc khác nhau, đó thường là nhóm hoặc vành thương của vành Euclide. Các phép toán trên các cầu trúc này phải rõ ràng đề có thê lập trình trên máy tính. Một cách đơn giản nhất đề tạo ra một cấu trúc là xét vành các tự đồng cấu End(6) với G là nhóm đã biết. Một ví dụ điển hình của vành các tự đồng cấu Enđ(6@) là vành Bergman End(Z„ x 7„›) với p là số nguyên tố.
Vành Bergman được giới thiệu trong [5] vào năm 1974 nhưng do các phép toán trên vành này là khó năm bắt nên hầu như không có hệ mã nào được xây dựng trên đó. Mãi đến năm 2011, Climent và các cộng sự mới thiết lập được đăng cầu giữa vành End(Z„ x Z„2) với vành ma trận b cấp 2 # 5: Ep = (oc ):a,b,c,d€7,0 < a,b,c <p,0 < d <p°] trong d [6]. Va dén nam 2013, các tác gia trong [4] đã định nghĩa E£, = RSA trên vành này (với p, q là hai số nguyên tổ phân biệt và n = pq). Một mo rong cua vanh Bergman la vanh End (Z, x Zym) đã được giới thiệu trong [7].
Các phần tử của vành này có thê được biểu diễn dưới dạng các ma trận a b 2X2 như sau: Ep pm = l m~1e d |a,b,c € Zụ„ d € Zpmt. Mat khac, cac phép toán trên vành này là hoàn toàn năm bắt được. Vì thế, mục đích của đề tài là đi xây dựng vành End(Z„ x Zm) (với p, q la hai s6 nguyén té phan biét va n = pq) va xay dung hé ma RSA trén vanh End(Z,, X Z,m) nay. “* Muc dich nghién ctru Mục đích nghiên cứu của luận văn là đi tìm hiểu và xây dựng hệ mã RSA trên vanh End(Z,, X Z,m).
s* Nhiệm vụ nghiên cứu e_ Tìm hiểu về hệ mã RSA gốc và các cách tân công ¢ Cac bién thé cua RSA e Tìm hiểu vành End(Z„ x Zym) e Xay dung vanh End(Z, X Z,m) va hé ma RSA trén vanh dé s% Giới hạn đề tài e_ Xây dựng minh họa một hệ mã RSA trên cầu trúc đã xây dựng e©_ So sánh ưu, khuyết điểm của hệ mã đã xây dựng với hệ mã RSA gốc s* Đóng góp của luận văn Luận văn đóng góp thêm một biến thê cho hệ mã RSA. KIÊN THỨC CƠ SỞ Nội dung chương này gồm: I. Nhắc lại một số kiến thức về nhóm — Phép toán hai ngôi — Nửa nhóm — Nhóm 2. Một số kiến thức về vành —_ Định nghĩa vành — lđêan —_ Vành thương 3.
Một số kiến thức về đồng dư số học — Phép đồng dư — Phần tử nghịch đảo 4. Thuật toán lũy thừa nhanh Trong chương này chúng tôi sẽ trình bày lại một số kiến thức cơ sở về nhóm, vành, phép đồng dư và thuật toán lũy thừa nhanh làm tiền đề đề trình bày những nội dung cho các chương còn lại. Phép toán hai ngôi Cho 4 là một tập hợp khác rỗng. Phép toán hai ngôi xác định trên tập hợp 4 là một ánh xạ từ 4Z vào A.
Ta kí hiệu ánh xạ là °, khi đó, ảnh của (x, y) € A2 có thể được kí hiệu là x°y. Tập hợp A với phép toán hai ngôi như vậy sẽ được gọi là tập có trang bị phép toán hai ngôi và kí hiệu là (4, °). Phép toán ° có thề thỏa mãn một vài tính chất nào đó, ví dụ như: e Tinh chat giao hoan: V x,y € A,x°y = y°x e Tinh chat két hop: V. x,y,z € A,x°(y°z) = (x°y)°z e Co phan tir don vi: de € A,V x € A,e°x = x°e =x Những ví dụ dễ thấy nhất về phép toán hai ngôi chính là phép cộng và phép nhân trên các tập Ñ, Z, Q,IR, CC.
Phép trừ cũng là phép toán hai ngôi trên các tập Z, Q, R, C nhung lại không là phép toán hai ngôi trên tập Ñ. Nứa nhóm (monoid) Cho (M,*) là một tập hợp được trang bị phép toán hai ngôi *. Nếu phép toán * thỏa mãn tính chất kết hợp: x * (y *Z) = (x *y) *zZ,Vx,y,z € M thì khi đó (M,*) được gọi là nửa nhóm. Ví dụ: Với phép cộng, tập hợp Ñ chính là một nửa nhóm.
Đồng câu nửa nhóm là một ánh xạ ƒ: M — N giữa hai nửa nhóm (M,*) và (N,-) sao cho ánh xạ đó bảo toàn phép toan: Vx, y € M, f(x * y) = f(x): f(y). Nhóm Tập hợp (Œ,*) được trang bị phép toán hai ngôi * được gọi là nhóm khi thỏa mãn các tính chất sau: e Tinh két hop: x * (y*z) = (x*y)*z,Yx,y,z €Œ # Có phần tử đơn vị e EG:e*x=x*e=x,VxEG se Khả nghịch: Vx € ŒG,3x/ € G thỏa mãn: x *xÝ = xÍ *x=e Trường hợp, phép toán + trên nhóm G co tinh giao hoán thì ta nói ứ là nhóm giao hoán. Chăng hạn, tập hợp các số nguyên Z với phép cộng chính là một nhóm giao hoán. Trong nhóm (6,*), nếu có một tập con H là một nhóm với phép toán * của Œ thì H được gọi là nhóm con của Œ.
Trong nhóm Œ, số lượng phần tử có trong nhóm được gọi là cấp của nhóm và được kí hiệu là |Œ|. Còn cấp của phần tử a trong nhóm Œ được định nghĩa là một số tự nhiên k nhỏ nhất thỏa mãn a k = e. Nếu không tôn tại số k như vậy ta noi a cé cap v6 han.1 (Định lý Lagrange trong lý thuyết nhóm) Nếu H là nhóm con của nhóm hữu hạn Œ thì số phần tử của Œ chia hết cho số phần tử của H. Từ định lý Lagrange trong lý thuyết nhóm có thể suy ra một số hệ quả Sau: Hệ quả 1.1 Cấp của mỗi phần tử trong một nhóm hữu hạn là ước của cấp của nhóm đó.2 Cho G là một nhóm hữu hạn cấp n và a là một phần tử của G.
Định nghĩa của vành Tập hợp (R, +,. ) có trang bị đồng thời hai phép toán hai ngôi là + (cộng) và. (nhân) được gọi là vành khi thỏa mãn các điều kiện sau đây: e_ Cấu trúc (R,+) là một nhóm giao hoán e_ Phép toán nhân của R có tính chất kết hợp e_ Phép nhân có tính chất phân phối hai bên đối với phép cộng, nghĩa là: Vx.y,z ER, x(yt+z) =xy + xz Vx,y,z € R,(y + Z)x = yx + Zx Một ví dụ điền hình nhất của vành chính là tập hợp các số nguyên Z với phép cộng và phép nhân. nêu có một tập hợp 4 là một vành với hai phép toán + và.
trên R thì A được gọi là vành con của vành R. Idéan (Ideal) Cho R là một vành. Mot idéan J 1a mét vanh con khác rỗng của R thỏa mãn: e Nếua,b€lIthìa+b€l se Nếua€lvàr € Rthì ar€lvàra €i Có thê thấy răng iđêan là một tập con của R đóng với phép cộng và phép nhân.