חישוב בקריפטוגרפיה

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

במאמר זה נחקור עוד על hashing.

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

נשמע מבלבל?

בואו ננסה להבין לפי הדוגמה.

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

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

דוגמה מודרנית לחשיש תהיה שחקני משחק שנרשמים למשחק. Valorant הוא משחק חופשי לשחק שהושק על ידי Riot. להיות חופשי לשחק פירושו שמיליוני אנשים ישחקו במשחק.

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

בואו ננסה להבין את זה ביתר פירוט בהמשך.

 

מה זה Hashing?

כאמור לעיל, Hashing היא שיטת הזיהוי של אובייקט מקבוצה.


כל אובייקט מקבל מספר זיהוי ייחודי לאחר חשיפתו.

אבל, מה זה אומר טכנית?

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

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

אם אתה שם את “שלום עולם!” ב אלגוריתם חשיש של SHA-256, תקבל את הפלט הבא:

קֶלֶט: שלום עולם!

תְפוּקָה: dffd6021bb2bd5b0af676290809ec3a53191dd81c7f70a4b28688a362182986f

כאן SHA256 מייצר את הפלט מהקלט הנתון. כפי שאתה יכול לראות, השתמשנו באלגוריתם הגיבוב של Secure Hash (SHA-256). זוהי אחת משיטות הגיבוב הפופולריות שם, כולל Message Direct (MD5), ו- Secure Hash Function (SHA1).

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

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

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

אבל אם אתה כאן בשביל דברים מתקדמים, אתה לא תתאכזב.

 

מהי פונקציית Hash וטבלאות Hash? ואיך הם עובדים?

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

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

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

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

בשיטה השנייה, הפונקציות יהיו כמפורט להלן:

hash = hash_function (מפתח) אינדקס = hash% array_size

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

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

 

כתיבת פונקציה טובה

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

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

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

 

מדוע אנו זקוקים לפונקציית Hash טובה?

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

נניח שאנחנו רוצים ליצור טבלת Hash באמצעות טכניקת hashing בה מחרוזות הקלט יהיו כדלקמן, {“agk”, “kag”, “gak”, “akg”, “kga”, “gka”}

כעת, אנו יוצרים פונקציית hash שמוסיפה בפשטות את ערך ASCII של a (97), g (103) ו- k (107) ואז עושה מודול של הסכום ב- 307.

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

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

 

לימוד אודות שולחנות האש

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

באופן מסורתי טבלאות האש הן בחירה טובה בפתרון בעיות הדורשות זמן O (n).

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

לכן, אם מחרוזת = “aacddce”, אז גישה כללית היא לעבור על המחרוזת מספר פעמים ולאחסן כל תדר.

# ספק מחרוזת קלט, וספור את תדירות התווים במחרוזת זו

# האלגוריתם הוא זמן מורכבות 0 (n)

temp_list = [] התחל = "א" str = "ababcddefff" def alpha_zeta (): alpha = ‘a’ עבור i בטווח (0,26): temp_list.append (alpha) alpha = chr (ord (alpha) + 1) return temp_list temp_list = alpha_zeta () #print (temp_list) def תדר_תדירות (str, temp_list): עבור כל אחד ב- temp_list: freq = 0 עבור i in str: if (i == each each): freq = freq + 1 print (each, freq) character_frequency (str, temp_list)

התפוקה של התוכנית לעיל תהיה כדלקמן:

a 2 b 2 c 1 d 2 e 1 f 3 g 0 h 0 i 0 .. ..

עכשיו, בואו וניישם טבלת חשיש ב- C ++ ונמנה את תדירות התווים.

# כלול שימוש ב- namespace std; תדר int [26]; int hashFunc (char c) {return (c – ‘a’); } void countFre (מחרוזת S) {עבור (int i = 0; i< S.length (); ++ i) {int index = hashFunc (S [i]); תדר [אינדקס] ++; } עבור (int i = 0; i<26; ++ i) {cout << (char) (i + ‘a’) << ” << תדר [i]<< endl; }} Int main () {cout<<"שלום עולם"; countFre ("abbaccbdd"); }

תפוקת התוכנית תהיה כמו להלן:

a 2 b 3 c 2 d 2

מורכבות ה- O (N) של האלגוריתם הופכת אותו למהיר יותר בהשוואה לגישות לינאריות אחרות.

כיצד לפתור התנגשויות

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

 

חקר האש בפייתון

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

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

התחביר של שיטת החשיש הוא:

חשיש (אובייקט)

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

הערך המוחזר של שיטת ה- hash () תלוי בקלט. עבור מספר שלם, הוא עשוי להחזיר את אותו המספר ואילו עבור עשרוני ומחרוזת יהיו שונים.

בואו נראה כמה דוגמאות למטה.

num = 10 deci = 1.23556 str1 = "ניטש" הדפס (hash (num)) הדפס (hash (deci)) הדפס (hash (str1))

הפלט של הקוד שלעיל הוא להלן:

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

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

תנועות = (‘a’, ‘e’, ​​’i’, ‘o’, ‘u’) הדפס (hash (vowels)) פלט ⇒ -5678652950122127926

חישוב בקריפטוגרפיה

Hashing שימושי לקריפטוגרפיה. ביטקוין משתמש ב- hashing כדי ליצור ולנהל עצי מרקל

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

עצי מרקל

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

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

עצי מרקל פותרים את הבעיה על ידי מתן דרך מהימנה ויעילה לשיתוף ואימות נתונים בין עמיתים.

דוגמה לעץ מרקל

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

עצי מרקל הוא עץ הפוך שיכול לסכם את כל מערך העסקה.

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

מדריך לעצי מרקל. שם דנו כיצד מיישמים עצי מרקל בביטקוין ובמקרי שימוש אחרים.

תהליך כרייה

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

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

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

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

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

ניתן לסכם את התהליך בשלבים הבאים:

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

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

 

סיכום

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

אז מה אתה חושב על זה? הגיבו למטה והודיעו לנו.

 

#שאלות נפוצות

מה מסתובב בקריפטוגרפיה?

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

כיצד משתמשים ב- hashing בקריפטוגרפיה?

קריפטוגרפיה משתמשת בסיסמאות hash ל- hash או ליצור מספרי זיהוי ייחודיים.

Mike Owergreen Administrator
Sorry! The Author has not filled his profile.
follow me
Like this post? Please share to your friends:
Adblock
detector
map