הוכחה באפס ידיעה – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
שורה 56:
בפרוטוקול משתתפים פגי (המוכיחה) וויקטור (המוודא). פגי בוחרת בסוד שני ראשוניים אקראיים <math>p</math> ו-<math>q</math> ומפרסמת את המכפלה שלהם <math>N=pq</math>. המשימה של פגי היא להוכיח לויקטור ששלם מסוים <math>y</math> הוא [[מספר ריבועי]] מודולו <math>N</math> מבלי לחשוף בפניו כל מידע שיעזור לו להוכיח לאחרים ש-<math>y</math> ריבועי מודולו <math>N</math>. יש לזכור ש[[הוצאת שורש ריבועי#הוצאת שורש מודולרית|הוצאת שורש ריבועי]] מודולו שלם פריק <math>N</math> היא בעיה מתמטית קשה. אך כיוון שפגי יודעת מהם הגורמים הראשוניים של <math>N</math> והוצאת שורש ריבועי מודלו מספר ראשוני קלה, ביכולתה למצוא בקלות [[שורש ריבועי]] מודולרי של כל שלם מודולו <math>N</math> על ידי [[משפט השאריות הסיני]], נניח שקיים <math>x</math> המקיים:
:<math>x^2\equiv y\text{ (mod }N)</math>.
ואת זה מעוניינת פגי להוכיח לויקטור מבלי לחשוף את <math>x</math> (במקרה זה <math>x</math> הוא הסיסמה הסודית של פגי). היא מוכיחה זאת באמצעות פרוטוקול המבוצע בכמה סבבים של חילופי מסרים שבסופם ויקטור יקבל או לא יקבל את טענתה. בכל סבב מתבצעים המהלכים הבאים:
1. פגי בוחרת שלם אקראי <math>r</math> מודולו <math>N</math>. היא מחשבת ושולחת לויקטור את השלם <math>s\equiv r^2\text{ (mod }N)</math>.
| |||