הצפנת רבין – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אלגוריתמיקאי (שיחה | תרומות) אין תקציר עריכה |
|||
שורה 1:
'''צופן רבין''' הנו שיטת [[קריפטוגרפיה|הצפנה]] [[מפתח ציבורי|אסימטרית]] ו[[חתימה דיגיטלית]], שהומצאה על ידי [[פרופסור]] [[מיכאל רבין]] ([[האוניברסיטה העברית בירושלים]]) בהיותו אורח [[המכון הטכנולוגי של מסצ'וסטס|במכון הטכנולוגי של מסצ'וסטס]] (MIT) ב-[[1979]]. אלגוריתם רבין מבוסס על בעיית [[שורש ריבועי]] [[מודולו]] שלם פריק שהיא בעיה קשה מבחינה [[חישוביות|חישובית]] והוא אלגוריתם הצפנת מפתח-פומבי הראשון ש[[הוכחה|הוכח]] [[מתמטיקה|מתמטית]] כי פיצוחו קשה כפתרון בעיית [[פירוק לגורמים]]
בדומה ל-RSA גם בשיטה זו מכינים [[חשבון מודולרי|מודולוס]] <math>\ n</math> שהוא כפולה של שני [[מספר ראשוני|מספרים ראשוניים]] גדולים <math>\ (p, q)</math>. ההצפנה היא פשוט העלאת המסר בריבוע (מודולו <math>\ n</math>) ואילו פענוח הוא חישוב שורש ריבועי מודולו <math>\ n</math>. אם הגורמים הראשוניים של <math>\ n</math> ידועים זו בעיה קלה. כיוון שכידוע לשורש ריבועי ישנם שני פתרונות אפשריים, על כן במקרה זה יתקבלו ארבעה פתרונות אפשריים (מודולו <math>\ p</math> ו-<math>\ q</math> בהתאמה), שמתוכם על המקבל להחליט בדרך כלשהי איזה מהם תואם את המסר שהוצפן. זהו חסרונה העיקרי של הצפנת רבין. ישנם מספר דרכים להתמודד עם בעיה זו כמו הוספת [[יתירות]], כפי שיובהר להלן.
שורה 81:
==קישורים חיצוניים==
[http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-TR-212.pdf פונקציית הצפנה וחתימה דיגיטלית עמידה כפירוק לגורמים], פרופסור מיכאל רבין, המכון הטכנולוגי של מסצ'וסטס, 1979.
[http://www.wisdom.weizmann.ac.il/~oded/p_acgs.html On the hardness of the least-signficant bits of the RSA and Rabin functions]
| |||