ב-Online
 
 
 
 
 
 
 
לפרק את הבייט 
מוזיקת המקרה 
 
 תוצאה אקראית? לא בטוח    צילום: GettyImages    
לפרק את הבייט |
 

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

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

נניח שאנחנו רוצים להצפין את המחרוזת החשובה "סופגניה עם ריבה". היא כוללת 15 תווים, שניתן לייצג אותם בקוד ASCII שבו כל תו הוא בייט יחיד. האות "א" מיוצגת בקוד זה על ידי המספר 128, האות "ב" על ידי 129 וכן הלאה. ניצור מחרוזת באורך זהה של בייטים עם ערכים אקראיים לגמרי – מחרוזת חדשה זו תהיה המפתח שלנו. כעת, נחבר לכל בייט במחרוזת המקורית את הבייט המקביל במפתח. טווח הערכים של בייט הוא בין 0 ל-255, וכשמבצעים בו פעולות חשבוניות שחורגות מטווח זה הוא מתנהג בצורה מעגלית, כמו שעון מחוגים: הוסיפו שעתיים לשעה 11 ותקבלו 1, החסירו חמש שעות מ-3 ותקבלו 10. לכן, אם נצפין את האות "א" בעזרת הבייט האקראי 185, התוצאה תהיה 57. המחרוזת המקורית תהפוך לרצף חסר משמעות לכאורה של בייטים, וללא המפתח אין שום אפשרות לפענח אותה, אלא אם כן נקבל המון מסרים שהוצפנו בעזרת אותו מפתח בדיוק – אלא שכאמור, הוא חד-פעמי.
 
 
שיטת הצפנה זו חזקה להפליא אך אינה מעשית במיוחד, כיוון שקשה מאד להעביר את המפתחות עצמם בין הצד המצפין לצד המפענח. כיוון שכך, משתמשים בשיטה זו רק לעתים נדירות מאד.

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


function GenerateKey(const Length : integer) : array of byte;
var j : integer;
begin
SetLength(Result, Length);
Randomize;
for j := 1 to Length do Result[j] := Random(256);
end;


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

אקראיות אמיתית ומדומה

קוד
 קוד 
 צילום: פליקר, p373, רשיון cc-by-sa 
 
במילים פשוטות, אירוע אקראי הוא אירוע שאיננו יכולים לחזות מראש. כמובן שהיכולת הזו תלויה בכמות המידע שיש לנו וביכולת החישוב שלנו. למשל, התוצאה של הטלת מטבע נחשבת לאקראית ביותר, אבל אם היה לנו מידע פיזיקלי מדויק על המטבע ועל כל הכוחות שמופעלים במהלך ההטלה, ייתכן שהיינו יכולים לנבא בעזרת סימולציית מחשב את התוצאה בכל פעם מחדש.

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

ללכוד את המקריות

סדרות אקראיות הן קריטיות לצורך הצפנה או סימולציות רציניות של תהליכים פיזיקליים (כגון מזג האוויר או פיצוץ אטומי), אלא שקשה מאד להפיק אותן. מנגנונים פיזיקליים אקראיים כגון מטבעות, קוביות או רולטה הם יעילים בתיאוריה, אבל איטיים מאד ומפיקים טווח מצומצם של מספרים. חוץ מזה, כמובן, הם עשויים להיות מוטים. קוביות "מזויפות" בנויות כך שמרכז הכובד שלהן אינו באמצע אלא קרוב יותר לאחת הפאות, כך שהסיכוי שהקוביה תיפול עם אותה פאה כלפי מטה גדול קצת יותר. ברוב הקוביות, המספרים מצוינים על ידי שקעים קטנים צבועים. השקעים הם, כמובן, חלולים – כלומר שככל שיש יותר שקעים בפאה מסוימת, היא תהיה קלה יותר! האפקט הזה בוודאי זעיר להפליא, אבל יש סיכוי שהוא מטה במידה כלשהי את התוצאות. אם נטיל קוביה מספיק פעמים, אולי נגלה שהתוצאות אינן מתפלגות באמת באופן שווה. אז מה עושים?
 
אקראיות מוחלטת (הופק באמצעות random.org)
 אקראיות מוחלטת (הופק באמצעות random.org)   
מתברר שיש אנשים שהמקצוע שלהם הוא לספק מספרים אקראיים. דוקטור מדס האאר מדבלין מספק לכל דורש, באמצעות אתר האינטרנט שלו random.org, מידע אקראי בצורת רשימות מספרים, מחרוזות, תמונות, קובצי רעש לבן ועוד. המידע הזה מגיע משלושה מקלטי רדיו שמכוונים בין תחנות וקולטים רעש אקראי מהאטמוספרה, וכן על אלגוריתמים חכמים שרצים ברקע ומוודאים שלא מופיעות תבניות ניתנות-לחיזוי כלשהן בנתונים. צרכני אקראיות כבדים יכולים ליצור חשבון בתשלום ולקבל מידע בכמויות גדולות יותר ובפורמטים מגוונים.
 
פרויקט HotBits של מעבדות פרמי מספק גם הוא ביטים אקראיים, שמבוססים על התפרקות רדיואקטיבית אקראית של גרעינים אטומיים, שנמדדת באמצעות מונה גייגר שמחובר למחשב. קצב הפקת הנתונים איטי מאד יחסית, בערך 100 בייטים לשניה. בימים שלפני האינטרנט, השגה של נתונים כאלה היתה קשה הרבה יותר – עד כדי כך שאנשים השתמשו בספרים מיוחדים שהכילו אך ורק ספרות אקראיות. חובבי נוסטלגיה ומשוגעים-לדבר עוד יכולים להשיג ספרים כאלה באמאזון.
 

אקראיות מתוכננת היטב

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

נחזור לפונקציית ההצפנה שלנו. המתכנת הלא-זהיר הכניס את פקודת האיפוס לתוך הפונקציה עצמה, כך שמחולל המספרים הפסודו-אקראיים מאופס עבור כל מפתח חדש שנוצר. בשפת דלפי ניתן לאפס את המחולל ידנית באמצעות ערך מספרי מסוג Integer של 32 ביטים, כלומר בין מינוס לפלוס שני מיליארד, מאה ארבעים ושבעה מיליון וחצי, בערך. גם האיפוס האקראי של פקודת Randomize עובד על הטווח הזה. כל שעלינו לעשות כדי לפצח את הצופן הוא להשיג הודעה מוצפנת ולדעת אילו תווים צפויים להופיע בה. נניח שאנו יודעים שההודעה מכילה רק תווים בעברית, ספרות, רווחים וסימני פיסוק. נכתוב פונקציה משלנו ליצירת מפתחות ונעבור על כל ארבעה מיליארדי האפשרויות לאיפוס המחולל. בעזרת כל מפתח חדש שנוצר ננסה לשחזר את ההודעה המקורית, ונעצור את הניסיון כשניתקל בתו מפוענח שאינו חוקי (שמעיד שהמפתח שגוי). מחשב ביתי רגיל, בעזרת תוכנה שלא עברה שום אופטימיזציה מיוחדת, הצליח לבחון את כל האפשרויות תוך דקה וארבעים לערך, כלומר שהמפתח הנכון התגלה וההצפנה ה"מושלמת" פוצחה בממוצע תוך חמישים שניות בלבד.
 
 
 
@@@@@@@@@@@@@@@@@@@ ilan @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 
@@@@@@@@@@@@@@@@@@@ ilan @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 
 
תגובות
הוסף תגובה0 תגובות
הוספת תגובה
מאת
 
נושא
 
תוכן
 
 
 
 
תודה! תגובתך התקבלה.
התגובה תתפרסם בכפוף לתנאי האתר.
 
 
 
 
 

כל הזכויות שמורות 2011 © נענע 10 בע"מ
 
 
 
 
כל הזכויות שמורות © Nana10 בע"מ
Video powered by