הצפנה הסתברותית – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
|||
שורה 6:
#אין הוכחה בהכרח שאם <math>f</math> חד-כיוונית יהיה תמיד קשה להפוך אותה גם כאשר <math>x</math> הוא בעל מבנה מיוחד. הדוגמה הכי פשוטה היא בהינתן פונקציית RSA ידוע שקל לחשב ערכים קטנים של <math>x</math> אם המעריך (מפתח ההצפנה) קטן, כך שהתוצאה אינה גדולה מהמודולוס.
#העובדה ש-<math>f</math> חד-כיוונית אינה מעידה בהכרח שלא ניתן לחלץ מידע חלקי לגבי <math>x</math>. לדוגמה אם <math>y\equiv g^x\text{ mod }p</math> כאשר <math>p</math> ראשוני ו-<math>g</math> הוא [[חבורה (מבנה אלגברי)#יוצרים ויחסים|יוצר]] של <math>Z_p^*</math> אזי <math>x</math> אינו מספר זוגי אם ורק אם <math>y</math> הוא [[שארית ריבועית]] מודולו <math>p</math> וקיים אלגוריתם הסתברותי יעיל
לסכימת הצפנה הסתברותית קשר למושג שנקרא [[סיבית קשה]], הבעיה שהועלתה על ידי גילס ברסרד היא כיצד להצפין סיבית בודדת באמצעות סכימת הצפנה אסימטרית, אפשר לראות שסכימה דטרמיניסטית כמו RSA אינה מתאימה למטרה זו כיוון שלמרות שהיא בטוחה, אפשר לחשב את הסיבית הפחות משמעותית. אפשר לנסות לפתור את הבעיה על ידי הטמעה של הסיבית הסודית בהתוך מספר אקראי כלשהו במיקום מוסכם או באמצעות חישוב כלשהו כמו [[XOR]], אך העובדה שבאופן עקרוני בכל סכימה דטרמיניסטית גם אם היא בטוחה אין זה סותר את העובדה שקל לחשב מידע חלקי כמו הסיבית הראשונה גורמת לכך שסכימה כזו לא מתאימה להצפנת סיבית אחת. ההצעה של גולדווסר ומיקלי פותרת בעיה זו.
| |||