[Powered by Google Translate] [RSA]
[רוב אודן] [טומי MacWilliam] [אוניברסיטת הרווארד]
[זה CS50.] [CS50.TV]
בואו נסתכל על RSA, אלגוריתם בשימוש נרחב להצפנת נתונים.
אלגוריתמי הצפנה כמו צופן Vigenère קיסר ואינם בטוחים.
עם קיסר הצופן, תוקף צריך רק לנסות 25 מפתחות שונים
כדי לקבל טקסט הרגיל של ההודעה.
בעוד צופן Vigenère בטוח יותר מאשר קיסר הצופן
בגלל מרחב החיפוש הגדול יותר עבור מקשים, ברגע שתוקף
יודע את אורכו של המפתח בצופן Vigenère,
שניתן לקבוע באמצעות ניתוח הדפוסים בטקסט המוצפן,
צופן Vigenère הוא לא הרבה יותר בטוח מאשר הקיסר הצופן.
RSA, לעומת זאת, אינו פגיע להתקפות מסוג זה.
קיסר הצופן וצופן Vigenère להשתמש באותו המפתח
לשניהם הצפנה ופענוח הודעה.
מאפיין זה הופך את אלגוריתמי מפתח סימטריים אלה צפנים.
בעיה בסיסית עם אלגוריתמי מפתח סימטריים
הוא כי הם סומכים על זה שהצפנה ושולח את ההודעה
ומי שמקבל את הפענוח וההודעה
לכבר הסכים מראש על המפתח שהם יהיו גם להשתמש בו.
אבל יש לנו קצת בעיה בהפעלה כאן.
איך 2 מחשבים שרוצים לתקשר אין להקים מפתח סודי ביניהם?
אם המפתח חייב להיות סודי, אז אנחנו זקוקים לדרך הצפנה ופענוח המפתח.
אם כל שיש לנו הוא הצפנה במפתח סימטרית
אז עכשיו אני חוזר לאותה הבעיה.
RSA, לעומת זאת, משתמש בזוג מפתחות,
אחד להצפנה ואחד לפענוח.
אחת נקרא המפתח הציבורי, והשני הוא המפתח הפרטי.
המפתח הציבורי משמש להצפנת הודעות.
כפי שאתם יכולים לנחש לפי שמו, שאנו יכולים לחלוק עם המפתח הציבורי שלנו
מי שאנחנו רוצים מבלי להתפשר על האבטחה של הודעה מוצפנת.
מסרים מוצפנים באמצעות מפתח ציבורי
יכול להיות מפוענח עם המפתח הפרטי המתאים לו בלבד.
בזמן שאתה יכול לחלוק את המפתח הציבורי שלך, אתה צריך תמיד לשמור בסוד המפתח הפרטי שלך.
ורק את המפתח הפרטי יכול לשמש כדי לפענח הודעות
אם 2 משתמשים רוצים לשלוח הודעות מוצפנות עם RSA
הלוך ושוב שני המשתמשים צריכים להיות זוג ציבורי ופרטי משלהם מפתח.
הודעות ממשתמש 1 עד משתמש 2
להשתמש בזוג של 2 משתמש מפתח, והודעות רק ממשתמש למשתמש 2 1
להשתמש בצמד המפתחות של המשתמש 1 בלבד.
העובדה שיש 2 מפתחות הנפרדים כדי להצפין ולפענח הודעות
עושה RSA אלגוריתם מפתח סימטרי.
אנחנו לא צריכים להצפנת המפתח הציבורי כדי לשלוח אותו למחשב אחר
מאז המפתח הוא ציבור בכל מקרה.
משמעות הדבר הוא כי RSA לא יש את אותה בעיה בהפעלה
כמו אלגוריתמי מפתח הסימטריים.
אז אם אני רוצה לשלוח הודעה באמצעות הצפנת RSA
לשדוד אותו, אני צריך את המפתח הציבורי של רוב ראשון.
כדי ליצור זוג מפתחות, רוב צריך לקחת 2 מספרים ראשוניים גדולים.
מספרים אלה יהיו בשימוש בשני המפתחות הציבוריים ופרטיים,
אבל המפתח הציבורי יהיה להשתמש במוצר של 2 מספרים אלה בלבד,
לא את המספרים עצמם.
ברגע שאני מוצפן הודעה באמצעות המפתח הציבורי של רוב
אני יכול לשלוח את ההודעה לרוב.
למחשב, מספרים הפקטורינג הוא בעיה קשה.
המפתח הציבורי, לזכור, לא השתמש במוצר של 2 מספרים ראשוניים.
אז המוצר הזה חייב להיות רק 2 גורמים,
שיקרה לך להיות את המספרים שמרכיבים את המפתח הפרטי.
כדי לפענח את ההודעה, RSA ישתמש במפתח פרטי זה
או את המספרים מוכפלים יחד בתהליך של יצירת המפתח הציבורי.
כי זה קשה מחשוב לגורם המספר
שימוש במפתח ציבורי למספרים 2 בשימוש במפתח הפרטי
זה קשה לתוקף להבין את המפתח הפרטי
שזה יהיה נחוץ כדי לפענח את המסר.
עכשיו בואו נלך לכמה פרטים ברמה נמוכים יותר של RSA.
בואו נראים תחילה כיצד אנו יכולים לייצר זוג המפתחות.
ראשית, אנחנו צריכים 2 מספרים ראשוניים.
אנחנו נתקשר 2 המספרים האלה p ו q.
על מנת לקחת p ו q, בפועל pseudorandomly יעוררו
מספרים גדולים ולאחר מכן להשתמש במבחן לקביעה אם או לא
המספרים האלה הם כנראה ממשלה.
אנחנו יכולים להחזיק את יצירת מספרים אקראיים שוב ושוב
עד שיש לנו 2 מספרים ראשוניים שאנחנו יכולים להשתמש בו.
הנה בואו לקחת p = 23, q = 43.
זכרו, בפועל, p ו q צריך להיות מספרים גדולים בהרבה.
עד כמה שאנחנו יודעים, גדולים יותר המספרים, כך קשה יותר
לפצח הודעה מוצפנת.
אבל זה גם יקר יותר להודעות הצפנה ופענוח.
היום זה מומלץ לעתים קרובות שp ו q הם לפחות 1024 ביטים,
מה שמעמיד את כל מספר במעל 300 ספרות אחרי נקודה עשרוניות.
אבל אנחנו ניקח את המספרים קטנים האלה לדוגמה זו.
עכשיו נכפיל p ו q יחד כדי לקבל מספר 3,
נכנה n.
במקרה שלנו, n = 23 * 43, אשר = 989.
יש לנו n = 989.
הבא אנו נכפיל p - 1 עם ש - 1
כדי לקבל מספר 4, שאנחנו קוראים למ '.
במקרה שלנו, מ '= 22 * ​​42, אשר = 924.
יש לנו מ '= 924.
עכשיו אנחנו נצטרך דואר מספר שיחסית לראש מ '
ופחות מ מ '.
שני מספרים הם יחסית ממשלה או coprime
אם המספר החיובי היחיד שמחלק את שניהם באופן שווה הוא 1.
במילים אחרות, מחלק המשותף הגדול ביותר של דואר ומטר
חייב להיות 1.
בפועל, זה נפוץ לדואר להיות המספר הראשוני 65537
כל עוד מספר זה לא קורה להיות פקטור של מטר.
למפתחות שלנו, אנחנו ניקח את הדואר = 5
מאז 5 הוא יחסית ממשלת 924.
לבסוף, אנחנו נצטרך יותר מספר אחד, שאנחנו קוראים ד.
D חייב להיות איזה שהוא ערך שמספק את משוואת דה = 1 (mod מ ').
מ mod זה מסמל אנו נשתמש משהו שנקרא חשבון מודולרי.
באריתמטיקה מודולרית, פעם במספר גבוה יותר מאשר מקבל כמה גבול העליון
זה יהיה לעטוף סביב חזרה ל 0.
שעון, למשל, משתמש בחשבון מודולרי.
דקה אחת אחרי 1:59, למשל, היא 2:00,
לא 1:60.
מחוג דקות שעוטף עד 0
עם הגעה לגבול עליון של 60.
לכן, אנו יכולים לומר 60 הם שווים ערך ל 0 (mod 60)
ו125 הוא שווה ערך ל 65 הוא שווה ערך ל 5 (mod 60).
המפתח הציבורי שלנו יהיה דואר הזוג וn
במקרה זה שבו דואר הוא 5 ו n הוא 989.
המפתח הפרטי שלנו יהיה הזוג ד ו n,
שבמקרה שלנו הוא 185 ו989.
שימו לב שהמספרים הראשוניים המקורי p ו q שלנו לא מופיעים
בכל מקום במפתחות הפרטיים או ציבוריים שלנו.
עכשיו יש לנו זוג המפתחות שלנו, בואו נסתכל על איך אנחנו יכולים להצפין
ופענוח של מסר.
אני רוצה לשלוח הודעה לרוב,
אז הוא יהיה זה שכדי ליצור צמד מפתחות זה.
ואז אני אשאל את רוב למפתח הציבורי שלו, שאני אשתמש
כדי להצפין את הודעה לשלוח אליו.
זכור, זה לגמרי בסדר לרוב לחלוק המפתח הציבורי שלו איתי.
אבל זה לא יהיה בסדר לשתף המפתח הפרטי שלו.
אין לי מושג מה הוא המפתח הפרטי שלו.
אנחנו יכולים לשבור מ 'המסר שלנו לכמה חתיכות
כל קטן יותר n ואז להצפין כל אחד מהגושים הללו.
אנחנו להצפין CS50 המחרוזת, שאנחנו יכולים להתפרק לחתיכות 4,
אחד לכל מכתב.
כדי להצפין את המסר שלי, אני צריך להמיר אותו לתוך
איזה ייצוג מספרי.
בואו לשרשר את ערכי ASCII עם הדמויות בהודעה שלי.
כדי להצפין מ 'הודעת נתונה
אני צריך לחשב ג = מ 'לדואר (mod n).
אבל מ 'חייב להיות קטן מ n,
או שהודעה המלאה לא יכולה לבוא לידי ביטוי מודולו n.
אנחנו יכולים לשבור מ 'לכמה חתיכות, שכולם קטנים מ n,
ולהצפין כל אחד מהגושים הללו.
הצפנה כל אחד מהגושים הללו, אנחנו מקבלים c1 = 67 עד 5 (mod 989)
אשר = 658.
עבור הנתח השני שלנו שיש לנו 83 ל5 (mod 989)
ש= 15.
עבור הנתח השלישי שלנו שיש לנו 53 עד 5 (mod 989)
אשר = 799.
ולבסוף, לחתיכה האחרונה שלנו שיש לנו 48 עד 5 (mod 989)
אשר = 975.
עכשיו אנחנו יכולים לשלוח את הערכים המוצפנים האלה לרוב.
הנה לך, רוב.
בעוד המסר שלנו נמצא במצב טיסה, בואו ניקח מבט נוסף
באיך הגיע לשווי שד.
מספר ד צורך לספק 5d = 1 (mod 924).
זה הופך ד ההופכים של 5 מודולו 924.
בהינתן 2 מספרים שלמים, ו-B, האלגוריתם אוקלידית המורחב
ניתן להשתמש בו כדי למצוא את המחלק המשותף הגדול ביותר של 2 המספרים שלמים האלה.
זה גם ייתן לנו 2 מספרים אחרים, X ו-Y,
שיספק את גרזן המשוואה + = ידי מחלק המשותף הגדול ביותר של ב.
איך זה יעזור לנו?
ובכן, חיבור e = 5 עבור
ו= 924 מ 'לב
אנחנו כבר יודעים שהמספרים האלה הם coprime.
המחלק המשותף הגדול ביותר שלהם הוא 1.
זה נותן לנו 5x + 924y = 1
או 5x = 1 - 924y.
אבל אם אכפת לנו רק על הכל מודולו 924
אז אנחנו יכולים להוריד - 924y.
היזכר לשעון.
אם מחוג דקות הוא על 1, ואז בדיוק 10 שעות תעבורנה,
אנחנו יודעים את מחוג דקות עדיין תהיה על 1.
כאן אנו מתחילים ב 1 ולאחר מכן לעטוף פעמים בדיוק y,
כך עדיין אהיה ב1.
יש לנו 5x = 1 (mod 924).
והנה x זה כמו ד אנחנו מחפשים קודם,
כך שאם אנו משתמשים באלגוריתם אוקלידית המורחב
כדי לקבל x המספר הזה, זה המספר שאנחנו צריכים להשתמש כד.
עכשיו בואו נרוץ האלגוריתם אוקלידית המורחב = 5
וB = 924.
אנו נשתמש בשיטה הנקראת שיטת השולחן.
השולחן שלנו יהיה 4 טורים, x, y, ד, ו-k.
השולחן שלנו מתחיל עם 2 שורות.
בשורה הראשונה יש לנו 1, 0, אז הערך שלנו, שהוא 5,
והשורה השנייה שלנו היא 0, 1, והערך שלנו עבור b, שהוא 924.
הערך של העמודה 4, k, יהיה התוצאה
חלוקת הערך של ד בשורה מעליו עם הערך של ד
באותה השורה.
יש לנו 5 חלקים 924 הם 0 עם שארית כלשהי.
זה אומר שיש לנו k = 0.
עכשיו את הערך של כל תא אחר יהיה הערך של 2 שורות התאים שמעליו
פחות הערך של השורה מעליה הפעמים k.
בואו נתחיל עם ד בשורה 3.
יש לנו 5-924 * 0 = 5.
הבא יש לנו 0-1 * 0 אשר 0
ו 1 - 0 * 0 שהוא 1.
לא רע, אז בואו נעבור לשורה הבאה.
ראשית, עלינו הערך של k שלנו.
924 חלקים 5 = 184 עם שארית מסוימת,
כל כך הערך שלנו עבור K הוא 184.
עכשיו 924-5 * 184 = 4.
1-0 * 184 הוא 1 ו 0 - 1 * 184 הם -184.
בסדר, בואו נעשה את השורה הבאה.
הערך של k יהיה 1 בגלל
5 חלקים 4 = 1 עם שארית כלשהי.
בואו למלא את העמודות האחרות.
5-4 * 1 = 1.
0-1 * 1 = -1.
ו 1 - 184 * 1 הוא 185.
בואו לראות מה הערך הבא שלנו יהיה k.
ובכן, זה נראה כאילו יש לנו 4 חלקי 1, שהוא 4.
במקרה זה שבו אנחנו מחלקים עד 1 k כזה שהוא שווה
הערך של ד בשורה שמעל אומר שאנחנו עושים עם האלגוריתם שלנו.
אנחנו יכולים לראות כאן שיש לנו x = 185, y = -1 בשורה האחרונה.
עכשיו בואו נחזור למטרה המקורית שלנו.
אנחנו אמרנו שהערך של x כתוצאה מהפעלת אלגוריתם זה
יהיו ההופכים של (mod ב).
זה אומר ש185 הם ההופכים של 5 (mod 924)
מה שאומר שיש לנו ערך של 185 לד.
העובדה שד = 1 בשורה האחרונה
מוודא שהדואר היה coprime למ '.
אם זה לא היה 1 ואז הייתי צריך לקחת את הדואר חדש.
עכשיו בואו נראה אם ​​רוב קבל את ההודעה שלי.
כשמישהו שולח לי הודעה מוצפנת
כל עוד נשמר אצלי המפתח הפרטי שלי בסוד
אני היחיד שיכול לפענח את ההודעה.
כדי לפענח חתיכה ג אני יכול לחשב את ההודעה המקורית
שווה לנתח לד כוח (mod n).
זכור כי ד ו n הוא מהמפתח הפרטי שלי.
כדי לקבל הודעה מלאה מגושיה לפענח כל חתיכה
ולשרשר את התוצאות.
בדיוק כמה מאובטח RSA?
האמת היא, שאנחנו לא יודעים.
אבטחה מבוססת על כמה זמן זה ייקח לפורץ לפצח הודעה
מוצפן עם RSA.
זכור כי תוקף יש גישה למפתח הציבורי שלך,
שמכיל גם דואר וn.
אם התוקף מצליח גורם n ל 2 המספרים הראשוניים שלה, p ו q,
אז היא הייתה יכולה לחשב ד באמצעות האלגוריתם אוקלידית המורחב.
זה נותן לה את המפתח הפרטי, שניתן להשתמש בו כדי לפענח כל הודעה.
אבל כמה מהר אנחנו יכולים גורמים מספרים שלמים?
שוב, אנחנו לא יודעים.
אף אחד לא מצא דרך מהירה לעשות את זה,
מה שאומר שנתן מספיק גדול n
זה ייקח תוקף לא ריאלי ארוך
לגורם המספר.
אם מישהו גילה דרך מהירה של מספרים שלמים פקטורינג
RSA עלול להישבר.
אבל גם אם פרוק שלם הוא מטבעו איטי
אלגוריתם RSA עדיין יכול להיות פגם כלשהו בזה
המאפשר לפענוח קל של הודעות.
אף אחד לא מצא וחשף פגם כזה עדיין,
אבל זה לא אומר שאינו קיים עדיין.
בתאוריה, מישהו יכול להיות בחוץ וקורא את כל הנתונים מוצפנים עם RSA.
יש קטע אחר של נושא פרטיות.
אם טומי מצפין מסר כלשהו באמצעות המפתח הציבורי שלי
ותוקף מצפין את אותו מסר באמצעות המפתח הציבורי שלי
התוקף יראה כי 2 הודעות זהות
וכך יודע מה טומי מוצפן.
כדי למנוע זאת, הודעות מרופדות בדרך כלל עם ביטים אקראיים
לפני מוצפן, כך שאותו המסר מוצפן
מספר פעמים תיראינה אחרות, כל עוד את הריפוד בהודעה היא שונה.
אבל זוכר איך יש לנו לפצל הודעות לגושים
כך שכל נתח קטן מn?
ריפוד גושי משמעות הוא שאולי יש לנו לפצל את הדברים
לגושים עוד יותר מאז הנתח המרופד חייב להיות קטן מ n.
הצפנה ופענוח הם יקרים יחסית עם RSA,
וכך הצורך לשבור את הודעה לגושים רבים יכול להיות יקר מאוד.
אם נפח גדול של נתונים צריך להיות מוצפן ומפוענח
אנחנו יכולים לשלב את היתרונות של אלגוריתמי מפתח סימטריים
עם אלה של RSA כדי לקבל ביטחון ויעילות.
למרות שלא ייכנסו לזה כאן,
AES הוא אלגוריתם מפתח סימטרי כמו Vigenère וצפני קיסר
אבל הרבה יותר קשה לפיצוח.
כמובן, אנחנו לא יכולים להשתמש AES בלי לקבוע מפתח סודי משותף
בין 2 המערכות, וראינו בעיה עם זה בעבר.
אבל עכשיו אנחנו יכולים להשתמש RSA להקים את המפתח הסודי המשותף בין 2 המערכות.
אנחנו קוראים למחשב שולח את הנתונים לשולח
והמחשב שמקבל את הנתונים למקלט.
המקלט יש זוג מפתח RSA ושולח
את המפתח הציבורי לשולח.
השולח יוצר מפתח AES,
מצפין אותו עם המפתח הציבורי RSA של המקבל,
ושולח את מפתח AES למקלט.
המקלט מפענח את המסר עם המפתח הפרטי של RSA.
השולח והמקבל עכשיו יש מפתח AES משותף ביניהם.
AES, שהוא הרבה יותר מהר בהצפנה ופענוח מRSA,
כעת ניתן להשתמש כדי להצפין את הכמויות הגדולות של נתונים ולשלוח אותם למקלט,
מי יכול לפענח באמצעות אותו המפתח.
AES, שהוא הרבה יותר מהר בהצפנה ופענוח מRSA,
כעת ניתן להשתמש כדי להצפין את הכמויות הגדולות של נתונים ולשלוח אותם למקלט,
מי יכול לפענח באמצעות אותו המפתח.
אנחנו רק צריכים RSA להעביר מפתח המשותף.
אנחנו כבר לא צריכים להשתמש RSA בכלל.
זה נראה כאילו יש לי הודעה.
זה לא משנה אם מישהו לקרוא מה יש על המטוס מנייר לפני שתפסתי אותו
כי אני יחיד עם המפתח הפרטי.
בואו לפענח כל אחד מהגושים בהודעה.
הגוש הראשון, 658, אנו מעלים לכוח ד, שהוא 185,
mod n, שהוא 989, שווה ל 67,
המהווה את אות C בASCII.
כעת, על הנתח השני.
הנתח השני יש את הערך 15,
שאנו מעלים לכוח 185,
mod 989, וזה שווה ל 83
אשר הוא אות S בASCII.
עכשיו לגוש השלישי, שיש לה ערך 799, אנו מעלים עד 185,
mod 989, וזה שווה ל 53,
שהוא הערך של הדמות 5 בASCII.
עכשיו עבור הנתח שעבר, שיש לה ערך 975,
אנו מעלים עד 185, 989 mod,
וזה שווה ל 48, שהוא הערך של 0 בתו ASCII.
השם שלי הוא רוב אודן, וזה CS50.
[CS50.TV]
RSA בכלל.
RSA בכלל. [שחוק]
בכלל.