הצפנת רבין

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

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


מייצרים שני מספרים ראשוניים גדולים p ו-q, ומחשבים n = p·q. n הוא המפתח הפומבי; p ו-q הם המפתח הפרטי.


כדי להצפין מספר m מחשבים את c = m^2 (mod n). כלומר מעלים את m בריבוע ולאחר מכן שומרים רק את השארית אחרי חלוקה ב-n. התלות הביטחונית היא בכך שלא ניתן למצוא שורש ריבועי מודולו n בלי לדעת את p ו-q.

הגרסה המקורית שונה במעט: הצפנה יכולה להיות c = m(m+b) (mod n), כאשר b הוא חלק מהמפתח הפומבי. הבטיחות דומה.


פענוח הוא הוצאת שורש ריבועי מודולו n. אם יודעים את p ו-q זה קל: מוצאים שורשים מודולו p ומודולו q, ואז משלבים אותם בעזרת משפט השאריות הסיני (כללי חיבור פתרונות מודולרים). לכל c קיימים ארבעה שורשים אפשריים מודולו n. זו בעיה מרכזית, כי על המקבל להחליט איזה מהארבעה הוא המסר המקורי.

כדי להקל על חישוב השורשים בוחרים פעמים רבות p ו-q כך ש-p≡3 (mod 4) ו-q≡3 (mod 4). אז משתמשים באלגוריתם אוקלידס מורחב כדי למצוא מקדמים, מחשבים חזקה מתאימה של c מודולו p ו-q, ומחברים בעזרת הנוסחאות שמביאות ל־±x ו±y כמחצית מהפתרונות.


נבחרו p=211 ו-q=227, לכן n=47897. אם בוב רוצה לשלוח את המספר 23, הוא בונה את המחרוזת 2323 ומשתמש בה כ-m. ההצפנה נותנת c=31865 שנשלח לאליס. אליס מחשבת את השורשים הריבועיים המודליים ומקבלת את ארבעת האפשרויות: 38189, 2323, 9708 ו-45574. מתוך התבוננות הערכים היא מזהה כי 2323 נראה כמו הודעה שחוזרת על עצמה, ולכן זו תשובת המסר המקורית.


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

עם זאת, יש מגבלות מעשיות: אם המסר אינו אקראי, למשל יש לו מבנה ידוע, יתכן שיוכלו לנצל זאת. בנוסף, יש התקפה פעילה הנקראת התקפת מוצפן-נבחר (chosen-ciphertext). בה התקף יכול לבחור m ולהשיג פענוח של c המתאים, ומכך לגזור גורם של n. לכן צופן רבין בטוח רק נגד יריב שקורא בלבד, לא נגד תוקף פעיל.

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


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

צופן רבין הומצא ב-1979 על ידי מיכאל רבין. זו דרך להצפין הודעות בעזרת שני מפתחות. מפתח אחד נפתח לכולם, והמפתח השני נשאר סודי.

הרעיון הקשה:
ההגנה של הצופן נשענת על כך שקשה לפרק מספר גדול לשני מספרים ראשוניים. פירוק כזה זה למצוא את המספרים הפשוטים שמכפילים יחד את המספר הגדול.


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


כאשר מפענחים לעתים יוצאות ארבע תשובות אפשריות. צריך דרך לבחור איזו תשובה היא הנכונה. קומבינציה פשוטה היא לחבר את ההודעה עם עצמה לפני ההצפנה. כך רק אחת מהתשובות תראה כמו הודעה חזרתית.


נניח שהבחירה היא p=211 ו-q=227. אז n=47897. בוב בוחר את המספר 23, מחבר אותו עם עצמו ויוצר 2323. הוא מצפין ושולח מספר גדול 31865.
אליס מפענחת ומקבלת ארבע אפשרויות. היא רואה שאחת מהן היא 2323, כלומר ההודעה שחוזרת על עצמה. זו ההודעה הנכונה.


שחזור ההודעה מהמספר המוצפן קשה אם לא יודעים את p ו-q. אבל אם תוקף יכול לבחור הודעה ולבקש לפענח אותה, הוא עשוי לגלות על p ו-q. לכן צריך לשים לב איך בונים את ההודעות לפני ההצפנה.


מוסיפים סדר או יתירות להודעה לפני ההצפנה. זה מקל על הזיהוי של התשובה הנכונה וממנע התקפות פשוטות.