Slide 1

Report
‫حمله مشبکه به امضاهای‬
‫‪Elgamal type‬‬
‫گردآورنده‪ :‬زهرا فرجی معز‬
‫با راهنمایی دکتر حسین حاجی ابوالحسن‬
‫‪ ‬در اینجا با استفاده از مشبکه حمله ای روی امضاهای‬
‫دیجیتال )‪ (DSA‬ارائه می شود‪.‬‬
‫‪ ‬این حمله از الگوریتم کاهشی ‪ LLL‬برای حل معادالت‬
‫چندجمله ای یک متغیره و دو متغیره استفاده می کند‪.‬‬
‫امضاهای دیجیتال از نوع الجمال‬
‫کلید عمومی ‪:‬‬
‫• گروه متناهی ‪، G‬‬
‫• ‪ g,hєG‬به طوریکه ‪h=g x‬‬
‫کلید خصوصی ‪:‬‬
‫• مقدار ‪x‬‬
‫• عدد اول ‪ P‬به طول حداقل ‪ 160‬بیت‪.‬‬
‫• تابع پوشای ‪f:G→Zp‬‬
‫خواهیم دید حمله به این امضا معادل‬
‫با حل مسئله ‪ appr CVP‬است‪...‬‬
‫) ‪(m, r ,s‬‬
‫‪Bob‬‬
‫‪f(g m/s h r/s)=r‬‬
‫‪Alice‬‬
‫‪Find s S.T‬‬
‫)‪m=sy-xr (mod p‬‬
‫‪m є Zp‬‬
‫]‪y є [1,…,p-1‬‬
‫)‪r=f(g y‬‬
‫هدف یافتن مقادیر ‪ y‬و ‪ x‬می باشد‪...‬‬
‫اگر فرض کنیم ‪ i‬برابر با تعداد متون امضا شده باشد‪ ،‬داریم‪:‬‬
‫)‪yi+Cix+Di = 0 (mod p‬‬
‫)‪mi-siyi+xri = 0 (mod p‬‬
‫پس در حالت کلی؛ معادله اولیه تبدیل به )‪(1≤i≤n) ، yi+Aiy0+Bi = 0 (mod p‬‬
‫]‪. Ai,Bxiє[0,…,p-1‬‬
‫هیچ=‪y0‬‬
‫فوق یا ‪x‬‬
‫معادالت = ‪yh‬‬
‫اگردردرحالی که ‪y0‬‬
‫می شود‬
‫مشخص نشده باشد‬
‫یکواز بیت های‬
‫معادله ‪h‬ام را با بقیه معادالت جمع کرده تا ‪ x‬حذف شود‪ .‬پس‬
‫‪ h-1‬معادله بر حسب ‪ yi‬و ‪ yh‬پدید می آید‪:‬‬
‫)‪yi+C΄iyh+D΄i = 0 (mod p‬‬
‫• فرض می کنیم بیت های مجهول ‪ yi‬متصل به هم باشند‪:‬‬
‫می توانیم ‪ yi‬را به صورت زیر نمایش دهیم‬
‫‪i‬‬
‫‪i‬‬
‫; ‪y i  z 2 z i 2 z‬‬
‫"‬
‫‪i‬‬
‫‪0  z i  X i  2i i , i  i , z i" 0‬‬
‫'‬
‫‪i‬‬
‫که تنها ‪ zi‬مجهول است‪.‬‬
‫به طور مثال اگر‪، yi=10100xy10‬داریم‪:‬‬
‫در نتیجه معادله )‪ yi+Aiy0+Bi = 0 (mod p‬تبدیل به )*) )‪،zi+uiz0+vi=0 (mod p‬‬
‫‪y i 02 12  y 2  x 2 02 02 12 02 12‬‬
‫‪8‬‬
‫به طوریکه‬
‫‪7‬‬
‫‪6‬‬
‫‪5‬‬
‫‪3‬‬
‫‪4‬‬
‫‪2‬‬
‫‪0‬‬
‫‪1‬‬
‫}‪ 2ui2, (vyi Є{0,…,p-1‬‬
‫‪ 2x )  2 (00,2i=1,2,…,n‬‬
‫) ‪ 2 02  2‬‬
‫‪4‬‬
‫‪3‬‬
‫‪2‬‬
‫'‪z i‬‬
‫‪2‬‬
‫‪4‬‬
‫"‪z i‬‬
‫حال نوبت به آن می رسد که نظریه مشبکه وارد عمل شود‪...‬‬
‫برای حل این معادالت‪ ،‬از مشبکه ‪ L‬تولید شده توسط ماتریس ‪A‬‬
‫استفاده می کنیم‪:‬‬
‫‪un ‬‬
‫‪ 1 u1‬‬
‫‪‬‬
‫‪‬‬
‫‪0‬‬
‫‪p‬‬
‫‪0‬‬
‫‪M‬‬
‫‪A ‬‬
‫)‪( n 1)( n 1) (Z‬‬
‫‪‬‬
‫‪0‬‬
‫‪‬‬
‫‪‬‬
‫‪0 p‬‬
‫‪0‬‬
‫بردار غیر مشبکه ‪ v‬را در نظر می گیریم‪:‬‬
‫‪v  (0,v 1,...,v n ) Zn 1‬‬
‫‪ ‬با توجه به تعریف ‪ L‬و‪ zi‬می توان نتیجه گرفت که‬
‫‪xєZn+1‬ای موجود است که )‪. xA-v=(z0,…, zn‬‬
‫‪ ‬از طرفی چون ‪ zi> Xi‬داریم ‪:‬‬
‫‪n‬‬
‫‪|| xA v ||2   X i2‬‬
‫‪i 0‬‬
:‫ خواهیم داشت‬، ε >1/(n+1) ‫ بگیریم که‬ε ‫ را برابر‬yi ‫اگر نسبت بیت های معلوم در‬
p1-ε <p
n
n+1
n 2 2
n 1
|| xA v ||  2
2
p
2n
n 1
(1)
‫ در نتیجه‬. Xi<p n/n+1 ‫ داریم‬، Xi=p 1-ε ‫از آنجا که‬
n
X
i 1
2
i
 np
2n
n 1
n 2
n 2 2
n 1
n
n 2 2
n 1
2
X
 i 2
i 1
p
2n
n 1
‫‪ Babai‬در مقاله خود‪ ،‬جایی که الگوریتم ‪ Nearest Plane‬را برای یافتن نزدیکترین‬
‫نقطه مشبکه )‪ (w‬به بردار دلخواه ‪ v‬ارائه می کند‪ ،‬ثابت می کند که‬
‫(‪)2‬‬
‫‪|| w v ||2  2n 1 || bn*1 ||2‬‬
‫‪|| bn*1 ||2‬‬
‫‪n 1‬‬
‫)‪1‬‬
‫‪2‬‬
‫(‪2‬‬
‫‪|| w v ||2  2‬‬
‫در نتیجه یافتن بردار ‪ x‬معادل با حل مسئله تقریب ‪ CVP‬است که‬
‫حلوآن می‬
‫با مقایسه الگوریتم‬
‫باشد‪.‬از آنجا که‬
‫همچنین‬
‫قادر )به‪)3‬‬
‫‪ )2Babai‬و‬
‫نامساوی های )‬
‫طبق قضیه ‪ 6.66‬در کتاب ‪ ، an introduction of mathematical cryptography‬داریم‪:‬‬
‫تعداد نقاط نزدیک به ‪ v‬در مشبکه زیاد نیست‪ ،‬می توان‬
‫‪n 1‬‬
‫‪n 1 j 1‬‬
‫همان بردار نزدیک به ‪ v‬در‬
‫‪2‬‬
‫‪|| bi || xA‬‬
‫بردار‪2‬‬
‫که ‪|| b *j‬‬
‫امیدوار بود ||‬
‫‪‬‬
‫‪‬‬
‫‪1  i  j  n 1‬‬
‫‪1‬‬
‫می‪ i‬باشد‪...‬‬
‫مشبکه ‪L(B)j 1‬‬
‫(‪)3‬‬
‫‪|| xA v ||2  22(n 1) || bn*1 ||2‬‬
‫(‪)1‬‬
‫‪n2‬‬
‫‪2‬‬
‫‪p n  2 || bn*1 ||n 1‬‬
‫‪j 1‬‬
‫‪2‬‬
‫|| ‪|| bi || 2 || b *j‬‬
‫‪n 1‬‬
‫|| ‪p     || bi‬‬
‫‪n‬‬
‫‪i 1‬‬
‫نتایج تجربی‬
‫حمله فوق را روی دستگاه ‪ HP-UX‬با اجراکننده ‪ PA1.1‬و حافظه ‪ 128 MB‬با استفاده از‪ C++‬برای‬
‫اجرای الگوریتم ‪ LLL‬به کاربرده ایم‪:‬‬
‫میانگین زمان به‬
‫ثانیه‬
‫مقدار دقیق ‪n‬‬
‫‪1/ε‬‬
‫‪ε‬‬
‫‪0.0102‬‬
‫‪2‬‬
‫‪2‬‬
‫‪0.500‬‬
‫‪0.0360‬‬
‫‪4‬‬
‫‪4‬‬
‫‪0.250‬‬
‫‪0.4428‬‬
‫‪11‬‬
‫‪10‬‬
‫‪0.100‬‬
‫‪8.6970‬‬
‫‪30‬‬
‫‪20‬‬
‫‪0.050‬‬
‫حل نشدنی‬
‫‪-‬‬
‫‪40‬‬
‫‪0.025‬‬
‫* در مورد ‪ ε =0.025‬؛ حمله فوق قادر به پیدا کردن کلید ها با این مقدار ‪ ε‬نبود‪ .‬زیرا الگوریتم‬
‫‪ Babai‬در این مورد برای پیدا کردن بردار نزدیک در لتیس شکست می خورد‪ .‬چرا که برای ‪p‬‬
‫‪ 160‬بیتی‪ ،‬تنها ‪ 4‬بیت مشخص شده است‪...‬‬
‫• فرض می کنیم بیت های مجهول ‪ yi‬متصل به هم نباشند‬
‫)اصطالً در بلوک های متفاوت هستند)‪:‬‬
‫می توانیم ‪ yi‬را به صورت زیر نمایش دهیم‬
‫‪d‬‬
‫‪d‬‬
‫‪d‬‬
‫‪ i , j 1 i , j‬‬
‫‪ij‬‬
‫'‬
‫‪y i  z i   y ij 2‬‬
‫‪;  y i , j  2 j 1‬‬
‫‪j 1‬‬
‫‪j 1‬‬
‫که تنها ‪ yij‬مجهول است‪.‬‬
‫به طور مثال اگر‪، yi=101xy010h1‬داریم‪:‬‬
‫‪6‬‬
‫‪7‬‬
‫‪8‬‬
‫‪9‬‬
‫‪+B‬‬
‫=‬
‫‪0‬‬
‫‪(mod‬‬
‫)‪p‬‬
‫در نتیجه معادله‬
‫)*)‪y i  20  2 h  22 0 23 ‬‬
‫تبدیل‪0‬به‪24 ‬‬
‫‪y y25i+A‬‬
‫‪ xiy‬‬
‫‪2‬‬
‫‪‬‬
‫‪2‬‬
‫‪‬‬
‫‪2‬‬
‫‪‬‬
‫‪0‬‬
‫‪‬‬
‫‪2‬‬
‫‪0‬‬
‫‪i‬‬
‫‪d‬‬
‫طوریکه‬
‫می شود‪ ،‬به‬
‫‪7‬‬
‫‪d‬‬
‫)‪z i ,1  u i , j z i , j  w i , j z 0, j v i  0 (mod p‬‬
‫) ‪ 2  2 (h )  2 (0 2  2 0 2  y  2  x  2  2‬‬
‫‪5‬‬
‫‪4‬‬
‫‪3‬‬
‫‪2‬‬
‫‪2‬‬
‫‪j 1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪j 2‬‬
‫‪ui,j,wi,j , vi Є{0,…,p-1} , i=1,2,…,n‬‬
‫قرار می دهیم‬
‫)تعداد بیت های مجهول ‪ yi‬در بلوک ‪j‬ام(‬
‫‪Zij:=2‬‬
‫تعریف می کنیم‬
‫در نتیجه‬
‫‪J‬‬
‫‪; J   Z i ,j‬‬
‫‪Z i ,j‬‬
‫‪1i  n‬‬
‫‪1 j d‬‬
‫‪Ji ,j ‬‬
‫‪1‬‬
‫‪p‬‬
‫‪i,j‬‬
‫‪Z‬‬
...‫حال نوبت به آن می رسد که نظریه مشبکه وارد عمل شود‬
B ‫ تولید شده توسط ماتریس‬L ‫ از مشبکه‬،‫برای حل این معادالت‬

Wt 
:‫استفاده می کنیم‬
 I d ( n 1)n

B 
U   M d ( n 1)d ( n 1) (Z)  D d ( n 1)d ( n 1)
 0


pI

n
 u1

U 
0

0

 ;u i
u n 
 u i ,1 
 
 
u 
 i ,d 
D  diag (J i ,0,..., J0,d , J1,2,..., J1,d , J n ,2,..., J n ,d , J1,1,..., J n ,1)
‫بردار غیر مشبکه ‪ v‬را در نظر می گیریم‪:‬‬
‫)‪v  (0,...,0,v 1J1,1,...,v n J n ,1‬‬
‫ای موجود‬xєZn+1 ‫ می توان نتیجه گرفت که‬zij‫ و‬L ‫با توجه به تعریف‬
xB-v=(z0,1 j0,1,…, zn,1 jn,1) ‫است که‬
:‫ داریم‬،‫ در نظر بگیریم‬ε>1/n+1 ‫حال اگر‬
p (1 )( n 1)  p

d ( n 1)

n
d ( n 1)
1
J
1
d ( n 1)
J 2  d (n 1)
J 
2
d ( n 1)
1
d ( n 1)
|| xB v ||2  d (n 1)
2
d ( n 1)
i 1
|| xB v || 
2
d ( n 1)

i 1
J2
:‫در نتیجه داریم‬
)1(
‫بنابر فرایند قسمت قبل‪ ،‬با به کارگیری نتایج الگوریتم ‪Babai‬‬
‫‪2‬‬
‫خواهیم داشت‬
‫‪2‬‬
‫)‪d ( n 1‬‬
‫(‪)2‬‬
‫‪|| w v ||  d (n 1)‬‬
‫در نتیجه یافتن بردار ‪ x‬معادل با حل مسئله تقریب ‪ CVP‬است که‬
‫الگوریتم ‪ Babai‬قادر به حل آن می باشد‪.‬‬
‫با مقایسه نامساوی های )‪ )1‬و )‪ )2‬و همچنین از آنجا که‬
‫تعداد نقاط نزدیک به ‪ v‬در مشبکه زیاد نیست‪ ،‬می توان‬
‫امیدوار بود که بردار ‪ xA‬همان بردار نزدیک به ‪ v‬در‬
‫مشبکه )‪ L(B‬می باشد‪...‬‬
‫نتایج تجربی‬
‫میانگین زمان به‬
‫ثانیه‬
‫مقدار دقیق ‪n‬‬
‫‪1/ε‬‬
‫‪ε‬‬
‫‪d‬‬
‫‪0.067‬‬
‫‪2‬‬
‫‪2‬‬
‫‪0.500‬‬
‫‪2‬‬
‫‪0.304‬‬
‫‪2‬‬
‫‪2‬‬
‫‪0.500‬‬
‫‪4‬‬
‫‪1.135‬‬
‫‪2‬‬
‫‪2‬‬
‫‪0.500‬‬
‫‪8‬‬
‫‪2‬‬
‫‪0.500‬‬
‫‪16‬‬
‫‪0.393‬‬
‫‪4‬‬
‫‪4‬‬
‫‪0.250‬‬
‫‪2‬‬
‫‪1.785‬‬
‫‪4‬‬
‫‪4‬‬
‫‪0.250‬‬
‫‪4‬‬
‫‪4‬‬
‫‪0.250‬‬
‫‪8‬‬
‫‪10‬‬
‫‪0.100‬‬
‫‪2‬‬
‫حل نشدنی‬
‫‪10‬‬
‫‪0.100‬‬
‫‪4‬‬
‫حل نشدنی‬
‫‪20‬‬
‫‪0.050‬‬
‫‪2‬‬
‫حل نشدنی‬
‫حل نشدنی‬
‫‪6.256‬‬
‫‪12‬‬
‫مشاهده می شود با کاهش ‪) ε‬نسبت تعداد بیت های معلوم)‪،‬‬
‫باید تعداد بلوک ها کاهش داده شود؛در غیر این‬
‫صورت ماتریس ها بزرگ و بزرگ تر می شوند و‬
‫زمان اجرای الگوریتم افزایش می یابد‪...‬‬
‫با تشکر از توجه شما‬

similar documents