כאמור אלגוריתם הצפנה א-סימטרי נפוץ הוא RSA.
אלגוריתם זה רשום כפטנט עולמי ומשמש כיום כאחד האלגוריתמים החשובים ביותר והחזקים ביותר. ניתן למצוא אותו בFIREWALLS, בפרוטוקולי תקשורת שונים וכמובן במרבית תוכנות ההצפנה למיניהן. את האלגוריתם פיתחו שלושה אנשים וביניהם ישראלי – עדי שמיר. אלגוריתם זה משמש בסיס למרבית האלגוריתמים האסימטריים. נכיר כיצד פועל אלגוריתם זה :
בשלב הראשון נמצא שני מספרים ראשוניים גדולים ומוצאים את מכפלתם. (בדוגמא זו נשתמש במספרים ראשוניים קטנים בכדי להקל על הבנת הצעדים).
למשל: P = 7, Q = 19 , N = P*Q = 133
אח"כ, נכניס למשתנה M את המכפלה M=(P-1)*(Q-1). במקרה שלנו, M = 108.
כעת, נמצא את המפתח הציבורי e, ע"י כך שנמצא את המספר הראשון שלו ול- M אין אף גורם משותף.
למשל עבור M = 108, e = 2,3,4 לא מתאימים אבל e = 5 מתאים.
כדי לייצר מפתח פרטי, נמצא את d כך שבנוסחה הבאה ייתן מספר שלם כאשר נציב ב- N מספר שלם
d = (1 + N*M)/ e.
למשל, עבור המקרה שבו אנו עוסקים:
אם N = 0 אז d = 1/5 ולכן N = 0 לא מתאים. אם N = 1 אז d= 109/5 ולכן N = 1 לא מתאים. אם N = 2 אז d = 217/5 ולכן N = 2 לא מתאים. אם N = 3 אז d = 325/5 = 65 ולכן N = 3 מתאים ו d = 65.
כך ייצרנו שני מפתחות: מפתח ציבורי = <133, 5> ומפתח פרטי = <133,65>. מפתחות אלה מתאימים רק למי שייצר אותם ואת שאר הפרמטרים יש כמובן להשמיד כדי שלא יהיה ניתן להתחקות אחרי תהליך יצירת המפתחות.
כדי להצפין נשתמש בנוסחה: C = msg^e mod N .
כדי לפענח נשתמש בנוסחה: msg = C^d mod N .
כלומר המפתח הציבורי המשמש להצפנה הוא : <N,e>
והמפתח הפרטי המשמש לפענוח הוא : <d,N>
כיצד מצפינים בעזרת RSA?
נניח שהמפתחות הפרטיים והציבוריים הם כפי שחישבנו למעלה.
אריק מעוניין להעביר את המספר 6 לבנץ. עליו לחפש את המפתח הציבורי של בנץ בין המפתחות הציבוריים ולהצפין ע"פ הנוסחה.
כך ההודעה המוצפנת תהיה : Encrypted(msg) = msg^e mod N =
6^5 mod 133 =
7776 mod 133 = 62
כלומר הערך 6 הוצפן ל- 62.
כעת נניח שבנץ קיבל את הערך 62 וברצונו לפענח אותו. עליו לקחת את המפתח הסודי שלו, אותו הוא זוכר בע"פ ולפענח ע"פ הנוסחה.
כך פענוח ההודעה יתבצע: Decrypted(msg) = msg^d mod N =
62^65 mod 133
כעת יכול בנץ להעלות 62 בחזקת 65 אבל זהו מספר גדול מאוד וקשה לפירוק, לכן ניתן להתחמק מביצוע דבר בדרך זו:
ניתן להעלות בחזקה בשלבים ולחשב את ה Mod בכל שלב:
62 ^ 65 mod 133 = 62 * (62 ^ 64) mod 133 = 62 * (3844 ^ 32) mod 133 = 62 * (120 ^ 32) mod 133 = 62 * ((120^2)^16) mod 133 = 62* (14400^16) mod 133 = 62 * (36 ^ 16) mod 133
62 * (99 ^ 8) mod 133 62 * (1296 ^ 8) mod 133 = =
= 62 * ((99^2) ^ 4) mod 133= 62 * (9801 ^ 4) mod 133 62 * (92 ^ 4) mod 133 =62 * ((92 ^ 2) ^ 2) mod 133 =
62 * (85 ^ 2) mod 133 62 * (8464 ^ 2) mod 133 ==
62 * 43 mod 133 =2666 mod 133 = 6 =