חלוקת סוד

בקריפטוגרפיה, חלוקת סוד (באנגלית: Secret sharing), היא בעיה של פיצולו של סוד בין קבוצת שותפים, באופן שאינו ידוע לאף אחד מהם לחוד וניתן לגלותו רק באמצעות שיתוף פעולה של כל או חלק מחברי הקבוצה. הסוד בהקשר של מדעי המחשב הוא ערך מספרי כלשהו ויכול להיות בעל חשיבות קריפטוגרפית כגון מפתח הצפנה או סיסמה. סכימת חלוקת סוד היא שיטה לפתרון בעיית חלוקת הסוד כך שניתן לחלק מידע נתון  ל- חלקים או שְׁתָפִים (באנגלית: Shares) , באופן כזה שניתן לשחזר את  בידיעת  חלקים בלבד, גם כאשר  חלקים הלכו לאיבוד. אולם לא ניתן לשחזר את הסוד בידיעה של רק  ממנו או ששחזורו קשה מאוד לביצוע ליריב בעל עוצמת חישוב מוגבלת. מאפיין זה נקרא סכימת סף  (באנגלית: Threshold scheme) כאשר . כאן  מייצג את סך כל השתפים ו- את המספר השתפים המינימלי הדרוש לשחזורו.

שימושים אפשריים

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

היסטוריה

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

בעיית חלוקת סוד כבעיה קומבינטורית

ניתן להמחיש את הבעיה הכללית של חלוקת סוד בעזרת בעיה קומבינטורית ידועה: אחד-עשר מדענים עובדים על פרויקט סודי אותו הם מעוניינים לשמור בכספת. מטעמי בטיחות כל מדען צריך לקבל מנעול ומפתח משלו, אולם למען הנוחות הם מעוניינים שדי יהיה בנוכחות שישה מהם כדי לפתוח את הכספת. מהו מספר המנעולים הקטן ביותר הדרוש להם? ומהו מספר המפתחות הקטן ביותר שכל מדען יידרש לשאת על מנת לאפשר זאת? הפתרון המתמטי (לפי נוסחת הבינום) מראה שמספר המנעולים הדרוש הוא 462 וכל מדען צריך לשאת 252 מפתחות. בדרך זו מובטח שכל תת-קבוצה של שישה מדענים תוכל לפתוח את הכספת. כמובן שפתרון זה אינו מעשי לאור העובדה שמספר המפתחות והמנעולים יגדל באופן מעריכי ככל שמספר המדענים יגדל (למשל למספר כפול של מדענים יידרשו לא פחות מ-74,613 מנעולים וכל מדען יאלץ לשאת 20,349 מפתחות לפחות).
כמובן שלא ניתן לפתור בעיה זו על ידי חלוקה פשוטו כמשמעו של הסוד לכל המשתתפים. למשל אם הסוד הוא מפתח הצפנה בגודל 64 סיביות אותו מעוניינים שני משתתפים לחלוק ביניהם. אם כל משתמש יקבל מחצית מהמפתח, קרי 32 סיביות. הרי שניחוש המפתח השלם באמצעות כוח גס על ידי המשתתף האחר או על ידי יריב במקרה שאחד נחשף מצריך רק  ניסיונות. בכללות עבור  סיביות ו- שתפים אפשר לנחש את הסוד ב- ניסיונות.

פנקס חד-פעמי

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

רעיון כללי

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

אלגוריתם

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