חלוקת סוד

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

בקריפטוגרפיה, חלוקת סוד - Secret sharing, היא בעיה של פיצולו של סוד בין קבוצת שותפים, באופן שאינו ידוע לאף אחד מהם לחוד וניתן לגלותו רק באמצעות שיתוף פעולה של כל או חלק מחברי הקבוצה. הסוד בהקשר של מדעי המחשב הוא ערך מספרי כלשהו ויכול להיות בעל חשיבות קריפטוגרפית כגון מפתח הצפנה או סיסמה. סכימת חלוקת סוד היא שיטה לפתרון בעיית חלוקת הסוד כך שניתן לחלק מידע נתון $\ D$ ל-$\ n$ חלקים או שְׁתָפִים (Shares באנגלית) $\ D_{1},D_{2},...D_{n}$, באופן כזה שניתן לשחזר את $\ D$ בידיעת $\ k$ חלקים בלבד, גם כאשר $\ k-1$ חלקים הלכו לאיבוד. אולם לא ניתן לשחזר את הסוד בידיעה של רק $\ k-1$ ממנו או ששחזורו קשה מאד לביצוע ליריב בעל עצמת חישוב מוגבלת. מאפיין זה נקרא סכימת סף $\ (n,k)$ (באנגלית Threshold scheme) כאשר $\ n=2k-1$. כאן $\ n$ מייצג את סך כל השתפים ו-$\ k$ את המספר השתפים המינימלי הדרוש לשחזורו.

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

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

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

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

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

היסטוריה

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

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

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

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

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

תכונות

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

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

פנקס חד-פעמי

קיימת שיטה פשוטה לחלוקת סוד עבור המקרה $\ 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}$, פחות מכך התוצאה שתתקבל תהיה חסרת תועלת לחלוטין.

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

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

רעיון כללי

המנגנון מבוסס על תכונה ידועה של פולינומים; בהינתן $\ 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_{1}x+...+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)$.

אלגוריתם

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

חלוקת הסוד על ידי הצד השלישי

1. בוחר ראשוני $\ p$ הגדול מהסוד $\ S$ ומ-$\ n$ ומגדיר את $\ a_{0}=S$.
2. בוחר $\ t-1$ מקדמים אקראיים בלתי תלויים $\ a_{1},...,a_{t-1}$ הנמוכים מ-$\ p$ ומכין את הפולינום $\textstyle \ f(x)=\sum _{j=0}^{t-1}a_{j}x^{j}$.
3. מחשב את $\ S_{i}=f(i){\mbox{ mod }}p$ עבור כל $\ n$ המשתמשים (או עבור כל הנקודות עד $\ p-1$) ושולח את החלקים $\ S_{i}$ לכל משתמש $\ P_{i}$ בהתאמה, יחד עם המציין $\ i$ (המציין של כל משתמש יהיה פומבי). כך כל נקודה $\ (x,y)$ מיוצגת על ידי $\ (i,S_{i})$.

שחזור הסוד על ידי $\ t$ משתמשים (או יותר)

1. אוספים את הנקודות $\ (x,y)=(i,S_{i})$ של כל $\ t$ המשתמשים כדי לחשב את המקדמים $\ a_{j}$ המקבילים ובעזרת אינטרפולציה של לגראנז' להלן, משחזרים את הסוד שהוא $\ f(0)=a_{0}=S$.
2. לפי נוסחת לגראנז' הסוד $\ S$ מחושב על ידי:

$\ S=\sum _{i=1}^{t}c_{i}y_{i}$

כאשר $\ y_{i}$ הוא השתף של המשתמש $\ i$ ו-$\ c_{i}$ מחושב כך:

$\ c_{i}=\prod _{1\leq j\leq t,j\neq i}{x-x_{j} \over x_{i}-x_{j}}$

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

חלוקת סוד בעזרת משפט השאריות הסיני

אחד הרעיונות לשימוש ב-CRT ככלי לחלוקת סוד הוצע על ידי Asmuth-Bloom ב-1983. תחילה מכינים סדרה עולה של שלמים חיוביים זרים זה לזה $p_{0},p_{1}<\cdots <p_{n}$ שמקיימת:

$\ p_{0}\cdot \prod _{i=0}^{k-2}p_{n-i}<\prod _{i=1}^{k}p_{i}$

ואז בהינתן סדרה פומבית כזו וסוד $S$ המיועד לחלוקה בין $n$ חברים, כאשר $S<p_{0}$, האלגוריתם פועל כדלהלן:

1. מכינים $n$ שתפים $I_{1},I_{2},...,I_{n}$ כדלקמן $I_{i}=(S+\gamma \cdot p_{0})\ {\mbox{mod}}\ p_{i}$. כאשר $\gamma$ שלם אקראי כלשהו המקיים $S+\gamma \cdot p_{0}<\prod _{i=1}^{n}p_{i}$.
2. בהינתן תת-קבוצה של $k$ שתפים מתוך $n$, הסוד $S$ ניתן לחילוץ על ידי $S=x\ {\mbox{mod}}\ p_{0}$, כאשר את $x$ מחשבים על ידי פתרון מערכת הקונגרואנציות כפתרון יחיד מודולו $p_{i_{1}}\cdots p_{i_{k}}$:

$\left\{{\begin{array}{lr}x\equiv &I_{i_{1}}\ {\mbox{mod}}\ p_{i_{1}}\\\vdots &\ \\x\equiv &I_{i_{k}}\ {\mbox{mod}}\ p_{i_{k}}\end{array}}\right.$

ישנן שיטות יעילות לחישוב CRT. השיטה הישירה לפי גאוס מוצאת פתרון בסיבוכיות זמן של $\ O(({\mbox{lg}}\ n)^{2})$ פעולות בסיביות. בשיטה זו הפתרון הוא $\textstyle x=\sum _{j=1}^{k}{(I_{i})}_{j}N_{j}M_{j}\ {\mbox{mod}}\ p'$ כאשר $p'=p_{i_{1}}\cdot p_{i_{2}}\cdots p_{i_{k}}$ וכן $N_{j}=p'/p_{j}$ ו-$M_{j}=N_{j}^{-1}\ ({\mbox{mod}}\ p_{j})$. כלומר $x$ הוא סכום הכפולות של השתפים הנוטלים חלק בשחזור הסוד והערכים $M_{j},N_{j}$ בהתאמה, המחושבים מודולו הכפולה של המודולים המקבילים להם. והערך $M_{j}$ הוא הופכי כפלי מודולרי של $N_{j}$ אותו אפשר לחשב על ידי אלגוריתם אוקלידס המורחב.

דוגמה במספרים קטנים

דוגמה במספרים קטנים לסכימת סף (5,3). יהי הסוד $S=123$ ונתונה הסדרה $p=\{991,1049,1249,1423,1553\}$ עבור $n=5$ משתתפים וכן $p_{0}=571$ שים לב שמתקיים התנאי $p_{0}\cdot p_{4}\cdot p_{5}<p_{1}\cdot p_{2}\cdot p_{3}$. אם נבחר $\gamma =4445$ תוצאת חישוב השתפים תהיה $u=\{267,687,250,1009,616\}$ כעת אם תת-קבוצה של $k=3$ חברים, נניח: $u_{2}$, $u_{3}$ ו-$u_{5}$ מעוניינים לשחזר את הסוד תחילה עליהם לפתור את מערכת הקונגרקואנציות:

$x\equiv 687\ ({\mbox{mod}}\ 1,049)$

$x\equiv 250\ ({\mbox{mod}}\ 1,249)$

$x\equiv 616\ ({\mbox{mod}}\ 1,553)$

קיים פתרון יחיד $x=2,538,218\ ({\mbox{mod}}\ p'=2,034,742,153)$ והסוד הוא $x\ {\mbox{mod}}\ 571=123$. שיתוף פעולה של פחות מ-$k$ חברים לא יחשוף שום מידע לגבי הסוד.

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

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

• חלוקת סוד עם מאפיין אימות; שיטת חלוקת סוד המאפשרת למנוע ממשתתף אחד לשקר בקשר לסודו, על מנת לחלץ מידע מהמשתתפים האחרים. טל רבין ומיכאל בן-אור הציעו שיטה כזו המבוססת על בעיית חישוב רב-משתתפים בטוח כמו בעיית המליונר. בשיטה זו ניתן למנוע רמאות של עד שליש מהמשתתפים.
• חלוקת סוד במערכת הצבעה אלקטרונית מבוזרת; ניתן ליישם את רעיון חלוקת הסוד במנגנון הצבעה אלקטרונית (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, מסת"ב 1-58488-508-4

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

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