הצפנת רבין – הבדלי גרסאות

אם נסמן <math>q=x^2</math> (מודולו <math>n</math>) הוא 'שארית ריבועית'. משפט רבין אומר שאם אפשר למצוא שורש ריבועי של <math>q</math> עבור 1% מכל השאריות הריבועיות ב-<math>\mathbb{Z}_n</math> אזי אפשר לפרק לגורמים את <math>n</math> בזמן פולינומי. ההוכחה היא, נניח שנתונה קופסה שחורה <math>B</math> כך כאשר מזינים קלט <math>q</math> מחזירה את השורש הריבועי שלו באחוז אחד מהמקרים, אזי אפשר לבצע את הניסוי הבא: בוחרים <math>i</math> אקראי כלשהו ב-<math>Z_n</math> ומזינים ל-<math>B</math> את <math>q=i^2</math> (מודולו <math>n</math>) אם התוצאה אינה <math>i</math> או <math>-i</math> אזי אפשר לפרק את <math>n</math> בגלל העובדה שאם נתונים <math>x,y\in Z_n</math> כך שמתקיים <math>x^2\equiv y^2</math> אך <math>x\ne \pm y</math> (מודולו <math>n</math>) אזי <math>\mbox{Gcd}(n, x\pm y)</math> הוא גורם ראשוני לא טריוויאלי של <math>n</math>. Gcd היא [[מחלק משותף מקסימלי]]. מספר הניסיונות הממוצע הוא 2, היות שכמחצית מהאלמנטים ב-<math>Z_n</math> הם שורשים ריבועיים, מכאן שהסיכויים לפרק את <math>n</math> הם 50%. לכן מספיק יהיה להוכיח שאפשר לפרוץ את הצפנת רבין רק ב-1% סיכויי הצלחה כדי לפרק את <math>n</math> לגורמים ומכאן שאם פירוק לגורמים היא בעיה קשה, הצפנת רבין תהיה קשה גם היא.

 

 

שיטת רבין מוכחת כבטוחה רק כנגד יריב פסיבי, אך פגיעה להתקפה אקטיבית שנקראת [[התקפת מוצפן-נבחר]] (שבה היריב מסוגל לבחור את הטקסט אותו הוא מעוניין להצפין). בהתקפה כזו היריב יכול לחשוף את הגורמים הראשוניים של <math>\ n</math> כדלהלן: היריב בוחר <math>\ m</math> אקראי כלשהו מחשב את <math>\ c = m^2 \mbox{ mod }n</math> ואז מבקש מהמקבל לפענח עבורו את <math>\ c</math>. מכיוון שהמקבל לא מכיר את <math>\ m</math> שנבחר על ידי התוקף יש סיכוי שהתוצאה שתוחזר לא תהיה <math>\ m</math> אלא אחת מהתוצאות האחרות האפשריות אם נקרא לתוצאה שהוחזרה <math>\ y</math> כאשר <math>\ y \ne \pm m</math> אזי <math>\ \mbox{gcd}(m-y,n)</math> הנו אחד הגורמים של <math>\ n</math> (הפונקציה gcd מייצגת [[מחלק משותף מקסימלי|מחלק משותף מרבי]]). בסוג כזה של התקפה מניחים כי התוקף מסוגל לדרוש מהצד המפענח (למשל [[שרת]]) לפענח עבורו כל מסר שידרוש.