مفاهیم و کاربردهای عملی دانایی صفر

مفاهیم و کاربردهای عملی دانایی صفر

اسلاید 1: 1مفاهیم و کاربردهای عملی دانایی‌صفر (Zero–knowledge)سید مهدی محمد حسن زادهHasanzadeh@Raymandcrypto.irشرکت صنایع الکترونیک زعیم زمستان 1383

اسلاید 2: 2مقدمهیک اثبات‌کننده(P) سعی‌می‌کند تصدیق‌کننده (V) را متقاعدکند که ادعایش صحیح است. در حالت عادی، P در یک ارتباط یک سری اطلاعات به V می‌دهد و V با محاسباتی صحت ادعای P را تاییدمی‌کند.آیا می‌توان بدون انتقال اطلاعات اضافی، V را متقاعد نمود؟آیا می‌توان پیام‌های بیشتری ردوبدل‌کرد و در عین حال اطلاعات اضافه منتقل نشود؟ آیا می‌توان با درنظر گرفتن احتمال خطای غیرصفر و با انتقال اطلاعات کم و کافی V را راضی نمود؟

اسلاید 3: 3تعریف دانایی صفردر یک اثبات هنگامی که منظور اصلی بدون هیچ اطلاعات اضافی منتقل شود (واقعیتی برطرف مقابل آشکار شود) آنگاه اثبات با دانایی صفرنامیده می‌شود. در این نوع اثبات V متقاعد می‌شود که P صاحب اطلاعاتی است، اما به‌هیچ طریقی نمی‌تواند این اطلاعات را استخراج کند. در یک پروتکل دانایی – صفر می‌توان کارهایی از قبیل شناسایی، اثبات یک واقعیت یا عملیات دیگر رمزنگاری را، بدون فاش‌کردن اطلاعات محرمانه در هنگام برقراری ارتباط، انجام داد.

اسلاید 4: 4غاردانایی صفر کسی که کلمه‌ رمز در انتهایی غار را بداند، می‌تواند از نقطه C به نقطه D برسد و برعکس. فرض‌کنیم P کلمه‌ رمز را می‌داند و می‌خواهد این آگاهی را به V بفهماند، اما نمی‌خواهد کلمه‌ رمز را بازگو نماید.

اسلاید 5: 5V در نقطه A می‌ایستدP وارد غار می‌شود وبه هرکدام از مسیرها که مایل باشد، می‌رود. هنگامی که P در غار ناپدید شد، V به نقطه B می‌آیدV باصدازدنPازاومی‌خواهد که :از مسیر سمت راست بازگردداز مسیر سمت چپ بازگرددPاین خواسته‌ Vرابرآورده ‌می‌کند. درصورت نیازکلمه رابه ‌زبان می‌آورد واز در انتهایی غار می‌گذردPو Vمراحل فوق را nبارتکرار می‌کنند

اسلاید 6: 6حل یک مسئله‌ی دشوار(1) فرض‌کنیدPحل یک مسئله‌ دشوار را می‌داند. برای اثبات این آگاهی به‌صورت ‌زیر عمل می‌نماید:P با استفاده از اطلاعاتش و با انتخاب یک عدد تصادفی مسئله‌ دشوار را به یک مسئله‌ دشوار جدید تبدیل‌می‌کند. این مسئله‌ جدید باید هم شکل Isomorphicمسئله اول باشد. سپس با استفاده از اطلاعاتش و آن عدد تصادفی مسئله‌ جدید را حل‌می‌کند.

اسلاید 7: 7حل یک مسئله‌ی دشوار(2)P مسئله‌ جدید را برای V ارسال‌می‌کند. V از P می‌خواهد که یکی از دو کار زیر را انجام دهد: ثابت‌کند که مسئله‌ اول و مسئله‌ جدید هم‌شکل هستندجواب مسئله جدید را بیان‌کند و نشان دهد که حل آن استP موافقت‌می‌کند و انجام می‌دهدمراحل فوق را n بار تکرارکنند

اسلاید 8: 8نکات پروتکل حل یک مسئله‌ دشواردر این الگوریتم P هیچ گاه نباید برای مسئله‌ دشوار جدیدی که به‌دست می‌آورد هر دو درخواست بند (5) را پاسخ دهد. تبدیل‌های تصادفی و مسئله‌ها نیز باید به‌گونه‌ مناسبی انتخاب شوند تا V اطلاعاتی برای حل مسئله‌ اصلی به‌دست نیاورد. همه‌ مسایل دشوار برای این کاربرد مناسب نیستند. اما تعداد زیادی از این مسایل می‌توانند استفاده شوند.

اسلاید 9: 9ویژگی‌های پروتکل دانایی صفر تصدیق‌کننده‌ هیچ معلوماتی از پروتکل به‌دست نمی‌آورد: تصدیق کننده با اتکا به خودش نمی تواند مراحل پروتکل را طی کند و به کنش و واکنش اثبات کننده نیاز دارد. پروتکل هیچ اطلاعات محرمانه ای را فاش نمی کند، در غیر این صورت پروتکل را با حداقل افشاسازی می نامند.اثبات‌کننده نمی‌تواند تصدیق کننده را فریب دهد: باتکرارپروتکل احتمال موفقیت اثبات‌کننده متقلب رامی توان به اندازه دلخواه کاهش داد.دراین پروتکل ها با اولین اشتباه اثبات‌کننده می توان اثبات‌کننده متقلب را شناسایی کرد.تصدیق‌کننده نمی‌تواند اثبات کننده را فریب دهد: تصدیق‌کننده نمی‌تواند از اطلاعات اثبات کننده آگاهی یابد.تصدیق‌کننده نمی‌تواند خودرابه‌عنوان اثبات کننده برای شخص سومی معرفی کند: تصدیق‌کننده حتی نمی‌تواندبه شخص سومی اثبات کندکه اثبات‌کننده دارای اطلاعات سری است.

اسلاید 10: 10روش های استفاده از پروتکل های دانایی صفر (1)برای استفاده از پروتکل‌های دانایی صفر به سه طریق زیر می‌توان عمل نمود:موازی: به‌نحوی که P تعدادی مسئله تدوین‌می‌کند و برای V می‌فرستد. آن‌گاه V درخواست‌های مربوط به هر مسئله را به‌صورت یک جا برای P می‌فرستد. بدین‌صورت از تعداد ردوبدل پیام در مواردی که برقرار ارتباط با تاخیر همراه است، کاسته می‌شود.

اسلاید 11: 11روش های استفاده از پروتکل های دانایی صفر(2)تاثیر متقابل: که در آن P و V با ردوبدل متوانی پیام‌هایی مسیر پروتکل را دنبال‌می‌کنند. دراین حالت اثبات به‌صورت قسمت‌به‌قسمت محقق می‌شود.زمان غیر واقعی: در این حالت یک تابع درهم یک‌طرفه برروی مسئله‌ها و داده‌ها نقش V را بازی‌می‌کند و برای امضای دیجیتال مورد استفاده قرار می گیرد.

اسلاید 12: 12امنیت پروتکل‌های دانایی صفر امنیت پروتکل‌های دانایی صفر معمولاً بر چند مسئله سخت برای حل تکیه دارد. مهمترین آنها عبارتنداز:مسئله‌ به‌دست آوردن لگاریتم گسسته‌ (در هنگ n) یک عدد بزرگ (صدها بیت)مسئله‌ آگاه شدن از این که یک عدد در هنگ n مربع کامل است، به‌شرط این که از عامل‌های اول آن عدد بی‌خبر باشیممسئله‌ تجزیه یک عدد بزرگ که حاصل‌ضرب دو یا چند عدد اول بزرگ (صدها بیت) است

اسلاید 13: 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: 14اثبات هویتFeige-Fiat-Shamir ابتدا یک داور یا میانجی عدد بزرگ n را که حاصل‌ ضرب دو عدد اول بزرگ است انتخاب‌می‌کند. کلید عمومی اثبات‌کننده که با vنمایش داده می‌شود، به ‌نحوی انتخاب می‌شود که x2=v mod n (باقیمانده یک مربع کامل درهنگ n) و نیز معکوس v درهنگ n موجود باشد. کلید خصوصی اثبات‌کننده، s، را به‌صورت کوچکترین عدد که S=sqrt(v-1) mod n تعیین‌می‌کند

اسلاید 15: 15اثبات هویت Feige-Fiat-Shamir اثبات‌کننده عدد دلخواه r کوچکتراز n را انتخاب‌می‌کند. سپس x= r2 mod n را محاسبه و مقدار x را برای تصدیق‌کننده ارسال می‌نماید.تصدیق‌کننده یک بیت تصادفی bبرای اثبات‌کننده می‌فرستداگر b=0 بود اثبات‌کننده مقدار r و در صورتی که b=1 بود، مقدار y=rs mod n را ارسال‌می‌کند

اسلاید 16: 16اثبات هویت Feige-Fiat-Shamirاگرb=0 باشد، تصدق‌کننده درستی عبارت x= r2 mod n را امتحان‌می‌کند تا مطئن شود که اثبات‌کننده از Sprt(x) باخبر است. اگرb=1 باشدتصدق‌کننده درستی عبارت x= y2v mod n را برای اطمینان از این‌ که اثبات‌کننده Sprt(xv-1) را می‌داند، امتحان‌می‌کنداین مراحل t بار تکرار می‌شود تا تصدق‌کننده راضی شود که اثبات‌کننده از s باخبر است

اسلاید 17: 17امضای دیجیتال در اثبات هویت Feige-Fiat-Shamir اگر تصدیق‌کننده را با یک تابع درهم یک‌طرفه جایگزین‌کنیم، به‌صورتی که خروجی این تابع حالت انتخابی در بند 5 و 6 پروتکل را تعیین‌کند، آنگاه پروتکل امضای دیجیتال مربوطه حاصل می‌شود. در این حالت تصدیق‌کننده نهایی مقادیر خروجی تابع درهم یک‌طرفه و همچنین صحت تساوی‌های پروتکل را بازرسی ‌می‌کند.

اسلاید 18: 18مقایسه سه پروتکل

اسلاید 19: 19کارت‌های هوشمند یک کارت هوشمند یک سیستم حافظه‌دار قابل حمل و نقل می‌باشد، که امکان معرفی و اثبات هویت، انتقال اطلاعات محرمانه، اثبات آگاهی از مطالب سری و غیره را دارد. این کارت در حقیقت یک ریزپردازنده‌ی تک‌چیپ می‌باشد.استفاده از دانایی صفر در کارت هوشمند در حال افزایش می باشد.

اسلاید 20: 20امنیت کارت‌های باهوش روش‌های ساده: با اعمال یک ولتاژ غیراستاندارد فیوزهای محافظ اطلاعات پاک می‌شوندروش‌های تخصصی ولی ارزان:با ردیابی مغناطیسی جریان‌ها در یک چیپ در حال کارروش‌های گران‌قیمت ولی کارآمد:با شستن لایه‌به‌لایه چیپ با اسیدپروتکلها واطلاعات کارت هوشمند به روشهای زیرقابل دسترسی می باشد:

اسلاید 21: 21نتیجه‌گیریدانایی صفر روش مفیدی برای متقاعدکردن طرف مقابل، بدون انتقال اطلاعات محرمانه است. این روش کار، استفاده‌های متعددی در عمل رمزنگاری می‌تواند داشته باشد، دارای امنیت محاسباتی خوبی می‌باشد. دانایی صفر همواره با ردوبدل پیام (حداقل یک رفت و برگشت برای هر طرف) همراه است.

اسلاید 22: 22نتیجه‌گیریبرای تحقق دانایی صفر، پروتکل‌های مختلفی قابل استفاه‌اند که همگی برمسایل دشواری استوار هستند. پروتکل‌های تئوری معمولاً محاسبات سنگینی احتیاج دارند، لذا برای پیاده‌سازی این پروتکل‌ها در عمل، باید مقدار محاسبات را کاهش‌داد. یکی از کاربردهای دانایی صفر در عمل، استفاده‌ آن در کارت‌های هوشمند می‌باشد. برای این منظور باید پروتکل‌ها را به‌نحوی مناسب طراحی‌کرد.

اسلاید 23: 23نتیجه‌گیریاستفاده از این کارت‌ها باید با ریزبینی در ارتباط با مسایل امنیتی همراه باشد. باتوجه به حجم محاسباتی کمتر دانایی صفر در مقایسه با کلید عمومی، انتظار می‌رود که استفاده از آن به‌خصوص در سیستم‌های محدود بیشتر موردتوجه قرار گیرد. لذا این مقوله جای کار فراوان دارد.