הצפנה הסתברותית – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
שורה 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>p-1</math> יש גורם ראשוני גדול, העובדה היא ש-<math>x</math> אינו מספר זוגי אם ורק אם <math>y</math> הוא [[שארית ריבועית]] מודולו <math>p</math> וקיים אלגוריתם הסתברותי יעיל להכריע אם מספר הוא שארית ריבועית מודולו מספר ראשוני כלשהו. לכן תמיד אפשר לדעת מהי הסיבית הפחות משמעותית של <math>x</math>.
לסכימת הצפנה הסתברותית קשר למושג שנקרא [[סיבית קשה]], הבעיה שהועלתה על ידי גילס ברסרד היא כיצד להצפין סיבית בודדת באמצעות סכימת הצפנה אסימטרית, אפשר לראות שסכימה דטרמיניסטית כמו RSA אינה מתאימה למטרה זו כיוון שלמרות שהיא בטוחה, אפשר לחשב את הסיבית הפחות משמעותית. אפשר לנסות לפתור את הבעיה על ידי הטמעה של הסיבית הסודית בתוך מספר אקראי כלשהו במיקום מוסכם או באמצעות חישוב כלשהו כמו [[XOR]], אך העובדה שבאופן עקרוני בכל סכימה דטרמיניסטית גם אם היא בטוחה אין זה סותר את העובדה שקל לחשב מידע חלקי כמו הסיבית הראשונה גורמת לכך שסכימה כזו לא מתאימה להצפנת סיבית אחת. ההצעה של גולדווסר ומיקלי פותרת בעיה זו.
| |||