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

From האנציקלופדיה היהודית
Jump to navigation Jump to search

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

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

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

הפרוטוקול[edit | edit source]

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

תהליך הכנה חד פעמי[edit | edit source]

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

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

בחירת סוד פרטי[edit | edit source]

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

  • בוחר הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k} שלמים אקראיים הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s_1,s_2,...,s_k} בטווח הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ [1,n-1]} וכן הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k} סיביות אקראיות הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ b_1,b_2,...,b_k} (כמובן שצריך להתקיים הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \mbox{gcd}(s_i,n)=1} , אולם כמעט בטוח שדרישה זו לא תופר לעולם כיוון שמשמעות הדבר שנמצא גורם ראשוני של המודולוס מה שלא סביר שיקרה).
  • מחשב את הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("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} עבור כל השלמים הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s_i} (באופן זה מבטיחים ש-הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ v} משתרע על פני כל השלמים מודולו הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} וכן כל הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ v_i} זר ל-הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} ובעל סימן יעקובי 1, דרישה זו הכרחית כדי להבטיח שלא ייחשף כל מידע בנוגע לסוד).
  • המפתח הציבורי יהיה הווקטור הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ v_1,v_2,...,v_k} אותו המשתמש רושם אצל הצד השלישי. המפתח הפרטי הוא הווקטור הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s_1,s_2,...,s_k} ומשמש כסודו של A.

מהלכי הפרוטוקול[edit | edit source]

  1. הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \rarr B} : הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x = \pm r^{2}\mbox{ mod }n}
  2. הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \larr B} : הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ e_1,e_2,...,e_k, (e \in \{0,1\})}
  3. הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \rarr B} : הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("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}

פירוט המהלכים[edit | edit source]

מהלכי הפרוטוקול מבוצעים הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t} פעמים כדלהלן:

  • A בוחר מספר אקראי הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ r} בטווח הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ [1,n-1]} וסיבית אקראית אחת הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ b} ומחשב את הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x=(-1)^b\cdot r^2\mbox{ mod }n} ושולח את הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x} הנקרא הוכחה ל-B.
  • B שולח ל-A את האתגר שהוא וקטור סיביות אקראי הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ e_1,e_2,...,e_k} .
  • A מחשב את הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("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} (כלומר כפולה של הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ r} בכל השלמים הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s_j} אשר מקבילים ל-1 בוקטור האתגר) ושולח את המענה הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y} ל-B.
  • B מחשב את הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("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} ומוודא ש-הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ z=\pm x} וכן ש-הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ z\ne 0} .

אם בכל הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t} הסבבים הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ z=\pm x} כנדרש, B יכול לקבל את הוכחת הזהות של A ולא, ההוכחה תדחה.

דוגמה להמחשה[edit | edit source]

נתון המודולוס הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n=631\cdot 983=620273} והפרמטרים הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t=1,k=4} . להכנה המשתמש A בוחר 4 שלמים אקראיים הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("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} המשמשים כמפתח פרטי וכן וקטור סיביות הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("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} ומחשב את המפתח הפומבי: הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ v_1=587652,v_2=370139,v_3=537354,v_4=109516}

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

אם A מתחזה ואין לו שמץ של מושג לגבי הסוד הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s} . הוא יכול לרמות רק אם ידע מראש מה תהיה מחרוזת סיביות האתגר שהשרת ישלח לו. במקרה כזה הוא יכול פשוט לקבוע את: הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("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}} ואז המענה יהיה תמיד הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y=r} . עבור כל סיבית סיכוייו לרמות הם חצי ובסך הכול סיכוייו הם הפענוח נכשל (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 2^{-k}} עבור סבב בודד.

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

בטיחות[edit | edit source]

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

שיפורים[edit | edit source]

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

מקורות[edit | edit source]

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

הערות שוליים[edit | edit source]

  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 תווים

לעדכון מוויקיפדיה, לחץ כאן.

NivdakVeushar.png