קריפטוגרפיה קוונטית

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

מה הקשר בין מספרים ראשוניים וקריפטוגרפיה?

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

ההרצאות שלי בפסטיבל אייקון 2012

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

פנקס חד-פעמי – הצופן המושלם (?)

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

ושאינו יודע מה שאלו

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

אז מה הקטע עם המאגר הביומטרי?

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

אז איך באמת בודקים ראשוניות (בעזרת אלגוריתם מילר-רבין)?

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

למה RSA טרם נפרץ? (בגלל החשיבה המתמטית הלא פרקטית)

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

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

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

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

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

מה קורה כשמחלקים שרלטן באפס? כשזה פומבי זה נהיה מביך

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

להמשיך ללכת, אין מה לראות פה

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

שיתוף, זה כל הסוד

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

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

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

כיצד פרדוקס יום ההולדת מוליד חוב בבנק

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

זה לא ראשוני, זה אפילו לא פריק

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

המתמטיקה של RSA

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

זמן לחתום (בתמצות) את סאגת אליס ובוב

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

אליס ובוב: ידועים בציבור

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

עולמם המופלא של אליס ובוב

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