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

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

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

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

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

איך לחלוק סוד

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

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

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

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

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

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

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

ממציא סוד

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

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

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

משחזר את הסוד

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

תוכנית השיתוף הסודי של שמיר

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

תוכנית השיתוף הסודי של שמיר

מאז שאנחנו יודעים את זה תוכנית השיתוף הסודי של שמיר , התאוששות נעשה בפשטות:

תוכנית השיתוף הסודי של שמיר

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

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

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

תוכנית השיתוף הסודי של שמיר

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

תוכנית השיתוף הסודי של שמיר

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

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

תוכנית השיתוף הסודי של שמיר

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

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

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

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

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

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

תוכנית השיתוף הסודי של שמיר

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

תוכנית השיתוף הסודי של שמיר

ואז הוא מנסה שוב תוכנית השיתוף הסודי של שמיר מחליף в :

תוכנית השיתוף הסודי של שמיר

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

שיקולי אבטחה

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

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

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

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

Демо

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

מקור: www.habr.com