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

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

הפרוטוקול

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

דוגמה להמחשה

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

מקורות

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