חלוקת סוד

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

מושג חלוקת הסוד הקריפטוגרפי הומצא בשנת 1979 באופן בלתי תלוי בידי עדי שמיר וג'ורג' בלקלי.

[עריכה] הרעיון הבסיסי

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

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

לצורכי פשטות ויעילות, עוסקים לרוב רק במקרה פשוט יותר של חלוקת סוד: מחלקים את הסוד ל-n שתפים שונים, כך שכל קבוצה של t שתפים מסוגלת לשחזר אותו. כך למשל בדוגמה הקודמת n=6, ואם נגדיר t=3 פירוש הדבר יהיה שגם שלושת המנהלים הזוטרים מסוגלים לשחזר בעצמם את הסוד, ואילו אם t=4 פירוש הדבר יהיה שהמנכ"ל ושני סגניו חייבים שיתוף פעולה של אחד המנהלים הזוטרים כדי לשחזר את הסוד.

עם זאת, ניתן לתת "משקל" גדול יותר לבעלי תפקידים שונים באמצעות חלוקת מספר גדול יותר של שתפים. למשל, אם היו נותנים למנכ"ל שלושה שתפים, לסגניו שניים ולמנהלים הזוטרים אחד וקובעים t=4, הייתה מתקבלת הסיטואציה בה המנהלים הזוטרים אינם יכולים לשחזר את הסוד לבדם, אך כל תת קבוצה בת שני אנשים מבין המנכ"ל וסגניו מסוגלת לשחזר את הסוד (במקרה זה n=10 - זהו מספר השתפים, ולא מספר האנשים שמשתתפים בחלוקת הסוד).

שיטת חלוקת סוד כזו, שבה מחולקים n שתפים ונדרשים k שתפים לגילוי הסוד, מסומנת בתור "שיטת חלוקה (t,n)".

[עריכה] שיטות נאיביות לחלוקת סוד

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

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

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

את השתף ה-n מחשבים על ידי ביצוע פעולת XOR לסוד עם כל השתפים האחרים. כלומר, אם $\ S$ הוא הסוד ואילו $\ r_1,\dots,r_{n-1}$ הם השתפים, השתף האחרון מחושב על ידי $\ r_n=S\oplus r_1\oplus\dots\oplus r_{n-1}$ . לא קשה להוכיח כי מאקראיות השתפים האחרים נובע שגם $\ r_n$ הוא אקראי ולכן אינו מכיל בפני עצמו שום אינפורמציה על $\ S$ . עם זאת, בהינתן כל השתפים השחזור של $\ S$ הוא מיידי: $\ S=r_1\oplus\dots\oplus r_{n-1}\oplus r_n$ .

[עריכה] שיטת שמיר לחלוקת סוד (t,n)

שיטת חלוקת הסוד שהציע עדי שמיר מבוססת על תכונותיהם של פולינומים; ידוע כי מעל שדה, בהינתן t זוגות $\ (x_i,y_i)$ של אברים מהשדה, קיים פולינום $\ p$ יחיד מדרגה t-1 המקיים $\ p(x_i)=y_i$ לכל t הזוגות (למשל - דרך שתי נקודות עובר קו אחד ויחיד, דרך שלוש נקודות עוברת פרבולה יחידה וכן הלאה).

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

בצורה פורמלית אם הסוד הוא מספר $\ S$ , מגדירים את הפולינום האקראי בתור $\ p(x)=S+\sum_{i=1}^{t-1}a_ix^i$ - כאשר $\ a_i$ הם מקדמים שנבחרו באקראי. ברור מהגדרתו כי $\ p(0)=S$ , ולכן כל מי שיודע מהו הפולינום יודע מהו הסוד.

כעת, לכל שתף מהסוד קובעים מספר מזהה ייחודי $\ z_i$ , ומחשבים את ערכו של הפולינום באותה נקודה - כלומר, כל שתף הוא מהצורה $\ (z_i,p(z_i))$ . בהינתן t שתפים ניתן לחשב את הפולינום $\ p(x)$ ואת הערך $\ p(0)$ ביעילות, למשל על ידי אינטרפולצית לגראנז'.

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

[עריכה] לקריאה נוספת

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

מקור: http://he.wikipedia.org../../../%D7%97/%D7%9C/%D7%95/%D7%97%D7%9C%D7%95%D7%A7%D7%AA_%D7%A1%D7%95%D7%93.html

קטגוריה: הצפנה