 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
?איך זה עובד
הצפנת RSA מבוססת על
המשפטים הבאים:
1
משפט פרמה הקטן: אם p הוא מספר
ראשוני, ו-a הוא טבעי, כך ש (a,p)=1 אז ap-1= 1(mod p).
הוכחה:
נניח שהמספרים (a x 1),
(a x 2), … ,(a x (p-1)) הם כולם מודולו p ושונים. אם חלק מהם היו שווים, למשל
am=an(mod p) אז a(m-n)=0(mod
p), כך ש m-n חייב להיות
כפולה של p. אבל מאחר ש כל m ו-n קטנים מ-p, אזי m=n.
לכן, a x 1, a x 2, … , a x (p-1) חייבים להיות סידור מחדש של 1,2, … ,
(p-1). אז מודולו p אנחנו מקבלים
(כאשר i רץ מ-1 עד p-1) Pi=Pai= ap-1Pi, לכן
ap-1=1(mod p).
2 משפט פרמה המורחב: אם (a,m)=1 אז af(m)=1(mod m), כאשר f(m) הוא מספר
הטבעיים שקטנים m, וראשוניים ביחס אל m.
הוכחה:
אותו
רעיון כמו בהוכחה הקודמת. נניח ש f(m)=n. כעת נניח שה-n מספרים שקטנים מ-m שראשוניים
ביחס ל-m הם: a1,a2,a3, … , an. אז a
x a1, a x a2, … , a x an הם גם ראשוניים ביחס ל-m, וכולם חייבים להיות
שונים, כך שהם חייבים להיות סידור מחדש של a1,a2,a3, … , an, לכן (כאשר i רץ מ-1 עד n) Pai=Pa x ai= anPai מודולו m כך ש an=1(mod m).
3 משפט השאריות הסיני: יהי p ו-q שני מספרים
(לא בהכרח ראשוניים) כך ש (p,q)=1. אזי אם a=b(mod p) וגם a=b(mod q) מקבלים ש
a=b(mod pq).
הוכחה: אם a=b(mod p) אזי p מחלק את
(a-b). באופן דומה, q מחלק את
(a-b). אבל p ו-q ראשוניים
ביחס אחד לשני, לכן pq מחלק את (a-b). כתוצאה מכך, a=b(mod pq).
בהינתן שלוש התיאוריות הללו, זאת הסיבה
שהצפנת RSA עובדת כראוי.
יהי M ההודעה הסודית,
ויהיו p ו-q שני מספרים שונים (גדולים) ראשוניים. יהי d מספר (קטן
יחסית) שהוא ראשוני ביחס ל (p-1)(q-1), ויהי e מספר כך ש de=1(mod (p-1)(q-1)). נניח ש N=pq. ההודעה
המקודדת היא C=Md(mod N). אנחנו צריכים
להראות שההודעה המפוצחת נתונה ע"י M=Ce(mod N).
הוכחה:
מאחר ש de=1(mod (p-1)(q-1)), de=1+k(p-1)(q-1). לכן
Ce=Mde=M1+k(p-1)(q-1) = M(Mp-1)k(q-1), אבל Mp-1=1(mod p), כך ש
Mde=M(mod p). מאותה סיבה,
Mde=M(mod q). לכן ע"פ
משפט השאריות הסיני, Mde=M(mod pq).
לבסוף, בהינתן d, כדי למצוא את e כך שיקיים de=1(mod(p-1)(q-1)), אנחנו יכולים להשתמש במשפט פרמה המורחב, כדי להגיע ל df((p-1)(q-1))=1(mod (p-1)(q-1)), כך ש df((p-1)(q-1))-1 (mod (p-1)(q-1)) הוא הערך המתאים עבור e.
