הצפנת רבין – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ בוט משנה: it:Crittosistema di Rabin |
מאין תקציר עריכה |
||
שורה 1:
'''צופן רבין''' הוא שיטת [[קריפטוגרפיה|הצפנה]] [[מפתח ציבורי|אסימטרית]] ו[[חתימה דיגיטלית]], שהומצאה על ידי [[פרופסור]] [[מיכאל רבין]] ([[האוניברסיטה העברית בירושלים]]) בהיותו אורח [[המכון הטכנולוגי של מסצ'וסטס|במכון הטכנולוגי של מסצ'וסטס]] (MIT) ב-[[1979]]. אלגוריתם רבין מבוסס על בעיית [[שורש ריבועי]] [[מודולו]] שלם פריק והוא אלגוריתם הצפנת מפתח-פומבי הראשון ש[[הוכחה|הוכח]] [[מתמטיקה|מתמטית]] כי פיצוחו קשה כפתרון בעיית [[פירוק לגורמים]] הנחשבת כבעיה [[חישוביות|חישובית]] קשה. ביתר פירוט, שחזור טקסט המקור מתוך הטקסט המוצפן ''עבור טקסט מקור שנבחר באקראי'' שקול מבחינה חישובית לפירוק לגורמים. (זאת בניגוד לפונקציית-[[RSA]], שלגביה לא ידועה הוכחה דומה). הוכח אף כי מציאת הסיביות הראשונות בטקסט המקור (LSB) שקול לפירוק לגורמים.
בדומה ל-RSA גם בשיטה זו מכינים [[חשבון מודולרי|מודולוס]] <math>\ n</math> שהוא כפולה של שני [[מספר ראשוני|מספרים ראשוניים]] גדולים <math>\ (p, q)</math>. ההצפנה היא פשוט העלאת המסר בריבוע (מודולו <math>\ n</math>) ואילו פענוח הוא חישוב שורש ריבועי מודולו <math>\ n</math>. אם הגורמים הראשוניים של <math>\ n</math> ידועים זו בעיה קלה. כיוון שכידוע לשורש ריבועי ישנם שני פתרונות אפשריים, על כן במקרה זה יתקבלו ארבעה פתרונות אפשריים (מודולו <math>\ p</math> ו-<math>\ q</math> בהתאמה), שמתוכם על המקבל להחליט בדרך כלשהי איזה מהם תואם את המסר שהוצפן. זהו חסרונה העיקרי של הצפנת רבין.
==הכנת מפתחות הצפנה==
| |||