Luận văn thạc sĩ: Tối ưu hóa xử lý số học trong hệ mã hóa RSA

Chia sẻ: Sdfas Vfdtg | Ngày: | Loại File: PDF | Số trang:26

Thêm vào BST

Báo xấu

202
lượt xem 53
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tối ưu hóa xử lý số học trong hệ mã hóa RSA nhằm nghiên cứu lý thuyết và hệ mật mã hóa công khai RSA, xây dựng thuật toán tối ưu hóa.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn thạc sĩ: Tối ưu hóa xử lý số học trong hệ mã hóa RSA

B GIÁO D C VÀ ĐÀO T O Đ I H C ĐÀ N NG LƯƠNG KHÁNH TÝ T I ƯU HÓA GI I THU T X LÝ S H C TRONG H MÃ HÓA RSA Chuyên ngành : KHOA H C MÁY TÍNH Mã s : 60.48.01 TÓM T T LU N VĂN TH C SĨ K THU T Đà N ng - Năm 2012
Công trình ñư c hoàn thành t i Đ I H C ĐÀ N NG Ngư i hư ng d n khoa h c: PGS.TSKH. TR N QU C CHI N Ph n bi n 1: PGS.TS. PHAN HUY KHÁNH Ph n bi n 2: TS. TRƯƠNG CÔNG TU N Lu n văn ñư c b o v t i H i ñ ng ch m Lu n văn t t nghi p th c sĩ k thu t h p t i Đ i h c Đà N ng vào ngày 03 tháng 03 năm 2012 Có th tìm hi u lu n văn t i: • Trung tâm Thông tin - H c li u, Đ i h c Đà N ng • Trung tâm H c li u, Đ i h c Đà N ng
M Đ U 1. Lý do ch n ñ tài Trong h u h t l ch s m t mã h c, khóa dùng trong các quá trình mã hóa và gi i mã ph i ñư c gi bí m t và c n ñư c trao ñ i b ng m t phương pháp an toàn khác (không dùng m t mã) như g p nhau tr c ti p hay thông qua m t ngư i ñưa thư tin c y. Vì v y quá trình phân ph i khóa trong th c t g p r t nhi u khó khăn, ñ c bi t là khi s lư ng ngư i s d ng r t l n. M t mã hóa khóa công khai ñã gi i quy t ñư c v n ñ này vì nó cho phép ngư i dùng g i thông tin m t trên ñư ng truy n không an toàn mà không c n th a thu n khóa t trư c. Trong m t mã h c, RSA là m t thu t toán m t mã hóa khóa công khai. Đây là thu t toán ñ u tiên phù h p v i vi c t o ra ch ký ñi n t ñ ng th i v i vi c mã hóa.Nó ñánh d u m t s ti n b vư t b c c a lĩnh v c m t mã h c trong vi c s d ng khóa công c ng. RSA ñang ñư c s d ng ph bi n trong thương m i ñi n t và ñư c cho là ñ m b o an toàn v i ñi u ki n ñ dài khóa ñ l n. H mã RSA th c hi n tính toán v i s nguyên l n, có th lên t i hàng trăm ch s .Đ ph c t p c a vi c gi i mã c a h mã này t l thu n v i ñ l n c a các s nguyên tham gia vào vi c t o khóa mã hóa và khóa công khai. Vì v y, ñ h mã ñư c an toàn c n tăng kích thư c c a s nguyên. V n ñ tăng kích thư c c a s nguyên s d n ñ n th i gian x lý chương trình mã hóa cũng tăng lên. M t khác thông tin mã hóa ngày càng ña d ng và có kh i lư ng l n ñòi h i h mã gi m thi u th i gian x lý.
Bên c nh ñó, do ngày càng có nhi u công c , ph n m m h tr nh m tìm cách b khóa ñ l y c p các thông tin vì th h mã c n ñư c nâng c p tính b o m t. Đó là nh ng lý do mà tôi ch n nghiên c u và th c hi n ñ tài “T i ưu hóa gi i thu t x lý s h c trong h mã hóa RSA”dư i s hư ng d n c a th y giáo PGS.TSKH. Tr n Qu c Chi n. 2. M c ñích nghiên c u M c tiêu c a ñ tài là nghiên c u lý thuy t v h m t mã hóa công khai RSA, xây d ng thu t toán t i ưu hóa nh m tăng hi u qu các phép tính toán v i s nguyên l n, t ñó tăng t c ñ x lý, tính b o m t c a h mã và th c hi n mã hóa – gi i mã các t p tin văn b n. 3. Đ i tư ng và ph m vinghiên c u * Đ i tư ng nghiên c u Nghiên c u lý thuy t cơ b n v h mã hóa công khai, ñ c bi t h mã hóa RSA là ñ i tư ng nghiên c u chính c a ñ tài nh m phát hi n các phép toán x lý s h c c n t i ưu.T ñó, bư c ñ u ñư c th nghi m h mã hóa RSA cho k t qu t i ưu hóa. * Ph m vi nghiên c u Trong ph m vi nghiên c u c a ñ tài này, tác gi th c hi n t i ưu hóa v i m t s phép toán s nguyên l n và xây d ng ng d ng mã hóa - gi i mã t p tin văn b n. Đ tài còn trong ph m vi ñưa ra gi i pháp, vì v y ñ ng d ng vào th c ti n c n có nhi u th i gian hơn n a. 4. Phương pháp nghiên c u - Thu th p và phân tích các tài li u sơ c p, tài li u trên Internet liên quan ñ n ñ tài. - Th o lu n, l a ch n hư ng gi i quy t v n ñ .
- Tìm hi u các thu t toán x lý s nguyên l n c a h mã hóa công khai RSA. - T i ưu hóa các phép toán x lý s h c c a h mã RSA làm tăng kh năng x lý t ng bư c. - Th c nghi m cài ñ t ng d ng ñ ñánh giá và so sánh k t qu trư c và sau khi t i ưu hóa. 5. Ý nghĩa khoa h c và th c ti n * Ý nghĩa khoa h c K t qu nghiên c u có th làm tài li u tham kh o cho vi c phân tích các thu t toán c a h mã hóa RSA. Ph n nghiên c u lý thuy t s ñưa ra m t cách nhìn t ng quát v mã hóa công khai và v n ñ t i ưu hóa phép toán x lý s h c v i s nguyên l n trong h mã RSA. * Ý nghĩa th c ti n Cài ñ t th nghi m các phép tính toán v i s nguyên có giá tr l n và s d ng thu t toán t i ưu hóa xây d ng ng d ng mã hóa – gi i mã các t p tin văn b n. 6. C u trúc c a lu n văn Ngoài ph n m ñ u, k t lu n và tài li u tham kh o trong lu n văn g m có các chương như sau : Chương 1 : Lý thuy t và th c ti n mã hoá d li u Chương 2 : Phân tích cơ ch ho t ñ ngc a h mã v i khóa công khai Chương 3 : T i ưu hóa gi i thu t x lý s h c và cài ñ t th nghi m h m t mã RSA
CHƯƠNG 1 - LÝ THUY T VÀ TH C TI N V MÃ HÓA D LI U 1.1 KHÁI NI M V MÃ HÓA D LI U 1.1.1 L ch s phát tri n 1.1.2 Khái ni m chung v m t mã 1.1.3 Nh ng yêu c u ñ i v i h m t mã hi n ñ i 1.1.4 Các phương pháp mã hóa 1.1.4.1 H th ng mã hóa ñ i x ng 1.1.4.2 H th ng mã hóa b t ñ i x ng B n mã B n rõ Mã hóa Gi i mã B n rõ Khóa mã Khóa gi i Hình 1.2: Sơ ñ ho t ñ ng c a mã hóa khóa b t ñ i x ng 1.2 KHÁI NI M Đ PH C T P THU T TOÁN 1.2.1 M t s ñ nh nghĩa Đ nh nghĩa 1.1: Đ nh nghĩa 1.2: M t thu t toán ñư c g i là có ñ ph c t p ña th c, ho c có th i gian ña th c, n u s các phép tính c n thi t khi th c hi n thu t toán không vư t quá O(P(n)),trong ñó P(n) là ña th c b c cao (t 2 tr lên). Các thu t toán v i th i gian O(αn), trong ñó α > 1, ñư c g i là các thu t toán v i ñ ph c t p mũ, ho c th i gian mũ.
T n t i nh ng thu t toán có ñ ph c t p trung giangi a ña th c và mũ.Các thu t toán ñó ñư c g i là thu t toán dư i mũ. B ng 1.1: B ng chi phí th i gian phân tích s nguyên n ra th a s nguyên t S ch s S phép tính Th i gian th p phân trên bit 50 1,4.1010 3,9 gi 12 75 9,0.10 104 ngày 15 100 2,3.10 74 năm 23 200 1,2.10 3,8.109 năm 300 1,5.1029 4,9.1015 năm 500 1,3.1039 4,2.1025 năm 1.2.2 Các bài toán khó tính toán và ng d ng trong m t mã h c Đ nh nghĩa 1.3: Đ nh nghĩa 1.4: Ví d v hàm m t chi u: - V i N = p*q, trong ñó p và q là các s nguyên t l n, khi ñó ta d dàng tìm ñư c N khi bi t p và q, nhưng n u cho trư c s N thì khó mà tìm ñư c 2 s p và q. - fg,N : x → gx mod N là hàm m t chi u. Th t v y, phép tính gxmod N có ñ ph c t p ña th c; nhưng tính f-1 l i là bài toán c c khó (bài toán logarithm r i r c). 1.3 CƠ S TOÁN H C C A M T MÃ H C 1.3.1 M t s ñ nh nghĩa 1.3.2 Lý thuy t ñ ng dư th c
Đ nh nghĩa 1.5: Cho a và b là các s nguyên, a ñư c g i là ñ ng dư v i b theo modulo n, ký hi u là a b (mod n) n u n chia h t (a- b). S nguyên n ñư c g i là modulo c a ñ ng dư. 1.3.3 Hàm phi Euler Đ nh nghĩa 1.6 Cho n ≥1, ñ t φ(n) là t p các s nguyên trong kho ng [1, n] nguyên t cùng nhau v i n. Hàm φ như th ñư c g i là hàm phi Euler. Tính ch t c a hàm phi Euler: 1. N u p là s nguyên t thì φ(p) = p – 1 2. Hàm phi Euler là hàm có tính nhân: N u gcd(m,n) = 1 thì φ(m.n) =φ(m).φ(n). (trong ñó gcd(m, n) là ký hi u ư c s chung l n nh t c a m và n) 3. trong ñó p1, p2,…pk là các th a s nguyên t c a n, ei (i=1...k) là d ng bi n ñ i s mũ c a n thì: Công th c này là m t tích Euler và thư ng ñư c vi t là v i tích ch y qua các s nguyên t p là ư c c a n. Ví d :
Đ nh lý 1.1 (Euler) 1.3.4 Không gian Zn * Các ñ nh nghĩa trong không gian Zn * Các tính ch t trong không gian Zn 1.3.5 Nhóm nhân Z*n 1.3.6 Th ng dư Đ nh nghĩa 1.7 1.3.7 Các thu t toán trong Zn * Thu t toán tính ngh ch ñ o nhân trong Zn Bài toán phát bi u như sau: Cho a Zn, hãy tìm a-1 mod n n u có. Bư c ñ u, dùng thu t toán Euclid m r ng sau ñ tìm các s nguyên x và y sao cho: ax + ny = d v i d = gcd(a,n). -1 N u d > 1 thì a mod n không t n t i.Ngư c l i, return (x). Thu t toán Euclid m r ng(N+={1,2,3,…,} Algorithm Euclid INPUT: a, b N+; //N+là t p các s nguyên dương OUTPUT: x, y Z th a ax + by = gcd(a, b) Method x0=1 : x1=0 : y0=0 : y1=1; While b>0 r= a mod b; if r=0 then Exit While; q= a / b;x= x0-x1*q;y= y0-y1*q; a=b;b=r;x0=x1;x1=x;y0=y1;y1=y; endwhile; return (x, y);
end. Ví d :V i a=29, b=8, gi i thu t tr i qua các bư c như sau - Bư c i ri ri + 1 ri + 2 qi + 1 xi xi + 1 xi + 2 yi yi + 1 yi + 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 k t qu trên ta có x = -3, y = 11 1.3.8 Thu t toán ki m tra tính nguyên t
CHƯƠNG 2 – PHÂN TÍCH CƠ CH HO T Đ NG C A H MÃ V I KHÓA CÔNG KHAI 2.1 H TH NG MÃ V I KHÓA CÔNG KHAI 2.1.1 Gi i thi u chung 2.1.2 M t s quan ñi m c a h m t mã v i khóa công khai 2.1.3 Nguyên lý ho t ñ ng c a h m t mã v i khóa công khai Đ i v i h th ng mã hóa khóa công khai: M i ngư i s d ng ph i t o riêng cho mình m t c p khóa. Trong ñó, m t khóa công khai (public key) cùng v i thu t toán mã hóa E, ñư c công b r ng rãi t i thư m c dùng chung cho m i ngư i s d ng. Còn l i là khóa riêng (private key) cùng v i thu t toán gi i mã D ñư c gi bí m t b i ngư i s d ng. Như v y, ngư i A mu n g i thông ñi p R ñ n cho ngư i B: Gi s : Khóa công khai c a B là: KB, Khóa riêng c a B là: MB Khóa công khai c a A là: KA , Khóa riêng c a A là: MA Thu t toán mã hóa: E, thu t toán gi i mã: D Ngư i A tìm khóa công khai KB c a ngư i B trong thư m c dùng chung và tính C = E(KB, R), sau ñó g i b n mã C cho ngư i B. Khi nh n b n mã C ngư i B s gi i mã d a vào khóa riêng MB c a mình ñ tính R = D(MB, C). 2.1.4 Các yêu c u c a h m t mã v i khóa công khai 2.2 H M T MÃ KHÓA CÔNG KHAI RSA 2.2.1 Bài toán phân tích s nguyên Bài toán 2.1 (Bài toán phân tích s nguyên): Bài toán 2.2 (Bài toán RSA):
Cho s nguyên dương N, N=p*q v i p và q là các s nguyên t phân bi t, s nguyên e sao cho th a mãn gcd(e, (p – 1) * (q – 1)) = 1, và s nguyên c. Tìm m t s nguyên m sao cho me c (mod N). Bài toán RSA cũng có ñ khó tương t như bài toán phân tích s nguyên, nhưng nó d dàng ñư c gi i n u như bi t ñư c hai s nguyên t p và q. 2.2.2 Quá trình t o khoá, mã hoá và gi i mã 2.2.2.1 T o khóa: - T o hai s nguyên t phân bi t p và q l n, sao cho bài toán phân tích th t s là khó gi i (kích c m i s kho ng 512 bits 1024 bits). - Tính N = p* q và φ(N) = (p – 1) * (q – 1). - Ch n m t s nguyên ng u nhiên e sao cho 1< e
- Bi n ñ i các ký t trong thông ñi p M thành các s nguyên tương ng, thí d theo qui t c: D u cách 00, A 01, B 02,..., Z 26. - Chia thông ñi p v a bi n ñ i thành k nhóm có chi u dài b ng nhau, m i nhóm bi u di n m t s nguyên Mi {0,…, N – 1} (v i 1 ≤ i ≤ k). - Th c hi n mã hóa l n lư t cho t ng s Mi Ci b ng cách: Ci = Mie (mod N). T p các s nguyên {C1, C2,...,Ck} là b n mã ñ g i ñ n ngư i nh n B. 2.2.2.3 Gi i mã: Ngư i nh n B th c hi n các bư c sau: - Th c hi n gi i mã l n lư t t ng s nguyên Ci Mib ng cách: Mi = D(Ci) = Cid (mod N) v i 0 ≤ Mi < N, (d là khoá bí m t c a B). - Th c hi n phép bi n ñ i ngư c l i t các s Mi thành các chu i ký t tương ng ñ khôi ph c l i n i dung thông ñi p M ban ñ u. 2.2.3 Tính ñúng c a quá trình gi i mã Ví d 2.1: Minh h a c a h m t mã RSA + T o khóa: Ch n p và q là nh ng s nguyên t nh v i m c ñích minh h a - Ch n hai s nguyên t p = 41, q = 67; - Tính N = 41 * 67 = 2747 và φ(N) = (41- 1) * (67-1) = 2640; - Ch n e = 59 th a mãn gcd(e, φ(N)) = gcd(2640, 59) = 1; - Do gcd(2640, 59) = 1 nên áp d ng thu t toán Euclid m r ng tìm ph n t ngh ch ñ o d = 179 (d là ph n t ngh ch ñ o c a e modulo φ(N)).
- Công b khóa công khai là c p s ( e = 59, N = 2747), khóa bí m t là (d,p,q) = (179,41,67) + Mã hóa: Gi s n i dung c n mã hoá là M = “MA HOA CONG KHAI ” - Bi n ñ i các ký t c a thông ñi p thành các s tương ng như sau: M A H O A C O N G 13 01 00 08 15 01 00 03 15 14 07 00 K H A I 11 08 01 09 - Chia thông ñi p thành 8 kh i, m i kh i g m 4 ch s bi u di n m t s nguyên Mi
Kh i 1 2 3 4 5 6 7 8 Ci=E(Mi) 2352 2537 1745 2733 1203 2651 0534 0454 Mi 1301 0008 1501 0003 1514 0700 1108 0109 - Th c hi n phép bi n ñ i ngư c t các s Mi thành các chu i ký t tương ng ñ khôi ph c l i thông ñi p g c ban ñ u M = "MA HOA CONG KHAI". 2.2.4 Chi phí th c hi n trong quá trình mã hóa và gi i mã - Chi phí cho quá trình mã hoá: Tính C = Me mod N, v i s mũ e thư ng ñư c ch n có d ng e = 216 – 1 Như v y, t ng chi phí c a quá trình mã hóa là hàm mũ. - Chi phí cho quá trình gi i mã: Quá trình gi i mã c a h RSA, ch th c hi n phép tính M = Cd mod N, v i s mũ bí m t d thư ng r t l n (d N) ñ ñ m b o ñ an toàn cho d li u. Vì v y, chi phí th c hi n gi i mã c a h RSA tương ñương v i chi phí ñ th c hi n hàm mũ. 2.2.5 Đánh giá h m t mã khóa công khai RSA 2.2.5.1 Đ an toàn H RSA ñư c thi t k d a trên ñ khó gi i bài toán phân tích ra th a s nguyên t . H u h t các phương pháp thám mã h RSA như tìm các th a s p và q, tìm φ(n), hay tìm khóa riêng d… ñ u khó như bài toán phân tích. Sau ñây,ta có b ng chi phí th i gian c n thi t ñ phân tích nh ng h m t mã RSA có kích c s modulo N khác nhau, b ng nh ng thu t toán phân tích t t nh t hi n nay. ñây chi phí tính toán ñư c tính b ng ñơn v MIPS-Years (ñó là s các phép tính ñã hoàn thành b i m t máy trong th i gian m t năm, v i t c ñ kho ng 106 phép tính trên m t giây, ta có 1MIPS-Years 245 phép tính).
B ng 2.2: B ng chi phí th i gian c n thi t ñ phân tích các s nguyên N Chi phí phân S ch s S Thu t H RSA Năm tích (MIPS- th p phân bit toán Years) RSA-129 129 462 MPQS 1994 5000 RSA-130 130 430 GNFS 1996 1000 RSA-140 140 465 GNFS 1999 2000 RSA-155 155 512 GNFS 1999 8000 RSA-576 174 576 GNFS 2003 13000 2.2.5.2 Hi u su t th c hi n và ng d ng 2.3 H M T MÃ RSA WITH CRT 2.3.1 Đ nh lý ñ ng dư Trung Hoa 2.3.2 Thu t toán Garner 2.3.3 Các quá trình t o khoá, mã hoá và gi i mã 2.4 PHÂN TÍCH CƠ CH HO T Đ NG C A H MÃ RSA 2.4.1 Phân tích quá trình t o khóa: - T o hai s nguyên t phân bi t p và q l n, sao cho bài toán phân tích th t s là khó gi i. - Tính N = p* q vàφ(N) = (p – 1) * (q – 1). - Ch n m t s nguyên ng u nhiên e sao cho 1< e
Như v y, m u ch t ñ tăng tính an toàn c a h mã RSA là ta c n th c hi n ñư c quá trình mã hóa xu t phát t các s nguyên t p, q l n. 2.4.2 Phân tích quá trình mã hóa: Gi s ñ g i thông ñi p M cho ngư i B. Ngư i A th c hi n: - L y khóa công khai c a ngư i nh n B: (e, N). - Bi n ñ i thông ñi p M thành nh ng s nguyên Mi tương ng sao cho Mi< N, (i = 1,…, k). Theo phép bi n ñ i sau: - Bi n ñ i ký t trong thông ñi p M thành các s nguyên tương ng, thí d theo qui t c: D u cách↔00, A↔01, B ↔02,.., Z ↔ 26. - Chia thông ñi p v a bi n ñ i thành k nhóm có chi u dài b ng nhau, m i nhóm bi u di n m t s nguyên Mi {0,…, N – 1} (v i 1 ≤ i ≤ k). - Th c hi n mã hóa l n lư t cho t ng s Mi→ Ci b ng cách: Ci = Mie (mod N). T p {C1, C2,...,Ck} là b n mã ñ g i ñ n ngư i nh n B. Ta th y r ng quá trình mã hóa ph i th c hi n liên ti p vi c mã hóa các s Mitheo công th c: Ci = Mie (mod N). Khi p và q l n thì ta có N = p*q r t l n. Trên lý thuy t, s e có th ch n ch c n th a mãn gcd(e, φ(N)) = 1, tuy nhiên ñ tăng tính an toàn, s e thư ng ñư c s là s l n hơn Max(p,q) v i Max(p,q) tr v s l n nh t gi a p và q. Do ñó, quá trình mã hóa s th c hi n v i các s r t l n nhưng v n ph i ñ m b o th i gian th c hi n vi c mã hóa là ñ t t. Xu t phát t các lí do trên, ta c n tác ñ ng vào quá trình mã hóa b ng các thu t toán t t ñ có th th a mãn các yêu c u trên. 2.4.3 Phân tích quá trình gi i mã: Ngư i nh n B th c hi n các bư c sau:
- Th c hi n gi i mã l n lư t t ng s nguyên Ci→ Mib ng cách: Mi = D(Ci) = Cid (mod N) v i 0 ≤ Mi< N, (d là khoá bí m t c a B). - Th c hi n phép bi n ñ i ngư c l i t các s Mi thành các chu i ký t tương ng ñ khôi ph c l i n i dung thông ñi p M ban ñ u. Quá trình gi i mã cũng ph i th c hi n vi c tính toán liên ti p ñ tìm Mi theocông th c: Mi = D(Ci) = Cid (mod N), quá trình này cũng th c hi n trên các s l n vì ta có d là s l n. Do ñó, quá trình gi i mã cũng c n có các tác ñ ng ñ ñ m b o th i gian gi i mã là ch p nh n ñư c. Đi u này có ý nghĩa r t quan tr ng vì h mã RSA có s lư ng phép tính l n, bên c nh ñó ñ có th th c hi n v i các b n rõ có n i dung l n thì ta ph i gi i quy t ñư c v n ñ này. K t lu n: Trong th c t , t c ñ mã hóa và gi i mã c a RSA ch m so v i các h mã khác.Đi u này d n ñ n vi c RSA ch y u ñư c dùng ñ mã hóa khóa bí m t ho c các các b n rõ ng n.Ph n n i dung chính c n g i s ñư c mã hóa b ng m t phương pháp mã hóa khác có t c ñ th c hi n nhanh hơn (Phương pháp này thư ng kém an toàn hơn so v i RSA). Ngư i nh n s gi i mã b ng RSA ñ l y khóa bí m t r i m i ti n hành gi i mã n i dung c n nh n. 2.5 KH NĂNG B B KHÓA C A H MÃ CÔNG KHAI RSA 2.5.1 M t s phương pháp t n công h mã RSA. 2.5.2 Đ an toàn c a h mã RSA. 2.6 H M T MÃ KHÓA CÔNG KHAI ELGAMAL 2.6.1 Bài toán logarithm r i r c 2.6.2 Đ nh nghĩa các t p làm vi c c a h m t mã ElGamal 2.6.3 Quá trình t o khoá, mã hoá, gi i mã 2.6.4 Đánh giá ñ an toàn và kh năng ng d ng c a h m t mã khóa công khai ElGamal
CHƯƠNG 3 –T I ƯU HÓA GI I THU T X LÝ S H C VÀ CÀI Đ T TH NGHI M H M T MÃ RSA 3.1 PHÂN TÍCH CÁC THU T TOÁN X LÝ S H CC A RSA Trong quá trình t o khóa ta c n ph i t o ra hai s nguyên t phân bi t p và q l n, sao cho bài toán phân tích th t s là khó gi i.Như v y, ñ ñ m b o an toàn cho h mã RSA, gi i thu t x lý ph i th c hi n ñư c v i các s l n hàng trăm ch s . 3.1.1 Phép nhân, c ng và tr Trong quá trình t o khóa, ta ph i tính ñư c N = p*q và φ(N) = (p–1)*(q–1). Do ñó chương trình c n x lý ñư c phép nhân hai s p và q v i p và q là các s nguyên t giá tr l n. 3.1.2 Phép lũy th a Quá trình gi i mã c a RSA c n tínhM = Cdmod N, v i s mũ bí m t d thư ng r t l n (d N) ñ ñ m b o ñ an toàn cho d li u. Vì v y chi phí th c hi n gi i mã c a h RSA tương ñương v i chi phí ñ th c hi n phép tính lũy th a nhanh là hàm mũ. Do ñó chương trình c n ph i x lý ñư c các phép tính lũy th a nhanh b ng cách: ñưa phép lũy th a v d ng phép nhân liên ti p s d ng các tính ch t ñ ng dư. Vì th , ñ tài s d ng gi i thu t Fast Fourier Transform ñ gi i quy t v n ñ này. 3.2 NG D NG GI I THU T FAST FOURIER TRANSFORM TRONG X LÝ PHÉP NHÂN 3.2.1 Gi i thi u thu t toán FFT Cho hai s l n X và Y v i kích thư c l n nh t là n-1, chúng có th ñư c vi t d ng sau: X = P(B), Y = Q(B)
V i B là cơ s (Thông thư ng B=10 ho c là lũy th a c a 10). P và Q là hai ña th c: K t qu khi th c hi n nhân P(z) v i Q(z), khi ñó ta có ñư c tích X.Y=R(B). B ng cách s p x p l i theo h s ta thu ñư c k t qu c a phép nhân X v i Y. D a trên lý thuy t này, ta áp d ng ñ th c hi n vi c nhân hai ña th c có b c nh hơn n. M t ña th c có b c nh hơn m là duy nh t khi nó ñư c t o b i các giá tr c th t i m ñi m. Do ñó, ñ tính tích R(z)= P(z).Q(z) ta c n ñi tính các giá tr R(wk) t i 2n ñi m phân bi t ng v i m i wk, ñi u này cũng có nghĩa là ta c n tính các giá tr c a P(wk) và Q(wk). Thu t toán FFT là m t g i ý phù h p v i vi c l a ch n cho wk căn c a ñơn v . là căn ph c b c n c a 1, trong ñó k = 0,1,…,2n-1 V i cách l a ch n này, các giá tr wk th a mãn hai thu c tính sau: - T p h p các giá tr (P(w0),...,P(w2n-1)) và (Q(w0),…,Q(w2n-1)) có th tính toán ñư c trong th i gian O(n logn). - T các giá tr R(wk), ña th c R(z) thu ñư c trong th i gian O(n logn). Khi ñó, h s th k kí hi u là rk c a R(z) th a mãn: 3.2.2 Bi n ñ i Fourier Cho dãy A = (a0, a1,…, a2n-1), tìm d ng bi n ñ i Fourier c a dãy A.