Bài tập lớn môn an toàn bảo mật thông tin

BÀI TẬP LỚN MÔN AN TOÀN BẢO MẬT THÔNG TIN SƠ ĐỒ XƯNG DANH GUILLOU-QUISQUATER Giáo viên hướng dẫn : Ks Trần Ngọc Thái Nhóm sinh viên : Nguyễn Khánh Ly Lê Hoàng Tùng Lớp CT702 Trường ĐHDL Hải Phòng NỘI DUNG CHÍNH. I.Giới thiệu II.Cấp chứng chỉ III.Giao thức xác nhận danh tính IV.Ví dụ minh họa V.Mở rộng I.Giới thiệu S¬ ®å Guillou-Quisquater còng ®­îc x©y dùng theo cïng mét c¸ch thøc nh­ c¸c s¬ ®å Schnorr vµ Okamoto kÓ trªn, nh­ng bµi to¸n khã mµ ta dùa vµo ë ®©y kh«ng phải lµ bµi to¸n tÝnh l«garit rêi r¹c mµ lµ bµi to¸n RSA. S¬ ®å cÇn cã sù tham gia cña mét c¬ quan uû th¸c TA ®Ó cÊp chøng chØ cho c¸c ng­êi tham gia. TA chän hai sè nguyªn tè lín p vµ q vµ tÝnh tÝch n =pq, giữ bÝ mËt p ,q vµ c«ng khai n. C¸c tham sè ®ã ®­îc chän sao cho bµi to¸n ph©n tÝch n thµnh thõa sè lµ rÊt khã. I.Giới thiệu TA còng chän thªm mét sè b lµ sè nguyªn tè cã ®é lín khoảng 240 nh­ lµ mét tham sè an toµn. Sè b còng ®­îc xem lµ sè mò thoả m·n ®iÒu kiÖn RSA, nghÜa lµ viÖc tÝnh v =ub modn lµ dÔ, nh­ng viÖc tÝnh ng­îc u tõ v lµ rÊt khã, nÕu kh«ng biÕt p,q. I.Giới thiệu Thñ tôc cÊp chøng chØ cho mét ng­êi tham gia A ®­îc tiÕn hµnh nh­ sau: 1.TA x¸c lËp c¸c th«ng tin vÒ danh tÝnh cña A d­íi d¹ng mét d·y ký tù mµ ta ký hiÖu lµ I A hay ID(A). 2. A chän bÝ mËt mét sè ngÉu nhiªn u (0 u  n-1), tÝnh vµ chuyÓn sè v cho TA. II.Cấp chứng chỉ. 3. TA t¹o chữ ký s =sigTA(IA, v) vµ cÊp cho A chøng chØ C(A) = (ID(A), v, s ). Nh­ vËy, chøng chØ mµ TA cÊp cho A gåm (IA, v) vµ chữ ký cña TA trªn th«ng tin (IA, v) ®ã. II.Cấp chứng chỉ. B©y giê, víi chøng chØ C(A) ®ã, A cã thÓ x­ng danh víi bÊt kú ®èi t¸c B nµo b»ng c¸ch cïng B thùc hiÖn mét giao thøc x¸c nhËn danh tÝnh nh­ sau: 1. A chän thªm mét sè ngÉu nhiªn k (0 k  n-1), tÝnh vµ göi cho B c¸c th«ng tin C(A) vµ . III.Xác nhận danh tính 2. B kiÓm thö chữ ký cña TA trong chøng chØ C(A) bëi hÖ thøc verTA(ID(A), v, s)=®óng. KiÓm thö xong, B chän mét sè ngÉu nhiªn r (1 r  b -1 ) vµ göi r cho A. 3. A tÝnh y =k.u r modn vµ göi y cho B. 4. B thö ®iÒu kiÖn (modn) vµ nÕu ®iÒu kiÖn ®ã ®­îc thoả m·n thi x¸c nhËn danh tÝnh cña A. III.Xác nhận danh tính ViÖc chøng minh tÝnh ®Çy ®ñ cña s¬ ®å lµ rÊt ®¬n giản: Mét ng­êi kh¸c A, do kh«ng biÕt sè bÝ mËt u , nªn kh«ng thÓ tÝnh ®óng ®­îc sè y ë b­íc 3 cña giao thøc ®Ó ®­îc B x¸c nhËn (nh­ lµ A) ë b­íc 4, tøc kh«ng thÓ m¹o nhËn minh lµ A; ®ã lµ tÝnh ®óng ®¾n cña s¬ ®å. III.Xác nhận danh tính Giả sö cã mét ng­êi O cã thÓ thùc hiÖn th«ng suèt giao thøc x¸c nhËn ®Ó cã thÓ ®­îc m¹o nhËn lµ A, ch¼ng h¹n Ýt nhÊt hai lÇn. ĐiÒu ®ã cã nghÜa lµ O biÕt ®­îc hai sè r1  r2 vµ hai sè y1, y2 sao cho Giả thiÕt r1  r2, khi ®ã ta cã III.Xác nhận danh tính Do 0 r1 -r2 b vµ b lµ sè nguyªn tè nªn gcd(r1 -r2, b) =1, cã thÓ tÝnh ®­îc dÔ dµng t =(r1 -r2)-1modb , vµ cã (modn). Do t =(r1 -r2)-1modb nªn ta cã (r1 -r2)t =lb +1 víi l lµ mét sè nguyªn d­¬ng nµo ®ã, vi vËy, (modn), III.Xác nhận danh tính hay lµ (modn). N©ng cả hai vÒ lªn luü thõa bËc b –1 mod (n), ta ®­îc III.Xác nhận danh tính cuèi cïng, tÝnh nghÞch ®ảo cña hai vÕ theo modn ta ®­îc u = mod n Nh­ vËy, O tÝnh ®­îc sè bÝ mËt u trong thêi gian ®a thøc! Theo giả thiÕt, ®iÒu ®ã kh«ng thÓ xÈy ra, vi vËy, giả thiÕt vÒ viÖc O cã thÓ thùc hiÖn th«ng suèt giao thøc x¸c nhËn ®Ó ®­îc m¹o nhËn danh tÝnh lµ A lµ kh«ng ®óng. =>s¬ ®å x­ng danh ®­îc chøng minh lµ an toµn. III.Xác nhận danh tính Giả sö TA chän p =467, q =479, =>n =223693, TA chän thªm b =503. Giả sö A chän sè bÝ mËt u =101576, vµ tÝnh v =(101576-1)503 mod223693 = 89888. TA t¹o chữ ký s =sigTA(ID(A),v) vµ cÊp cho A chøng chØ C(A) = (ID(A),v,s). IV.Ví dụ Giả thiÕt A muèn x­ng danh víi B, + A chän k =187485 , vµ göi cho B gi¸ trÞ  =187485503mod223693 =24412. + B dïng thuËt to¸n kiÓm thö verTA ®Ó thö ®iÒu kiÖn verTA(ID(A),v,s) = ®óng, sau ®ã göi ®Õn A c©u hái r = 375. A sÏ trả lêi l¹i b»ng y =187485.101576375 mod223693 = 93725. + B thö ®iÒu kiÖn (modn), trong tr­êng hîp nµy lµ 24412  89888375. 93725503(mod 223693), ®ång d­ thøc ®ã ®óng. VËy B x¸c nhËn danh tÝnh cña A. IV.Ví dụ B©y giê giả thiÕt lµ O biÕt ®­îc hai sè r1=401, r2=375 vµ c¸c sè t­¬ng øng y1=103386 vµ y2=93725. O biÕt r»ng: v 401.103386b  v 375. 93725b (modn). O sÏ tÝnh: t =(r1- r2)-1 modb = (401-375)-1mod503 =445, sau ®ã tÝnh ®­îc : IV.Ví dụ Cuèi cïng, O sÏ tim ®­îc gi¸ trÞ bÝ mËt u lµ modn = (103386/93725)445.8988823 mod 223693 = 101576, lµ sè bÝ mËt cña A. IV.Ví dụ Ta cã thÓ thay ®æi ®Ó biÕn s¬ ®å x­ng danh Guillou-Quisquater thµnh mét s¬ ®å x­ng danh dùa vµo danh tÝnh mµ kh«ng cÇn cã chøng chØ nh­ sau: V.Mở rộng S¬ ®å dïng mét hµm băm c«ng khai h , vµ thay cho viÖc cÊp chøng chØ C(A) cho ng­êi tham gia A, TA sÏ cÊp cho A danh tÝnh ID(A) cïng mét sè u ®­îc tÝnh bëi c«ng thøc u =(h(ID(A))-1)a modn . (a lµ mét sè mò bÝ mËt cña TA). Sè u ®­îc A giữ riªng cho minh. Khi A cÇn x­ng danh víi B, A vµ B cïng thùc hiÖn mét giao thøc x¸c nhËn danh tÝnh sau ®©y: V.Mở rộng 1.A chän mét sè ngÉu nhiªn k, 0 k  n -1, vµ tÝnh:  = k b modn , råi göi ID(A) vµ  cho B. 2. B tÝnh v =h(ID(A)); chän mét sè ngÉu nhiªn r (0 r 1) vµ göi r cho A. 3. A tÝnh y =kur modn vµ göi y cho B. 4. B thö ®iÒu kiÖn   v ryb (modn) ®Ó x¸c nhËn danh tÝnh cña A. V.Mở rộng Khi x­ng danh theo giao thøc nãi trªn víi B, A chØ cÇn biÕt gi¸ trÞ u lµ mét gi¸ trÞ ®­îc tÝnh bëi TA (vµ chØ TA tÝnh ®­îc gi¸ trÞ ®ã). O kh«ng thÓ giả m¹o danh tÝnh cña A vi O kh«ng biÕt gi¸ trÞ u. V.Mở rộng