להמשיך ללכת, אין מה לראות פה

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

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

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

שאלה טכנית בסיסית שצצה כעת היא למה הכוונה ב”לשים תמונות זו על זו” - הרי התמונה שלמעלה פשוט “מוחקת” את התמונה שמתחתיה. לכן הרעיון הוא להתייחס ללבן לא כאל צבע לבן, אלא כאל צבע “שקוף”; אם שמים שתי תמונות זו מעל זו, כך שבפיקסל מסויים בתמונה התחתונה הצבע הוא שחור, ובפיקסל המתאים בתמונה העליונה הפיקסל הוא שקוף, התוצאה הסופית תהיה פיקסל שחור. פיזית אפשר לממש את זה על ידי הדפסה על שקפים - השחור יודפס, הלבן לא. במחשב ניתן לראות את זה בכל תוכנת ציור שתומכת בשקיפות (התוכנה הפשוטה שאני משתמש בה בלינוקס, Kolourpaint, תומכת בזאת). הנה הנחיה למשתמשי חלונות: יש בצייר של ווינדוס בצד למטה (מתחת לכל כלי הציור) שתי תמונות של גליל כחול, תיבה ירוקה וכו’. צריך ללחוץ על הנמוכה יותר. כדי להעתיק את התמונות לשם מספיק ללחוץ עליהן עם הכפתור הימני, לבחור copy, ואז להדביק בתוך הצייר.

לפני שאמשיך, הנה דוגמה לאיך זה עובד. קחו את שתי התמונות הבאות ונסו להדביק אותן זו על זו כשלבן משמש כצבע שקוף:

על פניו זה נראה כאילו אני צוחק עליכם והעליתי שתי תמונות זהות. עם זאת, כששמים אותן זו על זו, זה מה שמקבלים:

מה הולך כאן? זו בפירוש לא תמונה מונוכרומטית “סטנדרטית”. למעשה, המקור של התמונה הזו היה התמונה המונוכרומטית הבאה של הומר סימפסון:

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

אם כן, זהו, בצורה ויזואלית, התעלול שבו משתמשים נאור ושמיר: שגם איזור כהה עדיין יכול להיחשב “לבן” אם יש איזורים כהים ממנו לידו. כעת אפשר גם לתת הסבר מעט יותר מפורט.

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

הנה כמה דוגמאות לפיקסלים שונים שיכולים להיווצר על ידי צביעת חלק מתת-הפיקסלים:

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

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

שימו לב שעדיין נשארתי עם דרגת חופש כלשהי. נניח שאני רוצה לחלק פיקסל לבן - האם בשנים החלקים אני אשים פיקסל שצבוע בשחור בצד שמאל, או שאצבע אותו בשחור דווקא מצד ימין? התשובה היא שאני מגריל את הבחירה שלי. באופן דומה, כשאני רוצה לחלק פיקסל שחור אני יודע שאני צריך להשתמש בפיקסל אחד שצבוע בשחור משמאל ובאחר שצבוע משחור מימין; אבל אף אחד לא אומר לי להשתמש בפיקסל שצבוע בשחור משמאל דווקא בחלק הראשון; אני יכול להשתמש בו בכל אחד מהחלקים במידה שווה. גם פה, אני מגריל את הבחירה שלי.

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

חדי העין שמכירים קצת קריפטוגרפיה ודאי מזהים כאן פנקס חד פעמי. אכן, מה שאני עושה בפועל כדי לייצר את שני החלקים הוא הדבר הבא: אני מגריל לכל פיקסל בחלק מס’ 1 האם השחור יהיה בו בצד שמאל, או שמא בצד ימין - כלומר, חלק מס’ 1 הוא הפנקס. חלק מס’ 2 הוא מה שמתקבל מביצוע xor של הפנקס עם התמונה: אם בפיקסל מסויים תמונה היה צבע לבן (שמקביל דווקא ל-0 במקרה הזה), אז בחלק מס’ 2, באותו הפיקסל יהיה בדיוק את אותו פיקסל כמו בחלק מס’ 1. אם בפיקסל בתמונה היה צבע שחור, אז יהיה בחלק מס’ 2 פיקסל הפוך לזה של חלק מס’ 1.

זה מסיים את תיאור השיטה הבסיסית, אבל נאור ושמיר הציעו כבר באותו מאמר הרחבה שהיא מגניבה פי כמה וכמה. הרעיון הבסיסי נותר זהה, אך במקום ששני החלקים ייראו כמו ג’יבריש, אפשר לגרום לשניהם להציג תמונות; והתמונות הללו יכולות להיות שרירותיות ונתונות לבחירתנו, ובוודאי שאינן תלויות בתמונה ה”משולבת”. הנה דוגמה:

נסו לשים את התמונות זו על זו וראו מה קורה. מה התעלול כאן? אין שום דבר חדש, אלא רק הרחבה של הרעיון הקודם. ראשית, אם קודם, בתוצר הסופי לבן היה פיקסל שהוא חצי לבן, ושחור היה פיקסל שהוא שחור לגמרי, כאן אנחנו קצת יותר קיצוניים - בתוצר הסופי לבן הוא פיקסל שהוא שלושת-רבעי שחור, ואילו שחור הוא פיקסל שהוא שחור כולו. כפי שקל לראות אם משלבים את התמונות, מספיק רבע פיקסל לבן כדי ליצור הפרדת גוונים מהותית.

בתוך החלקים עצמם, לעומת זאת, אנחנו קצת יותר שמרנים: לבן הוא פיקסל ששלושת-רבעי או חצי ממנו הוא לבן, ושחור הוא פיקסל ששלושת-רבעי ממנו שחור. לא קשה לראות שלכל קומבינציה של “צבע במקור מס’ 1/צבע במקור מס’ 2/צבע בתמונה שמחלקים” אפשר למצוא פיקסלים מתאימים; למשל, לקומבינציה של “לבן-שחור-שחור” אפשר לבחור את הפיקסלים שבתוך החלקים להיות הפיקסלים בתמונות הדוגמה שהבאתי למעלה - הזה שהוא שלושת-רבעי לבן, והזה שהוא שלושת-רבעי שחור. ברור שאם נשים את האחד על השני, נקבל משהו שהוא שחור לגמרי; ואם נרצה לטפל ב”לבן-שחור-לבן”, פשוט נסובב את אחד משני הפיקסלים, ואז כשנשים אותם זה על זה נקבל פיקסל שלושת-רבעי שחור בלבד - כלומר, “לבן”.

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

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

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