בחלק הקודם, הוסבר מה הכוונה כשאומרים קידוד דלת צונחת, אבל איך יוצרים קידוד כזה? קידוד אחד פופולארי מהצורה הזו נקרא הצפנת RSA, כאשר RSA משמעו Rivest, Shamir and Adleman. זה מבוסס על הרעיון הבא:

זה מאוד פשוט להכפיל מספרים, בייחוד עם מחשבים. אבל זה יכול להיות מאוד קשה למצוא גורמים של מספרים. לדוגמא, אם אני אבקש ממישהו להכפיל את 34537 ב99991, זאת לא בעיה למצוא את התשובה בעזרת מחשבון, 3453389167. אבל הבעיה ההפוכה הרבה יותר קשה! נניח שאני נותן למישהו את המספר 1459160519. אני אפילו אומר לו, שקבלתי את המספר ע"י הכפלת שני מספרים שלמים. האם הוא יוכל להגיד לי מה הם המספרים? זו בעיה קשה מאוד. מחשב מסוגל למצוא גורמים של מספרים יחסית במהירות, אבל (למרות קיומם של מספר טריקים) הוא עושה זאת ע"י ניסיון של כל הצירופים האפשריים. המחשב צריך לבדוק עד השורש הריבועי של המספר הנתון, שבמקרה הזה הוא יותר מ38000. כעת, זה לא לוקח למחשב יותר מדי זמן לנסות 38000 אפשרויות. אבל, מה קורה אם למספר הנדון אין 10 ספרות, אלא 400 ספרות? השורש הריבועי של מספר בעל 400 ספרות, הוא מספר בעל 200 ספרות. משך החיים של היקום הוא בערך 10 בחזקת 18. מספר בעל 19 ספרות. בהנחה שמחשב מסוגל לבדוק מיליון גורמים בשניה, במשך החיים של היקום, הוא יכול לבדוק 10 בחזקת 24 אפשרויות. אבל עבור מכפלה בעלת 400 ספרות, יש 10 בחזקת 200 אפשרויות. המשמעות היא שמחשב יצטרך לעבוד 10 בחזקת 176 פעמים של משך החיים של היקום, כדי למצוא את הגורמים של המספר הגדול הזה.

אך זה לא קשה מדי לבדוק האם מספר הוא ראשוני, במלים אחרות, האם הוא לא ניתן לפירוק לגורמים. אם הוא לא ראשוני, זה קשה למצוא את הגורמים שלו, אבל אם הוא ראשוני, זה לא קשה להראות את זה.

אז הצפנת RSA עובדת ככה. נמצא שני מספרים ראשונים גדולים, p ו-q, שיש להם 100 או 200 ספרות כל אחד. נשמור על שני המספרים הללו בסודיות (הם המפתח הפרטי שלנו), נכפול אותם כדי לקבל N=pq. המספר הזה הוא באופן בסיסי המפתח הציבורי שלנו. זה יחסית קל לקבל את N, צריך רק לכפול את שני המספרים שלנו. אבל אם מישהו יודע על N, זה בעצם בלתי אפשרי מבחינתו למצוא את p ו-q. כדי למצוא אותם צריך לפרק לגורמים את N, וזאת נראית משימה מאוד מאוד קשה.

אבל, איך בדיוק N משמש לקידוד הודעה, ואיך p ו-q משמשים כדי לפצח אותה? בהמשך מוצגת דוגמא מלאה, אבל אני אשתמש במספרים ראשונים קטנים, כדי שיהיה קל לעקוב אחרי החישוב. במערכת הצפנת RSA אמיתית, צריך לזכור שהמספרים פשוט עצומים.

בדוגמא, נניח שאדם A רוצה ליצור מפתח ציבורי, ואדם B רוצה להשתמש במפתח הזה כדי לשלוח ל-A הודעה. אנחנו נניח שההודעה ש-A שולח ל-B היא סתם מספר. נניח גם ש-A ו-B הסכימו על שיטה לקודד טקסט למספרים. הנה הצעדים:

u אדם A בוחר שני מספרים ראשוניים, p=23, q=41, לדוגמא הזאת. צריך לזכור שהמספרים האמיתיים ש-A צריך להשתמש חייבים להיות הרבה יותר גדולים.

v אדם A מכפיל את p ו-q כדי לקבל pq=21x43=943. 943 הוא המפתח הציבורי, שהוא נותן לאדם B (וגם לשאר העולם, אם הוא מבקש).

w אדם A גם בוחר מספר נוסף e, שחייב להיות ראשוני ביחס ל-(p-1)(q-1). במקרה זה 22x40=880. לכן e=7 הוא מצוין. e הוא גם חלק מהמפתח הציבורי, לכן A מדווח ל-B גם על הערך של e.

x כעת B יודע מספיק כדי לקודד הודעה ל-A. נניח, עבור דוגמא זו, שההודעה היא המספר M=35.

y B מחשב את הערך של M^e(mod N)=35⁷(mod 943).

z 35⁷=64339296875 ו- 64339296875(mod 943)=545. המספר 545 הוא הקידוד ש-B שולח ל-A.

{ כעת A רוצה לפצח את 545. כדי לעשות זאת, הוא צריך למצוא מספר d כך ש ed=1(mod(p-1)(q-1)), או במקרה זה, כך ש 7d=1(mod 880). פתרון אחד הוא d=503, מאחר ש 7x503=3521=4x880+1=1(mod 880).

| כדי למצוא את הפיצוח, A צריך לחשב C^d(mod N)=545⁵⁰³(mod 943). זה נראה כאילו זה הולך להיות חישוב נוראי, אבל צריך לשים לב ש 503=256+128+64+32+16+4+2+1 (זוהי רק הרחבה בינארית של 503). לכן זה אומר ש 545⁵⁰³=545^{256+128+64+32+16+4+2+1}=545²⁵⁶545¹²⁸…545¹.

אך, מאחר שרק אכפת לנו מהתוצאה מודולו 943, אפשר לחשב את כל החישובים החלקיים באותו מודולו, וע"י כך שנעלה בריבוע באופן חוזר את 545 בריבוע, אפשר להגיע אל כל המקדמים שהם חזקות של 2. לדוגמא: 545²(mod 943)=545. 545=297025(mod 943) = 923 ואז שוב בריבוע. 545⁴(mod 943)=(545²)²(mod 943)=923x923 = 851929(mod 943)=400 וכן הלאה. מקבלים את הטבלה הבאה:

545¹(mod 943)=545

545²(mod 943)=923

545⁴(mod 943)=400

545⁸(mod 943)=633

545¹⁶(mod 943)=857

545³²(mod 943)=795

545⁶⁴(mod 943)=215

545¹²⁸(mod 943)=18

545²⁵⁶(mod 943)=324

אז התוצאה שאנחנו רוצים היא:

545⁵⁰³(mode 943)=324x18x215x795x857x633x400x923x545(mod 943)=35. 

ע"י שימוש בחישוב המעיק (אבל פשוט עבור מחשב) הזה, A יכול לפצח את ההודעה של B, ולקבל את ההודעה המקורית, N=35.