מפתח ציבורי

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

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

יעילות

חסרונן העיקרי של מרבית שיטות המפתח הציבורי הוא במשאבי המחשוב הנדרשים ליישומן. לרוב נדרשת עוצמת חישוב גבוהה עשרת מונים בהשוואה להצפנה סימטרית, בעיקר בגלל הצורך באריתמטיקה מודולרית במספרים ארוכים מאוד. בעוד שבהצפנה סימטרית קונבנציונלית, הדרך כמעט היחידה לפיצוח אלגוריתמים סימטריים בטוחים היא באמצעות כוח גס, או במקרה הטוב באמצעות ניתוח סטטיסטי של כמות עצומה של מידע מוצפן שבדרך כלל אינו מעשי. הרי שבהצפנה אסימטרית קיימים אלגוריתמים טובים היעילים בהרבה מכח גס לפתרון הבעיות המתמטיות עליהן נשענת המערכת. לדוגמה 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. במקביל מצפין את מפתח השיחה באמצעות המפתח הציבורי של המקבל ואם עליו להוסיף חתימה דיגיטלית, מגבב את המסר באמצעות פונקציית גיבוב קריפטוגרפית וחותם על הערך המגובב באמצעות מפתח החתימה הפרטי שלו. את כל זה, קרי המסר המוצפן, מפתח השיחה המוצפן והחתימה, שולח יחד למקבל. המקבל בתורו פועל בסדר הפוך של האירועים: מחלץ את מפתח השיחה הסודי באמצעות המפתח הפרטי המתאים שברשותו - ביכולתו לעשות זאת כיוון שמפתח השיחה הוצפן עבורו באמצעות המפתח הציבורי שלו. מפענח את המסר המוצפן, מפיק ערך גיבוב מהמסר באמצעות פונקציית גיבוב זהה לזו שהשתמש בה השולח ובודק באמצעות מפתח האימות הציבורי של השולח, כי החתימה אותנטית ובכך מבטיח כי המסר לא שונה בדרך. פרוטוקול SSL פועל בדרך דומה, תחילה הלקוח מאמת את זהותו מול השרת בד בבד עם שיתוף מפתח שיחה חד פעמי באמצעות פרוטוקול שיתוף מפתח כמו דיפי-הלמן ואז מצפין את כל תעבורת הרשת בינו לבין השרת עם מפתח השיחה באמצעות צופן סימטרי מהיר.

היסטוריה

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