חידות מרקל

חידות מרקל הן מבנה של מערכת הצפנה הראשון שהומצא המיישם את רעיון המפתח הציבורי (public key). זהו פרוטוקול שיתוף מפתח שהומצא על ידי רלף מרקל ב-1974 וקרוי על שמו. כמו בפרוטוקול דיפי-הלמן, הפרוטוקול מאפשר לשני משתתפים לשתף ביניהם מפתח הצפנה סודי בערוץ פתוח שאינו מאובטח מבלי שיפגשו ומבלי שיהיה להם מידע מוקדם כמו סוד משותף. השיטה אינה מיושמת בפועל בשל חוסר יעילותה, חרף זאת מהווה דוגמה קלאסית לפרוטוקול מפתח ציבורי שאינו מבוסס על בעיה קשה מתורת המספרים כמו לוגריתם דיסקרטי, אלא רק אלגוריתם הצפנה סימטרי. כמו כן יש לזכור שהפרוטוקול בטוח רק כנגד ציתות פסיבי.

חידת מרקל

חידת מרקל היא הצפנת טקסט גלוי כלשהו המכיל בתוכו סוד מסוים, המוחלשת במכוון באופן שניתן יהיה לפענחה באמצעות כוח גס, במאמץ מסוים שהוא בפקטור שניתן לשליטה. הדרך הפשוטה להכנתה היא באמצעות צופן סימטרי, נניח AES. מצפינים מסר הכולל סוד (מפתח הצפנה חד-פעמי) באמצעות מפתח הצפנה מוחלש אותו מכינים מ- $n$ ספרות אקראיות והיתר מקבוע כלשהו שאינו סודי כמו מחרוזת אפסים. לדוגמה אם המפתח באורך 128 סיביות, והוא מורכב מ-96 אפסים מובילים ו-32 ספרות אקראיות סיבוכיות התקפת כוח גס כנגד הצופן, דהיינו ניסוי כל המפתחות האפשריים היא $2^{32}$ שזה בר ביצוע מבחינה מעשית, אך דורש מאמץ מסוים. אפשר לשלוט בכמות העבודה על ידי שינוי $n$ . כמו כן כדי שקל יהיה לדעת אם הפענוח הצליח, יש צורך להוסיף יתירות מכוונת כמו טקסט קבוע מוסכם מראש (למשל "חידה מספר..."). הטקסט הקבוע אינו סודי וידוע גם למצותת.

מחידה כזו אפשר לבנות פרוטוקול שיתוף מפתח כדלהלן; צד אחד נניח אליס מכינה חידות רבות, כאשר כל חידה היא הצפנה של מפתח-הצפנה סודי אקראי ומספר סידורי. שים לב שמדובר במפתח שונה מהמפתח שאיתו אליס מצפינה את החידה. כל חידה מכילה מפתח הצפנה סודי אחר ומוצפנת במפתח שונה, למעשה מספר החידות הוא כמספר המפתחות האפשריים בטווח $[0-2^{n}]$ . את החידות היא שולחת לצד השני נניח בוב. בוב בוחר באקראי חידה אחת אותה הוא מפענח בכוח גס, דהיינו מנסה את כל המפתחות האפשריים עד $2^{n}$ (במקרה הגרוע) עד שמוצא את המפתח הנכון, מחלץ את המפתח הסודי שבתוכה יחד עם המספר הסידורי, שולח את המספר הסידורי בחזרה לאליס ושומר את המפתח הסודי. אליס שהכינה את החידות בעצמה יודעת באמצעות המספר הסידורי איזו מהחידות פוענחה לכן יודעת איזה מפתח הצפנה ברשות בוב וכעת הם משתפים ביניהם את אותו מפתח.

המצותתת איב מסוגלת לראות את כל החידות ויכולה לפענח בדיוק כמו בוב כל חידה שתבחר כי כזכור משום שהמפתח קטן, פענוח חידה אחת בלי ידיעת המפתח, בר ביצוע. אך הבעיה היא שאינה יודעת איזו מהחידות בוב פיענח והמספר הסידורי מוסתר בתוך החידה, לכן עליה לנסות לפענח את כל החידות (או לפחות מחציתן במקרה הממוצע) כדי למצוא את המספר הסידורי שהחזיר בוב לאליס ואז לחלץ את המפתח שהם שיתפו ביניהם. אם אליס תשלח מספיק חידות זו תהיה משימה קשה. למעשה המאמץ מצד איב לפענוח כל החידות הוא בפקטור ריבועי ביחס לכמות העבודה שהושקעה מצד אליס ובוב.

תיאור הפרוטוקול

אליס ובוב מעוניינים לשתף ביניהם מפתח הצפנה סודי על מנת שיוכלו להתקשר זה עם זה בבטחה בערוץ פתוח. נניח לצורך הפרוטוקול שהם משתמשים בצופן AES עם מפתח 128 סיביות המיוצג כאן על ידי $E$ ונניח שכל מפתח $p_{i}$ בנוי משרשור מחרוזת של $128-n$ אפסים עם מספר אקראי כלשהו בגודל $n$ סיביות. עם מפתח זה אליס משתמשת כדי להצפין חידה אחת. מבנה החידה הוא מפתח אקראי סודי בגודל 128 סיביות המסומן כאן $K_{i}$ ומספר סידורי $i$ כשהם מוצפנים יחד עם טקסט קבוע כלשהו כמו ${\text{Puzzle }}\#$ . הם יפעלו כדלהלן:

אליס קובעת פקטור $n$ (למשל $n=32$ ), כך שהמאמץ הדרוש לפענוח חידה אחת יהיה $2^{n}$ .
בוחרת $2^{n}$ מספרים אקראיים $p_{i}\in \{0,1\}^{n}$ (בגודל $n$ סיביות). כל אחד מהם מרופד באפסים משלימים לקבלת אורך 128 סיביות: $p_{i}=0^{128-n}\|\ p_{i}$ .
בוחרת $2^{n}$ מפתחות הצפנה סודיים אקראיים $K_{i}$ (בגודל 128 סיביות).
מכינה $2^{n}$ חידות כדלהלן עבור $i=1,...,2^{n}$ החידה: ${\text{Puzzle}}_{i}=E_{p_{i}}({\text{''Puzzle }}\#{\text{''}}\ i\ \|\ K_{i})$ . הסימן $\|$ מייצג שרשור (הדבקת שתי מחרוזות למחרוזת אחת גדולה יותר).
שולחת את $2^{n}$ החידות לבוב.
בוב בוחר באופן אקראי חידה אחת ומפענח אותה באמצעות כוח גס ומחלץ את הטקסט הגלוי ${\text{''Puzzle }}\#{\text{i''}}$ ואת $K_{i}$ .
בוב מחזיר לאליס את המספר הסידורי של החידה $i$ ושומר בסוד את $K_{i}$ .
אליס מוצאת את המפתח המתאים למספר הסידורי $i$ וכעת הם משתפים ביניהם את $K_{i}$ מבלי שהמצותת יוכל לדעת.

סיבוכיות

נניח $N=2^{n}$ , מהפרוטוקול עולה שהמאמץ הדרוש לאליס להכנת כל החידות הוא $O(N)$ , כמו כן המאמץ הדרוש לבוב לפיענוח חידה אחת גם הוא $O(N)$ . אולם עבור המצותת איב המאמץ הדרוש לפתרון חידה אחת הוא $2^{n}$ וישנן $N$ חידות, במקרה הממוצע עליה לפענח לפחות מחצית מהן, כלומר $1/2N\cdot O(N)$ שזה $O(N^{2})$ . כלומר הוכח שקיים פער ריבועי של פקטור העבודה בין המשתתפים בפרוטוקול לבין המצותת, אך לא יותר מזה. מסיבה זו הפרוטוקול אינו יעיל, כיוון שלכל היותר מושג ביטחון ריבועי. למשל אם $N=2^{32}$ ביטחון המערכת הוא רק $2^{64}$ , שזה מעט ולא מצדיק את ההשקעה הדרושה מצד אליס ובוב. למרות זאת, עדיין אפשר לראות בשיטה כחלוצה ראשונה של תפישת המפתח הפומבי. רלף מרקל פיתח את שיטת החידות שלו כשהיה סטודנט בברקלי, וכבר אז צפה את הפוטנציאל הטמון במערכת מפתח פומבי, אולם לא הכול עמדו על חשיבותה. מאוחר יותר, כאשר דיפי והלמן פרסמו את עבודתם בנושא הצפנת מפתח ציבורי, ציינו שהרעיון של מרקל היווה בין היתר השראה עבורם לפיתוח מה שנודע לאחר מכן כפרוטוקול דיפי-הלמן שהוא כידוע תגלית דרמטית שהשפיעה כמעט יותר מכול על הקריפטוגרפיה המודרנית.