 |
בפרק העשירי: פיצוח מספרים וצפנים. כפי שכתב טל דיון 2734 הספר אינו ספר מתמטיקה אלא ספר על ההיסטוריה של המתמטיקה ולא בטוח שהנסיון שם להסביר את האלגוריתם מילולית תוך שימוש מינימלי בביטויים מתמטיים ימצא חן בעיניך (הסברים כאלו לעיתים גם מתקשים לחצות את מחסום התרגום). הסבר תמציתי שלא בורח מביטויים יש ב"סודות ההצפנה" של סיימון סינג בנספח י: המתמטיקה של צופן RSA.
לגבי ההרחבה, אני ממש לא הכתובת כי אני חובבן מתמטי לחלוטין. אני יכול רק לצטט את ההסבר הציורי של סינג בסודות ההצפנה:
א. יסוד הצופן הוא במנגנון המפתחות הציבוריים של דיפי-הלמן: נניח שא(ני) רוצה לשלוח לב(נק) את מספר האשראי שלי באופן בטוח. הבנק מייצר עבורי קופסת מטמון קטנה בעלת 2 מפתחות, מפתח נועל ומפתח פותח. הבנק שולח לי את הקופסה עם המפתח הנועל (e- מספר ההצפנה). אני שם פתק עם מספר האשראי שלי בקופסה, נועל אותה ושולח לבנק. הבנק הוא היחיד שיכול לפתוח את הקופסה כי רק ברשותו יש את המפתח הפותח. כלומר א' וכל העולם יכולים להצפין, אבל רק ב יכול לפענח.
ב. איך מממשים מפתחות חד כיווניים כאלו במתמטיקה? בוחרים פונקציה פשוטה שהיפוכה קשה מאוד. דוגמה פשוטה ולא מקרית היא העלאה בחזקה מודולו. נניח שמספר האשראי שלי הוא 7. אני מעלה אותו בחזקת E=3 (מעין מספר ההצפנה) מודולו N=31 , התוצאה היא 2. כעת אני יכול למסור לך את התוצאה (2), את מספר ההצפנה (3) ואת המפתח הציבורי (31) ועדיין יהיה לך קשה לשחזר את ה-7 המקורי.
ג. למזלך יהיה קשה, אך לא בלתי אפשרי (אתה צריך רק לבדוק הרבה פחות מ-31 אפשרויות). RSA השתמשו במשפט פרמה-אוילר (הרחבה של משפט פרמה הקטן) כדי להציע מפתחות חד כיווניים קצת יותר בטוחים. המשפט מבטיח ש-mod(X^(ed),N)=X כאשר ed=(p-1)*(q-1)+1, N=p*q ו-p,q ראשוניים. כעת הבנק בוחר p,q גדולים ובעזרתם מחשב ומפרסם את המפתח הציבורי N, את מספר ההצפנה e ומשאיר לעצמו את d בתור המפתח המפענח. אני מעלה את המספר שלי בחזקת e מוד N ושולח את הצופן לבנק. הבנק רק צריך להעלות את הצופן בחזקת d כדי לחשוף את הקוד המקורי.
ד. כפי שאמרת, הסודיות של ההצפנה נסמכת על הקושי שבפירוק N ל-p*q ראשוניים. לו היה זה קל, כל האקר היה יכול לשחזר את התהליך. למזלם של המשתמשים אין אלגוריתם מהיר מספיק כדי לעשות זאת עבור ראשוניים גדולים מספיק. אם הבנתי נכון את דה-סוטוי הרי שהאפסים של פונקציית רימאן קשורים איכשהו לחישוב - (pi(N - מספר המספרים הראשוניים הקטנים מ-N, כך שהקשר בין השערת רימאן לפרוק לגורמים ראשוניים נראה לי רחוק מאוד.
|
 |
RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש