מפתח תשובות · יחידה 7

קריפטוגרפיה.

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

קטלוג הטעויות הנפוצות

מפתח תשובות 4

שיעור 1 מתוך 4 · כ־20 דקות

חשבון של שעון

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

לפתוח את השיעור

6 השלבים והתשובות שלהם

שלב 1 מתוך 6
לפתוח את השלב
שארית
תרגול · חשבו
השאלה
כמה זה $17 \bmod 5$ ⁠?

התשובה הנכונה
2 ± 0.01
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
הסוד של אליס
6
הודעה נעולה / המתמטיקה
המתמטיקה
מתקבלת בטווח
± 0.01
ערך קבוע בשאלה
תשובות שגויות שהשאלה מזהה
- 3 ± 0.01
  טעות נפוצה: Gives the quotient of the division (how many times it goes in) instead of the remainder.
  משוב מהקטלוג
  „ $a \bmod n$ ⁠” הוא השארית בחלוקה של $a$ ⁠ ב־ $n$ ⁠, לא התוצאה של החילוק. ב־ $17 \div 5$ ⁠ החמישייה נכנסת $3$ ⁠ פעמים, $3 \times 5 = 15$ ⁠, ונשאר $2$ ⁠: לכן $17 \bmod 5 = 2$ ⁠. השארית תמיד בין $0$ ⁠ ל־ $n - 1$ ⁠, כמו מקום על שעון עם $n$ ⁠ מקומות.
- 3.4 ± 0.01
  טעות נפוצה: Gives the quotient of the division (how many times it goes in) instead of the remainder.
  משוב מהקטלוג
  „ $a \bmod n$ ⁠” הוא השארית בחלוקה של $a$ ⁠ ב־ $n$ ⁠, לא התוצאה של החילוק. ב־ $17 \div 5$ ⁠ החמישייה נכנסת $3$ ⁠ פעמים, $3 \times 5 = 15$ ⁠, ונשאר $2$ ⁠: לכן $17 \bmod 5 = 2$ ⁠. השארית תמיד בין $0$ ⁠ ל־ $n - 1$ ⁠, כמו מקום על שעון עם $n$ ⁠ מקומות.
משוב לתשובה נכונה
$17 = 3 \times 5 + 2$ ⁠, ולכן $17 \bmod 5 = 2$ ⁠. על שעון עם $5$ ⁠ מקומות, $0$ ⁠ עד $4$ ⁠, צעד של $17$ ⁠ מ־ $0$ ⁠ מקיף את השעון שלוש פעמים ונוחת על $2$ ⁠.

רמז
כמה פעמים נכנסת $5$ ⁠ ב־ $17$ ⁠, ומה נשאר?

פתרון מלא
1. חלקו: $5$ ⁠ נכנסת ב־ $17$ ⁠ שלוש פעמים, $3 \times 5 = 15$ ⁠.
2. השארית: $17 - 15 = 2$ ⁠.
3. לכן $17 \bmod 5 = 2$ ⁠.
אם עניתם $3$ ⁠ או $3.4$ ⁠, נתתם את תוצאת החילוק. „מודולו” שומר רק את מה שנשאר.
שלב 2 מתוך 6
לפתוח את השלב
סביב השעון
תרגול · חשבו
השאלה
השעון מראה $9$ ⁠. מה הוא יראה בעוד $8$ ⁠ שעות? (על שעון של $12$ ⁠ שעות, ו־ $12$ ⁠ נכתב כאן $0$ ⁠.)

התשובה הנכונה
5 ± 0.01
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
הסוד של אליס
6
הודעה נעולה / המתמטיקה
המתמטיקה
מתקבלת בטווח
± 0.01
ערך קבוע בשאלה
תשובות שגויות שהשאלה מזהה
- 17 ± 0.01
  טעות נפוצה: Forgets to wrap round: gives the plain result instead of its remainder mod n.
  משוב מהקטלוג
  בחשבון מודולרי כל תוצאה „מסתובבת” חזרה לשעון: אחרי $n - 1$ ⁠ באה $0$ ⁠. שעה $9$ ⁠ ועוד $8$ ⁠ שעות היא לא $17$ ⁠ על שעון של $12$ ⁠, אלא $17 \bmod 12 = 5$ ⁠. גם בחזקות: $5^2 = 25$ ⁠, אבל $5^2 \bmod 23 = 2$ ⁠. אחרי כל חישוב מחלקים ב־ $n$ ⁠ ושומרים רק את השארית.
משוב לתשובה נכונה
$9 + 8 = 17$ ⁠, ו־ $17 \bmod 12 = 5$ ⁠: חמש. זה חשבון מודולרי, חשבון של שעון: כל פעם שעוברים את $12$ ⁠, מתחילים שוב מאפס.

רמז
חברו, ואחר כך מצאו את השארית בחלוקה ב־ $12$ ⁠.

פתרון מלא
1. חברו: $9 + 8 = 17$ ⁠.
2. על שעון של $12$ ⁠ שעות: $17 = 1 \times 12 + 5$ ⁠.
3. $17 \bmod 12 = 5$ ⁠, והשעון יראה $5$ ⁠.
אם עניתם $17$ ⁠, שכחתם להסתובב: על השעון אין מקום $17$ ⁠.
שלב 3 מתוך 6
לפתוח את השלב
חזקות במודולו
תרגול · חשבו
השאלה
החשבון רץ מודולו $p = 23$ ⁠, עם $g = 5$ ⁠. הסוד של אליס קבוע על $a = 2$ ⁠. מה היא שולחת, $A = 5^2 \bmod 23$ ⁠?

התשובה הנכונה
2 ± 0.01
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
הסוד של אליס
2קבוע
הודעה נעולה / המתמטיקה
ערבוב צבעיםקבוע
מתקבלת בטווח
± 0.01
מחושבת מהסצנה בהגדרה של השלב
What Alice sends, A = gᵃ mod p/nodes/kx/outputs/alicePublic
תשובות שגויות שהשאלה מזהה
- 25 ± 0.01
  טעות נפוצה: Forgets to wrap round: gives the plain result instead of its remainder mod n.
  משוב מהקטלוג
  בחשבון מודולרי כל תוצאה „מסתובבת” חזרה לשעון: אחרי $n - 1$ ⁠ באה $0$ ⁠. שעה $9$ ⁠ ועוד $8$ ⁠ שעות היא לא $17$ ⁠ על שעון של $12$ ⁠, אלא $17 \bmod 12 = 5$ ⁠. גם בחזקות: $5^2 = 25$ ⁠, אבל $5^2 \bmod 23 = 2$ ⁠. אחרי כל חישוב מחלקים ב־ $n$ ⁠ ושומרים רק את השארית.
- 10 ± 0.01
  טעות נפוצה: Multiplies the base by the exponent (5 × 6) instead of raising it to that power (5⁶).
  משוב מהקטלוג
  $g^a$ ⁠ פירושו לכפול את $g$ ⁠ בעצמו $a$ ⁠ פעמים, לא לכפול את $g$ ⁠ ב־ $a$ ⁠. $5^3 = 5 \times 5 \times 5 = 125$ ⁠, ולא $5 \times 3 = 15$ ⁠. במודולו עושים את זה צעד אחרי צעד: כל חזקה היא הקודמת כפול $g$ ⁠, ואחר כך השארית. מ־ $5^2 \bmod 23 = 2$ ⁠ מקבלים $5^3 \bmod 23 = 2 \times 5 = 10$ ⁠.
- 1 ± 0.01
  טעות נפוצה: Gives the quotient of the division (how many times it goes in) instead of the remainder.
  משוב מהקטלוג
  „ $a \bmod n$ ⁠” הוא השארית בחלוקה של $a$ ⁠ ב־ $n$ ⁠, לא התוצאה של החילוק. ב־ $17 \div 5$ ⁠ החמישייה נכנסת $3$ ⁠ פעמים, $3 \times 5 = 15$ ⁠, ונשאר $2$ ⁠: לכן $17 \bmod 5 = 2$ ⁠. השארית תמיד בין $0$ ⁠ ל־ $n - 1$ ⁠, כמו מקום על שעון עם $n$ ⁠ מקומות.
משוב לתשובה נכונה
$5^2 = 25 = 1 \times 23 + 2$ ⁠, ולכן $A = 2$ ⁠. על החוגה עם $23$ ⁠ המקומות, המחוג של אליס מצביע על $2$ ⁠.

רמז
חשבו $5^2$ ⁠, ואחר כך את השארית בחלוקה ב־ $23$ ⁠.

פתרון מלא
1. $5^2 = 5 \times 5 = 25$ ⁠.
2. $25 = 1 \times 23 + 2$ ⁠.
3. $A = 25 \bmod 23 = 2$ ⁠.
אם עניתם $25$ ⁠, לא לקחתם שארית. אם עניתם $10$ ⁠, כפלתם $5 \times 2$ ⁠ במקום להעלות בריבוע. אם עניתם $1$ ⁠, נתתם את תוצאת החילוק במקום את השארית.
שלב 4 מתוך 6
לפתוח את השלב
צעד אחרי צעד
תרגול · הגיעו למטרה
השאלה
שנו את הסוד של אליס עד ש־ $A = 5^a \bmod 23$ ⁠ שווה $10$ ⁠, ולחצו על בדיקה.

המטרה
- 10 ± 0.1
  בתחילת השלב: 5
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
הסוד של אליס
1
הודעה נעולה / המתמטיקה
המתמטיקהקבוע
נקרא מהסצנה בנקודה
What Alice sends, A = gᵃ mod p/nodes/kx/outputs/alicePublic
הגדרה אחת שמגיעה למטרה
הסוד של אליס
3
משוב לתשובה נכונה
$a = 3$ ⁠: $5^3 \bmod 23 = (5^2 \bmod 23) \times 5 \bmod 23 = 2 \times 5 = 10$ ⁠. אין צורך לחשב את $5^3 = 125$ ⁠: אפשר לקחת שארית אחרי כל כפל, והמספרים נשארים קטנים. כך מחשבים חזקות של מספרים בני מאות ספרות.

משוב לתשובה שגויה
עוד לא. הסתכלו על הלוח של אליס: הוא מראה את $A$ ⁠ לכל $a$ ⁠.

רמז
כל חזקה היא הקודמת כפול $5$ ⁠, ואחר כך השארית: $5^1 \bmod 23 = 5$ ⁠, $5^2 \bmod 23 = 2$ ⁠, ומה הלאה?

פתרון מלא
1. $5^1 \bmod 23 = 5$ ⁠.
2. $5^2 \bmod 23 = 5 \times 5 \bmod 23 = 25 \bmod 23 = 2$ ⁠.
3. $5^3 \bmod 23 = 2 \times 5 \bmod 23 = 10$ ⁠.
4. קבעו את הסוד של אליס על $3$ ⁠.
אם ניסיתם $a = 2$ ⁠, קיבלתם $A = 2$ ⁠: $5 \times 2 = 10$ ⁠ הוא כפל, לא חזקה.
שלב 5 מתוך 6
לפתוח את השלב
דילוגים
תרגול · נבאו, ואז הסתכלו
השאלה
ב־ $a = 3$ ⁠ יוצא $A = 10$ ⁠. מה יהיה $A$ ⁠ כשהסוד של אליס יעלה ל־ $a = 4$ ⁠? כתבו מספר, ואחר כך הסצנה תעבור ל־ $a = 4$ ⁠.

התשובה הנכונה
4 ± 0.1
ניבוי מספרי נחשב נכון בטווח ± 0.1
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
הסוד של אליס
3קבוע
הודעה נעולה / המתמטיקה
המתמטיקהקבוע
אחרי נעילת הניבוי הסצנה משתנה
הסוד של אליס
4קבוע
ואז הסצנה מראה: 4 · What Alice sends, A = gᵃ mod p/nodes/kx/outputs/alicePublic
ניבוי אף פעם לא נחשב כישלון: בכל מקרה הלומדים רואים את התוצאה ואת ההסבר.
משוב לתשובה נכונה
$10 \times 5 = 50 = 2 \times 23 + 4$ ⁠, ולכן $A = 4$ ⁠. המחוג קפץ מ־ $10$ ⁠ אחורה ל־ $4$ ⁠: חזקות במודולו לא גדלות באופן מסודר, הן מדלגות על פני השעון. זה בדיוק מה שהופך אותן לקשות לניחוש.

משוב לתשובה שגויה
כפלו את $A$ ⁠ הקודם, $10$ ⁠, ב־ $g = 5$ ⁠, וקחו את השארית בחלוקה ב־ $23$ ⁠.

רמז
כפלו את $10$ ⁠ ב־ $5$ ⁠ וקחו שארית בחלוקה ב־ $23$ ⁠.

פתרון מלא
1. $5^4 = 5^3 \times 5$ ⁠, ולכן $5^4 \bmod 23 = (5^3 \bmod 23) \times 5 \bmod 23$ ⁠.
2. $10 \times 5 = 50$ ⁠.
3. $50 = 2 \times 23 + 4$ ⁠.
4. $A = 4$ ⁠.
אם כתבתם $50$ ⁠, שכחתם להסתובב על השעון. אם כתבתם $15$ ⁠, הוספתם $5$ ⁠ במקום לכפול בו.
שלב 6 מתוך 6
לפתוח את השלב
סיבוב שלם
תרגול · נבאו, ואז הסתכלו
השאלה
החזקות של $5$ ⁠ מודולו $23$ ⁠ מדלגות על פני החוגה. מה יהיה $A = 5^{22} \bmod 23$ ⁠? בחרו, ואחר כך הסוד של אליס יעבור ל־ $22$ ⁠.

התשובה הנכונה
- נכונה $1$ ⁠: אחרי $22$ ⁠ צעדים החזקות חוזרות להתחלה
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
הסוד של אליס
3קבוע
הודעה נעולה / המתמטיקה
המתמטיקהקבוע
האפשרויות
- נכונה $1$ ⁠: אחרי $22$ ⁠ צעדים החזקות חוזרות להתחלה
- שגויה $22$ ⁠, המקום האחרון על החוגה
  משוב
  אין סיבה שהחזקה ה־ $22$ ⁠ תנחת דווקא על המקום ה־ $22$ ⁠: החזקות מדלגות, ו־ $5^{11} \bmod 23$ ⁠ כבר נוחתת שם.
- שגויה $0$ ⁠: החזקה גדולה כל כך שהיא מגיעה לכפולה של $23$ ⁠
  משוב
  $5^{22}$ ⁠ הוא מכפלה של חמישיות בלבד, ו־ $23$ ⁠ ראשוני, ולכן $23$ ⁠ לא מחלק אותו לעולם: השארית אף פעם לא $0$ ⁠, גדול ככל שיהיה המעריך.
אחרי נעילת הניבוי הסצנה משתנה
הסוד של אליס
22קבוע
ואז הסצנה מראה: 1 · What Alice sends, A = gᵃ mod p/nodes/kx/outputs/alicePublic
ניבוי אף פעם לא נחשב כישלון: בכל מקרה הלומדים רואים את התוצאה ואת ההסבר.
משוב לתשובה נכונה
$5^{22} \bmod 23 = 1$ ⁠. החזקות של $5$ ⁠, מ־ $5^1$ ⁠ עד $5^{22}$ ⁠, עוברות על כל $22$ ⁠ המקומות שאינם אפס, כל אחד פעם אחת, וחוזרות ל־ $1$ ⁠. מכאן הן חוזרות על עצמן: $5^{23} \bmod 23 = 5$ ⁠. מספר כמו $5$ ⁠, שהחזקות שלו מגיעות לכל מקום, נקרא יוצר, ובו משתמשים בהחלפת מפתחות.

רמז
יש $22$ ⁠ מקומות על החוגה מלבד $0$ ⁠. אם $5$ ⁠ מגיע לכל אחד מהם בדיוק פעם אחת, לאן מגיעים אחרי סיבוב שלם?

פתרון מלא
1. החזקות של $5$ ⁠ מודולו $23$ ⁠: 5, 2, 10, 4, 20, 8, 17, 16, 11, 9, 22, 18, 21, 13, 19, 3, 15, 6, 7, 12, 14, 1.
2. אלה $22$ ⁠ מספרים שונים: כל המקומות על החוגה מלבד $0$ ⁠.
3. החזקה ה־ $22$ ⁠ היא $1$ ⁠, ומשם הרצף מתחיל מחדש.
זה מקרה של המשפט הקטן של פרמה: כש־ $p$ ⁠ ראשוני ו־ $g$ ⁠ לא מתחלק בו, $g^{p-1} \bmod p = 1$ ⁠.

שיעור 2 מתוך 4 · כ־25 דקות

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

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

לפתוח את השיעור

6 השלבים והתשובות שלהם

שלב 1 מתוך 6
לפתוח את השלב
מה זה ראשוני
תרגול · בחרו
השאלה
אילו מהמספרים הבאים ראשוניים? בחרו את כולם.

התשובה הנכונה
- נכונה $2$ ⁠
- נכונה $97$ ⁠
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
גבול הספירה
100
ניפוי הספירלה
ספירלהקבוע
האפשרויות
יותר מאפשרות נכונה אחת: צריך לסמן את כולן.
- שגויה $1$ ⁠
  טעות נפוצה: Counts 1 as a prime number.
  משוב מהקטלוג
  מספר ראשוני הוא מספר טבעי שיש לו בדיוק שני מחלקים: $1$ ⁠ והוא עצמו. ל־ $1$ ⁠ יש רק מחלק אחד, ולכן הוא לא ראשוני, וגם לא פריק. ההגדרה נבחרה כך כדי שלכל מספר יהיה פירוק אחד בלבד למכפלה של ראשוניים: אילו $1$ ⁠ היה ראשוני, אפשר היה לכתוב $6 = 2 \times 3 = 1 \times 2 \times 3$ ⁠ ועוד אינסוף דרכים.
- נכונה $2$ ⁠
- שגויה $51$ ⁠
  טעות נפוצה: Takes an odd number that has no obvious small factor, such as 51, 91 or 99, to be prime.
  משוב מהקטלוג
  מספר אי־זוגי לא מתחלק ב־ $2$ ⁠, אבל הוא יכול להתחלק ב־ $3$ ⁠, ב־ $7$ ⁠ או בכל ראשוני אחר. $51 = 3 \times 17$ ⁠, $91 = 7 \times 13$ ⁠ ו־ $99 = 9 \times 11$ ⁠. כדי לדעת שמספר ראשוני צריך לבדוק שאף ראשוני עד השורש שלו לא מחלק אותו: ל־ $91$ ⁠ צריך לבדוק את $2$ ⁠, $3$ ⁠, $5$ ⁠ ו־ $7$ ⁠, ו־ $7$ ⁠ מחלק אותו.
- שגויה $91$ ⁠
  טעות נפוצה: Takes an odd number that has no obvious small factor, such as 51, 91 or 99, to be prime.
  משוב מהקטלוג
  מספר אי־זוגי לא מתחלק ב־ $2$ ⁠, אבל הוא יכול להתחלק ב־ $3$ ⁠, ב־ $7$ ⁠ או בכל ראשוני אחר. $51 = 3 \times 17$ ⁠, $91 = 7 \times 13$ ⁠ ו־ $99 = 9 \times 11$ ⁠. כדי לדעת שמספר ראשוני צריך לבדוק שאף ראשוני עד השורש שלו לא מחלק אותו: ל־ $91$ ⁠ צריך לבדוק את $2$ ⁠, $3$ ⁠, $5$ ⁠ ו־ $7$ ⁠, ו־ $7$ ⁠ מחלק אותו.
- נכונה $97$ ⁠
משוב לתשובה נכונה
$2$ ⁠ ו־ $97$ ⁠. $2$ ⁠ הוא הראשוני הזוגי היחיד. $97$ ⁠ לא מתחלק ב־ $2$ ⁠, $3$ ⁠, $5$ ⁠ או $7$ ⁠, וזה מספיק, כי $11^2 = 121$ ⁠ כבר גדול ממנו. $51 = 3 \times 17$ ⁠, $91 = 7 \times 13$ ⁠, ו־ $1$ ⁠ אינו ראשוני: יש לו מחלק אחד בלבד.

רמז
לכל מספר, נסו לחלק אותו בראשוניים $2$ ⁠, $3$ ⁠, $5$ ⁠ ו־ $7$ ⁠.

פתרון מלא
1. $1$ ⁠: יש לו מחלק אחד בלבד, ולכן אינו ראשוני.
2. $2$ ⁠: מחלקיו $1$ ⁠ ו־ $2$ ⁠. ראשוני.
3. $51$ ⁠: סכום הספרות $6$ ⁠ מתחלק ב־ $3$ ⁠, ו־ $51 = 3 \times 17$ ⁠. פריק.
4. $91 = 7 \times 13$ ⁠. פריק.
5. $97$ ⁠: לא מתחלק ב־ $2$ ⁠, $3$ ⁠, $5$ ⁠ או $7$ ⁠, ו־ $\sqrt{97} < 10$ ⁠. ראשוני.
מספרים כמו $51$ ⁠ ו־ $91$ ⁠ „נראים” ראשוניים כי הם אי־זוגיים ולא נגמרים ב־ $5$ ⁠. צריך לבדוק את כל הראשוניים עד השורש.
שלב 2 מתוך 6
לפתוח את השלב
הגדול ביותר עד מאה
תרגול · חשבו
השאלה
גבול הספירה קבוע על $100$ ⁠. מהו הראשוני הגדול ביותר עד $100$ ⁠?

התשובה הנכונה
97 ± 0.1
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
גבול הספירה
100קבוע
ניפוי הספירלה
ספירלהקבוע
מתקבלת בטווח
± 0.1
מחושבת מהסצנה בהגדרה של השלב
The largest prime from 1 to count/nodes/spiral/outputs/largestPrime
תשובות שגויות שהשאלה מזהה
- 99 ± 0.1
  טעות נפוצה: Takes an odd number that has no obvious small factor, such as 51, 91 or 99, to be prime.
  משוב מהקטלוג
  מספר אי־זוגי לא מתחלק ב־ $2$ ⁠, אבל הוא יכול להתחלק ב־ $3$ ⁠, ב־ $7$ ⁠ או בכל ראשוני אחר. $51 = 3 \times 17$ ⁠, $91 = 7 \times 13$ ⁠ ו־ $99 = 9 \times 11$ ⁠. כדי לדעת שמספר ראשוני צריך לבדוק שאף ראשוני עד השורש שלו לא מחלק אותו: ל־ $91$ ⁠ צריך לבדוק את $2$ ⁠, $3$ ⁠, $5$ ⁠ ו־ $7$ ⁠, ו־ $7$ ⁠ מחלק אותו.
משוב לתשובה נכונה
$97$ ⁠. $100$ ⁠ ו־ $98$ ⁠ זוגיים, $99 = 9 \times 11$ ⁠, ו־ $97$ ⁠ לא מתחלק באף אחד מהראשוניים $2$ ⁠, $3$ ⁠, $5$ ⁠ ו־ $7$ ⁠. על המגש הוא אריח זהוב בולט.

רמז
רדו מ־ $100$ ⁠ ובדקו כל מספר אי־זוגי.

פתרון מלא
1. $100$ ⁠ ו־ $98$ ⁠ זוגיים: פריקים.
2. $99$ ⁠: סכום הספרות $18$ ⁠ מתחלק ב־ $3$ ⁠, ו־ $99 = 9 \times 11$ ⁠. פריק.
3. $97$ ⁠: נבדוק את הראשוניים עד $\sqrt{97} \approx 9.8$ ⁠, כלומר $2$ ⁠, $3$ ⁠, $5$ ⁠ ו־ $7$ ⁠. אף אחד מהם לא מחלק אותו.
4. $97$ ⁠ הוא הראשוני הגדול ביותר עד $100$ ⁠.
אם עניתם $99$ ⁠, הוא אי־זוגי אבל מתחלק ב־ $3$ ⁠ וב־ $11$ ⁠.
שלב 3 מתוך 6
לפתוח את השלב
הנפה
תרגול · נבאו, ואז הסתכלו
השאלה
גבול הספירה $400$ ⁠. הנפה של ארטוסתנס מקיפה ראשוני, מוחקת את הכפולות שלו, ועוברת לראשוני הבא. בכמה ראשוניים היא צריכה לעבור עד שכל אריח שנשאר הוא ראשוני? בחרו, ואחר כך ניפוי הספירלה יריץ את הנפה עד הסוף.

התשובה הנכונה
- נכונה $8$ ⁠: הראשוניים עד $20$ ⁠
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
גבול הספירה
400קבוע
ניפוי הספירלה
ספירלהקבוע
האפשרויות
- נכונה $8$ ⁠: הראשוניים עד $20$ ⁠
- שגויה $78$ ⁠: כל הראשוניים עד $400$ ⁠
  טעות נפוצה: Thinks the sieve must cross out multiples of every prime up to the count, not just of the primes up to its square root.
  משוב מהקטלוג
  מספר פריק עד $n$ ⁠ תמיד מתחלק בראשוני שאינו גדול מ־ $\sqrt{n}$ ⁠: אם שני הגורמים שלו היו גדולים מ־ $\sqrt{n}$ ⁠, המכפלה הייתה גדולה מ־ $n$ ⁠. לכן אחרי שהנפה עברה את הראשוניים עד $\sqrt{n}$ ⁠, כל מספר פריק כבר נמחק. עד $400$ ⁠, $\sqrt{400} = 20$ ⁠, ומספיקים שמונה ראשוניים: מ־ $2$ ⁠ עד $19$ ⁠.
- שגויה $4$ ⁠: הראשוניים $2$ ⁠, $3$ ⁠, $5$ ⁠ ו־ $7$ ⁠
  משוב
  $2$ ⁠, $3$ ⁠, $5$ ⁠ ו־ $7$ ⁠ מספיקים עד $120$ ⁠, אבל לא עד $400$ ⁠: $11^2 = 121$ ⁠, $13^2 = 169$ ⁠, $17^2 = 289$ ⁠ ו־ $19^2 = 361$ ⁠ הם פריקים שאף אחד מהם לא מוחק.
אחרי נעילת הניבוי הסצנה משתנה
ניפוי הספירלה
0.62 (ספירלה → נפה ורווחים)קבוע
ואז הסצנה מראה: 8 · How many primes the sieve runs through (those up to √count)/nodes/spiral/outputs/sievingPrimes
ניבוי אף פעם לא נחשב כישלון: בכל מקרה הלומדים רואים את התוצאה ואת ההסבר.
משוב לתשובה נכונה
שמונה: $2, 3, 5, 7, 11, 13, 17, 19$ ⁠. כל פריק עד $400$ ⁠ מתחלק בראשוני שאינו גדול מ־ $\sqrt{400} = 20$ ⁠, ולכן אחרי $19$ ⁠ כבר אין מה למחוק. הנפה מתחילה למחוק כל ראשוני מהריבוע שלו, כי הכפולות הקטנות יותר כבר נמחקו.

רמז
למספר פריק עד $400$ ⁠ יש גורם ראשוני שאינו גדול מ־ $\sqrt{400}$ ⁠.

פתרון מלא
1. אם $n = a \times b$ ⁠ ושני הגורמים גדולים מ־ $20$ ⁠, אז $n > 400$ ⁠.
2. לכן לכל פריק עד $400$ ⁠ יש גורם ראשוני שאינו גדול מ־ $20$ ⁠.
3. הראשוניים עד $20$ ⁠: $2, 3, 5, 7, 11, 13, 17, 19$ ⁠. שמונה.
4. אחרי שהנפה עברה בהם, כל אריח שנשאר הוא ראשוני.
אם בחרתם $78$ ⁠, הנפה הייתה ממשיכה לחינם: ל־ $23$ ⁠ אין אף כפולה פריקה עד $400$ ⁠ שלא נמחקה כבר, כי $23^2 = 529$ ⁠.
שלב 4 מתוך 6
לפתוח את השלב
מתדלדלים
תרגול · הגיעו למטרה
השאלה
עד $100$ ⁠ יש $25$ ⁠ ראשוניים. שנו את גבול הספירה עד שהלוח מראה $168$ ⁠ ראשוניים, ולחצו על בדיקה.

המטרה
- 168 ± 0.1
  בתחילת השלב: 25
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
גבול הספירה
100
ניפוי הספירלה
ספירלהקבוע
נקרא מהסצנה בנקודה
How many primes there are from 1 to count/nodes/spiral/outputs/primeCount
הגדרה אחת שמגיעה למטרה
גבול הספירה
1000
משוב לתשובה נכונה
ב־ $1000$ ⁠. פי עשרה מספרים, אבל רק פי $6.7$ ⁠ ראשוניים: עד $100$ ⁠ רבע מהמספרים ראשוניים, ועד $1000$ ⁠ פחות משישית. ככל שמספר גדול יותר, יש יותר ראשוניים קטנים שיכולים לחלק אותו.

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

רמז
אם הראשוניים היו שומרים על הצפיפות שלהם, $168$ ⁠ היו מגיעים כבר ב־ $700$ ⁠ בערך. הם לא.

פתרון מלא
1. הזיזו את גבול הספירה והסתכלו על מספר הראשוניים על הלוח.
2. עד $900$ ⁠ יש $154$ ⁠ ראשוניים, ועד $1100$ ⁠ יש $184$ ⁠.
3. בדיוק $168$ ⁠ מתקבל ב־ $1000$ ⁠.
אם ציפיתם ל־ $168$ ⁠ בסביבות $700$ ⁠, הנחתם שהראשוניים שומרים על רבע מהמספרים. הם מתדלדלים.
שלב 5 מתוך 6
לפתוח את השלב
שמינית
תרגול · חשבו
השאלה
גבול הספירה קבוע על $10\,000$ ⁠, והלוח מראה כמה ראשוניים יש עד שם. איזה חלק מהמספרים עד $10\,000$ ⁠ ראשוניים? ענו באחוזים.

התשובה הנכונה
12.29 ± 0.05
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
גבול הספירה
10000קבוע
ניפוי הספירלה
ספירלהקבוע
מתקבלת בטווח
± 0.05
מחושבת מהסצנה בהגדרה של השלב
How many primes there are from 1 to count/nodes/spiral/outputs/primeCount
תשובות שגויות שהשאלה מזהה
- 25 ± 0.05
  טעות נפוצה: Thinks primes keep the same share of the numbers however far you count, as the quarter below 100.
  משוב מהקטלוג
  הראשוניים הולכים ומתדלדלים. עד $100$ ⁠ יש $25$ ⁠, רבע מהמספרים; עד $1000$ ⁠ יש $168$ ⁠, פחות משישית; עד $10\,000$ ⁠ יש $1229$ ⁠, כשמינית. ככל שמספר גדול יותר, יש יותר ראשוניים קטנים ממנו שיכולים לחלק אותו. הסיכוי שמספר בסביבת $n$ ⁠ ראשוני הוא בערך $\tfrac{1}{\ln n}$ ⁠, והוא קטן לאט. ובכל זאת הם לא נגמרים: אוקלידס הוכיח שיש אינסוף ראשוניים.
- 16.8 ± 0.05
  טעות נפוצה: Thinks primes keep the same share of the numbers however far you count, as the quarter below 100.
  משוב מהקטלוג
  הראשוניים הולכים ומתדלדלים. עד $100$ ⁠ יש $25$ ⁠, רבע מהמספרים; עד $1000$ ⁠ יש $168$ ⁠, פחות משישית; עד $10\,000$ ⁠ יש $1229$ ⁠, כשמינית. ככל שמספר גדול יותר, יש יותר ראשוניים קטנים ממנו שיכולים לחלק אותו. הסיכוי שמספר בסביבת $n$ ⁠ ראשוני הוא בערך $\tfrac{1}{\ln n}$ ⁠, והוא קטן לאט. ובכל זאת הם לא נגמרים: אוקלידס הוכיח שיש אינסוף ראשוניים.
משוב לתשובה נכונה
$\tfrac{1229}{10\,000} \approx 12.3\%$ ⁠: כשמינית מהמספרים. עד $100$ ⁠ זה היה רבע, ועד $1000$ ⁠ כשישית. הצפיפות יורדת בערך כמו $\tfrac{1}{\ln n}$ ⁠, לאט, ולעולם לא מגיעה לאפס.

רמז
חלקו את מספר הראשוניים ב־ $10\,000$ ⁠ וכפלו ב־ $100$ ⁠.

פתרון מלא
1. הלוח מראה $1229$ ⁠ ראשוניים עד $10\,000$ ⁠.
2. החלק: $\tfrac{1229}{10\,000} = 0.1229$ ⁠.
3. באחוזים: $12.29\%$ ⁠.
אם עניתם $25\%$ ⁠ או $16.8\%$ ⁠, השתמשתם בצפיפות של $100$ ⁠ או של $1000$ ⁠. הראשוניים מתדלדלים ככל שסופרים הלאה.
שלב 6 מתוך 6
לפתוח את השלב
כיוון אחד קל
תרגול · בחרו
השאלה
קל לכפול: $89 \times 97 = 8633$ ⁠. עכשיו בכיוון השני: מישהו נותן לכם רק את $8633$ ⁠. מה נכון לגביו?

התשובה הנכונה
- נכונה הוא מכפלה של שני ראשוניים, ולמצוא אותם לוקח הרבה יותר זמן מלכפול אותם
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
גבול הספירה
10000
ניפוי הספירלה
נפה ורווחים
האפשרויות
מוצגות בסדר אקראי.
- נכונה הוא מכפלה של שני ראשוניים, ולמצוא אותם לוקח הרבה יותר זמן מלכפול אותם
- שגויה הוא ראשוני, כי הוא לא מתחלק ב־ $2$ ⁠, $3$ ⁠, $5$ ⁠ או $7$ ⁠
  טעות נפוצה: Takes an odd number that has no obvious small factor, such as 51, 91 or 99, to be prime.
  משוב מהקטלוג
  מספר אי־זוגי לא מתחלק ב־ $2$ ⁠, אבל הוא יכול להתחלק ב־ $3$ ⁠, ב־ $7$ ⁠ או בכל ראשוני אחר. $51 = 3 \times 17$ ⁠, $91 = 7 \times 13$ ⁠ ו־ $99 = 9 \times 11$ ⁠. כדי לדעת שמספר ראשוני צריך לבדוק שאף ראשוני עד השורש שלו לא מחלק אותו: ל־ $91$ ⁠ צריך לבדוק את $2$ ⁠, $3$ ⁠, $5$ ⁠ ו־ $7$ ⁠, ו־ $7$ ⁠ מחלק אותו.
- שגויה מוצאים את הגורמים שלו באותה מהירות שבה כופלים
  משוב
  כדי למצוא את הגורמים צריך לנסות ראשוניים אחד אחרי השני, עד $\sqrt{8633} \approx 93$ ⁠: עשרים וארבעה ניסיונות, ורק האחרון, $89$ ⁠, מצליח. כל זה במקום כפל אחד.
משוב לתשובה נכונה
$8633 = 89 \times 97$ ⁠. כפל לוקח רגע, אבל הדרך הפשוטה לפרק היא לנסות ראשוניים אחד אחרי השני, וכאן צריך להגיע עד $89$ ⁠. במספרים בני מאות ספרות הכפל עדיין לוקח רגע, ולפירוק לא ידועה שום דרך מהירה. על הפער הזה, בין כיוון קל לכיוון קשה, נשענת ההצפנה.

רמז
כדי לדעת אם $8633$ ⁠ ראשוני, צריך לבדוק את כל הראשוניים עד $\sqrt{8633}$ ⁠. כמה זה?

פתרון מלא
1. $\sqrt{8633} \approx 92.9$ ⁠, ולכן צריך לבדוק את הראשוניים עד $89$ ⁠.
2. $2$ ⁠, $3$ ⁠, $5$ ⁠, $7$ ⁠ ועוד תשעה־עשר ראשוניים, עד $83$ ⁠, לא מחלקים את $8633$ ⁠.
3. $89$ ⁠ מחלק: $8633 \div 89 = 97$ ⁠.
4. $8633 = 89 \times 97$ ⁠, מכפלה של שני ראשוניים.
אם חשבתם שהוא ראשוני, עצרתם מוקדם מדי: בדיקה עד $7$ ⁠ מספיקה רק למספרים עד $120$ ⁠.

שיעור 3 מתוך 4 · כ־20 דקות

מפתחות וניחוש

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

לפתוח את השיעור

6 השלבים והתשובות שלהם

שלב 1 מתוך 6
לפתוח את השלב
הודעה נעולה
תרגול · בחרו
השאלה
אליס רוצה לשלוח לבוב הודעה נעולה במפתח. איב מעתיקה כל מה שעובר בצינור. מה הבעיה בלשלוח קודם את המפתח באותו צינור?

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

רמז
מה איב יכולה לעשות עם כל דבר שהיא מעתיקה?

פתרון מלא
1. כל מה שעובר בצינור מגיע גם לאיב.
2. אם המפתח עובר בצינור, יש לאיב אותו מפתח שיש לבוב.
3. עם המפתח היא פותחת כל הודעה שננעלה בו.
נעילה של המפתח במפתח שני לא עוזרת: את המפתח השני צריך להעביר באותה דרך.
שלב 2 מתוך 6
לפתוח את השלב
לספור מפתחות
תרגול · חשבו
השאלה
אורך המפתח קבוע על $8$ ⁠ סיביות, ולוח המכונה של איב מראה $2^8 = 256$ ⁠ מפתחות לנסות. כמה מפתחות שונים יש באורך $16$ ⁠ סיביות?

התשובה הנכונה
65540 ± 0.5
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
אורך המפתח
8 סיביותקבוע
פתיחה צעד אחר צעד
הודעה נעולהקבוע
מתקבלת בטווח
± 0.5
ערך קבוע בשאלה
תשובות שגויות שהשאלה מזהה
- 512 ± 0.5
  טעות נפוצה: Thinks the number of keys grows in step with the key's length, doubling when the length doubles, instead of doubling with every bit added.
  משוב מהקטלוג
  למפתח של $n$ ⁠ סיביות יש $2^n$ ⁠ ערכים, כי כל סיבית מכפילה את מספר האפשרויות. מפתח ארוך בשמונה סיביות לא מכיל עוד שמונה מפתחות, וגם לא פי $\tfrac{64}{56}$ ⁠, אלא פי $2^8 = 256$ ⁠. ומפתח ארוך פי שניים, $256$ ⁠ סיביות במקום $128$ ⁠, מכיל לא פי שניים מפתחות אלא פי $2^{128}$ ⁠. זו הסיבה שמפתחות ארוכים במעט מוציאים את הניחוש מכל טווח.
- 32 ± 0.5
  טעות נפוצה: Thinks the number of keys grows in step with the key's length, doubling when the length doubles, instead of doubling with every bit added.
  משוב מהקטלוג
  למפתח של $n$ ⁠ סיביות יש $2^n$ ⁠ ערכים, כי כל סיבית מכפילה את מספר האפשרויות. מפתח ארוך בשמונה סיביות לא מכיל עוד שמונה מפתחות, וגם לא פי $\tfrac{64}{56}$ ⁠, אלא פי $2^8 = 256$ ⁠. ומפתח ארוך פי שניים, $256$ ⁠ סיביות במקום $128$ ⁠, מכיל לא פי שניים מפתחות אלא פי $2^{128}$ ⁠. זו הסיבה שמפתחות ארוכים במעט מוציאים את הניחוש מכל טווח.
משוב לתשובה נכונה
$2^{16} = 65\,536$ ⁠. שמונה סיביות נוספות הכפילו את מספר המפתחות שמונה פעמים: $256 \times 2^8 = 256 \times 256$ ⁠. מפתח ארוך פי שניים מכיל לא פי שניים מפתחות, אלא את מספר המפתחות הקודם בריבוע.

רמז
כל סיבית נוספת מכפילה את מספר המפתחות. כמה סיביות נוספו?

פתרון מלא
1. לכל סיבית שתי אפשרויות, $0$ ⁠ או $1$ ⁠.
2. ל־ $16$ ⁠ סיביות: $2 \times 2 \times \dots \times 2$ ⁠, שש־עשרה פעמים, כלומר $2^{16}$ ⁠.
3. $2^{16} = 2^8 \times 2^8 = 256 \times 256 = 65\,536$ ⁠.
אם עניתם $512$ ⁠, הכפלתם פעם אחת, כאילו מפתח ארוך פי שניים מכיל פי שניים מפתחות. אם עניתם $32$ ⁠, כפלתם $16 \times 2$ ⁠.
שלב 3 מתוך 6
לפתוח את השלב
בית אחד יותר
תרגול · נבאו, ואז הסתכלו
השאלה
אורך המפתח $56$ ⁠ סיביות, כמו של DES משנת 1977, והמכונה של איב מנסה את כל המפתחות בכעשרים שעות. עכשיו המפתח יתארך לאורך $64$ ⁠ סיביות. פי כמה יגדל הזמן שאיב צריכה?

התשובה הנכונה
- נכונה פי $256$ ⁠
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
אורך המפתח
56 סיביותקבוע
פתיחה צעד אחר צעד
הודעה נעולהקבוע
האפשרויות
- נכונה פי $256$ ⁠
- שגויה פי $1.14$ ⁠, כי המפתח ארוך יותר בשביעית
  טעות נפוצה: Thinks the number of keys grows in step with the key's length, doubling when the length doubles, instead of doubling with every bit added.
  משוב מהקטלוג
  למפתח של $n$ ⁠ סיביות יש $2^n$ ⁠ ערכים, כי כל סיבית מכפילה את מספר האפשרויות. מפתח ארוך בשמונה סיביות לא מכיל עוד שמונה מפתחות, וגם לא פי $\tfrac{64}{56}$ ⁠, אלא פי $2^8 = 256$ ⁠. ומפתח ארוך פי שניים, $256$ ⁠ סיביות במקום $128$ ⁠, מכיל לא פי שניים מפתחות אלא פי $2^{128}$ ⁠. זו הסיבה שמפתחות ארוכים במעט מוציאים את הניחוש מכל טווח.
- שגויה פי $8$ ⁠, כי נוספו שמונה סיביות
  טעות נפוצה: Thinks the number of keys grows in step with the key's length, doubling when the length doubles, instead of doubling with every bit added.
  משוב מהקטלוג
  למפתח של $n$ ⁠ סיביות יש $2^n$ ⁠ ערכים, כי כל סיבית מכפילה את מספר האפשרויות. מפתח ארוך בשמונה סיביות לא מכיל עוד שמונה מפתחות, וגם לא פי $\tfrac{64}{56}$ ⁠, אלא פי $2^8 = 256$ ⁠. ומפתח ארוך פי שניים, $256$ ⁠ סיביות במקום $128$ ⁠, מכיל לא פי שניים מפתחות אלא פי $2^{128}$ ⁠. זו הסיבה שמפתחות ארוכים במעט מוציאים את הניחוש מכל טווח.
אחרי נעילת הניבוי הסצנה משתנה
אורך המפתח
64 סיביותקבוע
ואז הסצנה מראה: 0.5845 · The same in years of 365.25 days/nodes/kx/outputs/yearsToTryAll
ניבוי אף פעם לא נחשב כישלון: בכל מקרה הלומדים רואים את התוצאה ואת ההסבר.
משוב לתשובה נכונה
פי $2^8 = 256$ ⁠: מעשרים שעות לכשבעה חודשים. כל סיבית מכפילה את מספר המפתחות ואת הזמן, ולכן שמונה סיביות, בית אחד, מכפילות אותו פי $256$ ⁠. ב־1998 מכונה מיוחדת מצאה מפתח DES בפחות משלושה ימים, וזו הסיבה שהיום משתמשים במפתחות ארוכים בהרבה.

רמז
כל סיבית מכפילה את מספר המפתחות. מה עושות שמונה סיביות?

פתרון מלא
1. ב־ $56$ ⁠ סיביות יש $2^{56}$ ⁠ מפתחות, וב־ $64$ ⁠ סיביות $2^{64}$ ⁠.
2. היחס: $\tfrac{2^{64}}{2^{56}} = 2^{8} = 256$ ⁠.
3. באותו קצב ניסיון, הזמן גדל פי $256$ ⁠: מכעשרים שעות לכ־ $0.58$ ⁠ שנה.
אם בחרתם פי $1.14$ ⁠ או פי $8$ ⁠, חשבתם שמספר המפתחות גדל באותו יחס כמו אורך המפתח. הוא גדל פי שניים לכל סיבית.
שלב 4 מתוך 6
לפתוח את השלב
שמונה סיביות נוספות
תרגול · נבאו, ואז הסתכלו
השאלה
אורך המפתח $40$ ⁠ סיביות, והמכונה של איב, שמנסה $10^{12}$ ⁠ מפתחות בשנייה, עוברת על כולם בכ־ $1.1$ ⁠ שניות. כמה זמן ייקח לה מפתח של $48$ ⁠ סיביות? כתבו בשניות.

התשובה הנכונה
281.5 s ± 5%
ניבוי מספרי נחשב נכון בטווח ± 5%
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
אורך המפתח
40 סיביותקבוע
פתיחה צעד אחר צעד
הודעה נעולהקבוע
אחרי נעילת הניבוי הסצנה משתנה
אורך המפתח
48 סיביותקבוע
ואז הסצנה מראה: 281.5 s · Seconds Eve needs to try every key at guessRate keys a second/nodes/kx/outputs/secondsToTryAll
ניבוי אף פעם לא נחשב כישלון: בכל מקרה הלומדים רואים את התוצאה ואת ההסבר.
משוב לתשובה נכונה
$1.1 \times 256 \approx 281$ ⁠ שניות, קצת פחות מחמש דקות. או ישירות: $\tfrac{2^{48}}{10^{12}} \approx \tfrac{2.8 \times 10^{14}}{10^{12}} = 281$ ⁠.

משוב לתשובה שגויה
כפלו את $1.1$ ⁠ השניות של $40$ ⁠ סיביות במספר הפעמים שבו גדל מספר המפתחות.

רמז
שמונה סיביות נוספות: $2^8 = 256$ ⁠ פעמים יותר מפתחות.

פתרון מלא
1. מ־ $40$ ⁠ ל־ $48$ ⁠ סיביות נוספות $8$ ⁠ סיביות, ומספר המפתחות גדל פי $2^8 = 256$ ⁠.
2. הקצב לא משתנה, ולכן גם הזמן גדל פי $256$ ⁠.
3. $1.0995 \times 256 \approx 281.5$ ⁠ שניות.
אם כתבתם $1.3$ ⁠ שניות בערך, הגדלתם את הזמן באותו יחס כמו אורך המפתח, $\tfrac{48}{40}$ ⁠.
שלב 5 מתוך 6
לפתוח את השלב
מחוץ להישג יד
תרגול · הגיעו למטרה
השאלה
שנו את אורך המפתח עד שהמכונה של איב צריכה כשבעה חודשים, $0.58$ ⁠ שנה, כדי לנסות את כל המפתחות, ולחצו על בדיקה.

המטרה
- 0.58 ± 5%
  בתחילת השלב: 10780000000000000000
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
אורך המפתח
128 סיביות
פתיחה צעד אחר צעד
הודעה נעולהקבוע
נקרא מהסצנה בנקודה
The same in years of 365.25 days/nodes/kx/outputs/yearsToTryAll
הגדרה אחת שמגיעה למטרה
אורך המפתח
64 סיביות
משוב לתשובה נכונה
$64$ ⁠ סיביות: $\tfrac{2^{64}}{10^{12}} \approx 1.8 \times 10^7$ ⁠ שניות, כשבעה חודשים. שמונה סיביות פחות, וזה עשרים שעות; שמונה סיביות יותר, $72$ ⁠, וזה כבר כמאה וחמישים שנה.

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

רמז
שנה היא כ־ $3.2 \times 10^7$ ⁠ שניות. כמה מפתחות המכונה מנסה בשבעה חודשים?

פתרון מלא
1. שבעה חודשים הם כ־ $0.58 \times 3.16 \times 10^7 \approx 1.8 \times 10^7$ ⁠ שניות.
2. בקצב של $10^{12}$ ⁠ מפתחות בשנייה, זה כ־ $1.8 \times 10^{19}$ ⁠ מפתחות.
3. $2^{64} \approx 1.8 \times 10^{19}$ ⁠.
4. קבעו את אורך המפתח על $64$ ⁠ סיביות.
שלב 6 מתוך 6
לפתוח את השלב
פי שניים באורך
תרגול · בחרו
השאלה
מפתח של $256$ ⁠ סיביות ארוך פי שניים ממפתח של $128$ ⁠ סיביות. פי כמה מפתחות יש בו?

התשובה הנכונה
- נכונה פי $2^{128}$ ⁠, בערך $3.4 \times 10^{38}$ ⁠
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
אורך המפתח
128 סיביות
פתיחה צעד אחר צעד
הודעה נעולה
האפשרויות
מוצגות בסדר אקראי.
- נכונה פי $2^{128}$ ⁠, בערך $3.4 \times 10^{38}$ ⁠
- שגויה פי $2$ ⁠
  טעות נפוצה: Thinks the number of keys grows in step with the key's length, doubling when the length doubles, instead of doubling with every bit added.
  משוב מהקטלוג
  למפתח של $n$ ⁠ סיביות יש $2^n$ ⁠ ערכים, כי כל סיבית מכפילה את מספר האפשרויות. מפתח ארוך בשמונה סיביות לא מכיל עוד שמונה מפתחות, וגם לא פי $\tfrac{64}{56}$ ⁠, אלא פי $2^8 = 256$ ⁠. ומפתח ארוך פי שניים, $256$ ⁠ סיביות במקום $128$ ⁠, מכיל לא פי שניים מפתחות אלא פי $2^{128}$ ⁠. זו הסיבה שמפתחות ארוכים במעט מוציאים את הניחוש מכל טווח.
- שגויה פי $128$ ⁠, כי נוספו $128$ ⁠ סיביות
  טעות נפוצה: Thinks the number of keys grows in step with the key's length, doubling when the length doubles, instead of doubling with every bit added.
  משוב מהקטלוג
  למפתח של $n$ ⁠ סיביות יש $2^n$ ⁠ ערכים, כי כל סיבית מכפילה את מספר האפשרויות. מפתח ארוך בשמונה סיביות לא מכיל עוד שמונה מפתחות, וגם לא פי $\tfrac{64}{56}$ ⁠, אלא פי $2^8 = 256$ ⁠. ומפתח ארוך פי שניים, $256$ ⁠ סיביות במקום $128$ ⁠, מכיל לא פי שניים מפתחות אלא פי $2^{128}$ ⁠. זו הסיבה שמפתחות ארוכים במעט מוציאים את הניחוש מכל טווח.
משוב לתשובה נכונה
$\tfrac{2^{256}}{2^{128}} = 2^{128}$ ⁠. כבר מפתח של $128$ ⁠ סיביות דורש מהמכונה של איב פי מיליארד מגיל היקום. מפתח של $256$ ⁠ סיביות מכפיל את זה עוד $3.4 \times 10^{38}$ ⁠ פעמים. ניחוש מפתח אינו דרך לפרוץ הצפנה טובה; מה שמאיים עליה הוא חולשה בשיטה עצמה.

רמז
$\tfrac{2^{256}}{2^{128}} = ?$ ⁠

פתרון מלא
1. ב־ $128$ ⁠ סיביות יש $2^{128}$ ⁠ מפתחות, וב־ $256$ ⁠ סיביות $2^{256}$ ⁠.
2. היחס: $\tfrac{2^{256}}{2^{128}} = 2^{256 - 128} = 2^{128}$ ⁠.
3. $2^{128} \approx 3.4 \times 10^{38}$ ⁠.
כשמכפילים את אורך המפתח, מעלים את מספר המפתחות בריבוע: $2^{256} = \left(2^{128}\right)^2$ ⁠.

שיעור 4 מתוך 4 · כ־30 דקות

החלפת המפתחות של דיפי והלמן

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

לפתוח את השיעור

6 השלבים והתשובות שלהם

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

התשובה הנכונה
- נכונה כן: כל אחד מערבב צבע סודי משלו בצבע הפומבי, שולח את התערובת, ומוסיף את הסוד שלו למה שקיבל
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
הסוד של אליס
6מוסתר
הסוד של בוב
15מוסתר
הודעה נעולה / המתמטיקה
ערבוב צבעיםקבוע
האפשרויות
מוצגות בסדר אקראי.
- נכונה כן: כל אחד מערבב צבע סודי משלו בצבע הפומבי, שולח את התערובת, ומוסיף את הסוד שלו למה שקיבל
- שגויה לא: קודם הם צריכים להיפגש, או לשלוח את הסוד בשליח
  טעות נפוצה: Thinks two parties can only agree on a secret key if some secret has already passed between them, in advance or down the channel.
  משוב מהקטלוג
  זה מה שכולם חשבו עד 1976, ודיפי והלמן הראו שזה לא נכון. בהחלפת המפתחות שלהם אף סוד לא עובר בערוץ: כל צד שומר את הסוד שלו, $a$ ⁠ או $b$ ⁠, ושולח רק $g^a \bmod p$ ⁠ או $g^b \bmod p$ ⁠. כל צד מצרף לערך שקיבל את הסוד שלו, ושניהם מגיעים לאותו $s$ ⁠. איב רואה כל מה שעובר, ובכל זאת אין לה דרך מהירה להגיע ל־ $s$ ⁠.
- שגויה כן, אם כל אחד שולח את הצבע הסודי שלו מהר מספיק
  משוב
  מהירות לא עוזרת: איב מעתיקה כל קפסולה, ואם צבע סודי עובר בצינור הוא כבר לא סודי.
משוב לתשובה נכונה
כן. בצינור עוברות רק תערובות של הצבע הפומבי עם סוד, והסודות עצמם נשארים בבית. כל צד מוסיף את הסוד שלו לתערובת שקיבל, ושניהם מגיעים לאותו צבע: פומבי, סוד של אליס וסוד של בוב, בכל סדר. איב יכולה לערבב רק את שתי התערובות, וזה נותן צבע עם יותר מדי צהוב.

רמז
הסתכלו על מה שעובר בצינור בסצנה: האם צבע סודי עובר בו אי פעם?

פתרון מלא
1. צבע פומבי ידוע לכולם, גם לאיב.
2. אליס שולחת פומבי + הסוד שלה; בוב שולח פומבי + הסוד שלו. הסודות לא נשלחים.
3. אליס מוסיפה את הסוד שלה למה שקיבלה מבוב, ובוב את הסוד שלו למה שקיבל מאליס.
4. בשני הצדדים יש עכשיו פומבי + סוד של אליס + סוד של בוב: אותו צבע.
5. לאיב יש שתי תערובות, ואי אפשר להפריד צבע מתערובת.
אם עניתם שהם חייבים להיפגש, זו הייתה ההנחה של כולם עד 1976.
שלב 2 מתוך 6
לפתוח את השלב
מצבע למספר
תרגול · חשבו
השאלה
עכשיו במספרים. הערכים הפומביים: $p = 23$ ⁠ ו־ $g = 5$ ⁠. הסוד של אליס הוא $a = 6$ ⁠. מה היא שולחת, $A = 5^6 \bmod 23$ ⁠?

התשובה הנכונה
8 ± 0.1
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
הסוד של אליס
6קבוע
הסוד של בוב
15קבוע
הודעה נעולה / המתמטיקה
ערבוב צבעיםקבוע
מתקבלת בטווח
± 0.1
מחושבת מהסצנה בהגדרה של השלב
What Alice sends, A = gᵃ mod p/nodes/kx/outputs/alicePublic
תשובות שגויות שהשאלה מזהה
- 30 ± 0.1
  טעות נפוצה: Multiplies the base by the exponent (5 × 6) instead of raising it to that power (5⁶).
  משוב מהקטלוג
  $g^a$ ⁠ פירושו לכפול את $g$ ⁠ בעצמו $a$ ⁠ פעמים, לא לכפול את $g$ ⁠ ב־ $a$ ⁠. $5^3 = 5 \times 5 \times 5 = 125$ ⁠, ולא $5 \times 3 = 15$ ⁠. במודולו עושים את זה צעד אחרי צעד: כל חזקה היא הקודמת כפול $g$ ⁠, ואחר כך השארית. מ־ $5^2 \bmod 23 = 2$ ⁠ מקבלים $5^3 \bmod 23 = 2 \times 5 = 10$ ⁠.
- 15630 ± 0.1
  טעות נפוצה: Forgets to wrap round: gives the plain result instead of its remainder mod n.
  משוב מהקטלוג
  בחשבון מודולרי כל תוצאה „מסתובבת” חזרה לשעון: אחרי $n - 1$ ⁠ באה $0$ ⁠. שעה $9$ ⁠ ועוד $8$ ⁠ שעות היא לא $17$ ⁠ על שעון של $12$ ⁠, אלא $17 \bmod 12 = 5$ ⁠. גם בחזקות: $5^2 = 25$ ⁠, אבל $5^2 \bmod 23 = 2$ ⁠. אחרי כל חישוב מחלקים ב־ $n$ ⁠ ושומרים רק את השארית.
- 679 ± 0.1
  טעות נפוצה: Gives the quotient of the division (how many times it goes in) instead of the remainder.
  משוב מהקטלוג
  „ $a \bmod n$ ⁠” הוא השארית בחלוקה של $a$ ⁠ ב־ $n$ ⁠, לא התוצאה של החילוק. ב־ $17 \div 5$ ⁠ החמישייה נכנסת $3$ ⁠ פעמים, $3 \times 5 = 15$ ⁠, ונשאר $2$ ⁠: לכן $17 \bmod 5 = 2$ ⁠. השארית תמיד בין $0$ ⁠ ל־ $n - 1$ ⁠, כמו מקום על שעון עם $n$ ⁠ מקומות.
משוב לתשובה נכונה
$A = 8$ ⁠. דרך קצרה: $5^6 = (5^2)^3$ ⁠, ו־ $5^2 \bmod 23 = 2$ ⁠, ולכן $5^6 \bmod 23 = 2^3 = 8$ ⁠. את $8$ ⁠ אליס שולחת בצינור, ואיב מעתיקה אותו. את $6$ ⁠ היא לא שולחת לאף אחד.

רמז
עלו בחזקות צעד אחרי צעד, עם שארית אחרי כל כפל: $5^2 \bmod 23 = 2$ ⁠, $5^3 \bmod 23 = 10$ ⁠, $5^4 \bmod 23 = 4$ ⁠…

פתרון מלא
1. $5^2 = 25$ ⁠, ו־ $25 \bmod 23 = 2$ ⁠.
2. $5^6 = (5^2)^3$ ⁠, ולכן $5^6 \bmod 23 = 2^3 \bmod 23$ ⁠.
3. $2^3 = 8$ ⁠, קטן מ־ $23$ ⁠.
4. $A = 8$ ⁠.
אפשר גם ישירות: $5^6 = 15\,625 = 679 \times 23 + 8$ ⁠. אם עניתם $30$ ⁠, כפלתם $5 \times 6$ ⁠. אם עניתם $15\,625$ ⁠, לא לקחתם שארית, ואם $679$ ⁠, נתתם את תוצאת החילוק.
שלב 3 מתוך 6
לפתוח את השלב
המפתח של אליס
תרגול · חשבו
השאלה
הסוד של בוב הוא $b = 15$ ⁠, והוא שלח $B = 19$ ⁠. אליס מצרפת אליו את הסוד שלה, $a = 6$ ⁠. מה המפתח המשותף שלה, $s = 19^6 \bmod 23$ ⁠?

התשובה הנכונה
2 ± 0.1
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
הסוד של אליס
6קבוע
הסוד של בוב
15קבוע
הודעה נעולה / המתמטיקה
ערבוב צבעיםקבוע
מתקבלת בטווח
± 0.1
מחושבת מהסצנה בהגדרה של השלב
The shared key s = Bᵃ mod p = Aᵇ mod p/nodes/kx/outputs/sharedSecret
תשובות שגויות שהשאלה מזהה
- 22 ± 0.1
  טעות נפוצה: Multiplies the base by the exponent (5 × 6) instead of raising it to that power (5⁶).
  משוב מהקטלוג
  $g^a$ ⁠ פירושו לכפול את $g$ ⁠ בעצמו $a$ ⁠ פעמים, לא לכפול את $g$ ⁠ ב־ $a$ ⁠. $5^3 = 5 \times 5 \times 5 = 125$ ⁠, ולא $5 \times 3 = 15$ ⁠. במודולו עושים את זה צעד אחרי צעד: כל חזקה היא הקודמת כפול $g$ ⁠, ואחר כך השארית. מ־ $5^2 \bmod 23 = 2$ ⁠ מקבלים $5^3 \bmod 23 = 2 \times 5 = 10$ ⁠.
- 47050000 ± 1
  טעות נפוצה: Forgets to wrap round: gives the plain result instead of its remainder mod n.
  משוב מהקטלוג
  בחשבון מודולרי כל תוצאה „מסתובבת” חזרה לשעון: אחרי $n - 1$ ⁠ באה $0$ ⁠. שעה $9$ ⁠ ועוד $8$ ⁠ שעות היא לא $17$ ⁠ על שעון של $12$ ⁠, אלא $17 \bmod 12 = 5$ ⁠. גם בחזקות: $5^2 = 25$ ⁠, אבל $5^2 \bmod 23 = 2$ ⁠. אחרי כל חישוב מחלקים ב־ $n$ ⁠ ושומרים רק את השארית.
- 14 ± 0.1
  טעות נפוצה: Thinks the shared key can be worked out directly from the public values, for example as A × B mod p.
  משוב מהקטלוג
  הסוד המשותף הוא $s = g^{ab} \bmod p$ ⁠: כדי להגיע אליו צריך את $a$ ⁠ או את $b$ ⁠. מהערכים הפומביים אפשר לקבל רק צירופים כמו $A \times B = g^{a+b}$ ⁠, עם סכום המעריכים ולא המכפלה שלהם. כאן $A \times B \bmod 23 = 8 \times 19 \bmod 23 = 14$ ⁠, ולא $2$ ⁠. כדי למצוא את $a$ ⁠ מתוך $A$ ⁠, איב צריכה לפתור את בעיית הלוגריתם הבדיד, ולזה לא ידועה דרך מהירה.
משוב לתשובה נכונה
$s = 2$ ⁠. $19^2 \bmod 23 = 16$ ⁠, $19^4 \bmod 23 = 16^2 \bmod 23 = 256 \bmod 23 = 3$ ⁠, ו־ $19^6 \bmod 23 = 3 \times 16 \bmod 23 = 48 \bmod 23 = 2$ ⁠. זה המפתח שאליס תנעל בו את ההודעות שלה.

רמז
$19^2 = 361$ ⁠, ו־ $361 \bmod 23 = 16$ ⁠. עכשיו $19^4 = (19^2)^2$ ⁠, ו־ $19^6 = 19^4 \times 19^2$ ⁠.

פתרון מלא
1. $19^2 = 361 = 15 \times 23 + 16$ ⁠, ולכן $19^2 \bmod 23 = 16$ ⁠.
2. $19^4 \bmod 23 = 16^2 \bmod 23 = 256 \bmod 23 = 3$ ⁠, כי $256 = 11 \times 23 + 3$ ⁠.
3. $19^6 = 19^4 \times 19^2$ ⁠, ולכן $19^6 \bmod 23 = 3 \times 16 \bmod 23 = 48 \bmod 23 = 2$ ⁠.
4. $s = 2$ ⁠.
אם עניתם $22$ ⁠, כפלתם $19 \times 6$ ⁠ במקום להעלות בחזקה. אם עניתם $14$ ⁠, כפלתם את שני הערכים הפומביים, $8 \times 19$ ⁠: את זה גם איב יכולה לעשות, וזה לא המפתח.
שלב 4 מתוך 6
לפתוח את השלב
המפתח של בוב
תרגול · נבאו, ואז הסתכלו
השאלה
בוב קיבל מאליס $A = 8$ ⁠, ומצרף אליו את הסוד שלו: הוא מחשב $8^{15} \bmod 23$ ⁠. מה הוא יקבל? בחרו, ואחר כך מבט פנימה יעבור להמתמטיקה.

התשובה הנכונה
- נכונה $2$ ⁠, אותו מפתח שיש לאליס
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
הסוד של אליס
6קבוע
הסוד של בוב
15קבוע
הודעה נעולה / המתמטיקה
ערבוב צבעיםקבוע
האפשרויות
- נכונה $2$ ⁠, אותו מפתח שיש לאליס
- שגויה מספר אחר, כי כל אחד השתמש בסוד אחר
  משוב
  כל אחד השתמש בסוד אחר, אבל כל אחד קיבל מהשני את הסוד השני, ארוז בתוך $A$ ⁠ או $B$ ⁠. בשני הצדדים יש בסוף $g$ ⁠ בחזקת $a$ ⁠ ובחזקת $b$ ⁠.
- שגויה $19$ ⁠, המספר שבוב עצמו שלח
  משוב
  $19$ ⁠ הוא $5^{15} \bmod 23$ ⁠: הסוד של בוב בלבד. ב־ $8^{15}$ ⁠ יש גם את הסוד של אליס, כי $8 = 5^6 \bmod 23$ ⁠.
אחרי נעילת הניבוי הסצנה משתנה
הודעה נעולה / המתמטיקה
המתמטיקהקבוע
ואז הסצנה מראה: 2 · The shared key s = Bᵃ mod p = Aᵇ mod p/nodes/kx/outputs/sharedSecret
ניבוי אף פעם לא נחשב כישלון: בכל מקרה הלומדים רואים את התוצאה ואת ההסבר.
משוב לתשובה נכונה
$2$ ⁠, בדיוק כמו אליס. $A^b = (g^a)^b = g^{ab}$ ⁠ ו־ $B^a = (g^b)^a = g^{ab}$ ⁠: שני הצדדים מחשבים את $5^{90} \bmod 23$ ⁠, כל אחד בדרך שלו. זה כל הטריק של דיפי והלמן, משנת 1976.

רמז
$8 = 5^6 \bmod 23$ ⁠, ולכן $8^{15} \bmod 23 = 5^{6 \times 15} \bmod 23$ ⁠. ומה זה $19^6 \bmod 23$ ⁠?

פתרון מלא
1. $A = 5^6 \bmod 23$ ⁠, ולכן $A^{15} \bmod 23 = 5^{6 \times 15} \bmod 23 = 5^{90} \bmod 23$ ⁠.
2. $B = 5^{15} \bmod 23$ ⁠, ולכן $B^{6} \bmod 23 = 5^{15 \times 6} \bmod 23 = 5^{90} \bmod 23$ ⁠.
3. אותו מספר: $s = 2$ ⁠.
4. אפשר לבדוק: $5^{22} \bmod 23 = 1$ ⁠, ו־ $90 = 4 \times 22 + 2$ ⁠, ולכן $5^{90} \bmod 23 = 5^2 \bmod 23 = 2$ ⁠.
שלב 5 מתוך 6
לפתוח את השלב
החיפוש של איב
תרגול · הגיעו למטרה
השאלה
עכשיו אתם איב. ראיתם את בוב שולח $B = 19$ ⁠, ואתם יודעים ש־ $g = 5$ ⁠ ו־ $p = 23$ ⁠. מצאו את הסוד שלו: שנו את הסוד של בוב עד ש־ $B = 5^b \bmod 23$ ⁠ יוצא $19$ ⁠, ולחצו על בדיקה.

המטרה
- 19 ± 0.1
  בתחילת השלב: 5
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
הסוד של אליס
6קבוע
הסוד של בוב
1
הודעה נעולה / המתמטיקה
המתמטיקהקבוע
נקרא מהסצנה בנקודה
What Bob sends, B = gᵇ mod p/nodes/kx/outputs/bobPublic
הגדרה אחת שמגיעה למטרה
הסוד של בוב
15
משוב לתשובה נכונה
$b = 15$ ⁠. כדי למצוא אותו הייתם צריכים לנסות, אחד אחרי השני, כי החזקות מדלגות על פני החוגה בלי סדר. זו בעיית הלוגריתם הבדיד: עם $23$ ⁠ מקומות זה לוקח דקה, עם ראשוני בן מאות ספרות זה לוקח יותר מגיל היקום, אבל לאליס ולבוב חזקה לוקחת חלק זעיר של שנייה גם אז.

משוב לתשובה שגויה
עוד לא. המשיכו לנסות: אחד מ־ $22$ ⁠ המעריכים נותן $19$ ⁠.

רמז
אין קיצור דרך: נסו מעריכים אחד אחרי השני והסתכלו על $B$ ⁠.

פתרון מלא
1. איב יודעת $g = 5$ ⁠, $p = 23$ ⁠ ו־ $B = 19$ ⁠, ומחפשת $b$ ⁠ שבו $5^b \bmod 23 = 19$ ⁠.
2. החזקות: $5^1 \to 5$ ⁠, $5^2 \to 2$ ⁠, $5^3 \to 10$ ⁠, …, $5^{14} \to 13$ ⁠, $5^{15} \to 19$ ⁠.
3. $b = 15$ ⁠: קבעו את הסוד של בוב על $15$ ⁠.
לא ידועה שום דרך מהירה בהרבה מלנסות. לכן בהחלפה אמיתית $p$ ⁠ הוא ראשוני בן מאות ספרות.
שלב 6 מתוך 6
לפתוח את השלב
פומבי וסודי
תרגול · בחרו
השאלה
איב העתיקה את $g = 5$ ⁠, $p = 23$ ⁠, $A = 8$ ⁠ ו־ $B = 19$ ⁠. מה עוד היא צריכה כדי לחשב את המפתח המשותף $s$ ⁠?

התשובה הנכונה
- נכונה את $a$ ⁠ או את $b$ ⁠: היא צריכה לפתור $5^x \bmod 23 = 8$ ⁠ או $5^x \bmod 23 = 19$ ⁠
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
הסוד של אליס
6
הסוד של בוב
15
הודעה נעולה / המתמטיקה
המתמטיקה
האפשרויות
מוצגות בסדר אקראי.
- נכונה את $a$ ⁠ או את $b$ ⁠: היא צריכה לפתור $5^x \bmod 23 = 8$ ⁠ או $5^x \bmod 23 = 19$ ⁠
- שגויה כלום: $s = A \times B \bmod p$ ⁠
  טעות נפוצה: Thinks the shared key can be worked out directly from the public values, for example as A × B mod p.
  משוב מהקטלוג
  הסוד המשותף הוא $s = g^{ab} \bmod p$ ⁠: כדי להגיע אליו צריך את $a$ ⁠ או את $b$ ⁠. מהערכים הפומביים אפשר לקבל רק צירופים כמו $A \times B = g^{a+b}$ ⁠, עם סכום המעריכים ולא המכפלה שלהם. כאן $A \times B \bmod 23 = 8 \times 19 \bmod 23 = 14$ ⁠, ולא $2$ ⁠. כדי למצוא את $a$ ⁠ מתוך $A$ ⁠, איב צריכה לפתור את בעיית הלוגריתם הבדיד, ולזה לא ידועה דרך מהירה.
- שגויה את $a$ ⁠ וגם את $b$ ⁠
  משוב
  מספיק אחד מהם: עם $a$ ⁠ איב מחשבת $B^a \bmod p$ ⁠, בדיוק כמו אליס, ועם $b$ ⁠ היא מחשבת $A^b \bmod p$ ⁠, כמו בוב.
משוב לתשובה נכונה
היא צריכה את אחד הסודות. $A \times B = g^{a} \times g^{b} = g^{a+b}$ ⁠, עם סכום המעריכים, ולא $g^{ab}$ ⁠: כאן $8 \times 19 \bmod 23 = 14$ ⁠, ולא $2$ ⁠. כדי לחלץ את $a$ ⁠ מתוך $A$ ⁠ היא צריכה לפתור לוגריתם בדיד, וזה החלק הקשה.

רמז
$s = g^{ab} \bmod p$ ⁠. מה איב יכולה לקבל מ־ $A$ ⁠ ו־ $B$ ⁠ בלי לדעת את המעריכים?

פתרון מלא
1. המפתח המשותף: $s = g^{ab} \bmod p$ ⁠.
2. מהערכים הפומביים איב יכולה לחשב צירופים כמו $A \times B \bmod p = g^{a+b} \bmod p = 14$ ⁠, אבל לא את $g^{ab}$ ⁠.
3. אם היא מוצאת את $a$ ⁠, היא מחשבת $B^a \bmod p = s$ ⁠. אם היא מוצאת את $b$ ⁠, היא מחשבת $A^b \bmod p = s$ ⁠.
4. לכן היא צריכה את $a$ ⁠ או את $b$ ⁠, כלומר לפתור $5^x \bmod 23 = 8$ ⁠ או $5^x \bmod 23 = 19$ ⁠.

בכל היחידה · 10 טעויות נפוצות

קטלוג הטעויות הנפוצות

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

תוכן העניינים

חשבון של שעון

שארית

השאלה

התשובה הנכונה

הסצנה בשלב הזה

תשובות שגויות שהשאלה מזהה

רמז

פתרון מלא

סביב השעון

השאלה

התשובה הנכונה

הסצנה בשלב הזה

תשובות שגויות שהשאלה מזהה

רמז

פתרון מלא

חזקות במודולו

השאלה

התשובה הנכונה

הסצנה בשלב הזה

תשובות שגויות שהשאלה מזהה

רמז

פתרון מלא

צעד אחרי צעד

השאלה

המטרה

הסצנה בשלב הזה

הגדרה אחת שמגיעה למטרה

רמז

פתרון מלא

דילוגים

השאלה

התשובה הנכונה

הסצנה בשלב הזה

אחרי נעילת הניבוי הסצנה משתנה

רמז

פתרון מלא

סיבוב שלם

השאלה

התשובה הנכונה

הסצנה בשלב הזה

האפשרויות

אחרי נעילת הניבוי הסצנה משתנה

רמז

פתרון מלא

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

מה זה ראשוני

השאלה

התשובה הנכונה

הסצנה בשלב הזה

האפשרויות

רמז

פתרון מלא

הגדול ביותר עד מאה

השאלה

התשובה הנכונה

הסצנה בשלב הזה

תשובות שגויות שהשאלה מזהה

רמז

פתרון מלא

הנפה

השאלה

התשובה הנכונה

הסצנה בשלב הזה

האפשרויות

אחרי נעילת הניבוי הסצנה משתנה

רמז

פתרון מלא

מתדלדלים

השאלה

המטרה

הסצנה בשלב הזה

הגדרה אחת שמגיעה למטרה

רמז

פתרון מלא

שמינית

השאלה

התשובה הנכונה

הסצנה בשלב הזה

תשובות שגויות שהשאלה מזהה

רמז