Giáo trình tin học : Tìm hiểu một sơ đồ chữ kí số phần 7

Trong phần này ta sẽ mô tả một hàm Hash do Chaum-Van Heyst và Pfĩtmann đưa ra. Hàm này an toàn do không thể tính được logarithm rời rạc.
Nội dung trích xuất từ tài liệu:
Giáo trình tin học : Tìm hiểu một sơ đồ chữ kí số phần 7Vietebooks Nguyễn Hoàng Cương7.3. hµm hash logarithm rêi r¹c Trong phÇn nµy ta sÏ m« t¶ mét hµm Hash do Chaum-Van Heyst vµPfÜtmann ®−a ra. Hµm nµy an toµn do kh«ng thÓ tÝnh ®−îc logarithm rêi r¹c.Hµm Hast nµy kh«ng ®ñ nhanh ®Ó dïng trong thùc tÕ song nã ®¬n gi¶n vµ chomét vÝ dô tèt vÒ mét hµm Hash cã thÓ an toµn d−íi gi¶ thuyÕt tÝnh to¸n hîp lýnµo sè. Hµm Hash Caum-Van Heyst- PfÜtmann ®−îc nªt trong h×nh 7.3. Sau®©y sÏ chøng minh mét ®Þnh lý liªn quan ®Õn sù an toµn cña hµm Hast nµy.§Þnh lý 7.2. NÕu cho tr−íc mét va ch¹m víi hµm Hash Chaum-Van Heyst-PfÜtmannh cã thÓ tÝnh ®−îc logarithm rêi r¹c logαβ mét c¸ch cã hiÖu qu¶.Chøng minh Gi¶ sö cho tr−íc va ch¹m h(x1,x2) = h(x3,x4)trong ®ã (x1,x2) ≠ (x3,x4). Nh− vËy ta cã ®ång d− thøc sau: αx1βx2 = αx3βx4hay αx1βx2 ≡ αx3βx4 (mod p)Ta kÝ hiÖu D = UCLN (x4-x2,p-1)V× p-1 =2q ,q lµ sè nguyªn tè nªn d ∈ {1, 2, q, p-1}. V× thÕ, ta cã 4 x¸c suÊtvíi d sÏ xem xÐt lÇn l−ît dwois ®©y. Tr−íc hÕt ,gi¶ sö d =1 ,khi ®ã cho y= (x4-x2)-1 mod (p-1)ta cã (x -x )y β ≡ β 4 2 (mod p) (x -x )y ≡ α 1 2 (mod p)V× thÕ, cã thÓ tÝnh loarithm rêi r¹c logαβ nh− sau: logαβ = (x1-x3) (x4-x2)-1mod (p-1)TiÕp theo, gi¶ sö d=2. V× p-1 =2q, lÎ nªn UCLN(x4-x2,q) =1. Gi¶ sö: y=(x4-x2)-1 mod q Trang 37Vietebooks Nguyễn Hoàng CươngxÐt thÊy (x4-x2)y = kq+1víi sè nguyªn k nµo ®ã. V× thÕ ta cã: (x -x )y β 4 2 ≡ βkq+1 (mod p) ≡ (-1)k β (mod p) ≡ ± β (mod p) β ≡-1(mod p) qV×Nªn α(x4-x2)y ≡ β (x1-x3) (mod p) ≡ ± β (mod p)Tõ ®ã suy ra r»ng: logαβ = (x1-x3)y mod (p-1) logαβ = (x1-x3)y mod (p-1)Ta cã thÓ dÔ dµng kiÓm tra thÊy mét trong hai x¸c suÊt trªn lµ ®óng. V× thÕnh− trong tr−êng hîp d =1, ta tÝnh ®−îc logαβ. X¸c suÊt tiÕp theo lµ d = q. Tuy nhiªn q-1≥ x1≥ 0 q-1≥ x3≥ 0vµnªn (q-1) ≥ x4-x2 ≥ -(q-1)do vËy UCLN(x4-x2,p-1) kh«ng thÓ b»ng q, nãi c¸ch kh¸c tr−êng hîp nµykh«ng x¶y ra. X¸c suÊt cuèi cïng lµ d = p-1. §iÒu nµychØ x¶y ra khi x2 =x4. Song khi®ã ta cã αx1βx2 ≡ αx3βx4 (mod p) αx1 ≡ αx3 (mod p)nªnvµ x1 =x2. Nh− vËy (x1,x2) = (x3,x4) ⇒ m©u thuÉn. Nh− vËy tr−êng hîp nµycòng kh«ng thÓ cã. V× ta ®· xem xÐt tÊt c¶ c¸c gi¸ trÞ cã thÓ ®èi víi d nªn cã thÓ kÕt luËnr»ng ,hµm Hash h lµ kh«ng va ch¹m m¹nh miÔn lµ kh«ng thÓ tÝnh ®−îclogarithm rêi r¹c logαβ trong Zp.Ta sÏ minh ho¹ lý thuyÕt nªu trªn b»ng mét vÝ dô.VÝ dô 7.1 Gi¶ sö p =12347 (v× thÕ q = 6173), α = 2, β = 8461. Gi¶ sö ta ®−îc ®−atr−íc mét va ch¹m α5692 β 144 ≡ α212 β4214 (mod 12347)Nh− vËy x1 = 5692, x2 = 144, x3 = 212, x4 = 4214. XÐt thÊy UCLN (x4 -x2,p-1)=2 nªn ta b¾t ®Çu b»ng viÖc tÝnh y = (x4 - x2)-1 mod q = (4214 - 144)-1 mod 6173 = 4312 Trang 38Vietebooks Nguyễn Hoàng CươngTiÕp theo tÝnh y = (x1- x3) mod (p-1) = (5692 - 212) 4312 mod 12346 = 11862XÐt thÊy ®ã lµ tr−êng hîp mµ logαβ ∈ {y’,y’+q mod (p-1)}. V× αy mod p =212346 = 9998nªn ta kÕt luËn r»ng: logαβ = y’ + q mod (p-1) = 11862 + 6173 mod 12346 = 5689nh− phÐp kiÓm tra, ta cã thÓ x¸c minh thÊy r»ng 25689 = 8461 (mod 12347)V× thÕ , ta c¸c ®Þnh ®−îc logαβ.7.5.c¸c hµm hash më réng Cho ®Õn lóc nµy, ta ®· xÐt c¸c hµm Hash trong vïng h÷u h¹n. B©y giê tanghiªn xÐu c¸ch cã thÓ më réng mét hµm Hash kh«ng va ch¹m m¹nh tõ vïngh÷u h¹n sang vïng v« h¹n. §iÒu nµy cho phÐp ký c¸c bøc ®iÖn cã ®é dµi tuú ý.GØa sö h: (Z2)m → (Z2)t lµ mét hµm hash kh«ng va ch¹m m¹nh ,trong ®ã m ≥t-1. Ta sÏ dïng h ®ªu x©y dùng hµm hash kh«ng va ch¹m m¹nh h: X →(Z2)ttrong ®ã ∞ U (Z2)t X= i =mTr−íc tiªn xÐt tr−êng hîp m ≥ t+2. Ta sÏ xem c¸c phÇn tö cña X nh− c¸c x©y bit. |x| chØ ®é dµI cña x (tøcsè c¸c bit trong x) vµ x||y ký hiÖu sù kÕt hîp c¸c x©y x vµ y. Gi¶ sö |x| = n >m. Cã thÓ biÓu thÞ x nh− mét chuçi kÕt hîp. X = x1||x2||...||xkTrong ®ã |x1| =|x2| = ... = |xk-1| = m- t-1vµ |xk| = m- t- 1- d H×nh 7.4. Më réng hµm hash h thµnh h* (m ≥t+2) Trang 39Vietebooks Nguyễn Hoàng Cương 1. For i= 1 to k ...