הצפנת רבין

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

בדומה ל-RSA גם בשיטה זו מכינים מודולוס $\ n$ שהוא כפולה של שני מספרים ראשוניים גדולים $\ (p,q)$. ההצפנה היא פשוט העלאת המסר בריבוע (מודולו $\ n$) ואילו פענוח הוא חישוב שורש ריבועי מודולו $\ n$. אם הגורמים הראשוניים של $\ n$ אינם ידועים זו בעיה קשה שעליה מסתמכת ההצפנה. מאידך אם הגורמים הראשוניים ידועים קל לפתור אותה, כיוון שמודולו $p$ ומודולו $q$ יש למספר ריבועי שני שורשים, ולפי משפט השאריות הסיני יש בסך-הכל ארבעה שורשים מודולו $n$. מתוכם על המקבל להחליט בדרך כלשהי איזה מהם תואם את המסר שהוצפן. זהו חסרונה העיקרי של הצפנת רבין. ישנן מספר דרכים להתמודד עם בעיה זו כמו הוספת יתירות מכוונת, כפי שיובהר להלן.

הכנת מפתחות הצפנה

• בוחרים שני מספרים ראשוניים אקראיים $\ p$ ו-$\ q$ (שווים בגודלם בקירוב).
• מחשבים את $\ n=pq$.
• המפתח הפומבי הוא $\ n$ והמפתח הפרטי הוא הגורמים הראשוניים ($\ p,q$).

הצפנה

להצפנת המסר $\ m$ מחשבים את:

$\ c=m^{2}{\mbox{ mod }}n$

פענוח

• לפענוח יש לחשב תחילה את השורשים הריבועיים של $\ c$ כלומר לפתור את $\ c\equiv m^{2}\ ({\mbox{mod }}n)$ (באמצעות הגורמים הראשוניים של $n$).
• התוצאה היא ארבעה פתרונות אפשריים $\ m_{1},m_{2},m_{3},m_{4}$. מה שנותר למקבל זה, להחליט בדרך כלשהי איזה מהם הוא הנכון.

הגרסה המקורית של אלגוריתם רבין כפי שהוצגה לראשונה על ידי רבין שונה במעט. ההצפנה היא: $\ c=m(m+b){\mbox{ mod }}n$. כאשר $\ b$ מהווה חלק מהמפתח הפומבי. בטיחות השיטה המתוארת זהה למקורית.

שורש ריבועי

שיטת ההצפנה של רבין מבוססת על הקושי של הוצאת שורש ריבועי מודולו מספר שלם, השקולה לפירוק שלו. כדי למצוא שורש ריבועי מודולו שלם פריק, די לפרק תחילה את המספר לגורמיו הראשוניים ואז לחשב את הפתרונות עבור כל אחד מהם. חישוב שורש ריבועי מודולו מספר ראשוני קל יחסית מבחינה חישובית (קיימים מספר אלגוריתמים יעילים למטרה זו). השיטה הישירה לחישוב שורש ריבועי של השלם $\ a$ מודולו $\ p$ (ראשוני כלשהו) היא כדלהלן:

• בוחרים שלם אקראי $\ b$ הנמוך מ-$\ p$ כאשר $\ b^{2}-4a$ אינו שארית ריבועית מודולו $\ p$, כלומר:

$\ \left({\frac {b^{2}-4a}{p}}\right)=-1$,

כמחצית האלמנטים ב-$\ \mathbb {Z} _{p}$ עונים על דרישה זו, כך שנדרשים בממוצע כשני ניסיונות כדי למצוא $\ b$ מתאים.

הערה: הסוגריים במשוואה מייצגים סימן לז'נדר, שהוא פונקציה מעל $\ p$ ו-$\ a$ שהטווח שלה הוא $\ [1,0,-1]$ המסמנים האם $\ a$ הוא שארית ריבועית מודולו $\ p$ או לא (קיימים אלגוריתמים פולינומיים לחישוב סימן לז'נדר).

• מגדירים את הפולינום $\ f(x)=x^{2}-bx+a$ בשדה $\ \mathbb {Z} _{p}[x]$.
• מחשבים את $\ r=x^{(p+1)/2}{\mbox{ mod }}f$.
• התוצאה היא $\ (r,-r)$.

הערה: בחשבון מודולורי מספר שלילי $\ -r$ מודולו $\ n$ מיוצג כ-$\ -r+n=n-r$.

סיבוכיות האלגוריתם המתואר היא $\ O({\mbox{lg}}\ p)^{3})$. על כן הדרך העדיפה היא לבחור מספרים ראשוניים בעלי מבנה ייחודי המקל על חישוב השורש הריבועי, כפי שמובא במאמר של רבין. אם $\ p$ מקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p \equiv 3\ (\mbox{mod }4)} כלומר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 4|(p+1)} כנ"ל לגבי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ q} , חישוב השורשים הריבועיים יהיה קל יותר באופן משמעותי, כדלהלן:

1. באמצעות אלגוריתם אוקלידס המורחב מוצאים שלמים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ b} המקיימים את משוואת אוקלידס: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ ap + bq = 1} .
2. מחשבים את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ r = c^{(p+1)/4} \mbox{ mod }p} .
3. מחשבים את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s = c^{(q+1)/4} \mbox{ mod }q} .
4. מחשבים את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x = (aps+bqr) \mbox{ mod }n} .
5. מחשבים את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y = (aps-bqr) \mbox{ mod }n} .

התוצאה היא: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \pm x} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \pm y} (מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} ).

שים לב שבידיעת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} אפשר לפרק את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} לגורמים כמו שציין רבין, כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \mbox{gcd}(|r-s|,n)} שווה לאחד הגורמים של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} .

דוגמה

נבחר את הראשוניים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p=211,q=227} , (שניהם שקולים ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 3} מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 4} , במילים אחרות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 4|212} וכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 4|228} ). אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n=pq=47897} , כך שהמפתח הפרטי של אליס הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (211,227)} , והמפתח הפומבי הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 47897} . (את הגורמים של 47897 אפשר למצוא בזמן קצר, אבל דוגמה זו ממחישה את עיקרי השיטה).

בוב מעוניין להצפין את המסר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m=23} עבור אליס (למען הפשטות, נניח שהוא בוחר לבנות את המסר כמתואר להלן, כלומר משרשר את המסר פעמיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m||m = 2323} ), כדי להצפין את המסר הוא מחשב את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m^2\mbox{ mod }n=2323^2\mbox{ mod }47897=31865} ושולח את $\ c=31865$ לאליס. כאשר אליס מקבלת את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ c} היא מחשבת את השורשים הריבועיים שלו כדלהלן:

1. מחשבת את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ r=31865^{53}\mbox{ mod }211=209} ,
2. מחשבת את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s=31865^{57}\mbox{ mod }227=53} ,
3. מחשבת את משוואת אוקלידס הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ ap+bq \ = \ -71 \cdot 211+66\cdot 227=1} ,
4. מחשבת את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x=(-71\cdot 211\cdot 53)+(66\cdot 227\cdot 209)\mbox{ mod }47897 = 38189} ,
5. מחשבת את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y=(-71\cdot 211\cdot 53)-(66\cdot 227\cdot 209)\mbox{ mod }47897 = -45574 } ,

כלומר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y=-45574+47897=2323} ,

אם כן השורשים הריבועיים האפשריים של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 31865} מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 47897} הם: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x=38189,y=2323,-x=9708,-y=45574} .

אמנם אליס אינה יכולה לדעת מה שלח בוב אולם מהתבוננות בערכים שהתקבלו, קל לראות כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y} נראה שונה מהיתר, בכך שהוא מורכב מערך שחוזר על עצמו פעמיים, משמע זהו הפתרון הנכון, על כן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m=y} .

ביטחון

המשימה של תוקף פונטנציאלי, קרי שחזור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m} מתוך הטקסט המוצפן $\ c$ היא בעיה קשה. למעשה בעיה זו נקראת בעיית שורש ריבועי מודולו שלם פריק. הבעיה הכללית מוגדרת כדלהלן:

נתון שלם פריק הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} ו-$\ q\in \mathbb {Z} _{n}$ שהוא שארית ריבועית מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} ,

מצא שלם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x} המקיים: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x^2 \equiv q \ (\mbox{mod }n)} .

היכולת להוציא שורש ריבועי מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} שקולה חישובית ליכולת לפרק את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} לגורמים. על כן, כל עוד בעיית פירוק לגורמים נותרת בעיה קשה, שיטת רבין תהיה בטוחה, בתנאי שהמודולוס הוא מספר גדול (כ-2000 סיביות לפחות) כלומר מעבר ליכולת לפרקו לגורמים בזמן סביר.

אם נסמן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle q=x^2} (מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} ) הוא 'שארית ריבועית'. משפט רבין אומר שאם אפשר למצוא שורש ריבועי של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} עבור 1% מכל השאריות הריבועיות ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z}_n} אזי אפשר לפרק לגורמים את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} בזמן פולינומי. ההוכחה היא, נניח שנתונה קופסה שחורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} כך כאשר מזינים קלט הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} מחזירה את השורש הריבועי שלו באחוז אחד מהמקרים, אזי אפשר לבצע את הניסוי הבא: בוחרים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} אקראי כלשהו ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Z_n} ומזינים ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle q=i^2} (מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} ) אם התוצאה אינה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} או הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle -i} אזי אפשר לפרק את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} בגלל העובדה שאם נתונים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x,y\in Z_n} כך שמתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^2\equiv y^2} אך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x\ne \pm y} (מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} ) אזי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mbox{Gcd}(n, x\pm y)} הוא גורם ראשוני לא טריוויאלי של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} . Gcd היא מחלק משותף מקסימלי. מספר הניסיונות הממוצע הוא 2, היות שכמחצית מהאלמנטים ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Z_n} הם שורשים ריבועיים, מכאן שהסיכויים לפרק את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} הם 50%. לכן מספיק יהיה להוכיח שאפשר לפרוץ את הצפנת רבין רק ב-1% סיכויי הצלחה כדי לפרק את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} לגורמים ומכאן שאם פירוק לגורמים היא בעיה קשה, הצפנת רבין תהיה קשה גם היא.

ההוכחה נכונה רק אם האלמנטים נבחרו באקראי. כלומר רק אם המסר שהוצפן נבחר באקראי בהסתברות שווה מתוך כל המסרים האפשריים. במציאות מסרים אינם לגמרי אקראיים, אם המסר הוא בעל יתירות מסוימת או מבנה מיוחד ייתכן שיהיה אפשר לנחש חלק ממנו או לקבל מידע מסוים לגביו למרות שחישוב שורש ריבועי מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} היא בעיה קשה. למשל אפשר לנחש את הסיבית הנמוכרה ביותר (LSB) באמצעות סימן יעקובי. לכן מעצם ההגדרה הצפנת רבין אינה בטוחה סמנטית.

שיטת רבין מוכחת כבטוחה רק כנגד יריב פסיבי, אך פגיעה להתקפה אקטיבית שנקראת התקפת מוצפן-נבחר (שבה היריב מסוגל לבחור את הטקסט אותו הוא מעוניין להצפין). בהתקפה כזו היריב יכול לחשוף את הגורמים הראשוניים של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} כדלהלן: היריב בוחר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m} אקראי כלשהו מחשב את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ c = m^2 \mbox{ mod }n} ואז מבקש מהמקבל לפענח עבורו את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ c} . מכיוון שהמקבל לא מכיר את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m} שנבחר על ידי התוקף יש סיכוי שהתוצאה שתוחזר לא תהיה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m} אלא אחת מהתוצאות האחרות האפשריות אם נקרא לתוצאה שהוחזרה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y \ne \pm m} אזי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \mbox{gcd}(m-y,n)} הנו אחד הגורמים של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} (הפונקציה gcd מייצגת מחלק משותף מרבי). בסוג כזה של התקפה מניחים כי התוקף מסוגל לדרוש מהצד המפענח (למשל שרת) לפענח עבורו כל מסר שידרוש.

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

יתירות

החסרון העיקרי של הצפנת רבין היא בעובדה שתוצאת ההצפנה היא אחת מארבע אפשרויות (פתרונות שורש ריבועי מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} ), הבעיה היא לזהות איזו מהן היא הנכונה. ניתן בקלות להתגבר על מכשלה זו על ידי הוספת יתירות מסוימת למסר המקורי לפני ההצפנה. לדוגמה אם המסר המיועד להצפנה הוא מהצורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m || m} (|| מסמל שרשור) רוב הסיכויים שרק אחד מארבעת הפתרונות האפשריים יהיה בעל מבנה זה ועל כן ניתן יהיה לזהותו בקלות. שיטה זו תמנע את ההתקפות המתוארות. למשל אם התוקף יבקש לפענח את השורש הריבועי של $\ m^{2}$ שהוא עצמו הכין עם היתירות האמורה. המערכת תחזיר עבורו את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m} עצמו, עובדה שאין בה כל מידע חדש שעשוי לסייע לו בהתקפה. אולם יש לשים לב כי בשיטה זו ההוכחה כי הצפנת רבין שקולה לפירוק לגורמים לא תהיה תקפה.

ראו גם

• חתימה דיגיטלית רבין

קישורים חיצוניים

• פונקציית הצפנה וחתימה דיגיטלית עמידה כפירוק לגורמים, פרופסור מיכאל רבין, המכון הטכנולוגי של מסצ'וסטס, 1979.
• On the hardness of the least-signficant bits of the RSA and Rabin functions מאמר המראה כי גם לגלות את הסיביות הראשונות בשיטת רבין היא בעיה קשה כפירוק לגורמים.