הצפנת רבין

צופן רבין הוא שיטת הצפנה אסימטרית וחתימה דיגיטלית, שהומצאה על ידי פרופסור מיכאל רבין (האוניברסיטה העברית בירושלים) בהיותו אורח במכון הטכנולוגי של מסצ'וסטס (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$ מקיים $\ p\equiv 3\ ({\mbox{mod }}4)$ כלומר $\ 4|(p+1)$ כנ"ל לגבי $\ q$, חישוב השורשים הריבועיים יהיה קל יותר באופן משמעותי, כדלהלן:

1. באמצעות אלגוריתם אוקלידס המורחב מוצאים שלמים $\ a$ ו-$\ b$ המקיימים את משוואת אוקלידס: $\ ap+bq=1$.
2. מחשבים את $\ r=c^{(p+1)/4}{\mbox{ mod }}p$.
3. מחשבים את $\ s=c^{(q+1)/4}{\mbox{ mod }}q$.
4. מחשבים את $\ x=(aps+bqr){\mbox{ mod }}n$.
5. מחשבים את $\ y=(aps-bqr){\mbox{ mod }}n$.

התוצאה היא: $\ \pm x$ ו-$\ \pm y$ (מודולו $\ n$).

שימו לב שבידיעת $r$ ו-$s$ אפשר לפרק את $n$ לגורמים כמו שציין רבין, כי $\ {\mbox{gcd}}(|r-s|,n)$ שווה לאחד הגורמים של $n$.

דוגמה

נבחר את הראשוניים $\ p=211,q=227$, (שניהם שקולים ל-$\ 3$ מודולו $\ 4$, במילים אחרות $\ 4|212$ וכן $\ 4|228$). אז $\ n=pq=47897$, כך שהמפתח הפרטי של אליס הוא $\ (211,227)$, והמפתח הפומבי הוא $\ 47897$. (את הגורמים של 47897 אפשר למצוא בזמן קצר, אבל דוגמה זו ממחישה את עיקרי השיטה).

בוב מעוניין להצפין את המסר $\ m=23$ עבור אליס (למען הפשטות, נניח שהוא בוחר לבנות את המסר כמתואר להלן, כלומר משרשר את המסר פעמיים $\ m||m=2323$), כדי להצפין את המסר הוא מחשב את $\ m^{2}{\mbox{ mod }}n=2323^{2}{\mbox{ mod }}47897=31865$ ושולח את $\ c=31865$ לאליס. כאשר אליס מקבלת את $\ c$ היא מחשבת את השורשים הריבועיים שלו כדלהלן:

1. מחשבת את $\ r=31865^{53}{\mbox{ mod }}211=209$,
2. מחשבת את $\ s=31865^{57}{\mbox{ mod }}227=53$,
3. מחשבת את משוואת אוקלידס $\ ap+bq\ =\ -71\cdot 211+66\cdot 227=1$,
4. מחשבת את $\ x=(-71\cdot 211\cdot 53)+(66\cdot 227\cdot 209){\mbox{ mod }}47897=38189$,
5. מחשבת את $\ y=(-71\cdot 211\cdot 53)-(66\cdot 227\cdot 209){\mbox{ mod }}47897=-45574$,

כלומר $\ y=-45574+47897=2323$,

אם כן, השורשים הריבועיים האפשריים של $\ 31865$ מודולו $\ 47897$ הם: $\ x=38189,y=2323,-x=9708,-y=45574$.

אמנם אליס אינה יכולה לדעת מה שלח בוב אולם מהתבוננות בערכים שהתקבלו, קל לראות כי $\ y$ נראה שונה מהיתר, בכך שהוא מורכב מערך שחוזר על עצמו פעמיים, משמע זהו הפתרון הנכון, על כן $\ m=y$.

ביטחון

המשימה של תוקף פוטנציאלי, קרי שחזור $\ m$ מתוך הטקסט המוצפן $\ c$ היא בעיה קשה. למעשה בעיה זו נקראת בעיית שורש ריבועי מודולו שלם פריק. הבעיה הכללית מוגדרת כדלהלן:

נתון שלם פריק $\ n$ ו-$\ q\in \mathbb {Z} _{n}$ שהוא שארית ריבועית מודולו $n$,

מצא שלם $\ x$ המקיים: $\ x^{2}\equiv q\ ({\mbox{mod }}n)$.

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

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

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

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

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

יתירות

החסרון העיקרי של הצפנת רבין הוא בעובדה שתוצאת ההצפנה היא אחת מארבע אפשרויות (פתרונות שורש ריבועי מודולו $\ n$), הבעיה היא לזהות איזו מהן היא הנכונה. ניתן בקלות להתגבר על מכשלה זו על ידי הוספת יתירות מסוימת למסר המקורי לפני ההצפנה. לדוגמה אם המסר המיועד להצפנה הוא מהצורה $\ m||m$ (|| מסמל שרשור) רוב הסיכויים שרק אחד מארבעת הפתרונות האפשריים יהיה בעל מבנה זה ועל כן ניתן יהיה לזהותו בקלות. שיטה זו תמנע את ההתקפות המתוארות. למשל אם התוקף יבקש לפענח את השורש הריבועי של $\ m^{2}$ שהוא עצמו הכין עם היתירות האמורה. המערכת תחזיר עבורו את $\ m$ עצמו, עובדה שאין בה כל מידע חדש שעשוי לסייע לו בהתקפה. אולם יש לשים לב כי בשיטה זו ההוכחה כי הצפנת רבין שקולה לפירוק לגורמים לא תהיה תקפה.

ראו גם

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

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

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