בתשובה לשוקי שמאל, 22/12/06 16:15
לגבי הציטוט של הארדי 425798
גדי אלכסנדרוביץ' • בתשובה לשוקי שמאל יום ו', 22/12/2006, 18:43
תוכל להפנות למקום בספר שבו מדובר על RSA, ואולי להרחיב קצת כאן? אני לא מבין בנושא כלום, אבל כדי לפצח את RSA צריך בעיקר לדעת איך לבצע פירוק מהיר לגורמים. למצוא ראשוניים גדולים צריך כל מי שרוצה להצפין עם RSA, אבל אלגוריתם מהיר בשביל זה קיים כבר כיום, מבלי שיהיה צורך בנכונות השערת רימן.
לגבי הציטוט של הארדי 425875
שוקי שמאל • בתשובה לגדי אלכסנדרוביץ' שבת, 23/12/2006, 16:03
בפרק העשירי: פיצוח מספרים וצפנים. כפי שכתב טל דיון 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, כך שהקשר בין השערת רימאן לפרוק לגורמים ראשוניים נראה לי רחוק מאוד.
לגבי הציטוט של הארדי 425881
גדי אלכסנדרוביץ' • בתשובה לשוקי שמאל שבת, 23/12/2006, 16:35
תודה על השיעור המעניין, אבל אני כבר מכיר את החומר הזה (מספרו הנחמד של סינג וממקורות אחרים). התהיה שלי הייתה על הקשר של השערת רימן לכל זה - קשר שככל הידוע לי (וכאמור, אני לא מבין בזה כלום) אינו קיים. אני אעיף מבט בספר של דה-סוטוי בהזדמנות הקרובה ואראה איך הוא מציג את זה (מכיוון שהוא מתמטיקאי, אני מניח שהוא לא יגיד דברים לא נכונים).

אגב, שים לב שהבעיה של "היפוך העלאה בחזקה מודולו" זה לא בדיוק מה ש-RSA משתמשים בו. הבעיה הזו נקראת "לוגריתם דיסקרטי", וגם היא בפני עצמה משמשת כבסיס למספר שיטות הצפנה ציבוריות. הפואנטה של RSA היא שקשה לחשב את d אם ידועים רק e ו-N. את d קל מאוד לחשב מתוך e אם ידוע מה שמכונה "פונקצית אוילר" של N, אבל הבעיה היא שהדרך הקלה ביותר שמכירים למציאת הערך שלה ב-N הוא על ידי פירוק N לגורמים (השאלה המעניינת היא האם יכולה להיות בתיאוריה דרך קלה יותר - עד כמה שידוע לי, אין תשובה כיום לשאלה הזו).
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות