הצפנת רבין – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ בוט החלפות: דוגמה; פונקציית; |
|||
שורה 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> בהתאמה), שמתוכם על המקבל להחליט בדרך כלשהי איזה מהם תואם את המסר שהוצפן. זהו חסרונה העיקרי של הצפנת רבין. ישנם מספר דרכים להתמודד עם בעיה זו כמו הוספת [[יתירות]], כפי שיובהר להלן.
שורה 40:
==דוגמה ==
נבחר את הראשוניים <math>\ p=211,q=227</math>, (שניהם שקולים ל-<math>\ 3</math> מודולו <math>\ 4</math>, במילים אחרות <math>\ 4|212</math> וכן <math>\ 4|228</math>). אז <math>\ n=pq=47897</math>, כך שהמפתח הפרטי של [[אליס ובוב|אליס]] הוא <math>\ (211,227)</math>, והמפתח הפומבי הוא <math>\ 47897</math>. (את הגורמים של 47897 אפשר למצוא בזמן קצר, אבל
[[אליס ובוב|בוב]] מעוניין להצפין את המסר <math>\ m=23</math> עבור אליס (למען הפשטות, נניח שהוא בוחר לבנות את המסר כמתואר להלן, כלומר משרשר את המסר פעמיים <math>\ m||m = 2323</math>), כדי להצפין את המסר הוא מחשב את <math>\ m^2\mbox{ mod }n=2323^2\mbox{ mod }47897=31865</math> ושולח את <math>\ c=31865</math> לאליס.
| |||