הצפנת רבין

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

נלקח מויקיפדיה

הגדרות נוספות הקשורות להצפנת רבין:
•הצפנה
•מפתח ציבורי
•חתימה דיגיטלית
•מספרים ראשוניים