Mã hóa bức điện nhỏ bằng hàm HASH phần 2

Giả sử p là số nguyên tố lớn và q =(p-1)/2 cũng là số nguyên tố. Cho α và β là hai phần tử nguyên thuỷ của Zp. Giá trị logαβ không công khai và giả sử rằng không có khả năng tính toán được giá trị của nó.
Nội dung trích xuất từ tài liệu:
Mã hóa bức điện nhỏ bằng hàm HASH phần 2Vietebooks Nguyễn Hoàng Cương Gi¶ sö p lµ sè nguyªn tè lín vµ q =(p-1)/2 còng lµ sè nguyªn tè. Cho α vµ β lµ hai phÇn tö nguyªn thuû cña Zp. Gi¸ trÞ logαβ kh«ng c«ng khai vµ gi¶ sö r»ng kh«ng cã kh¶ n¨ng tÝnh to¸n ®−îc gi¸ trÞ cña nã. Hµm Hash: h: {0,...,q-1}×{0,...,q-1} → Zp\ {0} ®−îc ®Þnh nghÜa nh− sau: h(x1,x2) =α 1β 2 mod p xx7.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) Trang 7Vietebooks Nguyễn Hoàng CươngV× 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 qxÐ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) Trang 8Vietebooks Nguyễn Hoàng Cương α 1 ≡ α 3 (mod p) x xnª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 = 4312TiÕ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 ®ã Trang 9Vietebooks Nguyễn Hoàng Cương ∞ 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) 1. For i= 1 to k-1 do y i = xi 2. yk = xk ||0d 3. cho yk+1 lµ biÓu diÔn nhÞ ph©n cña d 4. gi = h(0I+1||y1) 5. for i=1 to k do gi+1 = h(gi||1||yi+1) 6. h*(x) = gk +1Trong ®ã m- t- 2 ≥ d ≥0. V× thÕ ta cã k= ⎡ n⎤ ⎢ ⎣ m − t − 1⎥ ⎦Ta ®Þnh nghÜa h*(x) theo thuËt to¸n biÓu kiÔn trong h×nh 7.4.KÝ hiÖu y(x) = y1||y2||...||yk-1NhËn xÐt r»ng yk ®−îc lËp tõ xk b»ng c¸ch chÌn thªm d sè 0 vµo bªn ph¶I ®ÓtÊt c¶ c¸c kh ...