הצפנה הסתברותית – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
שורה 11:
==סכימה קונקרטית==
הסכימה ההסתברותית הקונקרטית הראשונה, שהוצעה על ידי גולדווסר ומיקלי{{הערה|Goldwasser, S. and S. Micali (1984). “Probabilistic encryption.” Journal of Computer and System Sciences, 28, 270–299}} מסתמכת על '''בעיית השארית הריבועית מודולו מספר פריק''' שנחשבת לפונקציה חד-כיוונית קשה והיא למעשה הסכימה הראשונה שהוכחה כבעלת ביטחון סמנטי.
הבעיה מוגדרת כדלהלן: נתון מודולוס <math>n</math> שהוא כפולה של שני ראשוניים <math>p,q</math> אם <math>x</math> [[מספר זר|זר]] ל-<math>n</math> אז <math>x</math> הוא שארית ריבועית (quadratic residue) ביחס למודולוס <math>n</math> אם למשוואה
:<math>x\equiv y^2\text{(mod }n)</math>
יש פתרון שלם <math>y</math>, אחרת אמרים ש-<math>x</math> אינו שארית ריבועית (quadratic non-residue).
בסכימה הבאה הטקסט המוצפן עבור כל סיבית מידע גדול (לפחות 1024 סיביות) מסיבה זו אינה נחשבת ליעילה מבחינה מעשית וחשיבותה בעיקר תיאורטית. היא פועלת כדלהלן:
בהינתן פרמטר ביטחון <math>k</math> המשתמש A מכין את הפרמטרים הבאים:
|