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

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

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

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

הפרוטוקול

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

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

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

• בוחרים שלם פריק ${\displaystyle \ n}$ שהוא כפולה של שני מספרים ראשוניים גדולים ${\displaystyle \ p}$ ו-${\displaystyle \ q}$ השקולים ל-3 (מודולו 4), עקב כך מספרים אילו מכונים מספרי בלום (Blum integer) וכן המספר ${\displaystyle \ -1}$ אינו שארית ריבועית מודולו ${\displaystyle \ n}$ כלומר שלו סימן יעקובי ${\displaystyle \ \left({\frac {-1}{n}}\right)=+1}$. המודולוס ${\displaystyle \ n}$ יהיה ציבורי ויירשם אצל הצד השלישי וכמו כן צריך להיות גדול דיו כדי לסכל ניסיון לפרקו לגורמים.
• בוחרים שלמים ${\displaystyle \ t}$ ו-${\displaystyle \ k}$ המשמשים כפרמטרים של בטיחות (ראה בטיחות).

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

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

• בוחר ${\displaystyle \ k}$ שלמים אקראיים ${\displaystyle \ s_{1},s_{2},...,s_{k}}$ בטווח ${\displaystyle \ [1,n-1]}$ וכן ${\displaystyle \ k}$ סיביות אקראיות ${\displaystyle \ b_{1},b_{2},...,b_{k}}$ (כמובן שצריך להתקיים ${\displaystyle \ {\mbox{gcd}}(s_{i},n)=1}$, אולם כמעט בטוח שדרישה זו לא תופר לעולם כיוון שמשמעות הדבר שנמצא גורם ראשוני של המודולוס מה שלא סביר שיקרה).
• מחשב את ${\displaystyle \ v_{i}=(-1)^{b_{i}}\cdot (s_{i}^{2})^{-1}{\mbox{ mod }}n}$ עבור כל השלמים ${\displaystyle \ s_{i}}$ (באופן זה מבטיחים ש-${\displaystyle \ v}$ משתרע על פני כל השלמים מודולו ${\displaystyle \ n}$ וכן כל ${\displaystyle \ v_{i}}$ זר ל-${\displaystyle \ n}$ ובעל סימן יעקובי 1, דרישה זו הכרחית כדי להבטיח שלא ייחשף כל מידע בנוגע לסוד).
• המפתח הציבורי יהיה הווקטור ${\displaystyle \ v_{1},v_{2},...,v_{k}}$ אותו המשתמש רושם אצל הצד השלישי. המפתח הפרטי הוא הווקטור ${\displaystyle \ s_{1},s_{2},...,s_{k}}$ ומשמש כסודו של A.

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

1. ${\displaystyle A\rightarrow B}$: ${\displaystyle \ x=\pm r^{2}{\mbox{ mod }}n}$
2. ${\displaystyle A\leftarrow B}$: ${\displaystyle \ e_{1},e_{2},...,e_{k},(e\in \{0,1\})}$
3. ${\displaystyle A\rightarrow B}$: ${\displaystyle \ y=r\cdot \prod _{e_{j=1}}s_{j}^{e_{j}}{\mbox{ mod }}n}$

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

מהלכי הפרוטוקול מבוצעים ${\displaystyle \ t}$ פעמים כדלהלן:

• A בוחר מספר אקראי ${\displaystyle \ r}$ בטווח ${\displaystyle \ [1,n-1]}$ וסיבית אקראית אחת ${\displaystyle \ b}$ ומחשב את ${\displaystyle \ x=(-1)^{b}\cdot r^{2}{\mbox{ mod }}n}$ ושולח את ${\displaystyle \ x}$ הנקרא הוכחה ל-B.
• B שולח ל-A את האתגר שהוא וקטור סיביות אקראי ${\displaystyle \ e_{1},e_{2},...,e_{k}}$.
• A מחשב את ${\displaystyle \ y=rs_{1}^{e_{1}}s_{2}^{e_{2}}\cdot \cdot \cdot s_{k}^{e_{k}}{\mbox{ mod }}n}$ (כלומר כפולה של ${\displaystyle \ r}$ בכל השלמים ${\displaystyle \ s_{j}}$ אשר מקבילים ל-1 בוקטור האתגר) ושולח את המענה ${\displaystyle \ y}$ ל-B.
• B מחשב את ${\displaystyle \ z=y^{2}\cdot \prod _{j=1}^{k}v_{j}^{e_{j}}{\mbox{ mod }}n}$ ומוודא ש-${\displaystyle \ z=\pm x}$ וכן ש-${\displaystyle \ z\neq 0}$.

אם בכל ${\displaystyle \ t}$ הסבבים ${\displaystyle \ z=\pm x}$ כנדרש, B יכול לקבל את הוכחת הזהות של A ולא, ההוכחה תדחה.

דוגמה להמחשה

נתון המודולוס ${\displaystyle \ n=631\cdot 983=620273}$ והפרמטרים ${\displaystyle \ t=1,k=4}$. להכנה המשתמש A בוחר 4 שלמים אקראיים ${\displaystyle \ s_{1}=5586,s_{2}=12546,s_{3}=1819,s_{4}=11777}$ המשמשים כמפתח פרטי וכן וקטור סיביות ${\displaystyle \ b_{1}=0,b_{2}=0,b_{3}=0,b_{4}=1}$ ומחשב את המפתח הפומבי: ${\displaystyle \ v_{1}=587652,v_{2}=370139,v_{3}=537354,v_{4}=109516}$

לצורך אימות מול B המשתמש A בחר מספר אקראי ${\displaystyle \ 5506}$ וסיבית אחת, נניח ${\displaystyle \ 0}$ ומחשב את ההוכחה: ${\displaystyle \ 5506^{2}{\mbox{ mod }}620273=542932}$ ושולח את ${\displaystyle \ 542932}$ לשרת. השרת מייצר רצף סיביות אתגר אקראי ${\displaystyle \ (0,0,1,0)}$ ושולח למשתמש. המשתמש בתורו מחשב את ${\displaystyle \ 5506\cdot 1819{\mbox{ mod }}620273=91046}$ (רק הסיבית ${\displaystyle \ e_{3}=1}$ לכן ${\displaystyle \ s_{3}}$ נכלל בחישוב) ושולח בחזרה לשרת את המענה ${\displaystyle \ 91046}$. מה שנותר לשרת כדי לאמת את זהותו זה לבדוק האם ${\displaystyle \ 91046^{2}\cdot 537354{\mbox{ mod }}620273=542932}$ כיוון שזהו אכן המקרה ההוכחה מתקבלת.

אם A מתחזה ואין לו שמץ של מושג לגבי הסוד ${\displaystyle \ s}$. הוא יכול לרמות רק אם ידע מראש מה תהיה מחרוזת סיביות האתגר שהשרת ישלח לו. במקרה כזה הוא יכול פשוט לקבוע את: ${\displaystyle \ x=r^{2}\cdot \prod _{i=1}^{k}v_{i}^{e_{i}}}$ ואז המענה יהיה תמיד ${\displaystyle \ y=r}$. עבור כל סיבית סיכוייו לרמות הם חצי ובסך הכול סיכוייו הם ${\displaystyle \ 2^{-k}}$ עבור סבב בודד.

קל יותר להבין את הרעיון עם סיבית אתגר בודדת. אם נתייחס רק לסיבית הראשונה המקבילה ל-${\displaystyle \ v_{1}=587652}$, נניח שהמתחזה ישלח לשרת את ${\displaystyle \ x=r^{2}\cdot v_{1}}$ הוא יצליח לענות תשובה נכונה רק אם סיבית האתגר שיקבל תהיה 1 כיוון שאז ${\displaystyle \ y^{2}\cdot v_{1}\equiv x{\mbox{ (mod }}n)}$ אולם תהיה לו בעיה עם סיבית 0 כי אז יהיה עליו לחשב את השורש הריבועי של ${\displaystyle \ r^{2}\cdot v_{1}{\mbox{ mod }}n}$. ולפי הדוגמה המובאת לעיל, אם המתחזה יבחר מספר אקראי ${\displaystyle \ r=1234}$ למשל וישלח לשרת את ${\displaystyle x=1234^{2}\cdot v_{1}{\mbox{ mod }}620273=119456}$, קל לראות שאם סיבית האתגר היא 1 המענה הנכון הוא ${\displaystyle \ y=1234}$ אולם אם סיבית האתגר תהיה 0 המענה צריך להיות השורש הריבועי של ${\displaystyle \ 119456}$ כיוון ש: ${\displaystyle \ 149683^{2}\equiv 119456{\mbox{ (mod }}620273)}$ הרי שהמענה הנכון הוא ${\displaystyle \ y=149683}$. מכיוון שהדוגמה המובאת כאן היא במספרים קטנים, קל כמובן למצוא שורש ריבועי בסדר גודל כזה, במיוחד אם הגורמים הראשוניים ידועים. אולם במספרים גדולים חישוב שורש ריבועי ללא ידיעת הגורמים הראשוניים הופך לבעיה מאוד קשה, על כן המתחזה יכשל.

ביטחון

• בעיית מציאת שורש ריבועי של שלם פריק שקולה לבעיית פירוק לגורמים, לא ידוע על דרך יעילה לחישוב שורש ריבועי מודולרי ללא הגורמים הראשוניים. לכן ביטחון האלגוריתם נשען על הקושי שבפירוק לגורמים. כדי שהפרוטוקול יהיה בטוח כמובן יש צורך להבטיח שלא ניתן יהיה לפרק את המודולוס לגורמים עם מיטב האלגוריתמים הידועים. ההנחה היא כיום שמודולוס בגודל 2048 סיביות רחוק מהישג יד של היכולת הטכנולוגית הנוכחית.
• הפרמטרים ${\displaystyle \ k}$ ו-${\displaystyle \ t}$ מספקים מדד יעילות וביטחון של הפרוטוקול. ${\displaystyle \ k}$ גדול משפיע על סיבוכיות הפרוטוקול (כמות העבודה) ואילו ${\displaystyle \ t}$ גדול משפיע על התקשורת (היקף התעבורה). מצד המוכיח עדיף ${\displaystyle \ t}$ קטן יותר כי הוא חושף פחות מידע, בעוד שהמאמת לעומת זאת מעדיף ${\displaystyle \ t}$ גדול. אם ${\displaystyle \ t=1}$ (כלומר הפרוטוקול מבוצע בסבב אחד) ו-${\displaystyle \ k}$ גדול יותר ניתן להגיע לביצועים טובים יותר על חשבון ביטחון, במקרה כזה הפרוטוקול לא יקרא הוכחה באפס ידיעה כיוון שאינו נאות לפי ההגדרה. אולם מבחינה מעשית לנאותות יש חשיבות מועטה. כיוון שהמושג אפס ידיעה תאורטי במהותו, כשזה נוגע להיבטים פרקטיים לעיתים מסתפקים ב-${\displaystyle \ t=1}$.
• בהנחה שפירוק לגורמים היא בעיה קשה, ההתקפה הטובה ביותר כנגד הפרוטוקול - התקפת טקסט-מוצפן-נבחר היא בעלת סיבוכיות ${\displaystyle \ 2^{-kt}}$ כך שמהיבט של ביטחון רצוי ש-${\displaystyle \ kt}$ יהיה גדול כדי לסכל התקפה כזו, אולם מהיבט של יעילות רצוי שלא יהיה גדול מדי. במקרים בהם קיימת הגנה נוספת (כגון אם תהליך אימות מצריך נוכחות פיזית של המאמת או במקרים בהם קיימת הגבלה של מספר ניסיונות האימות האפשריים בפרק זמן נתון) ${\displaystyle \ k=6,t=5}$ מספקים רמת ביטחון טובה (${\displaystyle \ 2^{-30}}$).

שיפורים

• בהתאם לצורך או לדרישות בטיחות, ניתן לממש את הפרוטוקול עם מודולוס נפרד לכל משתמש כשהגורמים הראשוניים ידועים רק לו. או באמצעות מודולוס משותף למספר משתתפים שגורמיו הראשוניים ידועים רק לשרת הצד-השלישי והוא אחראי להפקת מפתח פומבי ומפתח פרטי מתאים לכל משתמש.
• במקום לשלוח את ${\displaystyle \ x}$ במהלך הראשון לעיל, המשתתף A יכול לשלוח ערך גיבוב שלו ${\displaystyle \ h(x)}$ בכך ניתן לצמצם מעט את היקף התעבורה.
• ניתן ליישם את הפרוטוקול באופן שהוא יקרא מבוסס זהות. פרוטוקול אימות מבוסס זהות הוא פרוטוקול שבו המפתח הפומבי של המוכיח הוא פונקציה של פרטי זהותו הפומביים כמו שם פרטי, מספר תעודת זהות, כתובת וכדומה. במקרה כזה הצד השלישי, אחראי להפקת מפתחות פומביים עבור כל המשתמשים באמצעות פונקציה מוסכמת ומתוכם הוא מפיק את המפתחות הפרטיים המתאימים על ידי חישוב השורשים הריבועיים שלהם ושולח אותם לכל המשתמשים (כאמור חישוב השורשים הריבועיים אפשרי רק בידיעת הגורמים הראשוניים).
• ניתן ליישם את מהלכי הפרוטוקול באופן מקבילי, כלומר במקום שהפרוטוקול יבוצע ${\displaystyle \ t}$ פעמים, המוכיח והמאמת יכולים לשלוח זה לזה את כל האתגרים וההוכחות בו זמנית. אף על פי שהפרוטוקול במקרה כזה לא ייקרא הוכחה באפס ידיעה, יש בו תועלת להפחתת הסיכוי כנגד זיוף וניתן להוכיח כי הוא בטוח. למעשה שיטת חתימה דיגיטלית של פייגה-פיאט-שמיר פועלת על עיקרון זה כאשר במקום וקטור אתגר אקראי החותם משתמש בערך הגיבוב של המסר המיועד לחתימה.

מקורות

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

הערות שוליים

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