שני חברים רוצים להעביר כסף מאחד לשני, באמצעות שירות חבילות, אך לרוע המזל השירות מורכב מעבריינים רבים. שירות החבילות יעביר תמיד את החבילה, אך אם יש באפשרותו הוא יגנוב את תכולתה. לכן כל אחד מהחברים הצטייד במפתחות ומנעולים, כך שיוכל לנעול את החבילות שהוא שולח, באופן ששירות החבילות לא יוכל לפתוח את החבילה בדרך, אבל לרוע המזל גם החבר השני לא יוכל לפתוח את החבילה, משום שלאף אחד מהם אין מפתח לאחד מהמנעולים של רעהו. האם אפשר למצוא דרך שבה החברים יוכלו בכל זאת לשלוח כסף אחד לשני?
| פתרון
|
| הפתרון לחידה נקרא "אלגוריתם שלושת המעברים של שמיר" (Shamir's three-pass protocol) על שם ממציאו, עדי שמיר.
החבר הראשון שם את הכסף בחבילה, נועל אותה באחד המנעולים שלו. החבר השני איננו יכול לפתוח את החבילה אך הוא נועל את החבילה במנעול נוסף ושולח חזרה אל החבר הראשון. החבר הראשון פותח את המנעול שלו, שולח חזרה, החבר השני יכול עתה להסיר את המנעול שלו ולפתוח את החבילה.
שמיר הוא אחד משלושת הממציאים של שיטת ההצפנה RSA, שיטת הצפנה במפתח ציבורי. פיתוחה של שיטת הצפנה זו ואחרות שאבה השראה מחידות מסוג זה.
|
|