פונקציות גיבוב - מה הפשט?

היי,

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

תודה מראש

היי תומר,

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

מוסיף קצת קידום עצמי חסר בושה – 2 פוסטים שכתבתי בעבר בנושא:

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

משרשר לכאן.

עד סעיף 3 - אני מבין שהפעולות היו שרירותיות. תוכל לענות על השאלה שנתת פה? למה מודולו ולמה הערך הספציפי הזה? ומה הקשר בין ה מודולו X לאורך קבוע X.

" 1. כדי שהפלט תמיד יהיה באורך זהה, נשתמש במודולו 100,297 על התוצאה (חשבו: איך מודולו גורם לזה לקרות?)

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

תודה

1. מה מודולו עושה?
2. מה המספר המקסימלי שיוצא מ־n % 100? ומ־n % 1000? ומ־n % 10000?

( אמ;לק : עבור n%x מחזיר מספרים בין 0 ל x ) - אז עבור 100297 - לא נוכל לקבל מספר ארוך יותר ממנו.

(אם מישהי אחרת תרצה פירוט בעתיד)
והדרך הארוכה - כולל תשובות למה ששאלת :

מחזיר שארית בין שני מספרים. ( לדוג’ 2 = 5 % 7 )

%100 - 99 (הדו ספרתי הגדול ביותר) , %1000 - 999 - %10000 - 9999
(עבור חזקות של 10 - יחזיר את (חזקה) הספרות אחרונות של n )

כש n % x - כל n עד x יחזיר n
n = x * i יחזיר 0
x * i > n > x יחזיר את ההפרש ביניהם. (n-x)

@Yam

אני חושב שמה שבילבל אותי (ושלח אותי להבין לעומק) היה המשפט : “מחזירה ערכים באורך קבוע”

הפונק’ לא “:מחזירה ערכים באורך קבוע”. אלא מחזירה ערך שנמצא בטווח ערכים קבוע בין 0 ל 100,297(לא כולל)

אני מניחה שהכוונה היא שהערכים הם באורך קבוע של מילת מחשב. הכוונה אינה שהם באורך קבוע בייצוג העשרוני הרגיל

מהוא ה i במשוואה ? בחלק האחרון

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

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

י i הוא כופל של x בכל סבב של חישוב השארית, כמו מונה בלולאה.

כך שמודולו מתבצע בעצם על איבר x*i - והמקרה הטריוויאלי הוא הראשון כש i = 1

מה שאומר שכל הכפולות של מספר x יחזירו מודולו 0

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

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

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

זה משפט מבלבל נורא. פונקציית גיבוב לא מחזירה אמת או שקר.
אפשר לדמיין אותה כפונקצייה חד חד ערכית (היא לא[1]) שכשנותנים לה קלט היא מחזירה פלט מעורבל.
עבור אותה פונקציית גיבוב (נניח SHA1), מאותו קלט, תמיד יצא אותו פלט. עבור שני קלטים לעולם לא יצא אותו פלט (כמעט[1]).
אם משה נרשם והזין את הסיסמה password1 ואז שלומי נרשם והזין את הסיסמה password1, שניהם יקבלו את אותו פלט מפונקציית הגיבוב[2].
הדבר הנחמד בפונקציית גיבוב זה שכשהאקר שם את ידיו על מסד הנתונים, בו נשמר רק הגיבוב של password1, הוא לא יוכל להבין שהסיסמה אכן הייתה password1. הוא יראה משהו בסגנון של e38ad214943daad1d64c102faec29de4afe9da3d.

[1]
ניתן להוכיח די בקלות למה פונקציות גיבוב הן לא חד־חד־ערכיות (היא כן פונקציית על) בזכות עקרון שובך היונים:

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

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

היי
אם אנחנו כבר כאן, מקבלת שגיאה בכתיבת הפונקציה הנדרשת בתרגיל הנל
IndentationError: unexpected indent (< string >, line 1)

השורה הראשונה היא תחילת הפונקציה def
לא הצלחתי להבין מה לא טוב בקוד
אוכל לשלוח את הקוד בפרטי
תודה

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

באותה מידה יכלנו להשתמש במספר אחר באותו אורך במקום 100297? יש סיבה שהשתמשו דווקא בו?

כן. להבנתי זו בחירה שרירותית.
מודולו X יתן לך מספרים בין 0 ל X. - לא יחזיר מספרים ארוכים ממנו.

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