1
مفاهیم و کاربردهای عملی دانایی صفر (Zero–knowledge)
2
مقدمه
یک اثبات کننده(P) سعی می کند تصدیق کننده (V) را متقاعدکند که ادعایش صحیح است. در حالت عادی، P در یک ارتباط یک سری اطلاعات به V می دهد و V با محاسباتی صحت ادعای P را تاییدمی کند.
آیا می توان بدون انتقال اطلاعات اضافی، V را متقاعد نمود؟
آیا می توان پیام های بیشتری ردوبدل کرد و در عین حال اطلاعات اضافه منتقل نشود؟
آیا می توان با درنظر گرفتن احتمال خطای غیرصفر و با انتقال اطلاعات کم و کافی V را راضی نمود؟
3
تعریف دانایی صفر
در یک اثبات هنگامی که منظور اصلی بدون هیچ اطلاعات اضافی منتقل شود (واقعیتی برطرف مقابل آشکار شود) آنگاه اثبات با دانایی صفرنامیده می شود.
در این نوع اثبات V متقاعد می شود که P صاحب اطلاعاتی است، اما به هیچ طریقی نمی تواند این اطلاعات را استخراج کند.
در یک پروتکل دانایی – صفر می توان کارهایی از قبیل شناسایی، اثبات یک واقعیت یا عملیات دیگر رمزنگاری را، بدون فاش کردن اطلاعات محرمانه در هنگام برقراری ارتباط، انجام داد.
4
غاردانایی صفر
کسی که کلمه رمز در انتهایی غار را بداند، می تواند از نقطه C به نقطه D برسد و برعکس. فرض کنیم P کلمه رمز را می داند و می خواهد این آگاهی را به V بفهماند، اما نمی خواهد کلمه رمز را بازگو نماید.
5
V در نقطه A می ایستد
P وارد غار می شود وبه هرکدام از مسیرها که مایل باشد، می رود.
هنگامی که P در غار ناپدید شد، V به نقطه B می آید
V باصدازدنPازاومی خواهد که :
از مسیر سمت راست بازگردد
از مسیر سمت چپ بازگردد
Pاین خواسته Vرابرآورده می کند.
درصورت نیازکلمه رابه زبان می آورد واز در انتهایی غار می گذرد
Pو Vمراحل فوق را nبارتکرار می کنند
6
حل یک مسئله ی دشوار(1)
فرض کنیدPحل یک مسئله دشوار را می داند. برای اثبات این آگاهی به صورت زیر عمل می نماید:
P با استفاده از اطلاعاتش و با انتخاب یک عدد تصادفی مسئله دشوار را به یک مسئله دشوار جدید تبدیل می کند.
این مسئله جدید باید هم شکل Isomorphicمسئله اول باشد.
سپس با استفاده از اطلاعاتش و آن عدد تصادفی مسئله جدید را حل می کند.
7
حل یک مسئله ی دشوار(2)
P مسئله جدید را برای V ارسال می کند.
V از P می خواهد که یکی از دو کار زیر را انجام دهد:
ثابت کند که مسئله اول و مسئله جدید هم شکل هستند
جواب مسئله جدید را بیان کند و نشان دهد که حل آن است
P موافقت می کند و انجام می دهد
مراحل فوق را n بار تکرارکنند
8
نکات پروتکل حل یک مسئله دشوار
در این الگوریتم P هیچ گاه نباید برای مسئله دشوار جدیدی که به دست می آورد هر دو درخواست بند (5) را پاسخ دهد.
تبدیل های تصادفی و مسئله ها نیز باید به گونه مناسبی انتخاب شوند تا V اطلاعاتی برای حل مسئله اصلی به دست نیاورد.
همه مسایل دشوار برای این کاربرد مناسب نیستند. اما تعداد زیادی از این مسایل می توانند استفاده شوند.
9
ویژگی های پروتکل دانایی صفر
تصدیق کننده هیچ معلوماتی از پروتکل به دست نمی آورد:
تصدیق کننده با اتکا به خودش نمی تواند مراحل پروتکل را طی کند و به کنش و واکنش اثبات کننده نیاز دارد. پروتکل هیچ اطلاعات محرمانه ای را فاش نمی کند، در غیر این صورت پروتکل را با حداقل افشاسازی می نامند.
اثبات کننده نمی تواند تصدیق کننده را فریب دهد:
باتکرارپروتکل احتمال موفقیت اثبات کننده متقلب رامی توان به اندازه دلخواه کاهش داد.دراین پروتکل ها با اولین اشتباه اثبات کننده می توان اثبات کننده متقلب را شناسایی کرد.
تصدیق کننده نمی تواند اثبات کننده را فریب دهد:
تصدیق کننده نمی تواند از اطلاعات اثبات کننده آگاهی یابد.
تصدیق کننده نمی تواند خودرابه عنوان اثبات کننده برای شخص سومی معرفی کند:
تصدیق کننده حتی نمی تواندبه شخص سومی اثبات کندکه اثبات کننده دارای اطلاعات سری است.
10
روش های استفاده از پروتکل های دانایی صفر (1)
برای استفاده از پروتکل های دانایی صفر به سه طریق زیر می توان عمل نمود:
موازی:
به نحوی که P تعدادی مسئله تدوین می کند و برای V می فرستد. آن گاه V درخواست های مربوط به هر مسئله را به صورت یک جا برای P می فرستد. بدین صورت از تعداد ردوبدل پیام در مواردی که برقرار ارتباط با تاخیر همراه است، کاسته می شود.
11
روش های استفاده از پروتکل های دانایی صفر(2)
تاثیر متقابل:
که در آن P و V با ردوبدل متوانی پیام هایی مسیر پروتکل را دنبال می کنند. دراین حالت اثبات به صورت قسمت به قسمت محقق می شود.
زمان غیر واقعی:
در این حالت یک تابع درهم یک طرفه برروی مسئله ها و داده ها نقش V را بازی می کند و برای امضای دیجیتال مورد استفاده قرار می گیرد.
12
امنیت پروتکل های دانایی صفر
امنیت پروتکل های دانایی صفر معمولاً بر چند مسئله "سخت برای حل" تکیه دارد. مهمترین آنها عبارتنداز:
مسئله به دست آوردن لگاریتم گسسته (در هنگ n) یک عدد بزرگ (صدها بیت)
مسئله آگاه شدن از این که یک عدد در هنگ n مربع کامل است، به شرط این که از عامل های اول آن عدد بی خبر باشیم
مسئله تجزیه یک عدد بزرگ که حاصل ضرب دو یا چند عدد اول بزرگ (صدها بیت) است
13
اثبات دانایی
اگرpبخواهد برای Vاثبات کند که ازمقدارxکه درمعادله Ax B(mod p)
(p اول،A،Bوp معلوم )صدق می کند،آگاه است،به صوت زیرعمل می نماید:
Pعددr کوچکترازp-1 است را انتخاب و h=Ar را محاسبه می کند
سپس h را برای V ارسال می نماید
V یک بیت تصادفی b را برای P ارسال می کند
P مقدار s=r+bx (mod p-1)رامحاسبه می کندوبرای V می فرستد
رابطه As=hBb ار محاسبه و تاییدمی کند
مراحل فوق را t بار تکرارمی کنند
در این پروتکل شانس موفقیت برای اثبات کننده متقلب 2-t می باشد
14
اثبات هویتFeige-Fiat-Shamir
ابتدا یک داور یا میانجی عدد بزرگ n را که حاصل ضرب دو عدد اول بزرگ است انتخاب می کند.
کلید عمومی اثبات کننده که با vنمایش داده می شود، به نحوی انتخاب می شود که x2=v mod n (باقیمانده یک مربع کامل درهنگ n) و نیز معکوس v درهنگ n موجود باشد.
کلید خصوصی اثبات کننده، s، را به صورت کوچکترین عدد که S=sqrt(v-1) mod n تعیین می کند
15
اثبات هویت Feige-Fiat-Shamir
اثبات کننده عدد دلخواه r کوچکتراز n را انتخاب می کند.
سپس x= r2 mod n را محاسبه و مقدار x را برای تصدیق کننده ارسال می نماید.
تصدیق کننده یک بیت تصادفی bبرای اثبات کننده می فرستد
اگر b=0 بود اثبات کننده مقدار r و در صورتی که b=1 بود، مقدار y=rs mod n را ارسال می کند
16
اثبات هویت Feige-Fiat-Shamir
اگرb=0 باشد، تصدق کننده درستی عبارت x= r2 mod n را امتحان می کند تا مطئن شود که اثبات کننده از Sprt(x) باخبر است.
اگرb=1 باشدتصدق کننده درستی عبارت x= y2v mod n را برای اطمینان از این که اثبات کننده Sprt(xv-1) را می داند، امتحان می کند
این مراحل t بار تکرار می شود تا تصدق کننده راضی شود که اثبات کننده از s باخبر است
17
امضای دیجیتال
در اثبات هویت Feige-Fiat-Shamir اگر تصدیق کننده را با یک تابع درهم یک طرفه جایگزین کنیم، به صورتی که خروجی این تابع حالت انتخابی در بند 5 و 6 پروتکل را تعیین کند، آنگاه پروتکل امضای دیجیتال مربوطه حاصل می شود.
در این حالت تصدیق کننده نهایی مقادیر خروجی تابع درهم یک طرفه و همچنین صحت تساوی های پروتکل را بازرسی می کند.
18
مقایسه سه پروتکل
19
کارت های هوشمند
یک کارت هوشمند یک سیستم حافظه دار قابل حمل و نقل می باشد، که امکان معرفی و اثبات هویت، انتقال اطلاعات محرمانه، اثبات آگاهی از مطالب سری و غیره را دارد.
این کارت در حقیقت یک ریزپردازنده ی تک چیپ می باشد.
استفاده از دانایی صفر در کارت هوشمند در حال افزایش می باشد.
20
امنیت کارت های باهوش
روش های ساده: با اعمال یک ولتاژ غیراستاندارد فیوزهای محافظ اطلاعات پاک می شوند
روش های تخصصی ولی ارزان:با ردیابی مغناطیسی جریان ها در یک چیپ در حال کار
روش های گران قیمت ولی کارآمد:با شستن لایه به لایه چیپ با اسید
پروتکلها واطلاعات کارت هوشمند به روشهای زیرقابل دسترسی می باشد:
21
نتیجه گیری
دانایی صفر روش مفیدی برای متقاعدکردن طرف مقابل، بدون انتقال اطلاعات محرمانه است.
این روش کار، استفاده های متعددی در عمل رمزنگاری می تواند داشته باشد، دارای امنیت محاسباتی خوبی می باشد.
دانایی صفر همواره با ردوبدل پیام (حداقل یک رفت و برگشت برای هر طرف) همراه است.
22
نتیجه گیری
برای تحقق دانایی صفر، پروتکل های مختلفی قابل استفاه اند که همگی برمسایل دشواری استوار هستند.
پروتکل های تئوری معمولاً محاسبات سنگینی احتیاج دارند، لذا برای پیاده سازی این پروتکل ها در عمل، باید مقدار محاسبات را کاهش داد.
یکی از کاربردهای دانایی صفر در عمل، استفاده آن در کارت های هوشمند می باشد. برای این منظور باید پروتکل ها را به نحوی مناسب طراحی کرد.
23
نتیجه گیری
استفاده از این کارت ها باید با ریزبینی در ارتباط با مسایل امنیتی همراه باشد.
باتوجه به حجم محاسباتی کمتر دانایی صفر در مقایسه با کلید عمومی، انتظار می رود که استفاده از آن به خصوص در سیستم های محدود بیشتر موردتوجه قرار گیرد. لذا این مقوله جای کار فراوان دارد.