אז השיטה ברורה. עכשיו רק נשאר להסביר למה היא עובדת.
אם כן, נניח שעבור 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, עבור כל המספרים האלו. אז מובטח לך שזה יהיה נכון גם עבור כל מכפלה שלהם.
|
RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש