חלוקת סוד

שגיאה ביצירת תמונה ממוזערת:

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

בקריפטוגרפיה, חלוקת סוד - Secret sharing, היא בעיה של פיצולו של סוד בין קבוצת שותפים, באופן שאינו ידוע לאף אחד מהם לחוד וניתן לגלותו רק באמצעות שיתוף פעולה של כל או חלק מחברי הקבוצה. הסוד בהקשר של מדעי המחשב הוא ערך מספרי כלשהו ויכול להיות בעל חשיבות קריפטוגרפית כגון מפתח הצפנה או סיסמה. סכימת חלוקת סוד היא שיטה לפתרון בעיית חלוקת הסוד כך שניתן לחלק מידע נתון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ D} ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} חלקים או שְׁתָפִים (Shares באנגלית) הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ D_1,D_2,...D_n} , באופן כזה שניתן לשחזר את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ D} בידיעת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k} חלקים בלבד, גם כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k-1} חלקים הלכו לאיבוד. אולם לא ניתן לשחזר את הסוד בידיעה של רק הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k-1} ממנו או ששחזורו קשה מאד לביצוע ליריב בעל עצמת חישוב מוגבלת. מאפיין זה נקרא סכימת סף הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (n,k)} (באנגלית Threshold scheme) כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n=2k-1} . כאן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} מייצג את סך כל השתפים ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k} את המספר השתפים המינימלי הדרוש לשחזורו.

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

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

שימוש נוסף לשיטת חלוקת סוד הוא פיזור סמכויות. כגון מורשי חתימה בארגון, שברשות כל אחד מהם מפתח חתימה דיגיטלית. אם כל מורשה יחזיק בעותק של מפתח החתימה הסודי של הארגון זה יהיה נוח אך יוצר סיכון לשימוש בלתי הולם מצד אחד המורשים. אם יוחלט שדרושות חתימות כל המורשים יחדיו כדי שהחתימה תהיה תקפה, הסיכון נמוך כי לא סביר שכל מורשי החתימה יקשרו קשר נגד הארגון, אולם לא נוח במקרים בהם אחד המורשים אינו זמין. הדרך האידאלית היא לחייב שיתוף פעולה של לפחות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} מורשים כלשהם כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle k\le n} . קל ליישם זאת עם סכימת סף הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (n,k)} . באופן זה יקטן הסיכון להונאה כיוון שדרוש שיתוף פעולה של מספר גורמים.

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

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

היסטוריה

הצורך בחלוקת סוד התעורר בהקשר של ניהול מפתחות הצפנה בסביבות 1977. עדי שמיר וג'ורג' בלקלי פרסמו בנפרד את רעיונות חלוקת הסוד בשנת 1979. עדי שמיר במאמרו "איך לשתף סוד" הסביר את עקרונות השיטה; חלוקת סוד, פיזור סמכויות וסכימת-סף והציע דרך מעשית ליישום מנגנון חלוקת סוד באמצעות אינטרפולציה של פולינומים. הרעיון של עדי שמיר (ראו להלן) מבוסס על תכונה ידועה של פולינומים; דרך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k} נקודות עובר רק פולינום יחיד מסדר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k-1} . (למשל - דרך שתי נקודות עובר קו יחיד, דרך שלוש נקודות עוברת פרבולה יחידה וכן הלאה).

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

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

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

כמובן שלא ניתן לפתור בעיה זו על ידי חלוקה פשוטו כמשמעו של הסוד לכל המשתתפים. למשל אם הסוד הוא מפתח הצפנה בגודל 64 סיביות אותו מעוניינים שני משתתפים לחלוק ביניהם. אם כל משתמש יקבל מחצית מהמפתח, קרי 32 סיביות. הרי שניחוש המפתח השלם באמצעות כוח גס על ידי המשתתף האחר או על ידי יריב במקרה שאחד נחשף מצריך רק הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 2^{32}} ניסיונות. בכללות עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ r} סיביות ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t} שתפים אפשר לנחש את הסוד ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 2^{r/t}} ניסיונות.

תכונות

סכמת חלוקת סוד תקרא מושלמת אם אף קבוצה לא מורשית של משתתפים לא תוכל להסיק כל מידע ביחס לסוד מהחלקים שניתנו לחבריה. כלומר בהינתן רק הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k-1} חלקים או פחות, הסוד יכול להיות כל ערך בהסתברות שווה. סכימת הסף של עדי שמיר נקראת מושלמת בהקשר זה. יתירה מזו בניגוד לשיטות קריפטוגרפיות אחרות, שיטת שמיר אינה מסתמכת על השערות בלתי מוכחות כלשהן כגון בעיות מתמטיות פתוחות מתורת המספרים. בנוסף סכימת-הסף של עדי שמיר מקיימת את התכונות הבאות:

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

פנקס חד-פעמי

קיימת שיטה פשוטה לחלוקת סוד עבור המקרה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n=t} , כלומר כאשר יש צורך בכל השתפים על מנת לשחזר את הסוד. שיטה זו מושלמת מהיבט של תורת האינפורמציה והיא מבוססת על פנקס חד פעמי כדלהלן: הסוד מקודד כמחרוזת סיביות ועבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t} משתתפים מייצרים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t-1} רצפים אקראיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ S_1,S_2,...,S_{t-1}} וכל משתתף הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ P_i} למעט האחרון יקבל אחד מהם בהתאם. כאשר המשתתף האחרון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ P_t} יקבל את $\ S_{t}=S\ \oplus \ S_{1}\ \oplus \ S_{2}\ \oplus ,\ ...,\ \oplus \ S_{t-1}$. כלומר חיבור מודולו 2 (XOR) של כל הערכים האקראיים עם הסוד. לא קשה להוכיח כי מאקראיות השתפים האחרים נובע שגם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ S_t} אקראי ולכן אינו מכיל בפני עצמו כל מידע על הסוד. רק שיתוף פעולה של כל המשתתפים כלומר רק חיבור XOR של כל הערכים האקראיים יניב את תוצאה הרצויה; כלומר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ S=S_1\oplus S_2\oplus...\oplus S_t} , פחות מכך התוצאה שתתקבל תהיה חסרת תועלת לחלוטין.

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

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

רעיון כללי

המנגנון מבוסס על תכונה ידועה של פולינומים; בהינתן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k} נקודות במישור דו-ממדי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (x_i,y_i),...,(x_k,y_k)} עם קואורדינטות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x_i} שונות, קיים פולינום אחד ויחיד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ q(x)} מסדר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k-1} המקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ q(x_i)=y_i} , עבור כל שלם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ i} .

כדי לחלק את הסוד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ D} ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} משתתפים בוחרים פולינום אקראי מסדר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k-1} המוגדר: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ q(x)=a_0+a_1x+...+a_{k-1}x^{k-1}} , קובעים את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a_0=D} (הסוד עצמו) ואז מחלקים לכל אחד את ערך הפולינום בנקודה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ i} באופן זה: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ D_i=q(i),...,D_n=q(n)} בהתאם למספר המשתתפים (למעט הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ D_0} ). בהינתן כל תת-קבוצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k} של נקודות (הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ D_i} עם מציין הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ i} ) ולא חשוב איזה מהם, ניתן לשחזר את הפולינום הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ q(x)} ולכן לשחזר את הסוד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ D=q(0)} . מאידך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k-1} ערכים כאלו אינם מספיקים. חישוב המקדמים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a_i} על ידי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k} הנקודות אפשרי על ידי אינטרפולצית לגראנג'. שמיר המחיש את הרעיון באמצעות חשבון מודולרי בשדות סופיים ולא בשדות ממשיים או שדה המספרים המרוכבים, הן בשל הנוחות שביישום ממוחשב של שדות אילו והן מטעמי בטיחות. קבוצת השלמים מודולו מספר ראשוני גדול מהווה שדה סופי, שבו אינטרפולציה היא פשוטה לביצוע, ואפשר להוכיח שהוא מספק רמת בטיחות גבוהה. קיימים אלגוריתמים לאינטרפולציה בשדות מסדר ראשוני בסיבוכיות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(n\mbox{log}^2 n)} .

אלגוריתם

מנגנון חלוקת סוד של עדי שמיר מאפשר לחלק סוד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ S} בין הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} משתמשים באופן כזה שכל קבוצה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t} משתמשים תוכל לצרף את חלקם יחד ולשחזר את הסוד. ניתן ליישם את המנגנון כך שהמשתמשים מסתייעים בצד שלישי שתפקידו לבחור את הסוד בעצמו ולחלקו בין המשתמשים בדרך בטוחה, כך שכל משתמש מכיר רק את חלקו בסוד.

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

1. בוחר ראשוני הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p} הגדול מהסוד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ S} ומ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} ומגדיר את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a_0=S} .
2. בוחר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t-1} מקדמים אקראיים בלתי תלויים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a_1,...,a_{t-1}} הנמוכים מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p} ומכין את הפולינום הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textstyle \ f(x)=\sum_{j=0}^{t-1} a_jx^j} .
3. מחשב את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ S_i=f(i)\mbox{ mod }p} עבור כל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} המשתמשים (או עבור כל הנקודות עד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p-1} ) ושולח את החלקים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ S_i} לכל משתמש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ P_i} בהתאמה, יחד עם המציין הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ i} (המציין של כל משתמש יהיה פומבי). כך כל נקודה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (x,y)} מיוצגת על ידי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (i,S_i)} .

שחזור הסוד על ידי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t} משתמשים (או יותר)

1. אוספים את הנקודות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (x,y)=(i,S_i)} של כל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t} המשתמשים כדי לחשב את המקדמים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a_j} המקבילים ובעזרת אינטרפולציה של לגראנז' להלן, משחזרים את הסוד שהוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ f(0)=a_0=S} .
2. לפי נוסחת לגראנז' הסוד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ S} מחושב על ידי:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ S=\sum_{i=1}^t c_iy_i}

כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y_i} הוא השתף של המשתמש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ i} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ c_i} מחושב כך:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ c_i=\prod_{1\le j\le t, j\ne i} {x-x_j\over x_i-x_j}}

שהוא צירוף לינארי של כל המציינים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ i} של הקבוצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t} . שים לב שערכי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ c_i} קבועים ואינם תלויים בסוד על כן ניתן לחשבם מראש, אם הערך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t} קבוע.

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

אחד הרעיונות לשימוש ב-CRT ככלי לחלוקת סוד הוצע על ידי Asmuth-Bloom ב-1983. תחילה מכינים סדרה עולה של שלמים חיוביים זרים זה לזה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_0, p_1 < \cdots < p_n} שמקיימת:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p_0 \cdot \prod_{i=0}^{k-2} p_{n-i}<\prod_{i=1}^{k} p_{i}}

ואז בהינתן סדרה פומבית כזו וסוד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} המיועד לחלוקה בין הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} חברים, כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S < p_0} , האלגוריתם פועל כדלהלן:

1. מכינים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} שתפים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle I_1,I_2,...,I_n} כדלקמן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle I_i=(S + \gamma\cdot p_0)\ \mbox{mod}\ p_i} . כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gamma} שלם אקראי כלשהו המקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S + \gamma\cdot p_0 <\prod_{i=1}^n p_i} .
2. בהינתן תת-קבוצה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} שתפים מתוך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , הסוד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} ניתן לחילוץ על ידי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S = x\ \mbox{mod} \ p_0} , כאשר את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} מחשבים על ידי פתרון מערכת הקונגרואנציות כפתרון יחיד מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_{i_1} \cdots p_{i_k}} :

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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. השיטה הישירה לפי גאוס מוצאת פתרון בסיבוכיות זמן של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O((\mbox{lg}\ n)^2)} פעולות בסיביות. בשיטה זו הפתרון הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textstyle x = \sum_{j=1}^k {(I_i)}_jN_jM_j\ \mbox{mod}\ p'} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p'=p_{i_1}\cdot p_{i_2}\cdots p_{i_k}} וכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N_j= p'/p_j} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M_j=N_j^{-1}\ (\mbox{mod}\ p_j)} . כלומר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} הוא סכום הכפולות של השתפים הנוטלים חלק בשחזור הסוד והערכים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M_j, N_j} בהתאמה, המחושבים מודולו הכפולה של המודולים המקבילים להם. והערך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M_j} הוא הופכי כפלי מודולרי של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N_j} אותו אפשר לחשב על ידי אלגוריתם אוקלידס המורחב.

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

דוגמה במספרים קטנים לסכימת סף (5,3). יהי הסוד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S=123} ונתונה הסדרה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p= \{991,1049,1249,1423,1553 \}} עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=5} משתתפים וכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_0=571} שים לב שמתקיים התנאי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_0 \cdot p_4 \cdot p_5 < p_1 \cdot p_2 \cdot p_3} . אם נבחר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gamma=4445} תוצאת חישוב השתפים תהיה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle u= \{ 267,687,250,1009,616 \}} כעת אם תת-קבוצה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle k=3} חברים, נניח: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle u_2} , הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle u_3} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle u_5} מעוניינים לשחזר את הסוד תחילה עליהם לפתור את מערכת הקונגרקואנציות:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \equiv 687 \ (\mbox{mod} \ 1,049)}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \equiv 250 \ (\mbox{mod} \ 1,249)}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \equiv 616 \ (\mbox{mod} \ 1,553)}

קיים פתרון יחיד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x=2,538,218 \ (\mbox{mod}\ p' = 2,034,742,153)} והסוד הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \ \mbox{mod} \ 571 = 123} . שיתוף פעולה של פחות מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

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

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

חלוקת_סוד20240276Q1386603