פרוטוקול פייגה-פיאט-שמיר

בקריפטוגרפיה, שיטת פייגה-פיאט-שמיר (Feige-Fiat-Shamir) בקיצור FFS היא סוג של פרוטוקול הוכחת אפס ידע מקבילי שפותח על ידי אוריאל פייגה, עמוס פיאט ועדי שמיר ב-1988, לצורך אימות זהויות ברשת במקום שיטת האימות הקונבנציונלית באמצעות סיסמה. ככל הוכחה באפס ידע, פרוטוקול פייגה-פיאט-שמיר מאפשר למשתתף אחד להוכיח בפני המשתתף האחר ידיעת סוד מבלי הצורך לחשוף בפניו אף לא רמז קל בנוגע לסוד עצמו שלא ניתן היה להשיג באמצעים אחרים. גרסה דומה של הפרוטוקול מתאימה גם לצורך חתימה דיגיטלית.

פרוטוקול פייגה-פיאט-שמיר הוא הרחבה של פרוטוקול פיאט-שמיר הבסיסי^[1] שפיתחו ב-1986 המיישם את רעיון אפס ידע ומשתמש בקושי המשוער שבמציאת שורש ריבועי מודולו שלם פריק, כאשר גורמיו הראשוניים אינם יודעים, שהיא כידוע בעיה מתמטית קשה. השימוש בבעיה זו כבסיס לפרוטוקול אימות כבר עלה כשנתיים קודם לכן על ידי פישר, מכלי ורקוף ביורוקריפט 84^[2], אולם פרוטוקול פיאט-שמיר משופר יותר. חסרונו היחידי הוא בכך שבכל סבב מועברת סיבית אתגר אחת בלבד, מסיבה זו כדי להגיע לרמת בטיחות סבירה יש צורך במספר גדול מאד של סבבים, מה שהופך את האלגוריתם ללא יעיל. לעומתו פרוטוקול זה משתמש במחרוזת סיביות אתגר בו זמנית בכל סבב ועל כן יעיל יותר.

פרוטוקול פייגה-פיאט-שמיר מתאים לשימוש כאמצעי לאימות זהויות המוטמע בכרטיס חכם או כל מתקן נייד אחר המכיל מעבד קטן שמסוגל לבצע חישובים בהיקף מצומצם. למרות שהפרוטוקול משתמש באריתמטיקה מודולרית צורך משאבי מחשוב קטנים יחסית ל-RSA ומתאים למימוש במתקנים ניידים.

הפרוטוקול

פרוטוקול פייגה-פיאט-שמיר הוא מערכת הוכחה אינטראקטיבית, כלומר מהלכי הפרוטוקול המתוארים מבוצעים במספר סבבים, בהם המוכיח שולח הוכחה כלשהי למוודא, זה בתורו מחזיר אתגר אקראי למוכיח והאחרון משיב לאתגר במתן מענה נכון התלוי בסודו. באמצעות המידע הפומבי, ההוכחה והמענה לאתגר שקיבל, המוודא מסוגל להשתכנע כי המוכיח מחזיק בסוד הידוע רק לו ובשום שלב אין המוכיח נדרש לחשוף מאומה מהסוד. היות שמהלכי הפרוטוקול כוללים שימוש במספרים אקראיים, לא ניתן להעתיק את מהלכי הפרוטוקול לצורך אימות עתידי ללא ידיעת הסוד, רק מי שבידיו הסוד המתאים יוכל לענות על כל אתגר שיוצב לו נכונה.

תהליך הכנה חד פעמי

במערכת אימות זהויות מעשית הלקוח A מגיש בקשת התחברות לשרת B ומנסה לאמת את זהותו מולו על ידי הוכחת ידיעת הסיסמה מבלי לחשוף את הסיסמה עצמה. לשם כך מסתייעים בצד שלישי נאמן (נקרא גם רשות מאשרת), הלקוח רושם מפתח פומבי מתאים אצל הצד השלישי בעזרתו השרת מסוגל לאמת את זהות הלקוח. על כן ההנחה היא שהמפתח הפומבי של הלקוח מאומת ומשויך לו באמצעים מקובלים כמו תעודת מפתח פומבי החתומה על ידי רשות מאשרת, כך שהשרת B יוכל להשיג את המידע הציבורי הדרוש לצורך הפרוטוקול, באופן בטוח. לצורך הכנה חד-פעמית:

בוחרים שלם פריק הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} שהוא כפולה של שני מספרים ראשוניים גדולים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p} ו- $\ q$ השקולים ל-3 (מודולו 4), עקב כך מספרים אילו מכונים מספרי בלום (Blum integer) וכן המספר $\ -1$ אינו שארית ריבועית מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} כלומר שלו סימן יעקובי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \left( \frac{-1}{n} \right)=+1} . המודולוס הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} יהיה ציבורי ויירשם אצל הצד השלישי וכמו כן צריך להיות גדול דיו כדי לסכל ניסיון לפרקו לגורמים.
בוחרים שלמים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t} ו- $\ k$ המשמשים כפרמטרים של בטיחות (ראה בטיחות).

בחירת סוד פרטי

כחלק מתהליך ההכנה, כל משתמש פועל כדלהלן:

בוחר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k} שלמים אקראיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s_1,s_2,...,s_k} בטווח הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ [1,n-1]} וכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k} סיביות אקראיות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ b_1,b_2,...,b_k} (כמובן שצריך להתקיים $\ {\mbox{gcd}}(s_{i},n)=1$ , אולם כמעט בטוח שדרישה זו לא תופר לעולם כיוון שמשמעות הדבר שנמצא גורם ראשוני של המודולוס מה שלא סביר שיקרה).
מחשב את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ v_i=(-1)^{b_i}\cdot (s^2_i)^{-1}\mbox{ mod }n} עבור כל השלמים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s_i} (באופן זה מבטיחים ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ v} משתרע על פני כל השלמים מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} וכן כל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ v_i} זר ל- $\ n$ ובעל סימן יעקובי 1, דרישה זו הכרחית כדי להבטיח שלא ייחשף כל מידע בנוגע לסוד).
המפתח הציבורי יהיה הווקטור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ v_1,v_2,...,v_k} אותו המשתמש רושם אצל הצד השלישי. המפתח הפרטי הוא הווקטור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s_1,s_2,...,s_k} ומשמש כסודו של A.

מהלכי הפרוטוקול

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \rarr B} : הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x = \pm r^{2}\mbox{ mod }n}
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \larr B} : הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle \ e_{1},e_{2},...,e_{k},(e\in \{0,1\})}
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \rarr B} : הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y=r\cdot \prod_{e_{j=1}} s_j^{e_j} \mbox{ mod }n}

פירוט המהלכים

מהלכי הפרוטוקול מבוצעים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t} פעמים כדלהלן:

A בוחר מספר אקראי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ r} בטווח הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ [1,n-1]} וסיבית אקראית אחת $\ b$ ומחשב את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x=(-1)^b\cdot r^2\mbox{ mod }n} ושולח את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x} הנקרא הוכחה ל-B.
B שולח ל-A את האתגר שהוא וקטור סיביות אקראי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ e_1,e_2,...,e_k} .
A מחשב את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y=rs_1^{e_1}s_2^{e_2}\cdot\cdot\cdot s_k^{e_k} \mbox{ mod }n} (כלומר כפולה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ r} בכל השלמים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s_j} אשר מקבילים ל-1 בוקטור האתגר) ושולח את המענה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y} ל-B.
B מחשב את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ z=y^2\cdot \prod_{j=1}^k v_j^{e_j}\mbox{ mod }n} ומוודא ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ z=\pm x} וכן ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ z\ne 0} .

אם בכל $\ t$ הסבבים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ z=\pm x} כנדרש, B יכול לקבל את הוכחת הזהות של A ולא, ההוכחה תדחה.

דוגמה להמחשה

נתון המודולוס הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n=631\cdot 983=620273} והפרמטרים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t=1,k=4} . להכנה המשתמש A בוחר 4 שלמים אקראיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s_1=5586,s_2=12546,s_3=1819,s_4=11777} המשמשים כמפתח פרטי וכן וקטור סיביות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ b_1=0,b_2=0,b_3=0,b_4=1} ומחשב את המפתח הפומבי: הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle \ v_{1}=587652,v_{2}=370139,v_{3}=537354,v_{4}=109516}

לצורך אימות מול B המשתמש A בחר מספר אקראי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 5506} וסיבית אחת, נניח הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 0} ומחשב את ההוכחה: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 5506^2\mbox{ mod }620273=542932} ושולח את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 542932} לשרת. השרת מייצר רצף סיביות אתגר אקראי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (0,0,1,0)} ושולח למשתמש. המשתמש בתורו מחשב את $\ 5506\cdot 1819{\mbox{ mod }}620273=91046$ (רק הסיבית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ e_3=1} לכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s_3} נכלל בחישוב) ושולח בחזרה לשרת את המענה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 91046} . מה שנותר לשרת כדי לאמת את זהותו זה לבדוק האם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 91046^2\cdot 537354\mbox{ mod }620273=542932} כיוון שזהו אכן המקרה ההוכחה מתקבלת.

אם A מתחזה ואין לו שמץ של מושג לגבי הסוד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s} . הוא יכול לרמות רק אם ידע מראש מה תהיה מחרוזת סיביות האתגר שהשרת ישלח לו. במקרה כזה הוא יכול פשוט לקבוע את: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x = r^2\cdot \prod_{i=1}^k v_i^{e_i}} ואז המענה יהיה תמיד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y=r} . עבור כל סיבית סיכוייו לרמות הם חצי ובסך הכול סיכוייו הם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 2^{-k}} עבור סבב בודד.

קל יותר להבין את הרעיון עם סיבית אתגר בודדת. אם נתייחס רק לסיבית הראשונה המקבילה ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ v_1=587652} , נניח שהמתחזה ישלח לשרת את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x=r^2\cdot v_1} הוא יצליח לענות תשובה נכונה רק אם סיבית האתגר שיקבל תהיה 1 כיוון שאז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y^2\cdot v_1 \equiv x\mbox{ (mod }n)} אולם תהיה לו בעיה עם סיבית 0 כי אז יהיה עליו לחשב את השורש הריבועי של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ r^2\cdot v_1\mbox{ mod }n} . ולפי הדוגמה המובאת לעיל, אם המתחזה יבחר מספר אקראי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ r=1234} למשל וישלח לשרת את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x=1234^2\cdot v_1\mbox{ mod }620273=119456} , קל לראות שאם סיבית האתגר היא 1 המענה הנכון הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y=1234} אולם אם סיבית האתגר תהיה 0 המענה צריך להיות השורש הריבועי של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 119456} כיוון ש: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 149683^2\equiv 119456\mbox{ (mod }620273)} הרי שהמענה הנכון הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y=149683} . מכיוון שהדוגמה המובאת כאן היא במספרים קטנים, קל כמובן למצוא שורש ריבועי בסדר גודל כזה, במיוחד אם הגורמים הראשוניים ידועים. אולם במספרים גדולים חישוב שורש ריבועי ללא ידיעת הגורמים הראשוניים הופך לבעיה מאד קשה, על כן המתחזה יכשל.

בטיחות

בעיית מציאת שורש ריבועי של שלם פריק שקולה לבעיית פירוק לגורמים, לא ידוע על דרך יעילה לחישוב שורש ריבועי מודולרי ללא הגורמים הראשוניים. לכן בטיחות האלגוריתם נשענת על הקושי שבפירוק לגורמים. כדי שהפרוטוקול יהיה בטוח כמובן יש צורך להבטיח שלא ניתן יהיה לפרק את המודולוס לגורמים עם מיטב האלגוריתמים הידועים. ההנחה היא כיום שמודולוס בגודל 2048 סיביות רחוק מהישג יד של היכולת הטכנולוגית הנוכחית.
הפרמטרים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t} מספקים מדד יעילות ובטיחות של הפרוטוקול. הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k} גדול משפיע על סיבוכיות הפרוטוקול (כמות העבודה) ואילו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t} גדול משפיע על התקשורת (היקף התעבורה). מצד המוכיח עדיף הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t} קטן יותר כי הוא חושף פחות מידע, בעוד שהמאמת לעומת זאת מעדיף הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t} גדול. אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t=1} (כלומר הפרוטוקול מבוצע בסבב אחד) ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k} גדול יותר ניתן להגיע לביצועים טובים יותר על חשבון בטיחות, במקרה כזה הפרוטוקול לא יקרא הוכחה באפס ידע כיוון שאינו נאות לפי ההגדרה. אולם מבחינה מעשית לנאותות יש חשיבות מועטה. כיוון שהמושג אפס ידע תאורטי במהותו, כשזה נוגע להיבטים פרקטיים לעיתים מסתפקים ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t=1} .
בהנחה שפירוק לגורמים היא בעיה קשה, ההתקפה הטובה ביותר כנגד הפרוטוקול - התקפת טקסט-מוצפן-נבחר היא בעלת סיבוכיות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 2^{-kt}} כך שמהיבט של בטיחות רצוי ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ kt} יהיה גדול כדי לסכל התקפה כזו, אולם מהיבט של יעילות רצוי שלא יהיה גדול מדי. במקרים בהם קיימת הגנה נוספת (כגון אם תהליך אימות מצריך נוכחות פיזית של המאמת או במקרים בהם קיימת הגבלה של מספר ניסיונות האימות האפשריים בפרק זמן נתון) הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k=6, t=5} מספקים רמה של בטיחות טובה (הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 2^{-30}} ).

שיפורים

בהתאם לצורך או לדרישות בטיחות, ניתן לממש את הפרוטוקול עם מודולוס נפרד לכל משתמש כשהגורמים הראשוניים ידועים רק לו. או באמצעות מודולוס משותף למספר משתתפים שגורמיו הראשוניים ידועים רק לשרת הצד-השלישי והוא אחראי להפקת מפתח פומבי ומפתח פרטי מתאים לכל משתמש.
במקום לשלוח את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x} במהלך הראשון לעיל, המשתתף A יכול לשלוח ערך גיבוב שלו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ h(x)} בכך ניתן לצמצם מעט את היקף התעבורה.
ניתן ליישם את הפרוטוקול באופן שהוא יקרא מבוסס זהות. פרוטוקול אימות מבוסס זהות הנו פרוטוקול שבו המפתח הפומבי של המוכיח הוא פונקציה של פרטי זהותו הפומביים כמו שם פרטי, מספר תעודת זהות, כתובת וכדומה. במקרה כזה הצד השלישי, אחראי להפקת מפתחות פומביים עבור כל המשתמשים באמצעות פונקציה מוסכמת ומתוכם הוא מפיק את המפתחות הפרטיים המתאימים על ידי חישוב השורשים הריבועיים שלהם ושולח אותם לכל המשתמשים (כאמור חישוב השורשים הריבועיים אפשרי רק בידיעת הגורמים הראשוניים).
ניתן ליישם את מהלכי הפרוטוקול באופן מקבילי, כלומר במקום שהפרוטוקול יבוצע $\ t$ פעמים, המוכיח והמאמת יכולים לשלוח זה לזה את כל האתגרים וההוכחות בו זמנית. למרות שהפרוטוקול במקרה כזה לא ייקרא הוכחה באפס ידע, יש בו תועלת להפחתת הסיכוי כנגד זיוף וניתן להוכיח כי הוא בטוח. למעשה שיטת חתימה דיגיטלית של פייגה-פיאט-שמיר פועלת על עקרון זה כאשר במקום וקטור אתגר אקראי החותם משתמש בערך הגיבוב של המסר המיועד לחתימה.

מקורות

הספר Handbook of Applied Cryptography פרק 10.

הערות שוליים

^ A. Fiat and A. Shamir, "How to prove yourself: Practical solutions to identification and signature problems", Advances in Cryptology–CRYPTO ’86 (LNCS 263), 186–194, 1987.
^ M. Fischer, S. Micali, and C. Rackoff, "A secure protocol for oblivious transfer", unpublished, הוצג ב- Eurocrypt '84

[1] A. Fiat and A. Shamir, "How to prove yourself: Practical solutions to identification and signature problems", Advances in Cryptology–CRYPTO ’86 (LNCS 263), 186–194, 1987.

[2] M. Fischer, S. Micali, and C. Rackoff, "A secure protocol for oblivious transfer", unpublished, הוצג ב- Eurocrypt '84

[1]

[2]