סיסמאות ואנטרופיה – האורך כן קובע

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

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

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

בואו ניתן דוגמא נוספת – תחנת מזג אויר שולחת עבור כל יום שתי מדידות: האם היה קר או לא, והאם היה גשום או לא. באיזור שנמדד 75% מהימים הם קרים וגשומים, עוד 15% קרים ויבשים, רק 7% גשומים וחמים והיתר יבשים וחמים. הנתונים נשלחים במקבצים של 100 ימים כל פעם.

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

00: חם ויבש

01: חם וגשום

10: קר ויבש

11: קר וגשום

מאוד פשוט לעבוד עם פרוטוקול כזה מבחינת פענוח (כל יום מיוצג על ידי שני ביטים בדיוק), ובפרוטוקול כזה נשלח 2 ביטים עבור כל יום, ועבור 100 ימים סה"כ 200 ביטים.

עכשיו נחשוב על הפרוטוקול הבא:

0 – קר וגשום

10 – קר ויבש

110 – יום חם וגשום

1110 – יום חם ויבש

גם הפרוטוקול הזה פשוט לעבודה שכן 0 משמש כחוצץ (כל הודעה של יום מסוים מסתיימת ב0),  אבל על פניו הוא פחות יעיל מהראשון שכן אורך ההודעה הממוצע הוא 2.5 ביט לעומת 2 בראשון.  האמת היא שבנתוני השאלה הפרוטוקול הזה יעיל יותר שכן לכל מאה יום נשלח בערך 75 הודעות של תו אחד, 15 של שני תוים וכו', ובסך הכל מקבץ של 100 ימים ידרוש 138 ביט בלבד!

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

אותיות ומספרים – האמנם?

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

האנטרופיה של סיסמא מסוימת זהה לכמות הניסיונות שיש לעשות כדי לפצח אותה. סיסמא בת 6 תוים מהאלף בית האנגלי תכיל 266 פרמוטציות, ובאופן כללי הצורה הי­­­א   nm כאשר n הוא מספר האפשרויות לכל תו וm הוא אורך המחרוזת.

אם אנחנו "משחקים" עם מספר האפשרויות לכל תו, הפונקציה שלנו נראית כמו חזקה רגילה מהצורה xm, ואילו אם נשחק אם אורך המחרוזת נקבל nx – פונקציה מעריכית שמאופיינת בכך שהיא גדלה מהר יותר מכל פולינום!

באופן יותר קונקרטי, ניקח כדוגמא סיסמא בת 6 אותיות. עכשיו נכריח את המשתמשים להשתמש בכל מה שיש למקלדת להציע – אותיות קטנות וגדולות, מספרים וסמלים מיוחדים, סה"כ 72 תוים. האנטרופיה החדשה היא 726 או 1.39314E+11.

עכשיו נבדוק כיוון אחר – נשתמש רק באותיות, אפילו ללא רגישות לאותיות קטנות וגדולות, ונוסיף סה"כ 2 תוים לסיסמא. עכשיו נקבל 228שהם 1.20727E+12, כלומר הרוחנו יותר על ידי פעולה פשוטה של הוספת 2 תוים לאורך, מאשר על ידי פעולה מסורבלת של הגדלת מס' התוים האפשריים.

מבחינת שימושיות ברור שלאדם יותר קל לזכור סיסמאות ארוכות ובעלות משמעות (למשל הסיסמא my password is strong) מאשר סיסמאות מוזרות עם ספרות ותוים כמו pa$$w0rD ולכן לא ברור מי חשב שעדיף לקבל מעט אנטרופיה ובקושי (על ידי הגדלת האפשרויות לכל תו) בזמן שאפשר לקבל הרבה אנטרופיה, ובקלות (על ידי סיסמאות ארוכות שניתן לכתוב באנגלית פשוטה).

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

2 מחשבות על “סיסמאות ואנטרופיה – האורך כן קובע

  1. ניטפיקינג קל – 6 בחזקת 22 זה עבור הא"ב העברי, עבור ה- ABC זה יהיה 6 בחזקת 26. לא שאני חושב שזה ישנה את התוצאה…

כתיבת תגובה

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

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s