חלוקת סוד

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

בקריפטוגרפיה, חלוקת סוד - Secret sharing, היא בעיה של פיצולו של סוד בין קבוצת שותפים, באופן שאינו ידוע לאף אחד מהם לחוד וניתן לגלותו רק באמצעות שיתוף פעולה של כל או חלק מחברי הקבוצה. הסוד בהקשר של מדעי המחשב הוא מידע המיוצג כערך מספרי. הסוד יכול להיות מידע בעל חשיבות קריפטוגרפית, למשל מפתח הצפנה או סיסמה. שיטת חלוקת סוד או סכימת חלוקת סוד פותרת את הבעיה האמורה בכך שהיא מאפשרת לחלק את המידע הנתון $\ D$ ל-$\ n$ חלקים או שתפים (shares באנגלית) $\ D_1,D_2,...D_n$, באופן כזה שניתן לשחזר את $\ D$ בקלות גם בידיעת רק $\ k$ חלקים ממנו, אולם אפילו ידיעה של $\ k-1$ חלקים אינה חושפת מאומה בקשר לסוד. שיטת חלוקת סוד עם מאפיין זה נקראת סכימת סף $\ (n,k)$ (באנגלית: Threshold scheme) כאשר $\ n=2k-1$. כאן $\ n$ מייצג את מספר חלקי הסוד הכולל ו-$\ k$ את המספר החלקים המינימלי הדרוש לשחזורו. בשיטה זו אפשר לשקם את $\ D$ גם כאשר $\ k-1$ חלקים ממנו הלכו לאיבוד, כל עוד השתמרו $\ k$ חלקים כלשהם. למרות זאת היריב אינו יכול לשחזר את הסוד או שהשחזור יהיה קשה מאוד לביצוע ליריב בעל עצמת חישוב מוגבלת, גם אם בשל פרצה כלשהי עלה בידו להשיג $\ k-1$ חלקים.

שימושים מעשיים

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

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

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

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

בעיית חלוקת סוד ובעיית הסף

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

כמובן שלא ניתן לפתור בעיה זו על ידי חלוקה פשוטו כמשמעו של הסוד לכל המשתתפים. למשל אם הסוד הוא מפתח הצפנה בגודל 64 סיביות אותו מעוניינים שני משתתפים לחלוק ביניהם. אם כל משתמש יקבל מחצית מהמפתח, קרי 32 סיביות. הרי שניחוש המפתח השלם באמצעות כוח גס מצד כל אחד מהמשתתפים מצריך רק $\ 2^{32}$ נסיונות. בכללות עבור $\ r$ סיביות ו-$\ t$ משתתפים כל משתתף יוכל לנחש את המפתח ב-$\ 2^{r/t}$ נסיונות. שזה הרבה יותר קל מניחוש המפתח כולו.

קיימת שיטה פשוטה לחלוקת סוד עבור המקרה $\ n=t$, כלומר כאשר יש צורך בכל השתפים על מנת לשחזר את הסוד. שיטה זו מושלמת מהיבט של תורת האינפורמציה והיא מבוססת על פנקס חד פעמי כדלהלן: הסוד מקודד כמחרוזת סיביות ועבור $\ t$ משתתפים מייצרים $\ t-1$ רצפים אקראיים $\ S_1,S_2,...,S_{t-1}$ וכל משתתף $\ P_i$ למעט האחרון יקבל אחד מהם בהתאם. כאשר המשתתף האחרון $\ P_t$ יקבל את $\ S_t=S\oplus S_1\oplus S_2\oplus,...,\oplus S_{t-1}$. כלומר חיבור מודולו 2 (XOR) של כל הערכים האקראיים עם הסוד. לא קשה להוכיח כי מאקראיות השתפים האחרים נובע שגם $\ S_t$ אקראי ולכן אינו מכיל בפני עצמו כל מידע על הסוד. רק שיתוף פעולה של כל המשתתפים כלומר רק חיבור XOR של כל הערכים האקראיים יניב את תוצאה הרצויה; כלומר $\ S=S_1\oplus S_2\oplus...\oplus S_t$, פחות מכך התוצאה שתתקבל תהיה חסרת תועלת לחלוטין. החסרון הוא כאמור בצורך בשיתוף פעולה של כולם, בדרך זו אין אפשרות לשחזר את הסוד על ידי מספר קטן יותר של משתתפים. עובדה היוצרת בעיה בהיעדר אחד המשתתפים (כגון במקרה של מחלה או מוות פתאומי) או כאשר אחד מהם אינו מעוניין לשתף פעולה.

היסטוריה

הצורך בחלוקת סוד התעורר בהקשר של ניהול מפתחות הצפנה בסביבות 1977. עדי שמיר וג'ורג' בלקלי פרסמו בנפרד את רעיונות חלוקת הסוד בשנת 1979. עדי שמיר במאמרו "איך לשתף סוד" הסביר את עקרונות השיטה; חלוקת סוד, פיזור סמכויות וסכימת-סף והציע דרך מעשית ליישום מנגנון חלוקת סוד באמצעות אינטרפולציה של פולינומים. הרעיון של עדי שמיר (ראו להלן) מבוסס על תכונה ידועה של פולינומים; בהינתן $\ k$ נקודות במישור דו-ממדי $\ (x_i,y_i),...,(x_k,y_k)$ עם קואורדינטות $\ x_i$ שונות, קיים פולינום אחד ויחיד $\ q(x)$ מסדר $\ k-1$ המקיים $\ q(x_i)=y_i$, עבור כל שלם $\ i$ (למשל - דרך שתי נקודות עובר קו יחיד, דרך שלוש נקודות עוברת פרבולה יחידה וכן הלאה). כדי לחלק את הסוד $\ D$ ל-$\ n$ משתתפים בוחרים פולינום אקראי מסדר $\ k-1$ המוגדר: $\ q(x)=a_0+a_1x+...+a_{k-1}x^{k-1}$, קובעים את $\ a_0=D$ (הסוד עצמו) ואז מחלקים לכל אחד את ערך הפולינום בנקודה $\ i$ באופן זה: $\ D_i=q(i),...,D_n=q(n)$ בהתאם למספר המשתתפים (למעט $\ D_0$). בהינתן כל תת-קבוצה $\ k$ של נקודות ($\ D_i$ עם מציין $\ i$) ולא חשוב איזה מהם, ניתן לשחזר את הפולינום $\ q(x)$ ולכן לשחזר את הסוד $\ D=q(0)$. מאידך $\ k-1$ ערכים כאלו אינם מספיקים. חישוב המקדמים $\ a_i$ על ידי $\ k$ הנקודות אפשרי על ידי אינטרפולצית לגראנג' (ראו להלן). שמיר המחיש את הרעיון באמצעות ארתימטיקה מודולרית בשדות סופיים ולא בשדות ממשיים או שדה המספרים המרוכבים וזאת הן בשל הנוחות שביישום ממוחשב של שדות אילו והן מטעמי בטיחות. קבוצת השלמים מודולו מספר ראשוני גדול, מהווה שדה סופי שבו אינטרפולציה פשוטה לביצוע ואפשר להוכיח שהוא מספק רמת בטיחות גבוהה. קיימים אלגוריתמים לאינטרפולציה בשדות מסדר ראשוני בסיבוכיות של $\ O(n\mbox{log}^2 n)$ (ראו קאנות').

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

תכונות

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

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

מנגנון סכימת-סף (n,t) של עדי שמיר

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

1. בוחר ראשוני $\ p$ הגדול מהסוד $\ S$ ומ-$\ n$ ומגדיר את $\ a_0=S$.
2. בוחר $\ t-1$ מקדמים אקראיים בלתי תלויים $\ a_1,...,a_{t-1}$ הנמוכים מ-$\ p$ ומכין את הפולינום $\ f(x)=\sum_{j=0}^{t-1} a_jx^j$.
3. מחשב את $\ S_i=f(i)\mbox{ mod }p$ עבור כל $\ n$ המשתמשים (או עבור כל הנקודות עד $\ p-1$) ושולח את החלקים $\ S_i$ לכל משתמש $\ P_i$ בהתאמה, יחד עם המציין $\ i$ (המציין של כל משתמש יהיה פומבי). כך כל נקודה $\ (x,y)$ מיוצגת על ידי $\ (i,S_i)$.
4. שחזור הסוד מתבצע על ידי $\ t$ משתמשים או יותר כדלהלן: אוספים את הנקודות $\ (x,y)=(i,S_i)$ של כל $\ t$ המשתמשים כדי לחשב את המקדמים $\ a_j$ המקבילים ובעזרת אינטרפולציה של לגראנז' להלן, משחזרים את הסוד שהוא $\ f(0)=a_0=S$.
5. לפי נוסחת לגראנז' הסוד $\ S$ מחושב על ידי:

$\ S=\sum_{i=1}^t c_iy_i$

כאשר $\ y_i$ הוא השתף של המשתמש $\ i$ ו-$\ c_i$ מחושב כך:

$\ c_i=\prod_{1\le j\le t, j\ne i} {x_j\over x_j-x_i}$

שהוא צירוף לינארי של כל המציינים $\ i$ של הקבוצה $\ t$. שים לב שערכי $\ c_i$ קבועים ואינם תלויים בסוד על כן ניתן לחשבם מראש, אם הערך $\ t$ קבוע.

שימושים נוספים בחלוקת סוד

ניתן ליישם חלוקת סוד במספר שיטות מתקדמות, עם מאפיינים נוספים כגון:

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

לקריאה נוספת

• Amos Beimel, Secret-Sharing Schemes: A Survey, 2011.
• G. R. Blakley, "Safeguarding cryptographic keys", in proceedings of the National Computer Conference, 48, pp 313–317, 1979.
• Adi Shamir, How to share a secret, Communications of the ACM, 22(1), pp612–613, 1979
• Chapter 13 of Cryptography: Theory and Practice (Third Edition) by Douglas R. Stinson, Chapman & Hall, ISBN 1-58488-508-4

קישורים חיצוניים

• גדי אלכסנדרוביץ', שיתוף, זה כל הסוד, באתר "לא מדויק"