בתשובה לשלגון סגול, 30/01/08 1:30
469578
גדי אלכסנדרוביץ' • בתשובה לשלגון סגול יום ד', 30/1/2008, 7:52
אני עדיין לא מבין. הבנתי את הרעיון הבסיסי, אבל לא למה זה עובד. אתה אומר "נצפין בדרך הרגילה" ו"נפענח בדרך הרגילה" - אבל איך אתה עושה את זה? כדי לבנות מפתחות הצפנה ופענוח שעובדים, אתה צריך לדעת את פונקצית אוילר של pq; כדי לדעת אותה, אתה צריך לדעת את p,q *ולדעת שהם ראשוניים*. אם הם לא ראשוניים, אנחנו באותו ברוך כמו כל מי שמנסה לפרוץ מבחוץ; החישוב של פונקצית אוילר של מספר קשה בדיוק כמו הפירוק שלו לגורמים.

אז מה שקורה (לדעתי; לא בדקתי אף פעם מימוש "אמיתי" של RSA) הוא שמחשבים את פונקצית אוילר פשוט בעזרת הנוסחה

(p-1)(q-1)

שנכונה רק עבור ראשוניים. אם אין לך ראשוניים, תקבל d שייתכן מאוד שלא יעבוד (עשיתי כמה ניסויים עצמיים בזה - מקבלים d שלפעמים עובד ולפעמים לא). אני לא רואה למה השיטה שאתה מציע פותרת את הבעיה הזו (כמובן שייתכן שהיא פותרת ואני פשוט מפספס את החשבון).
469582
שלגון סגול • בתשובה לגדי אלכסנדרוביץ' יום ד', 30/1/2008, 8:35
אז השיטה ברורה. עכשיו רק נשאר להסביר למה היא עובדת.

אם כן, נניח שעבור A מסוים אנחנו יודעים ש- A^(p-1)=1 מודולו p, וש- A^(q-1)=1 מודולו q. עכשיו, את מפתחות ההצפנה והפענוח d,e בונים כך שיתקיים de=1 מודולו (p-1)(q-1). אם ההודעה המקורית היתה A, ההודעה המפוענחת תהיה A^de. נבדוק מה קורה מודולו p ומודולו q בנפרד. מודולו p:

A^(de) = A^(k*(p-1)*(q-1)+1) = (A^(p-1))^(k*(q-1))*A = 1^(k*(q-1))*A = A

ואותו הדבר מודולו q. ממשפט השאריות הסיני(1) נובע שנקבל חזרה את A, ולכן הפענוח יצליח.

-----------------
(1) עכשיו שמתי לב שבעצם יש פה דרישה נוספת - ש- p ו- q יהיו זרים (כלומר, אם במקרה נפלנו בשניהם על מספרים פריקים, ואם במקרה שני המספרים הפריקים אינם זרים זה לזה - נדפקנו). אפשר פשוט לוודא שהם זרים (אלגוריתם GCD הוא פולינומיאלי בגודל הקלט). לחליפין, אפשר לפתור בדרך אחרת: במקום לבדוק ש- 2,3,5 וכו' עוברים את מבחן פרמה, תבדוק ש- a^de=a מודולו pq, עבור כל המספרים האלו. אז מובטח לך שזה יהיה נכון גם עבור כל מכפלה שלהם.
469613
גדי אלכסנדרוביץ' • בתשובה לשלגון סגול יום ד', 30/1/2008, 12:35
אחלה. עכשיו אני נוטה להסכים שמדובר בשיטה לא משהו, אבל שהיא עובדת.
469775
הפונז • בתשובה לשלגון סגול יום ה', 31/1/2008, 14:04
אני בטוח שאחרי השרשור הזה נחה דעתו והתבססה הבנתו של מוס גולמי :-)
469979
שלגון סגול • בתשובה להפונז יום ו', 1/2/2008, 14:54
לדעתי נחה הבנתו (היא לא התקדמה לשום מקום) והתבססה דעתו (על משתתפי הדיון).
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות