מפתח ציבורי

הצפנת מפתח ציבורי (Public key encryption) היא ענף בקריפטוגרפיה הנקרא גם הַצְפָּנָה אָסִימֶטְרִית (Asymmetric encryption), שבו מפתח ההצפנה שונה ממפתח הפענוח. כלומר, כל משתמש מכין לעצמו זוג מפתחות: מפתח ציבורי (Public key) שהוא מפתח הצפנה הנגיש לכל ומפתח פרטי (Private key) מתאים, הנשמר בסוד ומשמש לפענוח. ההתאמה היא חד-חד-ערכית ועל (לכל מפתח ציבורי קיים אך ורק מפתח פרטי יחיד המתאים לו, ולהפך)^[1][2]. כדי להצפין מסר בשיטה זו על המצפין להשיג לידיו עותק אותנטי של המפתח הציבורי של המקבל, שבעזרתו הוא מצפין ושולח לו את המסר. רק המקבל מסוגל לשחזר את הטקסט המוצפן בעזרת המפתח הפרטי המתאים שברשותו. ביטחון שיטת המפתח הציבורי נשען על הקושי שבחישוב המפתח הפרטי מתוך המפתח הציבורי. מסיבה זו מכונה שיטה זו "אסימטרית", בניגוד לשיטת הצפנה סימטרית, שבה מפתח הפענוח זהה למפתח ההצפנה (על כל פנים ניתן לחישוב בקלות מתוך מפתח ההצפנה).

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

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

תרשם כללי של מערכת מפתח ציבורי

הגדרה בסיסית

כל מערכת הצפנת מפתח ציבורי מכילה מספר פרמטרים בסיסיים. לצורך ההסבר, מקובל לכנות את השולח והמקבל אליס ובוב ואיב היא מצותתת פסיבית, ייתכנו גורמים נוספים כמו קרול או מלורי שלהם "תפקידים" שונים בהתאם לנושא. בתיאור זה אליס היא השולחת ובוב המקבל. ${\displaystyle {\mathcal {M}}}$ מייצג את מרחב כל המסרים האפשריים מהם אליס מעוניינת לשלוח מסר אחד ${\displaystyle m}$ לבוב, בסימון מתמטי ${\displaystyle m\in {\mathcal {M}}}$. מרחב המסרים יכול להיות מקודד בכל דרך מוסכמת כמו מחרוזת בינארית או מספר שלם ובלבד שתהיה דרך קלה ומסוכמת להמיר את המסר לפורמט המתאים למערכת ההצפנה ובחזרה. המסר המוצפן המתקבל שייך למרחב המסרים המוצפנים של המערכת המסומן ב-${\displaystyle {\mathcal {C}}}$ או בקיצור ${\displaystyle c\in {\mathcal {C}}}$. (ברוב המקרים המרחבים חופפים כך שמתקיים ${\displaystyle |{\mathcal {C}}|=|{\mathcal {M}}|}$ אך אין זה חובה). מה שמייחד מערכת אסימטרית הוא מרחב המפתח ${\displaystyle {\mathcal {K}}}$ של בוב, שבניגוד למערכת סימטרית מורכב למעשה משני מפתחות, מפתח פרטי המסומן ב-${\displaystyle k_{\text{priv}}}$ ומפתח ציבורי מתאים ${\displaystyle k_{\text{pub}}}$. באופן פורמלי:

${\displaystyle (k_{\text{priv}},k_{\text{pub}})\in {\mathcal {K}}}$

המפתח הציבורי ${\displaystyle k_{\text{pub}}}$ משמש את פונקציית ההצפנה ${\displaystyle e}$ כך:

${\displaystyle e_{k_{\text{pub}}}:{\mathcal {M}}\longrightarrow {\mathcal {C}}}$.

במילים, פונקציית ההצפנה ${\displaystyle e}$ היא פונקציה חד-כיוונית שיכולה להיות גם פונקציה הסתברותית, המקבלת את ${\displaystyle m}$ ואת ${\displaystyle k_{\text{pub}}}$, מצפינה את ${\displaystyle m}$ ומחזירה את הטקסט המוצפן ${\displaystyle c}$. במקרה של הצפנה הסתברותית נוסף לתהליך ההצפנה אלמנט אקראי כך שבכל פעם שמצפינים את ${\displaystyle m}$ יתקבל ${\displaystyle c}$ אחר, אפילו אם המפתח זהה.

באופן דומה המפתח הפרטי ${\displaystyle k_{\text{priv}}}$ משמש את פונקציית הפענוח ${\displaystyle d}$ כך:

${\displaystyle d_{k_{\text{priv}}}:{\mathcal {C}}\longrightarrow {\mathcal {M}}}$.

פונקציית הפענוח ${\displaystyle d}$ היא פונקציה דטרמיניסטית המבצעת את הפעולה ההפוכה, היא מקבלת את ${\displaystyle c}$ ואת המפתח הפרטי ${\displaystyle k_{\text{priv}}}$ ומשחזרת את ${\displaystyle m}$ המקורי. עבור כל מפתח ציבורי קיים אך ורק מפתח פרטי יחיד המתאים לו וכמו בכל מערכת הצפנה כדי שהיא תקרא שלמה; בהינתן כל זוג מפתחות תואם ${\displaystyle (k_{\text{priv}},k_{\text{pub}})\in {\mathcal {K}}}$ וכל מסר ${\displaystyle m\in {\mathcal {M}}}$ צריך תמיד להתקיים:

${\displaystyle d_{k_{\text{priv}}}(e_{k_{\text{pub}}}(m))=m}$.

לפי עקרונות מערכת הצפנה מודרנית מקובל שפונקציות ההצפנה והפענוח אינן סודיות והן ידועות לכל, הדבר היחידי שנשמר בסוד הוא מפתח הפענוח. ומעל הכול כדי שמערכת כזו תקרא בטוחה, חובה שיהיה "קשה מאוד" לאויב לחשב את מפתח הפענוח הפרטי ${\displaystyle k_{\text{priv}}}$ מתוך מפתח ההצפנה הציבורי ${\displaystyle k_{\text{pub}}}$ הידוע לכל. ולכן יהיה קשה מאוד לחשב את פונקציית הפענוח ${\displaystyle d_{k_{\text{priv}}}(c)}$ בהינתן המידע המתקבל מפונקציית ההצפנה ${\displaystyle e_{k_{\text{pub}}}(m)}$.

ישנם כמה מודלים תאורטיים להערכת ביטחון מערכת הצפנה אסימטרית. באופן לא פורמלי בביטוי "קשה מאוד" מתכוונים שניסיון לנחש את המפתח הפרטי מתוך המפתח הציבורי עם מיטב האלגוריתמים הידועים יהיה בסיבוכיות גבוהה מעבר ליכולת המחשוב הנוכחית עם שולי ביטחון מניחים את הדעת. זו תכונה יסודית של מערכת הצפנה אסימטרית ומכאן נובע שמה. מסיבה זו המקבל בוב יכול לשלוח לאליס ללא חשש את מפתח ההצפנה באמצעות ערוץ תקשורת פתוח שניתן לציתות על ידי כל אחד. הדרך היחידה לפענח מסר שהוצפן עבור בוב עם המפתח הציבורי שלו היא לדעת מהו מפתח הפענוח ${\displaystyle k_{\text{priv}}}$ המתאים שברשותו. ההנחה היא שרק בוב יודע מהו כי הוא נשמר בסוד ולעולם אינו נשלח ברשת פתוחה. המפתח הפרטי נקרא מהיבט תאורטי "דלת צונחת" מכיוון שהוא מאפשר קיצור דרך למקבל כדי לחשב את הפונקציה ההופכית של פונקציית ההצפנה החד-כיוונית ולפענח את המסר המוצפן ביעילות.

בתרשים למעלה מתוארת מערכת מפתח ציבורי טיפוסית: בוב מכין זוג מפתחות ${\displaystyle k_{\text{priv}},k_{\text{pub}}}$. את המפתח הציבורי ${\displaystyle k_{\text{pub}}}$ הוא שולח לאליס ואת ${\displaystyle k_{\text{priv}}}$ הוא שומר בסוד. כעת אליס מצפינה את המסר ${\displaystyle m}$ עבור בוב באמצעות הפונקציה ${\displaystyle c=e_{k_{\text{pub}}}(m)}$ ואילו בוב משחזר את הטקסט המוצפן באמצעות ${\displaystyle m=d_{k_{\text{priv}}}(c)}$. איב שהיא מצותתת פאסיבית המסוגלת לראות את תעבורת הרשת, רואה את ${\displaystyle k_{\text{pub}}}$ (שנשלח על ידי בוב) ואת ${\displaystyle c}$ (שנשלח על ידי אליס). אולם ההנחה היא שאיב תוכל לפענח את הטקסט המוצפן ${\displaystyle c}$ רק בידיעת ${\displaystyle k_{\text{priv}}}$. כיוון ש-${\displaystyle k_{\text{priv}}}$ מעולם לא שודר, ביכולתה רק לנחשו בכוח גס כלומר ניסוי כל האפשרויות שברוב המכריע של המקרים, אם המפתח מספיק גדול, אינו בר ביצוע מבחינה מעשית.

ביטחון

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

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

לדוגמה, הפונקציה:

${\displaystyle {\boldsymbol {f(x)=x^{2}\mathbf {\ (mod\ } pq)}}}$

כאשר ${\displaystyle p}$ ו-${\displaystyle q}$ הם שני ראשוניים גדולים, היא כנראה הדוגמה הטובה ביותר לפונקציה חד-כיוונית עם דלת צונחת. אפשר להשתמש בה להצפנה פשוט על ידי העלאה בריבוע של המסר ונטילת השארית לאחר חילוק ב-${\displaystyle pq}$. קל לראות שבעוד שהעלאה בחזקה היא פעולה קלה הרי שהפעולה ההפוכה, בהינתן ${\displaystyle y}$ למצוא ${\displaystyle x}$ המקיים ${\displaystyle y\equiv x^{2}{\mbox{ (mod }}pq)}$, קרי הוצאת שורש ריבועי מודולו שלם פריק היא בעיה קשה (למעשה עליה מבוססת הצפנת רבין). דלת הסתרים במקרה זה היא הגורמים הראשוניים ${\displaystyle p}$ ו-${\displaystyle q}$ שכן ידוע שהוצאת שורש ריבועי מודולו מספר ראשוני היא פעולה קלה ומכאן הדרך לפתרון קלה כי אפשר לשלב את הפתרונות לשורשים הריבועיים של הגורמים הראשוניים ${\displaystyle p}$ ו-${\displaystyle q}$ ובאמצעות משפט השאריות הסיני לקבל ארבעה פתרונות אפשריים לשורש ריבועי מודולו ${\displaystyle pq}$ מהם המקבל צריך לבחור את הפתרון הנכון.

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

תשתית מפתח ציבורי

ערך מורחב – PKI

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

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

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

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

X.509

ערך מורחב – X.509

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

רשת אמון (Web of trust)

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

תקני הצפנת מפתח ציבורי

תקן הצפנת מפתח ציבורי של מעבדות RSA הנקרא PKCS (קיצור של Public Key Cryptography Standard) מכיל אוסף מפרטים לתקנים שונים הקשורים בהצפנת מפתח ציבורי שחלקם אומצו על ידי ארגוני תקינה בינלאומיים כמו ANSI X9 או ISO. הסדרה PKCS נמצאת בפיתוח מתמיד עקב ההתקדמות הטכנולוגית והחידושים הרבים בתחום ההצפנה. להלן תקציר הגרסאות:

מספר סידורי	תיאור
PKCS #1	אלגוריתם RSA (כולל תקנים #2 ו-#4)
PKCS #3	פרוטוקול דיפי-הלמן
PKCS #5	תקן קריפטוגרפי לפרוטוקול מבוסס סיסמה
PKCS #6	תקן לתחביר מתקדם של תעודת מפתח ציבורי
PKCS #7	תקן למבנה מסר קריפטוגרפי
PKCS #8	תקן למבנה מפתח פרטי
PKCS #9	מאפיינים שונים
PKCS #10	תקן לתחביר בקשת תעודת מפתח ציבורי
PKCS #11	ממשק לאסימון קריפטוגרפי
PKCS #12	תקן לפורמט קובץ המכיל מידע קריפטוגרפי
PKCS #13	תקן הצפנת מפתח ציבורי בעקום אליפטי
PKCS #15	תקן לפורמט אסימון קריפטוגרפי.

יעילות

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

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

אימות

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

אורך מפתחות מומלץ

הבעיה במערכות הצפנה אסימטריות התלויות בקושיין (התאורטי/חישובי) המשוער של בעיות מתורת המספרים, בראשן בעיית פירוק לגורמים היא שאף על פי שהן קשות לפתרון, קיימים עבורן אלגוריתמים טובים בסיבוכיות זמן נמוכה משמעותית מכוח גס. מסיבה זו רצוי שמפתחות ההצפנה יהיו גדולים במידה ניכרת כדי להשוות את רמת בטיחותן לאלגוריתמים סימטריים. עד שנת 2003, מקובל היה להשתמש במודולוס בגודל 1024 סיביות. מעבדות RSA פרסמה בשנת 2003 הצהרה, לפיה מפתח אסימטרי בגודל 1024 סיביות מספק רמת הגנה מקבילה למפתח סימטרי בגודל 80 סיביות, 2048 סיביות מקבילות לאלגוריתם סימטרי עם מפתח 112 סיביות ו-3072 סיביות מקביל ל-128 סיביות. המלצה שלהם להשתמש במפתח 2048 סיביות לשימוש רגיל ו-3072 סיביות לשימוש מיוחד במקרים קיצוניים, זאת עד לשנת 2030. ארגון התקינה NIST נוקט בגישה מחמירה מעט יותר, לפי תקן NIST Special Publication 800-57 נכון ליולי 2012 מפתח אסימטרי בגודל 3072 סיביות מקביל ברמת בטיחותו למפתח סימטרי בגודל 128 סיביות (שהוא מהסוג הנפוץ כיום באלגוריתם AES) ואילו לרמת בטיחות גבוהה, מפתח בגודל 15,360 סיביות יהווה מקבילה בטיחותית ראויה למפתח סימטרי בגודל 256 סיביות.

הדברים אמורים לגבי כל סוגי ההצפנה האסימטרית כולל חתימה דיגיטלית כגון DSA המבוססת על בעיית הלוגריתם הבדיד, זאת בשל ההערכה כי בעיית לוגריתם בדיד דומה בקושיה לבעיית פירוק לגורמים. יוצא מן הכלל הוא מערכת ההצפנה בעקום אליפטי (ECC). תקן FIPS PUB 186-4 שנכלל בערכת ההצפנה Suite B של NSA, מגדיר מפתח בגודל 256–384 סיביות המקביל לרמה של 128 סיביות באלגוריתם סימטרי, להצפנת מסמכים עבור הממשל האמריקאי ברמה של SECRET ואילו לרמה של TOP SECRET מומלץ 512 סיביות ומעלה. באופן כללי ההנחיה של NIST היא שמפתח ECC יהיה בערך כפול בגודלו ממפתח סימטרי. הערכה זו מניחה כי לא ידועה פריצת דרך משמעותית לפתרון הבעיה המתמטית עליה מבוססת ECC זאת כיוון שהאלגוריתמים הידועים מנצלים תכונות מסוימות של שדה המספרים עליו בנוי האלגוריתם ושדות ECC שונים באופיים במידה ניכרת כך שהם אינם ישימים בהם.

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

מערכת היברידית

צד השולח

צד המקבל

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

היסטוריה

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

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

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

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

מאז 1970 הומצאו אלגוריתמים נוספים מבוססי מפתח ציבורי, הן להצפנה והן לחתימה דיגיטלית, חלקם התגלה מאוחר יותר כלא בטוח וחלקם לא היה מעשי, כמו הצפנת התרמיל של רלף מרקל ומרטין הלמן המבוססת על בעיית התרמיל. ב-1978 הומצאה הצפנת מקאליס המבוססת על קוד תיקון שגיאות שחסרונה העיקרי הוא בגודל מפתח ההצפנה, ב-1979 פרסם פרופסור מיכאל רבין שיטת הצפנה הנקראת על שמו הצפנת רבין, שיטה מבוססת מפתח ציבורי בדומה ל-RSA הנשענת על בעיית שורש ריבועי מודולו שלם פריק, היכולה לשמש גם כחתימה דיגיטלית. ב-1984 הומצא אלגוריתם אל-גמאל, (על ידי טאהר אלגמאל), המבוסס על בעיית לוגריתם בדיד בדומה לדיפי-הלמן, שיטה זו היוותה בסיס להמצאת אלגוריתם DSA לחתימה דיגיטלית על ידי ממשלת ארצות הברית מספר שנים לאחר מכן. בסוף שנות השמונים ניל קובליץ ובמקביל ויקטור מילר הציגו לראשונה מערכת מפתח ציבורי המבוססת על עקום אליפטי ומכונה בקיצור ECC, למרות היותה מסובכת התפרסמה השיטה בעיקר בזכות מפתח ההצפנה הקצר שהציעה והיא בשימוש כיום במרבית מערכות אבטחת המידע המסחריות. עם המצאת הצפנה הסתברותית ב-1983 התפתח ענף פופולרי של הצפנה בטוחה סמנטית כמו הצפנת בלום-גולדווסר וכן סכימות חדשות כמו הצפנת פאיי.

הצפנה סימטרית מול הצפנה אסימטרית

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

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

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

יתרונות הצפנה סימטרית:

• שיטות סימטריות בדרך כלל מהירות ויעילות, במיוחד בחומרה. בתצורה אופטימלית אפשר להגיע לתפוקה של 10Gbit/s ויותר.
• מפתח הצפנה סימטרי בדרך כלל קצר (128 - 256 סיביות נכון ל-2013).
• הצפנה סימטרית עשירה באלגוריתמים שמספקים מגוון פתרונות קריפטוגרפיים יעילים, כגון: מחוללי מספרים אקראיים, מנגנוני אימות (אימות מסרים ואימות זהויות), הבטחת שלמות וכן ניתנים לשילוב באופן שמגביר את חוסנם.
• לשיטות סימטריות היסטוריה עשירה יותר. הבסיס המתמטי היה ידוע שנים לפני המצאת המחשבים ומרביתן נחקרו היטב במרוצת הזמן, אם כי בעיקר עם המצאת המחשבים. קיימת אף שיטת הצפנה סימטרית הנקראת פנקס חד פעמי, המוכחת כבטוחה מבחינה מתמטית.

חסרונות הצפנה סימטרית:

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

יתרונות מפתח ציבורי

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

חסרונות מפתח ציבורי

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

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

מסיבת חתימה על מפתחות ציבוריים

ערך מורחב – מסיבת חתימה על מפתחות ציבוריים

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

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

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

ראו גם

• RSA
• צופן אל-גמאל

לקריאה נוספת

• סיימון סינג, סודות ההצפנה, הוצאת ידיעות אחרונות, 2003.

קישורים חיצוניים

מדיה וקבצים בנושא מפתח ציבורי בוויקישיתוף

• כתריאל טראום, מבוא ל-GnuPG באתר הפינגווין
• אורנה אגמון, הוראות לעריכת מסיבת חתימת מפתחות ציבוריים באתר כנס אוגוסט פינגווין
• גדי אלכסנדרוביץ', אליס ובוב: ידועים בציבור, באתר "לא מדויק", 21 בנובמבר 2007
• מפתח ציבורי, באתר אנציקלופדיה בריטניקה (באנגלית)
• מפתח ציבורי, באתר MathWorld (באנגלית)

• Whitfield Diffie, Martin E. Hellman, New Directions in Cryptography, IEEE Transactions on Information Theory, 22 (6), November 1976, pp. 644–654
• Martin E. Hellman, The Mathematics of Public-Key Cryptography, Scientific American, Vol. 241, No. 2 (August 1979), pp. 146-157, in JSTOR

הערות שוליים

1. Public Key Cryptography, www.su18.eecs70.org
2. S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, Algorithms, July 18, 2006, עמ' 41-42