קריפטוגרפיה עם מפתח א-סימטרי

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

עד סוף השיעור נכסה:

• מהי קריפטוגרפיה עם מפתח א-סימטרי
• שימושים בקריפטוגרפיה עם מפתח א-סימטרי, כולל חילופי מפתחות וחתימות דיגיטליות
• אבטחת קריפטוגרפיה עם מפתח א-סימטרי באופן כללי
• פרטים נוספים על אלגוריתמים ואבטחת RSA,‏ DSA ועקומות אליפטיות
• דוגמאות קוד Python שמראות כיצד האלגוריתמים עובדים בפועל
• איומים על אלגוריתמים אלה מקומפיוטרים קלאסיים וקוונטיים כאחד

מבוא לקריפטוגרפיה עם מפתח א-סימטרי

כפי שלמדנו בשיעור הקודם, קריפטוגרפיה עם מפתח סימטרי מהירה ויעילה מאוד להגנת מידע, אך יש לה כמה מגבלות:

1. ככל שמספר הצדדים שרוצים להחליף מידע מאובטח גדל, מספר המפתחות הנדרשים גדל בצורה קומבינטורית. אין מנגנון לחלוקה מאובטחת של מפתחות אלה בין שולחים ומקבלים.
2. אין הוראה לאי-כפירה. כל צד יכול לפענח או להצפין הודעות ללא דרך להבטיח שהודעה התקבלה או מאיפה היא הגיעה

הפתרון לשתי בעיות אלה מסופק על-ידי קריפטוגרפיה עם מפתח א-סימטרי (AKC), הידועה גם בשם קריפטוגרפיה עם מפתח ציבורי (PKC), שמהווה אבן יסוד של האבטחה הדיגיטלית המודרנית.

קריפטוגרפיה עם מפתח א-סימטרי (AKC) כוללת שימוש בזוג מפתחות — אחד ציבורי ואחד פרטי. המפתחות הציבורי והפרטי מקושרים קריפטוגרפית ונוצרים בדרך כלל בו-זמנית כ-זוג מפתחות באמצעות אלגוריתם מתמטי מיוחד. המפתח הציבורי, כפי שמשמו ניכר, מיועד לחלוקה חופשית, בעוד שהמפתח הפרטי נשמר בסוד על-ידי הצד שיצר את זוג המפתחות. אבטחת תקשורת שמשתמשת בזוגות מפתחות א-סימטריים מובטחת כל עוד המפתח הפרטי נשאר סודי.

איור 1. הצפנה עם מפתח א-סימטרי

AKC מציעה מספר פונקציות שימושיות, כגון:

1. הצפנה ופענוח לאפשור סודיות בתקשורת.
2. חתימות דיגיטליות להבטחת אותנטיות, שלמות, ואי-כפירה.
3. חילופי מפתחות מאובטחים להקלת השימוש הבא בקריפטוסיסטמות סימטריות.

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

חילופי מפתחות עם קריפטוגרפיה א-סימטרית

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

חילופי מפתחות אינטראקטיביים

פרוטוקול חילופי מפתחות אינטראקטיבי מתייחס לשיטה שבה שני צדדים משתפים פעולה ליצירת מפתח סוד משותף דרך ערוץ תקשורת לא מאובטח. מפתח הסוד המשותף הזה יכול לשמש לאחר מכן למשימות הצפנה ופענוח סימטריות.

הפרוטוקול הידוע ביותר בקרב פרוטוקולים אלה הוא אלגוריתם Diffie-Hellman (DH), שתוכנן במיוחד לאפשר חילופי מפתחות. בפרוטוקול זה, כל צד מייצר זוג מפתחות (ציבורי ופרטי) ומשדר את המפתח הציבורי שלו. לאחר מכן כל צד משתמש במפתח הפרטי שלו ובמפתח הציבורי של הצד השני ליצירת מפתח סוד משותף. DH מנצל את עקרונות האריתמטיקה המודולרית כדי להבטיח שכל שני הצדדים מגיעים לאותו סוד משותף למרות שלכל צד יש גישה רק למפתח הציבורי של הצד השני.

קריפטוסיסטמות מודרניות המבוססות על קריפטוגרפיה עם עקומות אליפטיות (ECC) מרחיבות מושג זה עם חילופי מפתחות Diffie-Hellman עם עקומה אליפטית) (ECDH). ECDH פועל בצורה דומה ל-DH אך מנצל את תכונות העקומות האליפטיות, מה שמביא למערכת מאובטחת ויעילה יותר.

איור 2. פרוטוקול חילופי מפתחות

חילופי מפתחות לא-אינטראקטיביים

בניגוד לפרוטוקולי חילופי מפתחות כמו DH ו-ECDH, שהם אינטראקטיביים ודורשים תקשורת הלוך ושוב לקביעת המפתח הסימטרי, AKC מספקת גם דרכים לא-אינטראקטיביות לביסוס מפתח סוד משותף. בסכמות כאלה, צד אחד מייצר זוג מפתחות (ציבורי ופרטי) ומשתף את המפתח הציבורי עם הצד השני. הצד השני מייצר מפתח סימטרי אקראי, מצפין אותו עם המפתח הציבורי שקיבל, ושולח אותו חזרה לצד הראשון. הצד הראשון משתמש במפתח הפרטי שלו לפענוח ההודעה שהתקבלה, ובכך מקבל את המפתח הסימטרי המשותף. הסכמה הזו היא לא-אינטראקטיבית בכך שהמפתח הסימטרי נקבע על-ידי צד אחד ופשוט מועבר באופן מאובטח לצד השני בצורה מוצפנת.

שיקול חשוב בחילופי מפתחות לא-אינטראקטיביים קשור להפרש באורך בסיביות בין המפתח הסימטרי שהצדדים רוצים להחליף לבין גדלי ההודעות המומלצים ב-AKC. בדרך כלל, מפתחות סימטריים מודרניים הם בטווח של 128-256 סיביות, בעוד שקריפטוסיסטמות א-סימטריות כמו RSA עובדות עם גדלי הודעות של כ-1024-4096 סיביות. לכן, כאשר משתמשים ב-AKC להעברת מפתח סימטרי, יש לקודד אותו להודעה ארוכה יותר של 1024-4096 סיביות. ניתן להשיג זאת בשתי גישות:

• חילופי מפתחות מבוססי-ריפוד: בגישה זו, המפתח הסימטרי הקצר יותר (128-256 סיביות) נוצר תחילה, ולאחר מכן משתמשים בסכמת ריפוד הפיכה מוסכמת כמו OAEP להטמעתו בהודעה ארוכה יותר (1024-4096 סיביות). הודעה ארוכה זו מוצפנת באמצעות AKC ומשודרת כטקסט מוצפן. המקבל מפענח תחילה את הטקסט המוצפן ואז מסיר את הריפוד כדי לחלץ את המפתח הסימטרי הקצר יותר.

• מנגנוני אנקפסולציה של מפתחות (KEMs): עם חילופי מפתחות מבוססי-KEM, נוצרת תחילה הודעת טקסט פשוט אקראית וארוכה (1024-4096 סיביות), ממנה ניתן לחלץ מפתח סימטרי קצר יותר (128-256 סיביות) באמצעות פונקציית גזירת מפתח (KDF) מוסכמת. הטקסט הפשוט הארוך יותר מוצפן באמצעות AKC ומשודר למקבל כטקסט מוצפן. המקבל מפענח את הטקסט המוצפן באמצעות המפתח הפרטי שלו ואז משתמש ב-KDF לחילוץ המפתח הסימטרי הקצר יותר (128-256 סיביות). קריפטוסיסטמות פופולריות כמו RSA, עם היכולת שלהן להצפין נתונים ישירות, יכולות לשמש ליישום KEMs.

איור 3. מנגנון אנקפסולציה של מפתחות

חתימות דיגיטליות עם קריפטוגרפיה א-סימטרית

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

איור 4. חתימות דיגיטליות עם קריפטוגרפיה א-סימטרית

אלגוריתמים ייעודיים לחתימה דיגיטלית

כיום, תקן עיבוד המידע הפדרלי האמריקאי (FIPS) לחתימות דיגיטליות הוא סכמה ייעודית הנקראת פשוט אלגוריתם החתימה הדיגיטלית (DSA). בדומה מסוים לפרוטוקול Diffie-Hellman, ה-DSA משתמש בתכונות האלגבריות של חזקה מודולרית והיפוכים כפליים ליצירה ואימות חתימות.

אלגוריתם החתימה הדיגיטלית עם עקומה אליפטית (ECDSA) הוא גרסת ECC של DSA, שמספקת את אותה פונקציונליות אך עם מפתחות קצרים משמעותית. הדבר מביא ליעילות משופרת, מה שהופך אותו לבחירה פופולרית למערכות עם מגבלות משאבים.

גם DSA וגם ECDSA יומחשו בפירוט רב יותר בהמשך.

סכמות חתימה דיגיטלית באמצעות קריפטוסיסטמות כלליות

בנוסף לאלגוריתמים ייעודיים, חתימות דיגיטליות ניתן לייצר גם באמצעות קריפטוסיסטמות א-סימטריות כלליות, כגון RSA.

RSA, שיידון בפירוט בסעיף מאוחר יותר, מנצל גם הוא היפוכים כפליים מודולריים וחזקה מודולרית כפעולות בסיסיות אך משלב אותן ברצף שונה מ-DSA. ב-RSA, החותם בדרך כלל יוצר hash של ההודעה ואז מצפין את ה-hash עם המפתח הפרטי שלו, מה שיוצר את החתימה הדיגיטלית. כל צד יכול לאמת את החתימה הזו על-ידי פענוחה עם המפתח הציבורי של החותם והשוואתה עם ה-hash של ההודעה.

יישומים של קריפטוגרפיה א-סימטרית

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

1. תקשורת אינטרנטית: תקשורת מאובטחת דרך האינטרנט, כמו HTTPS, מסתמכת רבות על קריפטוגרפיה א-סימטרית. Transport Layer Security (TLS) וקודמו, Secure Sockets Layer (SSL), משתמשים בקריפטוגרפיה א-סימטרית במהלך תהליך לחיצת היד הראשונית לביסוס מפתח סימטרי, שמשמש לאחר מכן לשאר הפגישה התקשורתית.

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

3. הצפנת דואר אלקטרוני: פרוטוקולי הצפנת דואר אלקטרוני כמו PGP (Pretty Good Privacy) והחלופה הקוד-פתוח שלו GPG (GNU Privacy Guard) משתמשים בקריפטוגרפיה א-סימטרית להבטחה שרק הנמען המיועד יוכל לקרוא את תוכן המייל.

4. מעטפת מאובטחת (SSH): SSH הוא פרוטוקול להתחברות מרחוק מאובטחת ושירותי רשת מאובטחים אחרים ברשת לא מאובטחת. הוא משתמש בקריפטוגרפיה א-סימטרית לאימות השרת מול הלקוח, ובאופן אופציונלי, של הלקוח מול השרת.

5. VPN (רשת פרטית וירטואלית): הצפנה א-סימטרית משמשת לביסוס חיבורים מאובטחים ב-VPNs, להבטחת תקשורת מאובטחת ברשתות ציבוריות.

6. בלוקצ'יין ומטבעות קריפטוגרפיים: טכנולוגיות בלוקצ'יין, כולל Bitcoin ו-Ethereum, משתמשות בקריפטוגרפיה א-סימטרית. לדוגמה, בעלות על Bitcoin מוקמת דרך חתימות דיגיטליות המשתמשות בקריפטוגרפיה א-סימטרית.

7. רשויות אישורים: קריפטוגרפיה א-סימטרית משמשת רשויות אישורים (CAs) להנפקה ולחתימה על אישורים דיגיטליים, המשמשים בתקשורת TLS, חתימת קוד, הצפנת דואר אלקטרוני ועוד. אישור דיגיטלי קושר מפתח ציבורי לישות מסוימת (לדוגמה, אדם או שרת).

איור 5. הנפקה וחתימה על אישורים דיגיטליים באמצעות קריפטוגרפיה א-סימטרית

אבטחת קריפטוגרפיה א-סימטרית

מספר מושגים קריפטוגרפיים משתלבים כדי לאפשר קריפטוגרפיה א-סימטרית מאובטחת, כולל:

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

פונקציונליות פח המלכודת ב-AKC, פעולות ההצפנה והפענוח כוללות מפתחות משלימים שונים מזוג מפתח יחיד. טקסט מוצפן שנוצר על-ידי הצפנה באמצעות אחד המפתחות (לדוגמה המפתח הציבורי) חייב להיות בלתי-מובן לצדדים שלישיים בעוד שהוא בר-פענוח בקלות על-ידי מחזיק המפתח המשלים (במקרה זה המפתח הפרטי). במילים אחרות, ההצפנה צריכה לדמות פונקציה חד-כיוונית עם פח מלכודת כך שצדדים שלישיים לא יוכלו להפוך את הפעולה ולשחזר את הטקסט הפשוט, אך המפתח הפרטי מספק פח מלכודת סודי המאפשר היפוך קל. אלגוריתמי AKC פופולריים משתמשים בחזקה מודולרית כדי ליצור התנהגות של פונקציה חד-כיוונית עם פח מלכודת.

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

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

פרוטוקול	גדלי מפתח טיפוסיים (בסיביות)	יישום
RSA	1024 (מיושן), 2048, 3072, 4096	הצפנה, חתימות דיגיטליות
DSA	1024 (מיושן), 2048, 3072	חתימות דיגיטליות
DH	2048, 3072, 4096	חילופי מפתחות
ECDH	224, 256, 384, 521	חילופי מפתחות
ECDSA	224, 256, 384, 521	חתימות דיגיטליות

תשתית מפתחות ציבוריים: ב-AKC, המפתחות הפרטיים חייבים להישמר בסוד על-ידי הבעלים בעוד שהמפתחות הציבוריים משותפים. יש צורך במנגנון מאובטח לניהול והפצה של מפתחות ציבוריים אלה בין משתמשים. תשתית מפתחות ציבוריים (PKI) מספקת דרך לעשות זאת באמצעות אישורים דיגיטליים. אישור דיגיטלי מספק הוכחה לזהות הבעלים של המפתח הציבורי ומונפק על-ידי רשות מהימנה כמו רשות אישורים (שהיא חלק מ-PKI). לכן, PKI ממלאת תפקיד בלתי-נפרד באבטחת יישומים מודרניים המשתמשים ב-AKC על-ידי אפשור ניהול מפתחות בקנה מידה רחב (יצירה, ניהול, הפצה וביטול אישורים דיגיטליים).

סיכוני אבטחה לקריפטוגרפיה א-סימטרית

כפי שמפורט בטבלה לעיל, אלגוריתמי מפתח א-סימטרי מודרניים כמו RSA משתמשים בדרך כלל בגדלי מפתח גדולים בהרבה ממקביליהם הסימטריים הנפוצים כמו AES-128. אפילו הפרוטוקולים מבוססי-ECC (ECDH ו-ECDSA) שיש להם מפתחות קטנים יותר משתמשים לפחות ב-224 סיביות למפתחות. זה בתורו מרמז שמתקפת כוח גס הכוללת חיפוש ממצה של מרחב המפתחות הפרטיים לזיהוי המפתח הנכון אינה ישימה חישובית בעתיד הנראה לעין. זה נכון אפילו אם יופעלו קומפיוטרים קוונטיים למשימה זו. לכן, מתקפות נגד AKC מתמקדות בדרך כלל בניצול חולשות פוטנציאליות אחרות של קריפטוסיסטמות ספציפיות. כמה מצבי מתקפה מתועדים היטב מכוונים ל:

1. חולשה אלגוריתמית על-ידי שימוש באמצעים מתמטיים וחישוביים מתוחכמים לפגיעה בהנחות הקושי המשמשות לניסוח אלגוריתמי מפתח א-סימטרי. לדוגמה, האבטחה של RSA מבוססת על קושי פירוק מספרים ראשוניים גדולים, והתקדמות חישובית אחרונה אפשרה פירוק מוצלח של מפתחות RSA של 829 סיביות. לכן, RSA של 1024 סיביות מיושן כיום. כפי שיידון בהמשך, הסיכון העיקרי שמציבים קומפיוטרים קוונטיים ל-AKC נכלל גם בקטגוריה זו.

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

3. פגמי יישום כמו שגיאות ביישום אלגוריתמים קריפטוגרפיים שחושפים בטעות מידע על המפתחות. לדוגמה, ריפוד שגוי עלול לחשוף פרטים על מפתחות.

4. ערוצי צד המתייחסים לדליפת מידע מהמערכת הפיזית המבצעת את הקריפטוגרפיה. דליפות כאלה יכולות להיות בצורת מידע תזמון, צריכת חשמל, או אפילו קול, שניתן לנצל במתקפת ערוץ צד. לדוגמה, ניתוח משך הביצוע של פעולות קריפטוגרפיות עשוי לחשוף את מספר ה-'1'ים במפתח בינארי. דליפה לכאורה תמימה זו מצמצמת משמעותית את מרחב החיפוש, ומגלה פתרונות אפשריים לבעיות שנראו בתחילה כבלתי-אפשריות.

5. חילופי מפתחות על-ידי יירוט מפתחות בזמן חילופם, כמו במתקפת אדם-באמצע (MITM). פרוטוקול DH רגיש למתקפות MITM אם לא משולבים שלבי אימות נוספים.

6. אחסון מפתחות שמטרתו לגנוב מפתחות מאחסון לא מאובטח דיו. זה כולל מתקפות פיזיות כמו מניפולציה או גניבה של אמצעי אחסון.

אבטחת קריפטוסיסטמות א-סימטריות מפני מגוון המתקפות האפשריות היא לכן משימה משמעותית הכוללת שיקולים מתמטיים, חומרתיים, תוכנתיים, לוגיסטיים ומשפטיים.

RSA

אלגוריתם RSA (Rivest-Shamir-Adleman) הוא אחת מהקריפטוסיסטמות הראשונות עם מפתח ציבורי ומשמשת באופן נרחב להעברת נתונים מאובטחת. מדובר בקריפטוסיסטמה מגוונת שמספקת את הפעולות הנחוצות לאפשור הצפנה, פענוח, חתימות דיגיטליות וחילופי מפתחות במסגרת משותפת.

בסעיף זה, נמחיש קריפטוגרפיה א-סימטרית (AKC) באמצעות RSA דרך דוגמאות פשוטות.

נשתמש בתרחיש הסטנדרטי של שני צדדים, אליס ובוב, שרוצים לתקשר באופן מאובטח באמצעות AKC.

אלגוריתם RSA

אלגוריתם RSA הבסיסי כולל ארבע פעולות: ייצור מפתח, הפצת מפתח, הצפנה ופענוח:

1. ייצור מפתח:

   מפתחות ציבוריים ופרטיים נוצרים על בסיס עקרונות מתמטיים סביב מספרים ראשוניים, שחישובם קל אך ההפך קשה.

   נתייחס לאלה:

   • מפתח ציבורי: $(e, n)$
   • מפתח פרטי: $(d, n)$

   שים לב ש-$n$ משותף למפתח הציבורי ולמפתח הפרטי, ומכונה המודולוס. נצטרך להשתמש בזה בהמשך.

Mathematical detail

• בחר שני מספרים ראשוניים שונים, $p$ ו-$q$.
  • נבחרים באקראי (מטעמי אבטחה).
  • הם צריכים להיות דומים בסדר גודל, אך להשתנות באורך בכמה ספרות, כדי להקשות על פירוק.
  • מספרים ראשוניים ניתן לבחור ביעילות באמצעות בדיקת ראשוניות.
• חשב $n = p*q$.
  • $n$ הוא המודולוס עבור שני המפתחות הציבורי והפרטי.
• חשב את הטוטיינט $φ$ $(n) = (p-1)*(q-1)$.
  • הטוטיינט מיועד להישמר בסוד ובדרך כלל נמחק לאחר ייצור המפתח.
• בחר מספר שלם $e$ כך ש-$1 < e <$ $φ$ $(n)$ ו$gcd$$(e,$$φ$$(n)) = 1$.
  • כלומר, $e$ ו$φ$$(n)$ צריכים להיות קופריים.
  • המספר $e$ זה מהווה את המעריך של המפתח הציבורי ובדרך כלל נבחר כמספר קטן ליעילות חישובית.
  • המספר הראשוני $65537 = 2^{16} + 1$ משמש לעתים קרובות.
  • חשב $d$ כדי לספק את יחס הקונגרואנס $d*e ≡ 1 ($$mod$$φ$$(n))$.
    • כלומר, $d$ הוא ההיפוך הכפלי של $e$ מודולו $φ$$(n)$.
    • חישוב זה יעיל יותר באמצעות אלגוריתם אויילר המורחב.
    • המספר $d$ זה הוא המעריך של המפתח הפרטי.
• המפתח הציבורי מורכב מ-$(e, n)$, והמפתח הפרטי הוא $(d, n)$.

2. הפצת מפתח:

   • המפתח הציבורי $(e, n)$ מפורסם לאלה שעשויים לרצות לשלוח הודעה
   • המפתח הפרטי $(d, n)$ נשמר בסוד.

3. הצפנה:

   • אליס רוצה לשלוח הודעה $M$ לבוב. במקרה זה מספר שלם פשוט
   • אליס משתמשת במפתח הציבורי של בוב $(e, n)$ להצפנת ההודעה לטקסט מוצפן $C$
   Mathematical detail

   • $M$ הוא מספר שלם $0 ≤ M < n$.
   • $C ≡ M^e (mod n)$, כאשר $C$ הוא הטקסט המוצפן.

4. פענוח:

   • בוב מקבל את הטקסט המוצפן $C$
   • בוב משתמש במפתח הפרטי שלו $(d, n)$ לפענוח ההודעה חזרה להודעה $M$
   Mathematical detail

   • $M ≡ C^d (mod n)$.

זה קו המתאר הבסיסי של RSA. בפועל, סכמות ריפוד מתוחכמות יותר מוחלות על הטקסט הפשוט $M$ לפני ההצפנה כדי להבטיח שטקסטים פשוטים שווים מביאים לטקסטים מוצפנים שונים. זה מונע מגוון של מתקפות אפשריות נגד יישומים נאיביים של RSA ומאפשר אבטחה סמנטית.

המחשת RSA ב-Python

בתאי הקוד הבאים, נמחיש דוגמה פשוטה של אלגוריתם RSA באמצעות מספרים שלמים קטנים ואחר כך נדגים יישומים מעשיים של הפצת מפתחות וחתימות דיגיטליות באמצעות ספריות Python המיישמות RSA.

הערה

הערה: בסעיף זה נציג את חישובי המתמטיקה בפירוט כחלק מקוד ה-Python

ייצור מפתח RSA

בוא נעבור שלב-אחר-שלב על מופע פשוט של אלגוריתם RSA עם מספרים ראשוניים קטנים.

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

נסביר דרך פשוטה אחת לחישוב זה, אך הרבה יותר יעיל עם מספרים שלמים גדולים יותר להשתמש בפונקציה math.gcd של Python.

# Added by doQumentation — required packages for this notebook
!pip install -q cryptography

import math

# Example function to compute the gcd (greatest common divisor)
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

# let's calculate some examples using algorithm
n1 = gcd(50, 10)
n2 = gcd(99, 33)
n3 = gcd(59, 9)

# do the same with the python library call

m1 = math.gcd(50, 10)
m2 = math.gcd(99, 33)
m3 = math.gcd(59, 9)

# Confirm they are the same
assert n1 == m1
assert n2 == m2
assert n3 == m3

# They are - print out the values for explanation
print("gcd(50,10) =", m1)
print("gcd(99,33) =", m2)
print("gcd(59,9) =", m3)

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

# Choosing two prime numbers and keep them secret
p = 13
q = 19
print("The secret prime numbers p and q are:", p, q)

לאחר מכן, המודולוס $n$, שהוא פשוט המכפלה של שני הראשוניים שנבחרו, מחושב. מודולוס זה יפורסם כחלק מהמפתח הציבורי.

# Calculate n which is the modulus for both the public and private keys
n = p * q
print("modulus n (p*q)=", n)

פונקציית הטוטיינט של אויילר $\varphi(n)$ מחושבת לאחר מכן, שכן היא נדרשת לפעולת ההיפוך הכפלי המודולרי המשמשת לקביעת המפתחות ב-RSA. $phi$ גם נשמר בסוד ובדרך כלל נמחק לאחר ייצור המפתח.

# Compute Euler's totient function, φ(n) and keep it secret
phi = (p - 1) * (q - 1)
print("The secret Euler's function (totient) [phi(n)]:", phi)

אנחנו מוכנים כעת לחשב את המפתחות הציבוריים והפרטיים. ב-RSA, כל אחד מהם מצוין על-ידי טאפל של שני מספרים שלמים. הערך הראשון בכל טאפל הוא מספר שלם שונה, והערך השני הוא המודולוס $n$ שמשותף לשני המפתחות.

הערך הראשון במפתח הציבורי יכול להיות כל מספר שלם גדול מ-1 שהוא קופרי ל-$phi$. שני מספרים שלמים הם קופריים אם המחלק המשותף המקסימלי שלהם הוא 1. לכן אנחנו משתמשים בפונקציה math.gcd כדי למצוא מספר שלם $e$ קופרי ל-$phi$.

# Choose an integer e such that e and φ(n) are coprime
e = 2
while e < phi:
    if math.gcd(e, phi) == 1:
        break
    else:
        e += 1
print("Public Key (e):", e)

המפתח הפרטי דורש מספר שלם $d$, שהוא ההיפוך הכפלי של $e$ מודולו $phi$; כלומר, הוא מספק את יחס הקונגרואנס $d*e\equiv 1 \pmod{\varphi(n)}$. להמחשה פשוטה זו שבה אנחנו עוסקים במספרים שלמים קטנים, אנחנו יכולים פשוט לעבור על המספרים השלמים החיוביים כדי לאתר $d$ מתאים. בהגדרות ריאליסטיות, אלגוריתם אויילר המורחב היעיל חישובית משמש למטרה זו.

# Compute a value for d such that (d * e) % φ(n) = 1
d = 1
while True:
    if (d * e) % phi == 1:
        break
    else:
        d += 1
print("Private Key (d):", d)

אנחנו יוצרים כעת את הטאפלים $(e, n), (d, n)$, שמהווים את המפתחות הציבורי והפרטי בהתאמה. המפתח הציבורי מפורסם לאחר מכן, בעוד שהמפתח הפרטי נשמר בסוד.

# Public and Private Key pair
public = (e, n)
private = (d, n)

print(f"The Public key is {public} and Private Key is {private}")

הצפנה ופענוח ב-RSA משתמשים בפעולת חזקה מודולרית. יתר על כן, המפתחות הציבורי והפרטי הם משלימים בכך שניתן להשתמש בכל אחד מהם להצפנת הודעה שהמפתח השני יוכל לפענח.

כאן אנחנו ממחישים את המקרה שבו המפתח הציבורי $(e,n)$ משמש להצפנה והמפתח הפרטי $(d, n)$ משמש לפענוח על-ידי הגדרת פונקציית Python לכל פעולה.

לאחר מכן אנחנו מצפינים ומפענחים הודעת מספר שלם $msg$.

# Encryption function
def encrypt(plain_text):
    return (plain_text**e) % n

# Decryption function
def decrypt(cipher_text):
    return (cipher_text**d) % n

# Simple message to encode
msg = 9

# encrypt then decrypt
enc_msg = encrypt(msg)
dec_msg = decrypt(enc_msg)

print("Original Message:", msg)
print("Encrypted Message:", enc_msg)
print("Decrypted Message:", dec_msg)

בעוד שהמספרים השלמים הקטנים שנעשה בהם שימוש לעיל שימושיים להתוות בקלות את הרעיונות המרכזיים באלגוריתם RSA, ביישומים אמיתיים RSA דורש שימוש במספרים שלמים גדולים מאוד. לדוגמה, RSA של 2048 סיביות כולל שימוש במודולוס $n$ שאורכו 2048 סיביות, שהמקבילים העשרוניים שלהם הם בסביבות 10$^616$. מספרים עצומים אלה נחוצים לאבטחה המעשית של RSA.

חילופי מפתח סימטרי עם RSA

כפי שנדון בעבר, AKC מאפשרת לשני צדדים שרוצים לתקשר לבסס באופן מאובטח סוד משותף, שניתן להשתמש בו, למשל, כמפתח הסוד להצפנה סימטרית של כמות גדולה של טקסט פשוט.

בוא נשקול את התרחיש הבא. אליס ובוב רוצים להשתמש ב-SKC כדי להצפין ולפענח הודעות. עם זאת, לפני שניתן לאתחל תהליך זה, עליהם להסכים על מפתח סוד משותף. אפשרות אחת היא שצד אחד — נאמר, אליס — תייצר מפתח סוד ואז תעביר אותו בצורה מאובטחת לבוב. כדי להשיג העברה מאובטחת זו, אליס מחליטה להשתמש ב-RSA כמנגנון אנקפסולציה של מפתח (KEM).

התהליך כולל את השלבים הבאים:

• ראשית, אליס מייצרת מפתח סימטרי אקראי, שאותו היא מתכוונת לשתף עם בוב.
• לאחר מכן, בוב מייצר זוג מפתחות א-סימטריים ומפרסם את המפתח הציבורי שלו בערוץ מתאים.
• לאחר מכן, אליס משתמשת במפתח הציבורי של בוב כדי להצפין את המפתח הסימטרי, ובכך לאנקפסל אותו בטקסט מוצפן.
• לאחר מכן, אליס משדרת את הטקסט המוצפן דרך ערוץ אמין אך לא בהכרח מאובטח.
• לבסוף, בוב מקבל את הטקסט המוצפן ומפענח אותו באמצעות המפתח הפרטי שלו. כעת יש לו גישה למפתח הסימטרי שנוצר על-ידי אליס.

איור 1. חילופי מפתח סימטרי עם RSA

דוגמה לחילופי מפתח מבוססי-ריפוד ב-Python

זרימת עבודה מעשית המשתמשת ב-RSA לחילופי מפתח לא-אינטראקטיבי מבוסס-ריפוד ממוחשת כעת באמצעות ספריית ה-Python cryptography.

ייבא מודולים נחוצים מספריית ה-Python cryptography. אם נדרש, ניתן להתקין ספרייה זו באמצעות הפקודה pip install cryptography.

לאחר מכן אליס מייצרת מפתח סוד אקראי, שאותה היא מתכוונת להעביר לבוב.

# pip install cryptography
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.fernet import Fernet
from cryptography.hazmat.primitives import hashes

symmetric_key = Fernet.generate_key()
print(f"\nSymmetric key generated by Alice: {symmetric_key}")

באמצעות מודול rsa מספריית cryptography, בוב מייצר זוג מפתחות ואז משדר את המפתח הציבורי שלו. כל אחד יכול ליירט את המפתח הציבורי ולקרוא את המספרים הציבוריים $(e,n)$ שמרכיבים אותו.

# Bob generates a 2048-bit RSA key pair
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()
print(f"Public key broadcast by Bob: {bob_public_key}")
print(f"\nPublic numbers in Bobs' public key: {bob_public_key.public_numbers()}")

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

# Encryption
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Ciphertext:", ciphertext)

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

# Bob decrypts ciphertext to access the symmetric key
decrypted_symmetric_key = bob_private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted key:", decrypted_symmetric_key)
assert decrypted_symmetric_key == symmetric_key

בשלב זה, לאליס ולבוב יש גישה למפתח הסימטרי הסודי, שבו הם יכולים להשתמש ליישומי SKC.

סימולציה של מנגנון עטיפת מפתח עם RSA בפייתון

בתהליך העבודה הבא, אנחנו ממחישים את השימוש ב-RSA לסימולציה של מנגנון עטיפת מפתח (KEM) שבו הודעה סודית אקראית ארוכה מספיק מוחלפת בצורה מאובטחת ולאחר מכן מומרת לסוד משותף באורך המתאים באמצעות KDF.

שוב, אליס ובוב רוצים לבסס סוד משותף ללא אינטראקציה, ואליס היא הצד שמחליט איזה סוד להשתמש בו.

נתחיל בייבוא כמה ספריות פייתון נדרשות.

בוב מייצר אז את זוג מפתחות ה-RSA שלו ומשדר את המפתח הציבורי שלו.

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes
from os import urandom

# Bob's RSA key pair
private_key_Bob = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_key_Bob = private_key_Bob.public_key()

print("Bob's private and public keys created")

אליס מייצרת תחילה סוד אקראי ארוך שממנו יגזר הסוד המשותף בסופו של דבר. ב-KEM טהור, הסוד הארוך יהיה אלמנט אקראי מהמבנה האלגברי שעומד בבסיס מערכת ההצפנה. במקרה של RSA 2048 סיביות, זה יהיה מספר שלם אקראי מודולו המודולוס של RSA 2048 סיביות. כך KEM טהור לא דורש ריפוד נוסף, אבל בדוגמה זו אנחנו רק מסמלצים KEM באמצעות RSA, וספריית cryptography דורשת שימוש בריפוד בעת הצפנה עם RSA. לכן נשתמש בסוד ארוך קצת יותר קצר, שעדיין ארוך בהרבה ממפתח AES סטנדרטי של 256 סיביות.

Alice_long_secret = urandom(160)  # A 160 byte or 1280 bit random message
print("Alice's secret created")

לאחר מכן אליס מצפינה את הסוד הארוך באמצעות המפתח הציבורי של בוב, והסוד המוצפן מועבר לבוב.

Alice_encrypted_secret = public_key_Bob.encrypt(
    Alice_long_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)
print("Alice's secret encrypted")

בוב מפענח את הסוד המוצפן שקיבל מאליס באמצעות המפתח הפרטי שלו.

Bob_decrypted_secret = private_key_Bob.decrypt(
    Alice_encrypted_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

assert Alice_long_secret == Bob_decrypted_secret, "Secrets do not match!"

# if we get here they match
print("Secrets match")

לבסוף, גם אליס וגם בוב מיישמים בנפרד פונקציית גזירת מפתח (KDF) מוסכמת על הסוד הארוך כדי לגזור את המפתח הסימטרי.

שים לב שהתהליך כולל פרוטוקול גיבוב ושימוש במלח אקראי שמבטיח ייחודיות ובלתי-צפיות של המפתח הסימטרי המשותף במקרה שהסוד הארוך ישמש שוב (לא מומלץ). אולם המלח עצמו לא חייב להיות סודי, וברגע שנוצר אקראית, נניח על ידי אליס בדוגמה זו, ניתן לשדר אותו לבוב לצד הסוד הארוך המוצפן.

לכן נניח שלאליס ולבוב יש גישה לאותו מלח אקראי.

def key_derivation_function(secret, salt):
    hkdf = HKDF(
        algorithm=hashes.SHA256(),
        length=32,  # Desired key length
        salt=salt,
        info=None,
        backend=None,
    )
    return hkdf.derive(secret)

common_salt = urandom(16)  # Random salt accessible to both Alice and Bob

symmetric_key_Alice = key_derivation_function(Alice_long_secret, common_salt)
symmetric_key_Bob = key_derivation_function(Bob_decrypted_secret, common_salt)

assert symmetric_key_Alice == symmetric_key_Bob, "Derived keys do not match!"
print(
    f"A symmetric key of length {len(symmetric_key_Alice)*8} bits was successfully derived by both Alice and Bob!"
)

חתימות דיגיטליות עם RSA

כעת נרחיב את תרחיש התקשורת הסודית שלמעלה עם אליס ובוב לתרחיש שכולל גם אימות בעזרת חתימה דיגיטלית.

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

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

נבחן את ההגדרה הכללית הזו, הכוללת את השלבים הבאים:

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

איור 2. חתימות דיגיטליות עם RSA

תהליך העבודה של חתימה דיגיטלית זה ממוחש בהמשך.

שוב נייבא כמה מודולים שימושיים מספריית cryptography. כמקודם, אליס מתכוונת לשלוח בסודיות מפתח סימטרי לבוב, אבל היא גם רוצה לחתום עליו דיגיטלית. במקרה זה, אנחנו צריכים מפתחות ציבוריים גם לאליס וגם לבוב. לכן, הצעד הראשון הוא שגם אליס וגם בוב יצרו זוג מפתחות משלהם באמצעות RSA וישדרו את המפתח הציבורי שלהם לעולם.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import padding, rsa
from cryptography.hazmat.primitives.asymmetric.utils import Prehashed

# Generate keys for Bob
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()

# Generate keys for Alice
alice_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
alice_public_key = alice_private_key.public_key()

print("Private and Public keys generated for Bob and Alice.")

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

# Alice encrypts the message using Bob's public key
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("ciphertext of symmetric key: ", ciphertext)

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

1. יצירת גיבוב של הטקסט המוצפן באמצעות אלגוריתם גיבוב.
2. הצפנת הגיבוב באמצעות המפתח הפרטי של אליס, שמהווה חתימה.

# Alice signs the ciphertext using her private key
digest = hashes.Hash(hashes.SHA256())
digest.update(ciphertext)
hash_to_sign = digest.finalize()

signature = alice_private_key.sign(
    hash_to_sign,
    padding.PSS(mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH),
    Prehashed(hashes.SHA256()),
)

print("signature: ", signature)

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

# Bob receives the ciphertext and signature
received_ciphertext = ciphertext
received_signature = signature

# Send signature and ciphertext here
print("Sending ciphertext and signature.....")

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

# Bob creates a hash of the ciphertext using the same algorithm used by Alice
digest = hashes.Hash(hashes.SHA256())
digest.update(received_ciphertext)
hash_to_verify = digest.finalize()

print("hash to verify: ", hash_to_verify)

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

בקוד הפייתון שלהלן, פעולות אלה משולבות לפונקציית שירות שימושית הנקראת verify שמסופקת על ידי אובייקט המשויך למפתח הציבורי של אליס.

from cryptography.exceptions import InvalidSignature

def is_signature_valid(public_key, signature, data_hash):
    try:
        public_key.verify(
            signature,
            data_hash,
            padding.PSS(
                mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH
            ),
            Prehashed(hashes.SHA256()),
        )
        return True
    except InvalidSignature:
        return False

if is_signature_valid(alice_public_key, received_signature, hash_to_verify):
    print("The signature is valid.")
else:
    print("The signature is not valid.")

לאחר שאימת את השלמות והאותנטיות של הטקסט המוצפן שקיבל, בוב יכול לפענחו באמצעות המפתח הפרטי שלו מכיוון שאליס יצרה את הטקסט המוצפן באמצעות המפתח הציבורי של בוב.

# Bob decrypts the message using his private key
decrypted_message = bob_private_key.decrypt(
    received_ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted message:", decrypted_message.decode())

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

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

שבירת RSA

האבטחה והשימושיות של אלגוריתם RSA שתואר לעיל מבוססים על שתי הנחות מתמטיות:

1. מציאת ההופכי הכפלי המודולרי $d$ כאשר יש גישה רק ל-$(e, n)$ היא בלתי אפשרית חישובית.

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

ההתקפה הבולטת ביותר על אלגוריתם RSA שואפת לפגוע בהנחה 1 על ידי שחזור יעיל של מספר המפתח הפרטי $d$ דרך פירוק המודולוס $n$ לגורמים ראשוניים. כפי שיודגם להלן, קל לשחזר את $d$ אם יש גישה לגורמים הראשוניים $p$ ו-$q$ של $n$ או לטוטיינט $φ$$(n)$. נזכיר ש-$p$, $q$ ו-$φ$$(n)$ נשמרים בסוד במהלך יצירת המפתח ומושמדים לאחר מכן. צד שלישי המשחזר מידע זה באמצעות מחשב קלאסי או קוונטי בעצם חושף את המפתח הפרטי, ובכך שובר את RSA. לפיכך, פירוק לגורמים ראשוניים הוא הפרימיטיב החישובי המרכזי הנחוץ לשבירת RSA.

מחשוב קלאסי ו-RSA

פירוק מספרים שלמים גדולים לגורמים ראשוניים ידוע כבעל סקאלביליות על-פולינומיאלית או תת-אקספוננציאלית במחשבים קלאסיים. האלגוריתם הקלאסי הידוע ביותר לפירוק מספרים שלמים גדולים מ-$10^{100}$ לגורמים הוא מסננת שדה המספרים הכללית (GNFS)

Mathematical detail

$L_n[\frac{1}{3}, (\frac{64}{9})^{(\frac{1}{3})}] = e^{[((\frac{64}{9})^{(\frac{1}{3})} + o(1)) (log(n))^{\frac{1}{3}}(log(log(n))^{\frac{2}{3}})]}$

כפונקציה של המספר השלם $n$ שיש לפרק לגורמים.

סקאלביליות זו היא על-פולינומיאלית במספר הסיביות הנדרשות לייצוג $n$.

לכן, פירוק לגורמים ראשוניים נחשב ללא יעיל במחשבים קלאסיים.

כיום, המספרים השלמים הגדולים ביותר שפורקו לגורמים על חומרה קלאסית הם בטווח של 829 סיביות או 250 ספרות עשרוניות. בהינתן הצמיחה האקספוננציאלית בעוצמת המחשוב הקלאסי שנצפתה בעשורים האחרונים, RSA של 1024 סיביות כבר אינו נחשב מאובטח בטווח הקרוב ועבר הוצאה משימוש. ובכל זאת, בעתיד הנראה לעין, פירוק מספרים שלמים של 2048 סיביות שגודלם הוא בטווח של $10^{617}$ נחשב כיום בלתי אפשרי במערכות קלאסיות, מה שמצביע על כדאיות מתמשכת. עם זאת, הופעת המחשבים הקוונטיים מבטלת הערכה זו.

אלגוריתם הקוונטי של שור ו-RSA

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

האלגוריתם של שור יכול לפרק ראשוניים ב-$O(n^2)$ כאשר $n$ הוא מספר הסיביות.

Mathematical explanation of Shor's algorithm

בהקשר של RSA, האלגוריתם של שור פועל על ידי ניצול התקופתיות של פונקציית החזקה המודולרית $f(x) = a^x (mod~n)$ ומספק פרימיטיב קוונטי למציאת תקופה המאפשר פירוק יעיל של המודולוס $n$ לגורמים ראשוניים.

תיאור כללי ומפושט של השיטה הכוללת של שור לשבירת RSA הוא כדלקמן:

1. בהינתן המודולוס $n$, המפורסם כחלק מהמפתח הציבורי, בחר מספר $a$ ראשוני יחסי ל-$n$, כלומר $gcd(a,n) = 1$. מכיוון שאנחנו יודעים ש-$n = p*q$ יש לו בדיוק שני גורמים ראשוניים $(p, q)$, כמעט כל מספר קטן מ-$n$ שנבחר באקראי סביר שיהיה ראשוני יחסי ל-$n$.

2. לאחר שבחרת $a$, מצא את המעריך $r$ כך ש-$a^r \equiv 1 (mod~n)$. זה מרמז ש-$a^r - 1 \equiv 0 (mod~n)$. קיומו של מעריך $r$ כך שמתקיימת הקונגרואנציה לעיל מובטח על ידי תכונת התקופתיות של החזקה המודולרית.

3. אם $r$ הוא זוגי, $a^r - 1 \equiv 0 (mod~n) \implies (a^{r/2} - 1) (a^{r/2} + 1) = \gamma*n$ עבור מספר שלם כלשהו $\gamma$. הצד השמאלי של השוויון האחרון חייב להכיל את $p$ ו-$q$ כשניים מהגורמים הראשוניים שלו מכיוון שהצד הימני מכיל אותם. אם $r$ הוא אי-זוגי, חזור לשלב 1 ונסה בחירה שונה של $a$.

4. השתמש באלגוריתם אוקלידס המורחב למציאת $gcd((a^{r/2} - 1), n)$ או $gcd((a^{r/2} + 1), n)$. ה-GCD המחושב סביר מאוד לזהות אחד מהגורמים הראשוניים $p$ או $q$. חלק את $n$ בגורם ראשוני זה כדי לשחזר את האחר.

5. לאחר שנודעו $p, q$, השתמש בצעדים מאלגוריתם RSA המקורי לשחזור הטוטיינט $\phi(n)$ ולייצור מספר המפתח הפרטי $d$ כההופכי המודולרי של מספר המפתח הציבורי הידוע $e$.

באוגוסט 2023 Oded Regev פרסם שיפור על הגרסה המקורית של שור תוך שימוש בגישה רב-ממדית שמביאה ל-$O(n^{1.5})$. ממשיכים להיות מחקרים נוספים בתחום זה כולל על ידי Ragavan ו-Vaikuntanathan שעשויים לשפר את הזמן, העלות, או מספר ה-Qubit הנדרשים. אמנם לא ניתן לומר מתי הפעלת אלגוריתמים כאלה נגד הצפנת RSA אמיתית הופכת ממשית, אך זה הולך ומתקרב כל הזמן.

דוגמת Python המדגימה שבירת הצפנת RSA

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

הערה

בחלק זה נראה את חישובי המתמטיקה בפירוט כחלק מקוד ה-Python

בדוגמה, יש לנו מפתח ציבורי $(5, 247)$, ונשחזר את המפתח הפרטי.

שלב 1: הצעד הראשון הוא לבחור מספר ראשוני יחסי ל-247. כמעט כל מספר שנבחר יעשה את העבודה. בואו נבחר 6.

n = 247  # the modulus
e = 5  # public key number
a = 6  # an integer coprime to n
assert gcd(a, n) == 1
print(f"Checked {n} and {a} are coprime")

שלב 2: לאחר מכן עלינו למצוא את התקופה $r$ כך ש-$6^r \equiv 1 (mod~247)$. בדוגמה זו, אנחנו מחשבים את $r$ קלאסית באמצעות כוח גס, אבל יכולנו גם להשתמש באלגוריתם של שור במחשב קוונטי באמצעות Qiskit.

r = 0
rem = 100
while rem != 1:
    r += 1
    rem = (a**r) % n

print(f"period r is: {r}")
assert a**r % n == 1

print(f"Checked {a}^{r} mod {n} is 1")

שלב 3: מכיוון שהתקופה $r = 36$ זוגית, אנחנו יכולים לחשב $f1 = (a^{r/2}-1), f2=(a^{r/2}+1)$.

# explicitly use as integer
f1 = int(a ** (r / 2) - 1)
f2 = int(a ** (r / 2) + 1)

print(f"f1 = {f1}")
print(f"f2 = {f2}")

שלב 4: מצא את ה-GCD של אחד מהגורמים האלה עם $n$. פשוט חלק את $n$ בגורם הראשוני שכבר נמצא כדי לקבל את הגורם הראשוני השני.

q_found = gcd(f1, n)
print(f"One possible prime factor of n ({n}) is: {q_found}")

# explicit int (to avoid floating point)
p_found = int(n / q_found)
print(f"The second prime factor of n ({n}) is: {p_found}")

assert n == p_found * q_found

שלב 5: לאחר שחזור הגורמים הראשוניים של $n = 247$ כ-$p_{found}=13$ ו-$q_{found}=19$, אנחנו מחשבים את הטוטיינט $\phi_{found} = (p_{found}-1)*(q_{found}-1)$.

המפתח הפרטי הוא ההופכי המודולרי של מספר המפתח הציבורי $e=5$.

# Compute the totient
phi_found = (p_found - 1) * (q_found - 1)
print(f"The totient is: {phi_found}")

# Recover the private key number d_found by satisfying (d_found * e) % phi_found = 1
d_found = 1
while True:
    if (d_found * e) % phi_found == 1:
        break
    else:
        d_found += 1
print("Private Key number:", d_found)

בשיטה לעיל, שלב 2 הוא פעולת מציאת התקופה המכרעת שעבורה האלגוריתם של שור משתמש בשני פרימיטיבים קוונטיים בסיסיים, כלומר הטרנספורמציה של פורייה הקוונטית ואומדן הפאזה הקוונטי. להסבר מפורט של ההיבטים הקוונטיים של האלגוריתם של שור, ראה את שיעור אומדן הפאזה והפירוט לגורמים ביסודות אלגוריתמים קוונטיים. שלבים 1 ו-3 עד 5 כוללים פעולות זולות יחסית שניתן לבצע בקלות במחשבים קלאסיים.

אופציונלית, הנה הדרכה חזותית מפורטת של מימוש האלגוריתם של שור.

במחשבים קוונטיים, האלגוריתם של שור יכול להציג סקאלביליות פולי-לוגריתמית נוחה כמו $O((log~n)^2 (log~log~n))$ מבחינת המודולוס $n$, או סקאלביליות פולינומיאלית מבחינת מספר הסיביות הנדרשות לייצוג $n$. זוהי האצה על-פולינומיאלית בהשוואה לאלגוריתם GNFS הקלאסי.

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

חילופי מפתחות Diffie-Hellman ואלגוריתם החתימה הדיגיטלית

בחלק הקודם דנו במערכת ההצפנה RSA, שאבטחתה מבוססת על הקושי החישובי של פירוק לגורמים ראשוניים. כאן נדון בשני פרוטוקולים פופולריים של הצפנת מפתח אסימטרי, חילופי מפתחות Diffie-Hellman (DH) ואלגוריתם החתימה הדיגיטלית (DSA), שניהם מבוססים על בעיה מתמטית שונה, כלומר בעיית הלוגריתם הדיסקרטי (DLP).

בעיית הלוגריתם הדיסקרטי

במשוואה הבאה עלינו למצוא את $a$ בהינתן רק $e$, $M$, $c$

$a^e$ $mod$ $M = c$

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

זה ידוע כבעיית הלוגריתם הדיסקרטי (DLP).

פרטים מתמטיים של בעיית הלוגריתם הדיסקרטי

ה-DLP מוצגת בדרך כלל בהקשר של חבורות מחזוריות ומנוסחת כדלקמן.

שקול חבורה מחזורית $G$ הנוצרת על ידי איבר חבורה $g \in G$ ובהינתן איבר שרירותי $h \in G$, מצא מספר שלם $k$ כך ש-$h = g^{k}$.

כאן המספר השלם $k \equiv log_{g}h$ הוא הלוגריתם הדיסקרטי. התכונה המחזורית של $G$ מבטיחה שעבור כל $h$, קיים מספר שלם $k$ תקף.

להצפנה, ה-DLP על החבורה הכפלית של מספרים שלמים מודולו מספר ראשוני $p$, המסומנת $(\mathbb{Z}_p)^{\times}$, מתגלה כשימושית. איברי $(\mathbb{Z}_p)^{\times}$ הם מחלקות קונגרואנציה המסומנות על ידי מספרים שלמים מודולו $p$ שהם ראשוניים יחסית ל-$p$.

לדוגמה:

$(\mathbb{Z}_5)^{\times} = \{[1],[2],[3],[4]\}~\mathrm{and}~(\mathbb{Z}_7)^{\times} = \{[1],[2],[3],[4],[5],[6]\}$

פעולת הכפל $(\times)$ על חבורות אלה היא פשוט כפל מספרים שלמים רגיל ואחריו צמצום מודולו $p$, והחזקה במספר שלם $k$ היא פשוט כפל חוזר $k$ פעמים וצמצום מודולו $p$.

בואו נדגים דוגמה של DLP על $(\mathbb{Z}_7)^{\times}$.

לחבורה הכפלית הזו יש שני מחוללים ${[3],[5]}$ הידועים גם כשורשים פרימיטיביים. נשתמש ב-$[5]$ כמחולל; כלומר, נייצר כל איבר של $(\mathbb{Z}_7)^{\times}$ באמצעות חזקות מספריות עוקבות של 5.

#Generate elements of (Z_7)^{x} using generator [5].
g = 5
p = 7
print(f"Using generator {g}")
for k in range(3*p):
    print(f"{g}**{k} mod {p} ≡ {(g**k)%7}")

אנחנו רואים שבחשבון מודולו 7, העלאת 5 לחזקות מספריות עוקבות מניבה כל איבר של $(\mathbb{Z}_7)^{\times}$ בדיוק פעם אחת לפני שהמחזור חוזר ללא הגבלה עם תקופה $p-1 =6$.

לכן DLP על $(\mathbb{Z}_7)^{\times}$ עם מחולל [5] הוא:

$\mathrm{Given}~h \in (\mathbb{Z}_7)^{\times} \mathrm{, find~} k \mathrm{~such~that~} 5^{k} \equiv h~(mod~7)$.

מפלט תא ה-Python לעיל אנחנו רואים ש:

$h = 2 \implies k=4 \mathrm{~or~} 4 = log_5(2) (mod~7)$

$h = 6 \implies k=3 \mathrm{~or~} 3 = log_5(6) (mod~7)$

בחשבון המספרים הממשיים הרגיל, החזקה היא פונקציה מונוטונית ומציאת הלוגריתם של כל מספר לכל בסיס היא קלה חישובית. לעומת זאת, כפי שנראה ברור מהדוגמה הפשוטה של $(\mathbb{Z}_7)^{\times}$ לעיל, החזקה המודולרית היא לא-מונוטונית, ואף שהיא תקופתית עם תקופה $p-1$, היא לא טריוויאלית אחרת. לכן חישוב ההיפוך שלה, הלוגריתם הדיסקרטי, מתברר כלא יעיל עבור $p$ גדול במחשבים קלאסיים.

תצפית זו עומדת בבסיס חילופי המפתחות Diffie-Hellman (DH) ואלגוריתם החתימה הדיגיטלית (DSA), המדוברים בחלק הבא.

ניתן להרחיב את ה-DLP לתתי-חבורות מחזוריות כדלקמן:

• שקול $(\mathbb{Z}_p)^{\times}$ שהוגדרה לעיל ואיבר $g \in (\mathbb{Z}_p)^{\times}$ מסדר ראשוני $r$, כלומר $g^r \equiv 1 (~mod~p)$.
• קבוצת החזקות השלמות של $g$: $\{g^k~(mod~p) | 1 \le k \le r\} = \langle g \rangle$ היא תת-חבורה מחזורית של $(\mathbb{Z}_p)^{\times}$ עם סדר חבורה $r$.
• ניתן לציין DLP על $\langle g \rangle$ על ידי בחירת $h \in \langle g \rangle$ ושאלה אחרי $1 \le a \le r$ כך ש-$g^a~(mod~p) = h$

חילופי מפתחות Diffie-Hellman

ב-1976, Whitfield Diffie ו-Martin Hellman הציעו פרוטוקול חילופי מפתחות כדי לאפשר יצירת מפתח סוד משותף על ערוצי תקשורת לא מאובטחים. מפתח הסוד יכול לשמש לאחר מכן את הצדדים החולקים אותו להצפנה סימטרית. האלגוריתם מסתמך על ה-DLP.

איור 1. חילופי מפתחות Diffie-Hellman

Mathematical details of Diffie-Hellman key exchange

כאשר Alice ו-Bob הם שני הצדדים המתקשרים, הפרוטוקול פועל כדלקמן:

• ראשית, Alice ו-Bob מסכימים על מספר ראשוני גדול $p$ ועל שורש פרימיטיבי או מחולל $a$.
• לאחר מכן, Alice בוחרת מעריך סודי $k_A$ באקראי עם $1 \le k_A \le p-2$ ומחשבת $h_A = a^{k_A}~(mod~p)$. $k_A, h_A$ הם המפתח הפרטי והציבורי של Alice בהתאמה.
• לאחר מכן, Bob בוחר מעריך סודי $k_B$ באקראי עם $1 \le k_B \le p-2$ ומחשב $h_B = a^{k_B}~(mod~p)$. $k_B, h_B$ הם המפתח הפרטי והציבורי של Bob בהתאמה.
• לאחר מכן, Alice שולחת ל-Bob את $h_A$ ו-Bob שולח ל-Alice את $h_B$ על ערוץ אמין אך לא בהכרח מאובטח.
• לאחר מכן, Alice משתמשת ב-$h_B$ שקיבלה כדי לחשב את מפתח הסוד המשותף $\kappa = h_B^{k_A}~(mod~p)$.
• לבסוף, Bob בינתיים משתמש ב-$h_A$ שקיבל כדי לחשב את מפתח הסוד המשותף $\kappa = h_A^{k_B}~(mod~p)$.

עם פרוטוקול זה,

• מובטח ש-Alice ו-Bob יסיימו עם אותו מפתח סוד $\kappa$ מכיוון ש-$h_B^{k_A}~(mod~p) = (a^{k_B})^{k_A}~(mod~p) = a^{k_A k_B}~(mod~p) = (a^{k_A})^{k_B}~(mod~p) = h_A^{k_B}~(mod~p)$.
• צד שלישי שמיירט את $h_A$ או $h_B$ לא יכול לבנות את מפתח הסוד $\kappa$ כיוון שאין לו גישה ל-$k_B$ או $k_A$ בהתאמה.
• חילוץ $k_A$ או $k_B$ באמצעות המידע הציבורי $a$, $p$, $h_A$ ו-$h_B$ הוא קשה חישובית מכיוון שהוא שקול לפתרון ה-DLP על $(\mathbb{Z}_p)^{\times}$.

איור של פרוטוקול Diffie-Hellman ב-Python

בואו נסתכל על דוגמה פשוטה של פרוטוקול DH ב-Python תוך שימוש במספרים ראשוניים קטנים:

הערה

בחלק זה נראה את חישובי המתמטיקה בפירוט כחלק מקוד ה-Python

שלב 1: Alice ו-Bob מסכימים על ראשוני $p$ ושורש פרימיטיבי $a$. בואו נבחר $p=11, a=7$.

# Step 1: Choose a prime `p` and a primitive root `a`
p = 11
a = 7

print(f"prime: {p}")
print(f"primitive root: {a}")

שלבים 2, 3: Alice בוחרת מעריך סודי $k_A$ ומחשבת $h_A = a^{k_A}~(mod~p)$. באופן דומה, Bob בוחר מעריך סודי $k_B$ ומחשב $h_B = a^{k_B}~(mod~p)$.

k_A = 4  # Alice's private key
h_A = (a ** (k_A)) % p  # Alice's public key

print(f"Alice's private key is {k_A} and public key is {h_A}")

k_B = 8  # Bob's private key
h_B = (a ** (k_B)) % p  # Bob's public key

print(f"Bob's private key is {k_B} and public key is {h_B}")

שלב 4: שני הצדדים משדרים את מפתחותיהם הציבוריים $h_A$ ו-$h_B$.

שלבים 5, 6: כל צד משלב את המפתח הפרטי שלו עם המפתח הציבורי של הצד השני כדי ליצור את מפתח הסוד המשותף.

secret_key_alice = h_B**k_A % p
secret_key_bob = h_A**k_B % p
assert secret_key_alice == secret_key_bob
print(f"The shared secret key is: {secret_key_bob}")

Alice ו-Bob יכולים כעת להשתמש במפתח הסוד המשותף להצפנה סימטרית.

אבטחת חילופי מפתחות Diffie-Hellman

כפי שצוין לעיל, אבטחת DH מבוססת על הקושי החישובי בפתרון ה-DLP עם ראשוניים גדולים $p$. ביישומים טיפוסיים, NIST ממליץ על מספרים ראשוניים של 2048 או 3072 סיביות עבור חילופי מפתחות DH, הנחשבים מאובטחים מספיק מפני ניסיונות לפתור את ה-DLP באמצעות מחשבים קלאסיים.

התקפות Man-in-the-middle (MITM): העובדה ש-DH הוא תוכנית אינטראקטיבית שבה הסוד המשותף תלוי בשילוב המפתח הפרטי של צד אחד עם המפתח הציבורי של הצד השני הופכת אותו לפגיע לתקיפה הנקראת Man-in-the-middle (MITM).

Mathematical details of DH security and MITM attacks

בתרחיש זה, צד שלישי — נניח, Eve — מיירטת את המפתחות הציבוריים $h_A, h_B$ במהלך השידור ומחליפה את המפתח הציבורי שלה $h_E$ עבור כל אחד מ-$h_A$ ו-$h_B$ לפני העברתם ל-Bob ול-Alice בהתאמה.

לאחר מכן, במקום להשתמש ב-$h_B$ ליצירת הסוד המשותף שלה, Alice תשתמש ב-$h_E$ בחשבה שהיא משתמשת במפתח הציבורי של Bob. באופן דומה, במקום להשתמש ב-$h_A$ ליצירת הסוד המשותף שלו, Bob ישתמש ב-$h_E$ בחשבו שהוא משתמש במפתח הציבורי של Alice.

מכיוון ש-$h_E$ שימש ליצירת הסוד המשותף של Alice (Bob), טקסט רגיל שהוצפן על ידי Alice (Bob) ניתן לפענוח על ידי Eve.

לפיכך, חילופי מפתחות DH משמשים בדרך כלל בשילוב עם אלגוריתם חתימה דיגיטלית כדי להבטיח שכל צד משתמש במפתח ציבורי מאומת ליצירת הסוד המשותף שלו.

אלגוריתם החתימה הדיגיטלית (DSA)

למרות שמערכות הצפנה כלליות כמו RSA מספקות פונקציונליות של חתימה דיגיטלית, ב-1994 אימץ NIST סכמת חתימה ייעודית המבוססת על חזקה מודולרית ועל בעיית הלוגריתם הדיסקרטי כסטנדרט הפדרלי לחתימות דיגיטליות. סכמה זו, שנודעה פשוט בשם אלגוריתם החתימה הדיגיטלית (DSA), כוללת ארבעה שלבים נפרדים:

1. יצירת מפתחות:

   מפתחות DSA נוצרים מ:

   • 2 מספרים ראשוניים העומדים בכללים מסוימים
     • $p$ - בדרך כלל 256 סיביות (נקרא לאורך זה $N$)
     • $q$ - בדרך כלל 3072 סיביות (נקרא לאורך זה $L$)
   • פונקציית גיבוב קריפטוגרפית שתמיר מחרוזות באורך $L$ ל-$N$
   • פרמטר נוסף $g$ (ראו פרטים להלן)

   מכאן בוחרים מספר אקראי $x$ כמפתח פרטי, ומסוגלים לחשב מפתח ציבורי $y$

   Mathematical details of key generation

   • יצירת פרמטרים: מבחינה מתמטית, DSA עוסק בתת-חבורה ציקלית של $(\mathbb{Z}_p)^{\times}$ המיוצרת על ידי איבר $g$ בסדר ראשוני q < p. הצעד הראשון ב-DSA הוא לכן לבחור שני מספרים ראשוניים p, q להקמת המבנים המתמטיים הדרושים.

     • בחר מספר ראשוני $q$ בן $N$ סיביות.
     • בחר מספר ראשוני $p$ בן $L$ סיביות כך ש-$p-1$ הוא מכפלה של $q$. הבחירה של $p$ מגדירה את החבורה $(\mathbb{Z}_p)^{\times}$
     • בחר מספר שלם $1 < h < p-1$ באקראי וחשב $g = h^{(p-1)/q}~mod~p$. אם $g=1$ דבר שקורה לעיתים נדירות, נסה $h$ אחר.
     • ודא ש-$g^q~mod~p = 1$. כך $g$ הוא מחולל של תת-חבורה ציקלית $\langle g \rangle$ של $(\mathbb{Z}_p)^{\times}$ בסדר ראשוני q.

     הפרמטרים $(q, p, g)$ מגדירים מופע של האלגוריתם והם מידע ציבורי. בדרך כלל, $N \sim 256$ ו-$L \sim 3072$ ביישומים מציאותיים.

     הפרוטוקול דורש גם פונקציית גיבוב קריפטוגרפית $H : \{0,1\}^L \rightarrow \{0, 1\}^N$ הממירה מחרוזות בינאריות בנות $L$ סיביות למחרוזות בנות $N$ סיביות, לדוגמה, SHA-256.

   • יצירת זוג מפתחות: החותם צריך לייצר זוג מפתחות בצדו שלו.

     • בחר מספר שלם סודי אקראי $x \in \{1,2...q-1\}$. $x$ הוא המפתח הפרטי.
     • צור $y = g^{x}~mod~p$. $y$ הוא המפתח הציבורי של החותם.

2. הפצת מפתחות:

   המידע הבא משותף עם כל מי שרוצה לאמת חתימה

   • הפרמטרים המשומשים $(p,q,g)$ המתארים את האלגוריתם
   • פונקציית הגיבוב $H$
   • המפתח הציבורי $y$

3. חתימה:

   • החותם יכול עכשיו לחתום על הודעה $m$. החתימה המתקבלת היא $(r,s)$
   • ההודעה והחתימה נשלחות עכשיו לנמען
   Mathematical details of signing a message

   החותם חותם על הודעה $m$ כך:

   • בחר מספר שלם סודי k באקראי מ-$\{1,2...q-1\}$
   • חשב $r = (g^k~mod~p)~mod~q$. במקרה הנדיר שבו $r=0$, נסה k אקראי אחר.
   • חשב $s = (k^{-1} (H(m) + xr))~mod~q$. במקרים נדירים אם $s=0$, נסה k אקראי אחר.
   • החתימה היא הצמד $(r, s)$.
   • החותם משדר את ההודעה $m$ וכן את החתימה $(r,s)$ לאימות.

   מאחר ש-$r, s$ שניהם מספרים שלמים, מודולו $q$ גודל החתימה הוא בסדר גודל של $N$ סיביות ולא $L$ הארוכות יותר.

4. אימות:

   הנמען רוצה עכשיו לאמת את אותנטיות השולח. יש לו גישה למידע הציבורי $(q, p, g, H, y, (r,s), m)$ הוא יכול לבצע חישוב שמוכיח שלשולח הייתה גישה למפתח הפרטי $x$

   ומבקש לקבוע שהחותם הוא מישהו עם גישה למפתח הפרטי $x$.

   Mathematical details of DSA verification scheme

   • ודא ש-$0 \lt r \lt q$ ו-$0 \lt s \lt q$, כלומר, $r, s$ הם מספרים שלמים תקינים מודולו~q.
   • חשב $w = s^{-1}~mod~q$.
   • חשב $u_1 = H(m)w~mod~q$.
   • חשב $u_2 = rw~mod~q$.
   • חשב $v = (g^{u_1}y^{u_2}~mod~p)~mod~q$.
   • החתימה מאומתת אם $v = r$.

   לחתימות לגיטימיות, נכונות אלגוריתם DSA ניתן להדגים בקלות כדלהלן:

   • מצד החותם: $s = (k^{-1} (H(m) + xr))~mod~q \implies k = ((H(m) + xr)s^{-1})~mod~q$
   • בהתחשב בצד הימני של השוויון האחרון, המאמת יכול לחשב $s^{-1}, H(m)$ מכיוון ש-$s, q, m, H$ הם מידע ציבורי.
   • לכן, המאמת מחשב $w = s^{-1}~mod~q$ ו-$u_1 = H(m)w~mod~q = H(m)s^{-1}~mod~q$.
   • המאמת מחשב גם $u_2 = rw~mod~q = rs^{-1}~mod~q$ שכן $r$ הוא גם ציבורי.
   • שים לב ש-$k = (u_1 + xu_2)~mod~q$.
   • עם זאת, למאמת אין גישה ל-$x$ מאחר שהוא המפתח הפרטי של החותם, ולכן לא ניתן לחשב את $k$ ישירות. - הסכמה מסתמכת על כך שגם אם המאמת לא יכול לחשב את $k$, עם חותם לגיטימי, המאמת אמור לדעת לחשב מחדש $(g^k~mod~p)~mod~q = r$ בעזרת המפתח הציבורי של החותם $y = g^{x}~mod~p$.
   • לכן, המאמת מחשב $v = (g^{u_1}y^{u_2}~mod~p)~mod~q = (g^{u_1}g^{xu_2}~mod~p)mod~q = (g^{u_1+xu_2}~mod~p)mod~q = (g^k~mod~p)mod~q$.
   • השוויון האחרון נובע מכך ש-$g$ מסדר $q$ ומוכיח ש-$v = r$ עבור חתימות תקינות.

המחשה של DSA בפייתון

בדוגמה זו, נשתמש בראשוניים קטנים כדי להדגים את תהליך ה-DSA בתרחיש שבו אליס שולחת הודעה חתומה לבוב. נשתמש בשלמים קטנים בדוגמה זו. תרחיש מהעולם האמיתי ישתמש בראשוניים גדולים הרבה יותר בסדר גודל של 2048-3072 סיביות.

הערה

אפשר לנסות להריץ מחדש את הדוגמה הזו עם ערכים שונים כדי לראות כיצד האלגוריתם מתנהג, אבל יש לוודא שמתחילים להריץ מהתא הראשון בסעיף זה.

נתחיל בייבוא הספריות הדרושות ובבחירת הפרמטרים שלנו. הפרמטרים השלמים $p$, $q$, $g$ הם מידע ציבורי ועומדים בכללים הבאים:

• $p$, $q$ שניהם ראשוניים
• $(p-1) \mod\ q = 0$
• $g \ge 2$
• $g \le (p-2)$
• $g^{(p-1)/q} \mod\ p \neq 1$

from random import randint

# parameter generation: select the primes q, p and generator g:
# EXPERIMENT with the values, they must meet certain rules
# this example code does not verify p,q are prime

q = 11
p = 23
g = 4

assert (p - 1) % q == 0
assert g >= 2
assert g <= (p - 2)
assert (pow(g, (p - 1) / q) % p) != 1

print(f"Public information is good: q={p}, p={q}, g={g}")

עכשיו החותמת, אליס, מייצרת את המפתח הפרטי שלה.

המפתח הפרטי, k (‏alice-private-key בקוד הפייתון) חייב לעמוד בדרישות:

• $k \ge 2$
• $k \le (q-1)$

# Alice chooses an integer randomly from {2..q-1}
# EXPERIMENT with the values

alice_private_key = randint(2, q - 1)
# alice_private_key =

assert alice_private_key >= 2
assert alice_private_key <= (q - 1)

print(f"Alice's private key is {alice_private_key}")

אליס שומרת את המפתח הפרטי שלה בסוד.

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

מהסבר המתמטיקה למעלה, אנחנו יודעים שניתן לחשב זאת באמצעות הנוסחה:

$y = g^{x} \mod\ p$

alice_public_key = pow(g, alice_private_key, p)
# Alternatively can use (g ** alice_private_key) % p

print(f"Alice's public key is {alice_public_key}")

כרגיל, אליס מפרסמת את המפתח הציבורי שלה בערוץ שאינו חייב להיות סודי.

עכשיו אליס יכולה לחתום על הודעה.

לצורך סכמת החתימה הדיגיטלית, עלינו לייצר גיבוב $H(m)$ של ההודעה $m$ שייחתם.

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

hash_dict = {}

def mock_hash_func(input_message):
    print(input_message)
    if input_message not in hash_dict:
        hash_dict[input_message] = randint(1, q)
    return hash_dict[input_message]

alice_message = "Inspection tomorrow!"
alice_hash = mock_hash_func(alice_message)  # In reality, you'd use a hash function
print(f"Alice's message hash is: {alice_hash}")

בשלב הבא, אליס צריכה לייצר מספר סוד אקראי לכל הודעה $k$ וכן את ההופכי הכפלי שלו מודולו $q$ כדי לחשב את החתימה.

ניתן להשתמש באלגוריתם brute-force פשוט לחישוב ההופכי המודולרי. עם זאת, עדיף להשתמש באחת מהפונקציות המובנות של פייתון pow כפי שמוצג להלן

# brute-force implementation to find modular inverse
def modular_inverse(k, q):
    for i in range(0, q):
        if (k * i) % q == 1:
            return i
    print(f"error! no inverse found! for {k},{q}")
    return 0

# Let's compare this algorithm with the standard python 'pow' function

n1 = modular_inverse(3, 7)
n2 = modular_inverse(4, 11)
n3 = modular_inverse(7, 5)
m1 = pow(3, -1, 7)
m2 = pow(4, -1, 11)
m3 = pow(7, -1, 5)

assert n1 == m1
assert n2 == m2
# assert(n3==m3)

print(f"modular_inverse(3,7) = {m1}")
print(f"modular_inverse(4,11) = {m2}")
print(f"modular_inverse(7,5) = {m3}")

# Some numbers don't have modular inverses - our function throws an error
n4 = modular_inverse(2, 6)

# The python library will throw an exception, which must be caught
if math.gcd(2, 6) == 1:
    m4 = pow(2, -1, 6)
else:
    print("Exception from pow() - no modular inverse found!")

עכשיו אליס יכולה לחשב את החתימה.

• $r = (g^{k} \mod p) \mod\ q$
• $s = (k^{-1} (H(m) + xr)) \mod q$

שים לב שיש תנאים מסוימים שיחייבו אותנו לבחור ערך שונה ל-$k$ במקרה שבו $r$ או $s$ מחושבים כ-$0$. במקרה זה נייצר ערך חדש ונחזור על התהליך.

# Start an infinite loop; we will 'break' out of it once a valid signature is found.
while True:
    k = randint(1, q - 1)  # Should be different for every message
    print("Using random k =", k)

    r = pow(g, k, p) % q
    # If r is 0, the value is invalid. Try again with a new k.
    if r == 0:
        print(f"{k} is not a good random value to use to calculate r. Trying another k")
        continue

    s = (pow(k, -1, q) * (alice_hash + alice_private_key * r)) % q
    # If s is 0, the value is also invalid. Try again with a new k.
    if s == 0:
        print(f"{k} is not a good random value to use to calculate s. Trying another k")
        continue

    # If we've reached this point, both r and s are valid. Break the loop.
    signature = (r, s)
    print(f"Alice's signature is : {(r,s)}")
    break

# After the loop, the valid r and s values can be used here.
# print(f"Generated Signature -> r: {r}, s: {s}")

אליס משדרת את ההודעה ואת חתימתה לנמען או לאמת, בוב.

בוב קיבל בעבר את המפתח הציבורי של אליס ועכשיו יכול לאמת את החתימה כדי לאמת את הודעתה.

לשם כך, הוא מבצע כמה בדיקות, ואז מייצר מחדש גיבוב של ההודעה המשודרת של אליס ומחשב את הכמויות העזר $w, u_1, u_2$ ו-$v$.

• $0 < r < q$
• $0 < s < q$
• $w = s^{-1} \mod\ q$
• $u_{1} = H(m) . w \mod\ q$
• $u_{2} = r . w \mod\ q$
• $v = (g^{u1}y^{u2} \mod\ p) \mod\ q$

לבסוף, בוב בודק אם $v$ שווה ל-$r$. אם הם שווים, החתימה מאומתת.

# Bob re-generates message hash using Alice's broadcast message
bob_hash = mock_hash_func(alice_message)

# Bob computes auxiliary quantities w (using modular inverse), u1, u2 and v
w = (pow(s, -1, q)) % q
u1 = (bob_hash * w) % q
u2 = (r * w) % q
v = ((g**u1 * alice_public_key**u2) % p) % q

if v == r:
    print("Signature is valid!")
else:
    print("Signature is invalid!")

אבטחת ה-DSA

עם מחשוב קלאסי, אבטחת ה-DSA יכולה להיות מושפעת ממספר גורמים:

1. גודל מפתח: כתמיד, גודל המפתח מספק הגנה בסיסית מפני התקפות כוח גס. יישומים מודרניים המשתמשים ב-DSA משתמשים בגדלי מפתח של לפחות 2048 סיביות.

2. איכות $k$: ב-DSA, כל חתימה זקוקה לערך $k$ ייחודי, אקראי וסודי (ראו לעיל). הייחודיות, האנטרופיה והסודיות של $k$ הן קריטיות, וחולשה בכל אחד מהיבטים אלה עלולה להוביל לפגיעה במפתח הפרטי $x$. גנרטורי המספרים האקראיים המשמשים ליצירת $k$ צריכים להיות מאובטחים בעצמם.

3. חוזק פונקציית הגיבוב: מכיוון ש-DSA משתמש בפונקציית גיבוב כחלק מתהליך יצירת ואימות החתימה, פונקציית גיבוב חלשה עלולה לפגום באבטחת החתימה הדיגיטלית. לדוגמה, השימוש ב-SHA-1 עם DSA אינו מומלץ עוד, ומומלץ להשתמש ב-SHA-2 או גרסה מאוחרת יותר.

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

החלפת מפתחות מאומתת עם Diffie-Hellman ו-DSA

פרוטוקולי אבטחת רשת מודרניים, כגון Transport Layer Security (TLS) ורבים אחרים, כוללים שילוב של פונקציות החלפת מפתחות ואימות. בהקשר של Diffie-Hellman, אימות נדרש כדי להגן מפני התקפות MITM. בתאים הבאים של הקוד, אנחנו ממחישים דוגמה שבה אליס ובוב מבצעים החלפת מפתחות מאומתת על ידי שילוב פרוטוקולי Diffie-Hellman ו-DSA. לשם כך, נשתמש בספריית Python ‏cryptography.

איור 2. החלפת מפתחות מאומתת עם Diffie-Hellman ו-DSA ראשית, אליס ובוב מסכימים על קבוצת פרמטרי DH ומייצרים זוגות מפתחות ציבוריים-פרטיים של DH.

# import necessary library modules
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import dh, dsa

# Generate DH parameters
parameters = dh.generate_parameters(generator=2, key_size=2048)

# Generate Alice's DH private key and public key
alice_dh_private_key = parameters.generate_private_key()
alice_dh_public_key = alice_dh_private_key.public_key()

# Generate Bob's DH private key and public key
bob_dh_private_key = parameters.generate_private_key()
bob_dh_public_key = bob_dh_private_key.public_key()

print("Public and private keys generated for Bob and Alice")

המפתחות הציבוריים של DH מופצים לכולם. לאחר מכן, גם אליס וגם בוב מייצרים בנפרד זוג מפתחות לשימוש עם DSA. מפתחות אלה ישמשו בתורם לחתימה על המפתחות הציבוריים של DH שיוחלפו.

# Generate DSA keys for Alice and Bob
alice_dsa_private_key = dsa.generate_private_key(key_size=2048)
alice_dsa_public_key = alice_dsa_private_key.public_key()
bob_dsa_private_key = dsa.generate_private_key(key_size=2048)
bob_dsa_public_key = bob_dsa_private_key.public_key()

print("Additional key pair generated for signing")

אליס חותמת על המפתח הציבורי שלה ב-DH באמצעות המפתח הפרטי שלה ב-DSA.

# Alice signs
alice_public_bytes = alice_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
alice_signature = alice_dsa_private_key.sign(alice_public_bytes, hashes.SHA256())

print("Alice signed public key")

באופן דומה, בוב חותם על המפתח הציבורי שלו ב-DH באמצעות המפתח הפרטי שלו ב-DSA.

bob_public_bytes = bob_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
bob_signature = bob_dsa_private_key.sign(bob_public_bytes, hashes.SHA256())

print("Bob signed public key")

המפתחות הציבוריים של DH והחתימות המתאימות מופצים כעת על ידי אליס ובוב. לאחר שכל אחד קיבל את המפתח הציבורי והחתימה של הצד השני, כל צד מאמת שהחתימה תקפה. כך ניתן למנוע התקפת MITM, כיוון שאליס, למשל, יודעת שהמפתח הציבורי של בוב ב-DH אכן נחתם על ידי בוב, ולהפך.

# Alice and Bob verify each other's DH public keys using DSA public keys
# An InvalidSignature exception will occur if they are not valid
alice_dsa_public_key.verify(alice_signature, alice_public_bytes, hashes.SHA256())
bob_dsa_public_key.verify(bob_signature, bob_public_bytes, hashes.SHA256())

print("Signatures are valid")

לאחר אימות החתימה, אליס ובוב מייצרים את הסוד המשותף, שמשלים את החלפת המפתחות.

# Perform key exchange
alice_shared_key = alice_dh_private_key.exchange(bob_dh_public_key)
bob_shared_key = bob_dh_private_key.exchange(alice_dh_public_key)

print("Shared secrets generated")

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

# Derive a shared symmetric key using key-stretching
def derive_key(shared_key):
    return HKDF(
        algorithm=hashes.SHA256(),
        length=32,
        salt=None,
        info=None,
    ).derive(shared_key)

alice_symmetric_key = derive_key(alice_shared_key)
bob_symmetric_key = derive_key(bob_shared_key)

assert alice_symmetric_key == bob_symmetric_key
print("Keys checked to be the same")

שבירת Diffie-Hellman ו-DSA

גם פרוטוקול Diffie-Hellman (DH) וגם DSA כוללים יצירת מפתחות ציבוריים בצורה $y = g^{x}~mod~p$, כאשר המפתח הפרטי $x$ הוא הלוגריתם הדיסקרטי.

תוקף שיכול לפתור מופע של ה-DLP יכול לחשוף את המפתח הפרטי של אחד משני הצדדים ו, על ידי שילובו עם המפתח הציבורי של הצד השני, לקבל גישה לסוד המשותף. במקרה של DSA, תוקף שיכול לפתור את ה-DLP יכול לשחזר את המפתח הפרטי של החותם, ובכך לבטל את ההנחה הבסיסית של חתימה דיגיטלית.

במחשבים קלאסיים, מאמינים ש-DLP אין לו פתרון בזמן פולינומי. אך כפי שהראה Peter Shor במאמרו המקורי מ-1994, אלגוריתם שור פותר גם את ה-DLP בזמן פולינומי על מחשבים קוונטיים.

אלגוריתם שור ובעיית הלוגריתם הדיסקרטי

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

Mathematical details of Shor's algorithm

אלגוריתם שור מספק פתרון יעיל ל-DLP על ידי מיפויו לבעיה כללית יותר בתורת החבורות המכונה בעיית תת-החבורה הנסתרת (HSP).

ב-HSP, נתונה חבורה אלגברית $G$ ופונקציה $f: G \rightarrow X$ מ-$G$ לאיזשהו קבוצה $X$ כך ש-$f$ קבועה על כל חוצן של תת-חבורה $H$ של $G$ (ושונה על חוצנים שונים). המשימה היא לקבוע את $H$. ידוע שמחשבים קוונטיים יכולים לפתור את ה-HSP על חבורות אבליות סופיות בזמן פולינומי ב-$log~|G|$ כאשר $|G|$ הוא סדר החבורה.

במקרה של ה-DLP השלמים שנדון בשיעור זה, המיפוי ל-HSP הוא כדלהלן:

• יהי $p$ ראשוני ונביט ב-DLP הנתון על ידי $y = g^r~mod~p$ כאשר $g$ הוא גנרטור של $(\mathbb{Z}_p)^{\times}$. מכיוון ש-$g^{p-1} \equiv 1~mod~p$, ל-$g$ יש סדר $p-1$.
• נבחר $G = \mathbb{Z}_{p-1} \times \mathbb{Z}_{p-1}$ כאשר $\mathbb{Z}_{p-1}$ היא חבורת השלמים מודולו $(p-1)$.
• נבחר $f : G \rightarrow (\mathbb{Z}_p)^{\times}$ הנתון על ידי $f(a, b) = g^a y^{-b}~mod~p \equiv g^{a-rb}~mod~p$ .
• הגרעין של $f$ הוא אז תת-החבורה $H_0 = \langle (r, 1) \rangle = \{(a,b) \in G | f(a,b) \equiv 1~mod~p\} = \{ (a, b) \in G | a - rb \equiv 0~mod~(p-1)\}$.
• $f$ קבועה על החוצנים $(\delta, 0) + H_0$ ו"מסתירה" את תת-החבורה $H_0$ ומגדירה HSP.

בהתחשב באמור לעיל, אלגוריתם הקוונטי של שור ל-DLP השלמים משתמש ב-oracle קוונטי להערכת הפונקציה $f$ על מצב המייצג סופרפוזיציה אחידה על $G$, ולאחר מכן משתמש בטרנספורם פורייה הקוונטי ומדידות עם אמידת פאזה כדי לייצר מצבים קוונטיים המאפשרים זיהוי הגנרטור $(r, 1)$ של $H_0$. מתוך כך ניתן לחלץ את $r$, הלוגריתם הדיסקרטי שמעניין אותנו.

המאמר המקורי של שור מכיל תיאור מפורט של האלגוריתם.

קריפטוגרפיית עקומות אליפטיות

קריפטוגרפיית עקומות אליפטיות (ECC), המבוססת על המתמטיקה של עקומות אליפטיות, מציעה גישה חזקה לקריפטוגרפיית מפתח א-סימטרי. ידוע ש-ECC מספקת רמת אבטחה דומה לשיטות כגון RSA אך עם מפתחות קצרים יותר, מה שהופך אותה ליעילה יותר ומתאימה במיוחד למערכות עם משאבים מוגבלים, כגון מערכות משובצות ומכשירים ניידים, שבהם חיסכון האחסון והחישוב של גדלי מפתח קטנים יותר הם רצויים מאוד.

עקרונות בסיסיים של קריפטוגרפיית עקומות אליפטיות

עקומה אליפטית היא בדרך כלל בצורה $y^2 = x^3 + ax + b$ עם כמה תכונות מעניינות.

• היא סימטרית אופקית. לכן עבור כל נקודה $(x,y)$ על העקומה, השיקוף שלה $(x,-y)$ נמצא גם הוא על העקומה
• כל קו ישר לא אנכי יחתוך את העקומה בלכל היותר שלוש נקודות

איור 1. פעולות חיבור והכפלת נקודה על עקומה אליפטית. פאסט 1 מגדיר P + Q = -R. פאסט 2 ממחיש הכפלת נקודה 2Q = -P. פאסט 3 מגדיר את ההופכי החיבורי של נקודה כשיקופה לגבי ציר ה-x, כלומר, P = -Q

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

Mathematical principles of elliptic curve cryptography

עקומה אליפטית מעל שדה אלגברי $K$ מוגדרת על ידי משוואה מתמטית, בדרך כלל בצורה $y^2 = x^3 + ax + b$ עם המקדמים $a, b \in K$ ומתארת נקודות $(x, y) \in K \otimes K$ עם הדרישה הנוספת שלעקומה לא יהיו עיקולים או נקודות עצמיות.

תכונות העקומות האליפטיות מאפשרות הגדרת פעולות "חיבור" ו"כפל סקלרי" הכוללות נקודות על העקומה.

חיבור: אם $P$ ו-$Q$ הן שתי נקודות על עקומה אליפטית, אז $P + Q$ מתאר נקודה שלישית ייחודית המזוהה כדלהלן: נצייר את הקו החותך את $P$ ואת $Q$ ונמצא את הנקודה השלישית, $R$, שבה הקו חותך שוב את העקומה. לאחר מכן מגדירים $P + Q = −R$, הנקודה הנגדית ל-$R$ המשוקפת דרך ציר ה-$x$ (ראו איור למטה). כאשר הקו דרך $P, Q$ אינו חותך את העקומה בשום $(x, y)$ סופי, אנחנו אומרים שהוא חותך את העקומה בנקודה באינסוף $\mathbf{O}$.

חיבור עקומות אליפטיות מקיים תכונות חבורה אלגבריות עם הנקודה באינסוף כזהות החיבורית.

הכפלה וכפל סקלרי: פעולת הכפלת נקודה, המתאימה לכפל סקלרי ב-$2$, מתקבלת על ידי הצבת $P = Q$ בפעולת החיבור, ומבחינה גרפית כוללת את הקו המשיק ב-$P$. כפל סקלרי כללי במספר שלם $n$ המוגדר כ-$nP = P + P + ...~n$ פעמים מתקבל על ידי הכפלות וחיבורים חוזרים.

בעיית הלוגריתם הדיסקרטי של עקומות אליפטיות

לבעיית הלוגריתם הדיסקרטי של עקומות אליפטיות (ECDLP) יש הרבה דמיון לבעיית הלוגריתם הדיסקרטי שנדונה קודם לכן, שכן שתיהן מבוססות על קשיי מציאת גורמים.

פעולת כפל סקלרי על עקומות אליפטיות מאפשרת הגדרת בעיית הלוגריתם הדיסקרטי של עקומות אליפטיות:

בהינתן נקודות $P, Q$ על עקומה אליפטית כך ש-$Q = nP$, קבע את $n$.

בעיה זו ידועה כבלתי אפשרית לפתרון במחשבים קלאסיים עבור $n$ גדול ומספקת בסיס לאבטחה קריפטוגרפית.

Mathematical description of ECDLP

קריפטוגרפיית עקומות אליפטיות מבוססת בעיקר על ECDLP המנוסח על שדות סופיים אלגבריים מסוימים. ב-1999 המליצה NIST על עשרה שדות סופיים לשימוש ב-ECC. אלה הם:

• חמישה שדות ראשוניים $\mathbb {F} _{p}$ עבור ראשוניים $p$ בגודל $\{192, 224, 256, 384, 521\}$ סיביות.
• חמישה שדות בינאריים $\mathbb {F} _{2^{n}}$ עבור $n \in \{163, 233, 283, 409, 571\}$.

עם ההגדרה לעיל, מערכת קריפטוגרפיה א-סימטרית מבוססת ECC במקרה של שדות ראשוניים ניתן לפרט כדלהלן:

• נבחר $p$ מרשימת הערכים המומלצת של NIST כדי לציין את $\mathbb {F} _{p}$.

• נבחר פרמטרים $a, b$ של העקומה האליפטית.

• נבחר נקודת בסיס $G$ ש"מייצרת" תת-חבורה מחזורית על העקומה עם סדר $n$; כלומר, המספר השלם הקטן ביותר כך ש-$nG = \mathbf{O}$.

• נחשב את המקדם $h = |E(\mathbb {F} _{p})|/n$ כאשר $|E(\mathbb {F} _{p})|$ הוא מספר הנקודות על העקומה. $h$ הוא בדרך כלל מספר שלם קטן.

• פרמטרי התחום $(p, a, b, G, n, h)$ מאפשרים ציון מפתחות א-סימטריים בדרך הבאה:

  • המפתח הפרטי הוא מספר שלם $d$ שנבחר באקראי עם כמה סיביות כמו בראשוני $p$. יש לשמור עליו בסוד.
  • המפתח הציבורי הוא תוצאת "כפל" נקודת הבסיס $G$ במפתח הפרטי $d$. זה מסומן בדרך כלל כ-$Q = dG$.

שחזור $d$ שווה ערך לפתרון ה-ECDLP, שנחשב בלתי אפשרי עבור $d$ גדול. ה-ECDLP מהווה לכן את הבסיס לסכמות חילופי מפתחות וחתימות דיגיטליות באנלוגיה ישירה לסכמות Diffie-Hellman ו-DSA המוגדרות מעל $(\mathbb{Z}_p)^{\times}$ שנדונו קודם.

החלפת מפתחות עם ECC

אחד השימושים העיקריים של ECC הוא בפרוטוקול החלפת מפתחות המכונה Diffie-Hellman של עקומות אליפטיות (ECDH). ב-ECDH, כל צד מייצר זוג מפתחות פרטי-ציבורי ולאחר מכן מחליף מפתחות ציבוריים. כל צד משתמש אז במפתח הפרטי שלו ובמפתח הציבורי של הצד השני כדי לחשב סוד משותף, שניתן להשתמש בו כמפתח להצפנה סימטרית.

בעוד שקל יחסית לבצע חיבור נקודות על עקומה אליפטית ולגזור מפתח ציבורי ממפתח פרטי, בלתי אפשרי מבחינה חישובית להפוך את התהליך ולגזור מפתח פרטי ממפתח ציבורי. התנהגות "חד-כיוונית" זו מספקת את אבטחת החלפת מפתחות ה-ECDH.

כאן נמחיש דוגמה לביצוע החלפת מפתחות ECDH באמצעות Python וספריית cryptography.

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import hashes

# Each party generates a private key
private_key1 = ec.generate_private_key(ec.SECP384R1())
private_key2 = ec.generate_private_key(ec.SECP384R1())

# They exchange public keys
public_key1 = private_key1.public_key()
public_key2 = private_key2.public_key()

# Each party uses their own private key and the other party's public key
# to derive the shared secret
shared_key1 = private_key1.exchange(ec.ECDH(), public_key2)
shared_key2 = private_key2.exchange(ec.ECDH(), public_key1)

# The shared secrets are the same
assert shared_key1 == shared_key2
print("Keys checked to be the same")

חתימות דיגיטליות עם ECC

ניתן להשתמש ב-ECC גם ליצירת חתימות דיגיטליות באמצעות אלגוריתם החתימה הדיגיטלית של עקומות אליפטיות (ECDSA). ב-ECDSA, החותם יוצר חתימה באמצעות המפתח הפרטי שלו, ואחרים יכולים לאמת את החתימה באמצעות המפתח הציבורי של החותם. בדיוק כמו עם ECDH, אבטחת ECDSA מסתמכת על ה-ECDLP. בלתי אפשרי מבחינה חישובית למישהו לזייף חתימה ללא גישה למפתח הפרטי של החותם.

להלן דוגמה לעסקת חתימה ואימות פשוטה באמצעות ECDSA עם Python ו-cryptography.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import ec

# Generate a private key for use in the signature
private_key = ec.generate_private_key(ec.SECP384R1())

message = b"A message to be signed"

# Sign the message
signature = private_key.sign(message, ec.ECDSA(hashes.SHA256()))

# Anyone can verify the signature with the public key
public_key = private_key.public_key()

def check_ecdsa_signature(public_key, signature, message):
    try:
        public_key.verify(signature, message, ec.ECDSA(hashes.SHA256()))
        return True
    except InvalidSignature:
        return False

if check_ecdsa_signature(public_key, signature, message):
    print("The signature is valid.")
else:
    print("The signature is invalid.")

בקוד לעיל, אם משנים את ההודעה לאחר שנחתמה, האימות ייכשל, ומספק ערובה לאמינות ולשלמות ההודעה.

שבירת ECDH ו-ECDSA

באופן אנלוגי לבעיית הלוגריתם הדיסקרטי של השלמים, ה-ECDLP מתברר כקשה במחשבים קלאסיים אך יש לו פתרון יעיל במחשבים קוונטיים שוב דרך אלגוריתם שור. אנחנו מפנים אתכם לספרות עדכנית לדיון הנוגע להכללת אלגוריתם שור למקרה ה-ECDLP.

סיכום

בשיעור זה, התחלנו בבחינת המאפיינים העיקריים של קריפטוגרפיית מפתח א-סימטרי (AKC) ודנו בשיקולי אבטחה בסיסיים העומדים בבסיס מערכות הצפנה א-סימטריות. בפרט, הצגנו את שני היישומים העיקריים של AKC — כלומר, החלפת מפתחות וחתימות דיגיטליות — שניהם מרכיבים חיוניים של תקשורת מודרנית מבוססת אינטרנט.

לאחר מכן בחנו את מערכת ההצפנה RSA, שמאז שנות ה-70 הוכיחה את ערכה האדיר לאבטחת תקשורת דיגיטלית מודרנית על ידי מתן אפשרות לחילופי מפתחות וחתימות דיגיטליות במסגרת פשוטה ורב-תכליתית. האבטחה הקריפטוגרפית של RSA ביחס למחשוב קלאסי מבוססת על קושי פירוק מספרים שלמים גדולים לגורמים, ודורשת גדלי מפתח בטווח של 2048 סיביות כדי להבטיח שהמספרים השלמים המשמשים ביישומים מעשיים גדולים מספיק כדי לעמוד בפני פירוק לגורמים.

לאחר מכן בחנו את חילופי המפתחות של Diffie-Hellman (DH) ואת אלגוריתם החתימה הדיגיטלית (DSA). אבטחת סכמות אלה מבוססת על בעיית הלוגריתם הדיסקרטי השלמי (DLP), כאשר המפתח הפרטי קשה חישובית לחילוץ בהינתן המפתח הציבורי, ללא פתרון בזמן פולינומי על מחשבים קלאסיים. שימוש במפתחות אקראיים וייחודיים מספק אבטחה נוספת מפני התקפות. גם השדה הסופי של שלמים וגם הגרסאות של עקומות אליפטיות של פרוטוקולי DH ו-DSA נמצאות כיום בשימוש נרחב ברבים מפרוטוקולי תקשורת דיגיטלית מודרניים כגון TLS, SSH, ועוד.

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

כל האלגוריתמים הללו חשופים להתקפה מאלגוריתמים קוונטיים, שכן ניתן לפתח פתרונות לפתרון הבעיות המתמטיות שהיוו הנחת יסוד בעיצובם. דוגמה אחת לכך היא אלגוריתם שור. לכן יהיה צורך להחליפם במערכות הצפנה א-סימטריות בטוחות קוונטית שיהיו עמידות יותר בפני התקפות קוונטיות — תוך שמירה על אבטחה גם מול אלגוריתמים קלאסיים. הבעיות המתמטיות שעליהן הם מסתמכים יכולות להיפתר ביעילות על ידי מחשבים קוונטיים, מה שמחייב פיתוח מערכות הצפנה א-סימטריות בטוחות קוונטית שיכולות לעמוד בפני התקפות קוונטיות תוך שמירה על אבטחה קלאסית.