מפתח ציבורי

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

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

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

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

הגדרה בסיסית

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

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

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

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

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

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

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

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

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

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

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

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

ביטחון

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

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

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

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

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