גימטרעה

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

המתמטיקה של RSA

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

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

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

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

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

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

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

אוף, כל הקטע עם השורש הריבועי באמת יוצא מסובך

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

ועכשיו למשהו מסובך יותר – הוצאת שורש ריבועי!

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