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

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

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

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

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

איך לחלוק סוד

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

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

אינטרפולציה פולינומית

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

דרך שתי נקודות ניתן לצייר מספר בלתי מוגבל של פולינומים בדרגה 2. כדי לבחור את היחיד מתוכם, צריך נקודה שלישית. אִיוּר: ויקיפדיה

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

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

ממציא סוד

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

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

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

משחזר את הסוד

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

ב נוכל לפתור את זה כך ולהחזיר את הפונקציה הפולינומית המקורית שלנו:

מאז שאנחנו יודעים את זה , התאוששות נעשה בפשטות:

שימוש באריתמטיקה של מספרים שלמים לא בטוחים

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

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

לאחר מכן התוקף יכול למצוא , סופר :

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

לאחר מכן התוקף יכול לחשב את הערכים האפשריים מחליף в :

עם אפשרויות מוגבלות עבור מתברר כמה קל לבחור ולבדוק את הערכים . יש כאן רק חמש אפשרויות.

פתרון הבעיה באמצעות אריתמטיקה לא בטוחה של מספרים שלמים

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

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

אנו יכולים להדגים כיצד זה משפר את האבטחה של התכנית שלנו על ידי יישום התכנית על הדוגמה הקודמת שלנו ושימוש . הפונקציה הפולינומית החדשה שלנו , והנקודות החדשות . כעת שומרי המפתח יכולים שוב להשתמש באינטרפולציה פולינומית כדי לשחזר את הפונקציה שלנו, רק שהפעם פעולות החיבור והכפל חייבות להיות מלוות בהפחתת מודולו (לְמָשָׁל ).

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

עכשיו התוקף שלנו מוצא שוב , בחישוב :

ואז הוא מנסה שוב מחליף в :

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

שיקולי אבטחה

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

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

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

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

Демо

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

מקור: www.habr.com